数学游戏与谜题 · 游戏是数学的原初形态

本书怎么读：一门关于「玩」如何塑造数学的学问

本书只讲一件事：游戏性（playfulness）是数学最重要的特质。数学不是从「有用」开始的，而是从「玩」开始的——巴比伦的泥板上，人们为了好玩而排算数字；希腊人把竞技场上的争胜精神带进了几何证明（「设此为事实，则……」的每一次反证都是一次对局）；《九章算术》把解题写成「术」，一条「术」就是一段可以照着走的规则游戏；印度的谜题里藏着算法。而这场「玩」在二十世纪被彻底看穿：Hilbert 说数学是一场「按固定规则摆弄无意义记号的游戏」，Wittgenstein 说数学是「语言游戏」，Conway 更彻底——他直接把数定义成游戏：{ | } = 0，{0 | } = 1，{0 | 1} = ½，全部实数乃至超限序数都从对局中生长出来。本书要回答三个问题：为什么「有规则、有对局、有策略、有终局」这种结构恰好是数学最深的内核？为什么最漂亮的一些数学问题以游戏的面貌出现（Nim 的异或、Chomp 的策略偷取、Gale–Stewart 无限对局、Ehrenfeucht–Fraïssé 博弈刻画同构、交互证明 IP = PSPACE）？为什么「自由」——自由地选规则、自由地换视角、自由地玩——正是数学创造力的引擎？

本书不是一本益智游戏书。本册不教数独技巧，不收集脑筋急转弯，不写「巧解速算三百例」。每遇到一个游戏，要问的永远是三件事：它的数学结构是什么？它的策略能不能被证明？它通向哪一条定理、哪一个现代分支？——Nim 通向异或与 Sprague–Grundy 定理，Chomp 通向「策略偷取」这种不构造必胜法的存在性证明，超现实数通向序数的算术，折纸通向高次方程与 Galois 理论，赌局通向测度论与鞅，无限对局通向选择公理与决定性公理，生命游戏通向 Turing 完备性，围棋与扑克通向计算复杂性与现代博弈论。游戏的俗套是「好玩」；游戏的数学是「好玩背后的结构」——本书只玩后者。

本书按章组织：绪论摆出主旨——游戏为什么是数学的原初形态，从争胜、规则与自由三条线讲起，并给出全册路线图；第一章入门公平组合博弈——Nim 与异或判据（Bouton 定理）、P/N 位置、游戏的和与 Grundy 值（Sprague–Grundy 定理）、Chomp 与策略偷取、Wythoff 游戏与黄金比；第二章把数交给游戏——Conway 的 {L | R} 构造、生日归纳、超现实数是全序域、* 与 nimber、模糊（fuzzy）与非数游戏；第三章打开几何的游戏面——折纸公理与高次方程、Euler 的七桥与图论诞生、Hamilton 的 Icosian Game、15-拼图与置换奇偶性、魔方群、Hex 与策略偷取、铺砌与 Wang 砖块；第四章走进赌局——Pascal–Fermat 通信与期望的诞生、圣彼得堡悖论、赌徒破产、鞅与「赌博系统不可能」、随机游走与 Pólya 回归、Kuhn 扑克与混合策略、Monte Carlo；第五章玩到逻辑与无限——Gale–Stewart 的无限对局与决定性公理、Banach–Mazur 游戏与 Baire 性质、Ehrenfeucht–Fraïssé 博弈、证明的游戏（Curry–Howard 与对话）、生命游戏与 Turing 完备、扫雷与数独的 NP-完全性；第六章看现代前沿——von Neumann 的 minimax、Nash 均衡、演化博弈、机制设计与拍卖、乘法权重与学习、IP = PSPACE 与零知识证明、AlphaZero 的自我对弈，最后回到数学的自由精神；综合站用年表、人物谱、总图、两个综合实验与二十四题自查收束全书。

写作的三条约束（本书的自我要求）。① 结构先于技巧：任何一个游戏先摆棋盘、再定规则、再问「谁赢、为什么」，最后才谈胜负判据；判据必须被证明，而不是被「试出来的规律」冒充（把必胜判据统计当窍门，正是本书要打破的误读）。② 一步一图：凡能画的都画——Nim 的胜负位置树、Grundy 的递归 mex、{L | R} 的生日树、七桥的奇点计数、15-拼图的置换分解、魔方的置换环、赌局的二叉树、无限对局的博弈树、生命游戏的滑翔机。游戏最迷人的地方正在这些图上：一步棋、一次递归、一个等价，画出来便一目了然。③ 自给自足：不假设手边另有教材——异或与二进制、初等概率、群与置换、序数与良基归纳、可计算性的基本概念，都在需要它的那一页随用随补；每条定义同时给出形式陈述与一句大白话的直觉。个别深刻而整体的结论（Sprague–Grundy 定理、超现实数的域公理、Gale–Stewart 决定性、Nash 存在性、IP = PSPACE）给出精确陈述、完整证明思路与文献指引，数值与程序对拍在实验页随附、可自行复算。

页型节奏。每章以 导引 开篇（一页说清这一章要解决什么）；主体是 讲义 页（概念、定理、证明，一步一图）；每章配 例题 与 习题（先示范再放手）、知识地图 一页（本章概念怎么连成网）、小结（正面清单＋易错清单）、思想卡（一句话立起本章的哲学）、挑战（一道通向文献的硬题）、实验（一段可复算的程序）、格物札记（中西算学传统里的平行直觉）、速查表（本章公式与记号一页备翻）；章末另设 衔接讲义，把下一章的问题提前立起来。所有编号 可跳读：每一页都自带上下文，随手翻开一页也能读下去。

难度标记。讲义页用 ★–★★★★★ 标出阅读难度：★ 高中基础即可（Nim 的玩法、七桥、15-拼图），★★ 需要初等概率与线性代数的熟练经验（赌局、随机游走、魔方群，书内自给），★★★ 需要抽象代数与实分析的入门（Grundy 值的群结构、超现实数的域公理、Baire 性质，书内随用随补），★★★★ 需要数理逻辑与可计算性的经验（决定性公理、Ehrenfeucht–Fraïssé、Turing 完备、NP-完全性，书内随用随补），★★★★★ 需要现代博弈论与复杂性理论的观点（Nash 存在性、机制设计、IP = PSPACE、零知识，第六章疆界各页）。若只求理解主线，读绪论、第一章的 Nim 与 Sprague–Grundy、第二章的 {L | R} 与超现实数、第三、四章的经典游戏即可；若求完整掌握，按章顺序逐页推进，并把每章习题做完。

三条线索贯穿全书：

① 明线——从 Nim 到自由：一部「玩出来的数学」：先在公平组合博弈里学会「局面 = 结构、胜负 = 定理」（第一、二章），再把几何、概率、逻辑逐一带进游戏的语言（第三、四、五章），最后看现代数学如何把博弈当作定义与证明本身（第六章：均衡、机制、交互证明、自我对弈）——这正是数学从「消遣」长成「公理自由」的轨迹。

② 暗线——游戏三要素：规则、等价、策略。本书反复演练同一套动作：把游戏拆成局面（规则）、把局面化成标准形（等价，如 Grundy 值与超现实数的规范形）、再从标准形读出必胜策略（策略）。什么时候能把一个游戏「化简成数」，什么时候遇到了「非数的游戏」（*、↑），什么时候必须升到无限对局与公理层面，是全书的核心招式。

③ 接口——通往四个邻域。游戏是数学的枢纽：与代数（异或与二元域、游戏群、置换群）、概率与分析（期望、鞅、随机游走）、逻辑与计算（决定性、模型论博弈、计算复杂性、Turing 完备）三条战线直接相通，并与现代博弈论与经济学（均衡、机制设计）深度合流，第六章与综合站余韵两页逐条架桥。

写法约定（TEX 标准）：博弈记 G、H（变量斜体），局面记 s，P/N 位置记 𝒫、𝒩；异或（nim-sum）记 ⊕，Grundy 值记 𝒢(G)；游戏的和记 G + H；超现实数记 {L | R}，生日记 b(G)；博弈树记 T(G)；鞅记 M_n，期望记 𝔼。变量用斜体，函数名与算子名（mex、nim、Sprague、Grundy、Nash、IP、PSPACE）用正体；关键一步配图，规则与策略逐章对照。

扫码进馆：四十个页面的末尾附有二维码卡——手机扫码（或直接输入卡上的网址）即可打开对应的游戏工坊，本书讲到的每一座「馆」都能上手玩。卡片分属主站的两个专区：数学游戏工坊合集与解谜的艺术。全部馆的总入口见全册结构总览（p191）与速查页（p203）；书末另附「全书配套工坊总览」，纸书直接扫。

绪论 游戏：数学的原初形态导引：从「玩」开始

★ 二十世纪最著名的一本游戏研究著作给出了这样的定义：游戏是自由的（voluntary）、有规则的、自成目的的（把过程当作目的本身）活动。把这三条放在数学身上，会发现它们严丝合缝——数学的起点是自由（没有谁逼迫 Pythagoras 研究无理数），它的形态是规则（公理与推理规则），而它的目的从不是「有用」，而是把这场游戏玩下去、玩得漂亮。

本册的主张只有一个：游戏性是数学最重要的特质。不是「数学也可以娱乐」，也不是「游戏有助于学数学」，而是——规则、对局、策略、终局这四件事，构成了数学最内核的运作方式。有理数域上的二次互反律是一次漂亮的对局的结果；Nim 的胜负判据是一条线性代数定理；Conway 干脆把数定义成游戏。本册要沿着这条路走两千年：从希腊人把竞技精神带进证明，到 Hilbert 说数学是「按规则摆弄记号的游戏」，再到 Conway 把 ½ = {0 | 1} 写成一场对局，最后到 AlphaZero 在棋盘上自己教自己下棋。

本册不是一本益智游戏书。我们不教数独技巧，不收集脑筋急转弯，不写「巧解速算三百例」。每遇到一个游戏，要问的永远是三件事：它的数学结构是什么？它的策略能不能被证明？它通向哪一条定理、哪一个现代分支？游戏的俗套是「好玩」；游戏的数学是「好玩背后的结构」。一个游戏只有能生出一门学问，才配写进这本书。

读法（绪论 → 六章 → 综合站）。绪论建立语感：争胜、规则、自由三条线，加上判据、年表与路线图；第一章取子游戏与博弈的群结构（Nim → Sprague–Grundy）；第二章数即游戏（Conway 的超现实数）；第三章几何的游戏（折纸、七桥、魔方群）；第四章概率与策略（赌局中的数学）；第五章逻辑与无限的游戏（策略、选择与不可判定）；第六章现代前沿（博弈论、算法与数学的自由精神）。综合站收全册。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

数学游戏工坊合集专区入口四十六座工坊总入口，按群论·幻方·组合博弈分类philomath.cn/coll.html解谜的艺术专区专区入口逻辑推理 · 密码破译 · 图形拼合 · 益智趣题philomath.cn/puzzle.html

绪论 游戏：数学的原初形态争胜：证明是一场对局

★ 数学的第一次自我认识发生在希腊。Homer 笔下的英雄在竞技场上争胜（agōn），而 Euclid 把这种精神搬进了纸面——《几何原本》的每一个命题都是一场结构完整的对局：先从对手必须点头的前提出发（定义、公设、已证命题），再一步步走子（推理），最后把对手逼到无处可退（结论）。证明之所以要求「无懈可击」，正因为它在字面上是一场谁都无法耍赖的比赛。

反证法是这条线索最纯粹的形态。要证明「素数无穷多」，我们先替对手摆好立场——假设只有有限多个素数，然后按规则走子：把它们乘起来加一，得到的数既不被任何一个整除，又不可能是别的素数。对手被将死了。这个动作的形状：假设对手的立场 → 沿着规则推演 → 逼出矛盾。这正是一个双人博弈中「先手走一步、后手应对、直到分出胜负」的标准剧本。

希腊人还给这门游戏定下了「裁判规则」。哪些前提可以直接引用（公设与已证命题）、哪些步骤被允许（三段论）、什么算赢（矛盾或无矛盾的构造）——这一切在今天被写成形式系统的四要素，而在本册的语汇里，它就是棋盘、走法、终局。数学史上每一次基础危机（无理数、无穷小、集合论悖论），本质上都是有人发现棋盘上出现了一步无法判定的棋，于是数学家重画棋盘、重写规则，然后接着玩下去。

这场对局在二十世纪被重新发现了两次。一次是证明论中的「对话」观点：每一句话都由一方主张、另一方质疑，逻辑联结词获得游戏论的解释（第五章会讲到 Curry–Howard 对应与对话语义）；一次是复杂性理论中的交互证明：证明者与验证者来回若干轮，验证者只在以极大概率被说服时接受——IP = PSPACE 定理说的正是「凡能被一场交互对局说服的，都可以被一场多项式空间的证明说服」（第六章）。从 Euclid 的纸面对局，到 P 与 V 的电线两端，数学一直是同一件东西：一场诚实的比赛。

绪论 游戏：数学的原初形态规则：Hilbert 的记号游戏

★ 二十世纪的第一次回答来自 Hilbert：数学是一场按固定规则摆弄无意义记号的游戏。这个说法当年听起来像挑衅——「数学研究的真理与意义，被说成了符号游戏？」但它其实是一个精确定义的纲领：把数学写成形式系统：给出符号表、规定哪些符号串合式、列出公理、列出推理规则，然后「定理」就是能被规则一步步生成出来的符号串。

把这份定义与游戏对照，会发现它们逐条对齐。符号表是棋子与格位，合式规则是合法摆法，公理是开局布局，推理规则是允许的走法，而定理就是「按规则能走到、并停在终局」的局面。Hilbert 的纲领因此可以翻译成一句话：数学的可靠性 = 这场游戏不会把合法的局面走到自相矛盾。他想证明的「一致性」，就是证明棋盘上永远走不出「既赢又输」的死局。

Wittgenstein 把这条线推得更远。在他看来，数学根本不是关于对象的科学，而是一族语言游戏（Sprachspiel）：符号的意义由它在游戏中的用法决定，而不是由它指称的对象决定。「2 + 2 = 4」之所以为真，不是因为某个柏拉图世界里的对象恒等，而是因为我们同意这样玩——规则是我们立的，因此也可以被改写。这一观点把「数学是发明还是发现」的争议转化成了更锋利的问题：规则的边界在哪里？我们能否走出自己立的规则？

五年之后，Gödel 给出了一个令人不安的答案：任何足够强的、一致的形式系统，都无法在自身内部证明自身的一致性；而且总存在「真但不可证」的命题。用游戏的比喻说：存在一些局面，规则既不能判它赢、也不能判它输——但作为「站在棋盘外的人」，我们看得见它是真的。这正是本册的核心张力：规则给了数学严谨，而规则的不完备给了数学自由。因为无法被规则穷尽，数学才必须不断创造新规则、新棋盘、新游戏——这就是 Hilbert 的形式游戏留下的最美遗产。

绪论 游戏：数学的原初形态自由：当数被定义成游戏

★★ 如果说 Hilbert 把数学看成游戏，那么 Conway 走得更远：他让数学成为游戏。一九七〇年前后，Conway 在研究围棋终局时发现，每一种局面都可以抽象成一个「游戏」，而两个游戏可以相加（两盘棋同时进行），于是问题变成：「游戏」这种对象，能不能像数一样被加、被比较、被排序？他的回答写成了《On Numbers and Games》——一本书同时造出了两样东西：组合博弈论与超现实数。

构造只有一行：G = {L | R}，其中 L、R 是已经造好的游戏（分别表示「左方可走到的局面」与「右方可走到的局面」）。从空集开始：{ | } 是零号游戏，记作 0——没有走法，谁先走谁输，正是一个「零和的中立局面」。于是 {0 | } 是 1（左方可以先走到 0，把「先走者输」的局面交给对方），{ | 0} 是 −1，而 {0 | 1} 恰好是 ½——因为它「夹」在 0 与 1 中间，正是那个最小的、大于 0 又小于 1 的数。

「生日」是这套构造的时间轴。空集是第 0 天造出的；用已有的游戏当左右集合，得到第 1 天的 1、−1；第 2 天得到 2、½、−½、−2；如此下去，用超限归纳一直走到第 ω 天，就得到 ω 本身（第 n 天所有的自然数都被造完之后，那个「比所有自然数都大」的游戏），再往下还能造出 1/ω、√2、π……全部实数，乃至比实数丰富得多的对象，都从一场游戏中长了出来。第二章会用整整一章来完成这件事：证明这样造出的对象构成一个全序域，并让第一章的 Grundy 值在这里找到归宿。

这里藏着本册主线的第二个关键词：自由。数学的自由有三重形态。第一重是自由地选公理——十九世纪，Lobachevsky 与 Bolyai 拒绝 Euclid 的第五公设，造出了非欧几何：既然第五公设不能被前四条推出，我们凭什么不能反过来假设它不成立？这一跃换来了一整个新的几何宇宙（第三章的折纸会再遇到它）。第二重是自由地造对象——Cantor 造出无穷基数，Conway 造出超现实数：数学对象的合法性来自「能否被无矛盾地定义」，而不是来自「能否被直观到」。第三重是自由地换视角——Klein 的 Erlangen 纲领说：「几何学」就是「在某个变换群下不变的性质」，于是同一条定理由不同的群就有了不同的身份（第六章回望）。正因为数学是一场自由的游戏，它才能不断自我超越；而正因为游戏有规则，这份自由才不会滑向任意。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

数之日 · 超现实数工坊合集从 {L | R} 逐天造出所有的数philomath.cn/surreal/

绪论 游戏：数学的原初形态什么是数学游戏：四条判据

★ 现在该给「数学游戏」下一个可操作的判据了。日常语言里的「游戏」太宽（赌博是游戏、电子游戏是游戏、孩子的过家家也是游戏），本册需要一条能划出数学疆域的标准。我们采用四条判据：① 规则清晰（每一步的合法走法由规则完全确定）；② 状态可判定（局面是数学对象，可以判定、比较、计数）；③ 终局与胜负明确（什么时候结束、谁赢，有精确定义）；④ 策略可被证明（胜利判据能够被数学地证明，而不是靠「试了很多次都对」）。

第四条是关键，也是本册与「益智」的分水岭。很多游戏都能被「玩」出规律：试 n = 1, 2, 3… 全对，于是宣称「必胜法」。数学不接受统计归纳——判据必须来自结构，必须能被证明对所有局面成立。第一章的 Bouton 定理之所以是定理而不是窍门，正在于它给出了证明：Nim 的胜负由各堆石子数的按位异或是否为零完全决定，与堆数、石子数的大小无关。

四条判据把游戏分成四个家族。最纯的一族是公平组合博弈（impartial combinatorial game）：双方可走的走法完全相同，局面有限，无平局，终局永远是「不能动者输」——Nim、Chomp、Wythoff 游戏、Green Hackenbush 都属这里，第一章与第二章的主战场。第二族是一般零和博弈：规则可以不对称、可以含随机，胜负由收益矩阵给出，需要「混合策略」与 minimax 定理，扑克与拍卖在其中，第六章的主战场。第三族是无限对局：局数没有长度限制，胜负由「谁活到最后」判定，Gale–Stewart 与决定性公理所在，第五章的主战场。第四族是单人谜题：没有对手，但有规则与目标，于是「能否解出」变成一个判定问题，难度可以被测量——数独是 NP-完全、扫雷是 NP-完全，这是第四章与第五章的连接点。

