Machine Learning Laboratory Experiences for Introducing
Undergraduates to Artificial Intelligence
NSF DUE CCLI-A&I Award Number 0409497
Solving the Dice Game Pig:
an introduction to dynamic programming and value
iteration
The
jeopardy dice
game Pig is very simple to describe, yet the
optimal policy
for play is far from trivial. Using the computation of the
optimal solution as a central challenge problem, we introduce dynamic
programming and value iteration methods, applying them to similar problems
using the Java language.
- Dynamic Programming:
- Demonstrate the need for dynamic programming through Fibonacci number computation.
- Guide the student through the details of a Java solution to a simple Pig variant with an acyclic state space.
- Provide problem solving exercises that will ground the student's understanding of dynamic programming in experience.
- Value Iteration:
- Introduce the method of value iteration.
- Demonstrate its application to a simple coin variant of Pig called Piglet.
- Guide the student through the details of a Java solution to Piglet.
- Provide problem solving exercises that will ground the student's
understanding of value iteration in experience.
Before starting the project, the student will want to understand the definition of a Markov decision process, perhaps by covering the recommended background reading below.
Stuart Russell and Peter Norvig. Artificial Intelligence: a modern approach, 2nd ed. Prentice Hall, Upper Saddle River, NJ, USA, 2003.
Students are encouraged to play the game of Pig in order to have a better
understanding of the problem. An
applet with an optimal computer
player is available at the
Game of Pig
page.
Example code described in the project is available here:
This code was generated from the same source file that generated pig.pdf using the literate programming tool noweb.
We recommend having students do at least one dynamic programming exercise and one value iteration exercise.
Students seeking
more extended challenges will also find descriptions of related advanced
projects for dynamic programming and value iteration.
Here is a sample syllabus used in CS 371 - Introduction to AI at Gettysburg College:
First class: Tuesday 9/28/04
Preparatory Reading: Sections 1-2 of
pig.pdf.
Dynamic programming
Homework due Thursday 9/30/04: One complete exercise from section 2.4
Second class: Thursday 9/30/04
Preparatory Reading: Remaining sections of
pig.pdf,
Russell & Norvig sections 17.1, 17.2
Value Iteration
Homework due Thursday 10/7/04: One complete exercise from section 3.5
(There was a two-day break 10/4-10/5. Without the break, Tuesday
10/5 rather than 10/7 would have been appropriate.)
The following additional coverage is not included in this project, but
may provide the instructor additional ideas:
Third class: Thursday 10/7/04:
(no preparatory reading)
Mountain Car Problem of Example 8.2 of
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: an
introduction. MIT Press, pp. 214-215. (Online at
http://www.cs.ualberta.ca/~sutton/book/8/node9.html)
See also:
http://www-anw.cs.umass.edu/rlr/domains.html,
http://www.cs.ualberta.ca/~sutton/MountainCar/MountainCar.html
Our approach to this problem is to simply apply value iteration, discretizing the state space into a 400-by-400 grid of cells, and approximating the dynamics of each time step as a mapping from one cell to another. In other words, overlay the 2D state space (position, velocity) with a 400-by-400 grid. Simulate one time-step from each grid intersection and note which is the nearest intersection to the resulting state. This defines a mapping to discretely approximate the system dynamics. Then apply value iteration with a reward of -1 for each step that the system is not at the rightmost position.
Cambridge, Massachusetts, 1998.