5

对于我的 AI 课程，我必须使用 alpha-beta 修剪制作一个量子井字游戏。

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

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

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

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

4

2 回答 2

0

如果您的问题只是井字游戏，那么您可以像我的这个程序那样代表您的董事会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)，下一个更好的位置是在位置 5 中放置一个“x”，即中心 (suc[0][1]==000010000)

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

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

小心

于 2011-03-25T20:41:44.177 回答
0

如果还有人对此感兴趣

我最终使用了两个单独的数据结构：

  • 用于折叠节点的经典井字棋盘（3x3 矩阵）
  • 纠缠节点的图表列表。每个图的节点都是棋盘坐标（在 3x3 矩阵中），并且图是全连接的。

当我们纠缠节点 A 和 B 时：

  • 如果两者都不在现有图表中，则创建一个新图表 [A,B] (NEW_GRAPH)
  • 一个（例如 A）在现有图表中 [..., A, ...] (EXISTING_GRAPH)
    • 如果 B 不在现有图表中，则将 B 添加到 EXISTING_GRAPH
    • 如果 B 在现有图表中，我们知道我们关闭了一个循环，并且我们进行了折叠（图表从列表中删除，新节点添加到经典板）
于 2019-06-24T12:25:27.260 回答