[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.
Ah… It looks really good – both the backlit buttons and the other metallic buttons. And the leds against the black background. Nice. But the wooden box around it makes it look a bit tacky though….
I actually wrote a small NIM implementation for a PIC16F1503 a few weeks ago. I had to make four games that could be played with four touch buttons as input and three 7-segment led displays as output. So NIM was one of the games for it, but I ended up replacing it with another game in the final moment.
But I’ll have a peek at your AI-implementation of it since it sounds cool.
I agree about the wood trim. I think it’s just the natural finish that looks off though, if he painted it I think it would look great.
The work done on this seems pretty impressive. I’m sure Greg learnt a lot developing the AI, but now sadly I feel I should probably mention that there is an easy method for unbeatable AI (assuming first move or one blunder if the human goes first). http://en.wikipedia.org/wiki/Nim puts it better than I can, and I also don’t want to spoil the fun for anyone. This is more likely to be the mothod used on that Apple II, as it is really easy to implement in software, and is also a great way of winning bets with your friends provided you can do a bit of binary maths in your head :)
If you’ll read the blog article (which is much more interesting than this article lets on), you’ll see he also implemented that version, and even identified a “flaw” in it (in that it seems to miss “openings” to turn the tide). I agree with him that the “learning” version is MUCH more interesting though…
I think it should be possible to make the AI implementation fairly easily. It shouldn’t need more than 32768 bytes of precompiled data, even less if you take out all of the invalid states of the game. You don’t have to store the entire chain of the game in order to do it, just the state of the board followed by the best possible move. To build that might take a bit of time though since you’d need to iterate through every board state and find the next best move, but even then it shouldn’t be too bad. I might take a stab at that later tonight…
Or you just check wikipedia, which has a small program with optimal strategy:
http://en.wikipedia.org/wiki/Nim
Chili Roulette anyone?
https://www.youtube.com/watch?v=3Lu1Tol0yL4&feature=player_detailpage#t=451
I remember programming a very simple AI, so-to-say, to play this on my HP-28S, those where the fun days !