奥赛罗棋盘游戏的简单数据结构？

Question

我在很久以前就已经把我的程序作为一个uni项目来做了，至少它在某种程度上是有效的(你可以尝试一下Monkey here新手级别：)。

我想重新设计并重新实现它，以便在数据结构和算法上进行实践。

在我之前的项目中，最小-最大搜索和alpha-beta修剪是缺失的部分，以及缺乏开放字典。

因为游戏板在水平和垂直方向上都是对称的，所以我需要一个比我之前的方法更好的数据结构：

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 11 12 13 14 15 16 17 18 -1
-1 21 22 23 24 25 26 27 28 -1
-1 31 32 33 34 35 36 37 38 -1
    . . . . . .

这样，在给定任意单元格值的情况下，可以很容易地计算相邻位置：

x-11 x-10 x-9
x-1   x   x+1
x+9  x+10 x+11

这些-1就像是“墙”，以防止错误的计算。

最大的问题是它没有考虑对称/方向，也就是说，与平行开口一样，相同的开口在数据库中会有4个相应的开口案例，每个方向对应一个。

有什么好的建议吗？我也在考虑尝试ruby，因为它比PHP有更快的计算速度(只是为了最小-最大α-β修剪，以防我会把它编程为超前n步)。

非常感谢事先提出的建议。

Answer 1

当您对一个位置进行散列以在数据库中存储或查找时，将对所有八个对称位置进行散列，并仅存储或查找八个对称位置中最小的一个。因此，所有对称位置都散列为相同的值。

这将数据库的大小减少了8倍，但是哈希的成本却增加了8倍。这是一个好的权衡吗？这取决于您的数据库有多大，以及您进行数据库查找的频率。

Answer 2

在你转到C/C++后:-)考虑将游戏棋盘表示为“位板”，例如两个64位向量，例如白色和黑色，例如结构板{无符号长白，黑色}；

小心的话，你可以避免数组索引来测试棋子的位置，实际上可以使用一系列位逻辑运算符、移位和掩码从一个位置并行搜索所有向上捕捉、向上捕捉等，并且没有循环(!)。快得多。

然而，这种表示思想与你的开卷对称问题是正交的。

祝你黑客快乐。

Answer 3

如果将电路板的表示从内部表示中分离出来，这个问题很容易处理。一旦进行了洞口移动，就会得到平行、对角线或垂直的洞口。它们中的每一个都可以是4个方向中的任何一个。旋转内部电路板表示，直到它与您的开卷书对齐。然后，在绘制棋盘时，只需考虑旋转。

关于游戏，你需要研究一下移动性理论。看看Hugo Calendars这本关于这个主题的书。Nick Buro也写了一些关于他的程序Logistello的文章。A FAQ