The Most Recent Milestone
While both chess and Go have their own respective
levels of complexity, they both involve perfect infor-
mation. In other words, both players can see all the
pieces on the board at all times. The game of heads-up
(or two-player), no-limit Texas Hold'em, on the other
hand, is a game of imperfect information. A player
cannot see the two face down cards dealt to the other
player and the three cards turned up over the three
rounds of play after the deal are unknown. To provide
a sense for this complexity, when you're dealt into a
game, the cards you're dealt and the communal cards
that appear are one possibility of 10^160. That's one
followed by 160 zeroes, or more than the number of
atoms in the universe. This represents a problem that
cannot readily be brute-forced by simply throwing
compute power at it.
Around the same time that AlphaGo Master was mak-
ing strides against its predecessor AlphaGo Lee in
January 2017, an AI program named Libratus was pit-
ted against four top human poker players - Jason Les,
Dong Kim, Daniel McAulay and Jimmy Chou. After 20
days of play and 120,000 hands of poker, Libratus
emerged as the winner.
Carnegie Mellon Professor Tuomas Sandholm and his
graduate students developed Libratus as a successor
to a prior version called Claudico (originally called
Tartanian). Libratus used three different approaches
that worked together, and this was its key
differentiator.
First, it used a technique called reinforcement learn-
ing in which the program used random trial and error
to learn by playing a game against itself, via an algo-
rithm known as counterfactual regret minimization.
Note that this technique appears to have subse-
quently been adopted by the latest versions of
AlphaGo (AlphaGo Zero and AlphaZero). The tech-
nique ends up testing such a wide range of approaches
that it finds some optimized strategies that humans
would otherwise not think to try. In certain cases,
this actually ended up throwing human opponents off.
AlphaGo is a more com-
plex game than chess
with a 19x19 board and
the added complexity of
pieces being flipped
when surrounded by
an opponent's stones.
SPRING
2018 | THE DOPPLER | 39