A theoretical and empirical investigation of search in imperfect information games. (English) Zbl 0954.68056
Summary: We examine search algorithms for games with imperfect information. We first investigate Monte Carlo sampling, showing that for very simple game trees the chance of finding an optimal strategy rapidly approaches zero as size of the tree increases. We identify the reasons for this sub-optimality, and show that the same problems occur in Bridge, a popular real-world imperfect information game. We then analyse the complexity of the underlying problem, proving it to be NP-complete and describing several polynomial time heuristics. We evaluate these heuristics theoretically and experimentally, demonstrating that they significantly out-perform Monte Carlo sampling. Indeed, on a set of Bridge problems drawn from a definitive expert text, our heuristics consistently identify strategies as good as, or superior to, the expert solutions – the first time a game-general tree search algorithm has been capable of such performance.
References:
| [1] | ACBL, The Official Encyclopedia of Bridge, 5th Edition, American Contract Bridge League, Inc., 2990 Airways Boulevard, Memphis, TN 38116-3875, 1994.; ACBL, The Official Encyclopedia of Bridge, 5th Edition, American Contract Bridge League, Inc., 2990 Airways Boulevard, Memphis, TN 38116-3875, 1994. |
| [2] | Blair, J. S.; Mutchler, D.; van Lent, M., Perfect recall and pruning in games with imperfect information, Comput. Intelligence (1996) |
| [3] | R.A. Corlett, S.J. Todd, A Monte-Carlo approach to uncertain inference, in: P. Ross (Ed.), Proc. Confe. on Artificial Intelligence and Simulation of Behaviour, 1985, pp. 28-34.; R.A. Corlett, S.J. Todd, A Monte-Carlo approach to uncertain inference, in: P. Ross (Ed.), Proc. Confe. on Artificial Intelligence and Simulation of Behaviour, 1985, pp. 28-34. |
| [4] | E. Crowhurst, Personal communication, May 17 1996.; E. Crowhurst, Personal communication, May 17 1996. |
| [5] | Frank, A., Brute force search in games of imperfect information, (Levy, D. N.L.; Beal, D. F., Heuristic Programming in Artificial Intelligence 2 - The Second Computer Olympiad (1989), Ellis Horwood: Ellis Horwood Chichester, UK), 204-209 · Zbl 0754.68096 |
| [6] | I. Frank, Search and planning under incomplete information: a study using bridge card play, Ph.D. Thesis, Department of Artificial Intelligence, Edinburgh, 1996, also published by Springer-Verlag in the Distinguished Dissertations Series, ISBN 3-540-76257-4, 1998.; I. Frank, Search and planning under incomplete information: a study using bridge card play, Ph.D. Thesis, Department of Artificial Intelligence, Edinburgh, 1996, also published by Springer-Verlag in the Distinguished Dissertations Series, ISBN 3-540-76257-4, 1998. |
| [7] | I. Frank, D. Basin, Optimal play against best defence: complexity and heuristics, in: H.J. van den Herik, H. Iida (Eds.), Proc. 1st Internat. Conf. of Computers and Games, CG98, Lecture Notes in Computer Science, Vol. 1558, Tsukuba, Japan, Springer, Berlin, 1998, pp. 50-73, ISBN 3-540-65766-5.; I. Frank, D. Basin, Optimal play against best defence: complexity and heuristics, in: H.J. van den Herik, H. Iida (Eds.), Proc. 1st Internat. Conf. of Computers and Games, CG98, Lecture Notes in Computer Science, Vol. 1558, Tsukuba, Japan, Springer, Berlin, 1998, pp. 50-73, ISBN 3-540-65766-5. |
| [8] | Frank, I.; Basin, D., Search in games with incomplete information: a case study using bridge card play, Artifi. Intell., 100, 1-2, 87-123 (1998) · Zbl 0906.68049 |
| [9] | I. Frank, D. Basin, A. Bundy, An adaptation of proof-planning to declarer play in bridge, Proc. ECAI-92, Vienna, Austria, 1992, pp. 72-76, longer version available from Edinburgh as DAI Research Paper No. 575.; I. Frank, D. Basin, A. Bundy, An adaptation of proof-planning to declarer play in bridge, Proc. ECAI-92, Vienna, Austria, 1992, pp. 72-76, longer version available from Edinburgh as DAI Research Paper No. 575. |
| [10] | I. Frank, D. Basin, H. Matsubara, Monte-carlo sampling in games with incomplete information: empirical investigation and analysis, Workshop on Game Tree Search: Past, Present and Future, Princeton, NJ, 1997, also available from the Electrotechnical Laboratory, 1-1-4 Umezono, Japan, as Technical Report ETL-97-18.; I. Frank, D. Basin, H. Matsubara, Monte-carlo sampling in games with incomplete information: empirical investigation and analysis, Workshop on Game Tree Search: Past, Present and Future, Princeton, NJ, 1997, also available from the Electrotechnical Laboratory, 1-1-4 Umezono, Japan, as Technical Report ETL-97-18. |
| [11] | I. Frank, D. Basin, H. Matsubara, Finding optimal strategies for imperfect information games, Proc. AAAI-98, 1998, pp. 500-507.; I. Frank, D. Basin, H. Matsubara, Finding optimal strategies for imperfect information games, Proc. AAAI-98, 1998, pp. 500-507. |
| [12] | Fudenberg, D.; Tirole, J., Game Theory (1995), MIT Press: MIT Press Cambridge, MA |
| [13] | Garey, M. R.; Johnson, D. S., Computers and Intractabilitya Guide to the Theory of NP-Completeness (1979), W H Freeman: W H Freeman New York · Zbl 0411.68039 |
| [14] | M. Ginsberg, Partition search, Proc. AAAI-96, 1996, pp. 228-233.; M. Ginsberg, Partition search, Proc. AAAI-96, 1996, pp. 228-233. |
| [15] | Goren, C. H., Goren’s New Bridge Complete (1986), Century Hutchinson Limited |
| [16] | Koller, D.; Meggido, N.; von Stengel, B., Efficient computation of equilibria for extensive two-person games, Games Econom Behav, 14, 2, 247-259 (1996) · Zbl 0859.90127 |
| [17] | Levy, D. N.L., The million pound bridge program, (Levy, D. N.L.; Beal, D. F., Heuristic Programming in Artificial Intelligence - The First Computer Olympiad (1989), Ellis Horwood: Ellis Horwood Chichester, UK), 95-103 |
| [18] | Duncan Luce, R.; Raiffa, Howard, Games and Decisions - Introduction and Critical Survey (1957), Wiley: Wiley New York · Zbl 0084.15704 |
| [19] | Nau, D. S., The last player theorem, Artif. Intell., 18, 53-65 (1982) · Zbl 0471.90003 |
| [20] | Nygate, Y.; Sterling, L., Pythonan expert squeezer, J. Logic Programming, 8, 1,2 (1990) · Zbl 0698.68084 |
| [21] | Shannon, C. E., Programming a computer for playing chess, Philos. Mag., 41, 256-275 (1950) · Zbl 0041.44605 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