划清边界之后，还要说清本册不写什么。不写纯技巧性的魔术（如「猜你想的数」这类把戏），因为它们没有可证明的结构；不写需要偶然运气的纯赌博（如彩票号码「规律」），因为它把胜负交给了概率而非策略；也不写「大脑训练」式的题目汇编，因为那里的目标是熟练度而不是理解。本册收录的每一个游戏，都必须能带出一张定理、一个构造或一个计算模型——这是筛选标准，也是本书的趣味所在。

绪论 游戏：数学的原初形态两千年的一瞥：从赌局到 AlphaZero

★ 本册的历史观可以用三个转折点概括：每一次都是某个游戏逼出了数学的一大块新领域。

转折一：赌博 → 概率（1494–1654）。概率论的第一次呼吸来自赌桌。Pacioli 在《算术大全》里提出「未完成的赌局如何分赌本」，一百多年没人答对；直到 Pascal 与 Fermat（1654）在通信中用期望解决了它，概率论才开始有了自己的语言。随后 Cardano 早在十六世纪就写下《论赌博游戏》的手稿（出版却在死后），Huygens 把期望整理成公理。赌博不生产数学，但它迫出数学：期望、大数律、鞅、随机游走，全都是在「为什么赢不了」这个问题的压力下长出来的（第四章）。

转折二：取子 → 代数（1901–1970）。「谁取最后一颗石子谁赢」这类游戏看似幼稚，却需要真正的代数工具。一九〇一年 Bouton 发表 Nim 的异或判据——这是二元域上的线性代数第一次出现在游戏的胜负表里；此后 Sprague（1935）与 Grundy（1939）各自独立证明了那一定理：任何公平博弈都等价于一堆 Nim 石子，其「大小」由 Grundy 值给出。博弈于是构成了一个加法群。到了 Conway 那里（1970），游戏与数合流：{L | R} 既是局面又是数（第一、二章）。

转折三：对局 → 公理（1913–1975）。如果把游戏玩到无限，规则还够用吗？Zermelo 在一九一三年用选择公理讨论无限棋局；Gale 与 Stewart（1953）证明：任何开集上的无限对局都是决定的——一方必有必胜策略，这条定理在 ZFC 内可证，且不需要选择公理之外的东西。一旦把「所有对局都可决定」当作公理（AD），就与选择公理发生冲突——两种数学宇宙在此分道。二十世纪七十年代的无穷博弈理论最终让决定性成为描述集合论的核心议题（第五章）。

当代的续章。这份年表并没有停在上个世纪。二〇〇二年，Kayes 等人证明扫雷的判定问题是 NP-完全；二〇一六年 AlphaGo 击败人类顶尖棋手；一年后的 AlphaZero 用自我对弈从零学会国际象棋与围棋，把「博弈 + 学习」写成算法史上最著名的实验之一；二〇二三年起，Lean 与 Mathlib 让形式化证明进入机器可校验时代——Hilbert 的「符号游戏」终于有了真正的游戏机。游戏既是数学最古老的面貌，也是它最新鲜的战场。

绪论 游戏：数学的原初形态全册路线图

★★ 全册的旅行可以画成一张两行的图（上图）。第一章与第二章是最纯的组合博弈：先把「公平博弈」拆成局面的有向图，用 Nim 学会异或判据，再把「值」的思想推到极致——Conway 把数本身变成游戏。第三章转向几何：折纸、七桥、15-拼图、魔方群让「游戏」长出拓扑、图论与群论的骨架。第四章是概率：赌局迫使数学发明期望与鞅，并在随机游走与扑克中演示混合策略。第五章进入逻辑与无限：无限对局逼出决定性公理，Ehrenfeucht–Fraïssé 用游戏刻画同构，生命游戏与扫雷把游戏连到 Turing 完备与 NP-完全。第六章是现代前沿：博弈论、机制设计、交互证明、自我对弈，最后回到「数学的自由精神」。综合站把六章收成一张年表、一张总图与两个可复算的实验。

每一章带走的「一张支票」。第一章：给定任何公平博弈，我能判断谁赢，并把它的值算成一个数。第二章：我能说明「数从何而来」，并把游戏的和、序、等价纳入一个域。第三章：我能把一个几何游戏翻译成图、置换群或拓扑定理。第四章：我能计算一个赌局的期望、终局概率，并证明某类必胜系统不存在。第五章：我能陈述支配有限与无限对局的定理，并把谜题的难度写成复杂性类。第六章：我能陈述 Nash 均衡的存在性，并说明交互证明与零知识「为什么是游戏」。

四条准备知识（书内随用随补）。① 二进制与异或：位运算的算术（第一章 p11 起给足）；② 初等概率：期望、条件概率、独立（第四章 p100 起给足）；③ 置换与群：群、轨道、置换的奇偶性（第三章 p88 起给足）；④ 序数与归纳：超限归纳与良基序（第二章 p46 起给足）。只要具备高中代数的熟练度，本书的全部主线（第一、二、三、四章）都可读通；第五、六章需要一点数理逻辑与复杂性的耐心，但概念都在书内首次出现时解释。

读法建议（三种）。其一，主线速读：绪论 → 第一章（Nim、Grundy）→ 第二章（超现实数）→ 综合站，约四十页，把「局面 = 数」这条最漂亮的思想吃透。其二，主题跳跃：对几何感兴趣从第三章切入，对概率从第四章切入，对逻辑从第五章切入——每章首页的导引与地图页都足以独立成篇。其三，完整研读：按章顺序推进，做完全部习题与挑战，两个综合实验自己动手复算。无论哪条路，本册的口令：先问结构，再问策略，最后问它通向哪条定理。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

数学游戏工坊合集专区入口四十六座工坊总入口，按群论·幻方·组合博弈分类philomath.cn/coll.html解谜的艺术专区专区入口逻辑推理 · 密码破译 · 图形拼合 · 益智趣题philomath.cn/puzzle.html

绪论 游戏：数学的原初形态绪论小结：游戏与自由

★ 绪论小结：游戏与自由。

六页语感的账目。① 争胜：证明在结构上是一场对局，反证法是「让对手先走」（p3）；② 规则：Hilbert 把数学定义为「按规则摆弄记号的游戏」，形式系统与游戏四要素逐条对应（p4）；③ 自由：Conway 用 {L | R} 把数造出来，数学自由的三种形态（选公理、造对象、换视角）（p5）；④ 判据：数学游戏的四条判据，与「益智」的分水岭在「策略能否被证明」（p6）；⑤ 年表：赌博 → 概率、取子 → 代数、对局 → 公理三个转折（p7）；⑥ 路线图：六章 + 综合站 + 四条准备知识（p8）。

本册的语法（四句话，先背下来）。① 「摆」：把游戏写成局面构成的有向图——棋盘先画出来，问题就看得见；② 「算」：给局面找一个不变量（异或、Grundy 值、期望、势函数），让胜负变成不变量的比较；③ 「化」：把局面化成标准形（等价类、规范形、数值），两个游戏同时进行就变成两个标准形相加；④ 「证」：任何判据都必须被证明对整个游戏类成立——这是本册与「益智书」的根本区别。

方法论预告（三条）。① 「先有限，再取极限」：组合博弈先假设局面有限，无限对局则交给公理（第五章）；② 「换个对象看同一个问题」：同一个 Nim 在石子数、二进制向量、nimber、超现实数四个层面各有面貌，其中必有一层让答案显形；③ 「难度也是定理」：一个谜题「难」不是感觉，而是可被写成 NP-完全、PSPACE-难或不可判定的命题。

与相邻领域的握手。会发现：第一章的 Grundy 值正是那里「不变量与结构」思想的化身；在 Wythoff 游戏与 Beatty 序列里认出黄金比的老朋友；在第六章的博弈论里看到「不动点定理」的重现（Nash 均衡）；在 Hex 的「不可能平局」里遇到 Jordan 曲线定理。同一批事实，换一种语言，就换一种力量——这正是本册反复要演示的事。

下一章预告。第一章「取子游戏与博弈的群结构」：从最简单的一堆石子开始，用二进制与异或算出 Nim 的胜负，把 P/N 位置画成一棵树，然后证明 Sprague–Grundy 定理——任何公平博弈都等价于一堆 Nim 石子，而它的「大小」可以算出来。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy本章导引：从一堆石子开始

★ 本章从全世界最简单的游戏之一出发。Nim 的规则只有一句话：桌上若干堆石子（数目任意），两人轮流从任意一堆中取走任意正数颗石子，取走最后一颗石子的人获胜。它简单到可以在餐巾纸上玩，却完整地藏着一个代数结构——本章要把它挖出来，并顺着它走到组合博弈论的核心定理。

为什么从一个「幼稚」的游戏开始？因为 Nim 是公平组合博弈的原子：一九〇一年 Bouton 给出它的胜负判据（异或为零者必败），一九三九年前后 Sprague 与 Grundy 各自证明了一个惊人的一般结论——任何有限无平局的公平博弈，都等价于一堆大小确定的 Nim 石子。这个「大小」就是 Grundy 值。于是「谁会赢」这个看似要看遍全盘棋谱的问题，被压缩成了一次位运算。

本章的路线（见上图）。先备好两件工具：二进制与异或（p11）、P/N 位置与逆推（p13）；然后用它们证明 Bouton 定理（p14）并看清它其实是二元域上的线性代数（p15）。接着做第一次抽象升级：把「两个游戏同时进行」定义成游戏的和（p16），引出 mex 与 Grundy 值（p17），证明 Sprague–Grundy 定理（p18–p19），并看到博弈的等价类构成一个交换群（p21）。最后用四个漂亮的应用收尾：竹节游戏（p20）、Chomp 与策略偷取（p22）、Wythoff 游戏与黄金比（p23）、对称与配对策略（p24）。

本章要建立的动作，将贯穿全书：① 把游戏画成有向图（局面是顶点，走法是边）；② 给局面找一个不变量（异或、Grundy 值），使胜负变成不变量的比较；③ 把局面化成标准形（一堆等价大小的 Nim 石子），使「并行」变成「相加」。学会这三个动作，就掌握了组合博弈论的全部直觉。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.1 二进制、异或与位运算

★ 本章要用到的唯一工具是异或（exclusive or，记 ⊕）。它的定义简单到可以写进一行：两个二进制位相同则为 0，不同则为 1。把两个数写成二进制后逐位异或，就得到它们的异或。例如 5 = 101₍₂₎、3 = 011₍₂₎，逐位异或得 110₍₂₎ = 6。

异或记成「无进位的加法」。普通加法在两位都是 1 时会进位（1 + 1 = 10₍₂₎），而异或把进位直接丢掉（1 ⊕ 1 = 0）。丢掉进位之后，「加法」这个操作变得异常温顺：它满足交换律、结合律，每个元素自己是自己的逆元（a ⊕ a = 0），而 0 是单位元。用代数的话说：整数在异或下构成一个 ℤ₂ 上的向量空间——这正是本章定理「线性」味道的来源。

为什么异或会出现在 Nim 里？先记住一个直觉：异或度量的是「两个局面差在哪里」。若一堆石子被取走若干，它的二进制会变；异或恰好把这「变化」记录成一组「哪些位不同」的标记。在 Nim 中，胜负判据将恰好是「各堆石子数的异或是否为零」——「为零」意味着这些堆两两之间在每一位上都「配平」了，像一个完美的对称局面。而对称的局面，正是后手方最想看到的（p24 会把这个直觉讲透）。

三个必须练熟的运算事实（后面反复使用）：① 异或的逆运算就是它自己：若 a ⊕ b = c，则 a = b ⊕ c——这条让「回零」的操作总可以实现；② 异或为 0 的一组数中，任何非空的子集的异或等于其余部分的异或——这条让对手无法破坏对称；③ 若一组数的异或非 0，则该组的最高位（最高那个 1）必出现在奇数个元素中——这条是 Bouton 定理证明的钥匙（p14）。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.2 Nim：规则与第一印象

★ 规则。桌上有 n 堆石子，第 i 堆有 a_i 颗。两位玩家轮流行动，每次必须从恰好一堆中取走至少一颗（可以取光整堆，但不可以跨堆取）。轮到谁时桌上已经没有石子，谁就输了——等价地说：取走最后一颗石子的人获胜。这就是 Nim（据说名字来自德语 nimm，「拿」）。

先玩两分钟，找找感觉。一堆石子：先手一次取光，必胜。两堆相等，比如 (4, 4)：先手无论怎么取，后手只需在另一堆取同样多，就能保持两堆相等；最后后手取完最后一颗——两堆相等是必败位置。两堆不等，比如 (3, 4)：先手把 4 那堆取成 3，局面变成 (3, 3) 交给对手——必胜走法就是「造出对称」。三堆呢？(1, 2, 3) 该往哪里走？(3, 4, 5) 呢？纯靠观察会越来越吃力——我们需要一个判据。

Nim 的三个特点，让它成为「原子游戏」。① 公平（impartial）：双方可走的走法完全相同，规则不区分玩家；② 有限且无平局：石子总数每走一步严格减少，游戏必然在有限步内结束，且一定有一方无法行动（也就是输）；③ 完全信息：局面公开，没有隐藏信息。凡是满足这三条的博弈（走法可相同、有限、无平局），本章称公平组合博弈。Sprague–Grundy 定理将说明：所有这样的游戏，胜负结构都不过是若干个「Nim 堆」的组合。

一个反直觉之处：堆的大小不重要，堆的「二进制形状」才重要。后面会看到，(1, 2, 3) 是必败位置，而 (1, 1, 1) 是必胜位置；(2, 2) 必败，而 (1, 2) 必胜。规律显然与数字的大小关系不大——这一切将由异或刻画。先把 (3, 4, 5) 这个「先手必胜」的例子放在这里：3 ⊕ 4 ⊕ 5 = 2 ≠ 0，必胜走法是把第三堆取成 3 ⊕ 4 = 7……等等，7 比 5 大，取不到；正确的算法在 p14 给出，那里会说明为什么「回零走法」总能存在（若不大于原堆就要换一堆算）。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

珍珠劫 · NIM工坊合集异或必胜密码，五级闯关philomath.cn/nim/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.3 P 位置与 N 位置：逆推法

★★ 判定博弈的第一步，是把「赢」这个动态概念换成一个静态标签。我们给每个局面两种标签：𝒫 位置（Previous player wins，上一位行动的玩家获胜，也就是「轮到谁走谁必败」）与 𝒩 位置（Next player wins，「轮到谁走谁必胜」）。终局（没有石子，无法行动）显然是 𝒫 位置——轮到的人无路可走，判负。

逆推三律（把标签从终局推回开局）。① 终局标 𝒫；② 若某局面能一步走到 𝒫，它标 𝒩（把必败的局面甩给对手）；③ 若某局面所有走法都只能走进 𝒩，它标 𝒫（无论怎么走，对手都能赢）。这三条规则是自洽的：因为游戏有限且无平局，每个局面要么能一步入 𝒫（则它是 𝒩），要么所有后继都是 𝒩（则它是 𝒫），二者必居其一，绝不会出现「无法判定」的局面。

逆推法给出一个算法，但它通常太慢。对于 Nim，只要堆数或堆的大小稍大，局面数就爆炸（三堆各 30 颗就有 31³ ≈ 3×10⁴ 个局面，实际游戏里动辄上亿）。我们需要的不是「算得出来」，而是一条闭式判据——一个像「异或是否为零」这样的公式，能立刻判定任意局面。这正是 Bouton 定理的价值：它把「逆推」换成了「按位异或」。

先看两堆的小表（下图）。把第 1 堆与第 2 堆的数目排成一张 5×5 的表，按逆推填标签：(0,0) 是 𝒫；任何能走到它的（(0,1)、(1,0) 等）是 𝒩；再往上是……填完会看到对角线全是 𝒫，其余全是 𝒩——「两堆相等者必败」。用异或检验：a ⊕ b = 0 恰好等价于 a = b。表格与异或判据的吻合，是本章定理的第一个证据。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.4 Bouton 定理：异或判据

★★ Bouton 定理（1901）。在 Nim 中，局面 (a₁, …, a_n) 是 𝒫 位置（轮到者必败）当且仅当 a₁ ⊕ a₂ ⊕ ⋯ ⊕ a_n = 0。换言之：各堆石子数的异或为零者必败，非零者必胜。

证明（两个方向，都只用「逆推三律」）。为叙述方便，记局面的值为 X = a₁ ⊕ ⋯ ⊕ a_n。

方向一：若 X = 0，则任何合法走法之后 X ≠ 0。一次走法只改变一堆，设把 a_i 改成 a'_i < a_i。新值 X' = X ⊕ a_i ⊕ a'_i = a_i ⊕ a'_i（用到 X = 0）。因为 a_i ≠ a'_i，所以这个异或非零。从零出发永远回不到零——终局（全零，X = 0）扮演了「陷阱」的角色：走进它的对手只能把非零局面交还出去。

方向二：若 X ≠ 0，则存在一步走法使 X = 0。设 X 的二进制中最高位的 1 在第 k 位（从 0 开始数）。因为异或的每一位等于「这一位为 1 的堆数的奇偶性」，所以有奇数个堆在第 k 位上是 1。取其中一个这样的堆，设它是 a_i，令

a'_i = a_i ⊕ X

关键的两点：① a'_i < a_i——因为 X 的最高位是第 k 位，而 a_i 在第 k 位上是 1，异或后这一位变 0、更高位不变，所以数值变小；② 把 a_i 换成 a'_i 后，新的异或为 X ⊕ a_i ⊕ a'_i = X ⊕ X = 0。于是任何非零局面都存在一步「回零走法」，且这一步合法（取走的石子数为正）。

合起来。终局异或为 0 且是 𝒫 位置；由方向一，异或为 0 的局面不可能走到异或为 0 的另一个局面，故它们「彼此隔离」；由方向二，异或非 0 的局面总能走到异或为 0。用逆推三律自终局反向归纳即得：异或为 0 ⟺ 𝒫 位置。◻

回头看 (3, 4, 5)：3 ⊕ 4 ⊕ 5 = 010₍₂₎ = 2 ≠ 0，最高位是第 1 位（值 2），在第 1 位为 1 的堆是 3（011）与 5（101）——取 5：5 ⊕ 2 = 7 > 5 不合法；取 3：3 ⊕ 2 = 1 < 3 合法。必胜走法：把第一堆从 3 取成 1，得 (1, 4, 5)（验证 1 ⊕ 4 ⊕ 5 = 0 ✓）。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

珍珠劫 · NIM工坊合集异或必胜密码，五级闯关philomath.cn/nim/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.5 异或的代数：ℤ₂ 上的向量空间

★★ Bouton 定理可以用线性代数的语言重写一遍，重写之后为什么它是「代数」而不是「窍门」就一目了然了。

把每个堆看成一个向量。设最大堆不超过 2^m − 1，则每个 a_i 可以写成 m 位二进制，也就是 ℤ₂^m 中的一个向量（在 ℤ₂ 里，1 + 1 = 0）。逐位异或恰好就是向量加法。于是 Bouton 定理变成一句话：局面是 𝒫 位置 ⟺ 全部堆向量之和为零向量。

