带有神经网络和机器学习的井字棋人工智能
5.00/5 (17投票s)
本文描述了如何创建一个使用神经网络和机器学习的井字棋玩家。
目录
引言
本文是我参加 CodeProject AI 竞赛 “图像分类挑战赛”[^] 的参赛作品。我的目标是教会一个神经网络玩井字棋游戏，它一开始只知道规则。
井字棋是一个已解决的游戏。 存在一个 完美策略[^]，因此使用神经网络有点大材小用，并且不会像现有程序和人类那样表现出色。尽管如此，由于它是一个简单的游戏，因此它是开始试验能够自学游戏的神经网络的好选择。
游戏算法
从高层次描述：当 AI 需要走一步棋时，它会遍历所有可能的走法，生成走完给定这一步后的棋盘状态，并使用神经网络来评估执行该走法后的局面好坏。神经网络充当评估函数：给定一个棋盘，它会给出它对该局面好坏的看法。AI 会选择能导致最佳局面（由网络评估）的走法。
对于更复杂游戏的基于神经网络的 AI 使用更精细的搜索算法来决定最佳走法。在那里，神经网络也充当评估函数，以获得对局面好坏的“静态”度量。例如，Leela Chess Zero 使用神经网络作为评估函数，并结合蒙特卡洛树搜索作为搜索算法。井字棋 AI 的搜索算法非常浅，只向前看一步。
网络
神经网络的数学原理超出了本文的范围，但基本概念是神经网络由几个“层”组成：输入层、几个隐藏层和输出层。每一层都可以表示为一个向量，并由指定数量的单元组成，称为神经元。为了从层 A 过渡到层 B，会在层 A 和权重矩阵之间执行矩阵乘法。将激活函数应用于该乘法结果的每个元素（因此层 B 的神经元值保持在一定范围内）。然后重复此过程，直到达到输出层。（本网络的激活函数是双极 Sigmoid，它看起来像一个 Sigmoid[^]，但输出值范围是 -1 到 1，而不是 0 到 1。）权重矩阵是网络的核心：它们决定了输出的外观。基于输入和已知的期望输出，可以调整权重矩阵的值。一种常见的方法是使用 反向传播[^] 和 梯度下降[^]。学习的“速度”由 学习率[^] 决定——你必须仔细选择这个值：过高或过低，你的网络都学不到太多东西！
神经网络有一个输入层，包含 9 个神经元（每个棋盘方格一个），几个隐藏层（分别有 18、9 和 3 个神经元），以及一个输出层，包含一个神经元，其值介于 -1（“我输了”）和 1（“我赢了”）之间。输入层的取值包括 0.01（空方格）、1（“我”）和 -1（“对手”）。
为什么空方格用 0.01 而不是 0？我尝试了两者，0.01 的效果比 0 好得多，也更一致（证据请参见“比较网络架构和训练过程”）。
为什么不使用更简单的表示方法，例如输入用 1 表示 X，-1 表示 O，输出用 1 表示“X 赢”和 -1 表示“O 赢”？仅凭这些应该足以推断出轮到谁了，因为根据约定 X 先走，所以你只需要计算填满了多少方格，你就拥有了所有必要的信息。这是我之前的一次尝试，看起来神经网络并没有抓住这一点，尽管在其他方面表现良好。我在和它进行一场测试游戏，这是网络的一个走法
这明显是一个失误，而且在其他我可能获胜的位置，它都能很好地阻止我获胜。然而，它选择这个方格是有道理的：如果轮到 O 走，这个局面会非常有利。这使得网络很可能无法学会推断刚刚是谁走了。
视角表示真的有帮助吗？有好有坏。它有帮助，因为这样的局面不再出现（网络倾向于快速占据中心），但当我强迫它出现这个局面时，它仍然走错了。当局面不再自然出现时，这不是最大的问题，但然后发生了这个
它巧妙地发现了双重攻击，但完全忽略了 X 下一步很轻易就能获胜的事实。所以这次尝试也没有解决问题。不幸的是，我没有找到更好的方法（不引入搜索算法），所以我保持原样（至少，它比第一个棋盘表示要好一些）。
我尝试的另一种修复方法，而不是使用视角表示，是添加第十个输入字段来指示轮到谁了。这效果远不如视角表示，甚至比根本没有指示要差得多。改变层的大小或网络的学习率并没有带来太大变化，结果仍然很差。我不太确定原因。
训练过程
为了训练网络，AI 会自己和自己玩大量的训练游戏，或者与随机走法的对手玩游戏。训练游戏周期如下：
- AI 对 AI
- AI 对随机
- 随机 对 AI
- AI 对 AI
- 随机 对 AI
- AI 对随机
这个周期确保了所有类型的游戏结果：平局、X 赢和 O 赢。省略 AI 对 AI 的游戏会稍微降低性能，而 AI 和随机游戏至关重要：如果 AI 只和自己玩，它似乎并没有学到太多东西。使用最终网络配置和学习率进行此项尝试，似乎 AI 只是找到了一种与自己打平的方法，然后在后续训练游戏中加强这一点。与它玩了几场游戏证明它什么都没学会。
为了训练网络，我们使用 AForge.NET[^] 库，特别是它的 AForge.Neuro 命名空间。该库可以作为 NuGet 包下载。
Install-Package AForge.Neuro -Version 2.2.5
比较网络架构和训练过程
前面，我几次提到网络在某些训练过程或棋盘表示的改变下表现得更好或更差。这如何量化？仅仅玩几局游戏就能提供一个相当不错的想法，但不总是有说服力，而且让你无法了解训练过程是如何进行的，你只能评估最终结果。
训练游戏中比赛结果的统计数据能很好地说明训练的进展。当训练顺利进行时，网络在与自己比赛时应该会打平，而在与随机走法者比赛时应该会获胜（在特殊情况下，随机走法者可能走得足够好以取得平局，但我们可以认为这是微不足道的）。对于每场训练游戏，我们记录一个位：如果游戏结果是“好”（如上所述），则为 1，如果游戏结果是“坏”（与自己比赛时非平局，与随机比赛时平局或输），则为 0。每 100 场游戏的块，将这些位加起来，然后可以绘制出来。
这是一张展示最终网络和训练配置（视角棋盘表示，学习率为 0.025）的训练过程的图。它从较低的数字开始（正如预期的那样，因为它还不了解游戏），但很快上升到 90-100 场比赛，这是好的。学习率在 0.0125（AForge 的默认学习率）和 0.075 之间的图看起来相似。当学习率增加到 0.1 时，它就出错了。
作为比较，下面是一张图，展示了一个训练过程（学习率为 0.025），其中没有任何 AI 与自己比赛的游戏（所以它只与随机对手比赛）。
第一张图显示，与只与随机对手比赛相比，当 AI 也与自己比赛时，最终性能值更接近 100。然而，对这两张图的比较并不完全公平，因为第一张图也包含了自对弈游戏，这可能对感知性能有利，也可能不利。为了确定这一点，我们需要绘制一个训练过程的图，其中既包含与随机对手比赛，也包含与自己比赛，但图上只显示与随机对手比赛的结果，并看看这与上面的图有何不同。结果如下所示：
这张图中的平均性能值（在大跳跃之后）比上一张图要高。所以，让 AI 与自己比赛似乎是有益的。
然而，只使用 AI 对 AI 的游戏，会产生糟糕的结果。图如下所示：
这可能看起来不错，因为我们在一定数量的游戏后每次都达到了 100。然而，在与 AI 对战时，很明显它什么都没学会：100 的性能来自于 100 场平局。AI 只是找到了与自己打平的方法，并在每场训练游戏中加强了这一点。
当使用 0 而不是 0.01 来表示空方格时，这是我达到的最佳结果（学习率为 0.05）。
训练在开始时明显不稳定，但后来似乎达到了一个点，变得和使用 0.01 作为空方格时一样稳定。然而，这是最好的表现之一，其他一些看起来像这样：
我无法确定第一个图中的巨大下降是否是由使用 0 而不是 0.01 引起的。但图表确实显示，使用 0 的平均性能远低于使用 0.01 时。
另一种效果不佳的网络配置是使用第十个神经元来指示轮到谁，而不是使用视角表示。这些训练过程的图（在不同的学习率下）表明，这也效果不佳。
代码
棋盘和游戏表示
游戏通过 TicTacToeGame 类来表示，该类将棋盘的状态保存在一个 int 数组中，并记录轮到谁下棋。
public class TicTacToeGame
{
int[] board;
public bool IsXTurn
{
get;
private set;
}
public TicTacToeGame()
{
board = new int[9];
IsXTurn = true;
}
board 将包含 0 表示空方格，1 表示 X，-1 表示 O（这不是神经网络的输入表示）。根据约定，X 先走。TicTacToeGame 有一个子枚举 Result 和一个相关的 GetResult() 方法，该方法返回当前棋盘状态对应的游戏结果（未知、X 赢、O 赢、平局）。
public enum Result
{
Unknown,
XWins,
OWins,
Tie
}
public Result GetResult()
{
int diagonal1 = board[0] + board[4] + board[8];
int diagonal2 = board[2] + board[4] + board[6];
int row1 = board[0] + board[1] + board[2];
int row2 = board[3] + board[4] + board[5];
int row3 = board[6] + board[7] + board[8];
int col1 = board[0] + board[3] + board[6];
int col2 = board[1] + board[4] + board[7];
int col3 = board[2] + board[5] + board[8];
if (diagonal1 == 3 || diagonal2 == 3 || row1 == 3 || row2 == 3 ||
row3 == 3 || col1 == 3 || col2 == 3 || col3 == 3)
{
return Result.XWins;
}
else if (diagonal1 == -3 || diagonal2 == -3 || row1 == -3 ||
row2 == -3 || row3 == -3 || col1 == -3 || col2 == -3 || col3 == -3)
{
return Result.OWins;
}
if (board.Contains(0))
{
return Result.Unknown;
}
else
{
return Result.Tie;
}
}
GetResult 检查是否有任何对角线、水平线或垂直线被所有 O 或 X 填满。如果不是这种情况，并且没有空方格了，则为平局。否则，结果为未知，因为游戏尚未结束。
GetBoardAsDouble 方法返回一个 double 数组，这是神经网络的输入表示：1 代表当前玩家，-1 代表对手，0.01 代表空方格。
public double[] GetBoardAsDouble(bool xPointOfView)
{
double[] bd = new double[board.Length];
int view = xPointOfView ? 1 : -1;
for (int i = 0; i < board.Length; i++)
{
if (board[i] == -1)
{
bd[i] = -view;
}
else if (board[i] == 1)
{
bd[i] = view;
}
else
{
bd[i] = 0.01;
}
}
return bd;
}
还有几个辅助方法：Move 用于在棋盘上走棋（不进行任何类型的棋步验证），ValidSquares 用于获取一个 IEnumerable<int>，其中包含所有有效的（即空的）可走方格，以及 PrintBoard 用于在控制台上打印棋盘。
public void Move(int square)
{
board[square] = IsXTurn ? 1 : -1;
IsXTurn = !IsXTurn;
}
public IEnumerable<int> ValidSquares()
{
for (int i = 0; i < board.Length; i++)
{
if (board[i] == 0)
{
yield return i;
}
}
}
public void PrintBoard()
{
Console.WriteLine(@"-------------
| {0} | {1} | {2} |
-------------
| {3} | {4} | {5} |
-------------
| {6} | {7} | {8} |
-------------", board.Select(x => x == 1 ? "X" : (x == 0 ? " " : "O")).ToArray<object>());
}
训练好的模型
Model 类封装了一个训练好的 ActivationNetwork（AForge.NET 的一个类），并提供了一个 BestSquare 方法，该方法返回网络评估的最佳下一个方格的索引。该方法遍历所有有效方格，并使用网络评估假设选择当前方格后当前玩家的局面好坏。得分最高的方格将被返回。
public class Model
{
ActivationNetwork net;
internal Model(ActivationNetwork network)
{
net = network;
}
public int BestSquare(TicTacToeGame game)
{
int bestSquare = 0;
double bestScore = double.NegativeInfinity;
foreach (int square in game.ValidSquares())
{
double[] boardAfter = game.GetBoardAsDouble(game.IsXTurn);
boardAfter[square] = 1;
double score = net.Compute(boardAfter)[0];
if (score > bestScore)
{
bestScore = score;
bestSquare = square;
}
}
return bestSquare;
}
}
训练器
神经网络的训练发生在 Trainer 类中。训练完成后，该类将训练进度和训练好的模型作为 Progress 和 Model 属性公开。
public class Trainer
{
public List<bool> Progress { get; private set; }
public Model Model { get; private set; }
Random rand = new Random();
public Trainer()
{
Progress = new List<bool>();
Model = null;
}
rand 用于部分训练的网络与随机走法对手之间的训练游戏。Progress 中的布尔值根据“比较网络架构和训练过程”中解释的方式为 true 或 false。
为了训练网络，我们使用 AForge.NET 的 ActivationNetwork 作为网络，并使用 BackPropagationLearning 类来训练网络。AForge 的训练过程很简单：你可以一直输入 double 数组的输入及其对应的 double 数组的期望输出，直到你想要为止。每场训练游戏都会产生一个 double 数组集合（包括输入和输出），对应游戏中的每个棋盘状态。每个输入数组有 9 个元素，每个输出数组有 1 个元素。PlayTrainingGame 方法通过玩游戏来获取这些数组。游戏要么是在两个部分训练的网络实例之间进行，要么是在部分训练的网络与随机走法对手之间进行。该方法接受三个参数：ActivationNetwork net（当前网络状态）、bool aiX（指定 AI 是否下 X，但仅在对手是随机走法对手时才真正相关）和 bool fullAi（true 表示游戏在两个网络之间进行）。该方法通过一个循环玩完一整场游戏，直到游戏结束，棋步要么由网络决定，要么由 Random 实例决定。当出现每个局面时，它都会被添加到 List<double[]> inputs 中，正确的输出只能在游戏结束后确定。如果 X 赢了，则输出数组集合看起来像 { { 1 }, { -1 }, { 1 }, ... }，因为就像棋盘是视角表示一样，输出数组也必须如此。1 表示“如果‘我’在这个局面下走了棋，那么这个局面‘对我’（X）有利”，反之，如果 O 赢了，则集合看起来像 { { -1 }, { 1 }, { -1 }, ... }，如果平局，则全为零。游戏结束后，会将一个新的布尔值添加到 Progress 中，以指示网络表现是否良好。
Tuple<double[][], double[][]> PlayTrainingGame(ActivationNetwork net, bool aiX, bool fullAi)
{
TicTacToeGame game = new TicTacToeGame();
List<double[]> inputs = new List<double[]>();
List<double[]> outputs = new List<double[]>);
Model current = new Model(net);
while (game.GetResult() == TicTacToeGame.Result.Unknown)
{
int playSquare;
if (aiX == game.IsXTurn || fullAi)
{
playSquare = current.BestSquare(game);
}
else
{
int[] validSquares = game.ValidSquares().ToArray();
playSquare = validSquares[rand.Next(validSquares.Length)];
}
game.Move(playSquare);
inputs.Add(game.GetBoardAsDouble(!game.IsXTurn));
}
double output;
TicTacToeGame.Result result = game.GetResult();
if (result == TicTacToeGame.Result.XWins)
{
output = 1;
}
else if (result == TicTacToeGame.Result.OWins)
{
output = -1;
}
else
{
output = 0;
}
for (int i = 0; i < inputs.Count; i++)
{
outputs.Add(new double[] { output * (i % 2 == 0 ? 1 : -1) });
}
Progress.Add(fullAi ? result == TicTacToeGame.Result.Tie :
(aiX ? result == TicTacToeGame.Result.XWins : result == TicTacToeGame.Result.OWins));
return new Tuple<double[][], double[][]>(inputs.ToArray(), outputs.ToArray());
}
Train 方法使用此方法，该方法玩给定数量的训练游戏，然后将训练好的模型赋值给 Model 属性。三分之一的游戏是网络对网络，其余游戏是网络对随机（其中 X 和 O 的扮演者是平衡的）。
public void Train(int games)
{
ActivationNetwork net =
new ActivationNetwork(new BipolarSigmoidFunction(), 9, 18, 9, 3, 1);
BackPropagationLearning teacher = new BackPropagationLearning(net);
net.Randomize();
teacher.LearningRate = 0.025;
for (int i = 0; i < games; i++)
{
var trainingGame = PlayTrainingGame(net, i % 2 == 0, i % 3 == 0);
double[][] inputs = trainingGame.Item1;
double[][] outputs = trainingGame.Item2;
for (int j = 0; j < inputs.Length; j++)
{
teacher.Run(inputs[j], outputs[j]);
}
}
Model = new Model(net);
}
BipolarSigmoidFunction 是一种激活函数，它看起来像 Sigmoid 函数，但范围是 -1 到 1，这非常适合我们的网络。
有了所有这些，你就可以轻松创建一个程序，该程序可以训练一个网络，并通过控制台窗口让你与它玩游戏。
var trainer = new Trainer();
Stopwatch sw = new Stopwatch();
sw.Start();
trainer.Train(500000); // 500K training games
sw.Stop();
Console.WriteLine("Training completed in {0} seconds.",
sw.Elapsed.TotalSeconds.ToString("0.0"));
var model = trainer.Model;
bool playerIsX = true;
while (true)
{
Console.WriteLine("Let's play a game.");
TicTacToeGame game = new TicTacToeGame();
while (game.GetResult() == TicTacToeGame.Result.Unknown)
{
game.PrintBoard();
if (game.IsXTurn == playerIsX)
{
Console.Write("Type a square (0-8): ");
int square = int.Parse(Console.ReadLine().Trim());
if (game.ValidSquares().Contains(square))
{
game.Move(square);
}
else
{
Console.WriteLine("Invalid square");
}
}
else
{
game.Move(model.BestSquare(game));
}
}
game.PrintBoard();
Console.WriteLine("Result: {0}", game.GetResult().ToString());
playerIsX = !playerIsX;
}