HackerRank Game Theory Contest

On 2016/05/19 at 19:36

Recently, I was trying to improve my problem solving skills, so I started practicing algorithm problems on Codeforces, HackerRank ...etc. The Game Theory contest held by HackerRank is quite interesting. This is a great resource to learn combinatorial game theory step by step. Here I will write down the ideas of game theory I learned in the contest.

The most interesting fact I learned is the Sprague–Grundy theorem stating that every impartial game can be transformed into a Nim Game by assigning every position in the game with a nimber (also called Grundy numbers).

Nim Game and Misere Nim are the two basic problems for understanding and practicing solving Nim Game.

Nimble Game can be solved by some observations and transform into classic Nim Game easily. Poker Nim teaches you adding does not effect the result because your opponent can counter it by reversing your move.

Chessboard Game, Again! is a very good problem for me to understand how to assign the Grundy number to any impartial game. For every position in the chessboard, we can assign its grundy number by checking the its neighbors' grundy value first. The grundy number of its neighbors can be thought as a position of stones in this pile after I make a move. The position with more stones than current position will not be considered because Poker Nim already teaches you adding does not effect the result. So we assign the grundy number to be the smallest non-negative value that does not contain in its neighbors' grundy value.