1 of 35

Go:

The Deepest Game

Peter Drake, Lewis & Clark College

2 of 35

Overview

  • The game of Go
  • The challenge
  • Traditional methods
  • Monte Carlo tree search
  • Enhancements

3 of 35

The game of Go

4 of 35

The elements

  • The board is initially empty
  • Black plays first
  • To play, place a stone on an intersection

5 of 35

Capturing

  • A contiguous group of stones with no liberties is removed
  • Suicide is illegal, but a move that captures something is not suicide

6 of 35

Where can black capture?

7 of 35

Play Capture Go

  • The first player to capture anything wins

8 of 35

Territory

9 of 35

Passing and scoring

  • You may pass (giving the opponent a prisoner) instead of placing a stone
  • Two consecutive passes ends the game, but white must pass last
  • Score is <territory> - <stones lost>

10 of 35

The ko rule

  • It is illegal to repeat a previous board state

11 of 35

Where should black play?

12 of 35

Rules summary

  • Black plays first
  • On a turn, place a stone or pass
  • A group with no liberties is captured and removed
  • Suicide is illegal
  • It is illegal to repeat a previous board state
  • Two passes ends the game
  • White passes last
  • Score = territory - stones lost
  • High score wins

13 of 35

Life and death

14 of 35

Can black live?

15 of 35

The challenge

16 of 35

Why is this so hard?

  • Estimating the score is difficult
  • The space is … vast

​

​

17 of 35

When you say “vast”...

3361 ≅10172

​

There are about 1080 atoms in the universe.

​

Also, Go is PSPACE-complete.

18 of 35

Minimax search

19 of 35

Variations on minimax

  • Alpha-beta pruning
  • Static evaluation
  • Move suggestion

20 of 35

Janice Kim vs Handtalk

  • “Weak” professional player
  • 25-stone handicap
  • Winner: human

21 of 35

Monte Carlo methods

22 of 35

The k-armed bandit

23 of 35

UCB: Upper Confidence Bounds

24 of 35

One-ply Monte Carlo search

25 of 35

Monte Carlo tree search

26 of 35

Kim Myungwan vs MoGo

  • Strong pro
  • 800 processor cores
  • 9-stone handicap
  • Winner: computer

27 of 35

Go ranks

9 dan professional (top player)

...

1 dan professional

9 dan

…

1 dan (“black belt”)

1 kyu

2 kyu

…

29 kyu

30 kyu (absolute beginner)

28 of 35

Recent history of program strength

29 of 35

Local search

30 of 35

RAVE: Rapid Action Value Estimation

31 of 35

The last good reply

  • For choosing moves beyond the tree
  • If it worked last time, do it
  • Variations: 2 moves, forgetting

32 of 35

Patterns

33 of 35

Bloom filters

34 of 35

Where to learn more

  • American Go Association (usgo.org)
  • Browne, et al., “A Survey of Monte Carlo Tree Search Methods,” IEEE Transactions on Computational Intelligence and AI in Games, vol.4, no.1, pp.1-43, March 2012
  • https://sites.google.com/a/lclark.edu/�drake/research/orego

35 of 35

Acknowledgments

  • Funding
    • Willamette Valley REU-RET Consortium for Mathematics Research (NSF)
    • John S. Rogers Science Research Program (Lewis & Clark)
  • Cardboard Go sets: American Go Foundation
  • Images
    • Wikipedia
    • BoardGameGeek
    • xkcd
    • American Go E-Journal
    • Microsoft Research
    • Adam Smith
    • Peter Shotwell