April 06, 2004
pearls before swine 3
Got this link from a coworker.
Play it for a while and you learn to hate Juan. I realized quickly that it's not trivial to find a winning strategy.
I eventually stumbled upon the concept of game states, winning states and losing states. For one row or two rows it's straightforward to prove by induction which states are winning states. For one-row games you should modify the game slightly to make it more interesting: have a row of n stones and allow each player to take for example 1, 2 or 3 stones. What is the winning strategy ? What have all winning positions in common ? (Depends on n).
But even after my coworker gave me a hint saying "binary representation" I couldn't come up with a property that characterizes winning states for games with more than two rows.
Well, after another hint telling me that this game is also known as Nim I found the solution on the web: It falls into the domain of impartial combinatorial games and these two papers give a pretty good description of the theory behind it:
Thomas S. Ferguson: Game Theory
Harold Reiter: Games and Representations
Posted by Uwe Hoffmann at April 6, 2004 10:26 PM