首先,动态博弈是指参与人的行动有先后顺序,而且行动在后者可以观察到行动在先者的选择,并据此作出相应的选择。典型的例子是下棋(如象棋、围棋、跳棋等)。下棋有两个博弈参与者,一人一步,游戏规则和每一步的信息都是完全公开的,且无任何运气成分,游戏的所有可能局面有限且游戏规则已决定游戏会在有限步内结束。策梅洛定理告诉我们:这类游戏先行或后行方当中必有一方有必胜或必不败的策略。
下面简单证明策梅洛定理。为方便计,对游戏的所有可能状态染色,如果某一状态已经判定先手胜则该状态染黑,同理先手负则该状态染白。如果某一状态是先手方行动且它的所有后继状态都是白色,则这一状态染白。如果某一状态是先手方行动且存在它的某一个后继状态是黑色,则这一状态染黑。如果是后手方行动,同上。此局先手(红)下一步无论怎么走,后继状态都是白色(输)。
总结一下:没有平局,每个游戏局面要么是必胜态,要么是必败态;一个状态是必败态,当且仅当它的所有后继状态都是必胜态;一个状态是必胜态,当且仅当它的后继状态存在一个必败态。必胜策略的核心本质是:理清必胜态和必败态,并构造必胜态与必败态之间的状态转移。
下面选取一些著名游戏的例子来说明如何构建必胜/败策略。为了方便,去掉可能出现平局的游戏。
Bash Game有枚棋子甲乙轮流拿,每次只能拿枚,谁拿到最后一枚棋子算胜。若甲先拿,问:谁有必胜策略?当n=1时,甲(先手)必胜;当n=2时,甲(先手)不管拿几枚,乙(后手)都可以在下一次全拿完,即甲行动的所有后继状态都是乙必胜,所以甲(先手)必败;当n=3时,甲(先手)只要拿1枚后,就可以让乙先手并面临n=2的情形,即甲行动的某一个后继状态都是乙必败,所以甲(先手)必胜。