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

Question

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

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

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

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

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

Answer 1

如果有人仍然对此感兴趣

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

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

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

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