Antti Laaksonen, Arto Vihavainen
ahslaaks@cs.helsinki.fi, avihavai@cs.helsinki.fi
University of Helsinki
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.
The following is an example of the game of sticks.
| 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) |
Sample handout available as a html page.