组合游戏
組合游戲的特點
???(1)兩個玩家
???(2)游戲的操作狀態是一個有限的集合
???(3)游戲的雙方輪流操作
???(4)雙方每次操作必須符合游戲規定
???(5)當一方不能將游戲繼續進行的時候，游戲結束，同時對方獲勝
???(6)無論如何操作，游戲總能在有限次操作后結束
?
必敗點(P點)與必勝點(N點)
???必敗點：前一個選手將取勝的位置稱為必敗點。
???必勝點：下一個選手將取勝的位置稱為必勝點。
?
必敗點與必勝點的性質
??（1）所有終結點是必敗點
??（2）從任何必勝點操作，至少有一種方法可以進入必敗點
??（3）無論如何操作，從必敗點都只能進入必勝點
?
?
博弈典例
???1.Regional??2006?BeiJing
?
???問題描述：David玩一個石子游戲，游戲中，有n堆石子，編號為0,1,2,...,n-1。兩名玩家輪流取石子，每一輪游戲，每名玩家取3堆石子i,j,k，i<j<k，且至少有一枚石子在第i堆中，從i中取出一枚石子，并向j，k中各放一枚石子，如果j=k，則向k中放2顆石子，最先不能取石子的人輸。
?
??此游戲中的新操作：拿走一個非0的石堆，并放入2個規模小于它的石堆(可以為0)
?
?
2.IPSC??2003??Got?Root？
???Alice和Bob在一個無向圖上玩伐木游戲，無向圖有唯一的根，兩人輪流從中截取一條邊，將與根不相連的部分拋棄，這樣，最先不能操作的人輸。對于給定的無向圖，Alice先行，兩個人都按照最優策略操作，輸出勝者的名字。
?
思路：圖轉化為樹-----樹轉化為鏈-----分別求出SG值，就是Nim博弈了，最后異或一下即可。
總結
- 上一篇： Java常见知识点
- 下一篇： 确定最小的正整数n，使得n！的结尾恰好有