检查四子连珠场地的算法

Question

检查四子连珠场地的算法

algorithm

16

我想知道在四子棋场上检查赢家的最佳方法是什么。

我很感兴趣你们的想法，是否有一些“众所周知”的算法可以解决这类问题呢？

解决方案：

我用Python实现了Ardavan的哈希表解决方案。

我让算法在每个场地上运行一次。我的实现中最快的检查时间是0.047毫秒，最差的是0.154毫秒，平均为0.114毫秒，在我的Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz上运行。这对我的需求来说已经足够快了，而且这个算法对我来说看起来很整洁。

- naeg

你想要在许多次游戏已经发生之后进行检查，还是逐个检查每一次游戏？ - PengOne

是的，但在游戏进行时检查一步棋比在游戏结束后检查整个棋盘更受限制。 - PengOne

阅读了第一个答案后，我明白你的意思了。我猜更好的方法应该是依次逐个处理，而不是一遍又一遍地处理整个字段。 - naeg

在这种情况下，算法很大程度上取决于您使用的编程语言。如果您的语言支持它，您可以使用：模式匹配、列表推导、旋转、指针等。 - Eelvex

我可能表达不够清晰。所谓的“连接所有字段”，是指连接行中的每个单元格，例如会得到“xxxoooo”。 - naeg

显示剩余3条评论

3个回答

7

每个单元格最多只能归属于12个获胜组合（4个水平方向，4个垂直方向和4个对角线）。每个组合将包括4个单元格，包括正在考虑的那个。而且这些数字对于靠近边缘的单元格来说会低得多。因此，预先编译这些组合并存储相关单元格的哈希值是有意义的，这可以让一个简单的游戏玩家成为赢家。这样，每个单元格被玩家使用后，您只需提取相关的组合/单元格以检查它是否为赢家。

- Ardavan

如果我没有算错的话，总共有69个获胜组合。每一行有4种可能的组合，有6行=>24。每列有3种可能的组合，有7列=>21。每个对角线和反对角线有12个组合=>24。总计69个组合。不确定将它们全部存储在哈希表中是否比手动检查更快？我猜哈希表更快，但我认为我还是要试一下。 - naeg

我已经实现了你的算法，它非常适合我的需求。 - naeg

1

这与以下问题相关：如何找到任意大小的井字棋游戏的赢家？

不同之处在于7x6的棋盘中需要连成4个，而不是NxN棋盘中需要连成N个。但是轻松适应解决方案来连接4个。

编辑：实际上，将其他解决方案调整为此解决方案并不是那么容易。但是您可以进行一些额外的工作来完成它。

对于每行、每列、每条对角线和反对角线，存储每个玩家的计数，它们可以连成4个棋子。当其中一个玩家的计数达到4或更多时，请检查该行/列/对角线/反对角线是否有四个棋子相连。如果是，该玩家获胜！

- MSN

只是为了明确我理解得对：我为每一行、列和对角线创建两个计数器（player1和player2）。如果一个玩家的计数器在一行/列/对角线上达到4，他就赢了。这样正确吗？还是有更好的解决方案？ - naeg

我不明白那个答案与这个问题有什么关系。 - Karoly Horvath

检查四个连续的最佳方法是使用我的字符串方法吗？还是有更好的方法？ - naeg

@naeg，为什么要使用字符串，当你可以计算匹配相邻字段的数量呢？ - MSN

@naeg，如果你认为优雅的定义是“我可以写出没有循环的代码”，那么是的，它很优雅。 - MSN

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christian Ammer · Accepted Answer

从John Tromp的Fhourstones基准测试中获取的源代码使用了一种迷人的算法来测试连接四游戏是否胜利。该算法使用以下比特棋盘表示游戏：

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42  BOTTOM

红色玩家和黄色玩家各有一个位棋盘。 0 表示空单元格，1 表示已填充的单元格。该位棋盘存储在一个无符号 64 位整数变量中。第 6、13、20、27、34、41、≥48 位必须为0。

算法如下：

// return whether 'board' includes a win
bool haswon(unsigned __int64 board)
{
    unsigned __int64 y = board & (board >> 6);
    if (y & (y >> 2 * 6))     // check \ diagonal
        return true;
    y = board & (board >> 7);
    if (y & (y >> 2 * 7))     // check horizontal
        return true;
    y = board & (board >> 8);
    if (y & (y >> 2 * 8))     // check / diagonal
        return true;
    y = board & (board >> 1);
    if (y & (y >> 2))         // check vertical
        return true;
    return false;
}

你需要调用上一个玩家的位棋盘函数。

我在回答"如何确定井字游戏结束?"这个问题时尝试解释了算法。