Single-Agent and Adversary Search In Combinatorial Spaces: Fun With Puzzles and Games
|
Bart Massey
Department of Computer Science, Portland State University
|
|
Abstract:
The essence of the difficulty of puzzles and traditional games lies in
their requirement to choose wisely from a large set of possible
futures. These choices are made by manipulating combinations of a
small set of elements. Most modern computer programs that
successfully tackle problems of "intelligent" puzzle-solving or game
play do so by shallowly examining the consequences of a wide range
of choices at each decision point.
This talk explains some theoretical underpinnings of this
"combinatorial search" problem and briefly surveys the
methods used for combinatorial search in puzzles and
games. A couple of examples from past and current
research will be discussed: specifically optimal Yahtzee
and optimal Boggle boards. Finally, some consideration
will be given to outstanding problems in this area.
|
|
Bart Massey ('87, Physics) is an Assistant Professor of
Computer Science at Portland State University where his
research focuses on open source software engineering, and
on software applications of combinatorial search and other
AI techniques. His doctorate is from the University of
Oregon Computational Intelligence Research Laboratory
(CIRL), with a dissertation on search direction in
general-purpose planning.
|