<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Wythoff Game - 威佐夫博弈 -------- #### 問題 $$ A $$和$$ B $$兩人輪流從蘋果和梨子中取出水果，兩堆水果的數量分別為$$ p $$（蘋果）和$$ k $$（梨子）且$$ p \ne k $$。 每人每次既可以從一堆水果中取任意個水果（至少取$$ 1 $$個），也可以從兩堆水果中同時取任意個水果（至少取$$ 1 $$個），取的數量沒有上限，最后一個把水果取光的人獲勝。 給定$$ p, k $$，當我方先手，我方和對方都是高手（在能贏的情況下一定能贏），求我方是否能贏。 #### 解法 $$ (1) $$ 當我方面臨$$ p = 2, k = 1 $$局勢時，我方必輸，因為我方無法一次把兩堆物品取光，且必然留給對方局勢$$ (p, p) $$（$$ p \ge 0 $$），對方可以一次將兩堆物品取光； $$ (2) $$ 當我方面臨$$ p = 3, k = 1 $$局勢時，我方取$$ p = 1 $$時，留給對方$$ p = 2, k = 1 $$局勢，我方才贏； $$ (3) $$ 當我方面臨$$ p = 3, k = 2 $$局勢時，我方取$$ p = 1, k = 1 $$時，留給對方$$ p = 2, k = 1 $$局勢，我方必贏。對于所有的$$ p = k + 1, 2 \le k $$局勢，我方從兩堆物品中同時取$$ k - 1 $$時必贏。 $$ \cdots $$ 把$$ (2, 1), (3, 1) $$這樣的局勢看作棋盤上的坐標時，很像“皇后的棋步”（Queen's Move）。  上圖中$$ (1,1), (2,2), (3,2), (2,3), (3,3), (3,4), (4,3) \dots $$這些在虛線上的坐標，當我方面對這樣的局勢時必贏（稱這樣的局勢為安全局勢）。棋盤上關鍵的位置是紅色的$$ (1,2), (2,1), (3,5), (5,3) \dots $$，這些是安全局勢的邊界點，當我方面臨邊界點時必輸。 根據數學研究，這些邊界實際是兩條直線：  在二維坐標系上這兩條直線的坐標計算方式是 $$ \phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887\dots \\ \frac{y}{x} = \phi \\ \frac{x}{y} = \phi $$ 其中$$ \phi $$常被稱為“黃金比例”（Golden Ratio），也稱“黃金分割”。黃金分割常數是一個無理數，任何正整數乘以或除以它，結果都不是整數。本問題中給定一個坐標時可以算出另一個黃金分割點的坐標，再向坐標系的外圍方向取整，可以得到兩條直線上安全局勢的邊界點。我們將二維坐標系上半邊黃金分割線稱為$$ upper $$，黃金分割線稱為$$ lower $$。 在下圖中，當給定點$$ x, y $$，可以算出其與$$ x, y $$軸平行的直線與兩條黃金分割線的四個交點$$ a, b, c, d $$。  $$ x = 2.5, y_{c} = \lceil x \times \phi \rceil \approx \lceil 2.5 \times 1.618 \rceil \approx \lceil 4.045 \rceil = 5 \\ x = 2.5, y_{d} = \lfloor x \div \phi \rfloor \approx \lfloor 2.5 \div 1.618 \rfloor \approx \lfloor 1.545 \rfloor = 1 \\ y = 1.8, x_{b} = \lceil y \times \phi \rceil \approx \lceil 1.8 \times 1.618 \rceil \approx \lceil 2.912 \rceil = 3 \\ y = 1.8, x_{a} = \lfloor y \div \phi \rfloor \approx \lfloor 1.8 \div 1.618 \rfloor \approx \lfloor 1.112 \rfloor = 1 \\ $$ 若點$$ x,y $$滿足$$ x_{a} \lt x \lt x_{b}, y_{d} \lt y \lt y_{c} $$，則該點為安全局勢，即處于黃金分割線區域內的一方必贏。 $$ (1) $$ 當$$ (p, k) $$處于黃金分割區域，我方必贏； $$ (2) $$ 當$$ (p, k) $$處于黃金分割區域的邊界點，我方必輸，因為無論我方如何取物品，對方下一輪都會進入黃金區域； $$ (3) $$ 當$$ (p, k) $$處于其他區域時，我方需要取一個合適的數，將對方下一輪置于黃金分割區域的邊界點，我方才贏； 當我方和對方都是高手時，只需一次計算即可分出勝負。該算法的時間復雜度為$$ O(1) $$。 -------- #### Wythoff’s Game * http://math.rice.edu/~michael/teaching/2012Fall/Wythoff.pdf -------- #### 源碼 [WythoffGame.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/WythoffGame.h) [WythoffGame.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/WythoffGame.cpp) #### 測試 [WythoffGameTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/WythoffGameTest.cpp)