确定井字游戏结束的算法 [英] Algorithm for Determining Tic Tac Toe Game Over

问题描述

我用 Java 编写了一个井字游戏，我目前确定游戏结束的方法考虑了游戏结束的以下可能情况:

I've written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over:

1. 棋盘已满，尚未宣布获胜者:游戏为平局.
2. Cross 赢了.
3. Circle 赢了.

不幸的是，这样做时，它会从表中读取一组预定义的这些场景.考虑到棋盘上只有 9 个空间，因此桌子有点小，这不一定是坏事，但是有没有更好的算法方法来确定游戏是否结束?确定某人是否获胜是问题的核心，因为检查 9 个空格是否已满是微不足道的.

Unfortunately, to do so, it reads through a predefined set of these scenarios from a table. This isn't necessarily bad considering that there are only 9 spaces on a board, and thus the table is somewhat small, but is there a better algorithmic way of determining if the game is over? The determination of whether someone has won or not is the meat of the problem, since checking if 9 spaces are full is trivial.

table 方法可能是解决方案，但如果不是，那又是什么?另外，如果板的尺寸不是 n=9 怎么办?如果它是一个更大的棋盘，比如 n=16、n=25 等等，导致连续放置的项目获胜的数量是 x=4、x=5 等等?用于所有 n = { 9, 16, 25, 36 ... }?

The table method might be the solution, but if not, what is? Also, what if the board were not size n=9? What if it were a much larger board, say n=16, n=25, and so on, causing the number of consecutively placed items to win to be x=4, x=5, etc? A general algorithm to use for all n = { 9, 16, 25, 36 ... }?

推荐答案

你知道只有在 X 或 O 做出他们最近的一步之后才能获胜，所以你只能搜索包含可选 diag 的行/列在尝试确定获胜板时，此举旨在限制您的搜索空间.此外，由于在进行最后一步棋的棋盘棋游戏中有固定的步数，如果它不是获胜棋步，则默认情况下为平局游戏.

You know a winning move can only happen after X or O has made their most recent move, so you can only search row/column with optional diag that are contained in that move to limit your search space when trying to determine a winning board. Also since there are a fixed number of moves in a draw tic-tac-toe game once the last move is made if it wasn't a winning move it's by default a draw game.

此代码用于 n x n 板，连续 n 获胜(3x3 板需要连续 3 等)

edit: this code is for an n by n board with n in a row to win (3x3 board requries 3 in a row, etc)

添加了检查反诊断的代码，我无法找出一种非循环方式来确定该点是否在反诊断上，所以这就是缺少该步骤的原因

edit: added code to check anti diag, I couldn't figure out a non loop way to determine if the point was on the anti diag so thats why that step is missing

public class TripleT {

    enum State{Blank, X, O};

    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;

    void Move(int x, int y, State s){
        if(board[x][y] == State.Blank){
            board[x][y] = s;
        }
        moveCount++;

        //check end conditions

        //check col
        for(int i = 0; i < n; i++){
            if(board[x][i] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check row
        for(int i = 0; i < n; i++){
            if(board[i][y] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check diag
        if(x == y){
            //we're on a diagonal
            for(int i = 0; i < n; i++){
                if(board[i][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check anti diag (thanks rampion)
        if(x + y == n - 1){
            for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check draw
        if(moveCount == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }
}

这篇关于确定井字游戏结束的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！