基于强化学习的井字棋游戏

唯一获胜的走法，就是不走棋

这段代码实现了一个神经网络，利用强化学习来学习井字棋的游戏规则——只需与随机对手对弈，仅用不到400行C语言代码完成，且未使用任何外部库。虽然市面上已有大量基于强化学习的示例代码，这些代码或以PyTorch为框架编写，或采用其他机器学习框架，但我真正想实现的是从零开始完整地构建这个系统，让每一部分都清晰易懂、一目了然。

尽管这段代码只是一个“玩具”级的程序，旨在帮助有兴趣的读者掌握强化学习的基础知识，但它却充分展示了强化学习在无需事先了解游戏规则的情况下，仍能高效学习并掌握新事物的强大能力：

1. 采用冷启动策略：神经网络的权重初始化为随机值。
2. “白手起家”的学习方式：程序中并未预设任何关于游戏规则的知识，除了明确X和O不能落在已被占用的方格中；同时，当连续出现三个相同符号，或所有方格都被填满时，即判定为胜利或平局。
3. 训练神经网络所依赖的唯一信号，便是游戏的奖励：赢、输、平。

在我过去使用Kilo编辑器和Picol解释器的经历中，我注意到：对于那些希望深入了解新领域（尤其是年轻程序员）的开发者来说，简洁、无依赖、结构清晰、注释详尽且“极其短小”的C语言程序，往往是一个很好的入门起点。因此，为了向萨顿和巴托颁发图灵奖致敬，我决定亲手编写这段代码。

要运行此程序，请使用以下命令进行编译：

cc ttt.c -o ttt -O3 -Wall -W -ffast-math -lm

然后执行：

./ttt

默认情况下，程序将与随机对手对弈（即每次移动时，对手会随机在随机位置投放“X”）。玩家将进行15万局对弈。随后，程序会启动一个命令行界面，供用户与人类玩家对弈。您可以通过在第一个参数中指定想要与随机对手对弈的局数，来调整游戏的对局数量：

./ttt 2000000

在运行200万局后（所需时间仅几秒），程序通常已不再输掉任何一局。

经过多次自我对弈，程序最终达到了近乎完美的水平：

Games: 2000000, Wins: 1756049 (87.8%)
                    Losses: 731 (0.0%)
                    Ties: 243220 (12.2%)

需要注意的是，有些运行结果比其他运行更幸运，这很可能与神经网络的权重初始化有关。如果您无法达到0局输棋，不妨多运行几次程序。

程序的工作原理

代码力求简单，并附有详尽的注释，每两行代码大约只有一行注释：理解其工作原理应该相当容易。不过，在本README中，我仍将重点阐述几个关键点。此外，请务必仔细阅读代码内部的“LEARNING OPPORTUNITY”注释——在那里，我尝试突出显示神经网络领域中一些重要的研究成果或技术，这些内容或许值得您进一步深入研究。

方格板的表示

游戏的状态仅由以下数据构成：

typedef struct {
    char board[9];          // 可以是“.”（空格）或“X”、“O”。
    int current_player;     // 0 表示人类玩家（X），1 表示电脑玩家（O）。
} GameState;

人类玩家和电脑玩家始终按相同的顺序进行游戏：人类先手，电脑则根据人类的走法作出回应。双方也始终使用相同的标记：人类玩家用“X”，电脑玩家用“O”。

方格板本身仅由9个字符表示，具体取决于该方格是否为空，或者已放置“X”或“O”。

神经网络

神经网络的结构非常简单，因为代码的设计初衷就是追求简洁：它仅包含一层隐藏层，而这一层足以很好地模拟这款如此简单的游戏（增加更多层不仅无法加快收敛速度，反而可能使游戏表现更差）。

值得注意的是，井字棋共有5478种可能的状态；默认情况下，我们的神经网络拥有100个隐藏神经元：

• 18个输入神经元 * 100个隐藏神经元 +
• 100个隐藏神经元 * 9个输出神经元 +
• 100个隐藏神经元 + 9个偏置项

总计2809个参数，因此我们的神经网络几乎能够完全记住游戏中的每一个状态。不过，您也可以将隐藏层的神经元数量减少至25个（甚至更少），即便如此，我们的神经网络依然能够以约700个参数左右的规模，出色地完成游戏对弈任务——尽管未必能达到完美水平。

typedef struct {
    // 权重与偏置。
    float weights_ih[NN_INPUT_SIZE * NN_HIDDEN_SIZE];
    float weights_ho[NN_HIDDEN_SIZE * NN_OUTPUT_SIZE];
    float biases_h[NN_HIDDEN_SIZE];
    float biases_o[NN_OUTPUT_SIZE];

    // 为了简化起见，激活函数直接存储在结构体中。
    float inputs[NN_INPUT_SIZE];
    float hidden[NN_HIDDEN_SIZE];
    float raw_logits[NN_OUTPUT_SIZE]; // 激活函数之前的数据。
    float outputs[NN_OUTPUT_SIZE];    // 激活函数之后的数据。
} NeuralNetwork;

激活函数直接存储在神经网络内部，因此计算梯度并进行反向传播的过程极为简单。

我们选择ReLU作为激活函数，因为其导数简单。在本例中，几乎所有其他激活函数都能正常工作。权重初始化并不需要考虑ReLU，它们只是从-0.5到0.5之间随机生成（无需采用He初始化方法）。