「和为零」是一张对称性证书。在向量空间里，一组向量之和为零意味着它们「张成的部分互相抵消」——用扑克的比喻，就是这些堆的每一位上都有偶数（含零）次出现，形成完美的配对。这个视角下，后手的策略变得可以一句话说清：无论先手动哪一堆（在哪些位上做了改动），后手只需在「其余的堆」中补上同样的改动，就能把总和重新压回零；而方向二保证只要总和非零，就一定存在这样一处「补账」的位置（具体是哪一堆，由最高位决定）。「补账」在 ℤ₂ 里永远可行，因为每个元素都是自己的逆元。

线性代数的三个直接好处。① 判定是线性的：扫描一遍所有堆，累加异或即可，时间复杂度 O(n)，与堆的数值大小无关；② 必胜走法可构造：算总和 X，找最高位、找该位为 1 的堆、把它改成 a_i ⊕ X，O(n) 完成；③ 多种必胜走法可枚举：所有满足 a'_i = a_i ⊕ X < a_i 的堆都是候选——这也是习题 1 的一部分。

一个警示。把 Nim 看成线性代数，意味着它的「结构」是线性结构；后面遇到的博弈若不再是线性的（如 Chomp、Wythoff），异或判据就失效，需要更一般的「Grundy 值」。但：Grundy 值理论的一般结论仍然说「每个博弈等价于一个 Nim 堆」——Nim 的线性结构，将成为一切公平博弈的「标准坐标」（p18）。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.6 游戏的和：两盘棋同时下

★★ 现在做本章最重要的一次抽象升级。Nim 之所以能被理论刻画，是因为它的局面有一个隐藏的加法结构：每一堆是一个独立的小游戏，整个 Nim 是这些小游戏「同时进行」的结果。把这一点形式化，就能把「多个游戏」变成一个「游戏」。

定义（游戏的和，disjunctive sum）。设 G、H 是两个公平博弈。它们的和 G + H 定义为一个新游戏：一个局面是「G 的一个局面」与「H 的一个局面」组成的有序对；轮到某人行动时，他必须选择其中一个游戏并走一步，另一个不动；谁无法行动（两个游戏都无法动）谁输。用石子的话说：桌上有两堆，但每次只许从一堆里取——这正是 Nim 的规则本身。

于是 Nim 获得了自己的身份。把「一堆 a 颗石子、每次取至少一颗」这个单人游戏记作 ∗a，则

Nim(a₁, …, a_n) = ∗a₁ + ∗a₂ + ⋯ + ∗a_n

而 Bouton 定理说的是 𝒢(∗a) = a（一堆 a 的「值」就是 a），并且和的值等于值的异或：𝒢(G + H) = 𝒢(G) ⊕ 𝒢(H)。这条公式将在 p18 的定理中成为主角，它是「游戏的和 ↔ 数的加法」这座桥的最后一根梁。

为什么「和」的定义是自然的？因为它精确对应现实中的情形：一个棋盘上几个不互相干扰的区域（围棋终局的几块孤棋）、桌上几堆独立的石子、若干块互不相邻的多格骨牌——这些局部的走法互不影响，胜负却由它们共同决定。把局部抽象成游戏、把整体写成局部的和，是从「玩一个游戏」到「做一门理论」的第一步。下一节给每个游戏分配一个数（Grundy 值），加法规则就完全清楚了。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.7 mex 与 Grundy 值

★★ 现在给每个公平博弈分配一个数——这就是 Grundy 值（也叫 nimber 值、nim-value）。它的定义只用到一个运算：mex。

定义（mex）。对任意非负整数集合 S，mex S 是最小的不属于 S 的非负整数。例如 mex{0,1,3} = 2、mex{1,2} = 0、mex{0,1,2} = 3、mex ∅ = 0（空集时最小缺席者是 0）。mex 是「找第一个缺口」的操作：把集合里的数从小到大排好，从 0 开始数，第一个没出现的数就是它。

定义（Grundy 值）。对游戏 G，

𝒢(G) = mex{ 𝒢(G′) : G′ 是 G 的一步后继 }

这是一条递归定义：要算 𝒢(G)，先算出所有后继的 Grundy 值，再取 mex。因为游戏有限（走法使局面严格「下降」），递归会终止。终局（没有后继）的值是 mex ∅ = 0。

三条立刻可见的性质。① 𝒢(G) = 0 ⟺ G 是 𝒫 位置——因为「值非零」意味着后继中有值为 0 的（mex 的定义保证：若 k = mex S ≠ 0，则 0 ∈ S），而「值为零」意味着后继里没有 0；② 一堆 a 颗石子的 Grundy 值恰是 a：因为从 a 能走到 0, 1, …, a − 1，故 𝒢(∗a) = mex{0,1,…a−1} = a——这解释了 Bouton 定理里为什么「异或」是对的；③ Grundy 值可以重复出现：不同的博弈可以有相同的值，这正是下一节「等价」的基础。

把 Grundy 值当成「游戏的大小」。直觉上：值为 k 的游戏，在各种「组合」中表现出的作用和一堆 k 颗的 Nim 完全相同。下一节的 Sprague–Grundy 定理将把这句话变成精确的定理：在「和」的意义下，𝒢 值相等就是等价。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

多堆 NIM工坊合集多堆取子的异或判据philomath.cn/moore/珍珠劫 · NIM工坊合集异或必胜密码，五级闯关philomath.cn/nim/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.8 Sprague–Grundy 定理（陈述）

★★★ 组合博弈论的第一基本定理，由 Sprague（1935）与 Grundy（1939）各自独立证明。它的分量之重，值得反复读三遍。

定理（Sprague–Grundy）。设 G 是任意有限、无平局的公平博弈，𝒢(G) 是它的 Grundy 值。则对任意公平博弈 H：在「游戏的和」意义下，G 与「一堆 𝒢(G) 颗石子的 Nim」扮演完全相同的角色。特别地：

𝒢(G₁ + G₂ + ⋯ + G_n) = 𝒢(G₁) ⊕ 𝒢(G₂) ⊕ ⋯ ⊕ 𝒢(G_n)

读法一（胜负）。由它立刻得到本章反复用的判决：𝒢(G) = 0 ⟺ G 是 𝒫 位置。而「G 与一堆 0 颗等价」的另一面刻画更有名：G 是 𝒫 位置 ⟺ G + G 是 𝒫 位置——两个一模一样的游戏并排（后手总能镜像对手的走法，p24 会证明），谁也无法靠「自己的那一份」占便宜。于是「值相等」可以被定义为「差为零」，就像整数一样（p21 展开）。

读法二（计算）。要判断一个复杂博弈的和谁赢，只需：① 把整体拆成互不干扰的分量；② 对每个分量单独算 Grundy 值（分量局部小，递归可行）；③ 把所有值异或起来：非零则先手必胜，为零则必败；④ 若要找必胜走法，则找一步使异或变 0 的走法（p14 的构造法在此通用）。「拆分 → 各自求值 → 异或」这三步，是组合博弈论的通用算法。

定理为什么配得上「第一基本定理」这个称号？因为它把「博弈」这个看起来无限丰富的对象类，压缩到了一个极简单的标准模型上：一堆 Nim 石子。凡有限的公平博弈——无论走法表多奇特（皇后的走法、骨牌的摆放、竹节的切断）——在加法的世界里都只是一个非负整数。这一节的证明放在下一页（p19），那里可以看到 mex 的两个漂亮性质如何撑起整座桥。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.9 Sprague–Grundy 定理（证明）

★★★ 证明分两步：先建立「Grundy 值为零 = 𝒫 位置」这条桥（引理 1），再建立「和的值 = 值的异或」（引理 2）。两条桥合起来，定理就成立了。

引理 1。对任意公平博弈 G：𝒢(G) = 0 ⟺ G 是 𝒫 位置。证明：对 G 的结构做良基归纳（对「局面的大小」，此处即博弈树的高度）。① 若 G 是终局，无后继，𝒢(G) = mex ∅ = 0，且终局正是 𝒫 位置（无路可走者负）——两边一致。② 若 G 有后继：由 mex 的定义，𝒢(G) = 0 等价于 0 ∉ {𝒢(G′)}，即每个后继的值都非零；由归纳假设，这等价于「每个后继都不是 𝒫 位置」，即「所有走法都走向 𝒩 位置」——由逆推三律，这正是 𝒫 位置的刻画。◻

引理 2。对任意公平博弈 G、H：𝒢(G + H) = 𝒢(G) ⊕ 𝒢(H)。证明思路：记 x = 𝒢(G) ⊕ 𝒢(H)。需要验证两件事，才能用 mex 的定义下结论。

第一件：G + H 的任何后继的值都不等于 x。若走的是 G 这一边，走到 G′，新值是 𝒢(G′) ⊕ 𝒢(H)。若它等于 x = 𝒢(G) ⊕ 𝒢(H)，两边同时异或 𝒢(H) 就得到 𝒢(G′) = 𝒢(G)——但这不可能，因为按 mex 的定义，G 的后继值集合里不含 𝒢(G) 本身（𝒢(G) = mex{…} 意味着它不在集合里）。同理走 H 那边也一样。所以 x 确实「缺席」，是待选的 mex 候选人。

第二件：任何小于 x 的非负整数 y，都能被某个后继取到。把 y 与 x 比较：取 y 中最高位（设为第 k 位）——在这位上 y < x 意味着 y 那位是 0、x 那位是 1。而 x 的第 k 位是 1 意味着 𝒢(G) 与 𝒢(H) 中恰有一个第 k 位为 1；设是 𝒢(G)（另一情形对称）。令 z = y ⊕ 𝒢(H)，则 z 与 𝒢(G) 在第 k 位同为 1，且更高位相同（因为 y 与 x 在更高位一致），故 z < 𝒢(G) 在数值上成立……但要断言「z 是 G 的某个后继的值」，需要更细的论证（用 mex 的「小于者必出现」性质：若 k = mex S，则 0, 1, …, k−1 ∈ S）。严格的形式化留作习题（p31 挑战页给出完整版本）。

合起来。由引理 2 的两件事，mex{G+H 的后继值} = x，即 𝒢(G+H) = 𝒢(G) ⊕ 𝒢(H)。◻ 一般情形（n 个分量）由两两相加与异或的结合律归纳得到。特别注意这两个引理都没有用到 Nim 的任何特殊性——所以定理对一切公平博弈成立，这才有资格叫「第一基本定理」。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.10 应用：Green Hackenbush 与 Kayles

★★★ Sprague–Grundy 定理的威力在于：凡是能从局部拆开的博弈，都只需算局部的值。第一个漂亮的例子是竹节游戏（Green Hackenbush，由 Conway 命名并推广）。

规则。画一些绿色的线段（「竹枝」），每根线段的下端连在一个固定的「地面」上或连在别的线段上，形成一个连通的树状结构。两位玩家轮流切断一根绿线；被切断的线连同它上面连着的所有部分全部消失（掉到地上）。谁无法行动（没有绿线可切）谁输。

它是公平的（双方都能切任何一根线），有限（每步至少减少一根线），无平局——因此 Sprague–Grundy 定理适用，每个局面都有一个 Grundy 值。问题变成：怎么算？

单根「竹竿」（一条直线，n 节）的值是 n。用归纳：设 n 节竿的值为 v_n。切最下面一节，整竿消失（得 0 节的局面，值 0）；切第 k 节（从下往上数，k = 1, …, n），剩下的是下面 k − 1 节——因为切点以上全部落地。所以后继值集合是 {v₀, v₁, …, v_n−1}，mex 给出 v_n = n。一根 n 节的竹竿 = 一堆 n 颗石子的 Nim。

树状结构要用「冒号原理」（colon principle）：把挂在某个节点上的若干枝理解为一组并联的博弈——它们都依赖同一个「根」节点。可以证明：若某节点挂着的所有枝的 Grundy 值为 x₁, …, x_r，则这个节点连同它的枝整体等价于「把这些值按某种规则合并」的单枝（精确形式：合起来等价于一个值为「把各枝化为二进制后逐位做某种运算」的枝，对「并联」形（冒号）由 x₁ ⊕ x₂ ⊕ ⋯ 给出）。不必记住完整细节，记住方法论即可：把树拆成枝、把枝化成竿、把竿当成 Nim 堆。

第二个应用：Kayles（保龄球游戏）。一排 n 个瓶子，每人滚一次球，可击倒一个或相邻两个瓶子；击倒后那一段被断开，两侧成为两个独立的游戏。设 g(n) 为一排 n 个瓶子的值，则

g(n) = mex{ g(i) ⊕ g(n−1−i), g(j) ⊕ g(n−2−j) : 0 ≤ i, j }

（第一项对应「击倒一个」，把剩下分成左右两段；第二项对应「击倒两个」。）算出的数列（n = 0,1,2,…）是 0,1,2,3,1,4,3,2,1,4,2,6,4,1,2,7,…，它最终是周期的——这是组合博弈中的常见现象（证明周期性的方法叫「Guy–Smith 定理」，超出本册）。Kayles 展示了「拆分 + 递推 + mex」这套算法的典型用法。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

Hackenbush解谜专区红蓝树枝博弈，剪出胜负数philomath.cn/hackenbush/凯尔斯球馆工坊合集一排瓶子，Grundy 值算一遍philomath.cn/kayles/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.11 博弈的等价类构成交换群

★★★ Sprague–Grundy 定理有一个几乎自动的推论：公平博弈的等价类构成一个交换群。这是本章「群结构」标题的兑现处。

先把「等价」说清楚。定义 G ≡ H（读作「G 与 H 等价」）当且仅当「G + H 是 𝒫 位置」——直觉是「两局一起下，后手必胜，谁也占不到便宜」。由引理 2 立得：G ≡ H ⟺ 𝒢(G) = 𝒢(H)。于是等价类与「非负整数」（即 Grundy 值）一一对应。这些值在组合博弈论里有个专名：nimber。

三条群公理逐条验证。① 单位元：值 0 的类。凡 𝒢(G) = 0 的游戏（𝒫 位置）都等价于「空游戏」，即「什么都没有」，因为把它们加进任何博弈，只是把局面交给对手而改变不了胜负（想想「加一局必败的游戏」对全局的影响）。② 逆元：每个元素都是自己的逆元！因为 𝒢(G) ⊕ 𝒢(G) = 0，即 G + G ≡ 0——两个一模一样的博弈并排，后手必胜（镜像策略，p24）。③ 结合律与交换律：继承自「和」的定义与异或的代数性质（加法的顺序、结合方式不影响结果）。

由此得到一幅干净的图像。把每个公平博弈送到它的 Grundy 值，得到映射 𝒢：博弈（模等价）→ 非负整数（在异或下）。这是一个群同构——而且是「无穷维 ℤ₂ 向量空间」的语言：每个值都可以写成二进制串，串的每一位是一个「独立的方向」，异或就是逐位相加，平局就是零串。于是：

一切有限公平博弈 ≅ ⨁_i≥0 ℤ₂　（按二进制位分解）

这个结论有多强？它说：组合博弈论（公平、有限、无平局这一类）的分类问题被彻底解决了——每个博弈恰好属于一个等价类，类被一个非负整数标记，两个博弈的组合由加减（异或）给出。第一章的「群结构」标题至此兑现。当然，这只是「公平有限」这一狭小世界的胜利：一旦允许非公平（Left/Right 走法不同），等价类就不再由单个整数刻画，而是需要第二章的超现实数；一旦允许无限局，胜负判据又会反过来追问公理（第五章）。结构的边界，正是后续章节的起点。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.12 Chomp 与策略偷取

★★ 并非所有公平博弈都能立刻算出 Grundy 值；有些博弈的完整分析至今仍是难题。Chomp 就是最著名的例子。

规则。一块 m × n 的巧克力（格子），两人轮流选一格「吃」掉——同时被吃掉的还有这一格右上方（含正上方与正右方）的所有格子（也就是保持「左上角的阶梯形」的矩形区域）。左下角那一格是毒药：谁被迫吃掉它谁输（等价地：谁吃掉最后一格毒药谁输）。

局面天然是一个「阶梯形状」（每行剩下的长度从下到上非增），所以局面不多也不少；即便如此，除了 1 × n（答案是先手取到只剩毒药）与少数小情形之外，没有已知的胜负判据——不知道 P 位置长什么样，不知道必胜走法怎么找。

但先手必胜是可以证明的。用一个漂亮的「不构造证明」：

策略偷取（strategy stealing）。假设（反证）后手有必胜策略 S。先手的第一步就吃左上角那一格——由于它右上方没有任何格子，这一手只吃掉一格，得到一个「除去左上角」的阶梯形局面。现在，后手必须走一步；无论他走什么，先手都可以照搬 S（把 S 当作自己的策略）。于是先手「偷」了后手的策略——但先手还有额外的一格已经吃掉了，局面只会对先手更有利（多吃不会被惩罚，因为目标是吃光、吃的越多越接近胜利）。矛盾。所以后手不可能有必胜策略，先手必胜。◻

这个证明的形状：它给出了「先手有必胜策略」的存在性，却完全没有给出这个策略是什么。这是组合博弈论中一类特殊的证明——存在性而不构造（non-constructive）。在 Nim 那里我们能算出一个必胜走法（异或），在 Chomp 这里我们只知道「有」，不知道「哪一个」。这类现象与逻辑中的「非构造性存在」是同一血脉：知道某物存在，却无法指出它。（第五章的「决定性 vs 选择公理」会把这个话题推到极致。）

策略偷取的适用条件（值得记住）。① 游戏是单调的：多吃/多走不会变差；② 存在一个「白吃一步」的开局走法（通常是最小的那一手）；③ 对手的策略可以被照搬。凡是满足这三条的博弈，先手必胜都不需要看棋盘——一页纸就证明完。（有趣的是：策略偷取本身来自 Hex 游戏（p？第三章），Nash 在一九四八年的一篇笔记里用它证明了 Hex 的先手必胜。）

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

毒巧克力 · Chomp工坊合集策略偷取：先手必胜，但怎么走？philomath.cn/chomp/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.13 Wythoff 游戏与黄金比

★★★ 现在换一个「规则稍强」的取子游戏。它会把一个让人意想不到的常数请进棋盘：黄金比。

Wythoff 游戏（1907）。两堆石子 (a, b)，两人轮流行动，每一步可以：① 从任一单堆取走任意正数颗（Nim 的走法）；或者 ② 从两堆各取走相同数目的颗数（+k, +k 型的对角线走法）。取走最后一颗者胜。这就好比把 Nim 与「对角线移动」合在一个棋盘上：在平面上的一枚棋子，可以向左、向下、或向左下（对角）移动任意步，到达 (0,0) 者胜。

P 位置长什么样？用逆推可以手算出前几个：(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)…（按 a ≤ b 排列，交换亦同）。数列 a_n = 0, 1, 3, 4, 6, 8, 9, 11, … 与 b_n = 0, 2, 5, 7, 10, 13, 15, 18, …。

定理（Wythoff，1907）。设 φ = (1 + √5)/2 ≈ 1.618 为黄金比，则 (a, b)（含顺序）是 𝒫 位置当且仅当它形如

(a, b) = (⌊nφ⌋, ⌊nφ²⌋)　或　(⌊nφ²⌋, ⌊nφ⌋)，n = 0, 1, 2, …

