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...

- There is a pile of coins
- There are two players
- The players decide on a maximum number of coins that may be taken during a turn
- Initially a decision has to be made as to whose turn it is first (this is crucial given two competent players)
- Players take alternate turns, they remove any number of coins between 1 and the maximum (inclusive)
- The one who removes the last coin buys the next round of drinks

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!. )

- 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.
- 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
- 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.
- 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)
- 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#)

#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

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