Nim Game

DMCommunity’s Jan-2020 challenge “Nim Rules” offers to find a winning strategy for this game: “There is a number of red balls in the row below (it could be 15, 16, or 17 balls). Two players take turns removing balls from the row, but only 1, 2 or 3 balls at a time. The player who removes the last ball loses.”

People play different versions of the Nim game since ancient times. First time I played this game with 15 parrots against a clown at a children’s party when I was 7. Later on during my first university’s year my math professor challenged me to play this game instead of answering my exam questions. He said he will tell me the total number of objects N and the number of objects K we can take at a time, and asked me to think about it. 10 mins later I came up with a simple formula and told him that I am ready. When he offered me the values of N and K, I asked him to make the first move. Without any moves or further questions he said that I passed my exam. He was a really good teacher!

Back to the challenge. There is already an interesting solution that uses OPL CPLEX. But can we define a playing strategy using the simple rules?  Actually, I used this game ~5 years ago to demonstrate that power of OpenRules Dialog – you still can play it online from here. After playing quite a few games you will figure out how many objects you want to leave your opponents after each move (e.g. 13, 9, 5,…). Without thinking about the formula, you may write your rules in this decision table:

Hopefully, this table is intuitive enough without explanations. You can find the entire project “Nim” in the latest OpenRules Decision Manager installation. When you execute this project it will produce:

I’d also like to explore an ML-based approach when after playing a certain number of games against itself, an ML algorithm can generate these or similar rules automatically.  It will be interesting to see who would do it first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.