算法检查连接四个字段

Question

我想知道在连接四场上检查胜利者的最佳方法是什么.

我对你们的想法感兴趣,是否对这类问题有一些"众所周知的"算法？

解:

我在Python中实现了Ardavan的哈希表解决方案.

我让算法在每个字段上运行一次.我的实现的最佳检查时间是0.047毫秒,最差的0.154毫秒和我的英特尔(R)酷睿2双核CPU T9600 @ 2.80GHz上的平均0.114毫秒.这足以满足我的需求,算法看起来很整洁.

Answer 1

来自John Tromp 的Fhourstones Benchmark的源代码使用了一种迷人的算法来测试连接四场比赛的胜利.该算法使用以下游戏的位板表示:

.  .  .  .  .  .  .  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 2

每个单元格只能归因于最多12个获胜组合.(4水平,4垂直和4对角线).每个组合将有4个单元,包括正在考虑的单元.对于靠近两侧的细胞来说,这些数字会更低.因此,预编译这些组合并存储相关单元格的哈希散列是有意义的,这可以使单个游戏成为赢家.这样,在每个单元格是玩家之后,您只需拉出相关的组合/单元格以检查它是否是赢家.