Solving Heads-up Poker with Counterfactual Regret Minimization

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

Date

2024-04-26

Department

Major/Subject

Data Science

Mcode

SCI3095

Degree programme

Aalto Bachelor’s Programme in Science and Technology

Language

en

Pages

26

Series

Abstract

Playing poker well algorithmically has historically been a major challenge, in contrast to traditional games with perfect information. Especially heads-up poker is gametheoretically interesting, as playing a Nash equilibrium strategy guarantees the player not to lose in the long run, compared to multiplayer poker, where opponents’ suboptimal decisions may still harm the player playing in a Nash equilibrium. Focusing on heads-up poker provides insight on how to solve games with uncertainty and imperfect information. The aim of the thesis is to analyze modern algorithms and techniques utilized by computer programs trying to play heads-up poker strategies close to the Nash equilibrium strategy. The Nash equilibrium approximations are acquired after performing game abstractions to reduce the game size and after running the counterfactual regret minimization (CFR) algorithm on the abstracted game tree. The approximation this procedure produces is called an ϵ-Nash equilibrium, where ϵ indicates how much utility the opponent can gain by playing the optimal counter-strategy to the player strategy. A literature review of both the CFR algorithm and game abstractions was conducted in order to explore various proposed solutions and analyze them. Computational efficiency and implementation feasibility is crucial in real-world applications. In addition to the vanilla counterfactual regret minimization algorithm, Monte Carlo CFR and CFR+ can be utilized to speed up the process. Game abstractions must also be of such size that they do not cause computational issues. However, making the abstractions too coarse reduces the solution accuracy. When applied properly, these methods are capable of producing a poker playing program stronger than any human player. Such capabilities are remarkable, especially in the context of online poker played for money. This revolutionizes the poker landscape and marks a significant advancement in artificial intelligence. Similar methods could also be applied to different situations with imperfect information, such as negotiations.

Johtuen peliin sisältyvästä epätäydellisestä informaatiosta pokerin pelaaminen algoritmisesti on historiallisesti ollut suuri haaste peliteorian alalla. Pokerin muodoista erityisesti kaksinpeli on peliteoreettisesti kiinnostava, koska Nash-tasapainostrategiassa pelaava pelaaja ei varmasti häviä pitkällä aikavälillä. Moninpelipokerissa Nash-tasapaino ei ole yhtä merkittävässä asemassa, sillä muiden pelaajien epäoptimaaliset päätökset voivat aiheuttaa pelaajalle tappiota, vaikka tämä pelaisi Nash-tasapainostrategiaa. Näistä syistä johtuen kahden pelaajan pokeri tarjoaa mielenkiintoisia näkökulmia liittyen epätäydellisen informaation ja epävarmuuden sisältämien pelien ratkaisuun. Tämän kandidaatintyön tavoite on analysoida nykyaikaisia algoritmeja ja tekniikoita, joita tietokoneohjelmat käyttävät yrittäessään ratkaista kaksinpelipokerin Nashtasapainoaseman approksimaatioita. Nash-tasapainoaseman approksimaatiot saavutetaan kahdessa vaiheessa; ensin pelipuusta luodaan abstraktio, joka vähentää sen kokoa. Sen jälkeen abstraktoituun pelipuuhun sovelletaan counterfactual regret minimization -algoritmia (CFR), joka luo Nash-tasapainoasema-approksimaation. Tätä ratkaisua kutsutaan ϵ-Nash-tasapainoksi, missä ϵ kuvaa, miten paljon etua vastustaja voi saada pelaajan strategiaa vastaan pelaamalla optimaalisesti pelaajan strategiaa vastaan. Tutkimus suoritettiin kirjallisuustutkimuksena CFR-algoritmista ja abtraktioalgoritmeista. Kandidaationtyö tutkii erilaisia ehdotettuja ratkaisuja ja analysoi niitä. Laskennallinen tehokkuus on metodien toimimisen keskipisteessä. Abstraktioalgoritmit tulee toteuttaa siten, että pelipuu tulee riittävän pieneksi. Toisaalta abstraktion muuttaminen liian suurpiirteiseksi vähentää ratkaisun tarkkuutta. Myös CFR-algoritmista voi olla tarpeellista käyttää optimoituja versioita, kuten Monte Carlo CFR- tai CFR+-algoritmeja. Oikein toteutettuna näiden metodien käyttäminen mahdollistaa ihmispelaajaa vahvemman pokeritekoälyn luomisen. Tämä on merkittävää, sillä pokeria pelataan rahasta. Sen lisäksi että työllä on merkittäviä vaikutuksia pokeriin itsessään, merkitsee se myös merkittävää edistystä tekoälyn alalla ja epätäydellisen informaation pelien ratkaisemissa. Samankaltaisia metodeja voi olla mahdollista hyödyntää myös muissa epätäydellisen informaation tilanteissa, kuten neuvotteluissa.

Description

Supervisor

Korpi-Lagg, Maarit

Thesis advisor

Rintanen, Jussi

Keywords

artificial intelligence, counterfactual regret minimization, game theory, poker

Other note

Citation

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202406184534

Collections

[kand] Perustieteiden korkeakoulu / SCI