Evolving Nash-optimal poker strategies using evolutionary computation

doi:10.1007/s11704-009-0007-5

Front Comput Sci Chin

0, Vol.

Issue () : 73-91 https://doi.org/10.1007/s11704-009-0007-5

Evolving Nash-optimal poker strategies using evolutionary computation

Hanyang QUEK, Chunghoong WOO, Kaychen TAN(

), Arthur TAY

Department of Electrical and Computer Engineering, National University of Singapore, Singapore 117576, Singapore

Download: PDF(1776 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

This paper focuses on the development of a competitive computer player for the one versus one Texas Hold’em poker using evolutionary algorithms (EA). A Texas Hold’em game engine is first constructed where an efficient odds calculator is programmed to allow for the abstraction of a player’s cards, which yield important but complex information. Effort is directed to realize an optimal player that will play close to the Nash equilibrium (NE) by proposing a new fitness criterion. Preliminary studies on a simplified version of poker highlighted the intransitivity nature of poker. The evolved player displays strategies that are logical but reveals insights that are hard to comprehend e.g., bluffing. The player is then benchmarked against Poki and PSOpti, which is the best heads-up Texas Hold’em artificial intelligence to date and plays closest to the optimal Nash equilibrium. Despite the much constrained chromosomal strategy representation, simulated results verified that evolutionary algorithms are effective in creating strategies that are comparable to Poki and PSOpti in the absence of expert knowledge.

Keywords evolutionary algorithm poker game theory Nash equilibrium

Corresponding Author(s): TAN Kaychen,Email:eletankc@nus.edu.sg

Issue Date: 05 March 2009

Cite this article:

Hanyang QUEK,Chunghoong WOO,Kaychen TAN, et al. Evolving Nash-optimal poker strategies using evolutionary computation[J]. Front Comput Sci Chin, 0, (): 73-91.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-009-0007-5
https://academic.hep.com.cn/fcs/EN/Y0/V/I/73

1	Using artificial neural networks tomodel opponents in Texas Hold’em. Machine Learning in Games Undergraduate Research Course, CMPUT 499, Computer Poker Research Group, University of Alberta , 1999
2	Korb K B, Nicholson A E, Jitnah N. Bayesian poker. In: Proceedings of the Uncertainty in Artificial Intelligence (UAI) , 1999, 343-350
3	Billings D. Computer Poker. M. Sc. research essay, Computer Poker Research Group. Alberta: University of Alberta, 1995
4	Cosmic Log, MSNBC. Human Beat Poker Bot ··· Barely , 2007, http://cosmiclog.msnbc.msn.com/archive/2007/07/25/289607.aspx
5	Holland J H. Genetic Algorithms, 2005, http://www.econ.iastate. edu/tesfatsi/holland.GAIntro.htm
6	Nash J. Equilibrium points in n-person games. In: Proceedings of the National Academy of Sciences of the United States of America , 1950, 36(1): 48-49 doi: 10.1073/pnas.36.1.48
7	Billings D, Davidson A, Schaeffer J, Szafron D. The challenge of poker. Artificial Intelligence Journal , 2002, 134(1-2): 201-240 doi: 10.1016/S0004-3702(01)00130-8
8	Billings D, Papp D, Schaeffer J, Szafron D. Opponent modeling in poker. In: Proceedings of the fifteen AAAI conference , 1998, 493-499
9	Billings D, Papp D, Schaeffer J, Szafron D. Poker as a testbed for machine intelligence research. In: Mercer R, Neufeld E, eds. Advances in Artificial Intelligence. Springer-Verlag , 1998, 1-15
10	Papp D. Dealing with imperfect information in poker. M.Sc. thesis. Alberta: University of Alberta, 1998
11	Billings D, Pena L, Schaeffer J, Szafron D. Using probabilistic knowledge and simulation to play poker. In: Proceedings of the sixteenth AAAI conference , 1999, 697-703
12	Davidson A, Billings D, Schaeffer J, Szafron D. Improved opponent modeling in poker. In: Proceedings of the 2000 International Conference on Artificial Intelligence (ICAI’2000) , 2000, 1467-1473
13	Express News, University of Alberta . U of A researchers win computer poker title, 2006, http://www.expressnews.ualberta.ca/article. cfm?id=7789
14	Billings D, Burch N, Davidson A, Holte R, Schaeffer J, Scauenberg T, Szafron D. Approximating game-theoretic optimal strategies for fullscale Poker. In: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03) , 2003, 661-668
15	Barone L, While L. An adaptive learning model for simplified Poker using evolutionary algorithms. In: Proceedings of the Congress on Evolutionary Computation (GECCO-1999) , 1999, 1: 153-160
16	Barone L,While L. Adaptive learning for poker. In: Proceedings of the Genetic and Evolutionary Computation Conference 2000 (GECCO-2000) , 2000, 566-573
17	Oliehoek F, Vlassis N, De Jong E. Coevolutionary Nash in poker games. In: Proceedings of the seventeenth Belgian-Dutch Conference on Artificial Intelligence (BNAIC-2005) , 2005, 188-193 10.1007/s11704-009-0007-5
18	The Early Show, CBS News. Poker’s Popularity Surging, 2004, http: //www.cbsnews.com/stories/2004/12/25/earlyshow/living/main663053. shtml
19	Kuhn H W. Extensive games and the problem of information. In: Proceedings of Contributions to the Theory of Games, Annals of Mathematics Studies , 1953, 2(28): 193-216

