检查连接四个字段的算法

Question

我想知道在连续四场比赛中检查获胜者的最佳方法是什么。

我很想知道你们是怎么想的，是否有解决这类问题的“知名”算法？

解决方法:

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

我让算法遍历每个字段一次。在我的 Intel(R) Core(TM)2 Duo CPU T9600 @ 2.80GHz 上，我的最佳检查时间是 0.047 毫秒，最差 0.154 毫秒，平均 0.114 毫秒。这足以满足我的需求，而且算法对我来说似乎很简洁。

Answer 1

源代码来自Fhourstones Benchmark来自 John Tromp 的文章使用了一种迷人的算法来测试四连胜游戏的胜负。该算法使用以下 bitboard游戏表示:

.  .  .  .  .  .  .  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;
}

您必须为执行最后一步的玩家的位板调用该函数。 我试着在我的 answer to the question "How to determine game end, in tic-tac-toe?" 中解释算法.