KrwEmd: Revising the Imperfect-Recall Abstraction from Forgetting Everything
This addresses a domain-specific challenge in game AI for imperfect-information games, offering a novel solution to enhance performance.
The paper tackles the problem of excessive abstraction in imperfect-information games like Texas hold'em, which impairs AI performance, by introducing KrwEmd, an algorithm that uses k-recall winrate features and earth mover's distance to cluster infosets, resulting in significant improvements in AI gameplay.
Excessive abstraction is a critical challenge in hand abstraction-a task specific to games like Texas hold'em-when solving large-scale imperfect-information games, as it impairs AI performance. This issue arises from extreme implementations of imperfect-recall abstraction, which entirely discard historical information. This paper presents KrwEmd, the first practical algorithm designed to address this problem. We first introduce the k-recall winrate feature, which not only qualitatively distinguishes signal observation infosets by leveraging both future and, crucially, historical game information, but also quantitatively captures their similarity. We then develop the KrwEmd algorithm, which clusters signal observation infosets using earth mover's distance to measure discrepancies between their features. Experimental results demonstrate that KrwEmd significantly improves AI gameplay performance compared to existing algorithms.