在井字游戏实施中，我猜想最具挑战性的部分是确定机器要发挥的最佳动作。

可以采用哪些算法？我正在研究从简单到复杂的实现。我将如何解决这部分问题？

解决方案

用数字分数对每个正方形进行排名。如果采用正方形，则移至下一个选择(按等级降序排列)。我们将需要选择一种策略(首先有两个主要策略，第二个是三个(我认为))。从技术上讲，我们可以只编程所有策略，然后随机选择一个。那会使对手难以预测。

生成每个可能的木板并根据其随后在树上进一步产生的木板评分的蛮力方法不需要太多的内存，特别是一旦我们意识到90度的木板旋转是多余的，例如围绕垂直方向的翻转水平轴和对角线轴。

一旦达到这一点，在树形图中将有不到1k的数据来描述结果，从而成为计算机的最佳举措。

-亚当

由于我们仅处理可能位置的3x3矩阵，因此很容易编写所有可能性的搜索而无需增加计算能力，这非常容易。对于每个开放空间，在标记该空间之后，我将计算所有可能的结果(递归地说)，然后以最大的获胜可能性使用此举。

确实，优化它会浪费很多精力。尽管一些简单的方法可能是：

• 首先检查另一支球队可能取得的胜利，阻止找到的第一支球队(无论如何有2场比赛)。
• 如果中心是开放的，则始终将其居中(并且上一条规则没有候选者)。
• 在边角前弯(同样，如果先前的规则为空)

我们可以在一些示例游戏中让AI发挥自身作用，以供学习。使用监督学习算法来帮助它。

维基百科上玩完美游戏(每次都赢或者平)的策略似乎是简单的伪代码：

Quote from Wikipedia (Tic Tac Toe#Strategy)
  
  A player can play a perfect game of Tic-tac-toe (to win or, at least, draw) if they choose the first available move from the following list, each turn, as used in Newell and Simon's 1972 tic-tac-toe program.[6]
  
  
  Win: If you have two in a row, play the third to get three in a row.
  Block: If the opponent has two in a row, play the third to block them.
  Fork: Create an opportunity where you can win in two ways.
  Block Opponent's Fork:
  
  Option 1: Create two in a row to force
  the opponent into defending, as long
  as it doesn't result in them creating
  a fork or winning. For example, if "X"
  has a corner, "O" has the center, and
  "X" has the opposite corner as well,
  "O" must not play a corner in order to
  win. (Playing a corner in this
  scenario creates a fork for "X" to
  win.)
  
  Option 2: If there is a configuration
  where the opponent can fork, block
  that fork.
  Center: Play the center.
  Opposite Corner: If the opponent is in the corner, play the opposite
  corner.
  Empty Corner: Play an empty corner.
  Empty Side: Play an empty side.

如建议的那样，可以以暴力方式识别"叉"状情况。

注意："完美"的对手是很好的练习，但最终不值得"对抗"。但是，我们可以更改上述优先级，以使对手的性格特有的弱点。

我们需要的(井字游戏或者类似Chess的难度更大的游戏)是minimax算法，或者其更复杂的变体，即alpha-beta修剪。但是，普通的天真minimax可以很好地解决与井字游戏一样小的搜索空间的游戏。

简而言之，我们要做的不是寻找可能为我们带来最佳结果的举动，而是寻找可能取得最糟糕结果的举动。如果我们认为对手的表现最佳，则必须假设他们会采取对我们最不利的举动，因此我们必须采取使他们的最大收益最小化的举动。