带有alpha-beta修剪的量子井字游戏 - 状态的最佳表示形式？

Question

对于我的AI类，我必须制作一个使用alpha-beta修剪的quantum tic-tac-toe游戏。

我正在考虑代表董事会状态的最佳方式 - 我的第一个直觉是使用一种邻域矩阵，即9x9矩阵，而M[i,j]是表示移动的整数哪些（井字棋）方块i和j被标记（如果没有这样的连接 - M[i,j]为零）。 M[i,i]不是0如果方形i已折叠。然后，我会创建一个这样的矩阵的游戏树，并使用alpha-beta修剪的经典极大极小。

但是，这种方法似乎相当昂贵 - 将会有一个相对较大的分支因子加上每个节点的基本操作 - 检查周期并找到9x9矩阵的所有等价状态。

我有一种感觉，必须有一个更智能的解决方案 - 也许是沿着线看到一个量子游戏作为一套经典的井字游戏，并使用一种广义极小搜索的方式，所以它会所有这些都回归到（小）经典的井字问题？我看不出这会如何工作。

有没有人有这个（或类似）问题的经验，你能指出我在正确的方向吗？

Answer 1

如果您的问题只是井字棋，比你能代表你的板子的方式我的这个程序做http://pastie.org/1715115

它是一个基于三进制数矩阵。董事会是一个9位数字的数字，其中每个数字有三个可能的值之一：0表示空，1表示x和2表示o。

这种方法对于极小极大极好，因为电路板可以设置为一个整数！该基体具有一个形式：

int suc[TOTAL][2]={ { 0, 10000}, { 1, 20001}, { 10, 20010}, { 12, 1012}, { 21, 1021}, 
    { 100, 20100}, { 102, 100102}, ... 

其中每一对数字对应于（a）中的当前位置，和（b），下一个更好的位置由一个极小预先计算。所以，如果电路板是空的（suc [0] [0] == 0），下一个更好的位置是在位置5，即中心（suc [0] [1] == 000010000）中放置一个'x'

实际上，有了这个程序，你甚至不需要创建一个极小极大值，因为这个程序已经计算出了特殊矩阵中的所有可能的答案。最重要的功能，来选择下一步的行动，做简单的寻找到SUC（继任者）矩阵：

/* find and return the next board after the given board terno */ 
int move(int terno) 
{ 
    int i; 

    for (i=0; i<TOTAL; i++) 
     if (suc[i][0]==terno) 
      return suc[i][1]; 
    return 0; 
} 

它是量子算法（嵌入式系统），一个很好的办法。我希望这可以帮助你。

请小心