Recently, Koller and Pfeffer [15] [16] have developed Gala, a system for automating game-theoretic analysis for two-player competitive games with imperfect information. The system takes a description of a game, analyzes it, and outputs strategies for the different players which are game-theoretically optimal for the situation described. The implementation is composed of two main interacting pieces: a special-purpose game specification language, and an automatic game-theoretic analyzer for games in extensive form. The extensive form represents the games as a tree with the information sets (players' knowledge states) indicated.
For games with imperfect information, the system finds an optimal randomized strategy. The system can now solve simplified versions of two-player poker (e.g. 3-card deck, 1 card dealt to each player, 3 rounds; or 11-card deck, 5 cards each player, 3 rounds). However, the authors state that:
``While we can now solve games with tens of thousands of nodes, we are nowhere close to being able to solve huge games such as full-scale poker, and it is unlikely that we will ever be able to do so. A game tree for five-card draw poker, for example, where players are allowed to exchange cards, has over 1025 different nodes. The situation (for zero-sum games) is now quite similar to that of perfect-information games: We have algorithms that are fairly efficient in the size of the game tree; unfortunately, the game tree is often extremely large.'' [16]