为什么是黄金比？关键在一条「互补性」：𝒫 位置集合必须满足 ①（任意两个 𝒫 位置之间不能互相到达——否则前者就不是 𝒫）与 ②（任何非 𝒫 位置都能一步到达某个 𝒫 位置）。这两条逼迫 {a_n} 与 {b_n} 成为两个互补的（即不交且并起来恰好是全体正整数）递增数列，且 b_n − a_n = n。Beatty 定理（Rayleigh–Beatty）指出：两个形如 ⌊nα⌋、⌊nβ⌋ 的数列互补，当且仅当 1/α + 1/β = 1；结合 b_n = a_n + n 可解出 α = φ。黄金比不是被设计师放进来的，它是「互补性」这条要求的唯一解。

Wythoff 游戏与第一章的理论关系。它不是「若干独立分量的和」（走法②把两堆绑在一起），所以不能直接用「各堆异或」。但它仍然是公平、有限、无平局的博弈，因而依然有 Grundy 值（不过是两堆的函数），依然服从 Sprague–Grundy 定理的框架——只是它的 𝒫 位置有了一个漂亮的闭式描述。它提醒我们：定理给出的是「存在一个坐标」，而算不算得出坐标，是另一回事。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

威索夫工坊合集P 位置与黄金比的秘密philomath.cn/wythoff/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy1.14 对称策略与配对策略

★ 在引入 Grundy 值这套机器之前，人类对付博弈靠的是两种直觉：对称与配对。它们不但仍然有效，而且是理解本章定理的最佳入口。

对称策略。若局面由两块完全相同的部分组成（例如两堆石子相等、棋盘沿中轴镜像对称），则后手必胜：无论先手在其中一块上做什么，后手就在另一块的「镜像位置」做同样的事。关键的两点：① 镜像走法总是合法的（因为两块局面相同，先手能做后手也能做）；② 后手永远不会先走到「无路可走」（每次轮到后手，先手刚动过，必有可镜像之处）。于是后手走完最后一步，先手面对空局判负。这就是「G + G 是 𝒫 位置」，也就是 p21 里「每个元素是自己的逆元」的游戏论含义。

配对策略。更一般地，我们不需要整个局面镜像对称，只需要能把「可动的对象」两两配对，使得：先手动掉某个对象后，后手总能在它的「伙伴」上找到一步相抵的走法。例如「一排 2n 枚硬币，每次可翻一枚或相邻两枚」这类游戏，把硬币两两配对（第 1、2 枚一对，第 3、4 枚一对…），后手总能用「伙伴」回应。配对策略的证明总比对称策略麻烦一点：必须验证「先手的每一步都不会破坏配对的可续性」——这一步是具体问题具体分析的。

与本章理论的联系。① 对称策略是「G + G ≡ 0」的直接演示；② Nim 中「两堆相等是 𝒫 位置」正是对称策略的特例；③ Wythoff 游戏的判据可以理解为「在斜对角线上寻找某种互补结构」；④ Chomp 的策略偷取（p22）本质上是一种「不对称的偷取」——它先手多做一手（吃掉左上角），把「对后手有利的对称」偷过来。⑤ 更深的联系：Erdős 与 Selfridge 的「策略偷取」、Hales–Jewett 与 Hex 的无平局定理（第三章）都依赖这一直觉。

一个反例提醒。不是所有看起来对称的局面都有对称策略。若对称的两部分之间存在「交叉走法」能同时影响两边（例如 Wythoff 的对角走法），镜像就不再可行——这正是 Wythoff 不能简单用对称策略解决的原因，也是它需要黄金比的原因。「看起来对称」与「在走法下真的对称」是两件事：后者要求对称性被整个走法系统保持。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

点格棋工坊合集配对策略的经典战场philomath.cn/dots/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy误读：把「统计出的规律」当成判据

★ 本章最想打破的一种思维习惯是：把「试出来的规律」当成判据。这在游戏研究里极其常见——有人试算了几十个 Nim 局面，发现「异或为 0 的似乎都输」，就宣称找到了窍门；有人在棋盘上找出一堆「必胜模式」，就写成攻略。这些做法在数学上的问题是：它们只是猜想，不是定理。

为什么统计归纳在博弈里格外危险？因为局面空间通常指数级增长：3 堆各 30 颗就有三万个局面，5 堆各 100 颗就有一百亿个。「试了前五十个都对」在数学上等于什么都没说——反例可能恰好藏在没试的那一格。历史上确有游戏被误判：许多「看起来有必胜策略」的局面在更大盘面上崩掉，其中有些（如 Chomp 的完整判据）至今无人解决。

定理的正确形态是三件事。① 全称陈述：对所有局面成立（「任意 n 堆，异或为 0 ⟺ 必败」）；② 证明：给出逻辑链条，使反例在原则上不可能存在；③ 可操作：给出算法，能在有限时间内判定给定局面（最好还能给出必胜走法）。Bouton 定理三件事全都做到了：陈述是全称的，证明在 p14 给出，算法是 O(n) 的异或扫描。

另一个常见误读：把「存在必胜策略」误当成「知道必胜策略」。Chomp 是一个现成的例子（p22）：我们证明了先手必胜，却不知道必胜走法是什么，对一般 m × n 至今无解。「证明存在」与「构造出来」是两件不同的事——数学中这类「非构造性存在」随处可见（第五章会看到它在公理层面的极端形态）。本册要培养的判断力是：分清「试出来的」与「证明了的」，也分清「存在」与「构造」。本章的真跑实验（p36）刻意把两件事并置：一边是蛮力逆推（笨但可靠，用它检查判据），一边是公式（快但需要证明）——两者对拍一致，才算真的相信了定理。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy例题 1：Nim 的手算与必胜走法

★★ 例题 1：Nim 的手算与必胜走法。下面三小题依次练习「判定」与「构造」两件事。

例 1-1（判定）。局面 (3, 4, 5)，轮到先走，能赢吗？

解。算异或：3 = 011₍₂₎、4 = 100₍₂₎、5 = 101₍₂₎。逐位：第 0 位 1⊕0⊕1 = 0，第 1 位 1⊕0⊕0 = 1，第 2 位 0⊕1⊕1 = 0。故 3⊕4⊕5 = 010₍₂₎ = 2 ≠ 0，先手必胜。

例 1-2（构造必胜走法）。承上，给出一步必胜走法。

解。先算 X = 2，最高位是第 1 位。在第 1 位为 1 的堆有：3 = 011（第 1 位 1）、5 = 101（第 1 位 0，不算）——等等，5 = 101 的第 1 位是 0，第 0 位是 1；4 = 100 第 1 位是 0。所以只有 3 在第 1 位为 1。把它改成 3 ⊕ 2 = 1，得到局面 (1, 4, 5)。验证：1⊕4⊕5 = 0 ✓，且 1 < 3 合法。必胜走法：把第一堆从 3 取成 1。（这个局面恰好只有这一步回零走法——实验页的蛮力枚举证实了这一点。）

例 1-3（多重回零走法）。局面 (7, 5, 2)，求所有必胜走法。

解。7⊕5⊕2 = 111⊕101⊕010 = 000……算一下：7⊕5 = 2，2⊕2 = 0。异或为 0，这是必败局面——没有必胜走法（任何一步都会把非零局面交给对手）。这说明「先手必胜」不是普遍事实：判据必须每次都算。

例 1-4（把多堆当一个整体算）。局面 (1, 2, 3, 4, 5)，判定并给出走法。

解。1⊕2 = 3，3⊕3 = 0，0⊕4 = 4，4⊕5 = 1。故 X = 1（最高位第 0 位），先手必胜。第 0 位为 1 的堆：1、3、5。逐一试算：1⊕1 = 0（把 1 取成 0，去掉整堆）→ 局面 (2,3,4,5)，异或 2⊕3⊕4⊕5 = 0 ✓。必胜走法之一：取光第一堆。另外 3⊕1 = 2 < 3（把 3 取成 2）与 5⊕1 = 4 < 5（把 5 取成 4）也都是必胜走法——多重选择时，取「改动最大」的那一堆通常更利落，但数学上任何一步回零走法都同样必胜。

小结（手算的四步）。① 把每堆写成二进制（够用位数即可，挑最长的那堆定宽度）；② 逐位异或，得 X；③ X = 0 则必败（此时应当把局面尽量往「难缠」里拖，因为对手若也懂判据就输，但万一对手失误……不，数学上输）；④ X ≠ 0 则取 X 的最高位、在该位为 1 的堆中试 a_i → a_i ⊕ X，取到比原值小的那个即得回零走法。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy例题 2：算 Grundy 值（竹节与 Kayles）

★★★ 例题 2：算 Grundy 值（竹节与 Kayles）。这两个例子演示「拆分 + 递推 + mex」的完整流程。

例 2-1（单竿）。证明：一根 n 节竹竿的 Grundy 值等于 n。

解。对 n 归纳。切第 k 节（从下数，k = 1, …, n），剩下的恰好是下面 k − 1 节（上面全落地）。故后继值集合 S = {v₀, …, v_n−1}。由归纳假设 S = {0, 1, …, n − 1}，于是 v_n = mex S = n。◻（注意这个证明与 p17 的「一堆 a 颗石子）」是同一个论证——竹竿与 Nim 堆在数学上是同一个游戏。）

例 2-2（树状竹）。一根 3 节的主竿，在第二节处向上斜生一枝 2 节，求这个局面的 Grundy 值（只给思路）。

解。用「冒号原理」：挂在同一节点上的枝，可以被「合并」为一枝，其值由并联规则给出（对绿竹的冒号形，两个子枝的值 x, y 合起来等价于值为 x ⊕ y 的枝）。于是整个局面等价于：主竿 3 节 + 枝 2 节——把它们各当成 Nim 堆：3 ⊕ 2 = 1。局面值为 1，非零，先手（轮到的玩家）必胜；具体走法是把「值 1」消掉：在值为 3 的主竿上切到 2（3 ⊕ 1 = 2）。

例 2-3（Kayles 的递推）。用递推式算 g(0), …, g(6)。

解。递推：g(n) = mex{g(i) ⊕ g(n−1−i) : 0 ≤ i < n} ∪ {g(i) ⊕ g(n−2−i) : 0 ≤ i < n−1}。逐项：

g(0) = 0（无瓶可击）；g(1) = mex{g(0)⊕g(0)} = mex{0} = 1；

g(2) = mex{g(0)⊕g(1), g(1)⊕g(0), g(0)⊕g(0)} = mex{1, 1, 0} = 2；

g(3) = mex{1⊕2, 0⊕0, 2⊕1, 0⊕1, 1⊕0} = mex{3, 0, 3, 1, 1} = 2……

等等——实验页给出的是 g(3) = 3。让我重算：n = 3。击倒一个瓶子：剩 (i, 2−i)，i = 0,1,2 → 值 g(0)⊕g(2) = 0⊕2 = 2、g(1)⊕g(1) = 1⊕1 = 0、g(2)⊕g(0) = 2。击倒两个（相邻）：剩 (i, 1−i)，i = 0,1 → g(0)⊕g(1) = 1、g(1)⊕g(0) = 1。集合 {2, 0, 1}，mex = 3 ✓。与真跑一致。继续可算 g(4) = 1、g(5) = 4、g(6) = 3。完整数列见实验页：0, 1, 2, 3, 1, 4, 3, 2, 1, 4, 2, 6, 4, …

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy例题 3：Wythoff 判据与对称局面

★★★ 例题 3：Wythoff 判据与对称局面的应用。

例 3-1（判定）。Wythoff 游戏中局面 (4, 11)，谁必胜？

解。用公式：看 (a, b) 是否等于 (⌊nφ⌋, ⌊nφ²⌋)。注意 ⌊nφ²⌋ = ⌊nφ⌋ + n（因为 φ² = φ + 1），故判据可写成「b − a = n 且 a = ⌊nφ⌋」。这里 b − a = 7，故需 n = 7，而 ⌊7φ⌋ = ⌊11.326⌋ = 11 ≠ 4——不是 𝒫 位置，先手（轮到者）必胜。

例 3-2（找走法）。承上，给出一步必胜走法。

解。要从 (4, 11) 走到某个 𝒫 位置。列出附近的 𝒫 位置：(3,5)、(4,7)、(6,10)、(8,13)。检查三种走法：① 删一堆（把某堆取空）：(0, 11) 不是 𝒫（只有 (0,0) 是）；② 单堆减少：把 11 减到 5 得 (4,5) 不是；减到 7 得 (4,7) ✓ —— 把第二堆从 11 取成 7 即可（取走 4 颗）；③ 两堆各减同数：(4,11) → (3,10)? 不是 𝒫；→ (2,9)? 不是。（一般地，(4,11) 只有唯一一条通往 𝒫 的路——𝒫 位置的定义保证「每个非 𝒫 位置能到某个 𝒫，且只到唯一一个」。）

例 3-3（对称局面的判定）。一副 2n 张的牌，两人轮流拿牌，每次可拿 1 或 2 张，拿到最后一张者胜。谁必胜？

解。把牌分成 n 组、每组 2 张。配对策略：后手总在对手拿走一张时拿走同组另一张（若对手拿两张，那两张恰好可以同组——后手拿下一组的两张？不，对手拿了同一组的两张，后手就取另一组的两张？需仔细：配对法在这里更简单的形式是「每次取 3 的补数」——对手取 k 张，后手取 3 − k 张。因为每轮共取 3 张，只要 2n 是 3 的倍数，后手必胜；否则先手先取余数（2n mod 3 张）然后照此办理，先手必胜）。经验：凡「取子数目有上限」的游戏，先找「3 的补数」这类周期配对；它是配对策略最简的一次应用。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy习题 1：基础（异或、P/N、Grundy）

★★ 习题 1：基础（异或、P/N、Grundy）。

1. 把下列数写成二进制并计算异或：6 ⊕ 9、12 ⊕ 10、15 ⊕ 7 ⊕ 8、1 ⊕ 2 ⊕ 4 ⊕ 8。提示：先把每个数写成不超过所需位数的二进制，再逐位比较「1 的个数是奇还是偶」。

2. 判定下列 Nim 局面的胜负（轮到者视角），并给出一步必胜走法（若必胜）：(4, 4)、(1, 2)、(2, 3, 4)、(5, 6, 7)、(1, 1, 1)、(10, 10, 3)。

3. 证明：Nim 中「两堆相等」是 𝒫 位置。不依赖 Bouton 定理的对称策略直接证明（这是 p24 的手法）。

4. 证明：若 Nim 局面的异或为 0，则任何一步走法之后的异或都非 0。（这是 Bouton 定理的「方向一」，得细致一点。）

5. 计算 mex{2, 3, 5}、mex{0, 1, 2, 4, 5}、mex{1, 3, 5, 7}、mex{3}、mex ∅。

6. 从一堆 n 颗石子中每次可取 1、2 或 3 颗，取到最后者胜。求这个游戏的 Grundy 值 𝒢(n) 的公式，并指出 𝒫 位置的规律。递推算前几项，找周期（想想 4）。

7. 承上，若每次可取 1 至 k 颗，𝒫 位置是什么？与模 k + 1 有关。

8. 判定两堆 Nim 的 𝒫 位置集合，并说明它为何构成一条对角线。若把规则改为「两堆各取相同数（Wythoff）」或「两堆各取任意数但总数受限」，𝒫 位置会如何变形？

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy习题 2：进阶（拆分与构造）

★★★ 习题 2：进阶（Sprague–Grundy、拆分、构造）。

9. 用 Sprague–Grundy 定理计算：两堆各 3 颗石子的 Nim 与一个「3 节竹竿 + 5 节竹竿」的竹节游戏并行（即四个分量同时进行：3、3、3、5），谁必胜？给出一组必胜走法。

10. 证明引理：「若 k = mex S，则 0, 1, …, k − 1 ∈ S 而 k ∉ S」。然后用它补全 p19 引理 2 的第二件事（「任何小于 x 的数都能被某个后继取到」）中略去的那一步论证。

11. 「减法游戏」：给定集合 S = {1, 3, 4}，从一堆 n 颗中每次取 S 中的一个数目，取到最后者胜。求 𝒢(0..14)，并指出是否为周期数列。

12. Mock Turtles / Ruler 游戏：从一堆 n 颗中每次取「任意 2 的幂次」颗（1, 2, 4, 8, …），取到最后者胜。猜并用递推验证 𝒢(n) 的公式。试 n = 0…10，看它是否等于 n 模 3 的某种函数。

13. Chomp 的 1×n 情形（一排 n 格的巧克力，毒药在最左）：证明先手必胜（n ≥ 2）并给出必胜走法。

14. 用「策略偷取」证明：若一个博弈满足 ① 单调（多吃不亏）、② 存在「白吃一步」的最小开局走法，则先手必胜。指出 Chomp、Hex（第三章）各如何满足这两条。

15. Wythoff 游戏：证明两个 𝒫 位置之间不能互相到达（即「𝒫 位置集合是独立的」）。对「两堆各减同数」用差 b − a 不变，对「单堆减少」用差改变。

16. 用 Beatty 定理（⌊nα⌋ 与 ⌊nβ⌋ 互补 ⟺ 1/α + 1/β = 1）推导 Wythoff 判据中 α = φ。（提示：结合 b_n − a_n = n。）

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy第一章地图：概念怎么连成网

本章的概念网络可以读成三条链（见下图）。

链一（判定链）。游戏 → 有向图 → 𝒫/𝒩 标签 → 逆推三律 → 需要闭式判据 → Bouton 定理（异或为 0）。这条链回答「谁赢」。

链二（估值链）。局面 → Grundy 值（mex 递归）→ 游戏的和 → Sprague–Grundy 定理（和的值 = 值的异或）。这条链回答「怎么把一个游戏折算成数」。

链三（结构链）。值 → 等价类 → nimber → 交换群（ℤ₂ 无穷直和）→ 分类完成。这条链回答「博弈的世界长什么样」。

三个动作的对应关系。① 画图（链一）：把局面与走法画成有向图，是一切分析的起点；② 找不变量（链一、二的交汇）：异或、Grundy 值都是「在走法下按规则变化」的量，胜负由它是否为零决定；③ 化标准形（链三）：把一个游戏换成它的 Grundy 值，就把它送进了加法群——此后「并行」变成「相加」。

本章边界（重要）。本章的全部结论都建立在三个假设上：公平（双方走法相同）、有限（局数有界）、无平局。一旦破坏其中任意一条，理论就要升级：非公平 → 需要方向（Left/Right）与超现实数（第二章）；含随机 → 需要期望与混合策略（第四章）；无限 → 需要公理（第五章）。把边界记清楚，比记结论更重要。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy小结（一）：局面即结构

★★ 小结（一）：局面即结构。

正面清单。① 公平组合博弈的三个特征：双方走法相同、有限、无平局（p12）；② 局面图：顶点是局面、边是合法走法，游戏 = 图上的行走；③ 𝒫/𝒩 位置：终局是 𝒫；能一步到 𝒫 的是 𝒩；所有走法都到 𝒩 的是 𝒫（逆推三律）；④ Nim 的规则与三个特点；⑤ Bouton 定理：异或为 0 ⟺ 必败，双向证明齐全；⑥ 异或的代数：ℤ₂ 上的无进位加法，线性结构；⑦ 游戏的和：G + H 每次只动一个分量，Nim 是单堆游戏之和；⑧ mex 与 Grundy 值的递归定义；⑨ Sprague–Grundy 定理：一切有限公平博弈 ≅ 一堆 Nim；⑩ 等价类构成交换群（nimber）。

