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

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工作的思路是相似的：

tree_zero = % 

tree_one = [%, %, %] 

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

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

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

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

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

其中每个％是上面给出的主板之一（而且是理想更多：不是动不动就正好有三个选项）。但是这是一个缓慢而沉重的对象，python很难有效地使用内存（特别是当我比4层更深时）。

如果有人曾经使用过这样的程序，或有高效模块导入的想法让我知道！

对于游戏树的示例，请考虑wikipedia page，尤其是页面上的第一张图片。

编辑：理想情况下，我想进一步看比前进四步，这只是前四个级别的样子。此外，将会有多个给定树木的副本浮动以供使用。速度对于像这样呈指数增长的东西很重要。

Answer 1

在我看来，Python对于这类工作完全是完美的！也就是说，我在使用Python进行棋盘游戏的过程中度过了非常有趣且富有成效的时间。

我的第一个建议是探索Bit Boards。虽然这里的应用例子是国际象棋，但这个概念完全可以转让给Reversi。使用零和1来表示集合主板上存在的碎片不仅具有内存占用少的优点，而且还具有计算速度提高的优点（按位运算快于相等运算）。

此外，您应该重新设计您的模型以某种方式实现递归（由评分函数提供便利）。这样的实现意味着您可以编写单个函数，并允许它缩放无限移动深度（或者更确切地说，您的设计不受限制，仅受限于资源），而不是预测和硬编码1,2,3,4动作的逻辑。针对这种效应的精心设计的功能适用于双方（玩家），然后可以停止选择适合阈值的最佳选项（根据您选择的任何标准停止计算，实时计算的位置）。

作为参考，这里是一个board game called Thud的github，它与我的程序几乎完全相同。在这里，我使用了17x17的棋盘，三种不同的棋子和两种不同的策略 - 我们都可以看到它已经比Reversi的规则复杂得多。

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