4

我正在开发井字游戏,我需要算法来检查游戏何时结束(以及谁获胜)。在 3x3 游戏中,我会检查每种可能的获胜情况(有 8 种能力)。但是在 7x7 中(需要连续或列或对角线中的 4 个标志)是很多可能的获胜模式。

4

4 回答 4

38

如果您为每个玩家使用一个板,您可以使用位移操作来测试一个板是否获胜。

位板将具有以下结构:

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的 The Fhourstones Benchmark的资料中看到了这个迷人的功能。

于 2011-08-12T21:15:44.297 回答
4

虽然一个非常基本的方法是查看每个单元格的所有方向的运行,但这里有一种方法,然后只检查单个“行”中的单元格一次。“线”是可能获胜的行、列或对角线,就像在拉斯维加斯老虎机中一样 :)

  1. 对于每个“行”,移动到该“行”的开头,并且;
  2. 将计数器设置为 0。
  3. 对于“行”中的每个单元格(按顺序遍历行):
    • 如果单元格为 P1 且计数器 >= 0,则计数器加一
      • 如果计数器 = 4,则 P1 获胜。
    • 如果单元格为 P1 且计数器为负数,则将计数器设置为 0
    • 如果单元格为 P2 且计数器 <= 0,则从计数器中减 1
      • 如果计数器 = -4 则 P2 获胜
    • 如果单元格为 P2 且计数器为正,则将计数器设置为 0

重要编辑:如果单元格既不包含 P1 也不包含 P2,请将计数器重置为 0(doh!)。我省略了这个微不足道但必需的步骤。否则“11-11”将被视为胜利。

可以在给定起点和每次迭代的行/列偏移量的情况下遍历“线”(例如,从 (0,0) 开始,从 NW 到 SE 的最长对角线前进 (1,1))。当然,长度小于 4 的对角线可以完全避免被检查。

快乐编码。

于 2011-08-12T18:55:42.683 回答
2

循环所有位置。对于每个位置,检查右下对角线和右下角的四个字段(始终包括字段本身)。当您检查不存在的字段时,请进行适当的检查以避免炸毁您的应用程序。

于 2011-08-12T18:32:29.600 回答
0

简单的。for为所有行、列、增加对角线、减少对角线进行4 个循环。在每个中,测试是否有 4 个连续的片段。

于 2011-08-12T21:14:03.983 回答