桌游的策梅洛定理的证明

策梅洛定理指回合制完全信息游戏最优解下先手要么必胜，要么必败，要么和棋。

策梅洛定理证明起来三两句话就解释了。

回合制桌游从第一步开始就是一棵决策树，第一层每一个分支是先手玩家做的选择，然后每一个分支有子分支，子分支是另一名玩家的回合可以做的选择，然后一层层形成整个决策树，最末端的分支的值三种情况：先手胜、先手败、和棋。

最末端的分支有若干个并列分支，连在父分支上，父分支的值也就确定了，比如父分支是先手玩家，先手玩家会在分支里挑选一个作为结果，肯定是有先手胜选先手胜，没有选和棋，然后选先手负（所谓的alpha-beta剪枝算法差不多大意也是这句话），然后父分支的值就是确定的了。

决策树上一个父节点上的子节点个数是有限个，比如围棋只有361个点，即便这个数字可能很大很大，但依然是有限个，这个“有限”就保证了若所有子节点的结果知道了，父节点的结果也就知道了（无限在数学上复杂一点），然后一层层父节点推上去最终根节点上整盘游戏的输赢也就知道了。Q.E.D.

当然棋局的“输赢和棋”条件要保证游戏最终是能在有限步结束的，保证最末端分支的存在。

另外别被误导，alpha-beta剪枝算法也可以用在非完全信息回合制游戏上。

————————————

留个小思考题：假如我们有个计算力无穷的计算机，非完全信息博弈能不能统计所有最终叶子节点上的先手胜的数目和所有最终叶子节点上的后手胜的数目来得出先手优势或者后手优势的结论呢？

思考线索：不完全的信息也是可以穷举的，比如斗地主对面手牌的组合也是可以穷举，即便这个数字很大很大。