《稳操胜券》读书笔记

　　本书的读书笔记，风格上将没有很严格的ZFC洁癖，因为某些具体的结构的大小可能随随便便就有序数类大小。并且（虽然确实可以用一种图论的方式叙述来避免这一点）可能出现一个集合有关于$\in$的无穷递降列的情况。
　　
　　本书所提到的游戏会有以下性质的一部分：
　　1、有两位局中人，称为左方和右方；
　　2、存在着几种，一般是有限多种局势，通常有一个特殊的开局状态；
　　3、具有明确的规则来安排每一步走法，以使任一局中人从某一局势转移到他所选择的下一局势；
　　4、左方与右方在游戏进行的全过程中都应交替地行动；
　　5、按正常规定，不能行动的局中人就是输家；
　　6、游戏规则的安排将使一个局中人无法行动，此时博弈即告结束。这称为终止条件。因此，不允许反复走动而打成平局；
　　7、两位局中人完全了解进行中的一切情况，即博弈具有完全信息；
　　8、不存在随机行动，例如抛掷骰子或洗牌等。
　　本书后面章节中所讨论的一些博弈并不完全满足上述条件。但是，所有要讲到的博弈都满足条件7与8。
　　
　　
　　
　　
　　

一、关于接下来几小节的事先说明

　　接下来将会讲到的游戏，都将满足条件12345678，并且部分游戏的条件6会被加强。
　　
　　在这个设定之下，任何一个状态都是“由两个状态的集合构成的有序对”，记为$a=\{B|C\}$。此记号的意思是说，如果左方拿到状态$a$，则他可以将游戏改为$B$中的任何一个状态，而如果右方拿到状态$a$，则他可以将游戏改为$C$中的任何一个状态。（这段话可以理解为条件1、3的形式化叙述）
　　
　　一个游戏就是指一组状态构成的集合$\mathscr G$，且如果$\{A|B\}\in\mathscr G$，则$A\subset\mathscr G,B\subset\mathscr G$。$\mathscr G$中存在一个状态$s$，规定为初始状态。（这段话可以理解为条件2的形式化叙述，如果再加上$\mathscr G$有限的限定，那就是条件2中“状态有限”的形式化叙述）
　　
　　接着，递归定义一些概念：
　　1、一个状态$\{A|B\}$被称为“左先必败”当且仅当$A$中任何状态“右先必胜”；
　　2、一个状态$\{A|B\}$被称为“右先必败”当且仅当$B$中任何状态“左先必胜”；
　　3、一个状态$\{A|B\}$被称为“左先必胜”当且仅当$A$中存在一个状态“右先必败”；
　　4、一个状态$\{A|B\}$被称为“右先必胜”当且仅当$B$中存在一个状态“左先必败”。
（此递归定义是条件4和5的结果，其中定义1和2中由于虚真所造成的“空集则必败”的结果来自条件5）

　　关于条件6，可以描述为：
　　1、弱化的条件6是指，上述关于“必胜必败”的递归定义，使得$\mathscr G$中所有状态都完成了分类；
　　2、标准的条件6是指，$\mathscr G$中不存在满足$a_{2i+2}\in_la_{2i+1}\in_ra_{2i},\forall i\in\mathbb N$的无穷递降列，也不存在满足$a_{2i+2}\in_ra_{2i+1}\in_la_{2i},\forall i\in\mathbb N$的无穷递降列；（$a\in_l\{B|C\}$是指$a\in B$，$a\in_r\{B|C\}$是指$a\in C$）
　　3、强化的条件6是指，$\mathscr G$中不存在满足$a_{i+1}\in_{lr}a_i,\forall i\in\mathbb N$的无穷递降列。（$a\in_{lr}b$是指$a\in_lb\lor a\in_rb$）
　　
　　补充几个为了方便而存在的定义：
　　1、左先必胜且右先必胜简称先手必胜；
　　2、左先必败且右先必败简称先手必败；
　　3、左先必胜且右先必败简称左方必胜；
　　4、左先必败且右先必胜简称右方必胜。

二、有限深度极偏博弈（我暂时这么称呼，不知道常规称呼是什么）

