Babylonic Libation Support Device

In ancient Babylon there was a game of wit called nim. It was used to determine who would buy the next round of drinks, usually a tray of Tigris Tumblers or Euphrates Ecstasy's guaranteed to make hung gardeners droop. This mildly apocryphal tale leads in to the analysis of the things called nim which were games with coins.

Nim the first oft learnt by rote for a fixed set of coins (15), but easily generalised and a great thing to give kids as a programming project and a lesson in AI (that's Artificial Intelligence for you veterinaries!!)

Nim the second was invented to overcome the problem of finding reliable patsies to buy the drinks once the strategy for nim the first became common knowledge, more complex but still tractable.

After that some idiot invented chess, long game, no guaranteed strategy; definitely too long between drinks to sustain a civilisation... and so the Babylonians sobered up and, naturally, they all killed each other...

Nim the First

Have a go at a The javascript version of nim :-)

How to avoid buying the drinks:

Well this can be done by cheating or mathematical induction or by simple Arithmetic progressions. Now cheating is lot of fun but it inexorably leads to futures exchanges and derivative trading but that really has no Barings on the current matter. Some people don't like mathematical induction but they can't prove there is more than one of them so they don't count(!). Arithmetic progressions on the other hand are one of those dumb things kids have gotta do in Mafs (that's how they pronounce Mathematics in Australian Juvenile dialect).... so I'll do it that way. Lets suppose there is only one coin "O" (O is a good symbol for a coin), if it's your go, you're on your way to the bar, so the idea is to make sure your opponent is left with that one "O". Now for arguments sake lets suppose that the agreed maximum "O"s that can be taken on any one go is 3. Well we better make sure that on our preceding go we had between 2 and 4 coins in the pile...'cause then you can legally leave our opponent (hereintofor "the patsy") with one. Now that means that we had better have left the patsy with 5 coins on the go previous to that. That is, always exactly one "O" out of reach. So in this contrived game it means we have to always ensure that after our go we leave ... 17,13,9,5,1 coins for the patsy to play with (that is 3+1=4 apart). Now number separqated by a common difference is an Arithmetic progression, so if you know how to work out the terms of an A.P. then you can win this game

The actual numbers have no particular attraction, who wants to enumerate the games? (there was this guy who had this great program for working out which horse would win... yeh he is still a teacher... but he wanted to take a booklet to the races which was the printed output from the permutations of his program... I worked out that the hire of the nine semi trailers he'd need were not within his budgetary constraints)... so lets put some algebra into the nim thing:

Let M= maximum number of coins which may be taken on any one turn
Let N= the number of coins currently in the pile
So if 1 is the first patsy number then the i th patsy number is 1 + M(N-1) To decide if you should try to go first or not you should work out if the number of "O"'s sitting on the bar is a patsy number, if it is then contrive not to go first.

Each of your turns should leave the patsy on one of the sequence of patsy numbers. To do this you need to work out how far you are from the next lowest patsy number, this will be a number between 0 and M, so its a good time to introduce modular arithmetic: You should take (N-1) mod (M+1) coins. For example if there were 23 coins in the pile and M is 3, you should take (23-1) mod (3+1) which is 22 mod 4 or 2 coins, leaving the patsy with 21 coins, subsequently you leave the patsy with (21-4) 17 coins then 13,9,5,1 and then he's on his way to the bar. (Sorry about the "he" but "he slash she" is needlessly violent and "it" has not yet been adopted as a generic politically correct title for humans since it more familiarly applies to anything (alive or not), so PC is still anthropocentric, it hasn't run its full course yet!. )

So now how to sell nim to the kids

  1. Have them pair up and play (use stand alone graphics instruments and paper) Don't tell them the winning strategy. The two points here are to familiarise them with the game and let them find out that some thought is required.

  2. It's a challenge to write a program to play nim, even if kids aren't given the strategy there is the user interaction to set up and the screen display (Using HyperCard on a Macintosh makes this really easy, The javascript version is more involved). They are going to need a routine for the computers "go", a random number generator will do initially

  3. Having developed/plagiarised a working (but dumb) program, tell them (the kids) about the strategy, or coach them into finding out (this is a nifty cross curricula bit with maths), they can now alter their programs to determine when they are in a position to use the strategy (i.e the mod thingy is not zero) and when they should retain the random number generator in the hope that the (now not so) patsy will make an error later on.

  4. The AI part is to get the kids to pit their program against other people and (probably) beat them, then ask the kids to explain how they feel about that and if their program is "intelligent" or has stored their intelligence or the person who invented the strategy's intelligence or whatever.. that is get a personal handle on the concept of intelligence (be it artificial or not)

  5. Assessment could be cross curricula
    • Understanding of the algebraic bit (Maths er.. Mafs)
    • Presentation of a reasonable argument regarding Artificial Intelligence (English)
    • Assessment of the computer program*
    • Even a little play relevant to the game in some other context (speech and drama#)
*The way I like to assess computer programs especially big collaborative projects is in a test situation. I allow the victims any resources they want and insist that they bring their code (on disc or paper) then ask them to make minor changes to their program code (like alter the user prompt, or restrict selection of the maximum number of coins to a range) or to "circle" bits in their code which do things (like the optimal strategy). This process allows the victims to demonstrate their level of understanding of their project. You can throw in more challenging stuff (probably as take home assessment items), like discuss how you would adjust the strategy if the maximum number of coins that could be taken increased / decreased by x after each turn...

#As part of a conference where a team of us developed a presentation of program linking (on Macintosh of course: Apple conferences are a lot of fun) we used Nim as a symbolic conflict between George Bush and Sadam Hussein on separate computers. Graphics and voices courtesy of Desert Storm CD and animation style courtesy of Monty Python.

Bill Taylor

Return to Publications page

This page was created on 18 March 1995, last modified on 18 March 1995 and is supported by Bill Taylor