ISSN : 1796-203X
Volume : 2    Issue : 1    Date : February 2007

Tutoring an Entire Game with Dynamic Strategy Graphs: The Mixed-Initiative Sudoku Tutor
Allan Caine and Robin Cohen
Page(s): 20-32
Full Text:
PDF (891 KB)

In this paper, we develop a mixed-initiative intelligent tutor for the game of Sudoku called MITS. We
begin by developing a characterization of the strategies used in Sudoku as the basis for teaching
the student how to play. In order to reason about interaction with the student, we also introduce a
student modeling component motivated by the mixed-initiative model of Fleming and Cohen that
tracks what the student knows and understands. In contrast to other systems for tutoring games, we
are able to interact with students to complete an entire game. This is achieved by retaining a model
of acceptable next moves (called a strategy graph) and dynamically adjusting this model as the
student plays the game. We present the overall architecture of the system followed by an
explanation of the modules that encapsulate the rules of Sudoku. We also outline formulae for
reasoning about interaction with the student that support mixed-initiative where either the system or
the student can elect to direct the playing of the game. An implementation of the system is
discussed, including examples of MITS interacting with students in order to tutor the game. To
conclude, we discuss how this research is useful not only to gain insight into how to tutor students
about strategy games but also to understand how to support mixed-initiative interaction in tutorial

Index Terms
Intelligent Tutoring Systems, Mixed-Initiative Systems, Strategy Games, Student Modeling