　　此节中所叙述的游戏将增加一些条件，且这些条件不是那么方便一句话就说清。在这之前，先引入一棵二叉树。
　　一棵（点深度有限，整体深度无限）的完全二叉树$T$是指这样递归定义的集合：
　　1、$s\in T$，被称为根；
　　2、如果$a\in T$，则$l(a)\in T$，被称为$a$的左后继；
　　3、如果$a\in T$，则$r(a)\in T$，被称为$a$的右后继。
　　
　　在这棵树上可以定义深度函数$d:T\to\mathbb N$：
　　1、$d(s)=0$；
　　2、$d(l(a))=d(a)+1$；
　　3、$d(r(a))=d(a)+1$。
　　
　　在这棵树上可以递归定义节点的后代集$De:T\to\mathscr P(T)$：
　　1、$a\in De(a)$；
　　2、$b\in De(a)$则$l(b)\in De(a)$；
　　3、$b\in De(a)$则$r(b)\in De(a)$。
$a\in De(b)$也称为$b\in An(a)$，$An(a)$被称为$a$的祖先集。
　　
　　在这棵树上可以定义一个全序$\leq:T\to T\to Prop$（关于这确实是一个全序请自己验证）：
　　1、$a\leq a$；
　　2、$a\in De(l(b))$则$a\leq b$；
　　3、$a\in De(r(b))$则$b\leq a$。
由此可自然地衍生出$\geq,<,>$的定义。
　　
　　可以给该树上的所有节点对应一个二进制有限小数，将二进制有限小数集记为$\mathbb B$，并且此对应是序同构（请读者自己证明），故今后不再区分$T$和$\mathbb B$：
　　1、$0$对应于$s$且$l(0)=-1,r(0)=1$；
　　2、$\forall a\in\mathbb Z_-,l(a)=a-1,r(a)=a+\frac12$；
　　3、$\forall a\in\mathbb Z_+,r(a)=a+1,l(a)=a-\frac12$；
　　4、$\forall a=\frac p{2^q}(2\not|p)\in\mathbb B\setminus\mathbb Z,l(a)=a-\frac1{2^{q+1}},r(a)=a+\frac1{2^{q+1}}$。

　　对于$\mathbb B\cup\{-\Omega,\Omega\}$中的两个元素$a<b$，可以定义它们的“最简中间”$mid(a,b)$，是指满足$a<c<b$的$c$中，$d(c)$最小的，关于此定义的唯一性，请读者自己验证（而且$mid(a,b)$必定属于$\mathbb B$）。
　　
　　于是，对于一个满足条件12345678，6是强化版的，的游戏$\mathscr G$，如果存在映射$w:\mathscr G\to \mathbb B$满足以下条件，就称其为一个有限深度极偏游戏：

$$w(\{A|B\})=mid(\max_{a\in A}w(a),\min_{b\in B}w(b))$$ 。$w(a)$被称为$a$的游戏数。
（实际还声明了$\max_{a\in A}w(a)$以及$\min_{b\in B}w(b)$的存在性和$\max_{a\in A}w(a)<\min_{b\in B}w(b)$，并且此处设$\max_{a\in\varnothing}w(a)=-\Omega,\min_{a\in\varnothing}w(a)=\Omega$）

定理 一个有限深度极偏游戏上状态的必胜性的描述将非常简单：
　　1、$w(a)=0$则$a$先手必败；
　　2、$w(a)<0$则$a$右方必胜；
　　3、$w(a)>0$则$a$左方必胜。
证明 由于满足强条件6，所以直接超限归纳法证明就行：
1、$w(\{A|B\})=0$意味着，$\forall a\in A,w(a)<0$且$\forall b\in B,w(b)>0$，于是$A$中状态均右方必胜，$B$中状态均左方必胜，由此得$\{A|B\}$先手必败。
2、$w(\{A|B\})<0$意味着，$\forall a\in A,w(a)<0$且$\forall b\in B,w(b)\leq0$，于是$A$中状态均右方必胜，$B$中存在左先必败，由此得$\{A|B\}$右方必胜；
3、$w(\{A|B\})>0$意味着，$\forall a\in A,w(a)\geq0$且$\forall b\in B,w(b)<0$，于是$A$中存在右先必败，$B$中状态均左方必胜，由此得$\{A|B\}$左方必胜。

