Proposer: Ian Frank, ianf@aisb
Suggested Supervisors: Alan Bundy, Ian Frank
Principal goal of the project: To investigate the performance of a complete information search architecture in a domain with incomplete information. Specifically, to examine the extent of the problems of non-locality and strategy mixing when using a double-dummy architecture in the game of Bridge.
Description:
Every time a computer game-playing program performs well against top human opposition, the area of game-playing receives renewed publicity. The opening defeat of Kasparov by the Deep Blue chess computer in their 6-game match is just the most recent of these cases (Kasparov went on to win the match 4-2).
However, one game in which computers have yet to approach the level of human players is contract Bridge. The main reason for the poor performance of computers in Bridge seems to be that the presence of incomplete information makes it difficult for computers to carry out look-ahead search. The winner of the 1982 Computer Olympiad Bridge tournament, for example, did no look-ahead search at all. When compared to humans, who can typically project play forwards to the end of the game, it is perhaps not surprising that such systems do very badly.
Some authors have suggested tackling Bridge with an architecture that carries out a traditional look-ahead search under the assumption that information is in fact complete. By repeating this search on a `representative' sample of the possible world states (a kind of repeated minimaxing architecture), the action which `usually works best' can be selected. However, Ian Frank's PhD thesis shows that this approach suffers from the twin problems of strategy mixing and non-locality.
The aim of this project would be to utilise a simple double-dummy solver to produce a program capable of generating lines of play for single-suit card combinations in the game of Bridge. Matt Ginsberg has produced a public version of a double-dummy solver (written in C) which it should be possible adapt to the purpose. The results of this investigation would help inform the debate on whether this type of architecture will ever be scale up to play good Bridge.
The first stage of the project would involve producing a repeated minimaxing architecture into which a double-dummy solver could be incorporated. This architecture would then be tested against the 650 problems contained in the Bridge Encyclopedia. The basic task would be to find the number of problems in which the correct first move would be selected. The second stage would then involve checking whether the moves selected on the following rounds of play were also correct. At this stage, a comparison with the department's existing Finesse planning system would also be very useful.
Further extensions to the project would involve identifying the specific situations in which problems were created by strategy mixing and non-locality, and maybe categorising each `mistake' of the program into either category. Also, it would be interesting to investigate whether modifications to the basic repeated minimaxing architecture could improve the performance. For instance, it seems likely that replacing the minimax propagation algorithm with average propagation would reduce the effects of strategy mixing (but also adversely affect speed). Also, it is possible that searching the entire game tree at each move instead of just the possible continuations from the current state could reduce the impact of non-locality.
Resources Required: A workstation. Access to the Finesse planning system.
Degree of Difficulty: At the basic level the project is likely to be time-consuming, but not necessarily conceptually difficult. Any of the extensions, however, present opportunities for challenging and creative work.
Background Needed: Knowledge of the game of Bridge would be highly advantageous for interpreting the results of the program. Some knowledge of C will be necessary if Matt Ginsberg's code is to be used or modified, and at least some proficiency in Prolog will also be required if the Finesse planning system is going to be used for comparison.
Degree Programmes Suitable:
References: