Efektywne rozwiązanie problemu rozgrywki w otwarte karty w brydżu

• Autorzy: Beling P.
• Języki publikacji: PL

Abstrakty

EN

This paper presents a review of algorithms which allow effective solution to a double dummy problem in the card game of Bridge. From game-theory point of view, the problem is a finite, zero-sum, two-player game with perfect information. It has a huge game tree (of the order of about 13! . 2 39 ≈ 3 .10 21, even if we assume that the average branching factor for players to follow the suit is just 2). The proposed solutions was implemented and checked in practice. Performance analyses and comparisons to another popular program are included.

Słowa kluczowe

PL

problem gry w otwarte karty; teoria gier; suma gry zerowej dla dwóch graczy; gra karciana brydż; podział wyszukiwania; alfa-beta przycinanie; MTD; ETC

EN

double dummy problem; game theory; zero-sum two-player game; card game of Bridge; partition search; MinMax; alpha-beta pruning; MTD; ETC

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2011
• Tom: nr 3
• Strony: 5--18
• Opis fizyczny: Bibliogr. 25 poz., rys., tab.

Twórcy

autor

Beling P.

• Uniwersytet Łódzki, Wydział Matematyki i Informatyki

Bibliografia

• [1] M. L. Ginsberg. How computers will play bridge. The Bridge World, 1996.
• [2] M. L. Ginsberg. GIB: Imperfect Information in a Computationally Challenging Game. J. Artif.Intell. Res. (JAIR), 14:303–358, 2001.
• [3] S. Kupferschmid, M. Helmert. A Skat Player Based on Monte-Carlo Simulation. Computers and Games, pp. 135–147, 2006.
• [4] M.-S. Chang. Building a Fast Double-Dummy Bridge Solver. Technical Report TR1996-725, New York University, August, 1996.
• [5] A. Plaat, J. Schaeffer, W. Pijls, A. de Bruin. A New Paradigm for Minimax Search. Research Note EUR-CS-95-03, Erasmus University Rotterdam, Rotterdam, Netherlands, 1995.
• [6] A. Plaat. Research, Re: Search & RE-SEARCH. PhD thesis, Erasmus Univ., Rotterdam, 1996.
• [7] M. L. Ginsberg. Partition Search. AAAI/IAAI, Vol. 1, pp. 228–233, 1996.
• [8] B. Haglund. Search Algorithms for a Bridge Double Dummy Solver. http:// privat.bahnhof.se/wb758135/. [dost˛ep: 2011-10-01].
• [9] P. Beling. Praktyczne aspekty programowania gier logicznych. Master’s thesis, Politechnika Łódzka, Łódź, 2006.
• [10] T. A. Marsland. A review of game-tree pruning. International Computer Chess Association Journal, 9(1):3–19, 1986.
• [11] Chess Programming Wiki. http://chessprogramming.wikispaces.com/ . [dost˛ep: 2011-10-01].
• [12] A. Michalski. Współczesne techniki przeszukiwania grafów gier dwuosobowych. Slajdy do wykładu, 2004.
• [13] T. Michniewski. Samouczenie programów szachowych. Master’s thesis, Uniwersytet Warszawski, 1995.
• [14] M. N. J. van Kervinck. The Design and Implementation of the Rookie 2.0 Chess Playing Program. Master’s thesis, Technische Universiteit Eindhoven, Eindhoven, August 2002.
• [15] H. Kwaśnicka, A. Spirydowicz. Uczący się komputer. Programowanie gier logicznych. Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław, 2004.
• [16] M. Buro. From Simple Features to Sophisticated Evaluation Functions. Computers and Games, Proceedings of CG98, LNCS 1558, pp. 126–145. Springer-Verlag, 1999.
• [17] G. Tesauro. Temporal Difference Learning and TD-Gammon. Communications of the ACM, 38(3):58–68, March 1995.
• [18] A. L. Samuel. Some studies in machine learning using the game of checkers. IBM Journal of Research and Development, 44(1):206–227, 2000.
• [19] M. Fierz. Strategy Game Programming. http://www.fierz.ch/ strategy.htm. [dost˛ep: 2011-10-01].
• [20] M. Borkowski. Analiza algorytmów dla gier dwuosobowych. Master’s thesis, Politechnika Warszawska, 2000.
• [21] A. Paterek. Modelowanie funkcji oceniającej w szachach. Master’s thesis, Uniwersytet Warszawski, 2004.
• [22] A. Kujawski. Programowanie gry w szachy. Master’s thesis, Uniwersytet Warszawski, 1994.
• [23] J. Kozłowska-Pięcek. Porównanie różnych strategii heurystycznych dla gier. Master’s thesis, Politechnika Warszawska, 1999.
• [24] A. Plaat. MTD(f), A Minimax Algorithm faster than NegaScout. http://people.csail.mit.edu/plaat/mtdf.html. [dost˛ep: 2011-10-01].
• [25] M. L. Ginsberg. GIB: Steps Toward an Expert-Level Bridge-Playing Program. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99), pp. 584–589, 1999.