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

Question

我很久以前就完成了我的程序here作为一个 uni 项目，至少它在某种程度上是有效的(你可以尝试 Monkey 和 Novice 级别:))。

我想重新设计并重新实现它，以便练习数据结构和算法。

在我之前的项目中，min-max search 和 alpha-beta pruning 是缺失的部分，也缺少开放字典。

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

-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 更快的计算速度(仅用于最小-最大 alpha-beta 修剪，以防我将其编程为向前看 n 步)。

非常感谢您提前提出建议。

Answer 1

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

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