具有 α-β 剪枝的量子井字棋 - 状态的最佳表示？
对于我的 AI 课程，我必须制作一个量子 tic-tac-toe 游戏使用 alpha-beta 剪枝。
我正在考虑表示棋盘状态的最佳方式 - 我的第一直觉是使用一种邻域矩阵，即 9x9 矩阵，并在 M[i,j]是表示 (tic-tac-toe) 方块 i 和 j 被标记的移动的整数（如果没有这样的连接 - M[i ,j] 为零）。如果正方形 i 折叠，则 M[i,i] 不为 0。然后，我将创建一个此类矩阵的博弈树，并使用经典的极小极大和 alpha-beta 剪枝。
然而，这种方法似乎相当昂贵——会有一个相对较大的分支因子加上每个节点的基本操作——检查循环并找到 9x9 矩阵的所有等效状态。
我有一种感觉，必须有一个更聪明的解决方案——也许可以将量子游戏视为一组经典的井字棋游戏，并使用一种广义的极小极大搜索，这样它就会回归到一个（小）一组经典的井字棋问题？我不明白这到底是如何运作的。
有谁有解决这个（或类似）问题的经验，你能给我指出正确的方向吗？
For my AI class, I have to make a quantum tic-tac-toe game using alpha-beta pruning.
I'm thinking about the best way to represent a state of the board - my first intuition is to use a sort of neighborhood matrix, that is, a 9x9 matrix, and on M[i,j] is the integer which represents the move in which (tic-tac-toe) squares i and j are marked (if there is no such connection - M[i,j] is zero). M[i,i] is not 0 if square i is collapsed. Then, I would create a game tree of such matrices and use classical minimax with alpha-beta pruning.
However, it seems that this approach would be quite expensive - there would be a relatively big branching factor plus the basic operations for every node - checking for cycles and finding all equivalent states for 9x9 matrix.
I have a feeling that there's got to be a smarter solution - maybe something along the line as seeing a quantum game as a set of classical tic-tac-toe games and use a kind of generalized minimax search, so it would all regress to a (small) set of classical tic-tac-toe problems? I can't see how that would work exactly.
Does anyone have experience with this (or similar) problem, and could you point me in the right direction?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果有人仍然对此感兴趣，
我最终使用了两种单独的数据结构：
当我们纠缠节点 A 和 B 时：
If anyone is still interested in this
I ended up using two seperate data structures:
When we entangle nodes A and B:
如果您的问题只是井字棋，那么您可以像我的这个程序那样代表您的董事会 http://pastie .org/1715115
它是一个基于三进制的数字矩阵。棋盘是一个 9 位数字，其中每个数字都有 3 个可能值之一：0 表示空，1 表示 x，2 表示 o。
这种方法非常适合极小极大，因为棋盘可以设置为单个整数！该矩阵的形式为：
其中每对数字对应于（a）当前位置，以及（b）预先通过极小极大计算出的下一个更好位置。因此，如果棋盘是空的（suc[0][0]==0），下一个更好的位置是将“x”放入位置 5，即中心（suc[0][1]==000010000）
实际上，使用这个程序，您甚至不需要创建一个极小极大值，因为该程序已经计算了临时矩阵中所有可能的答案。最重要的功能是选择下一步，只需查看 suc（后继）矩阵即可完成：
对于量子算法（和嵌入式系统）来说，这是一个很好的方法。我希望这对你有帮助。
小心
If your problem is just Tic-Tac-Toe, than you can represent your board the way this program of mine does http://pastie.org/1715115
It is a ternary based number matrix. A board is a 9-digit number where each digit has one of 3 possible values: 0 for empty, 1 for x and 2 for o.
This approach is excellent for minimax as a board can be set in a single integer! The matrix has a form of:
where each pair of numbers corresponds to (a) the present position, and (b), the next better position calculated beforehand by a minimax. So, if the board is empty (suc[0][0]==0) the next better position is to put an 'x' into the position 5, i.e. the center (suc[0][1]==000010000)
Actually, with this program you even don't need to create a minimax as this program already calculated all possible answers in the ad-hoc matrix. The most important function, to chose the next move, is done simple looking into the suc (successor) matrix:
It is a good approach for quantum algorithms (and embedded systems). I hope this helps you.
Take care