量子Tic-Tac-Toe AI

Question

在我的数据结构类中，我们被分配给一个项目，在这个项目中，我们被要求做一个充分发挥作用的量子Tic-Tac- to游戏，在这个游戏中，玩家面对一个机器人来赢得比赛。

教授建议我们在人工智能中使用游戏树。然而，像往常一样，我正在寻找更有挑战性的东西。

有人能提出一个更好，更先进的方法，我可以研究和实施吗？

我不是在找一些让问题变得更复杂的完全荒谬的东西。相反，我正在寻找一种先进的方法--比如使用A*算法而不是BFS。

Answer 1

你学习新事物的愿望(甚至是你自己)是很好的。然而，一个复杂的解决方案通常是不是最好的解决方案。

有一个很好的理由，你的教授建议使用游戏树为人工智能。这是因为它是适合这项工作的工具。没有更好的方法可以研究，因为它是最好的方法。

您提到的是数据结构类(通常是第一年或第二年的类)。我猜你的作业的重点是学习树数据结构。如果你想让事情变得更复杂，先写树版本，然后去研究解决相同问题的其他方法。

Answer 2

有两个部分来评估一个回合为基础的游戏。

1. 游戏树。
2. 效用函数。

游戏树允许你提前发挥移动，看看他们将在哪里领导。如果游戏非常复杂，以至于无法计算所有的可能性(游戏)，那么您需要一种方法来确定一个特定的板子场景有多“好”。国际象棋的实用函数很差，可能只是计算棋子的值而忽略位置。

您还需要一种高效的方法来遍历游戏树。阅读关于Minimax，α-β剪枝，Negascout等。

Answer 3

实际上，我现在正在处理这个特定的问题：http://www.rickb.com/quantum-tic-tac-toe

我也考虑过做一些更高级的事情，但我只是坚持好的ol‘α-β搜索算法。我的主要问题是想出一个很好的算法来“得分”每个特定的董事会状态。QTTT比标准的tic toe要复杂得多，要搜索的状态数是指数级的。我有完整的标准tic toe游戏树，用于快速查找每个“经典”板状状态的得分，但之后我必须以某种方式对叠加状态进行评分。状态的数量是如此之多，以至于你不能在树中走得太深，所以必须有一个适当的评分函数来提前修剪树。