Top

Hint

Swipe to navigate through the chapters of this book

Published in:

2021 | OriginalPaper | Chapter

The \(\alpha \mu \) Search Algorithm for the Game of Bridge

Authors: Tristan Cazenave, Véronique Ventos

Published in: Monte Carlo Search

Publisher: Springer International Publishing

Abstract

\(\alpha \mu \) is an anytime heuristic search algorithm for incomplete information games that assumes perfect information for the opponents. \(\alpha \mu \) addresses and if given enough time solves the strategy fusion and the non-locality problems encountered by Perfect Information Monte Carlo search (PIMC). Strategy fusion is due to PIMC playing different strategies in different worlds when it has to find a unique strategy for all the worlds. Non-locality is due to choosing locally optimal moves that are globally inferior. In this paper \(\alpha \mu \) is applied to the game of Bridge and outperforms PIMC.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Testen Sie jetzt 15 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

inform now

next chapter Stabilized Nested Rollout Policy Adaptation

It is an acceptable simplification of the real scoring of Bridge. At Bridge, the declarer has to make six more tricks than the number in his contract.

Brown, N., Sandholm, T.: Superhuman AI for multiplayer poker. Science 365(6456), 885–890 (2019) MathSciNetCrossRef

Buro, M., Long, J.R., Furtak, T., Sturtevant, N.: Improving state evaluation, inference, and search in trick-based card games. In: Twenty-First International Joint Conference on Artificial Intelligence (2009)

Cowling, P.I., Powley, E.J., Whitehouse, D.: Information set Monte Carlo tree search. IEEE Trans. Comput. Intell. AI Games 4(2), 120–143 (2012) CrossRef

Frank, I., Basin, D.: Search in games with incomplete information: a case study using bridge card play. Artif. Intell. 100(1–2), 87–123 (1998) MathSciNetCrossRef

Frank, I., Basin, D.: A theoretical and empirical investigation of search in imperfect information games. Theoret. Comput. Sci. 252(1–2), 217–256 (2001) MathSciNetCrossRef

Frank, I., Basin, D.A., Matsubara, H.: Finding optimal strategies for imperfect information games. In: AAAI/IAAI, pp. 500–507 (1998)

Furtak, T., Buro, M.: Recursive Monte Carlo search for imperfect information games. In: 2013 IEEE Conference on Computational Intelligence in Games (CIG), pp. 1–8. IEEE (2013)

Ginsberg, M.L.: Partition search. In: Proceedings of the Thirteenth National Conference on Artificial Intelligence and Eighth Innovative Applications of Artificial Intelligence Conference, AAAI 1996, IAAI 1996, Portland, Oregon, USA, 4–8 August 1996, vol. 1, pp. 228–233 (1996). http://www.aaai.org/Library/AAAI/1996/aaai96-034.php

Ginsberg, M.L.: GIB: imperfect information in a computationally challenging game. J. Artif. Intell. Res. 14, 303–358 (2001). https://doi.org/10.1613/jair.820 CrossRefMATH

10.

Haglund, B.: Search algorithms for a bridge double dummy solver. Technical report (2010)

11.

Kupferschmid, S., Helmert, M.: A Skat player based on Monte-Carlo simulation. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 135–147. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75538-8_12 CrossRef

12.

Levy, D.N.: The million pound bridge program. In: Heuristic Programming in Artificial Intelligence The First Computer Olympiad, pp. 95–103 (1989)

13.

Lockhart, E., et al.: Computing approximate equilibria in sequential adversarial games by exploitability descent. arXiv preprint arXiv:1903.05614 (2019)

14.

Long, J.R., Sturtevant, N.R., Buro, M., Furtak, T.: Understanding the success of perfect information Monte Carlo sampling in game tree search. In: Twenty-Fourth AAAI Conference on Artificial Intelligence (2010)

15.

Mahmood, Z., Grant, A., Sharif, O.: Bridge for Beginners: A Complete Course. Pavilion Books (2014)

16.

Müller, M.: Partial order bounding: a new approach to evaluation in game tree search. Artif. Intell. 129(1–2), 279–311 (2001) MathSciNetCrossRef

17.

Silver, D., et al.: A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362(6419), 1140–1144 (2018) MathSciNetCrossRef

18.

Silver, D., et al.: Mastering the game of go without human knowledge. Nature 550(7676), 354 (2017) CrossRef

19.

Sturtevant, N., Zinkevich, M., Bowling, M.: Prob-max \(\hat{\,}\) n: Playing n-player games with opponent models. In: AAAI, vol. 6, pp. 1057–1063 (2006)

20.

Sturtevant, N.R., White, A.M.: Feature construction for reinforcement learning in hearts. In: van den Herik, H.J., Ciancarini, P., Donkers, H.H.L.M.J. (eds.) CG 2006. LNCS, vol. 4630, pp. 122–134. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-75538-8_11 CrossRef

21.

Ventos, V., Costel, Y., Teytaud, O., Ventos, S.T.: Boosting a bridge artificial intelligence. In: 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 1280–1287. IEEE (2017)

22.

Zinkevich, M., Johanson, M., Bowling, M., Piccione, C.: Regret minimization in games with incomplete information. In: Advances in Neural Information Processing Systems, pp. 1729–1736 (2008)

Title: The Search Algorithm for the Game of Bridge
Authors: Tristan Cazenave
Véronique Ventos
Publisher: Springer International Publishing
Book: Monte Carlo Search
Print ISBN: 978-3-030-89452-8

Electronic ISBN: 978-3-030-89453-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-89453-5_1

Springer Professional

Hint

Swipe to navigate through the chapters of this book

Abstract

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner