谜题 / 井字棋 · 一个被完全解出的游戏 / AI 怎么想:把每一步都算到终局 待审核 2 / 6
minimax · 向前看到底

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

完美一方不靠经验、不靠估值,靠穷举:对每个合法落点,假设此后双方都走最优,一路递归到终局,于是这步的结局是必胜、必和还是必负就完全确定了——这就是 Minimax 用在真实棋盘上。井字棋的树足够小,整棵都能算完。

注 · 每个空格上的数是在该处落子后、双方最优时的 minimax 分值:正数为必胜(绿)、00 为必和(灰)、负数为必负(红)。绝对值越大表示分胜负越快——分值按 10k10 - k 编码,kk 是连本手在内走到终局的手数,于是 +9+9 表示这一手立即连成,+7+7 表示还要走满 3 手。绿框是完美一方应走的最优着法。

图 0-1 · 每个空格标出落子后的 minimax 分值与最优着法。可点空格继续摆子搭局面,标注随之重算。

警示 · 最优着法不止一个:能赢时所有同样能赢的落点都对(只是有快慢之分),要和棋时所有守得住和的落点都对。真正致命的只有把必和或必胜走成必负那一步。这也解释了为什么再也赢不了——既然空盘起每个开局都标 00,双方都不犯错就只能平局。