　　现在定义一个新的东西，叫做游戏的加法，此概念不止在本节有用，今后还会用到：
定义 考虑两个状态$\{A|B\}$和$\{C|D\}$，定义$\{A|B\}+\{C|D\}$为：

$$\left\{\bigcup_{a\in A}\{a+\{C|D\}\}\cup\bigcup_{c\in C}\{\{A|B\}+c\}\Bigg|\bigcup_{b\in B}\{b+\{C|D\}\}\cup\bigcup_{d\in D}\{\{A|B\}+d\}\right\}.$$ 该定义的现实描述就是说，考虑有两个游戏摆在左方和右方面前，现在两个游戏分别处于某个状态，而任何一方接手这对状态的时候，允许做的是任选其中一个游戏并执行一步其在该游戏中能做的操作，并将回合交给对方。如果轮到某一玩家时，两个游戏都无法继续操作，则算其失败。此“递归定义”在游戏满足强化版条件6时，可以直接用递归方式理解，但如果不满足，若要想在集合论背景下理解这到底是什么意思，则需要用一种图论的方式来理解。注意，两个满足条件6的状态之和不一定满足条件6，但是两个满足强化版条件6的状态之和一定满足强化版条件6。（请读者自行证明第二点，以及给出第一点的例子，第一点的例子书上有）。
　　
定理 如果满足强化版条件6，状态的加法符合交换律以及结合律。
请读者自行证明。

接下来就是该节的核心定理，也是需要一些分类讨论才能证明的定理（如果用某些证明思路，可能分类讨论会异常繁琐）：
定理 对于有限深度极偏游戏中的两个状态$a,b$，$w(a+b)=w(a)+w(b)$。
证明 此命题实际就是说，

$$\forall a<b,c<d\in\mathbb B\cup\{\Omega,-\Omega\}, \\mid(a,b)+mid(c,d)=mid(\max(a+mid(c,d),mid(a,b)+c),\min(b+mid(c,d),mid(a,b)+d)).$$ 为了不要让分类讨论过于繁琐，先定义两个函数$L,R:\mathbb B\to\mathbb B\cup\{-\Omega,\Omega\}$：
1、$L(0)=-\Omega,R(0)=\Omega$；
2、$\forall a\in\mathbb Z_-,L(a)=-\Omega,R(a)=a+1$；
3、$\forall a\in\mathbb Z_+,L(a)=a-1,R(a)=\Omega$；
4、$\forall a=\frac p{2^q}(2\not|p)\in\mathbb B\setminus\mathbb Z,L(a)=a-\frac1{2^q},R(a)=a+\frac1{2^q}$。
于是，$mid(a,b)=c$等价于说$L(c)\leq a<c<b\leq R(c)$（这一点请读者自己证明）。
记$e=mid(a,b),f=mid(c,d)$，于是就是要证明 $$L(e+f)\leq\max(a+f,e+c)<e+f<\min(b+f,e+d)\leq R(e+f).$$ 其中两个小于号是显然的，故只证明两个小于等于号。
可以改为证明：
$$L(e+f)\leq\max(L(e)+f,e+L(f))\land\min(R(e)+f,e+R(f))\leq R(e+f)$$

①1+1型：

