Grundy Number and Games

Impartial Games §

Impartial game คือเกมที่ผู้เล่นสองคนมีตาในการเล่นเป็นของตัวเองและสามารถ the available moves ไม่ขึ้นกับว่าตานั้นเป็นตาของใคร

หมากรุกไม่เป็น impartial game เพราะว่า the available moves จะดูจากว่าตานั้นเป็นของใคร ( หมากดำ/ขาว )

MEX (Minimum Excludant) §

MEX คือฟังชั่นที่เอาไว้หา ตัวเลขใดที่น้อยที่สุดที่ยังไม่มีในเซ็ตที่ $\ge 0$

Example §

$S=\{0,1,3,15,20\}$ $MEX(S)=2$

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

Grundy Numbers §

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

Example §

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

สมมติให้ $GrundyNumbersof10=G(10)$

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

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

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

เพราะฉะนั้น $G(0)=0$ $\to$ เพราะว่าถ้าตาเราเหลือ 0 เหรียญเราแพ้ $\to$ ไม่เหลือ 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) $\ge 0$)

Example 1 §

สมมติ $S$ = Set of all possible positions If $XOR(S)=0\to Result=Lose$ else $Result=Win$

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

• เอาเหรียญในกองมาหาร 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)=1$ หรือก็คือเราจะชนะ แล้วที่เราต้องทำคือทำยังไงก็ได้ให้ตาต่อไป $RESULT=0$