スライド 1

A Survey on
Computer Game Players
M1 Hirokazu Ishii
Chikayama & Taura Lab
Agenda
1.
2.
3.
Introduction
Computer Game Players in General
Computer Go Players


4.
Features of Go
Implementations
Conclusion
Introduction
Computer Game Players

Has been studied for many years
 Easy
to evaluate
 Suitable to try out various basic
technologies

Was successful in some games
 Othello,

backgammon, chess ...
Great challenges remain in some
games
 Shogi,
go, ...
Computer Game
Players in General
Game Players
 Important
factors
Recognizing
the position
Generating candidate moves
 Searching
candidate moves
 Game
tree search
 Minimax
 Alpha-beta
 Evaluating
candidate moves
 Evaluation
Selecting
function
the best move
Computer Go Players
Features of Go

Simple and clear rules
 Stones
enclosed by opponent's are taken off.
 Sizes of obtained area decide the winner.
Require both strategy
and tactics.
 One of the most
complex board games.

Difficulties of Go
Large search space
 Criteria of evaluation are not clear
 Other difficulties

 Existence
of Ko
 Obscure definition of the end of a game
…
 While
a chess program had beaten
the human champion, go programs
has stopped at an amateur level (1
Dan).
Large Search Space

Large branching factor
 Full-board

search is too costly
Decompose the board into a number
of games called subgame
Criteria of Evaluation
 A single
stone does not have its own
value.

Roles of stones changes according to
circumstances.

Influence distribution
Existing Programs

‘Gifu challenge’ is one of the most
prosperous competition.
1st
2nd
3rd
4th
5th
2003 KCC
囲碁
HARU
KA
Go++
Goe
mate
Many
Faces of
Go
2004 KCC
囲碁
彩
勝也
Go
Intellect
碁里
霧中
Result
6th
7th
GNU Neuro
Go
Go
mar
tha
MASA
YAN
Structure Description
Current position
Data structure
Candidate moves
The best move
Next position
Structure Description
Current position
Data structure
Candidate moves
The best move
Next position
Data Structure

Meaningful unit of stones
 String,

group
Other data
 Moyo,
liberty, eye, ...
String
Group
Structure Description
Current position
Data structure
Candidate moves
The best move
Next position
Generating Candidate Moves
Local evaluation
 Full-board evaluation

 Knowledge
Pattern
based
Matching
 Search
Minimax
Alpha-beta
HARUKA
Knowledge based
Fuseki routine
Joseki routine
 Search
Life-and-death search routine
Semeai search routine
Center search routine
Local search routine

HARUKA
 Data
structure
Probability of capturing stones
Probability of cutting stones
Influence distribution
Eye shape …
HARUKA

Generate candidate moves
 Alpha-beta
search
Previous opponent move
 Previous own move
 Area surrounding the point which is influenced
by two moves


Evaluate the move
 Influence
distribution
Katsunari
 Generate
candidate moves
 Knowledge
based
Shape move
 Joseki move

 Search

Life-and-death move
Katsunari

Memory-based reasoning
 Data
structure

Shape

The move which High-level human played

Emergency
 Compare

shape data with current position
Criteria of similarity



Difference of stone
Distance from candidate move to surrounding stones
Distance from candidate move to the nearest stone
Katsunari

Value of shape move
 Emergency
 Similarity
 Distance
from the nearest stone
GNU Go
 Generate
Move
candidate moves
reasons
 Attacking
and defending stones
 Cutting and connecting stones
 Making or destroying eyes
…
 Evaluate
Correct
candidate moves
move reasons
GNU Go
 Knowledge
Pattern
based
matching
 Fuseki
 Joseki
 Connecting
and cutting stones
 Search
Pattern-based
minimax search
 Life-and-death
of string and group
NeuroGo

Full-board search
 1-ply

search
Evaluation function
 Neural
network
1-ply search
NeuroGo

Input
 The
go position
 Some local features of the position
A number of stones
 A number of liberties


Output
 Probability
point
to become alive at each
NeuroGo
Example of output
NeuroGo

Learning
 Self-play
and TD (0) learning
 Backpropagation
 Reinforcement learning
Single-point eye
 Connection
 Alive

NeuroGo

Network Architecture (a number of neurons per point)




Input layer ( one or more )
 The activations is set to 0 or 1 according to whether a input
feature is true or not.
First hidden layer ( one or more )
 The number of neurons is parameter of the network
architecture.
Second hidden layer ( one or more )
 The number of neurons is parameter of the network
architecture.
Simple eyes layer ( 2 (black 1, white 1) )
 The activation is a prediction of whether that color is able to
create a single point eye at this point.
 It receives a reinforcement signal.
NeuroGo

Network Architecture (a number of neurons per point)

Local connections layer ( 18 (black 9, white 9 )



Global connectivity layer ( 2×(board size)2 )


The activation is a prediction of whether that dolor is able to create
a connection from this point to each of the 9 points in a 3×3
window around this point.
It receives a reinforcement signal.
The activation is a prediction whether each color is able to create
a connection from this point to any point on the board.
Evaluation layer ( 1 )

The activation is a prediction whether this point will be alive for
Black ( activation 1 ) or White (activation 0 ).
NeuroGo

3 connections

Receptive fields


Connectivity pathfinder


3×3 square window
centered at this point.
Creating a global
connectivity map from
local connections layer.
Connectivity-based
weight selection

Assigning weights from
global connectivity layer.
Comparison

Full board
evaluation
Local search
Local
evaluation
HARUKA
Knowledge
based
勝也
GNU Go
NeuroGo
There is no program which excels other
programs crushingly.
Conclusion
Conclusion

I introduced ...
 Brief
of general game
 System description of go
 Four go players

There is no complete solution.
 Game
tree search
 Learning
 Parallel computing

Download Report