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 回答