Date: November 20, 2003

Time: 1:30 pm

Place: ASB 9705

Speaker: Oliver Schulte, Simon Fraser University

Title: Implementing Minimax Search in Logic Programs

This is not a presentation of finished research; I formulate a problem and
discuss some initial ideas for attacking it. The problem is to implement

minimax search efficiently in a logic program. Minimax search is the oldest
algorithm in game theory or multi-agent systems: Zermelo used it in 1913 to
prove that there were optimal strategies for chess that guarantee each player
the best possible outcome they he can get. Games programs, such as Schaeffer's
Chinook checkers program, use minimax search to attain perfect play towards
the end of game when there are fewer pieces. The problem is that as the space
of possible positions increases, the algorithm needs more computational resources
than are available. My basic idea is to use logic to give compact implicit descriptions
of the space of possible positions, and then reformulate minimax search so that
it is carried out directly on the (hopefully) short logical description of the
game rather than the huge explicitly represented set of possible positions.

This research has potential applications to zero-sum games other than parlour
games, for example cryptographic protocols, which are in effect a zero-sum game
between the communicating parties and possible adversaries.