我正在开发井字游戏,我需要算法来检查游戏何时结束(以及谁获胜)。在 3x3 游戏中,我会检查每种可能的获胜情况(有 8 种能力)。但是在 7x7 中(需要连续或列或对角线中的 4 个标志)是很多可能的获胜模式。
4 回答
如果您为每个玩家使用一个位板,您可以使用位移操作来测试一个板是否获胜。
位板将具有以下结构:
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
水平检查的步骤是:
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
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的资料中看到了这个迷人的功能。
虽然一个非常基本的方法是查看每个单元格的所有方向的运行,但这里有一种方法,然后只检查单个“行”中的单元格一次。“线”是可能获胜的行、列或对角线,就像在拉斯维加斯老虎机中一样 :)
- 对于每个“行”,移动到该“行”的开头,并且;
- 将计数器设置为 0。
- 对于“行”中的每个单元格(按顺序遍历行):
- 如果单元格为 P1 且计数器 >= 0,则计数器加一
- 如果计数器 = 4,则 P1 获胜。
- 如果单元格为 P1 且计数器为负数,则将计数器设置为 0
- 如果单元格为 P2 且计数器 <= 0,则从计数器中减 1
- 如果计数器 = -4 则 P2 获胜
- 如果单元格为 P2 且计数器为正,则将计数器设置为 0
- 如果单元格为 P1 且计数器 >= 0,则计数器加一
重要编辑:如果单元格既不包含 P1 也不包含 P2,请将计数器重置为 0(doh!)。我省略了这个微不足道但必需的步骤。否则“11-11”将被视为胜利。
可以在给定起点和每次迭代的行/列偏移量的情况下遍历“线”(例如,从 (0,0) 开始,从 NW 到 SE 的最长对角线前进 (1,1))。当然,长度小于 4 的对角线可以完全避免被检查。
快乐编码。
循环所有位置。对于每个位置,检查右下对角线和右下角的四个字段(始终包括字段本身)。当您检查不存在的字段时,请进行适当的检查以避免炸毁您的应用程序。
简单的。for
为所有行、列、增加对角线、减少对角线进行4 个循环。在每个中,测试是否有 4 个连续的片段。