$$L(e+f)=-\Omega=\max(L(e)+f,e+L(f))\\R(e+f)=\Omega=\min(R(e)+f,e+R(f))$$
②1+2型： $$L(e+f)=-\Omega=\max(L(e)+f,e+L(f))\\R(e+f)=f+1=\min(R(e)+f,e+L(f))$$
③1+3型： $$L(e+f)=f-1=\max(L(e)+f,e+L(f))\\R(e+f)=\Omega=\min(R(e)+f,e+R(f))$$
④1+4型： $$L(e+f)=f-\frac1{2^{q_f}}=\max(L(e)+f,e+L(f))\\R(e+f)=f+\frac1{2^{q_f}}=\min(R(e)+f,e+R(f))$$
⑤2+2型： $$L(e+f)=-\Omega=\max(L(e)+f,e+L(f))\\R(e+f)=e+f+1=\min(R(e)+f,e+R(f))$$
⑥2+3型： $$L(e+f)\leq e+f-1=\max(L(e)+f,e+L(f))\\R(e+f)\geq e+f+1=\min(R(e)+f,e+R(f))$$
⑦2+4型： $$L(e+f)=e+f-\frac1{2^{q_f}}=\max(L(e)+f,e+L(f))\\R(e+f)=e+f+\frac1{2^{q_f}}=\min(R(e)+f,e+R(f))$$
⑧3+3型： $$L(e+f)=e+f-1=\max(L(e)+f,e+L(f))\\R(e+f)=\Omega=\min(R(e)+f,e+R(f))$$
⑨3+4型： $$L(e+f)=e+f-\frac1{2^{q_f}}=\max(L(e)+f,e+L(f))\\R(e+f)=e+f+\frac1{2^{q_f}}=\min(R(e)+f,e+R(f))$$
⑩4+4型：
$p_e<p_f$： $$L(e+f)=e+f-\frac1{2^{q_f}}=\max(L(e)+f,e+L(f))\\R(e+f)=e+f+\frac1{2^{q_f}}=\min(R(e)+f,e+R(f))$$
$p_e=p_f$： $$L(e+f)\leq e+f-\frac1{2^{p-1}}<\max(L(e)+f,e+L(f))\\R(e+f)\geq e+f+\frac1{2^{p-1}}>\min(R(e)+f,e+R(f))$$

证毕。

　　根据已知的这些东西，可以开始考虑书上所说的以下游戏了（下述游戏的极偏性的证明以后有空再说，换句话说，关于其游戏数的通项式的证明，以后有空再说）：
　　
切饼 考虑一个大小为$m\times n$的格子图，左右双方轮流行动。任何左方的回合，左方可以从现有的格子图中选一个至少还有两列存在的，从任何一个竖线的位置将该格子图切成两个放回去，如果没有了则左方失败。任何右方的回合，右方可以从现有的格子图中选一个至少还有两行存在的，从任何一个横线的位置将该格子图切成两个放回去，如果没有了则右方失败。
于是根据游戏的描述，可以设$f(n,m)$表示$n$列$m$行的方格图所对应的状态的游戏数，其具有如下的递推式：

$$f(n,m)=mid(\max_{i=1}^{n-1}f(i,m)+f(n-i,m),\min_{i=1}^{m-1}f(n,i)+f(n,m-i)).$$

濯足节蛋糕 与上一个游戏类似，只不过每一次切割，不是随意找一条对应方向的线切开，而是要求将选中的方格图等分为至少两份，每一份的边长都依旧得是整数。
于是可得如下递推式：

$$f(n,m)=mid(\max_{d|n\land d\neq1}\frac ndf(d,m),\min_{d|m\land d\neq1}\frac mdf(n,d)).$$

三、（有限深度）无偏游戏

　　本节考虑的游戏，满足条件12345678且$\mathscr G$中所有状态都形如$\{A|A\}$。这样的游戏称为无偏游戏。
　　本节并不考虑所有的无偏游戏，而只是考虑满足以下条件的无偏游戏：存在$v:\mathscr G\to\mathbb N$，其满足

$$v(\{A|A\})=mex\{v(a):a\in A\}:=\min\mathbb N\setminus\{v(a):a\in A\}.$$ 我将满足此条件的无偏游戏称为有限深度无偏游戏。

定理 对有限深度无偏游戏中的一个状态$a$，若$v(a)=0$则其先手必败，若$v(a)\neq0$则其先手必胜。
证明
因为符合条件6，可以使用超限归纳法：
1、$v(\{A|A\})=0$意味着$A$中均为先手必胜态，故$\{A|A\}$先手必败；
2、$v(\{A|A\})\neq0$意味着$A$中存在先手必败态，故$\{A|A\}$先手必胜。

定理 对有限深度无偏游戏中的两个状态$a$和$b$，$v(a+b)=v(a)\oplus v(b)$。
证明
根据超限归纳法可知，只要证明，对任何真包含于$\mathbb N$的$A,B$，

