Yesterday, while waiting in a traffic jam, I implemented a small game. I read about this game in a book and to not get too annoyed about the waiting time I opened the lid of my laptop and wrote this game. This morning I completed it with some usual stuff to increase the usability..

It’s written in C++ and you can play against the CPU. There is a strategy that makes you win in almost every case! This game is a classic in game theory, but if I provide you with it’s original name it’ll too easy for you to solve the problem with help from Wikipedia or something like that. So just try it on you own ;)

The aim of the game is to clear all the stacks that are filled with o ‘s. The stacks may look like this:

Now it is your turn to choose one of these stacks and remove some or all o’s of it. Notice that you have to remove at least one of them and you can only remove o’s from one single stack! After your turn, the artificial intelligence will do the same. Afterwards it’s again your turn, until all stacks are cleared. Winner is the one who cleared the last stack, so try to get the last o ;) Here is the download.

You can choose the number of stacks and the maximum number of o’s a stack can carry:

If anybody knows the strategy, feel free to tell me!

Download: C++: NIM - the game (Please take a look at the man-page. Browse bugs and feature requests.)

Martin S. | Permalink | 2010-08-10 19:38:33

Hmmm, I think … I understand it. After a lot failures.

http://meet-unix.org/img/proof.jpg

martin | Permalink | 2010-08-10 21:34:17

Actually I cannot retrace your calculations, but it seems that you were able to conquer this problem. Congatulations! ;)

The original name of this game is NIM.