网站建设基本知识2021最火关键词
假设你和小红打赌，玩“拿走游戏”，输的人请对方吃饭....
你们面前有21个筹码，放成一堆；每轮你或者小红可以从筹码堆中拿走1个/2个/3个；第一轮你先拿，第二轮小红拿，你们两个人交替进行;拿走筹码堆中最后的一个的人赢得游戏。
是不是摩拳擦掌可以开始玩啦？你拿了两个，小红拿了三个...作为观众的我开始记录你们每轮交替拿走后，筹码堆中剩余筹码的数量（黑色代表你拿走之后的筹码剩余数，红色则代表小红拿走之后的）：
19；16；15；12；11；8；6；4；2；0
omg,小红拿走了最后一个筹码（她拿完后剩余筹码数变成0）。小红完美获胜！
输了游戏的你得请吃饭了....（顺便请下我)bushi)
下次还玩吗？
我偷偷告诉你，这个游戏有“必胜策略”。
请带着耐心往下看。
（碎碎念：第一部分“无偏组合游戏”的定义会有些枯燥，如果只想看制胜策略的话，可以跳过第一部分，直接看第二部分）
目录
一、无偏组合游戏（impartial combinational games）
1.组合游戏特点：
2.无偏游戏特点
3.组合游戏定义
二、拿走游戏的“制胜策略”
1.逆向推理（反向归纳法）（难推）
2.P&N positions解法（推荐）
一、无偏组合游戏（impartial combinational games）
拿走游戏属于一种无偏组合游戏，所以下面先介绍无偏组合游戏。
1.组合游戏特点：
设定如下：
- 两个玩家，I与II
- 完整信息(perfect information)
- 没有随机性（no chance move)
- 要么赢，要么输
比如开头的拿走游戏，就是你与小红两个玩家，你们都能看到场上的筹码和对方每轮的动作，你们一旦确定拿走几个筹码，就一定能拿走几个筹码；最后不可能平局，总会有个人拿走最后一个筹码，成为赢家，而另一个人成为输家。
2.无偏游戏特点
要求：
- 在每个位置，对于玩家I和玩家II的行动是同等的。也就是说，两个玩家的可选策略是相同的，且游戏的状态仅依赖于当前配置，而与玩家的身份无关。（比如上面提到的拿走游戏，不会因为你是小红还是小明，你是玩家I还是玩家II而影响策略）
有偏游戏则与无偏游戏的要求相反。（比如一些英雄游戏，你们的角色会影响你们的策略）
3.组合游戏定义
同时满足下列条件的游戏称作组合游戏：
- 两个玩家，I与II
- 一套通常有限的可能位置（positions）
- 游戏规则指定了两个玩家的合法行动；若规则对于两个玩家没有差别，则为无偏游戏，反之为有偏游戏。
- 玩家I和II交替行动
- 抵达其中一个位置时，游戏结束，同时下一个玩家无法行动。一般(normal)游戏规则是，最后一个完成行动的玩家获胜；misère(不幸）游戏规则相反，最后一个完成行动的玩家输掉游戏。
- 如果游戏永远不结束，陷入了平局(draw),必须要增加额外条件（也就是增加Ending Condition),来终结平局，评出胜负。
- 无论两个玩家怎么行动，最终游戏都能在有限步内结束
二、拿走游戏的“制胜策略”
1.逆向推理（反向归纳法）（难推）
19；16；15；12；11；8；6；4；..
回顾最开始你与小红的游戏过程，其实小红把筹码拿到只剩4个的时候，你就能意识到无论如何自己都输了。如果自己拿走1个，那么还剩3个；拿走2个剩2个；拿走3个剩1个。而无论自己拿走多少，剩的1/2/3个小红都能一次性全部拿走，取得游戏胜利。
于是逆向推理一下，如果自己想要赢，需要走到“4”的位置，也就是拿完筹码还剩4个。
我们要想拿完筹码还剩4个，出发点就得是5/6/7(也就是小红拿完后剩余的筹码数量）。
为了让小红拿完后还剩5/6/7,小红开始拿的时候就还得剩8个.....
我们把拿完就必胜的位置定义成“P-positions”,可以发现P-positions有：4,8,12,16,20.也就是说，只要你拿完了还剩4个或8个或其他P位置，只要你按制胜策略继续走下去，就一定能赢。
2.P&N positions解法（推荐）
P位置，即positions that are winning for the Previous player (the player who just moved)，拿完走到这个位置的玩家获胜。
N位置，即 winning for the Next player to move，拿完之后走到这个位置，你的对手玩家（也就是下一轮行动的玩家）会获胜。
要想赢拿走游戏，我们只需要四个步骤：
1）标记终点为P位置。（本游戏中，0为P位置）
2）有路径可以抵达P位置的标记为N位置。（1，2，3都可以抵达0，故1，2，3都为N）
3）只能到达N位置的标记为P位置。（4只能到达1，2，3，故4为P）
4）重复2）3）直至游戏中所有有限可达位置都被标记为P&N。
本游戏标记下来就是：
位置：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
P/N: P N N N P N N N P N N N P N N N P N N N P N
于是你可以总结规律（注意，不同游戏规则下这个规律不一样）：
P位置是4k;N位置是4k+1， 4k+2，4k+3.你需要努力走到4k的位置。
怎么证明你找到的规律是正确的？
1）证明终点是P点（即走到终点一定能获胜）
2）证明任何N点都能走到P点（对应4k+1， 4k+2，4k+3，我们拿走1/2/3个筹码一定能走到4k）
3) 证明任何P点都只能走到N点（对于4k,走不到4k的位置，只能走到4k+1或4k+2或4k+3的N位置）
学会了吗~学会了拿14个筹码，每次只能拿走1/3/4个筹码试一试哟~