Monte carlo tree search with transposition detection and probabilistic inference for the card game of hearts

Abstract

This work presents a Monte Carlo Tree Search (MCTS) algorithm for the imperfect information card game of Hearts. The algorithm introduces a novel mechanism specifically tailored to Hearts to detect transpositions of information sets, grouping nodes that, despite having different card distributions, follow the same general strategy. This significantly reduces computational redundancy. Additionally, it applies probabilistic inference to estimate the opponent’s cards using historical data from thousands of self-play games, enabling more accurate predictions of hidden information. Experimental tests were conducted in a controlled environment to evaluate the impact of these enhancements on performance, and on the PlayOk website against experienced human players. The results demonstrate the algorithm’s high-level performance, with potential for future applications in competitive AI for imperfect-information games.

Este trabalho apresenta um algoritmo de Monte Carlo Tree Search (MCTS) para o jogo de cartas com informação imperfeita Hearts. O algoritmo introduz um mecanismo inovador, especificamente adaptado para Hearts, para detectar transposições de conjuntos de informação, agrupando nós que, apesar de possuírem distribuições de cartas diferentes, seguem a mesma estratégia geral. Isso reduz significativamente a redundância computacional. Além disso, aplica inferência probabilística para estimar as cartas dos oponentes usando dados históricos de milhares de jogos jogados contra si mesmo offline, permitindo previsões mais precisas sobre as informações ocultas. Testes experimentais foram conduzidos em um ambiente controlado para avaliar o impacto dessas melhorias no desempenho e no site PlayOk contra jogadores humanos experientes. Os resultados demonstram o desempenho em alto nível do algoritmo, com potencial para aplicações futuras em IA competitiva para jogos de informação imperfeita.