Solving Games

Last week at Trustious, Islam gave a Talk about Games! But wait, its NOT your typical card games, board games or even video games. Islam’s talk was about impartial games with perfect information and a win-lose outcome. Self- explanatory right?

Let’s get to know these kinds of games a little bit more. “Perfect information” means all you need to know about how to win is in front of you, there is no chance, no hidden cards or anything of the sort. In “impartial games” the allowed moves for each player are the same and depend only on the current position. Basically what differentiates the 2 players is who goes first. This is what usually determines the winner and the loser, no draws hence the “win-lose outcome”.

Islam (left) playing a variation of Nim with Akram (right).

Nim is perhaps the most popular impartial perfect information game. Here’s a variation of Nim that Islam played with a volunteer (Akram) during the talk. Both players have access to a pile of stones. On a player’s turn, he has to take away 1, 2 or 3 stones from the pile. The loser is the one who cannot make any moves. In this case, the winner is one that takes the last stone(s) from the pile. Islam chose to setup a pile with 21 stones. Then he made his first move by taking 1 stone and giving the turn to Akram with 20 stones in the pile. Akram took away 3 stones and they continued playing until Islam was declared the winner in the end of the game! By the way, he didn’t cheat I was watching carefully :)

The winner was in fact declared before starting the game. With 21 stones in the pile, the one who goes first will always win, no matter what the other player does! In fact the only way for the first player to lose, is if and only if the number of stones in the pile was a multiple of 4. But, why? Let’s define the current position as the number of stones currently left in the pile. Then we can classify each position as either winning or losing. A losing position is one where you can only make moves that put your opponent in a winning position. While a winning position is one where you can make at least one move to put your opponent in a losing position. The clearest losing position is a pile with 0 stones. Positions 1, 2 and 3 are all winning positions since you can clear out the pile yourself and leave your opponent with 0 stones (a losing position). Position 4 is unfortunately losing! This is due to the lack of losing positions that you can put your opponent in. Given exactly 4 stones, all our allowed moves: taking 1 stone, 2 stones or 3 stones, put the opponent in a winning position, hence 4 is forcefully losing. And so on for 8, 12, 16 and so on. Islam was guilty of intentionally choosing 21 as the number of stones so that he can win and later explain to us how it happened :)

The talk was filled with other variations of Nim. Such as allowing moves of taking 1, 3, 4 stones, or instead playing with multiple piles in parallel. All variations that maintain the conditions mentioned above can in fact be solved with a simple algorithm to determine the inevitable winner. This is proved using the Sprague-Grundy Theorem which reduces each position to a Grundy Number. A thorough explanation of Nim, some of its variations, and proofs can be found in this paper. And for the problem solver inside you, here is an interesting tutorial with exercises from TopCoder.