游戏理论 | Hello World

游戏理论 | Hello World
这类问题的特点就是
1. 只有两个玩家。
2. 两个玩家轮流走，最后有一个赢或者输的条件
3. 每个玩家每步都有确定的输赢，不存在中间状态。
这类问题共同的做法就是每个玩家每步存在两种可能性，要么是wining position，要么是losing
每个状态有如下的属性：
1. 结束状态是losing position
2. 如果玩家可以按规则到达一个losing position，那么当前他就处在winning position
3. 如果没办法到达losing postion，所有可能的move都只能移动到winning position，说明当前是losing position，写出代码来就是
boolean isWin(position pos) {
try all possible newPos moves
if !isWin(newPos)
return true;
return false;
}
给个例子，如果我们有11个硬币，每次只能拿1,3,4个数，怎样判断先手是否能赢。（拿最后一个硬币的算赢）。
照上面的例子，如果拿到0个的时候，这时候就处在losing position了。所以写出代码
boolean isWin(position pos, int[] coins) {
if (pos W
1 �C => W
2 �C => L
3 �C => W
4 �C => W
5 �C => W
6 �C => W
7 �C => L
发现规律，对于连续n个-
如果分割成L + L或者W + W，当前是L， 如果一个L一个W，当前是W。如果循环所有可能分割，只要其中有一个W，那当前就是W
所以说可以用递归很容易找到每个连续的――这样的是W还是L，然后再考虑如果有多个连续的―-的情况，如果L的个数是一个，那么第一个走的玩家一定是L，反之如果有两个，那么第一个走的玩家是W的。以此类推，只要有奇数个L那么第一个玩家是输，不然的话是赢。
计算每个连续―的话，可以用dynamic programming 的方法来优化。
6.algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set choosable，target）
这道题属于游戏问题，topcoder里面有讲这类问题
https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/
idea就是如果你能走到losing position，那么你现在就处于winning position，不然说明你只能走到winning position，那说明你现在属于losing position，用递归写这道题就是
isWin(Set choosable, target){
if (choosable.isEmpty()){
return false;
}
for(int i : choosable) {
if (i >= target)
return true;
choosable.remove(i);
if (!isWin(choosable, target-i)) {
return true;
}
choosable.add(i);
}
return false;
}

Read full article from 游戏理论 | Hello World