在tic-tac-toe中如何确定游戏结束？

Question

我正在开发tic-tac-toe游戏,我需要算法来检查游戏何时结束(谁赢了).在3x3游戏中,我会检查每个可能的胜利情况(有8个功能).但是在7x7中(连续需要4个符号或者是对角线),很多可能的胜利模式.

Answer 1

如果您使用的是棋盘的每个玩家,你可以使用位移位运算来测试板的胜利.

该位板具有以下结构:

6 14 22 30 38 46 54
5 13 21 29 37 45 53
4 12 20 28 36 44 52
3 11 19 27 35 43 51
2 10 18 26 34 42 50
1  9 17 25 33 41 49
0  8 16 24 32 40 48

如果玩家占据游戏板中的位置,那么相关的位将是1另外的0(注意位7,15,23,...... 0).要检查玩家是否有获胜棋盘,您可以使用以下功能:

bool haswon(int64_t board)
{
    int64_t y = board & (board >> 7);
    if (y & (y >> 2 * 7)) // check \ diagonal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8)) // check horizontal -
        return true;
    y = board & (board >> 9);
    if (y & (y >> 2 * 9)) // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))     // check vertical |
        return true;
    return false;
}

在一个例子的帮助下,我将尝试解释:一个玩家的以下位置包括在垂直和对角线旁边赢得第一行中的获胜组合.

0101010
1110111
0111011
1101110
0001000
1010101
0011110 ... four occupied positions --> winning board

水平检查的步骤是:

1. y = board & (board >> 8)

   0101010   0010101   0000000
   1110111   0111011   0110011
   0111011   0011101   0011001
   1101110 & 0110111 = 0100110
   0001000   0000100   0000000
   1010101   0101010   0000000
   0011110   0001111   0001110

2. y & (y >> 2 * 8)

   0000000   0000000   0000000
   0110011   0001100   0000000
   0011001   0000110   0000000
   0100110 & 0001001 = 0000000
   0000000   0000000   0000000
   0000000   0000000   0000000
   0001110   0000011   0000010

水平检查产生一个设置了一位的电路板,这意味着电路板包含一个win并且函数返回true.

我已经使用了类似的功能来检查连接四场比赛的胜利.我在John Tromp 的Fhourstones Benchmark的消息来源中看到了这个令人着迷的功能.