<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Bash Game - 巴什博弈 -------- #### 問題 $$ A $$和$$ B $$兩人輪流從$$ n $$個物品中取出物品，每次取的物品數限定為$$ (1 - p) $$（至少取$$ 1 $$個，至多取$$ p $$個。$$ n, p $$都是正整數且$$ p \lt n $$，顯然若$$ p \ge n $$則第一個取的人一次就可以把所有物品取走從而獲勝）個，最后一個把物品取光的人獲勝。 給定$$ n $$和$$ p $$，當我方先手，我方和對方都是高手（在能贏的情況下一定能贏），求我方是否能贏。 巴什博弈還可以描述為：$$ A $$和$$ B $$兩人輪流向一個籃子中放入物品，籃子最多能放$$ n $$個物品。每次放的物品數量限定為$$ (1 - p) $$，最后一個把籃子填滿的人獲勝。 上面兩個問題其實是相同的，只是放和取的過程相反。本章中其他的博弈問題都可以像這樣用相反的過程進行顛倒。 #### 解法 若$$ n = p + 1 $$，$$ A $$取$$ (1 - p) $$個物品，剩下$$ (1 - p) $$個物品。下一次$$ B $$總能一次取光，$$ B $$獲勝。 介紹博弈論中的概念“局勢”，當一方做選擇時，剩余的物品數量為$$ x $$時，稱這一方面對的局勢為$$ (x) $$。對于$$ n = 50, p = 4 $$的情況： $$ (1) $$ 當我方面臨$$ (1 - 4) $$局勢時，我方必贏，因為我方可以將剩余物品都拿光； $$ (2) $$ 當我方面臨$$ (5) $$局勢時，我方必輸，因為我方取物品后，必然留給對方$$ (0 - 4) $$局勢，對方必贏； $$ (3) $$ 當我方面臨$$ (6 - 9) $$局勢時，我方必贏，因為我方可以留給對方$$ (5) $$局勢，對方必輸； $$ \cdots $$ 可以看出，當留給對方$$ p + 1 $$個物品時，下一輪對方必然會輸，因為對方必然取$$ (1 - p) $$個物品，留給我方$$ (1 - p) $$個物品。稱這樣的物品數量為必贏數量$$ w = p + 1 $$。 當我方取物品時面對$$ w $$的倍數個物品時，我方必輸，即$$ n \mod (p + 1) = 0 $$。否則對方必輸。 該算法的時間復雜度為$$ O(1) $$。 -------- #### 源碼 [BashGame.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/BashGame.h) [BashGame.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/BashGame.cpp) #### 測試 [BashGameTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/BashGameTest.cpp)