为了我的 AI 课程，我需要使用 alpha-beta 剪枝制作一个 量子井字棋 游戏。

我正在考虑表示棋盘状态的最佳方式 – 我的第一直觉是使用一种邻域矩阵，也就是一个 9×9 的矩阵，M[i,j] 上的值表示 (井字棋) 方格 i 和 j 被标记的步数（如果没有这种连接，则 M[i,j] 为零）。如果方格 i 已坍缩，则 M[i,i] 不为 0。然后，我会创建一个此类矩阵的博弈树，并使用经典的 minimax 算法与 alpha-beta 剪枝。

然而，这种方法似乎非常昂贵 – 分支因子会比较大，加上每个节点的基本操作 – 检查循环以及找到 9×9 矩阵的所有等效状态。

我感觉应该有一个更聪明的解决方案 – 也许可以这样理解，将量子游戏看作是一组经典的井字棋游戏，并使用一种广义的 minimax 搜索，这样所有的问题都会回归到一组（小的）经典井字棋问题？但我不太清楚具体该如何实现。

有没有人有这方面（或类似）的经验，可以指点我一下方向？

回答：

如果还有人对此感兴趣

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

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

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

• 如果两者都不在现有图中，则创建一个新图 [A,B]（NEW_GRAPH）
• 如果一个 (例如 A) 在现有图 […, A, …] 中 (EXISTING_GRAPH)
  • 如果 B 不在现有图中，则将 B 添加到 EXISTING_GRAPH
  • 如果 B 在现有图中，我们就知道我们关闭了一个循环，然后我们进行一次坍缩（图从列表中删除，新节点添加到经典棋盘）