Computer Science 5th Years Master's Thesis Presentation
— 4:30pm
Location:
In Person
-
Traffic21 Classroom, Gates Hillman 6501
Speaker:
MIRABEL HU
,
Masters Student, Computer Science Department, Carnegie Mellon University
Exploring Variations of Wythoff Nim
We investigate two modifications to the traditional rules of Wythoff Nim, a combinatorial game. In Wythoff Nim, players take turns removing stones from a pair of piles. In each turn, a player chooses to either (1) take any number of stones from one pile or (2) take an equal number from both. The player removing the last stone wins. A seminal result of Wythoff states that at any point in the game, the current player is in a P-position — that is, guaranteed to lose assuming the other player plays optimally — if and only if the pair of pile sizes is of the form (nø, nø^2) for some natural number n, where ø = 1.618… represents the golden ratio.
This thesis introduces a variant of Wythoff Nim, which we call W(a,b), characterized by positive integers a and b, where players' moves are constrained to either removing a multiple of a from the first pile, a multiple of b from the second, or an equal number from both. We prove that the P-positions of this variant also follow sloping “beams”, but with slopes determined by a and b. Additionally, we explore the consequences of modifying Wythoff's Nim by introducing additional fixed winning and losing positions. Our empirical observations suggest a convergence of the P-positions in the long run, resembling those of the regular Wythoff game. Together, these results shed light on the applicability of Wythoff's theory to variants of his original game.
Thesis Committee:
Danny Sleator (Advisor)
Klaus Sutner