python - 我应该使用哪些模块来创建游戏树？

Question

我正在为 Python 编码类(class)编写一个项目，我有一个问题。我在写 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 编写的想法类似于:

tree_zero = %

tree_one =  [%, %, %]

tree_two = [[%, %, %], [%, %, %], [%, %, %]]

tree_thre = [[[%, %, %], [%, %, %], [%, %, %]],
             [[%, %, %], [%, %, %], [%, %, %]],
             [[%, %, %], [%, %, %], [%, %, %]]],

tree_four = [[[[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]]],

             [[[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]]],

             [[[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]],
              [[%, %, %], [%, %, %], [%, %, %]]]]

其中每个 % 都是上面给出的棋盘之一(而且非常理想:并非每一轮都有恰好三个选项)。但这是一个缓慢而沉重的对象，python 很难有效地使用内存(特别是如果我比 4 层更深)。

如果有人以前使用过这样的程序，或者有导入高效模块的想法，请告诉我!

以博弈树为例，想想 wikipedia page尤其是页面上的第一张图片。

编辑:理想情况下，我想看得比前面的四步更远，这只是前四个级别的示例。此外，将有多个给定树的副本漂浮在周围供使用。对于像这样呈指数级增长的事物，速度很重要。

Answer 1

在我看来，Python 非常适合这类工作!也就是说，我在使用 Python 为棋盘游戏开发 AI 方面度过了一段非常有趣且富有成效的时光。

我的第一个建议是探索 Bit Boards .虽然这里的应用示例是国际象棋，但这个概念可以完美地转移到黑白棋上。使用 0 和 1 来表示集合大小的棋盘上存在的棋子，不仅具有内存占用更少的优势，还具有提高计算速度的优势(按位运算比相等运算更快)。

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

作为引用，这里是一个 board game called Thud 的 github我制作的要求与您的程序几乎完全相同。在这里，我使用了一个 17x17 的棋盘、三个不同的棋子和两种不同的策略——我们都可以看到这已经比黑白棋的规则更复杂了。

哦，一个好的递归模型也适用于多线程!