Grundy Number and Games

5 min read

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 \}$ $M E X (S) = 2$

สมมติเรามอง S เป็น Set ของ moves ที่เราทำได้ในตาของเรา $M E X (S)$ จะบอกเราว่า moves ที่เล็กที่สุดที่เราเล่นไม่ได้คืออะไร (เพราะมันหาเลขเล็กสุดที่ไม่ได้อยู่ใน S)

Grundy Numbers

$MEX(∅)=0Grundy\space Numbers = MEX(S); \space MEX(\varnothing)=0$ โดยที่ $S$ คือ Set of game states ที่เป็นไปได้หลังจากการกระทำในตาของเรา

Example

สมมติเรามีเหรียญ 10 เหรียญ แล้วเราสามารถหยิบออกมาได้ทีละ $\leq c \leq 3$ เหรียญโดยหยิบสลับกับผู้เล้นอีกคนคนละตา ตาไหนไม่สามารถหยิบเหรียญได้อีก (กรณีนี้คือ 0 เหรียญ) ผู้เล่นที่เล่นตานั้นแพ้

สมมติให้ $10=G(10)Grundy\space Numbers\space of\space 10 = G(10)$

$\rightarrow MEX(\{ G(9), G(8), G(7) \})$

อธิบาย สมมติตาเราที่กองมี 10 เหรียญ เพราะฉะนั้นเราสามารถหยิบได้ $\leq c \leq 3$ เหรียญ $→\rightarrow$ Game State ที่เกิดขึ้นได้คือเหลือ 9, 8, 7 เหรียญ (แล้วแต่ว่าจะหยิบเท่าไหร่) โดยจะเรียกเกมแบบนี้ว่า Nim Games (One Pile Nim Games ในกรณีนี้)

ขอเรียกเกมนี้ว่า 1-2-3-Nim

เพราะฉะนั้น $G (0) = 0$ $→\rightarrow$ เพราะว่าถ้าตาเราเหลือ 0 เหรียญเราแพ้ $→\rightarrow$ ไม่เหลือ action ให้ทำ = ไม่มี Game state ต่อไป

G(n)	MEX(S)
$G (1)$	$MEX(\{ G(0) \}) = MEX(0)$	1
$G (2)$	$MEX(\{ G(0), G(1) \}) = MEX(\{ 0, 1 \})$	2
$G (3)$	$MEX(\{ G(0), G(1), G(2) \}) = MEX(\{ 0, 1, 2 \})$	3
$G (4)$	$MEX(\{ G(1), G(2), G(3) \}) = MEX(\{ 1, 2, 3 \})$	0
$G (5)$	$MEX(\{ G(2), G(3), G(4) \}) = MEX(\{ 2, 3, 0 \})$	1

อาจจะงงว่าเอาไปทำอะไรได้ แต่เราสามารถเอา Grundy Numbers ไปเช็คได้ว่าใครจะชนะ Nim Games นั้นๆได้

อธิบาย จาก $G (4) = 0$ มันคือการบอกว่าถ้าตอนนี้ในกองมีเหรียญ 4 เหรียญ คนที่เล่นตานั่นจะแพ้

Intuitive

เราสามารถดูจาก Grundy number ได้ว่า คนที่เล่นในตาปัจจุบันมีเส้นทางไหนไป Winning State หรือไม่ สมมติว่า $G (u) = 2$ ก็คือบอกว่า จาก game state ปัจจุบัน (u) มีทางที่ทำให้ G(u+1) (state อื่นๆ u+1) = 0 หรือ 1 ได้ หรือก็คือ เราทำให้ $G (u + 1) = 0$ ได้

แล้วการที่ $G (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

สมมติ $S$ = Set of all possible positions If $\rightarrow Result =Lose$ else $R es u l t = W in$

สมมติเรามีเหรียญ 4 กอง กองละ 4, 6, 8 และ 2 เหรียญ โดยเราสามารถออก action ได้สามแบบ

เอาเหรียญในกองมาหาร 2 แล้วปัดลง
เอาเหรียญในกองมาหาร 3 แล้วปัดลง
เอาเหรียญในกองมาหาร 6 แล้วปัดลง หรือคือ $F L O O R [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 เหรียญ

$R E S U L T = X O R (G (4), G (6), G (8), G (2)) = X O R (3, 0, 0, 2) = 1$ หรือก็คือเราจะชนะ แล้วที่เราต้องทำคือทำยังไงก็ได้ให้ตาต่อไป $R E S U L T = 0$

Impartial Games #

MEX (Minimum Excludant) #

Example #

Grundy Numbers #

Example #

Sprague-Grundy Theorem #

Example 1 #

Impartial Games

MEX (Minimum Excludant)

Example

Grundy Numbers

Example

Sprague-Grundy Theorem

Example 1