易错清单（每条都来自真实的手算事故）。① 把「异或为 0」记成「石子数的和为零」——完全无关，异或是按位运算；② 把「必败位置」理解成「一定输给任何人」——它只说明「若对手懂判据，必输」，对手失误时当然还能赢；③ 忘了「取最后一颗者胜」意味着终局是 𝒫——若改为「取最后者输（misère play）」，Bouton 判据会变（只多一条例外规则，见习题）；④ 把 mex 当成 max——mex 是「最小的缺席者」，mex{0,1,2} = 3 而不是 2；⑤ 用「堆的大小」直觉判断——数字大小与胜负无关（(1,2,3) 必败而 (3,4,5) 必胜）；⑥ 把「两个游戏和的值」算成「值的和」——是异或，不是加；⑦ 在「非公平」或「含随机」的游戏上误用本章结论——边界之外要换工具。

一句话的总结。本章把「谁会赢」这个问题从「看棋盘」搬到了「算不变量」——局面是结构，胜负是结构上的一个函数（值是否为零）。这是组合博弈论的第一课，也是后续所有内容的模板。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy小结（二）：把局面化成数

★★★ 小结（二）：把局面化成数。

算法清单（遇到任何有限公平博弈时的标准流程）。① 拆：把整体分成互不干扰的分量（若不能拆，跳过此步，直接对整体求值）；② 求值：对每个分量递归算 Grundy 值（mex 后继值集合）；③ 合并：把所有值异或起来；④ 判决：异或为 0 则轮到者必败，非 0 则必胜；⑤ 构造：若必胜，找一步使异或变 0 的走法（在某分量上按「最高位」规则改动）。

三个本类游戏的「值工具箱」。① 取子型（一堆 n 颗，可取的数目属于集合 S）：𝒢(n) = mex{𝒢(n − s) : s ∈ S, s ≤ n}，通常最终周期化；② 切分型（Kayles、Dawson's Kayles、多米诺摆放）：枚举切点，左右两段的值异或后取 mex；③ 树型（Green Hackenbush）：单竿值 = 节数，树用冒号原理递归折平。

「化成数」这件事的意义，怎么强调都不过分。它有两个层次。第一层是技术：算一个数比记一张胜负表容易得多，运算（异或）也比「模拟对局」快得多。第二层是结构：一旦局面被化成数，两个游戏「同时进行」就变成了两个数「相加」，而「谁赢」变成了「和是否为零」——博弈论被翻译成了算术。这正是本册主线的第一个范式：换一种描述，让困难变成简单。

下一章的动机。本章的「值」是非负整数，只能表达「公平博弈」这一狭小世界。若允许左右双方走法不同（例如国际象棋里白方与黑方走法不同、围棋里的先手优势），等价类不再是整数，而需要一个更丰富的数值系统——在这个系统里，「小于零」「等于零」「大于零」分别对应「右方必胜」「先手必败」「左方必胜」，而每个游戏都能被赋予一个「数」。Conway 造出的正是这个系统：超现实数。第二章将走进它——并证明本章的 Grundy 值只是它的一小片影子。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy思想卡：值的思想

延伸思考（三问）。① 如果给每个局面分配的不是数而是一个向量或矩阵，「胜负 = 值为零」这个框架还成立吗？（提示：想一想「和」的运算是否还有交换、结合、可逆三性。）② 若游戏允许平局，𝒫/𝒩 二分就不够了——需要第三种标签（第三章的 Hex 无平局定理正是一条「消灭平局」的定理）。③ 若游戏允许无限对局，「值」还定义得出来吗？（第五章会看到，答案与公理的选择有关。）

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy挑战：Sprague–Grundy 定理的完整证明

★★★★ 挑战 1：完整证明 Sprague–Grundy 定理。p19 的证明在引理 2 的第二件事上「略过了一步」——现在把它补完。按下面的规范写作。

第一步（良定义）。对游戏的博弈树高度做良基归纳：终局高度 0，其余 h(G) = 1 + max{h(G′)}。证明 𝒢(G) 只依赖 G 的后继的值集合，故归纳良定义。说明为什么「公平 + 有限 + 无平局」保证高度有限。

第二步（引理 1 的双向）。① 若 𝒢(G) = 0：由 mex 定义，0 ∉ {𝒢(G′)}，故所有后继值非零；由归纳假设，后继都不是 𝒫（都是 𝒩），由逆推三律 G 是 𝒫。② 若 𝒢(G) ≠ 0：设 k = 𝒢(G)，由 mex 的第二条性质 0 ∈ {𝒢(G′)}（因为 0 < k 必出现），即存在后继值 0，由归纳假设该后继是 𝒫，故 G 是 𝒩。◻

第三步（引理 2，含被省略的那一步）。记 x = 𝒢(G) ⊕ 𝒢(H)。要证 mex{𝒢(G+H 的后继)} = x，需两件事。

(a) x 不在后继值集合中。p19 已证（用「𝒢(G) ∉ {𝒢(G′)}」与异或可逆）。

(b) 每个 0 ≤ y < x 都在后继值集合中。取 y，令 k 为 x ⊕ y 的最高位；则 x 与 y 在第 k 位不同。分两种情形（这正是被省略的那一步）：

情形 1：𝒢(G) 在第 k 位为 1。令 g′ = y ⊕ 𝒢(H)。可验证 g′ < 𝒢(G)（比较最高不同位）。由 mex 性质 (ii)，g′ ∈ {𝒢(G′)}，即存在 G′ 使 𝒢(G′) = g′。于是在 G + H 中走 G → G′，得到值 g′ ⊕ 𝒢(H) = y ✓。

情形 2：𝒢(H) 在第 k 位为 1。对称地取 H′ 使 𝒢(H′) = y ⊕ 𝒢(G)，在 H 上走一步即得值 y ✓。

由 (a)(b)，mex{…} = x，即 𝒢(G+H) = x。◻

挑战 2（选做）：形式化策略偷取。精确定义「单调博弈」（每个局面的「资源集合」在走法下单调不减地减少，且多吃一步不会使任何走法失效），然后证明：单调 + 存在「最小白吃步」⟹ 先手必胜。指出 Chomp 的「吃左上角」为什么是白吃步，以及为什么 Hex（第三章）也满足（在那里「白吃」表现为多占一个对自己无害的格子）。

挑战 3（研究型）：misère Nim。把「取最后者胜」改成「取最后者输」（misère play），Bouton 判据如何修改？算几个小局面找出规律，再查阅文献（Bouton 1901 之后的经典结果），并写出完整判据与证明思路。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy实验：Grundy 值求解器真跑

★★ 实验：Grundy 值求解器真跑（对拍验证）。本节的所有数字都来自本地脚本 p36_lab.py（纯 Python 标准库），输出存于 qa/p36_out.txt，可自行复算。

实验一：Nim 的异或判据 vs 蛮力逆推。蛮力：把每个局面标记为「轮到者必胜/必败」，用备忘录化的逆推（枚举所有走法）。对拍范围：1–4 堆、每堆不超过 8 颗。

① Nim：异或判据 vs 蛮力逆推
  对拍局面数 = 710（1–4 堆，每堆 ≤ 8）
  判据不符数 = 0   全一致 ✓
  (3,4,5)：xor = 345 = 2  →  先手必胜？蛮力：True
  回零走法（把某堆 a 取到 a'）：[(3, 1, (1, 4, 5))]

两件事值得注意：① 710 个局面零例外——判据与蛮力逐条一致，这是对 Bouton 定理的独立检验；② (3,4,5) 的回零走法只有一个（把 3 改成 1），与 p26 手算一致——「必胜走法可能有多个，也可能只有一个」。

实验二：Wythoff 的黄金比判据 vs 蛮力。

② Wythoff：黄金比判据 vs 蛮力逆推
  对拍局面数 = 496（0 ≤ a ≤ b ≤ 30）
  判据不符数 = 0   全一致 ✓
  P 位置（前 10 个）= [(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20),(14,23)]
  (⌊nφ⌋,⌊nφ2⌋) 前 8 个 = [(0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18)]

可见「𝒫 位置 = (⌊nφ⌋, ⌊nφ²⌋)」在小范围内完全正确，且这些点互不相同、也不共线——这正是 p23 所说的「互补性」的数值影子。

实验三：Kayles 的 Grundy 数列。

③ Kayles 的 Grundy 数列（递推 mex）
  g(0..24) = [0,1,2,3,1,4,3,2,1,4,2,6,4,1,2,7,1,4,3,2,1,4,6,7,4]
  未出现的值（0–8 中）: [5, 8]
  前 24 项的最大值 = 7 ；取到的不同值 = [0,1,2,3,4,6,7]

数列 0,1,2,3,1,4,3,2,1,4,2,6,4,… 与教科书一致。它最终是周期的（周期 12，从 n = 71 起），前 24 项还看不出周期——这也是「不能靠前几项猜规律」的实例。

实验四：Chomp 小棋盘的蛮力 P/N。

④ Chomp 小棋盘的蛮力 P/N（m 行 n 列）
  行\列   1     2     3     4     5     6
   1   先手败  先手胜  先手胜  先手胜  先手胜  先手胜
   2   先手胜  先手胜  先手胜  先手胜  先手胜  先手胜
   3   先手胜  先手胜  先手胜  先手胜  先手胜  先手胜
   4   先手胜  先手胜  先手胜  先手胜  先手胜  先手胜
   5   先手胜  先手胜  先手胜  先手胜  先手胜  先手胜
   6   先手胜  先手胜  先手胜  先手胜  先手胜  先手胜
  除 1×1 外，全部 m,n ∈ [1,6] 的先手是否必胜？True

数值证据与策略偷取的证明一致：除 1×1（先手被迫吃毒药）之外，所有 m × n 的 Chomp 都是先手必胜——但仔细：表格里只写了「先手胜」，没有写「怎么胜」。这正是 p22 强调的：证明给出存在性，不给出构造。

四个实验的共同结论。① 判据（异或、黄金比）与蛮力逆推逐条一致，说明定理不是巧合；② Grundy 递推给出可见的数列，且数列的规律性（周期性）需要小心对待；③ 「存在必胜策略」与「知道必胜走法」是两件事（Chomp 是活证据）。本册所有实验页都遵循同一格式：可复算的脚本 + 可核对的输出 + 与理论的对拍。自己动手跑一遍——「跑过」与「读过」在数学上差别巨大。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

珍珠劫 · NIM工坊合集异或必胜密码，五级闯关philomath.cn/nim/凯尔斯球馆工坊合集一排瓶子，Grundy 值算一遍philomath.cn/kayles/威索夫工坊合集P 位置与黄金比的秘密philomath.cn/wythoff/毒巧克力 · Chomp工坊合集策略偷取：先手必胜，但怎么走？philomath.cn/chomp/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy格物札记：中算传统里的「取子」与「对弈」

本章讲的「取子游戏」，在中国古代有两支近亲：一支是算法化的「术」，一支是棋戏化的「势」。

先说「术」。《九章算术》的写法是「术曰：……」，每一条「术」都是一串可以照着做的动作：把某数写在某位、以某数乘之、以某数除之、以余数为答。这种「程序化」的写作与本章的游戏规则在结构上完全一致——规则给出一串允许的动作，玩家照着走即可。事实上很多中算题目本身就是游戏：把一堆物按规则分配、合并、取余，答案就是终局。「术」是中国数学最早的游戏说明书。

再说「势」。围棋与六博的传统孕育了另一套语汇：「先手」「后手」「势」「劫」「气」。《棋经十三篇》里「宁输数子，勿失一先」正是本章「先手优势」的直觉表达；而「势」相当于本章的局面值——棋手凭经验给局面估一个「价值」，判据则是「谁的价值占优」。棋手数千年用直觉做的事，本章把它变成了一个可计算的不变量。孙武「凡战者，以正合，以奇胜」同样可以读成策略分层：正兵是「保证不输的对称走法」（𝒫 位置思维），奇兵是「抓住对手失误的一击」（𝒩 位置思维）。

两支线索的差别值得琢磨。中算传统更早写出了算法（《九章》的「术」是真正的程序），却在「对所有局面都成立」的普遍性证明上投入较少；古希腊传统恰好相反——Euclid 的每个命题都要「对所有情形」成立，为此发明了公理与演绎。（这不是优劣，而是两种文化的数学取向。）本章的内容恰好是两者的合流：Nim 的判据既是一条「术」（O(n) 可执行的算法），又是一条定理（对一切局面成立的证明）。

一个具体的中算游戏：约瑟夫问题。「今有围兵，从某处数起，每数至 k 者出列，问何处可生」——这是中国古代算书与印度数学里反复出现的题目，本质是「报数淘汰」游戏。它的解法（递推 J(n) = (J(n−1) + k) mod n）正是本章「递推 + mex/取模」手法的东方版本——用递推把大局面化归为小局面，是两种传统共有的核心技巧。（这个游戏在第三章与第五章还会以不同面貌出现。）

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

巴什钱局工坊合集每次至多拿 m 枚的补数口诀philomath.cn/bash/石阶拾金工坊合集阶梯上的取子游戏philomath.cn/staircase/

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy速查：第一章概念与公式

★ 速查：第一章概念与公式。

一、记号。𝒫 位置（Previous player wins，轮到者必败）；𝒩 位置（Next player wins，轮到者必胜）；⊕ 异或；𝒢(G) Grundy 值；G + H 游戏的和；mex S 最小缺席非负整数；∗a 一堆 a 颗的取子游戏。

二、定义。① 公平组合博弈：双方走法相同、有限、无平局；② 局面图：顶点 = 局面、边 = 合法走法；③ 逆推三律：终局 𝒫；能到 𝒫 者为 𝒩；后继全 𝒩 者为 𝒫；④ 𝒢(G) = mex{𝒢(G′)}；⑤ G ≡ H ⟺ 𝒢(G) = 𝒢(H) ⟺ G+H 是 𝒫 位置。

三、核心定理。① Bouton 定理：Nim 中 a₁ ⊕ ⋯ ⊕ a_n = 0 ⟺ 𝒫 位置；② Sprague–Grundy 定理：𝒢(G₁ + ⋯ + G_n) = 𝒢(G₁) ⊕ ⋯ ⊕ 𝒢(G_n)；任何有限公平博弈 ≅ 一堆 Nim；③ Wythoff 判据：𝒫 位置 = (⌊nφ⌋, ⌊nφ²⌋)；④ 对称/配对策略：G + G 是 𝒫 位置；⑤ 策略偷取：单调 + 白吃步 ⟹ 先手必胜（存在性）。

四、算法。判定 O(n)：累异或；构造 O(n)：取 X 最高位 → 找该位为 1 的堆 → 改成 a_i ⊕ X；求值：递归 mex（或递推 + 找周期）。

五、常用恒等式。a ⊕ a = 0；a ⊕ b = c ⟹ a = b ⊕ c；𝒢(∗a) = a；mex{0,1,…m−1} = m；若 k = mex S 则 {0,…k−1} ⊆ S, k ∉ S。

六、典型数值（实验真跑）。Nim 对拍 710 局面零例外；Wythoff 对拍 496 局面零例外；Kayles g(0..24) = 0,1,2,3,1,4,3,2,1,4,2,6,4,1,2,7,1,4,3,2,1,4,6,7,4；Chomp 除 1×1 外全先手胜。

七、三个动作。画图（局面 → 有向图）· 找不变量（异或、Grundy 值）· 化标准形（局面 → 数 → 加法群）。

第一章 取子游戏与博弈的群结构：从 Nim 到 Sprague–Grundy第二章预告：数即游戏

★★ 第二章预告：数即游戏。

本章留下的最大悬念。我们把每个公平博弈折算成一个非负整数（Grundy 值），并证明了「和 = 异或」。但回头看这个框架的一个缺口：它只处理「公平」博弈——双方走法完全相同。一旦左右双方走法不同（围棋里先手优势、象棋里白黑走法不同、博弈论里的「零和矩阵博弈」），整数就不够用了：我们需要能表达「左方有利」与「右方有利」的量，而且这两个量必须能相加减、能比较大小。

Conway 的回答。他把「博弈」本身当成数：一个博弈写成 G = {L | R}，其中 L 是左方能走到的局面集合、R 是右方能走到的集合。若左方的每个选择都优于右方的每个选择（形式地说：L 中任何元素都不大于 R 中任何元素），则 {L | R} 是一个数；否则它是一个「非数的游戏」。从这个定义出发：

0 = { | }　1 = {0 | }　−1 = { | 0}　½ = {0 | 1}　2 = {1 | }　ω = {0,1,2,… | }

整数、二进分数、实数、无穷大与无穷小都从「生日」归纳中生长出来，这就是超现实数（surreal numbers）。

第二章要完成的四件事。① 构造：定义 {L | R}、生日、序与加法，证明「数类」构成一个全序域；② 嵌入：把实数嵌入超现实数，看清 ½、1/3、√2、π 各自是「第几天」被造出来的；③ 非数的游戏：∗ = {0 | 0}（先手必胜的中立局面）、↑ = {0 | ∗}，它们与任何数都「不可比」（fuzzy）——第一章的 Nim 值（nimber）正是这些非数游戏的化身，本章将把这条线索接回去；④ 合流：证明对公平博弈而言，「超现实数意义下的值和」与「Grundy 值的异或」说的是同一件事的两面。

带着三个问题进入第二章：① 为什么 {0 | 1} 一定是 ½，而不是「某个全新的数」？② 若 L 中有元素不小于 R 中元素（「左右打架」），{L | R} 是什么？③ 「所有数都是游戏」这句话，反过来对游戏成立吗——每个游戏都是一个数吗？（答案：不，∗ 就不是数。而这正是第二章最让人兴奋的地方。）

一个预告性的比喻。第一章我们学会了「把游戏算成数」；第二章我们要学「把数看成游戏」。视角翻转之后，算术本身变成了博弈论的一个特例——「1 + 1 = 2」将被读成「两个必胜的半步相叠，得到一个更大的必胜」。这不是比喻，而是一条定理。

第二章 数即游戏：Conway 的超现实数本章导引：从「公平」到「方向」

★ 第一章的胜利有一个隐藏前提：博弈必须是公平的——双方可走的走法完全相同。正因为公平，每个局面才能折算成一个非负整数（Grundy 值），而「两盘棋同时下」才变成「两个数异或」。现在把这条假设拿掉：若左方与右方的可走法不同（象棋里白黑走法不同、围棋里的先手优势、矩阵博弈里行与列不对称），整数就不够用了——我们需要一个能同时表达「左方有利」与「右方有利」、并且可以相加减、比大小的数值系统。

Conway 的答案大胆到近乎鲁莽：把「游戏」本身定义成数。一个博弈写成 G = {L | R}，L 是左方能走到的局面之集、R 是右方能走到的局面之集；两个博弈的「并行」定义成加法（每次只动一边）。从这一个记号出发，Conway 造出了 0 = { | }、1 = {0 | }、½ = {0 | 1}，进而造出全部整数、二进分数、实数、序数，甚至比实数还多——这就是超现实数（surreal numbers）。

