谜题 / 井字棋 · 一个被完全解出的游戏 待审核 6 页

井字棋 · 一个被完全解出的游戏

井字棋 (tic-tac-toe / 圈叉 / OX) —— 3×3 棋盘, X 先手, 谁先把自己的记号连成横 / 竖 / 斜任意一条线即胜, 填满未连成则平局。规则简单到几乎人人会玩, 它却是博弈论里少数被「完全解出」(solved game) 的例子:整棵博弈树小到可以穷举, 于是「双方都不犯错会怎样」有确定答案 —— 必然平局。

本系列把这件事拆开看:先上手玩一局 (本地双人 / 对战完美 AI);再看 minimax 如何向前看到底给每一步定胜负;为什么对着完美一方再也赢不了;不输的下法(中心 / 角 / 双威胁 fork);整个游戏的状态空间到底有多大;最后用 WebRTC 搭一个无需自建后端也能两台设备真对战的联机版。与 alpha-beta 剪枝一节互补:那里讲「如何少搜博弈树」,这里讲「这棵树本身长什么样、能解出什么」。

先上手:把游戏跑起来

play · 可玩棋盘

上手玩：本地双人 / 对战完美 AI

系列的入口体验。一个能下的棋盘，本地双人轮流落子或对战 minimax 驱动的完美 AI，胜负即时判定并高亮连成的那条线。

完美对弈的内核:minimax 与「必和」

minimax · 向前看到底

AI 怎么想：把每一步都算到终局

对每个合法落点假设此后双方都最优、一路递归到终局，给这步标上必胜 / 必和 / 必负。分值还编码了最快几手分胜负。

solved · 为什么必和

为什么再也赢不了

solved game 的含义——从空盘起，九种开局在双方最优下全部通向平局。本页摆出九个开局的博弈论结果，并留一局给挑战方亲手验证。

strategy · 中心 / 角 / fork

不输的下法：威胁、防守与双威胁

一套八条的优先级清单就能保证不败，无需展开整棵博弈树。清单的关键一条是 fork——一步同时凑出两条将成之线，对手只能堵一条。

「解出一个游戏」分三档强度:其一 ultra-weak —— 只知道结果 (井字棋 = 和), 不给走法;其二 weak —— 给出从开局起保证该结果的策略;其三 strong —— 对任意合法局面都算出最优着法与结果。井字棋三档全部做到, 且小到能在一台手机上瞬间穷举。国际跳棋 (checkers) 2007 年被证明为 weakly solved (亦为和棋), 是迄今被解出的最复杂游戏之一;国际象棋、围棋则远超当前算力。

把整个游戏看全

count · 状态空间

这棋到底有多大：数一数

$9!$ 只是填满九格的排列上界。真正有意义的量在浏览器里现算：可达局面 5478、完整对局 255168、终局 958，对称归约后压到 765。

两人联机

online · WebRTC P2P

联机对战：无后端的 P2P 实现

用 WebRTC 在两个浏览器间直建 RTCDataChannel 传落子，信令降级为手动复制粘贴一段编码，于是连信令服务器都不需要。