TicTacToe的解算引擎

Question

我是一个初级程序员，我知道pascal和c++的基础知识。我用Player-Computer做了一个Tic Tac Toe游戏，游戏完成了。

计算机生成一个随机的位置，将O放在表上，这是不好的。

我认为我应该多次检查每个获胜的位置，否则计算机应该尝试阻止玩家的X或建立一个获胜的位置，但这将是浪费了大量的时间，因为所有的如果。

然后，我想到了一个带有某种it的更简单的版本，但它仍然需要花费大量的时间。

然后我想得更深:来个find-4游戏怎么样？到底怎么会有人设法检查每一个可用的空间，以及怎么可能有人可以做一个函数，来检查玩家/计算机位置的任何获胜或进展，哦，等等，这还不是全部，如果玩家在玩一些把戏，所以他屏蔽了计算机呢？电脑怎么知道的？！？可以肯定的是，这将需要很长时间来编程。我不是在说一件看起来更不可能的事情:国际象棋。

所以我在这里，问我自己，应该有一种更简单的方法，计算机应该搜索和解决一些问题，而不是成吨的如果。

在这种情况下，如果你们中的任何人知道解决这个问题的任何方法，我如何才能在TicTacToe游戏中实现最简单的程序来阻挡和击败玩家？

如果有人想检查或使用我的代码：http://pastebin.com/jhyUn7d1

Answer 1

你要找的是Minimax。

使用这个算法，计算机将赢得每一场Tic Tac Toe游戏，或者你可以调整计算机分析动作的深度，以实现某种中等难度。

这并不难实现，您应该熟悉递归性，并且您已经准备好了，当然实现方式根据您的代码而有所不同，但wikipedia页面提供了一个很好的起点。

Answer 2

Tic tac toe算法类似于：

1. Take spot如果要赢得
2. Take spot如果要失去
3. Take corner
4. Take non-corner

Answer 3

我最近处理了这个问题，尽管我的代码是用C#编写的。

我想出了一种方法来给每个候选人的走法打分。我采用的方法基于获胜所需的走法数量创建了一个分数(所需的步数越少，得分越高)。

我的算法还考虑了多个方块的组合移动次数。因此，算法倾向于会产生多个潜在胜利的移动(这是我所知道的Tic Tac Toe的唯一真正的策略)。例如，有时可以进行一次移动，从而产生两个必须被阻止的潜在胜利。由于对手只能阻挡一个，所以它会产生胜利。

我在文章A Tic-Tac-Toe Game Engine中发布了我的全部代码和描述。