[Greg] has been fascinated with the Game of NIM ever since he was a freshman in highschool. Recently he remembered it and decided to try his hand at making an AI version to play, written using Visual Basic.

If you’re not familiar with the game, it’s fairly simple. Each row of lights represents a certain type of object. The players make take as many objects from any one row, per turn. The player with the last object loses.

Now, as you can imagine, writing an AI into a game can be a rather challenging ordeal. [Greg’s] first attempt was to use a memory structure that captures every possible move. There’s only 15 moves, and 1 to 7 lights, and the options decrease as the game goes on so… That can’t be too bad, right? Upon running his freshly written code he got an out-of-memory error. Not just any out-of-memory error either, over an Exabyte of memory was needed! Whoops.

He eventually figured the proper code out, and what resulted in game play was a very interesting experience. You see, the computer learns from each game played. At first, it’s like playing a young child — easy to trick and beat. But as the games progressed, the computer picked up his patterns and never made the same mistake again. He simply lost track of the number of games he played with it, but it just kept getting better at better. Must be pretty satisfying to make something that learns from you — kind of like parenthood…

Anyway, [Greg] has an awesome writeup available on his blog, so you should definitely check it out — we can only summarize so much! Stick around after the break to see a video of the game in action.

Continue reading “The Game Of NIM” →