游戏理论算法：如何进行

Question

举一个例子：Permutation Game（interviewstreet.com）。我想知道我该如何处理这些问题。

P.S .:请不要发布完整的算法（因为这会破坏乐趣），只是几个指针。

Answer 1

我会设置一个小游戏，用小N和随机排列，然后画一个完整的α-β树 ...

http://en.wikipedia.org/wiki/Alpha-beta_pruning

的所有可能的行动

，然后工作底部在每个点上为每个玩家提供最佳选择。

然后从那里一般化，一旦你看到模式。

在博弈论的术语，你需要使用后向归纳找到完美子博弈均衡。

Answer 2

笔和纸

使用笔和纸，请确保您了解游戏的规则完全相同，然后想为游戏中所有可能的策略。

对于这样一个相对简单的问题，从赢得比赛的时候回想一下，一次展开一步，并确保进行该步骤的玩家不能做出更好的步骤，这是最优性要求。

对于更复杂的问题，请阅读关于博弈论的维基百科。

Answer 3

N比较小。在每个回合中，每个号码都有两种可能性：删除该号码或不删除该号码。尝试两种可能性，为每个测试用例产生一个O(N*2^N)算法。在实践中，这个数字会比较低，因为游戏通常会在所有数字被移除之前结束，并且您可以经常缩短搜索时间。

所以你想要一个回溯功能，尝试删除数字的所有可能性，如果Alice获胜，则返回1，如果Bob获胜，则返回2。在深度k（第一深度是k = 0），如果k % 2 = 0，则轮到Alice了。如果所有即时递归调用（深度为k + 1）返回1，她将​​获胜。如果他们中的至少一人返回2，那么她输了，因为至少有一种方式让鲍勃赢。

例如在1 3 2运行：

k = 0 - Alice removes 1: 
    k = 1 - Bob removes 3 => Bob wins because only 2 remains 
      - Bob removes 2 => Bob wins because only 3 remains (note: this step 
      is not needed, as Bob already proved he can win at this k = 1) 
     - Alice removes 3 => Alice wins because 1 2 is increasing 
     - Alice removes 2 => Alice wins because 1 3 is increasing 

于是，爱丽丝肯定有一个成功的策略（当发挥最佳），如果她删除3或先动2，因为这两个的递归分支永不放弃鲍勃作为赢家。

实施例上5 3 2 1 4（部分运行）运行：

k = 0 - Alice removes 5 
    k = 1 - Bob removes 3 
     k = 2 - Alice removes 2 => 1 4 => Alice wins 
    k = 1 - Bob removes 2 
     k = 2 - Alice removes 3 => 1 4 => Alice wins 
    k = 1 - Bob removes 1 
     k = 2 - Alice removes 3 => 2 4 => Alice wins 
    k = 1 - Bob removes 4 
     k = 2 - Alice removes 3 
      k = 3 - Whatever Bob removes, he wins 
     k = 2 - Alice removes 2 
      k = 3 - Whatever Bob removes, he wins 
     k = 2 - Alice removes 1 
      k = 3 - Whatever Bob removes, he wins 
    ... 

正如你可以看到，至少有一个为方式Bob落得通过去除5如果Alice开始获胜。如果你为她的其他可能性做同样的事情，你可能会得到相同的结果。因此，如果他打得最好，他肯定会赢。