吃苹果游戏和简单回合制游戏的通解
问题：
有20个苹果。
两个人轮流吃，可以吃一个，也可以吃半个。
吃半个的时候，可以吃原来就是半个的，也可以把一个完整的吃掉一半，也就是说可以有很多半个的苹果。
吃一个的时候，只能吃完整的一个。
没有其他选项。
最后吃苹果的人输。
请问，先吃还是后吃的有必胜的策略？这个必胜策略是什么？
答案：
后手有必胜策略。开始的时候先手怎么吃，后手就怎么吃，换言之后手总是设法保持剩下的整苹果和半苹果都是偶数即可。但当剩下的整苹果刚好只有两个的时候，肯定轮到先手吃，而后手此时不能跟先手学。如果先手吃掉一个整苹果，后手就把最后一个整苹果吃掉一半，让半苹果数量变成奇数。如果先手把一个整苹果吃掉一半，那么后手就吃掉最后一个整苹果，保持半苹果是奇数个。由于此时剩下奇数个半苹果，只能轮流吃，后手必胜。
这个问题的答案并不很难找到，通过倒推的方法很容易解决。但对于这类问题，有没有通用的解法呢？
现在就给出一个通用的解法：
通解：
- 确定游戏的完整状态（或者说局面）参数。比方说上面题目的完整状态参数就是(m,n,p)，m是整苹果的个数，n是半苹果的个数，p是此时由谁行动。
- 游戏的行动规则确定了状态的迁移规则，或者说从某个状态出发可以到达哪些状态。比方说上面题目从(m,n,p)出发只能到达(m-1,n,~p)——吃一个整苹果、(m,n-1,~p)——吃一个半苹果、(m-1,n+1,~p)——吃半个整苹果，~p表示轮到对方行动。
- 游戏的初始规则确定了状态空间的出发点。
- 游戏的获胜规则确定了哪些状态是直接被判定为某一方获胜的。比方说上面问题中(0,0,p)意味着p获胜。在这些状态上，哪个玩家获胜，那么这个状态本身对于这个玩家来说就是有必胜策略的状态（废话，这个状态玩家p都已经获胜了那么p在该状态上当然是有必胜策略的）。
- 最后一步就是从这些已知的必胜状态出发，递归地确定其他的状态是哪个玩家有必胜策略的状态。如果对于一个玩家来说，根据行动规则某个轮到自己行动的状态存在到达某个自己必胜的状态的行动选择，那么该点对于自己来说也是必胜状态，于是可以递归地将所有的状态都标记上是哪一方必胜，初始状态也会被标记，因此就可以确定初始状态哪一方有必胜策略。
上述解法原则上可以寻找任何完全信息的确定性的回合制的游戏的必胜方和必胜策略。完全信息意思是任何一个回合中，每一个玩家对游戏的局面都有完全的信息，因此不包括桥牌这种不知道对手手中有什么牌的游戏。确定性意思是轮到任何一个玩家行动的时候他可以做出完全确定的行动，因此不包括飞行棋之类需要掷骰子决定如何行动的游戏。回合制意思是参与游戏的若干玩家是按照确定的规则轮流行动的，行为决策是离散的，因此不包括需要连续不断地做行为决策的游戏。类似围棋象棋五子棋跳棋（可以是多方跳棋）的游戏原则上都可以用上述解法寻找必胜方和必胜策略。只不过对于大部分流行的棋类游戏，上述方案会过于庞大以至于无法实际应用。但对于前面这种可以用于做智力题的完全信息确定回合制游戏，用上述通用解法大都可以迅速找到必胜方和必胜策略。
现在以前面的问题为例来说明这个通用解法。由于规则是两个人交替行动，所以(m,n,p)里面的p可以省略，用(m,n)代表状态就可以了，于是状态空间就变成了二维平面上的格点空间。而游戏的行动规则决定了从一个格点出发可以到达哪些格点。注意，由于取消了参数p，所以(0,0)状态无法确定谁胜谁负，但只有一个半苹果的状态(0,1)显然是后手必胜，因为先手只能吃掉这半个苹果而输掉游戏。另外，只有一个整苹果的状态(1,0)显然是先手必胜，但这一点可以通过(0,1)是后手必胜来导出，因此是可有可无的。有了这一个确定的格点，其他所有的格点先手还是后手有必胜策略都可以确定了：对于任何一个格点S，如果从S出发能够到达的所有格点全都是先手有必胜策略的格点，那么S就是后手有必胜策略的格点（因为后手在下一步变为先手）。否则，如果从S出发能够到达的格点之中至少有一个是后手有必胜策略的格点，那么S就是先手有必胜策略的格点（因为先手可以选择进入这个后手必胜的格点，自己同时变成后手）。
上图中，直接确定了(0,1)、(1,0)两个画圈的点的必胜方和必胜策略。图中选了几个典型的点示范了其他点的颜色是如何确定的：凡是从该点出发只能到达绿色点的点都涂成红色，凡是从该点出发至少有一个目标点是红色的点都涂成绿色。从两个画圈的点出发（其实只从(0,1)出发就够了），可以递归确定所有点的颜色。只需要做几步就可以发现规律得到答案。
插件比较