Game of Sticks

Antti Laaksonen, Arto Vihavainen
ahslaaks@cs.helsinki.fi, avihavai@cs.helsinki.fi
University of Helsinki

Overview

In the game of sticks there is a heap of sticks on a board. On their turn, each player picks up 1 to 3 sticks. The one who has to pick the final stick will be the loser.

Sample game

The following is an example of the game of sticks.

Meta Information

Summary An assignment where the student will implement the game of sticks as well an AI for it that is able to learn from its mistakes. Depending on the implementation approach and given scaffolding, can be used to practice e.g. text io, arrays and/or maps. Can be also given out as a mathematical problem, where the students need to perform a mathematical analysis for the optimal solution that the AI eventually learns.
Topics Elementary artificial intelligence, probabilities, basic data structures such as arrays or maps depending on the implementation approach.
Audience Appropriate for CS1 or early CS2. Can be also used as a task in high-school programming clubs.
Difficulty This is an intermediate assignment that takes a day from a CS1 student. The difficulty can be adjusted by providing some parts of the code beforehand.
Strengths Main strength of the assignment is that it acts as an introduction to AI that can learn from its mistakes. It is a hit among the students; many are awed by the fact that they can produce an AI that is able to learn how to beat them at a game already during their first semester of studies.
Weaknesses As there is an optimal solution to the problem, creating a complex learning AI may be seen unnecessary. The approach taken in this assignment is not applicable to problems with a lot of states, as the AI keeps all of them in the memory.
Dependencies Requires an understanding of text I/O and some previous practice with the chosen data structure (e.g. arrays or maps). If the last part of the assignment is included, some mathematical maturity is also needed.
Variants A variant of this approach has been used to learn a strategy for playing tic-tac-toe. The tic-tac-toe -approach is described by D. Michie and R. A. Chambers in Machine Intelligence 2, published in 1968, (eds. E. Dale and D. Michie), pp. 137-152. Title "BOXES; an experiment in adaptive control". (link)

Handout

Sample handout available as a html page.