Transcript Document

The Game of Go
Two players, Black and White, take turns
• placing a stone on virtually any empty point
on a board (usually 19x19)
• or passing
Neighbouring stones of the same colour connected
along a line (but not a diagonal) share a common
fate: they form a “block”;
• they live together, or are captured together
A capture occurs when no stone in an enemy block
is neighbour to an empty point on the board.
• captured stones are removed
• it is permitted to play on the empty points
left behind after a capture
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
1
Restrictions on moves
Two rules prohibit certain moves

1. Suicide is not allowed (ok in Taiwan rules)
• You cannot play on a point if the block you
would make has no liberties (neighbouring
empty points)
• Any capture of enemy stones happens first, a 
capture will give you liberties, so not suicide
2. Repeating a previous position is not allowed
• The commonest case is “ko”, where
• opponent has just captured one stone

• if you played another stone there now, you
would capture back just that opponent stone
• then he could … you could … for ever

http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
2
Object of the game; Scoring a game
The object of the game is to control more of the
board than your opponent. There are two major
scoring systems, which almost always give the
same result (if game is played to the finish):
Japanese: each player counts the territory he
has surrounded, minus prisoners captured.
Players are expected to recognise when certain
stones on the board have no hope of survival,
and treat them as prisoners.
Chinese: each player adds the territory he has
surrounded to the stones he has on the board.
Doomed stones must actually be captured.
Territory means empty points in which the
opponent could not profitably play, any stones
he did play there would end up being captured.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
3
Phases of the game
The game in practice usually goes through four phases:
• Opening (“fuseki”)
Players lay claim first to corners, then edges of the board, typically playing
on the third and fourth lines counting from edges. It is easiest to make
territory in corners, hardest in the centre. Skilled players know many
standard sequences (“joseki”) for playing in the corners.
• Middle game (“chusan”)
Players attack each other’s groups of stones, threatening captures,
sometimes on a large scale. In attacking they also seek to exert control over
larger areas of empty points, thus building territory.
• Endgame (“yose”)
Players seek to win themselves a couple of points here, deny the opponent
a couple there. There are seldom significant captures in the endgame.
• Filling in “dame” - points of no value to either side.
• When both players pass, they then “tidy up” before counting the score.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
4
Levels of skill
Human players, amateur and professional, are ranked on a scale such that a
player at one point on the scale expects to win about 2/3 of his games against a
player one point lower.
“kyu” ranks go from 35k (absolute beginner) to 1k;
• but you quickly climb to around 16 k with a couple of dozen games
“dan” (expert amateur) go from 1d to 6d (or thereabouts);
“professional” goes from 1p to 9p; 1p  6d
me on a
good day
the very best
player I know
absolute beginners who
just know the rules
the best programs
the meijin
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
5
Handicaps
In games between equally-ranked players, chance dictates who takes Black and
goes first; White receives an allowance (komi, usu. 6.5 points) to compensate.
In friendly games between players one rank apart, the weaker one always gets
the advantage of playing Black, komi might be 0.5.
When players are two or more ranks apart, the weaker player is given free stones
at the beginning, in fixed positions, and White makes the first real move.
• The number of free stones corresponds to the difference in ranks.
• Up to nine stones are common.
• If more than nine stones are needed, usually White has to win by a margin of
10 points per extra rank difference (and usually succeeds)
• Players of radically different strengths can still enjoy a challenge.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
6
What makes Go hard for computers and AI?
High Branching factor:
• On a 19x19 board, for much of the game there are 100-350 moves
Game length:
• Games commonly last for 200-300 moves; sometimes even 350+
Difficulty of evaluation: easily the most significant:
• It is hard even to design algorithms for determining the Japanese scoring of
a game that players agree is over: one must determine which stones are dead,
either by search, by pattern recognition, or a mixture of those two.
• It is hard to design algorithms for determining that there are no more moves
worth making - i.e. that the game is over and counting should begin
• Crucially, it is hard to evaluate the worth of a position, hence the (minimax)
score for a move.
 What players want in positions has little to do with either the positions of