本章的路线（见下图）。先用 p41–p43 立起三块砖：游戏的形式定义 {L | R}、序与等价的递归定义、加法与负元。接着用 p44 的「数的判据」（每个左元素都小于每个右元素）把「游戏」分成「数」与「非数游戏」两类，用 p45 的「生日」给构造排出时间轴，然后在 p46–p48 一天天把 0, ±1, ±2, ±½, ±¼, ±¾, ±3/2 造出来。p49–p51 证明这些数构成全序域（比较、加法群、乘法），p52–p53 把实数与超限数 ω、1/ω 嵌进来，最后 p54 遇见本章另一半主角——不是数的游戏 ∗ = {0 | 0} 与 ↑ = {0 | ∗}，它们正是第一章 nimber 的化身。

本章要交出的支票只有一张：「数」不再是被给予的神秘对象，而是从游戏规则里被造出来的东西；「1 + 1 = 2」将被读成「两个半步之胜相叠」。这不是比喻，而是一条可以证明的定理。

第二章 数即游戏：Conway 的超现实数2.1 游戏的形式定义：{L | R}

★★ 定义（游戏）。一个游戏 G 是一对集合 G = {L | R}，其中 L、R 中的每个元素本身也是一个游戏（分别称为 G 的左选项与右选项）。轮到左方行动时，他从 L 中挑一个作为新局面；轮到右方行动时，从 R 中挑一个。若轮到某人而对应的集合为空，他无路可走，判负——这就是「正常玩法」（normal play）。

两个直觉要点。① L 与 R 是「选择」，不是「后果」：它们记录「如果轮到左方，他能把局面变成哪些样子」。② 左右不必对称：L 与 R 可以完全不同，这正是第一章「公平博弈」（L 与 R 结构相同）之外的新天地。

从空集开始。最简的游戏是 { | }：左右都无可选项。谁轮到它谁就输——因此它天然扮演「零」的角色，记作 0。再往前一步：{0 | } 表示「左方能走到 0（把「轮到就输」的局面甩给右方），右方无路可走」——这是一个对左方有利的游戏，记作 1。对称地 { | 0} = −1。接受这个记号，p46 会严格证明它们确实是数。

为什么用「集合」而不是「单个局面」？因为一个局面下左方常有多条走法（例如象棋里十几种着法）。把这些着法统统收进一个集合，既保留全部信息，又让「一个游戏」保持为一个对象——这是 Conway 构造的关键设计：用集合的整体而不是逐个走法来刻画局面。有了它，p42 才敢把「比较」与「相加」也递归地定义在集合上。

第二章 数即游戏：Conway 的超现实数2.2 序与等价：G ≤ H 的含义

★★★ 定义了对象，下一步是定义比较。对游戏而言，「G ≤ H」的直觉是：在 G 里站在左方，不会比在 H 里更差。但这句话不能直接用（「更好」是什么？），于是 Conway 把比较递归地定义在选项上：

G ≤ H　⟺　不存在 G^L ≥ H　且　不存在 H^R ≤ G

读法。要判断 G ≤ H，只需排除两种「反例」：① G 的某个左选项已经 ≥ H（说明左方在 G 里有比 H 更好的选择，「G 不超过 H」就不可信）；② H 的某个右选项 ≤ G（右方在 H 里有比 G 更差的选择，同理）。两种反例都不存在，才记 G ≤ H。式中的 ≥、≤ 又用到定义本身——这是一个递归定义，其合法性由「选项的生日更小」保证（p45）。

由 ≤ 派生的三个概念。① 相等：G = H 当且仅当 G ≤ H 且 H ≤ G。注意这是游戏的相等，不是「长得一样」——{ | } 与 {−1 | 1} 形状不同却相等（都等于 0）。② 严格小于：G < H 当且仅当 G ≤ H 且 H ≰ G。③ 模糊：G ‖ H 当且仅当既不 G ≤ H，也不 H ≤ G——单凭「≤」一个关系就同时造出了「相等」「小于」和「不可比」三种情形。

一个立刻的例子。0 = { | }、1 = {0 | }。验证 0 ≤ 1：0 没有左选项（反例①不存在），1 没有右选项（反例②不存在）——故 0 ≤ 1 成立。再验证 1 ≤ 0：1 的左选项是 0，而 0 ≥ 0 成立，正好是反例——故 1 ≤ 0 不成立。于是 0 < 1，与直觉一致。整章的证明都要用这个「查反例」的动作。

第二章 数即游戏：Conway 的超现实数2.3 加法与负元

★★★ 定义（和）。两个游戏 G = {G^L | G^R}、H = {H^L | H^R} 的和为

G + H = { G^L + H, G + H^L | G^R + H, G + H^R }

它的现实含义是「两盘棋同时进行」：左方的每一步，要么在左盘上走（得到 G^L + H），要么在右盘上走（得到 G + H^L）；右方同理。这正是一章「游戏的和」（p16）的推广——只是现在左右走法可以不同。

定义（负元）。−G = { −G^R | −G^L }：把左右两个集合对调，再把每个选项取负。直观上这就是「把棋盘换个方向坐」：原来左方能做的，现在都归右方做。负元是把「左方优势」翻转成「右方优势」的开关。

两条基本律（都可对生日归纳证明）。① 交换律：G + H = H + G——因为定义中「G^L + H」与「H + G^L」在归纳假设下相等，逐个选项配对即可。② 结合律：(G + H) + K = G + (H + K)——同理逐项展开、配对。证明的模式是统一的：把要证的等式两边都展开成 {… | …}，再对选项逐个用归纳假设，最后比较选项集合是否相等。

一个方便的直觉。先把每个游戏想成「一张有向图上的棋子」；加法就是把若干棋子放在各自的图上，每次只推一个；负元则是「镜像」。p46 会看到 1 + (−1) = 0，即「左方必胜 + 右方必胜 = 后手必胜」——和为零。「和」这个运算是全章的发动机：序、域、实数全都建立在它上面。

第二章 数即游戏：Conway 的超现实数2.4 什么是「数」：所有左元素都小于右元素

★★★ 现在到了本章的分水岭——什么样的 {L | R} 才是数？

定义（数）。游戏 G = {L | R} 是数，当且仅当 L 的每个元素都严格小于 R 的每个元素：

∀ G^L ∈ L, ∀ G^R ∈ R：　G^L < G^R

为什么这条判据如此关键？因为它把「左右打架」（某个左选项 ≥ 某个右选项）与「左右不打架」分开了。不打架时，{L | R} 落在一条有序的直线上——它「夹」在 max L 与 min R 之间，成为一个可以比较、可以排序的对象，也就是一个「数」。一旦打架，就无法把左右揉成一条线，只能作为一个「游戏」存在。

主角与非主角。主角是数：0 = { | }、1 = {0 | }、½ = {0 | 1}……它们构成全序域。非主角是「非数游戏」（是游戏但不是数），第一个例子就在眼前：∗ = {0 | 0}。0 < 0 不成立，故 ∗ 不是数——它的含义是「先手必胜的中立局面」，第一章 Nim 里的 ∗1 就是它。

三个层次，分清。① 游戏是最大的类（一切 {L | R}）；② 非数游戏是其中「左右打架」的那部分；③ 数是其中「每个左元素 < 每个右元素」的那部分。本章用一整章的力气证明第③部分是（真）全序域，同时也要留着第②部分——因为它承载了一章的胜负结构。

第二章 数即游戏：Conway 的超现实数2.5 生日与良基归纳

★★★ 递归定义必须有一个「落地」的度量，否则会无限循环。这个度量就是生日（birthday）。

定义（生日）。游戏 G 的生日 b(G) 是「严格大于 G 的所有左右选项的生日」的最小序数：

b(G) = 最小的序数 α，使 α > b(G^L) 且 α > b(G^R)（对所有选项）

空集情形：0 = { | } 没有任何选项，故 b(0) = 0——第 0 天。用第 0 天的数当左右集合，得到的是第 1 天的游戏（生日 1），依此类推。于是所有游戏被排成一条「天梯」：0、1、2、…、ω、…，序列可以是超限的，这正是「超现实」一名的由来。

良基归纳。生日的用处是让「对游戏做归纳」合法：要证明关于所有游戏的命题 P(G)，只需证明「假设 P 对所有生日小于 α 的游戏都成立，则 P 对生日为 α 的游戏也成立」。因为每个游戏的选项生日都更小，这个「回溯」永不循环。本章的每一条定义（序、加法、乘法）和每一个证明，都默认在做生日归纳。

一组重要的计数事实（实验 p66 真跑验证）。第 n 天新造出的数恰有 2ⁿ 个（n ≥ 1）；到第 n 天为止累计 2ⁿ⁺¹ − 1 个。特别地，第 n 天恰好造出全部分母不超过 2ⁿ⁻¹ 的二进分数——这就是 p48 的主题。

第二章 数即游戏：Conway 的超现实数2.6 第 0 天与第 1 天：0、1、−1

★★ 第 0 天：只有一个数。唯一没有选项的游戏是 0 = { | }。

第 1 天：±1。用第 0 天的数（只有 0）作选项，可能的组合只有三种：{0 | }、{ | 0}、{0 | 0}。前两个是数（0 < 空、空 < 0 自然成立），第三个不是数（0 < 0 不成立）。于是

1 = {0 | }　（左方走一步到 0，右方无路可走 ⟹ 左方必胜）

−1 = { | 0}　（右方必胜）　·　∗ = {0 | 0}　（先手必胜）

验证 0 < 1。由 p42 的定义：0 ≤ 1 成立（0 无左选项、1 无右选项，两种反例都不存在）；而 1 ≤ 0 不成立（1 的左选项 0 ≥ 0 就是反例）。故 0 < 1。对称地 −1 < 0。

验证 0 + G = G（0 是加法单位元）。展开 0 + 1 = { | } + {0 | }：左选项只有来自 1 的左边 {0 + 0}（0 的左右皆空），右选项为空。即 0 + 1 = {0 + 0 | }。若已知 0 + 0 = 0（把 { | } + { | } 展开即得），则 0 + 1 = {0 | } = 1。一般地 0 + G = G 对一切游戏成立（对生日归纳）：因为 0 没有任何选项，展开后式子原样回落。

还有一件事：{−1 | 1} = 0。虽然形状与 { | } 不同，但由 p42 可验证 {−1|1} ≤ 0 且 0 ≤ {−1|1}，故两者相等。「相等」是游戏的相等，不是书写的相同——这是本章最容易踩的坑之一（p55 专门讲）。

第二章 数即游戏：Conway 的超现实数2.7 第 2 天：2、½、−2、−½

★★ 第 2 天：2、½、−2、−½。现在左右集合可以取 −1, 0, 1 中任意「合法」的组合。逐一检查后，新的数有四个：

2 = {1 | }　·　−2 = { | −1}　·　½ = {0 | 1}　·　−½ = {−1 | 0}

（其余组合要么与已有数相等，要么左右打架不是数：{0 | 0} 已是 ∗，{−1 | 1} = 0，{1 | 0} 打架。）

为什么 {0 | 1} 一定是 ½？因为它是「大于 0、小于 1」的最简数。验证两步：① 0 ≤ {0|1} 且 {0|1} ≤ 1（由 p42 定义直接可查）；② 若某个数 G 满足 0 < G < 1，则必有 ½ ≤ G——即 ½ 是 0 与 1 之间的最小数。「最简单者胜出」是 Conway 构造的核心规则，p56 给出完整证明。

重点验证：½ + ½ = 1。展开

½ + ½ = {0|1} + {0|1} = { 0 + ½, ½ + 0 | 1 + ½, ½ + 1 }

若已知 0 + ½ = ½（单位元）与 ½ + 0 = ½，则左选项集合化为 {½}；右选项是 1 + ½ 与 ½ + 1。由定义逐项算出 1 + ½ = {1 | 2} = 3/2。于是

½ + ½ = { ½ | 3/2, 3/2 } = { ½ | 3/2 }

验证 {½ | 3/2} = 1：分别检验 {½|3/2} ≤ 1 与 1 ≤ {½|3/2}，两者都成立（因为 ½ < 1 < 3/2，1 恰好夹在中间且是最简者）。故 ½ + ½ = 1。◻ 实验 p66 用程序把这一串等式逐条复算了一遍。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

数之日 · 超现实数工坊合集从 {L | R} 逐天造出所有的数philomath.cn/surreal/

第二章 数即游戏：Conway 的超现实数2.8 第 3 天与二进分数

★★ 第 3 天：±3、±3/2、±3/4、±1/4。取第 2 天的数（−2,−1,−½,0,½,1,2）作选项，得到 8 个新数（第 2 天的两倍）：

3 = {2 | }　·　3/2 = {1 | 2}　·　3/4 = {½ | 1}　·　1/4 = {0 | ½}

分母的规律：第 1 天只出现整数（分母 1），第 2 天出现 ½（分母 2），第 3 天出现 ¼、¾（分母 4）。每过一天，可用的分母往前进一档（乘以 2）。

定理（有限天的二进分数）。一个数 x 在第 n 天之内被造出，当且仅当 x = m/2^k（m 为整数、k ≤ n−1），即 x 是一个二进分数（dyadic rational）。◻

证明思路（对 n 归纳）。① 若 x 的生日 ≤ n，由判据 x = {L|R} 夹在 max L 与 min R 之间；这两个都是分母 ≤ 2ⁿ⁻² 的二进分数，而它们之间最简的二进分数分母 ≤ 2ⁿ⁻¹，故 x 是二进分数。② 反过来，每个 m/2^k（k ≤ n−1）都能在第 n 天之前构造：它夹在两个相邻的、分母更小的二进分数之间。

一个漂亮的口号：½ 不是「0 与 1 之间的一个新符号」，而是「0 与 1 之间最简单的那个二进分数」。同理 1/4 是 0 与 ½ 之间最简的二进分数，3/4 是 ½ 与 1 之间最简的。于是第 n 天的全部数，就是在已有二进分数的每个相邻间隙里插中点，再把最外两端各推一格——一棵每天翻倍的二叉树（实验 p66 打印了第 0–4 天的完整名单）。

第二章 数即游戏：Conway 的超现实数2.9 全序：数的比较

★★★ 现在证明：全体数在关系 ≤ 下构成一个全序。需要三条：自反、传递，以及「任意两个数可比」（三分律）。

① 自反：G ≤ G。对生日归纳。若 G ≤ G 不成立，则要么存在 G^L ≥ G，要么存在 G^R ≤ G。但对数而言，每个左选项 G^L < G、每个右选项 G^R > G——两种反例都不可能出现。

② 传递：G ≤ H 且 H ≤ K ⟹ G ≤ K。反证。设 G ≤ H、H ≤ K 而 G ≰ K。由 G ≰ K，存在反例，分两种：(a) 有左选项 G^L ≥ K。由 G ≤ H 得 H ≰ G^L（否则 G^L 成了反例）；而由 G^L ≥ K 与 H ≤ K，用归纳的传递性得 H ≤ G^L，矛盾。(b) 有右选项 K^R ≤ G。由 H ≤ K 得 K^R ≰ H；由 K^R ≤ G 与 G ≤ H 得 K^R ≤ H，矛盾。两条都矛盾，故传递性成立。注意这里的归纳是对「三元组生日之和」做的——良基归纳的典型用法。

③ 三分律。任意两个数 G、H，必有 G ≤ H 或 H ≤ G。这一条对一般游戏不成立（∗ ‖ 0），但对数成立——它等价于「数之间的 ≤ 能由左右选项的夹逼决定」。数之所以能排成一条线，正是「每个左选项 < 每个右选项」这条判据的直接后果。三条合起来，数在 ≤ 下是全序。

第二章 数即游戏：Conway 的超现实数2.10 加法的群结构

★★★ 定理。全体数在加法下构成一个交换群：① 0 是单位元；② 每个数有负元，且 G + (−G) = 0；③ 加法的交换律与结合律成立。

① 单位元。0 + G = G 与 G + 0 = G：对生日归纳。展开 0 + G = { 0 + G^L | 0 + G^R }（0 左右皆空，故只剩 G 的选项），由归纳假设 0 + G^L = G^L，于是右边原样等于 {G^L | G^R} = G。

② 负元。证明 G + (−G) = 0（分两半：先证 G + (−G) ≤ 0，再证 0 ≤ G + (−G)）。以第一半为例：要证 G + (−G) ≤ 0，只需排除 0 的右选项（无）与和式的左选项。和式的左选项形如 G^L + (−G) 或 G + (−G^R)。以 G^L + (−G) 为例：由归纳假设 G^L + (−G^L) = 0，再用单调性 −G ≤ −G^L（因 G^L < G）得 G^L + (−G) ≤ G^L + (−G^L) = 0，故左选项 ≰ 0 的反例不存在——得 G + (−G) ≤ 0。另一半对称。

③ 交换与结合已在 p43 说明（逐项配对 + 归纳）。四者合起来，数构成交换群——而且是无挠的：若 n · G = 0（n ≥ 1）则 G = 0。

这条定理的意义。它说明「游戏的和」这套为胜负而设的运算，在「数」这一子类上退化成我们熟悉的加法——{L|R} 造出的数，其加法就是普通加法。于是「½ + ½ = 1」不再是一个需要小心核对的等式，而是群公理的推论。把「游戏」造得足够好，它自己会给出算术。

第二章 数即游戏：Conway 的超现实数2.11 乘法与有序域

★★★★ 有了加法群，还需要乘法。× 的递归定义比加法复杂得多，因为「G 的选项乘以 H 的选项」会产生交叉项。

定义（乘法）。对任意游戏 G、H，

G · H = { G^LH + GH^L − G^LH^L,　G^RH + GH^R − G^RH^R　|　G^LH + GH^R − G^LH^R,　G^RH + GH^L − G^RH^L }

这个怪物从哪里来？来自我们在中学就学过的分配律的逆向使用。我们希望乘法满足分配律 (a + b)c = ac + bc 与交换律 ab = ba。若 G = {G^L | G^R}，则形式上 G 是「G^L 与 G^R 的夹缝」。乘上 H 后，左方（对乘积有利）能用的手段是：在 G 上退到 G^L 而 H 不动，或在 H 上退到 H^L 而 G 不动，两种「退一步」叠加。但两次各退一步会重复计算那块小矩形 G^LH^L，所以要减掉它——这正是公式里 − G^LH^L 的来历（面积法）。四个式子分别对应：左方退 G、左方退 H、右方退 G、右方退 H。

定理（有序域）。全体数在 +, ·, ≤ 下构成一个全序域：交换律、结合律、分配律、每个非零元有逆元 G⁻¹ 均成立，且序与运算相容（G ≤ H ⟹ G + K ≤ H + K；K > 0, G ≤ H ⟹ GK ≤ HK）。这个域的证明是组合博弈论中最长的一段技术性论证，完整路线见挑战页 p65。它的结论却极简：我们造出了数域——而且是「生来就有序」的那一个。

先看两个乘法例子。1 · H = H（单位元）；2 · ½ = 1（½ 的乘法逆元就是 2）。用定义算 (−1)·(−1)：由 −1 = { | 0} 展开后可得 (−1)·(−1) = {0 | } = 1——「负负得正」在这里是被证明的，而不是被规定的。

第二章 数即游戏：Conway 的超现实数2.12 实数的嵌入：从 Dedekind 到 Conway

