Dave Auckly took the lead on this activity for the 2012 Circle on the Road festival.
AUDIENCE: High School Students and Teachers
APPRENTICES/TEAM MEMBERS: Matthias Kawski, Barbara Burns, Leo Marianiello, Amanda Serenevy
TITLE: Ski Jumps and Kalah
ABSTRACT: In this session participants will learn to play a die game, a variant of the game Kalah, and a game called Ski Jumps. Participants will learn the game of NIM and an optimal way to play NIM. They will also learn that many games are equivalent to NIM. In particular, they will try to discover NIM games equivalent to our variant of Kalah with various starting distributions.
Versions of Kalah boards were found in Africa dating back to the 6th and 7th centuries AD. It may be much older.
In earlier festivals we have explained the game of NIM and led participants to start finding the optimal play. This is a follow-up lesson that we can run assuming people already know the optimal way to play NIM. We will arrange this by telling them an optimal way to play.
In this lesson we will teach participants to play the Die Game, Ski Jumps, Kalah, and NIM. All team members should understand the rules of these games as described in the attached files. Team members should understand optimal play for the Die Game, and NIM.
Ask if you need further explanation. After playing the Die game a few times, we will get them started finding an optimal sequence of play. We will then show participants Ski Jumps and let them play a bit. In particular, we will encourage them to figure out the values of a few positions. Team members should at least try to answer the numbered questions on the Ski Jump hand-out. Finally, we will show them the game of Kalah and let them play for a while (maybe once). The main project for this circle session will
be determining the NIM values of various Kalah positions/and or Die Game positions.
References are listed on the Ski Jumps hand out.
To play the games we will need to bring a collection of egg cartons for Kalah, grid paper for Ski Jumps, Dice for the Die Game, macaroni noodles, and cut coffee stirers to use as counters for NIM and pieces for Ski Jumps.
“Nim” is a two-player game played with sticks. The sticks are divided into piles. The players alternate turns. On each player’s turn they may remove any number of sticks from one of the piles, up to the number of sticks remaining in that pile; but they can only take from a single pile on a given turn.
The goal is to take the last stick. Whoever takes the last stick wins.
NIM has a collection of kernel states. If it is your move and it is in a kernel state, you’re going to lose (unless I make a mistake). On the other hand, if it is not in a kernel state when it is your move, then you can force a win, by moving it into a kernel state, and then I’m forced to move out of a kernel state, and then you can move it back into a kernel state, and so on, and eventually we get to a winning state.
Example: Suppose the piles are 3, 7, 9
(it doesn’t matter which pile is which, just the set of numbers, order unimportant)
Then, go through each column and take the “parity” — a 0 if there are an even number of 1s, or a 1 if there are an odd number of 1s. This is known as a “bitwise xor”, and is also equivalent to adding each column mod 2.
The resulting value is 1101, thus this state is not in the kernel.
The rule is: in the kernel === all zeroes in parity computation (bitwise xor)
|Die Game Notes.pdf|