实现井字游戏的算法？

Question

可能重复：
What Algorithm for a Tic-Tac-Toe Game Can I Use To Determine the “Best Move” for the AI?实现井字游戏的算法？

我已经创建了一个井字游戏2名球员即玩互相反对。现在我已经计划实施相同的游戏，但是与电脑对战。那么任何人都可以提出一些很好的算法或想法来实现它？

Answer 1

由于游戏非常简单，你可以做一个搜索树。这是一个可以替代“你的动作”和“敌人动作”的树。敌人总是选择最适合他们的东西，而且你总是选择最适合你的东西。对于每个棋盘位置，如果最佳游戏分别产生赢/输/平局，则将其评为“胜利”/“丢失”/“打结”。执行深度优先搜索（或任何搜索）并选择分支。这基本上是如何打败大师们的复杂国际象棋程序（尽管它们是高度优化的并且在并行的优秀硬件上运行）。这就是所谓的minimax algorithm。

或者，您可以手动编写所有最佳动作（使用通过旋转和翻转电路板将其与已知动作进行比较的例程）。只有500个可能性。

但是由于tic-tac-toe是一个解决的游戏，它会相当无聊。如果电脑播放效果最佳，电脑将永远和你同在。由于tic-tac-toe只对5岁的孩子有挑战性，所以你可以考虑你的游戏的观众：让计算机做一个随机的不失败的举动可能是合理的。那么人类玩家至少有机会。

Answer 2

与ninjagecko一样，搜索树已经提出，对于代码编写来说，它是直接和最优的。

但就像制作搜索树比手工编码所有最佳动作更有趣一样，我认为尝试机器学习方法会更有趣。例如，制作一个使用reinforcement learning的程序将是一件很酷的事情。