Grundy Number and Games
Impartial Games
Impartial game คือเกมที่ผู้เล่นสองคนมีตาในการเล่นเป็นของตัวเองและสามารถ the available moves ไม่ขึ้นกับว่าตานั้นเป็นตาของใคร
หมากรุกไม่เป็น impartial game เพราะว่า the available moves จะดูจากว่าตานั้นเป็นของใคร ( หมากดำ/ขาว )
MEX (Minimum Excludant)
MEX คือฟังชั่นที่เอาไว้หา ตัวเลขใดที่น้อยที่สุดที่ยังไม่มีในเซ็ตที่ ≥0\geq 0
Example
S={0,1,3,15,20}S = \{ 0, 1, 3, 15, 20 \} MEX(S)=2MEX(S) = 2
สมมติเรามอง S เป็น Set ของ moves ที่เราทำได้ในตาของเรา MEX(S)MEX(S) จะบอกเราว่า moves ที่เล็กที่สุดที่เราเล่นไม่ได้คืออะไร (เพราะมันหาเลขเล็กสุดที่ไม่ได้อยู่ใน S)
Grundy Numbers
Grundy Numbers=MEX(S); MEX(∅)=0Grundy\space Numbers = MEX(S); \space MEX(\varnothing)=0 โดยที่ SS คือ Set of game states ที่เป็นไปได้หลังจากการกระทำในตาของเรา
Example
สมมติเรามีเหรียญ 10 เหรียญ แล้วเราสามารถหยิบออกมาได้ทีละ 1≤c≤31 \leq c \leq 3 เหรียญโดยหยิบสลับกับผู้เล้นอีกคนคนละตา ตาไหนไม่สามารถหยิบเหรียญได้อีก (กรณีนี้คือ 0 เหรียญ) ผู้เล่นที่เล่นตานั้นแพ้
สมมติให้ Grundy Numbers of 10=G(10)Grundy\space Numbers\space of\space 10 = G(10)
G(10)→MEX({G(9),G(8),G(7)})G(10) \rightarrow MEX(\{ G(9), G(8), G(7) \})
อธิบาย สมมติตาเราที่กองมี 10 เหรียญ เพราะฉะนั้นเราสามารถหยิบได้ 1≤c≤31 \leq c \leq 3 เหรียญ →\rightarrow Game State ที่เกิดขึ้นได้คือเหลือ 9, 8, 7 เหรียญ (แล้วแต่ว่าจะหยิบเท่าไหร่) โดยจะเรียกเกมแบบนี้ว่า Nim Games (One Pile Nim Games ในกรณีนี้)
ขอเรียกเกมนี้ว่า 1-2-3-Nim
เพราะฉะนั้น G(0)=0G(0)=0 →\rightarrow เพราะว่าถ้าตาเราเหลือ 0 เหรียญเราแพ้ →\rightarrow ไม่เหลือ action ให้ทำ = ไม่มี Game state ต่อไป
| G(n) | MEX(S) | |
|---|---|---|
| G(1)G(1) | MEX({G(0)})=MEX(0)MEX(\{ G(0) \}) = MEX(0) | 1 |
| G(2)G(2) | MEX({G(0),G(1)})=MEX({0,1})MEX(\{ G(0), G(1) \}) = MEX(\{ 0, 1 \}) | 2 |
| G(3)G(3) | MEX({G(0),G(1),G(2)})=MEX({0,1,2})MEX(\{ G(0), G(1), G(2) \}) = MEX(\{ 0, 1, 2 \}) | 3 |
| G(4)G(4) | MEX({G(1),G(2),G(3)})=MEX({1,2,3})MEX(\{ G(1), G(2), G(3) \}) = MEX(\{ 1, 2, 3 \}) | 0 |
| G(5)G(5) | MEX({G(2),G(3),G(4)})=MEX({2,3,0})MEX(\{ G(2), G(3), G(4) \}) = MEX(\{ 2, 3, 0 \}) | 1 |
อาจจะงงว่าเอาไปทำอะไรได้ แต่เราสามารถเอา Grundy Numbers ไปเช็คได้ว่าใครจะชนะ Nim Games นั้นๆได้
อธิบาย จาก G(4)=0G(4) = 0 มันคือการบอกว่าถ้าตอนนี้ในกองมีเหรียญ 4 เหรียญ คนที่เล่นตานั่นจะแพ้
เราสามารถดูจาก Grundy number ได้ว่า คนที่เล่นในตาปัจจุบันมีเส้นทางไหนไป Winning State หรือไม่ สมมติว่า G(u)=2G(u) = 2 ก็คือบอกว่า จาก game state ปัจจุบัน (u) มีทางที่ทำให้ G(u+1) (state อื่นๆ u+1) = 0 หรือ 1 ได้ หรือก็คือ เราทำให้ G(u+1)=0G(u+1) = 0 ได้
แล้วการที่ G(u+1)=0G(u+1) = 0 ก็คือการบอกว่า ณ game state u+1 ไม่มี action แบบไหนเลยที่จะทำให้เราชนะ
Sprague-Grundy Theorem
Sprague–Grundy theorem บอกกับเราว่า ทุก impartial game ภายใต้กติกาการเล่นแบบปกติ (normal play convention) (แกล้งแพ้ไม่ได้ เดินให้แพ้ไม่ได้) สามารถเทียบเท่าได้กับเกมนิมที่มีกองเดียว (one pile Nim game)
และ
ถ้าผู้เล่นทั้งสองคนเล่นไม่เคยพลาดเลย (optimally) คนที่เล่นก่อนจะชนะถ้า G(Position in each sub-games at the beginning of the game) ≥0\geq 0)
Example 1
สมมติ SS = Set of all possible positions If XOR(S)=0→Result=LoseXOR(S) = 0 \rightarrow Result =Lose else Result=WinResult =Win
สมมติเรามีเหรียญ 4 กอง กองละ 4, 6, 8 และ 2 เหรียญ โดยเราสามารถออก action ได้สามแบบ
- เอาเหรียญในกองมาหาร 2 แล้วปัดลง
- เอาเหรียญในกองมาหาร 3 แล้วปัดลง
- เอาเหรียญในกองมาหาร 6 แล้วปัดลง หรือคือ FLOOR[2,3,6]FLOOR[2, 3, 6]
| G(N) | MEX(S) | |
|---|---|---|
| G(1) | MEX(G(0), G(0), G(0)) | 1 |
| G(2) | MEX(G(0), G(0), G(1)) | 2 |
| G(3) | MEX(G(1), G(0), G(0)) | 2 |
| G(4) | MEX(G(2), G(1), G(0)) | 3 |
| G(6) | MEX(G(1), G(2), G(3)) | 0 |
| G(8) | MEX(G(4), G(2), G(1)) | 0 |
เพราะฉะนั้นสมมติเราได้เล่นคนแรกแต่ละกองมี 4, 6, 8 และ 2 เหรียญ
RESULT=XOR(G(4),G(6),G(8),G(2))=XOR(3,0,0,2)=1RESULT = XOR(G(4), G(6), G(8), G(2)) = XOR(3, 0, 0, 2) = 1 หรือก็คือเราจะชนะ แล้วที่เราต้องทำคือทำยังไงก็ได้ให้ตาต่อไป RESULT=0RESULT = 0