<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Nim Game - 尼姆博弈 -------- #### 問題 $$ A $$和$$ B $$兩人輪流從$$ n $$堆物品中取出一些物品，$$ n $$堆物品的數量分別為$$ [ s_{1}, s_{2}, s_{3} \dots s_{n} ] $$（所有物品數量都是正整數）。 每人每次從一堆物品中至少取$$ 1 $$個，多則不限，最后取光所有物品的人獲勝。 給定$$ n $$和$$ [ s_{1}, s_{2}, s_{3} \dots s_{n} ] $$，當我方先手，我方和對方都是高手（在能贏的情況下一定能贏），求我方是否能贏。 #### 解法 $$ (1) $$ 當我方面臨$$ [0, 7, 0] $$局勢（有$$ 1 $$堆物品）時，我方必贏，因為我方可以一次把剩下一組的物品取光； $$ (2) $$ 當我方面臨$$ [0, 1, 1, 0, 0] $$局勢（有$$ 2 $$堆物品且均剩$$ 1 $$個）時，我方必輸，因為我方必然留給對方只剩$$ 1 $$堆物品的局勢； $$ (3) $$ 當我方面臨$$ [0, 1, 1, 1, 0] $$局勢（有$$ 3 $$堆物品且均剩$$ 1 $$個）時，我方必贏，因為我方必然留給對方只剩$$ 2 $$堆物品且均剩$$ 1 $$個的局勢； $$ (4) $$ 當我方面臨$$ [3, 4, 5] $$局勢時，暫時無法看出我方是否必贏； $$ \cdots $$ 本問題背后的數學模型叫$$ Nim Sum $$，堆數組大小的二進制和，上面$$ 5 $$個局勢可以轉化為： $$ \begin{matrix} s_{1} = 0_{10} = 000_{2} \\ s_{2} = 7_{10} = 111_{2} \\ s_{3} = 0_{10} = 000_{2} \\ nim_{1} = 0 \bigoplus 7 \bigoplus 0 = 1 \end{matrix} $$ $$ \begin{matrix} s_{1} = 0_{10} = 000_{2} \\ s_{2} = 1_{10} = 001_{2} \\ s_{3} = 1_{10} = 001_{2} \\ s_{4} = 0_{10} = 000_{2} \\ s_{5} = 0_{10} = 000_{2} \\ nim_{2} = 0 \bigoplus 1 \bigoplus 1 \bigoplus 0 \bigoplus 0 = 0 \end{matrix} $$ $$ \begin{matrix} s_{1} = 0_{10} = 000_{2} \\ s_{2} = 1_{10} = 001_{2} \\ s_{3} = 1_{10} = 001_{2} \\ s_{4} = 1_{10} = 001_{2} \\ s_{5} = 0_{10} = 000_{2} \\ nim_{3} = 0 \bigoplus 1 \bigoplus 1 \bigoplus 1 \bigoplus 0 = 1 \end{matrix} $$ $$ \begin{matrix} s_{1} = 3_{10} = 011_{2} \\ s_{2} = 4_{10} = 100_{2} \\ s_{3} = 5_{10} = 101_{2} \\ nim_{4} = 3 \bigoplus 4 \bigoplus 5 = 2 \end{matrix} $$ 可以看出，當我方面臨$$ \bigoplus_{i=1}^{n} s_{i} = s_{1} \bigoplus s_{2} \bigoplus \cdots \bigoplus s_{n} \ne 0 $$局勢時必贏，否則必輸。 該算法時間復雜度為$$ O(n) $$。 -------- #### Nim Sum * http://www.math.ucla.edu/~radko/circles/lib/data/Handout-141-156.pdf * https://plus.maths.org/content/play-win-nim * http://samidavies.com/post/2016/03/09/games-intro.html * https://paradise.caltech.edu/ist4/lectures/Bouton1901.pdf * https://pdfs.semanticscholar.org/8ac7/c5d8d56847daafa73ad85ae2ad6f47149096.pdf * https://www.researchgate.net/publication/220343088_The_game_of_End-Nim -------- #### 源碼 [NimGame.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/NimGame.h) [NimGame.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/NimGame.cpp) #### 測試 [NimGameTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/GameTheory/NimGameTest.cpp)