算法学习---一个博弈问题

○●●○●●○●●○
●○○●○●●○●
○○○○
●●●○●●●
●

..比如说，如果你先走的话，你可以把第四行的第三个石子拿走，按规定第四行将会只剩下前面两个石子：

 

○●●○●●○●●○

●○○●○●●○●

○○○○

●●

●

 

现在轮到我走了。我可以拿走第二行倒数第二个石子，于是整个棋局变成了这样：

 

○●●○●●○●●○

●○○●○●●

○○○○

●●

●

 

现在，假如说你拿走了第二行中的第一个石子（于是第二行就没了），那么我就赢定了。我可以拿走第一行中的第一个石子，从而让整个棋局只剩下后面三行：

 

○○○○

●●

●
 

要求给出一种最合理的走法。


如果是残局
○○○○
●● 
●
把每个白色石子记作 +1 ，把每个黑色石子记作 -1 。于是 ○○○○ + ●● + ● = 4 – 2 – 1 = 1 ，结果是一个正数（记这个结果为特征值），这就表明该局面下我将必胜，即使此时轮到我先走。

你会发现上面的说法很有道理 如果棋局是这样

○○
●●●●
 
○○ + ●●●● = 2 – 4 = -2 ，是一个负数，这就意味着不管谁先走，你都能必胜，

如果是

○○
●●

如果我先走你后走，你就赢定了；如果你先走我后走，我就赢定了。因为 和为0。


所以正确的走法：只需要走特征值最大的就可以了。

博客原文http://www.matrix67.com/blog/archives/6333