通过暴力破解解决井字棋

Question

我最近一直在为这个问题苦恼。我需要通过暴力破解的方式来解决井字棋的问题，也就是说，让电脑通过自己对战几百万次来“学习”。

目前，我的“设置”是可以工作的，我简单描述一下。我的电脑通过随机生成棋步来进行自我对战，直到一方获胜为止。然后，它会保存这个游戏的棋步列表，并把这个列表和1、0或-1关联起来，分别表示胜利、平局或失败。

我现在使用的算法很简单；我会找出在当前棋盘上，所有可能的棋步中，和最多胜利、最少失败相关的那一步，然后就走那一步。

这种方法在几乎所有情况下都有效，但有一些重要的情况除外：分叉。

比如在这种情况下：

o - -       o - x     o - x

- x -   >   - x -  >  - x -

- - o       - - o     o - o

当电脑有下一步棋的时候，它总是会走到一个角落，结果后面就被对手分叉了。

有没有办法仅仅通过“暴力破解”来解决井字棋的问题（不使用最小/最大值、启发式方法、硬编码分叉等）？

Answer 1

几百万次可能有点多了。我觉得可能的“游戏”情况大约只有362,880种（统计学上：第一个玩家有9种选择，第二个玩家剩下8种，然后是7种，依此类推，所以9! = 362,880）。

我建议在选择行动时，不仅要考虑最终的胜负，还要考虑赢得比赛所需的步数。步数越少，决策就越好。

另外，一旦你建立了一个“完整”的地图，你可以把某些情况下的特定行动标记为“死亡”行动，这样做必然会导致失败。一个设计良好的评估标准会发现没有赢的可能性，从而永远不会选择那种行动（这也包括分叉的情况）。