$$mex\bigcup_{a\in A}\{a\oplus mexB\}\cup\bigcup_{b\in B}\{mex A\oplus b\}=mexA\oplus mexB.$$
设$s=mexA,t=mexB$，于是证明分为两部分：
1、$s\oplus t\notin\bigcup_{a\in A}\{a\oplus t\}\cup\bigcup_{b\in B}\{s\oplus b\}$，这一点很显然，只要注意到$(\mathbb N,\oplus)$构成一个交换群。
2、$\forall x<s\oplus t,x\in\bigcup_{a\in A}\{a\oplus t\}\cup\bigcup_{b\in B}\{s\oplus b\}$，此命题依靠对$s$和$t$的最大位数使用归纳法：
①$s=t=0$的情况，虚真；
②$s$的位数不等于$t$的位数的情况，设$s$的位数为$m$，$t$的位数为$n$，不妨设$m<n$。于是对于$x$的高$n-m$位小于$t$的高$n-m$位的情况，$b$的高$n-m$位同$x$高$n-m$位，而$b$的低$m$位的取法是自由的，故可以完全枚举所有$2^m$种
情况；而对于$x$的高$n-m$位等于$t$的高$n-m$位的情况，问题就被化归为了$s$和$t$的低$m$位的问题，归纳完成；
③$s$的位数等于$t$的位数且位数大于等于$1$的情况，设位数为$n$，于是$s\oplus t$的位数至多为$n-1$，这直接将问题化归为$s$和$t$的低$n-1$位的问题，归纳完成。

有限深度无偏游戏的例子非常常见，在此就不举例了。

四、负状态

从上文中会发现，至少对已经介绍到的满足加强版条件6的状态，分别存在着某种加法同态，对于此的扩展，就是基于本节所讲的东西。本节中所有讨论都满足条件12345678，且条件6是加强过的，不再说明。

定理
（1）对任何状态$a$和$b$，若$b$先手必败，则$a+b$和$a$的胜败性相同；（重点是要证明这一条，后四条都只是用于加强了方便使用归纳法）
（2）左先必败和右先必胜求和为右先必胜；
（3）左先必败和左先必败求和为左先必败；
（4）右先必败和左先必胜求和为左先必胜；
（5）右先必败和右先必败求和为右先必败。
证明

$$\{A|B\}+\{C|D\}=\\\left\{\bigcup_{a\in A}\{a+\{C|D\}\}\cup\bigcup_{c\in C}\{\{A|B\}+c\}\Bigg|\bigcup_{b\in B}\{b+\{C|D\}\}\cup\bigcup_{d\in D}\{\{A|B\}+d\}\right\}.$$
①如果$\{A|B\}$左先必胜，$\{C|D\}$先手必败，则$A$中存在右先必败的$a$，这个$a+\{C|D\}$就是右先必败的，故$\{A|B\}+\{C|D\}$左先必胜；
②如果$\{A|B\}$右先必胜，$\{C|D\}$先手必败，则$B$中存在左先必败的$b$，这个$b+\{C|D\}$就是左先必败的，故$\{A|B\}+\{C|D\}$右先必胜；
③如果$\{A|B\}$左先必败，$\{C|D\}$先手必败，则$A$中均右先必胜，$C$中均右先必胜，于是$a+\{C|D\}$均右先必胜，$\{A|B\}+c$均右先必胜，故$\{A|B\}+\{C|D\}$左先必败；
④如果$\{A|B\}$右先必败，$\{C|D\}$先手必败，则$B$中均左先必胜，$D$中均左先必胜，于是$b+\{C|D\}$均左先必胜，$\{A|B\}+d$均左先必胜，故$\{A|B\}+\{C|D\}$右先必败；
⑤如果$\{A|B\}$左先必败，$\{C|D\}$右先必胜，则$D$中存在左先必败的$d$，这个$\{A|B\}+d$左先必败，故$\{A|B\}+\{C|D\}$右先必胜；
⑥如果$\{A|B\}$左先必败，$\{C|D\}$左先必败，则$A$中均右先必胜，$C$中均右先必胜，于是$a+\{C|D\}$均右先必胜，$\{A|B\}+c$均右先必胜，故$\{A|B\}+\{C|D\}$左先必败；
⑦如果$\{A|B\}$右先必败，$\{C|D\}$左先必胜，则$C$中存在右先必败的$c$，这个$\{A|B\}+c$右先必败，故$\{A|B\}+\{C|D\}$左先必胜；
⑧如果$\{A|B\}$右先必败，$\{C|D\}$右先必败，则$B$中均左先必胜，$D$中均左先必胜，于是$b+\{C|D\}$均左先必胜，$\{A|B\}+d$均左先必胜，故$\{A|B\}+\{C|D\}$右先必败。

