General Game Playing with Incomplete Information using Zero-Suppressed Decision Diagrams

Abstract

The field of General Game Playing is concerned with creating AI agents capable of playing any game given only its rules. Traditionally General Game Playing has been mostly concerned with complete-information games. Recently work has been done to extend the field to games with incomplete information, but playing these games is much more challenging because the amount of information to keep track of can grow quickly. We describe and implement a new technique for representing the information set of incomplete information games using Zero Suppressed Decision diagrams to reduce the amount of memory needed, as well as a technique for reasoning directly on these data structures. The results are promising, but require further refinement to become practical for playing most games.