博弈組合入門(mén)

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

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

3、.2022/9/1911取子游戲算法實(shí)現(xiàn) 步驟1:將所有終結(jié)位置標(biāo)記為必?cái)↑c(diǎn)（P點(diǎn)）；步驟2: 將所有一步操作能進(jìn)入必?cái)↑c(diǎn)（P點(diǎn)）的位置標(biāo)記為必勝點(diǎn)（N點(diǎn)）步驟3:如果從某個(gè)點(diǎn)開(kāi)始的所有一步操作都只能進(jìn)入必勝點(diǎn)（N點(diǎn)） ，則將該點(diǎn)標(biāo)記為必?cái)↑c(diǎn)（P點(diǎn)） ；步驟4: 如果在步驟3未能找到新的必?cái)。≒點(diǎn)），則算法終止；否則，返回到步驟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實(shí)戰(zhàn)練習(xí)kikis game 2022/9/1914第二部分Nim游戲2022/9/1915Nim游戲簡(jiǎn)介有兩個(gè)玩家；有三堆撲克牌（比如：可以分別是 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定理一： 對(duì)于nim游戲的某個(gè)位置(x1,x2,x3),當(dāng)且僅當(dāng)它各部分的nim-sum等于0時(shí)（即x1x2x3=0），則當(dāng)前位于必?cái)↑c(diǎn)。定理一也適用于更多堆的情況2022/9/1920定理一的證明 2022/9/1921思考（1）：有了定理一，如果判斷某個(gè)游戲的先手是輸還是贏？2022/9/1922思考（2）：對(duì)于必勝點(diǎn)，如何判斷有幾種可行的操作方案？2022/9/1

6、923實(shí)例分析(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)_博弈入門(mén) 1517 A Multiplication Game 1079 Calendar Game 2147 ki