A self-play Q-learning agent looked competent in sampled matches: it drew against the original heuristic, won most games against random play, and produced plausible moves. Exact best-response evaluation told a different story. All six frozen baseline policy/seat cases could be forced to lose.
Tic-Tac-Toe made that discrepancy measurable rather than anecdotal. I could freeze each Q-table, keep its greedy decisions deterministic, and search every opponent branch for the worst achievable outcome. This is a best response to a fixed policy—not symmetric Minimax play.
The controlled progression
| Method | Force-loss policies | Strategic fixtures |
|---|---|---|
| Sampled self-play | 6/6 | 16/21 |
| + Opponent mixture | 6/6 | 20/21 |
| + Adversarial backup | 4/6 | 20/21 |
| + Adversarial backup + D4 | 0/6 | 21/21 |
Opponent mixture improved sampled behavior and fixed one conspicuous local error, but exact exploitability stayed at 6/6. That result weakens the hypothesis that broader sampled opponents alone were sufficient: the Bellman target still estimated the response that happened to be sampled.
The next intervention enumerated legal opponent responses and backed up the worst estimated continuation:
target = min_b [r_b + gamma max_a Q(s_b, a)]
That reduced exploitability to 4/6 and changed the residual failure type. The remaining mistakes were concentrated in sparsely updated state-actions and unresolved ties rather than high-confidence systematic misvaluation.
D4 canonicalization then pooled equivalent rotations and reflections. The reachable representation shrank from 4,520 to 627 states and from 16,167 to 2,270 state-actions. A historically sparse state went from 29 visits in one orientation to 169 pooled visits, allowing its action ranking to become Win > Draw > Loss.
Under the same Q-update budget, the final six policy/seat cases had zero force-loss vulnerabilities, passed 21/21 strategic fixtures, and selected exact-optimal greedy actions in 99.93–99.96% of reachable states.
This is a controlled evaluation and failure-analysis study in a deterministic, fully observable, exhaustively searchable environment. It is not a new general RL algorithm. Larger games, stochastic environments, partial observability, DQN, and PPO remain future work.
Top comments (0)