algorithm - 博弈论算法：如何进行

Question

举个例子：排列游戏（interviewstreet.com）。我想知道如何处理这些问题。

PS：请不要发布完整的算法（因为这会破坏乐趣），只是一些指示。

Answer 1

我会设置一个带有小 N 和随机排列的小游戏，然后绘制一个完整的Alpha-Beta 树...

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

所有可能的移动，然后自下而上地为每个玩家在每一点做出最佳选择。

一旦你看到模式，然后从那里概括。

在博弈论术语中，您需要使用反向归纳来找到子博弈完美平衡。

Answer 2

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

因此，您需要一个回溯函数，该函数尝试删除数字的所有可能性，并1在 Alice 获胜和2Bob 获胜时返回。在深度k（第一个深度是k = 0），如果k % 2 = 0，那么轮到爱丽丝了。如果所有直接递归调用（具有 depth k + 1）返回，她就赢了1。如果其中至少有一个返回2，那么她就输了，因为 Bob 至少有一种获胜方式。

示例运行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因此，如果 Alice 移除或2在第一步中，Alice 肯定有一个获胜策略（当两者都发挥最佳时） ，因为这两者的递归分支永远不会让 Bob 成为获胜者。

示例运行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如果Alice从删除5. 如果你对她的其他可能性做同样的事情，你可能会得到同样的结果。因此，Bob如果他发挥最佳，谁肯定会赢。

Answer 3

笔和纸

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

对于像这样一个相对简单的问题，从赢得比赛的那一刻开始向后思考，一次展开一步，并确保迈出这一步的玩家不可能迈出更好的一步，这就是最优性要求。

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