威佐夫（Wythoff）博弈

问题模型

Wythoff博弈：有两堆石子，由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。问现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

解题思路

动态规划

比较容易想到直接用博弈论的必败、必胜态进行动态规划：

设两堆石子数量为a和b，给定状态f，若先取者必胜令f(a,b)=1，否则先取者必败令f(a,b)=0，其中a，b都不小于0，易知f(a,b)=f(b,a)，所以这里总取b大于等于a。

状态转移方程：

        f(a,b)=1，若存在k使f(a-k,b)，f(a,b-k)或f(a-k,b-k)等于0；

        f(a,b)=0，若不存在k使f(a-k,b)，f(a,b-k)或f(a-k,b-k)等于0；

动态规划的时间复杂度为O(N*M)，其中N，M为两堆石子的数量。

公式

其实这个博弈问题的必败态是有规律可循的，前几个必败态的序列为

(0,0)、(1, 2)、(3, 5)、(4, 7)、（6, 10）、（8，13）、（9，15）、（11，18）、（12，20）

比较难看出来序列(a[k]，b[k])规律为

      a[k]=k(1+sqrt(5))/2，

      b[k]=a[k]+k

公式说明：

性质1：一个状态是必败态，当且仅当它的所有后续状态是必胜态；而一个状态是必胜态，只要它的后继状态有一个以上是必败态即可。

性质2：在所有必败态中，每个数字恰巧出现一次，根据在坐标轴中由已知必败态递归搜索由其推导出的必胜态，在剩余状态中继续选取必败态，如此循环。

性质3：在前面列出的一系列必败态可以看出，任一必败态中第一个数恰好是前面必败态中没有出现过的最小正整数。

性质4：第k个必败态(a[k],b[k])有b[k]=a[k]+k。k=0，1，2，……，用数学归纳法推导

Betty定理：如果存在正无理数 A, B 满足 1/A + 1/B = 1，那么集合 P = { [At], t ∈ Z+}、Q = { [Bt], t ∈ Z+} 恰为集合 Z+ 的一个划分，即：P ∪ Q = Z+，P ∩ Q = ø。其中[]为向下取整操作。

考虑到 Betty 定理中“恰为 Z+ 的划分”这一说，这意味着，Z+ 中的每个数都恰好出现一次，这与上述必败态序列的性质十分吻合。于是我们猜想每一个必败态第一列的数满足 [Φi] 的形式。于是我们得到每一个必败态第二列的数为 [Φi] + i = [Φi + i] = [(Φ + 1)i]。

我们的目的是要让 Z+ 中每个数都在这个矩阵中出现，于是考虑到 Betty 定理的条件，Φ 和 (Φ + 1) 应满足 1/Φ + 1/(Φ + 1) = 1。可以解得 Φ = (sqrt(5) + 1)/2。