井字棋 Q-learning 实战:把强化学习跑起来

int TicTacToeEnv::EncodeBoardKey(const std::array<Cell, 9> &board) {
  int key = 0, base = 1;
  for (int i = 0; i < 9; i++) {
    key += static_cast<int>(board[i]) * base;   // 空=0, X=1, O=2   1
    base *= 3;
  }
  return key;
}

1. 只在轮到 X(智能体)时调用 AgentStateKey()——Q 表存的是“轮到我下时,这盘棋值多少”。

board_[action] = player;
result_ = CheckResult();
out.done = IsTerminal();

if (result_ == GameResult::X_WIN)      out.reward = 1.0;              1
else if (result_ == GameResult::O_WIN)   out.reward = -1.0;
else if (result_ == GameResult::DRAW)    out.reward = 0.0;

if (!out.done) {
  agent_turn_ = !agent_turn_;
  out.agent_state_key = agent_turn_ ? AgentStateKey() : -1;           2
}

1. 奖励只在终局给出,对应第 12 章稀疏奖励;中间步 reward=0,靠 TD 目标里的 max Q(s′,·) 把价值从终局往回传。
2. 若未结束,交换行棋方,并准备好下一轮智能体行动时的状态键,供 Update 使用。

TabularQLearning::Config config;
config.alpha = 0.5;           // 学习率 α                         1
config.gamma = 0.99;          // 折扣 γ
config.epsilon = 1.0;         // 探索率, 训练初期几乎全随机          2
config.epsilon_min = 0.05;
config.epsilon_decay = 0.9995;
config.rand_seed = option.rand_seed;
agent.Init(config);

1. α 控制每次 TD 更新挪多大幅度;γ 让智能体更看长远(接近 1 时更重视终局赢棋)。
2. ε 从 1.0 指数衰减到 0.05——第 12 章 ε-greedy:先广探索,后多利用已学到的 Q。

if (explore && config_.epsilon > 0.0) {
  double sample = random.CreateRandom() / 1000000.0;
  if (sample < config_.epsilon)
    return TicTacToeEnv::ChooseRandomAction(legal_actions, ...);   1
}
return ArgmaxQ(state_key, legal_actions);                          2

1. 探索:在合法空位里随机挑一格。
2. 利用:挑 Q 最大的合法落子;Evaluate 时 explore=false,纯 greedy 下棋。

double old_q = QRow(state_key)[action];
double target = reward;
if (!terminal)
  target += config_.gamma * MaxQ(next_state_key, legal_actions_next);  1
QRow(state_key)[action] = old_q + config_.alpha * (target - old_q);    2

1. 贝尔曼目标 r + γ·max Q(s′,·)(第 12 章);终局时不再加未来项。
2. TD 误差 target − old_q,乘以 α 写回——和第 6 章“误差驱动更新”同构,但没有反向传播。

env.Reset();
while (!env.IsTerminal()) {
  int state_key = env.AgentStateKey();
  int action = SelectAction(state_key, env.LegalActions(), true);     1
  env.StepAgent(action, agent_step);
  if (agent_step.done) {
    Update(state_key, action, agent_step.reward, -1, {}, true);
    break;
  }
  env.StepOpponentRandom(opponent_action, opponent_step);            2
  if (opponent_step.done) {
    Update(state_key, action, opponent_step.reward, -1, {}, true);
    break;
  }
  Update(state_key, action, 0.0, opponent_step.agent_state_key,
         env.LegalActions(), false);                                  3
}

1. 每步用 ε-greedy 选合法落子;非法位置会被环境拒绝(测试里专门测过)。
2. 训练对手默认随机;也可 --opponent optimal 对抗 minimax(更难学、收敛慢)。
3. 非终局步 reward=0,用对手走完后的新局面作 s′ 做 bootstrap——价值就这样从赢棋局面倒灌回开局。

for (int episode = 0; episode < option.episodes; episode++) {
  agent.RunEpisode(env, train_opponent, stats);
  agent.DecayEpsilon();                                              1
  // 每 5000 局打印: 累计胜/和/负、Q 表状态数、当前 ε
}

1. 与第 23 章 Train 的外层 epoch 类似,但数据不是固定数据集,而是自己下棋现生成的轨迹。

auto random_eval = agent.Evaluate(env, OpponentType::RANDOM, eval_games);
auto optimal_eval = agent.Evaluate(env, OpponentType::OPTIMAL, eval_games);
PrintEval("Eval vs random (greedy)", random_eval, eval_games);       1

if (option.play)
  PlayInteractive(env, agent);   // stdin 输入 0–8, 你是 O            2

1. Evaluate 内部 SelectAction(..., false),不再随机探索,测的是“学成之后有多强”。
2. --play 让你亲自和训练好的 X 下一盘;棋盘位置编号 0|1|2 / 3|4|5 / 6|7|8。