实现井字游戏的最佳算法 - 通用（3X3或4x4或9x9等）

Question

任何人都可以帮助我。这是实现TicTacToe游戏的最佳算法。我需要以它应该是通用的方式编写代码，并且应该能够以更简单的方式处理更复杂的级别（通用方式），我可以从哪里开始？我读到我们可以使用MiniMax算法。我需要知道的最多。高效的算法

感谢，

Answer 1

“最好”的算法（它总是选择最好的游戏）被称为是NP完全问题。

因此，真正很难实施“好”的，它使用一些启发式来提高性能，它是非常宝贵的。

Minimax基本上只是“真正”起作用的方法，所以先从它开始，然后您可以思考并寻找优化。这个想法很简单，你尝试每一个动作，然后衡量该动作的“价格”（例如，创建更多相同的“X”或“O”排比创建“X”或“O”更胜于大多数东西，或者阻止敌人的“X”或“O”长线也不错）。

然后，对于每一个可能的动作，你都会尝试敌人去做所有可能的动作，并且你会计算出价格。

你到底“越深”，它越珍贵，但性能算法的代价越高。

对于这个例子，我说过，每做一次动作，你都会做每一次敌人的动作 - 你认为对手会尽可能的发挥出色，所以你从对手所发挥的所有动作中获得最大（他的最大值） 。 现在对于每一个可能的动作，你都有最好的敌人玩的价值。然后你选择最低限度 - 这意味着你想为你选择最好的，最坏的选择给敌人。

这就是为什么他们称之为极小极小。