[1]	Shiwei PAN, Yiming MA, Yiyuan WANG, Zhiguo ZHOU, Jinchao JI, Minghao YIN, Shuli HU. An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem[J]. Front. Comput. Sci., 2023, 17(4): 174326-.
[2]	Li ZHANG, Yuxuan CHEN, Wei WANG, Ziliang HAN, Shijian Li, Zhijie PAN, Gang PAN. A Monte Carlo Neural Fictitious Self-Play approach to approximate Nash Equilibrium in imperfect-information dynamic games[J]. Front. Comput. Sci., 2021, 15(5): 155334-.
[3]	Shuaiqiang WANG, Yilong YIN. Polygene-based evolutionary algorithms with frequent pattern mining[J]. Front. Comput. Sci., 2018, 12(5): 950-965.
[4]	Jayanthi MANICASSAMY, Dinesh KARUNANIDHI, Sujatha POTHULA, Vengattaraman THIRUMAL, Dhavachelvan PONNURANGAM, Subramanian RAMALINGAM. GPS: a constraint-based gene position procurement in chromosome for solving large-scale multiobjective multiple knapsack problems[J]. Front. Comput. Sci., 2018, 12(1): 101-121.
[5]	Maoguo GONG, Xiangming JIANG, Hao LI. Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework[J]. Front. Comput. Sci., 2017, 11(3): 362-391.
[6]	Yuan SU,Xi ZHANG,Lixin LIU,Shouyou SONG,Binxing FANG. Understanding information interactions in diffusion: an evolutionary game-theoretic perspective[J]. Front. Comput. Sci., 2016, 10(3): 518-531.
[7]	Wenjun WU, Wei-Tek TSAI, Wei LI. An evaluation framework for software crowdsourcing[J]. Front. Comput. Sci., 2013, 7(5): 694-709.
[8]	Carlos A. COELLO COELLO. Evolutionary multi-objective optimization:some current research trends and topics that remain to be explored[J]. Front Comput Sci Chin, 2009, 3(1): 18-30.
[9]	Maryjane TREMAYNE, Samantha Y. CHONG, Duncan BELL. Optimisation of algorithm control parameters in cultural differential evolution applied to molecular crystallography[J]. Front Comput Sci Chin, 2009, 3(1): 101-108.

Viewed

Full text

Abstract

Cited

Shared

Discussed