Game Theory – NIM and Sprague-Grundy

Last Wednesday we were given a talk by Radu, one of the third year students at Queens’. His talk introduced us to some interesting and cool concepts in game theory – a topic that relates well to Computer Science, such as in problems where the optimal play must be taken.

Radu’s talk focused on NIM-style games. The aim of the game is to be the last player to be able to play a move. The image below shows an example – three piles of coins exist, and a each turn a play is allowed to take as many coins as they like, from a single pile (they must take at least one coin). IE, the player could take all the coins from pile one, and then it would be the opposing players turn.

Screenshot from 2016-01-26 12-09-24

Through the clever use of XORing the numbers, Radu went on to show that calculating and making the optimal play is very easy. Once a player has forced themselves into a winning state (where the XOR-Sum of all numbers is 0), as long as the player maintains the optimal play, they cannot lose.

Screenshot from 2016-01-26 12-16-34

Moving on from the NIM game, Radu went on to show (Via the Sprague-Grundy theorem) that many games can be reduced into a NIM game, and thus an optimal solution can be found. One such example is represented in the image above, the “Poison Chocolate Problem”, where a player can take any row(s) or column(s) in a single turn, but must not be the player to eat the poisoned block.