individual stones, or the number of prisoners captured.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
7
6d commentator says “the game is over”!
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
8
Tactical possibilities
Players must be sensitive to the tactical chances of both sides - particularly
• sequences of moves that will capture a block of stones
• sequences of moves that can make a block of stones uncapturable
Some of the many tactics for capture are
• ladders - keeping an enemy block in atari - having just one liberty - until
eventually capturing it
• nets - surrounding a block a little more loosely, so that whichever way an
escape is attempted it can be prevented.
Tactics for securing a block of stones are
• forming eyes - empty points wholly surrounded by a block. Such points can
be played by the enemy only if capturing. With two eyes, neither can be
played by the enemy because of the no-suicide rule
• making seki - a local stalemate where neither side can safely make the first
move to capture the other
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
9
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
10
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
11
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
12
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
13
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
14
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
15
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
16
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
17
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
18
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
19
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
20
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
21
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
22
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
23
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
24
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
25
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
26
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
27
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
28
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
29
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
30
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
31
Ladder example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
32
Net example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
33
Net example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
34
Net example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
35
Net example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
36
Net example
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
37
Other standard tactics
There are plenty of other tactics sufficiently commonplace to have names:
• Loose ladder; Broken ladder; Ladder Breaker
• Nets of several varieties: geta, knight’s-move, …
• Sacrifices of various kinds: Snapback, Throw-In, …
• Connections of various kinds: Bamboo joint, One-space jump, …
• Ko fight: distant threats forcing responses, bypassing the ko rule
Blocks that surround one empty area of 1-6 empty points may not be safe, some
configurations of empty space can be filled in by the opponent to kill by nakade.
Whether a block (or a group of blocks) can be captured or secured may be
determined
• Dynamically, by search of possible moves
• Statically (sometimes), using patterns and/or algorithmic analysis
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
38
Strategic elements
In addition to recognizing the opportunity/threat of tactical combinations, players
recognize and reason with various high-level concepts:
ko threat - a forcing move, played to permit a subsequent move forbidden by ko
moyos - empty areas where one player has staked a rather insecure claim
walls - (nearly) straight lines of stones bordering a (significantly) large and
(almost) empty area
semeai - capturing races where two opposing groups can only survive by killing
the other
seki - stalemates where two opposing groups can survive only because the other
cannot afford the move to make atari
shape - good shape is a property of groups of stones that can easily acquire two
or more eyes.
overconcentration - too many stones of one player in an area
sente (initiative) - freedom to initiate activity in another part of the board
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
39
Moyos and Territories
Moyo
Territory
Moyo
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
40
Planning, and Multipurpose moves
Skilful players are good at finding multipurpose moves - moves that make
progress towards fulfilling more than one goal at the same time.
• Attacking enemy stones or positions
• Securing own stones or positions
• Reducing enemy moyo or territory
• Expanding own moyo or territory
• Splitting enemy position into weak fragments to be attacked later
• Connecting own fragments into stronger, more resilient whole
A program capable of finding such moves must do planning in the AI sense:
• formulate goals, formulate plans for achieving them
• recognise opponent moves as forming part of opponent plan,
• seek moves to thwart those plans
• find moves, possibly less than optimal for any one plan, yet multipurpose
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
41
Perception of fuzzily-defined structures & relationships
Skilled players describe positions in terms of high-level concepts: some are
tactical but most are strategic, like wall, moyo, connection, sente, influence.
Recognising these is challenging for an algorithm, since many of the
relationships and structures are hard even to define except in a fuzzy way.
Recognising them when the stones involved are not yet played is harder still!
Experimental psychological studies (using think-aloud protocols; measurement
of speed & accuracy of position recall; eye-tracking etc) beginning with the early
Reitman paper, have sought to elucidate what expert players perceive, so that
algorithms can be developed to perceive the same or similar.
(Reitman, 1976: Skilled perception in Go: Deducing Memory Structures from
inter-response times. Cognitive Psychology vol 8 pp336-356)
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
42
Revertible data structures?
• Chess programs need to represent the pieces on the board, and little else.
• Chess programs with fast search methods work well when combined with
static evaluation functions that examine the locations of pieces on the board.
• Go programs appear to need to represent structures much more complex
than the stones on the board.
• Most of these structures will be unaffected by any particular move.
• Should a program use revertible data structures, which can be incrementally
updated and downdated?
 Complex coding but perhaps cheap to use in backtracking search
• Or should it build structures from scratch for every move?
 Simpler coding, less bug-prone, arguably (Wilcox) equally cheap.
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
43
Use of machine learning techniques
Computer Go is second only to Computer Chess in terms of the research and
programming effort that has been put in - with far less success.
There are numerous attempts to use machine learning, with and without neural
networks, to extract and refine the implicit knowledge of human experts.
• Go Servers (IGS, KGS, NNGS, …) allow remote players to play online,
they keep records which can be mined.
• Professional and top-level amateur games are (manually) recorded, and
commented, and distributed via internet.
If a professional played this move it must be good …
learn to predict the move the professional chose, you have learnt something!
http://csiweb.ucd.ie/Staff/acater/comp4031.html
Artificial Intelligence for Games and Puzzles
44