我应该使用什么模块来创建游戏树？

Question

我正在为一个Python编码类写一个项目，我有一个问题。我正在编写一个Reversi引擎，它将在一个游戏中查看几步前进，然后选择它认为最好的移动。虽然我知道python不是一种理想的语言（因为它没有其他语言那么快），但我认为可以编写至少具有功能性的代码，同时仍然可能有点慢。在

也就是说，我正在尝试创建两个表：一个游戏板（比如一个矩阵）和一个包含整数的游戏树。我想使用一些内存效率高、速度快的东西来添加、删除和读取条目。在

我现在使用董事会的效率不高。我想问大家会建议什么模块（包括如何使用它们的说明）来编写一些与此类似但内存更轻的模块（例如：array、numpy；但我不知道如何使用这两个模块中的任何一个）：

self.board = [[0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 1, 2, 0, 0, 0,],
              [0, 0, 0, 2, 1, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,]
              [0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0,]]

对于游戏树，我有一些想法取决于列表列表的轻量级。我用标准python编写的一个想法类似于：

^{pr2}$

每一个%都是上面给出的一个板（这是非常理想的：不是每个回合都有三个选项）。但这是一个缓慢而沉重的对象，python很难有效地使用内存（尤其是如果我使用的是4层以上的内存）。在

如果有人以前使用过这样的程序，或者有高效模块导入的想法，请让我知道！在

举一个游戏树的例子，想想wikipedia page，尤其是页面上的第一张图片。在

编辑：理想的情况下，我想看的远不止四个步骤，这只是一个例子，前四个层次将如何看。此外，还将有多个给定树的副本漂浮在周围供使用。速度对于像这样呈指数增长的东西很重要。在

Answer 1

在我看来，Python非常适合这种工作！也就是说，我在用Python为一款棋盘游戏做人工智能时非常有趣和富有成效。在

我的第一个建议是探索Bit Boards。虽然这里的应用程序示例是针对国际象棋的，但这个概念完全可以转移到Reversi。使用零和一来表示一块固定大小的板上的数据块，不仅具有内存占用率较低的优点，而且还具有提高计算速度的优点（按位运算比相等运算快）。在

此外，您应该重新设计模型，以某种方式实现递归（由评分函数提供便利）。这样的实现意味着您可以编写一个函数，并允许它扩展无限的移动深度（或者更确切地说，不受设计限制，仅受资源限制），而不是预测和硬编码1、2、3、4个移动的逻辑。一个设计良好的函数对双方（玩家）都有效，然后可以暂停以选择符合某个阈值的最佳选项（根据您选择的任何标准暂停，计算位置/实时花费）。在

作为参考，这里是一个board game called Thud的github，它的需求与您的程序几乎完全相同。在这里，我使用了一个17x17的电路板，三个不同的部分和两个不同的策略，我们都可以看到，这已经比Reversi的规则更复杂了。在

哦，一个好的递归模型也能适应多线程！在