IEEE Spectrum July, 2014 - 52

The Games Computers Play
In two-player games
without chance or hidden
information, AIs have
achieved remarkable
success. However,
19-by-19 Go, with its
staggering array of
possible game positions,
remains a challenge.

Tic-Tac-Toe

oware

checkers

oThello

Game positions:
computer strength:

10
PerfecT

10
PerfecT

10
PerfecT

10 28
suPerhuman

9-by-9 Go

chess

XianGqi

shoGi

19-by-19 Go

10 38
besT
Professional

10 45
suPerhuman

4

11

(C h I n E SE C h E S S)

( J A PA n E SE C h E S S)

10 48
besT
Professional

10 70
sTronG
Professional

node of the search tree), select a candidate move (a leaf node)
for evaluation. At the very beginning of the search, the leaf node
is directly connected to the root. Later on, as the search deepens, the program follows a long path of branches to reach the
leaf node to be evaluated.
2. Simulation: From the selected leaf node, choose a random sequence of alternating moves until the end of the game
is reached.
3. Evaluation and back propagation: Determine whether the simulation ends in a win or loss. Use that result to update the statistics
for each node on the path from the leaf back to the root. Discard
the simulation sequence from memory-only the result matters.
4. Tree expansion: Grow the game tree by adding an extra
leaf node to it.
An MCTS-based program needs some intelligent way to select
which branches of the game tree to grow. Good policies for doing
that strike a balance between exploration (branching off nodes
with few simulations and therefore high uncertainty about their
prospects for leading to a win) and exploitation (pursuing moves
that branch off the most promising nodes).
52

|

jUl 2014

|

nORTh aMERICan

|

SPECTRUM.IEEE.ORG

20

10 172
sTronG
amaTeur

The best policies for expanding the tree also rely on a
decision-making shortcut called rapid action value estimation (RAVE). The RAVE component tells the program to collect another set of statistics during each simulation. If the
random sequence of moves results in a win, every grid point
where the program placed one of its stones (thus roughly
half the locations on the board) is given a numerical bonus.
In this quick and dirty method, each board location accumulates a RAVE statistic as simulations are played out. Then,
when the program is considering a move, it can look at both
the win-loss statistic for that move as well as the RAVE statistic for that location.
These policies control the selective growth of the game tree.
In typical MCTS programs, this growth is uneven: Promising
lines of play are explored much more deeply than other lines.
Because the search tree is grown one node at a time, the algorithm can be stopped at any time, and it will return the best
move found so far.
Determining the best move is tricky, however. The most
natural approach would be to pick the move with the highest



http://SPECTRUM.IEEE.ORG

Table of Contents for the Digital Edition of IEEE Spectrum July, 2014

IEEE Spectrum July, 2014 - Cover1
IEEE Spectrum July, 2014 - Cover2
IEEE Spectrum July, 2014 - 1
IEEE Spectrum July, 2014 - 2
IEEE Spectrum July, 2014 - 3
IEEE Spectrum July, 2014 - 4
IEEE Spectrum July, 2014 - 5
IEEE Spectrum July, 2014 - 6
IEEE Spectrum July, 2014 - 7
IEEE Spectrum July, 2014 - 8
IEEE Spectrum July, 2014 - 9
IEEE Spectrum July, 2014 - 10
IEEE Spectrum July, 2014 - 11
IEEE Spectrum July, 2014 - 12
IEEE Spectrum July, 2014 - 13
IEEE Spectrum July, 2014 - 14
IEEE Spectrum July, 2014 - 15
IEEE Spectrum July, 2014 - 16
IEEE Spectrum July, 2014 - 17
IEEE Spectrum July, 2014 - 18
IEEE Spectrum July, 2014 - 19
IEEE Spectrum July, 2014 - 20
IEEE Spectrum July, 2014 - 21
IEEE Spectrum July, 2014 - 22
IEEE Spectrum July, 2014 - 23
IEEE Spectrum July, 2014 - 24
IEEE Spectrum July, 2014 - 25
IEEE Spectrum July, 2014 - 26
IEEE Spectrum July, 2014 - 27
IEEE Spectrum July, 2014 - 28
IEEE Spectrum July, 2014 - 29
IEEE Spectrum July, 2014 - 30
IEEE Spectrum July, 2014 - 31
IEEE Spectrum July, 2014 - 32
IEEE Spectrum July, 2014 - 33
IEEE Spectrum July, 2014 - 34
IEEE Spectrum July, 2014 - 35
IEEE Spectrum July, 2014 - 36
IEEE Spectrum July, 2014 - 37
IEEE Spectrum July, 2014 - 38
IEEE Spectrum July, 2014 - 39
IEEE Spectrum July, 2014 - 40
IEEE Spectrum July, 2014 - 41
IEEE Spectrum July, 2014 - 42
IEEE Spectrum July, 2014 - 43
IEEE Spectrum July, 2014 - 44
IEEE Spectrum July, 2014 - 45
IEEE Spectrum July, 2014 - 46
IEEE Spectrum July, 2014 - 47
IEEE Spectrum July, 2014 - 48
IEEE Spectrum July, 2014 - 49
IEEE Spectrum July, 2014 - 50
IEEE Spectrum July, 2014 - 51
IEEE Spectrum July, 2014 - 52
IEEE Spectrum July, 2014 - 53
IEEE Spectrum July, 2014 - 54
IEEE Spectrum July, 2014 - 55
IEEE Spectrum July, 2014 - 56
IEEE Spectrum July, 2014 - 57
IEEE Spectrum July, 2014 - 58
IEEE Spectrum July, 2014 - 59
IEEE Spectrum July, 2014 - 60
IEEE Spectrum July, 2014 - 61
IEEE Spectrum July, 2014 - 62
IEEE Spectrum July, 2014 - 63
IEEE Spectrum July, 2014 - 64
IEEE Spectrum July, 2014 - 65
IEEE Spectrum July, 2014 - 66
IEEE Spectrum July, 2014 - 67
IEEE Spectrum July, 2014 - 68
IEEE Spectrum July, 2014 - Cover3
IEEE Spectrum July, 2014 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1217
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1117
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1017
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0917
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0817
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0717
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0617
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0517
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0417
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0317
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0217
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0117
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1216
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1116
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1016
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0916
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0816
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0716
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0616
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0516
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0416
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0316
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0216
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0116
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1215
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1115
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1015
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0915
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0815
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0715
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0615
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0515
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0415
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0315
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0215
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0115
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1214
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1114
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1014
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0914
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0814
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0714
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0614
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0514
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0414
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0314
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0214
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0114
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1213
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1113
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1013
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0913
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0813
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0713
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0613
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0513
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0413
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0313
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0213
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0113
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1212
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1112
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1012
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0912
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0812
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0712
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0612
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0512
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0412
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0312
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0212
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0112
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1211
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1111
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1011
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0911
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0811
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0711
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0611
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0511
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0411
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0311
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0211
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0111
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1210
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1110
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1010
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0910
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0810
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0710
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0610
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0510
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0410
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0310
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0210
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0110
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1209
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1109
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1009
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0909
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0809
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0709
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0609
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0509
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0409
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0309
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0209
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0109
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1208
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1108
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1008
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0908
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0808
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0708
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0608
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0508
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0408
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0308
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0208
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0108
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1207
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1107
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_1007
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0907
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0807
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0707
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0607
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0507
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0407
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0307
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0207
https://www.nxtbook.com/nxtbooks/ieee/spectrum_na_0107
https://www.nxtbookmedia.com