输出通过softmax函数计算得出，因为该神经网络本质上会为每一种可能的下一步行动分配概率。理论上，我们应使用交叉熵来计算损失函数，但在实际应用中，我们主要依据对局的结果来评估“智能体”的表现，因此在这里我们只是隐式地使用了交叉熵：

        deltas[i] = output[i] - target[i]

这就是在使用softmax和交叉熵时的梯度计算公式。

强化学习策略

此处采用的奖励策略如下：

    if (winner == 'T') {
        reward = 0.2f;  // 对于平局，给予较小的奖励
    } else if (winner == nn_symbol) {
        reward = 1.0f;  // 对于获胜，给予较大的奖励
    } else {
        reward = -1.0f; // 对于失败，给予负值奖励
    }

在进行奖励时，我们会为神经网络即将移动的所有游戏状态创建奖励，并且针对每个状态，我们都会对获胜的走法进行奖励（不仅仅是最终获胜的那一步，而是我们在赢得比赛的过程中所执行的所有走法），并将其他所有被设置为 0 的走法作为目标输出，而我们要奖励的走法则设置为 1。随后，我们通过一次反向传播过程来更新权重。

对于平局的情况，其奖励机制与胜利时类似，但奖励会被适当缩放。相反，在游戏失败时，我们以将走法设置为 0 的走法作为目标，同时将所有无效走法也设置为 0，并将所有其他有效走法设置为 1/(有效走法数量)。

不过，我们还会根据走法完成的时机进行相应的缩放：对于那些接近游戏开局的走法，我们给予较小的奖励；而对于那些在游戏后期（接近游戏结束时）才出现的走法，则会提供更高的奖励：

    float move_importance = 0.5f + 0.5f * (float)move_idx/(float)num_moves;
    float scaled_reward = reward * move_importance;

需要注意的是，上述设计对程序的运行方式产生了显著的影响。 此外，请注意，尽管这一方法在强化学习中看似与“时间差”有相似之处，但实际上并不相同：在这种情况下，我们并没有一种简单的方法来评估单个步骤是否带来了正向或负向的奖励——我们需要等待每一场游戏全部结束。上面提到的时间尺度缩放，只是在网络内部实现的一种编码方式：早期的走法更加开放，而随着游戏进程的推进，我们则需要更加有选择地进行决策。

权重更新

我们仅使用简单的反向传播算法，而代码的设计初衷正是为了清晰地展示：归根结底，程序的工作方式与监督学习非常相似：唯一的区别在于，输入/输出对并非事先已知，而是根据强化学习的奖励策略，实时动态地提供给模型。

如需了解更多信息，请查看相关代码。

未来工作

以下是我尚未进行测试的领域，因为这些内容若未充分测试，可能会因复杂度过高而削弱本程序的教育价值，或者由于时间不足而无法实现。不过，这些领域同样可以成为有趣的练习课题，甚至为其他项目或分支带来启发：

• 这种方法是否也能应用于四子棋？问题空间的规模要大得多，这将极具研究价值，而且也更贴近实际应用。
• 通过增加一个额外的输入变量——即即将执行走法的棋子符号（尤其在四子棋中很有用），训练网络以同时应对双方的博弈。这样一来，我们就可以直接利用网络本身作为对手，而非单纯地与随机走法进行对抗。
• 在上述场景中，实施合理的采样策略：初始阶段，走法应较为随机；随着游戏进程的推进，走法的选择也会逐渐变得更加稳定、更具针对性。
• 实现 MCTS 算法。

ttt-rl 快速上手指南

ttt-rl 是一个用纯 C 语言实现的井字棋（Tic-Tac-Toe）强化学习项目。它不依赖任何外部机器学习库，仅用不到 400 行代码展示了神经网络如何通过自我对弈从零开始学会玩游戏。

环境准备

本项目设计为无依赖的轻量级工具，对环境要求极低。

• 操作系统：Linux、macOS 或带有 GCC 的 Windows (如 WSL, MinGW)。
• 编译器：需要安装 gcc 或 clang。
  • Ubuntu/Debian: sudo apt-get install build-essential
  • macOS: 安装 Xcode Command Line Tools (xcode-select --install)
  • CentOS/RHEL: sudo yum groupinstall "Development Tools"
• 前置依赖：无第三方库依赖，仅需标准 C 数学库（通常由 -lm 链接）。

安装步骤

该项目无需复杂的安装过程，只需下载源码并编译即可。

1. 获取源码 克隆仓库或下载 ttt.c 文件到本地目录。

   git clone https://github.com/antirez/ttt-rl.git
   cd ttt-rl
   

2. 编译程序 使用以下命令进行优化编译：

   cc ttt.c -o ttt -O3 -Wall -W -ffast-math -lm
   

基本使用

编译成功后，可直接运行程序。程序默认会先进行自我训练，然后进入人机对战模式。

1. 默认运行（快速体验）

程序将自动与随机对手进行 15 万局训练，随后启动命令行界面供用户试玩。

./ttt

注：训练过程通常在几秒内完成。

2. 增加训练量（达到完美胜率）

若希望 AI 达到几乎不败的水平（损失率接近 0%），可指定更大的训练对局数（例如 200 万局）：

./ttt 2000000

运行后，你将看到类似以下的统计信息，表明 AI 已掌握完美策略：

Games: 2000000, Wins: 1756049 (87.8%)
                Losses: 731 (0.0%)
                Ties: 243220 (12.2%)

3. 人机对战

训练结束后，程序会自动进入 CLI 交互模式。

• 人类玩家：始终执 "X"，先行。
• AI 玩家：始终执 "O"，后手。
• 操作方式：根据提示输入棋盘位置索引（0-8）进行落子。