博弈论
一些简单的定义： 必胜点（N点）：走到必胜点的玩家一定胜利。 必败点（P点）：走到必败点的玩家一定失败。 定理1.所有游戏终结的点都是必败点。 定理2.所有一步 能 走到必败点的就是必胜点。因为对手将面临必败点。 定理3.通过一步操作 只能 到必胜点的就是必败点。因为对手将获得必胜点。 取石子游戏 有两堆石子和两个玩家。 每回合，玩家可以选择从 某一堆 取走一个石子，或者从 两堆 中都取走一个石子。 最后无法操作的玩家失败。 分析 以 ( A , B ) ( A , B ) 表示当前的状态：第一堆有 A A 个石子，第二堆有 B B 个石子。 由于这个游戏没有和局，所以 某个状态不是必败点就是必胜点 。 首先考虑 终结点 ：两堆石子都空了，面对这个状态的玩家必败。 于是有了第一个必败点： ( 0 , 0 ) ( 0 , 0 ) 。 定理2.所有一步能走到必败点的就是必胜点。因为对手将面临必败点。 由于 ( 0 , 1 ) ( 0 , 1 ) 和 ( 1 , 0 ) ( 1 , 0 ) 能走到 ( 0 , 0 ) ( 0 , 0 ) ，因此它们是必胜点。 定理3.通过一步操作 只能 到必胜点的就是必败点。因为对手将获得必胜点。 考虑 ( 0 , 1 ) ( 0 , 1 ) ，显然 ( 0 , 2 ) ( 0 , 2 ) 只能走到 ( 0 , 1 ) ( 0 , 1 ) ，所以 ( 0 , 2 ) ( 0 , 2 ) 是必败点。由于 ( 0 , 3 ) ( 0 , 3 ) 能走到 ( 0 , 2 ) ( 0 , 2 ) 让对手必败，所以 ( 0 , 3 ) ( 0 , 3 ) 是必胜点。 以此类推，我们得到结论： ( 0 , 2 k ) ( 0 , 2 k ) 是必败点， ( 0 , 2 k + 1 ) ( 0 , 2 k + 1 ) 是必胜点。 如何让对手面临 ( 0 , 2 k ) ( 0 , 2 k ) 呢？显然，当目前局面是 ( 1 , 2 k + 1 ) ( 1 , 2 k + 1 ) 时，可以两堆各取一个石子，所以 ( 1 , 2 k + 1 ) ( 1 , 2 k + 1 ) 是必胜点。 类似地， ( 1 , 2 k ) ( 1 , 2 k ) 是必胜点，因为：