上个月有个好基友面试weixin，连问两道博弈相关的题目。很多公司喜欢通过这一类型的题目，判断面试者的思维是否缜密。我们通过一个例子，来讲讲这类问题的一种解决思路。
原题
EllysCheckers
题意
2个人玩游戏，这个棋盘游戏是一个1*n的棋盘，每个位置上最多一个子。然后有两种不同的操作方式：
-
选择其中一个子往右边移动一步（右边的位置是空的）
-
选择一个子往右边移动3步（右一右二有棋子，右三没有）
当一个棋子到达最优边时，就立刻消失。
无路可走的人失败，现在给一个初始棋盘，问先手能否必胜。（假设两个人都是绝对聪明的玩家）
数据范围是20
思路
一道题上来我们先看数据范围，范围是20，棋盘有两种状态，这意味着我们能够枚举出所有棋盘的状态(2^20)。
我们把棋盘的每个状态称之为局面，两个绝对聪明的人博弈有下面这么一个原则：
-
每个局面不是必胜态，就是必败态。（两个人都会选择最优的结果）
-
如果能下一步是一个必败态，那么这个局面是必胜的。
-
如果一个局面只能到达必胜态，那么，这个是必败的。
在本题中，如果只有一个棋子，并且这个棋子在最右边，或者一个棋子都不存在，则为必败态。
我们可以用一个map来记录这个状态，然后开始记忆化搜索。
我们注意到这个题目还有另外一个条件，当棋子到达最右的时候消失，这个条件等价于最右的位置可以放多个棋子。
关键代码(JAVA)
private boolean canWin(int board, int length){
if (map.containsKey(board)){
return map.get(board);
}else{
//能够到达必败态的一定是必胜态, 到达不了必胜态的, 就是必败态.
boolean reachLoseGame = false;
//向右移动一位
for (int i = length - 1; i > 0; --i){
if (isChess(board, i)){
//右边没棋子或者右边是最后一位
if (i - 1 == 0 || !isChess(board, i - 1)){
if (!canWin(board ^ (1 << i) | (1 <<(i - 1)), length)){
reachLoseGame = true;
}
}
//右边两个棋子,并且第3位为空格 或者 是最后一位
if (i > 2 && isChess(board, i - 1) && isChess(board, i - 2)){
if (i - 3 == 0 || !isChess(board, i - 3)){
if (!canWin(board ^ (1 << i) | (1 << (i - 3)), length)){
reachLoseGame = true;
}
}
}
}
}
map.put(board, reachLoseGame);
return reachLoseGame;
}
}
