IEEE Spectrum - North American - March 2015 - 16

number of bet raises. But the software is still good enough to make
it virtually impossible-from a statistical significance standpoint-
to distinguish the algorithm's
solution from perfect play during a lifetime of poker games.
The algorithm, named CFR+ by
its creators, uses an improved
version of a technique called
counterfactual regret minimization (CFR). Regret-minimization
algorithms are easiest to understand for a single-step game, such
as rock-paper-scissors. They compare the outcome of a game, say,
how much money you lost, with
t he outcome of t he best possible choice. The difference is
the regret value. The algorithm
then comes up with a strategy-
expressed as the probabilit y
that you'll make a certain move-
for the next time you play that
minimizes the total regret for
all the times you've ever played.
Counterfactual regret minimization extends the process to work
for games like poker where there
are many steps between the start
and finish of the game. And CFR+
boosts the efficiency of the process by taking fewer and bigger
steps toward the best solution.
Past CFR algorithms never tried
solving the full game of heads-up
limit Texas Hold 'em because of
the huge amount of memor y
required-roughly 262 terabytes.
But CFR+, helped along by some
memory compression techniques,
was efficient enough to solve the
full game.
The next big challenge is trying
to solve heads-up no-limit Texas
Hold 'em, a more complex version
that allows unrestricted bet sizes.
Algorithms must consider many
more information sets that each

The Sandholm
group's AI
showed its
worth by
beating the
best rival
poker-playing
programs, at
a competition
in 2014.

MaR 2015

nORTh aMERICan

represent the possible moves
made by opponents at each stage
of the game. The difference in
the number of information sets
is huge-about 147 orders of magnitude. For that reason, researchers cannot hope for an algorithm
that can sort through every single possible play. Instead, they
fall back on using "abstractions"-
simplified representations of the
full game.
A Carnegie Mellon University
group led by Tuomas Sandholm
has developed a computer prog ram capable of handling an
ab st r ac t ver sion of no -l i m it
Texas Hold 'em that is six times
as large as any previous abstraction of the poker game. In fact,
it may be the largest imperfectinformation game ever attempted
by a computer.
Carnegie Mellon's abstraction
algorithm works by breaking
the abstract game into smaller
pi e c e s a nd s pre ad i n g t he m
across different blade servers in
the Blacklight supercomputer at
the Pittsburgh Supercomputing
Center-a 37-teraflops machine.
One "parent" part of the abstraction exchanges information with
the smaller pieces on other servers. That allows the team to create a much larger abstraction than
if it was all located on one server.
It's also about three times as fast
as spreading the abstraction
across many servers that must all
communicate with one another.
Once the CFR algorithm analyzes the abstract game and develops a poker-playing strategy, a
reverse-mapping algorithm is
needed to apply that strategy back
to the full version of no-limit Texas
Hold 'em. Sandholm's group developed such an algorithm-called
pseudo-harmonic mapping-
which can reduce the possibility of exploits by opponents
who take an action that is not
covered by the abstraction.
The Sandholm group's AI
showed its worth in 2014 by
beating the best rival pokerplaying programs. It's not a
solution for no-limit Texas
Hold 'em, but it's still useful.
"The algorit hms we developed are not for solving poker;
they're for solving imperfectinformation games in general,"
Sandholm says. "Poker is a
benchmark where we can test
progress from year to year."
-jer em y hsu

SPECTRUM.IEEE.ORG

Microgrids
for a postfukushiMa
Japan
three projects use diverse
energy sources to supply
power during disasters
before the fukushima earthquake and tsunami four years
ago this month, Toyota's
automotive plant in Miyagi
Prefecture, north of Fukushima, had
relied entirely on the Tohoku Electric Power Co.
for energy. But when the disaster shut down power
to its plant for two weeks, managers realized that
the company needed a more secure source. The
factory couldn't be independent of the electric
grid, but it could manage that energy better-
and supplement it.
"The earthquake was a big turning point," says
Atsuji Morita, a project manager for Toyota. "We
had this big blackout and realized we needed a new
system to increase our energy security."
That's a common theme in Japan these days. After
the disaster knocked out power to much of eastern
Japan, smart microgrid projects from industrial to
residential changed their approach. Initially focused
primarily on energy efficiency, projects have shifted
the emphasis to generating energy where it is consumed and to having a diversity of power sources.
In February 2013, Toyota formed a limited liability partnership called the Factory Grid, or F-Grid,
to create a smart grid that manages and provides
supplemental power to seven factories (most of
them owned by Toyota) within the industrial park.
F-Grid has built its own natural-gas-fired cogeneration plant, which produces 7,800 kilowatts. That
plant is supplemented by 740 kW from solar panels.
And, in a creative twist, the factory uses an array
of old Prius batteries capable of adding 90 kW of
power from energy stored during slow periods at
the industrial park. In an outage, even if all other

http://SPECTRUM.IEEE.ORG

Table of Contents for the Digital Edition of IEEE Spectrum - North American - March 2015