博弈組合入門

1、ACM程序設(shè)計杭州電子科技大學(xué) 劉春英 2022/9/192今天，你 了嗎？AC2022/9/193每周一星（10）：Lin2144 2022/9/194第十一講組合博弈入門（Simple Game Theory）2022/9/195導(dǎo)引游戲(1) 玩家：2人；(2) 道具：23張撲克牌；(3) 規(guī)則：游戲雙方輪流取牌；每人每次僅限于取1張、2張或3張牌；撲克牌取光，則游戲結(jié)束；最后取牌的一方為勝者。2022/9/196基本思路？請陳述自己的觀點2022/9/197第一部分簡單取子游戲（組合游戲的一種）2022/9/198什么是組合游戲有兩個玩家；游戲的操作狀態(tài)是一個有限的集合（比如：限定大小

2、的棋盤）；游戲雙方輪流操作；雙方的每次操作必須符合游戲規(guī)定；當(dāng)一方不能將游戲繼續(xù)進行的時候，游戲結(jié)束，同時，對方為獲勝方；無論如何操作，游戲總能在有限次操作后結(jié)束；2022/9/199概念:必敗點和必勝點(P點 & N點)必敗點(P點) :前一個選手(Previous player)將取勝的位置稱為必敗點。 必勝點(N點) :下一個選手(Next player)將取勝的位置稱為必勝點。 2022/9/1910必敗(必勝)點屬性(1) 所有終結(jié)點是必敗點（P點）；(2) 從任何必勝點（N點）操作，至少有一種方法可以進入必敗點（P點）；(3)無論如何操作， 從必敗點（P點）都只能進入必勝點（N點）

3、.2022/9/1911取子游戲算法實現(xiàn) 步驟1:將所有終結(jié)位置標(biāo)記為必敗點（P點）；步驟2: 將所有一步操作能進入必敗點（P點）的位置標(biāo)記為必勝點（N點）步驟3:如果從某個點開始的所有一步操作都只能進入必勝點（N點） ，則將該點標(biāo)記為必敗點（P點） ；步驟4: 如果在步驟3未能找到新的必?。≒點），則算法終止；否則，返回到步驟2。2022/9/1912課內(nèi)練習(xí):Subtraction Games:subtraction set S = 1, 3, 4x : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14Pos: P N P N N N N P N P N N N N P

4、2022/9/1913實戰(zhàn)練習(xí)kikis game 2022/9/1914第二部分Nim游戲2022/9/1915Nim游戲簡介有兩個玩家；有三堆撲克牌（比如：可以分別是 5，7，9張）；游戲雙方輪流操作；玩家的每次操作是選擇其中某一堆牌，然后從中取走任意張；最后一次取牌的一方為獲勝方；2022/9/19162022/9/1917初步分析(0, 0, 0) (0, 0, x) (0, 1, 1) (0, k, k) P-position P-position P-position N-position (14, 35, 46) ? 2022/9/1918引入概念：Nim-Sum定義: 假設(shè) (

5、xm x0)2 和(ym y0)2 的nim-sum是(zm z0)2,則我們表示成 (xm x0)2 (ym y0)2 = (zm z0)2, 這里，zk = xk + yk (mod 2)（k=0m）.2022/9/1919定理一： 對于nim游戲的某個位置(x1,x2,x3),當(dāng)且僅當(dāng)它各部分的nim-sum等于0時（即x1x2x3=0），則當(dāng)前位于必敗點。定理一也適用于更多堆的情況2022/9/1920定理一的證明 2022/9/1921思考（1）：有了定理一，如果判斷某個游戲的先手是輸還是贏？2022/9/1922思考（2）：對于必勝點，如何判斷有幾種可行的操作方案？2022/9/1

6、923實例分析(HDOJ_1850)Being a Good Boy in Spring Festival 2022/9/1924第三部分Graph Games &Sprague-Grundy Function2022/9/1925What is the graph game ?(1) Player I moves first, starting at x0.(2) Players alternate moves.(3) At position x, the player whose turn it is to move chooses a position y F(x).(4) The pl

7、ayer who is confronted with a terminal position at his turn, and thus cannot move, loses.2022/9/1926Example about graph game:0,0,01,0,00,0,10,1,05,7,92,0,02022/9/1927The Sprague-Grundy Function.Definition: The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-n

8、egative integer values, such thatg(x) =minn 0 : ng(y) for y F(x). (1)In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x.g(x) =mexg(y) : y F(x). (2)2022/9/1928Use of the Sprague-Grundy Function:P-positions: Positions x for which g(x) = 0 N

9、-positions: Positions x for which g(x) 0 2022/9/1929Exercise:What is the SG-value of the subtraction game with subtraction set S = 1, 2, 3?x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14. . .g(x) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2. . .2022/9/1930Question:What can the S-G value describe?2022/9/1931Part 4:Sums of Com

10、binatorial Games2022/9/1932What is so-called “Sums of Combinatorial Games”?2022/9/1933Theorem 2.If gi is the Sprague-Grundy function of Gi , i = 1, . . . , n, then G = G1 + + Gn has Sprague-Grundy function g(x1, . . . , xn) = g1(x1) gn(xn).2022/9/1934Applications:Sums of three Subtraction Games.In t

11、he first game: m = 3 and the pile has 9 chips. In the second: m = 5 and the pile has 10 chips. In the third:m = 7 and the pile has 14c hips.g(9, 10, 14) =?2022/9/1935附:參考源碼(HDOJ-1536)#include#include#includeusing namespace std;int k,a100,f10001;int mex(int p) int i,t; bool g101=0; for(i=0;ik;i+) t=p

12、-ai; if(t0) break; if(ft=-1) ft=mex(t); gft=1; for(i=0;i+) if(!gi) return i; int main() int n,i,m,t,s; while(scanf(%d,&k),k) for(i=0;ik;i+) scanf(%d,&ai); sort(a,a+k); memset(f,-1,sizeof(f); f0=0; scanf(%d,&n); while(n-) scanf(%d,&m); s=0; while(m-) scanf(%d,&t); if(ft=-1) ft=mex(t); s=sft; if(s=0) printf(L); else printf(W); printf(n); 2022/9/1936課后練習(xí)2008ACM ProgrammingExercise(12)_博弈入門 1517 A Multiplication Game 1079 Calendar Game 2147 ki