AI for Gin Rummy: Applying Counterfactual Regret Minimization in Imperfect Information Games

Abstract

Spill med ufullstendig innformasjon er en kategori spill der spillerne ikke har tilgang til all informasjon om den nåværende spill-statusen. I motsetning til spill med fullstendig innformasjon som sjakk, introduserer spill med ufullstendig innformasjon et ekstra lag av kompleksitet ved å kreve avgjørelser basert på begrensede observasjoner. Noen vanlige eksempler er kortspill som poker, der kortene i kortstokken eller motstandernes hender er ukjent. Disse spillene byr på unike utfordringer når man skal utvikle kunstig intelligens-agenter, ettersom løsninger må utformes for å håndtere usikkerhet og mangel på fullstendig informasjon effektivt.

Denne oppgaven fokuserer på å utvikle en spill-agent for gin rummy som er inspirert av en toppmoderne algoritme for "counterfactual regret minimization"(CFR). Gitt det ekstremt store tilstandsrommet som fører til et stort spilltre, i gin rummy kan vanlig CFR ikke brukes uten modifikasjoner. Derfor utforsker dette arbeidet ulike forenklings- og abstraksjonsmetoder for å redusere spilltreets kompleksitet uten å miste viktig innformasjon om spillet. I tillegg undersøker oppgaven integrering av nevrale nettverk for å komplementere den CFR-baserte tilnærmingen, og potensielt forbedre agentens ytelse. Flere enklere algoritmer ble implementert og brukt som benchmarks for hovedagenten.

Imperfect information games are a category of games in which players have incomplete information about the current state of play. Unlike perfect information games such as chess, where all game states are fully visible to all players, imperfect information games introduce an additional layer of complexity by requiring decisions based on limited observations and beliefs. Classic examples include card games like poker, where players do not know the unseen cards in the deck or their opponents' hands. These games present unique challenges for developing artificial intelligence agents, as solutions must be designed to handle uncertainty and the lack of complete information effectively.

This thesis focuses on developing an agent for gin rummy inspired primarily by a state-of-the-art counterfactual regret minimization (CFR) algorithm. Given the extremely large action state space and resulting game tree in gin rummy, vanilla CFR cannot be directly applied. Therefore, this work explores various simplification and abstraction methods to reduce the game tree's complexity without losing essential game aspects. Additionally, the thesis examines integrating neural networks to complement the CFR-based approach, potentially enhancing the agent's performance. Several simpler algorithms were implemented throughout the project and used as benchmarks for the main agent.