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.