artificial-intelligence - 带有 alpha-beta 修剪的量子井字棋 - 状态的最佳表示？

Question

对于我的 AI 课，我必须做一个 quantum tic-tac-toe使用 alpha-beta 剪枝的游戏。

我正在考虑表示棋盘状态的最佳方式——我的第一个直觉是使用一种邻域矩阵，即 9x9 矩阵，然后在 M[i,j] 上。是表示 (tic-tac-toe) 平方 i 的移动的整数和 j被标记(如果没有这样的连接 - M[i,j] 为零)。 M[i,i]如果平方 i 不为 0折叠了。然后，我会创建一个此类矩阵的博弈树，并使用经典的极小极大与 alpha-beta 修剪。

然而，这种方法似乎非常昂贵——每个节点都会有一个相对较大的分支因子加上基本操作——检查循环并找到 9x9 矩阵的所有等效状态。

我有一种感觉，必须有一个更聪明的解决方案 - 也许将量子游戏视为一组经典的井字棋游戏并使用一种广义的极小极大搜索，所以它都会回归到(小)经典井字棋问题集？我看不出这究竟是如何运作的。

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

Answer 1

如果您的问题只是井字游戏，那么您可以像我的这个程序那样代表您的董事会 http://pastie.org/1715115

它是一个基于三元的数字矩阵。棋盘是一个 9 位数字，其中每个数字都有 3 个可能值之一: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) 下一个更好的位置是将“x”放入位置 5，即中心 (suc[0][1]==000010000)

实际上，使用这个程序你甚至不需要创建一个极小值，因为这个程序已经在特别矩阵中计算了所有可能的答案。最重要的功能是选择下一步，只需查看 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;
}

这是量子算法(和嵌入式系统)的好方法。我希望这可以帮助你。

小心