Quantum Tic-Tac-Toe AI

Question

在我的数据结构类中，我们已经分配了一个项目，在该项目中，我们需要制作一个功能齐全的Quantum Tic-Tac-Toe游戏，其中玩家面对一个玩过赢得。

教授建议我们在AI中使用游戏树。不过，像往常一样，我正在寻找更具挑战性的东西。

任何人都可以提出一个更好，更高级的方法，我可以研究和实施？

---

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

Answer 1

你渴望学习新事物（甚至是你自己的）是好的。然而复杂的解决方案通常是not the best solution。

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

你提到你在一个数据结构类（通常是一年级或二年级）。我猜测你的任务的重点是学习树数据结构。如果你想让事情变得更复杂，首先编写树版本，然后去研究解决同样问题的其他方法。

Answer 2

提供一个学习功能，以您的实现，你可以看到模拟器Donald Mitchie的MENACE（火柴盒可教圈与叉引擎）...

编辑：
在寻找到它，这已经完成了很多，例如见CodeProjet
此外，在获取世界（或Tic-Tac-Toe简化世界的这里）的统计模型并基于这样一个模型的未来行动时，智能是智能的行为，这可能会被你的教授视为超出范围，因为没有触及你的主要概念（知识表示，决策树...）

Answer 3

有2部分评估回合制游戏。

1. 游戏树。
2. 实用功能。

游戏树允许您提前播放动作以查看它们将导致的位置。如果游戏足够复杂以至于无法计算所有可能性（http://en.wikipedia.org/wiki/Solved_game），那么您需要一种确定特定电路板情况如何“良好”的方法。一个糟糕的国际象棋实用功能可能只是计算棋子的价值而忽视位置。

您还需要遍历游戏树的有效方式。阅读关于Minimax，Alpha-beta修剪，Negascout等。

Answer 4

实际上，我在做这个具体问题现在：http://www.rickb.com/quantum-tic-tac-toe

我曾经考虑过做一些更先进的为好，但我只是坚持了好醇” Alpha-Beta搜索算法。我的主要问题是提出一个很好的算法来“评分”每个特定的棋盘状态。 QTTT比标准的tic tac toe要复杂得多，要搜索的状态数量会呈指数级增长。我在记忆中有完整的标准tic tac toe游戏树，我用它来快速查找每个“经典”棋盘状态的得分，但是我必须以某种方式评分叠加状态。州的数量非常之大，以至于树不能太深，所以提早修剪树的适当评分函数是必须的。