定义 对于状态$\{A|B\}$，定义$-\{A|B\}$为

$$\left\{\bigcup_{b\in B}\{-b\}\Bigg|\bigcup_{a\in A}\{-a\}\right\}.$$ 今后$a+(-b)$也被记为$a-b$。

定理 对任何状态$a$，$-(-a)=a$。
读者自己完成证明。

定理 对任何状态$a$和$b$，$-(a+b)=-a-b$。
读者自己完成证明。

定理 对任何状态$a$，$a$先手必败则$-a$先手必败，$a$先手必胜则$-a$先手必胜，$a$左方必胜则$-a$右方必胜，$a$右方必胜则$-a$左方必胜。
证明

$$-\{A|B\}=\\\left\{\bigcup_{b\in B}\{-b\}\Bigg|\bigcup_{a\in A}\{-a\}\right\}$$ ，于是：
①$\{A|B\}$先手必败意味着$a\in A$均先手必胜或右方必胜，$b\in B$均先手必胜或左方必胜，于是$-a$均先手必胜或左方必胜，$-b$均先手必胜或右方必胜，于是$-\{A|B\}$先手必败；
②$\{A|B\}$先手必胜意味着$a\in A$存在先手必败或左方必胜，$b\in B$存在先手必败或右方必胜，于是$-a$存在先手必败或右方必胜，$-b$存在先手必败或左方必胜，于是$-\{A|B\}$先手必胜；
③$\{A|B\}$左方必胜意味着$a\in A$存在先手必败或左方必胜，$b\in B$均先手必胜或左方必胜，于是$-a$存在先手必败或右方必胜，$-b$均先手必胜或右方必胜，于是$-\{A|B\}$右方必胜；
④$\{A|B\}$右方必胜意味着$a\in A$均先手必胜或右方必胜，$b\in B$存在先手必败或右方必胜，于是$-a$均先手必胜或左方必胜，$-b$存在先手必败或左方必胜，于是$-\{A|B\}$左方必胜。

定理 对任何状态$a$，$a-a$是先手必败的。
证明

$$\{A|B\}-\{A|B\}=\\\left\{\bigcup_{a\in A}\{a-\{A|B\}\}\cup\bigcup_{b\in B}\{\{A|B\}-b\}\Bigg|\bigcup_{b\in B}\{b-\{A|B\}\}\cup\bigcup_{a\in A}\{\{A|B\}-a\}\right\}$$ 而 $$\forall a\in A,a-a\in_ra-\{A|B\}\\\forall b\in B,b-b\in_r\{A|B\}-b\\\forall a\in A,a-a\in_l\{A|B\}-a\\\forall b\in B,b-b\in_lb-\{A|B\}$$ 于是完成了归纳。

定理 对任何状态$a$和$b$，$a-b$先手必败，则$b-a$先手必败。
证明 $a-b$先手必败，故$b-a=-(a-b)$先手必败。

定理 对任何状态$a,b,c$，若$a-b$先手必败且$b-c$先手必败，则$a-c$先手必败。
证明 $a-b$和$b-c$先手必败，故$(a-b)+(b-c)$先手必败，故$(a-c)+(b-b)$先手必败，又因为$b-b$先手必败，故$a-c$先手必败。

如上三条定理说明了本节核心定理：
定理 $a-b$先手必败构成了$a$和$b$的等价关系。

而且此等价关系在之后的章节将直接写作“$=$”，这样做是合理的，因为如下两个定理：

定理 加法在此等价类族上具有良定义。
证明 即要证明如果$a-b$先手必败且$c-d$先手必败，则$(a+c)-(b+d)$先手必败。因为$a-b$和$c-d$先手必败，所以$(a-b)+(c-d)=(a+c)-(b+d)$先手必败。

定理 胜败性在此等价类族上具有良定义。
证明 即要证明如果$a-b$先手必败，则$a$和$b$有相同的胜败性。因为$a-b$先手必败，故$b+(a-b)=a+(b-b)$和$b$具有相同的胜败性，又因为$b-b$先手必败，故$a$和$b$具有相同的胜败性。

下一节，将有必要用本节的结论重新审视二三两节的内容。