确定井字游戏结束的算法

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

1.棋盘已满，尚未宣布胜负：游戏平局。 2.克罗斯获胜。 3.圆圈获胜。

不幸的是，要做到这一点，它需要从表格中读取一组预定义的情况。考虑到棋盘上只有 9 个空格，因此表格有点小，这并不一定是坏事，但有没有更好的算法来确定游戏是否结束呢？确定某人是否获胜是问题的关键，因为检查 9 个空格是否满是微不足道的。

表格法可能是解决办法，但如果不是，那什么才是呢？另外，如果棋盘的大小不是 "n=9 "呢？如果棋盘大得多，比如n=16、n=25等等，导致连续摆放的棋子数为x=4、x=5等等呢？对所有 n = { 9, 16, 25, 36 ...}?

Nemus
已编辑的问题 3日 五月 2017 в 3:43
编程
java tic-tac-toe algorithm
29日 六月 2009 в 2:18
3 种观点
解决办法

要知道，只有在 X 或 O 下完最近的一步棋后，才有可能走赢，因此在尝试确定胜负棋盘时，只能搜索该步棋中包含的可选对角的行/列，以限制搜索空间。 此外，由于和棋中的步数是固定的，一旦下完最后一步棋，如果这步棋不是胜负手，那么这盘棋就默认为和棋。

编辑：此代码适用于 n×n 棋盘，连下 n 步即可获胜（3x3 棋盘要求连下 3 步，等等）。

编辑：添加了检查反斜线的代码，我想不出一个非循环的方法来确定点是否在反斜线上，所以缺少了这一步

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
        }
    }
}
mbacvanski
编辑本段答案18日 十一月 2017 в 9:31
评论(18)

您可以使用魔法方块 http://mathworld.wolfram.com/MagicSquare.html，如果任何一行、一列或对角线加起来是 15，那么玩家就赢了。

评论(8)

如果棋盘是n × n，那么有_n_行、_n_列和 2 条对角线。检查每条对角线上是否有全 X's 或全 O's，找出赢家。

如果只需要x < _n_个连续的方格就能获胜，那么情况就稍微复杂一些。最明显的解决方法是检查每个 x × x 方块是否有赢家。下面的代码可以证明这一点。

(我并没有实际测试过，但第一次尝试就编译成功了，耶！）。


public class TicTacToe
{
    public enum Square { X, O, NONE }

    /**
     * Returns the winning player, or NONE if the game has
     * finished without a winner, or null if the game is unfinished.
     */
    public Square findWinner(Square[][] board, int lengthToWin) {
        // Check each lengthToWin x lengthToWin board for a winner.    
        for (int top = 0; top
John Kugelman supports Monica
编辑本段答案29日 六月 2009 в 3:36
评论(3)