★★★★ 二进分数只是实数的一小部分。1/3、√2、π 呢？它们在第 ω 天（自然数天之后的那一天）被造出。

关键工具（最简性 + 夹逼）。对数而言，{L | R} 的值就是「严格夹在 max L 与 min R 之间的最简数」。当左右集合是无穷的（第 ω 天允许），就能「直取极限」：

√2 = { L | R }，L = { x : 二进分数且 x² < 2 }，R = { x : 二进分数且 x² > 2 }

因为 L 中每个元素都小于 R 中每个元素（左右不打架），所以这是一个数；又因为左右两族无限逼近 √2，它就是这个「割」唯一的数。同样的手法可定义 π = { L | R }（L、R 分别取 π 的全体二进分数下界与上界）。

与 Dedekind 切割的对照（p67 格物札记续谈）。Dedekind 造实数的方式是：在有理数集上取一个「切割」(A, B)（A 中每个数都小于 B 中每个数），把「切割」当作一个实数。Conway 的做法在形式上几乎一样：{L | R} 也是「左边一族、右边一族」——区别在于 Conway 的左右两族本身就是数（游戏），而且这套构造从 0 出发、不需要事先给定有理数或任何实数。Dedekind 从「已知的」造「未知的」；Conway 从「空」造「一切」。

一个深刻的结果。每个实数都有至多可数的生日（每个实数都在第 ≤ ω 天或某个可数序数天被造出）；但超现实数整体是真类（p53），比实数多得多。「嵌入」一词的含义是：实数是超现实数的一个子域，而超现实数在保留实数全部结构的同时，还额外装下了无穷大与无穷小。

第二章 数即游戏：Conway 的超现实数2.13 超限的生日：ω、1/ω 与 ε

★★★★ 现在让「天」数走到无穷。

先造无穷大。第 ω 天允许使用所有自然数（它们分别在第 0,1,2,… 天被造出）。于是

ω = {0, 1, 2, 3, … | }

它大于每一个自然数（左选项全是自然数、无右选项），因此是一个「比所有自然数都大」的数。但：它不是「∞」，而是一个真正的数——它可以加、可以乘、可以比较：ω + 1 = {ω | }、2ω、ω² 都造得出来。

再造无穷小。把 ω 取负得 −ω；而「1/ω」由

1/ω = {0 | 1, ½, ¼, ⅛, …}

定义：它大于 0，却小于每一个正数（因为右选项取遍所有正二进分数）。这就是一个正的无穷小（infinitesimal）。最早的正无穷小常写作 ε = 1/ω，满足 0 < ε < 1/n 对一切自然数 n 成立。于是我们在同一个数域里，同时拥有了无穷大与无穷小——这在实数域里是不可能的（Archimedes 性质禁止之），而超现实数域容得下它们。

「真类」的意思。超现实数不是集合，而是真类（proper class）：因为「所有序数」本身就是一个真类，而每个序数 α 都对应一个超现实数（第 α 天造出的那个「比所有更小序数都大」的数）。若超现实数是集合，则它包含全体序数，与 Burali–Forti 悖论（不存在「所有序数」的集合）矛盾。所以「数的世界」之大，超出了集合论的容量——它是 ZFC 里能谈论、却装不进一个集合的对象。

第二章 数即游戏：Conway 的超现实数2.14 非数的游戏：∗、↑ 与模糊关系

★★★★ 最后，回到本章另一半主角：不是数的游戏。

第一个例子：∗ = {0 | 0}。左右都能走到 0，但 0 < 0 不成立，故 ∗ 不是数。它的含义是先手必胜：无论谁先走，都走到 0（轮到对手就输），所以「谁先走谁赢」——这是第一章里 Grundy 值为 1 的局面 ∗1。更一般地，∗n = {0, ∗1, …, ∗(n−1) | 0, ∗1, …, ∗(n−1)} 就是第一章的 nimber n。

模糊（fuzzy）关系。既然 ∗ 不是数，试着比较它与 0：验证 0 ≤ ∗——需「无 ∗^R ≤ 0」，但 ∗^R = 0 而 0 ≤ 0 成立，故不满足——0 ≤ ∗ 假。同理 ∗ ≤ 0 假（0 ≤ ∗^L = 0 成立）。于是 ∗ ‖ 0（读作「∗ 与 0 模糊」）：既不 ≤，也不 ≥。这正是「先手必胜」在序关系上的表现——一个先手必胜的局面，既不能说它「对左方有利」，也不能说「对右方有利」。

第二个例子：↑ = {0 | ∗}。左方能走到 0、右方只能走到 ∗。可证 0 < ↑（左方略占优），且 ↑ ‖ ∗（与 ∗ 模糊）。↑ 是一个正的无穷小：它大于 0，却小于任何正数——和 1/ω 一样小，但不同于 1/ω（↑ − 1/ω 又是一个更小的、与 0 模糊的量）。↑ 的负元 ↓ = −↑ = {∗ | 0} 是负无穷小。这些「又小又模糊」的量，正是围棋残局、象棋先手优势这类「说不清谁好一点」的局面的数学化身。

nimber 上的序很怪。对 nimber 而言，要么相等，要么模糊：∗n ‖ ∗m 当 n ≠ m。也就是说「∗1 与 ∗2 哪个大」没有意义——它们不可比。（回想第一章：nimber 的「大小」由异或给出，而不是由整数序给出；「∗n 与 ∗m 相加」才是它们的算术。）第一章说「每个公平博弈等价于一堆 Nim」，第二章说「这些等价类就是这些模糊的游戏」——两句话说的是同一件事。

本章至此完整。数（每个左元素 < 每个右元素）组成全序域；非数游戏（左右打架）则是一章 nimber 与各种「优越/劣势/模糊」局面的家园。「游戏」比「数」大得多，而「数」只是其中秩序最好的那一部分。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

数之日 · 超现实数工坊合集从 {L | R} 逐天造出所有的数philomath.cn/surreal/

第二章 数即游戏：Conway 的超现实数误读：超现实数不是「实数加无穷」

★★ 本章最常被误传的一句话是：「超现实数就是实数再加上无穷大和无穷小。」它错在把超现实数想成了往实数上「外挂」几个符号。真相是：超现实数是从头造出来的一整个域，实数只是它的一部分，而无穷大与无穷小是这套构造自然生长的产物，不是外挂件。

误读一：把 ω 当作「新符号」。有人以为 ω 是「最大的自然数」那样的符号，被手写进公式里。不是的：ω = {0,1,2,… | } 是一个由已有数作左右集合造出的对象，它的每一条性质（ω > n 对一切自然数、ω + 1 = {ω | } 等）都由定义推出。没有任何符号是「规定」出来的，全部是「构造」出来的。

误读二：把 {0 | 1} 当作「0 与 1 之间的某个新数」。这个说法听起来对，其实指错了重点：{0|1} 不是「某个」新数，而是唯一确定的 ½——0 与 1 之间生日最小的那个数（p56 给出证明）。它不是一个含糊的「中间物」，而是一个有名字、可计算、参与一切算术的普通数字。

误读三：以为「每个实数都要人为指定生日」。恰恰相反：每个实数都在某个可数生日被造出（p52）。½ 在第 2 天，1/3 在第 ω 天（它是 {1/4, 1/4+1/16, … | 1/2, 1/2−1/16, …} 型的无穷夹逼），√2、π 亦然——没有一个是「外挂」进来的。

误读四：把「等价」当成「书写相同」。{ | } 与 {−1 | 1} 写法不同，却是同一个数 0；½ 也可以写成 {−1, 0 | 1}。游戏的「相等」由 ≤ 双向定义，而不是由长相定义（p42）。

那么超现实数的「多」到底在哪里？在于它的密度结构：实数之间没有「最小的正实数」，但超现实数在 0 附近有一整条无穷小阶梯：1/ω > 1/ω² > 1/ω³ > … > ↑ > 0，每一层附近又叠一层……实数只有一条线，超现实数在每一点的邻域里还藏着一个「无穷小的世界」——这就是它比实数「大得多」的确切含义（它是真类，见 p53）。

第二章 数即游戏：Conway 的超现实数例题 1：{0 | 1} = ½ 的证明

★★ 例题 1：证明 {0 | 1} = ½。这是全章第一个「值」的确定，必须按定义一步步验。

目标。记 ½ := {0 | 1}（它是一个数，因 0 < 1）。要证它「就是 ½」，即它与「直觉里的 ½」一致：夹在 0 与 1 中间、且是最简的那个。分三小步。

(a) ½ ≤ 1。按 p42 判据，要排除两种反例。反例①「某个 ½^L ≥ 1」：½^L = 0，而 0 ≥ 1 不成立（由 0 < 1）——反例①不存在。反例②「某个 1^R ≤ ½」：1 = {0 | } 无右选项——反例②不存在。故 ½ ≤ 1 成立。

(b) 0 ≤ ½。反例①「某个 0^L ≥ ½」：0 = { | } 无左选项——不存在。反例②「某个 ½^R ≤ 0」：½^R = 1，而 1 ≤ 0 不成立——不存在。故 0 ≤ ½。

(c) ½ 是 (0, 1) 中最简的数（「最简单者胜出」）。要说明「{0 | 1} 的值不可能是别的数」，只需说明：在开区间 (0, 1) 之内，½ 的生日最小。逐个检查更小的生日：第 0 天的数只有 0（不在 (0,1) 内）；第 1 天的数只有 −1, 1（也不在 (0,1) 内）。而 ½ = {0|1} 的生日是 2，且 0 < ½ < 1。故 (0,1) 中生日最小者就是 ½——这正是 {0|1} 的「最简性」含义。

一个必须纠正的流行说法。常有人把 (c) 写成「任何满足 0 < G < 1 的数 G 都有 ½ ≤ G」——这是错的：取 G = ¼，则 0 < ¼ < 1 但 ¼ < ½。反例提醒我们「最简」指的是生日最小，而不是「值最小」或「被所有中间数压住」。

结论。{0 | 1} = ½：它大于 0、小于 1，且是这对间隙里被「最简性」唯一选中的那个数。同理 {1 | 2} = 3/2、{0 | ½} = ¼、{½ | 1} = ¾——「夹在两个数中间最简者」是本章唯一的值判定规则。

第二章 数即游戏：Conway 的超现实数例题 2：加法与序的计算

★★★ 例题 2：加法与序的计算。用 p43 的加法定义逐项展开，再靠「最简性」收尾。四小题，全靠同一套动作：展开 → 用单位元/已知等式化简选项 → 取最简。

例 2-1（½ + ½ = 1）。展开 {0|1} + {0|1}：左选项 {0 + ½, ½ + 0} = {½, ½} = {½}；右选项 {1 + ½, ½ + 1} = {3/2, 3/2} = {3/2}。故 ½ + ½ = {½ | 3/2}。由最简性（(½, 3/2) 中生日最小者），它是 1。故 ½ + ½ = 1。◻

例 2-2（¼ + ½ = ¾）。¼ = {0 | ½}、½ = {0 | 1}。左选项：¼^L + ½ = 0 + ½ = ½；¼ + ½^L = ¼ + 0 = ¼。取较大者 ½。右选项：¼^R + ½ = ½ + ½ = 1；¼ + ½^R = ¼ + 1 = 5/4。取较小者 1。于是 ¼ + ½ = {½ | 1}，最简者 = ¾。故 ¼ + ½ = ¾。◻（与实验 p66 的 1/4 + 1/2 = 3/4 OK 一致。）

例 2-3（−½ + 1 = ½）。−½ = {−1 | 0}、1 = {0 | }。左选项：(−½)^L + 1 = −1 + 1 = 0；−½ + 1^L = −½ + 0 = −½。取较大者 0。右选项：(−½)^R + 1 = 0 + 1 = 1（1 无右选项）。于是 −½ + 1 = {0 | 1} = ½。◻ 这个 {0 | 1} 再次出现，恰好回到例 2-1 的主角。

例 2-4（序的计算：½ ≤ 1、−½ ≤ ½）。前者已在 p56 证过。后者：要证 {−1|0} ≤ {0|1}。反例①「(−½)^L ≥ ½」：−1 ≥ ½？否。反例②「½^R ≤ −½」：1 ≤ −½？否。两种反例都不存在，故 −½ ≤ ½。由 −½ ≤ ½ 与 ½ + (−½) = 0，又得「负数小于正数」——一切都从定义推出。

第二章 数即游戏：Conway 的超现实数例题 3：nimber 的语法

★★★ 例题 3：nimber 的语法。nimber 是「非数游戏」的主角，也是第一章 Grundy 值的真身。本例题把两章接起来。

例 3-1（∗ + ∗ = 0）。∗ = {0 | 0}。展开：左选项 {0 + ∗, ∗ + 0} = {∗, ∗} = {∗}；右选项同样 {∗}。故 ∗ + ∗ = {∗ | ∗}。而 ∗ 是它自己的负元（左右对称），所以 ∗ + ∗ = 0。直观：两个「先手必胜」并列，后手必胜——后手只要镜像先手在另一份里的走法（第一章 p24 的对称策略）。

例 3-2（∗ + ∗ + ∗ = ∗）。由例 3-1，∗ + ∗ = 0，故 ∗ + ∗ + ∗ = (∗ + ∗) + ∗ = 0 + ∗ = ∗。「三个先手必胜并列」又是先手必胜——这正是异或：1 ⊕ 1 ⊕ 1 = 1。

例 3-3（nimber 的定义与第一章的对应）。对 n ≥ 0，定义

∗n = { 0, ∗1, …, ∗(n−1) | 0, ∗1, …, ∗(n−1) }

则 ∗0 = 0、∗1 = ∗、∗2 = {0, ∗ | 0, ∗}。它与第一章的 Grundy 值一一对应：任何公平博弈 G 在「和」的意义下等价于 ∗𝒢(G)；而「和 = 异或」就是

∗n + ∗m = ∗(n ⊕ m)

例 3-4（∗2 + ∗3 = ∗1）。用上式：2 ⊕ 3 = 10₍₂₎ ⊕ 11₍₂₎ = 01₍₂₎ = 1，故 ∗2 + ∗3 = ∗1。（也可直接展开验证，但用对应的 Grundy 值最快。）——由此可见，第一章的「群结构」在本章获得了新名字：那些等价类就是这些模糊的 nimber。

例 3-5（nimber 之间不可比）。已知 ∗1 ‖ 0（p54）。一般地 ∗n ‖ ∗m（n ≠ m）。所以「∗2 与 ∗3 谁大」没有答案——它们不可比。要比较它们，只能用和与异或这套「nimber 算术」，而不是整数序。

第二章 数即游戏：Conway 的超现实数习题 1：构造与验证（基础）

★★ 习题 1：构造与验证（基础）。

1. 求出下列游戏的值（先判断是不是数，再用「最简性」定值）：{1 | 2}、{1 | 3}、{−1 | 1}、{0 | 2}、{−2 | 0}、{½ | 1}。提示：{0|2} 的答案不是「1 与 2 之间随便一个数」，而是区间 (0,2) 中生日最小者。

2. 证明 0 是加法单位元：对一切游戏 G，0 + G = G。写出对生日的归纳步骤（说明展开后为何「原样回落」）。

3. 证明 −(−G) = G（负元的对合性）。对生日归纳，直接用负元的定义 −G = {−G^R | −G^L} 展开两次。

4. 求下列游戏的生日：{ | }、{0 | }、{ | 0}、{1 | 2}、{½ | 1}、{0 | ½}。生日 = 1 + 左右选项生日的最大值（空集情形取 0）。

5. 判断下列哪些是数（哪些左右打架）：{0 | 1}、{0 | 0}、{1 | 0}、{−1 | 1}、{−½ | ½}、{1 | −1}。

6. 用定义展开验证 1 + 1 = 2（逐项写出左、右选项，再用最简性收尾）。

7. 验证 ½ ≤ 1 与 0 ≤ ½（写出被排除的两种反例）。

8. 证明 0 < ½ < 1 是严格的：即 {0|1} ≠ 0 且 {0|1} ≠ 1。用「严格小于」的定义（≤ 成立而反向 ≤ 不成立）。

第二章 数即游戏：Conway 的超现实数习题 2：序、域与游戏（进阶）

★★★ 习题 2：序、域与游戏（进阶）。

9. 完整证明 ≤ 的传递性：若 G ≤ H 且 H ≤ K 则 G ≤ K。把 p49 的两类反例写全，并指明每一步用到的归纳假设。

10. 证明 ↑ = {0 | ∗} 满足 0 < ↑ 且 ↑ ‖ ∗（与 ∗ 模糊）。证 0 < ↑ 用判据；证 ↑ ‖ ∗ 需分别说明 ↑ ≤ ∗ 与 ∗ ≤ ↑ 各因哪个反例而失败。

11. 证明 {0, ∗ | } 不是数（指出一对打架的左右元素）。再判断 {∗ | 0}、{0 | ∗} 是否为数。

12. 用乘法定义（p51）算 (−1)·(−1) = 1 的思路：写出 −1 = { | 0}、1 = {0 | }，展开四个选项式子，说明为何结果是 {0 | }。

13. 证明：若 G 是数则 G + (−G) = 0。这就是 p50 ② 的完整版；特别写清「单调性 G^L < G ⟹ −G ≤ −G^L」这一步。

14. 逐项展开证明 ¼ + ½ = ¾（左选项取最大、右选项取最小，再用最简性）。

15. 证明「第 n 天造出的数恰为分母不超过 2ⁿ⁻¹ 的二进分数」的第一段（若 x 生日 ≤ n 则是二进分数）。

16. 用 Grundy 值证明 ∗n + ∗m = ∗(n ⊕ m)，并算出 ∗4 + ∗6、∗5 + ∗2 + ∗7 的值。

第二章 数即游戏：Conway 的超现实数第二章地图：从博弈到全序域

本章的概念网络可以读成四条线（见下图）。

线一（构造线）。{L | R} → 生日 → 第 0/1/2/3 天的逐日构造 → 二进分数 → 实数 → 超限数 ω、1/ω。这条线回答「数从何而来」。

线二（运算线）。序与等价 → 加法与负元 → 乘法 → 全序域。这条线回答「造出的东西能否像数一样运算」。

线三（判据线）。数的判据（每个左元素 < 每个右元素）→ 三分律 → 全序。这条线回答「什么样的游戏才配叫数」。

线四（旁支）。左右打架的游戏 → ∗、↑、nimber → 模糊关系 ‖。这条线把第一章的 Grundy 值收进本章——非数游戏就是 nimber。

三个动作的对应关系。① 造：用已有游戏作左右集合，造一个新游戏（这是本章唯一的原始操作）；② 比：用「查反例」判断 ≤，进而得等号与模糊；③ 化：把游戏化成「最简的数」或「某个 nimber」，让运算变成普通算术。与第一章对照：那里把局面化成整数（Grundy 值），这里把游戏化成数或 nimber——同一套「化标准形」的思想。

本章的边界。本章的域只包含「数」；「非数游戏」只被部分刻画（我们知道了 ∗、↑，但一般的非数游戏理论远超本册）。而无限对局、随机博弈则完全在射程之外（第四、五章）。把边界记清楚，比记结论更重要。

第二章 数即游戏：Conway 的超现实数小结（一）：游戏即数

★★ 小结（一）：游戏即数。

正面清单。① 游戏的形式定义：G = {L | R}，左方从 L 取、右方从 R 取，无路可走者输（p41）；② 序与等价：G ≤ H ⟺ 不存在 G^L ≥ H 且不存在 H^R ≤ G（p42）；③ 加法与负元：G + H 与 −G 的定义、交换律、结合律（p43）；④ 数的判据：每个左元素 < 每个右元素（p44）；⑤ 生日与良基归纳（p45）；⑥ 0/1/½ 的构造顺序：0 = { | }、1 = {0 | }、−1 = { | 0}、½ = {0 | 1}（p46–p47）。

易错清单（每条都来自真实的手算事故）。① 把「左元素小于右元素」记反：判据是每个 L 都小于每个 R；写成「大于」或「存在一个」都不对。② 把等价当成相等：{ | } 与 {−1 | 1} 书写不同却相等（p42）。③ 以为 {0 | 1} 是「新数」：它就是 ½（p56）。④ 把「最简」理解成「值最小」：最简指生日最小；区间 (0,1) 里 ¼ 比 ½ 小，却不是最简者。⑤ 把 ∗ 当成数：∗ = {0|0} 因 0 < 0 不成立而不是数。⑥ 把模糊当「相等」：G ‖ H 表示既不 ≤ 也不 ≥（p54）。⑦ 以为「ω 是最大的自然数」：ω 不是自然数，它比一切自然数都大，且 ω + 1 > ω。

一句话的总结。本章把「数」这个最古老的对象，从「公理给定的」变成了「由游戏规则构造出来的」——{L | R} 是唯一的原始操作，其余全部是它的产物。造得出来，就无需假设；能运算，才配叫数。

第二章 数即游戏：Conway 的超现实数小结（二）：从公平博弈到全序域

★★★ 小结（二）：从公平博弈到全序域。

本章与第一章的接口（三处对接）。① 值 ↔ nimber：第一章把公平博弈折算成非负整数 𝒢(G)，第二章把这些等价类认作 ∗n——是游戏但不是数。② 和 ↔ 异或：第一章的和 = 异或，第二章把它写成 ∗n + ∗m = ∗(n ⊕ m)（p58）。③ 对称策略 ↔ 负元：第一章的「G + G 是 𝒫 位置」正是第二章的「∗n + ∗n = 0」，也就是「每个 nimber 是自身的负元」。第一章的全部结论，都能在第二章的语言里重述一遍。

两章的分工。第一章处理公平博弈，得到整数（模等价）；第二章允许左右不同，得到全序域与超现实数。前者是后者的一个切片：非负整数都嵌在超现实数里，而 nimber 是超现实数旁边那层「模糊的影子」。

算法清单（遇到一个 {L | R} 时的标准流程）。① 判：检查是否每个左元素 < 每个右元素——是数还是非数游戏？② 定值：若是数，取夹在 max L 与 min R 之间的最简数；③ 算生日：b(G) = 1 + max 选项生日；④ 运算：需要加减乘时，按递归定义展开、逐项配对、取最简；⑤ 接第一章：若是非数游戏，试着把它对应到一个 nimber。

通往第三章的钩子。本章把「游戏」翻译成了「数」。那么下一个问题自然冒出来：当游戏不再是抽象的石子，而是几何对象呢？折纸的一张纸、七桥的一幅图、魔方的 43 252 003 274 489 856 000 个状态——它们的「游戏」是什么结构？答案不会是一个数，而会是一个群、一张图、一个拓扑空间。第三章要把「游戏 → 结构」这条主线，从代数接到几何上。

第二章 数即游戏：Conway 的超现实数思想卡：自由造数

延伸思考（三问）。① 如果我们把「数的判据」放松为「每个左元素 ≤ 每个右元素」（允许相等），会造出什么？（提示：那正是非数游戏 ∗ 的入口。）② 如果不用「最简者胜出」，而用「左族最大者与右族最小者之间随便挑一个」，构造还唯一吗？③ 本章的构造只用了「集合」与「序数」；若把序数换成别的良基序，还能造出「数」吗？（这是「组合博弈论」推广到一般良基结构时的真问题。）

第二章 数即游戏：Conway 的超现实数挑战：超现实数的域公理

★★★★ 挑战：把「数是全序域」完整证明一遍。这是本册技术含量最高的一段论证，也是本章全部定义的价值所在。按下面的四步规范写作，每一步都要标明「对生日归纳」以及对哪个式子归纳。

第一步（全序）。定义 G ≤ H（p42），依次证明：① 自反（对数是显然的：每个左元素 < G < 每个右元素）；② 传递（反证 + 对三元组生日之和归纳，p49 给了骨架）；③ 三分律（任意两数可比）。关键：这三条只对「数」成立，对一般游戏不成立——指明哪里用到了「左右不打架」。

第二步（加法群）。① 0 是单位元；② G + (−G) = 0（分 ≤ 与 ≥ 两半，用到引理 A：G^L < G ⟹ −G ≤ −G^L）；③ 交换律、结合律（逐项配对 + 归纳）。

第三步（乘法与有序域）。① 先证乘法良定义：对 G、H 的「选项对数之和」归纳，说明公式 p51 的左右选项确实「每个左 < 每个右」（否则乘出的不是数）；② 证交换律 GH = HG（公式对 G、H 对称）；③ 证结合律与分配律（本章最长的两段归纳，建议先证分配律）；④ 证 1 = {0 | } 是乘法单位元。

第四步（序与运算相容 + 逆元）。① 单调性（引理 A 的乘法版）：G ≥ H 且 K ≥ 0 则 GK ≥ HK——先证 K > 0 的情形；② 逆元（引理 B）：对 G > 0，令

G⁻¹ = { 0, G^L/G, (G^L + 1)/G… | … }（按 Conway 的构造，形如「用已有数逼近 1/G」）

并证明 G · G⁻¹ = 1（对 G 的生日归纳，用乘法单调性把 1 夹在 G·G⁻¹ 两侧）。四步合起来：数在 +, ·, ≤ 下构成全序域。◻

参考文献（自学者按此顺序读）。① Conway《On Numbers and Games》（1976）——原始文献，本章的全部构造出自此书；② Gonshor《An Introduction to the Theory of Surreal Numbers》（1986）——最适合初学者的严格教材；③ Berlekamp–Conway–Guy《Winning Ways for Your Mathematical Plays》（1982）——组合博弈论的应用百科；④ Siegel《Combinatorial Game Theory》（2013）——现代标准参考书，含本挑战的完整证明。

第二章 数即游戏：Conway 的超现实数实验：超现实数的有限 Day 构造真跑

★★ 实验：超现实数的有限 Day 构造真跑。本节所有数字都来自本地脚本 qa/p66_lab.py（纯 Python 标准库，实现 {L | R} 的逐天构造、递归加法与 ≤），输出存于 qa/p66_out.txt，可自行复算。

实验一：逐天构造与计数。按生日逐天枚举所有「数」（用「值只依赖 max L 与 min R」做等价筛 + 规范形去重），得到：

① 逐天构造：Day 0-4 的全部数
  Day 0 : 0
  Day 1 : -1, 0, 1
  Day 2 : -2, -1, -1/2, 0, 1/2, 1, 2
  Day 3 : -3, -2, -3/2, -1, -3/4, -1/2, -1/4, 0, 1/4, 1/2, 3/4, 1, 3/2, 2, 3
  Day 4 : -4, -3, -5/2, -2, -7/4, -3/2, -5/4, -1, -7/8, -3/4, -5/8, -1/2,
          -3/8, -1/4, -1/8, 0, 1/8, 1/4, 3/8, 1/2, 5/8, 3/4, 7/8,
          1, 5/4, 3/2, 7/4, 2, 5/2, 3, 4

  Day n 新造出的数：
    Day 0 新增 ( 1 个): 0
    Day 1 新增 ( 2 个): -1, 1
    Day 2 新增 ( 4 个): -2, -1/2, 1/2, 2
    Day 3 新增 ( 8 个): -3, -3/2, -3/4, -1/4, 1/4, 3/4, 3/2, 3
    Day 4 新增 (16 个): -4, -5/2, -7/4, -5/4, -7/8, -5/8, -3/8, -1/8,
                        1/8, 3/8, 5/8, 7/8, 5/4, 7/4, 5/2, 4

可见 Day n 新造出的数恰为 2ⁿ 个（Day 3 八个、Day 4 十六个），且每天新增的数正好是「上个日子所有数的两倍」——与 p48 的定理一致。

③ 计数统计
  Day  新增个数  累计个数  正数个数  负数个数(累计)
    0         1         1         0           0
    1         2         3         1           1
    2         4         7         3           3
    3         8        15         7           7
    4        16        31        15          15
  规律核对：Day n 新增应 = 2n；累计应 = 2n+1-1
  计数规律是否全部吻合： True

  按分母（2 的幂）统计 Day 4 新增数：
    分母 20 : 2 个     分母 21 : 2 个
    分母 22 : 4 个     分母 23 : 8 个

实验二：{L | R} 的递归加法与 ≤（与二进数值对拍）。脚本用符号展开构造规范形，再按 Conway 定义实现 ≤ 与加法，逐条验证：

② {L|R} 的递归加法与 <= 验证（与二进数值对拍）
  符号展开 -> 规范形 -> 值：
    0     = {|}  ->        值 = 0
    1     = {0|}  ->       值 = 1
    -1    = {|0}  ->       值 = -1
    2     = {0,1|}  ->     值 = 2
    1/2   = {0|1}  ->      值 = 1/2
    -1/2  = {-1|0}  ->     值 = -1/2
    1/4   = {0|1,1/2}  ->  值 = 1/4
    3/4   = {0,1/2|1}  ->  值 = 3/4
    3/2   = {0,1|2}  ->    值 = 3/2
  加法验证：
    1/2 + 1/2 = 1     (期望 1)    OK
    1/4 + 1/2 = 3/4   (期望 3/4)  OK
    -1/2 + 1 = 1/2    (期望 1/2)  OK
    1 + 1 = 2         (期望 2)    OK
    3/4 + 1/4 = 1     (期望 1)    OK
    -1 + -1 = -2      (期望 -2)   OK
  序关系验证 (<=)：
    1/2 <= 1 ? True      1 <= 1/2 ? False
    0 <= 1/2 ? True      1/2 <= 1/2 ? True
    -1/2 <= 1/2 ? True   3/2 <= 2 ? True
  1/2 + 1/2 = 1 的「游戏等式」核对：
    le(1/2+1/2, 1) 且 le(1, 1/2+1/2) 是否都成立？ True

  {0|1} 的规范形是否为 1/2 ？ True   (L = [0] , R = [1])

三个值得注意之处。① 1/2 + 1/2 = 1、1/4 + 1/2 = 3/4、−1/2 + 1 = 1/2、1 + 1 = 2 全部通过——递归加法与二进数值逐条吻合，这是对 p43/p47 的独立检验；② {0|1} 的规范形（左集为 {0}、右集为 {1}）核实了 p56 的结论 {0|1} = ½；③ 序关系的验证（含 ½ ≤ ½ 的自反）与理论一致。

第四个环节（与理论对拍）。实验刻意把「蛮力逐天枚举」与「公式（2ⁿ 计数、二进分数定理）」并置：枚举是笨但可靠的，公式快但需要证明——两者对拍一致，才算真的相信了 p48 的定理。本册实验页都遵循同一格式：可复算的脚本 + 可核对的输出 + 与理论的对拍。

极限的提醒。本实验只跑到 Day 4（因为 2ⁿ 增长很快）。1/3、√2、ω 需要第 ω 天——那已经超出「有限枚举」的射程，只能靠 p52 的「割」来理解。「有限天可枚举，超限天靠构造」正是本章的分界线。

扫码进馆· 本页配套游戏工坊 · 手机上直接开玩

数之日 · 超现实数工坊合集从 {L | R} 逐天造出所有的数philomath.cn/surreal/

第二章 数即游戏：Conway 的超现实数格物札记：从 Dedekind 切割到生日构造

本章的「造数」不是孤例：它是一条从十九世纪延伸到二十世纪的方法论主线，而且在中国的算学传统里有自己的回声。

先说 Dedekind 切割。一八七二年，Dedekind 发现有理数轴是「不完整」的：√2 处有个洞。他的修补办法是：把一个「切割」（把有理数分成 (A, B)，A 中每一个都小于 B 中每一个）定义为实数。于是 √2 就是「平方小于 2 的有理数全体 / 平方大于 2 的有理数全体」这个切割。这是一个公理化补全：不再问「实数是什么」，只规定「实数是切割」，然后证明这样得到的对象满足实数的全部要求。

再说 Conway 生日构造。形式上看，二者几乎一样——都是「左边一族、右边一族，中间夹一个数」。但有一处决定性的差别：Dedekind 的切割需要事先给定有理数轴（背景域），而 Conway 的 {L | R} 从空集出发、不需要任何背景。有理数、实数、ω、1/ω 全部是这套规则的产物，而不是前提。Dedekind「补全已知」，Conway「生成一切」——这是「公理化」与「构造性」的典型对照。

中算传统的回声。中国的算学对「用已知夹出未知」这套动作异常熟悉。《九章算术》的「盈不足」（双假设法）就是一场漂亮的夹逼：先给两个猜测值分别算出「盈」与「不足」，再按线性插值定出真正的解——用两次试算把答案夹住。更著名的例子是刘徽的割圆术：用正多边形（内接与外切）从两侧逼近圆的面积，π 被夹在两个上、下界之间。可以发现这与 Conway 的 {L | R} 在结构上同构：左边一族（内接/不足）、右边一族（外切/盈），中间那个被夹住的量就是要找的数。「左右夹逼、取中间」，是一个跨越文化与世纪的普遍算法。

为什么强调「构造性」？因为公理化的造数需要先相信背景对象存在（有理数、实数），而构造性的造数只需要接受规则。前者回答「这个对象应当满足什么性质」，后者回答「这个对象是怎么来的」。在数学基础上，这两条路各有所长：公理化便于推理，构造性便于理解「最小假设」。本章选择构造性，正是为了展示数学的自由——不预设对象，只忠实于规则，让数自己长出来。这也解释了本章为什么从 { | } 这个「什么都没有」的游戏开始。

第二章 数即游戏：Conway 的超现实数速查：第二章概念与公式

★ 速查：第二章概念与公式。

一、记号。{L | R} 游戏（L 左选项、R 右选项）；≤ 序；= 游戏相等；‖ 模糊；b(G) 生日；G + H 和；−G 负元；∗n nimber；↑、↓ 正/负无穷小。

二、定义。① 游戏：{L | R}，无路可走者输；② G ≤ H ⟺ 不存在 G^L ≥ H 且不存在 H^R ≤ G；③ G = H ⟺ G ≤ H 且 H ≤ G；④ 数是左元素全小于右元素的游戏；⑤ G + H = {G^L+H, G+H^L | G^R+H, G+H^R}；⑥ −G = {−G^R | −G^L}；⑦ b(G) = 1 + max 选项生日。

三、核心定理。① 数判据：{L|R} 是数 ⟺ 每个左元素 < 每个右元素；② 最简性：{L|R}（数）的值 = 夹在 max L 与 min R 间生日最小的数；③ 生日归纳：第 n 天新增数 = 2ⁿ，累计 = 2ⁿ⁺¹ − 1；④ 二进分数定理：有限天造出 ⟺ 二进分数 m/2^k；⑤ 全序域：数在 +, ·, ≤ 下构成全序域；⑥ 乘法：G·H = {G^LH+GH^L−G^LH^L, … | …}；⑦ nimber：∗n + ∗m = ∗(n ⊕ m)，∗n ‖ ∗m（n ≠ m）。

四、常用数值。0 = { | }；1 = {0 | }；−1 = { | 0}；2 = {1 | }；½ = {0 | 1}；−½ = {−1 | 0}；¼ = {0 | ½}；¾ = {½ | 1}；3/2 = {1 | 2}；ω = {0,1,2,… | }；1/ω = {0 | 1, ½, ¼, …}；∗ = {0 | 0}；↑ = {0 | ∗}。常用等式：½ + ½ = 1、¼ + ½ = ¾、−½ + 1 = ½、G + (−G) = 0、∗ + ∗ = 0。

五、与第一章的接口。Grundy 值 𝒢(G) ↔ nimber ∗n；「和 = 异或」↔ ∗n + ∗m = ∗(n ⊕ m)；「G + G 是 𝒫 位置」↔「∗n + ∗n = 0」（每个 nimber 是自身负元）。

六、典型数值（实验真跑）。Day 0–4 全部数：0；±1；±2, ±½；±3, ±3/2, ±¾, ±¼；±4, ±5/2, ±7/4, ±5/4, ±7/8, ±5/8, ±3/8, ±1/8。Day n 新增 2ⁿ 个，验证全部通过。

七、三个动作。造（{L|R}）· 比（查反例判 ≤）· 化（化成最简数或 nimber）。

第二章 数即游戏：Conway 的超现实数第三章预告：几何的游戏

★★ 第三章预告：几何的游戏。

本章留下的接口。我们把「游戏」翻译成了「数」：抽象的 {L | R} 一步步长成全序域，而公平博弈的等价类落在 ∗n（nimber）上。但：本册遇到的「游戏」到目前为止都是抽象的——一堆石子、一个 {L|R}。如果游戏的对象是几何的呢？一张可以折的方纸、一座七座桥的城、一个每面都有颜色的魔方——它们的「游戏」是什么结构？

第三章的问题。几何从来是玩出来的：折纸（Origami）比尺规更强——Huzita–Hatori 公理允许的六种折叠操作能解三次方程，从而「三等分角」与「倍立方」在折纸上都成为可能；七桥问题是 Euler 为消遣而写的一页论文，却诞生了图论，「奇点计数」判据讲出了一笔画游戏的全部秘密；15-拼图的不可解性用置换的奇偶性一锤定音；魔方群是 43 252 003 274 489 856 000 个状态的置换群，而「上帝之数 = 20」是一条关于群直径的定理；Hex 的「不可能平局」是拓扑的对偶性，策略偷取在其中再次登场。

为什么它们属于同一套框架？因为本章的「结构 + 策略 + 等价」三件套在这里依然成立：① 结构——折纸的每一步是一次反射，七桥的每一步是走过一条边，魔方的每一步是一次置换；它们分别对应反射群、图、置换群。② 策略——「能否三等分角」「能否一笔画完」「魔方能否还原为 k 步」都是可以证明的判断，而不是手感。③ 等价——两个折纸构造是否达成同一个几何效果、两个图是否同构、两个魔方状态是否同属一个共轭类，都是「把一个对象化成标准形」的动作——与本章「把游戏化成数」同源。

本章的三个悬念。① 折纸为什么能解三次方程，而尺规不能？（答案在「可构造数域的次数」上。）② 一笔画游戏的判据（Euler 回路）为什么只看「奇点的个数」？③ 魔方的「上帝之数」为什么是 20 而不是 100？（这是群的直径问题，用双向 BFS + 群论剪枝证明。）

一个预告性的比喻。第二章说「游戏即数」，把游戏折算成一个代数对象；第三章要说「游戏即结构」——把游戏折算成一张图、一个群、一个拓扑空间。视角再翻转一次：数只是结构的一种，几何是更丰富的那一种。带上本章的行囊（造对象、查反例、取标准形），我们进入折纸与魔方的世界。