 |
Reinforcement Learning and
Artificial
Intelligence (RLAI)
|
Segmentation
|
The ambition of this web
page is to define the problem of Segmentation in Computer Go.
Definitions:
A region is a set of
intersections on the Go board (for example a string, group or
territory).
Segmentation is the process of
dividing up the Go board into regions. At the end of the game, the
board is (usually) fully segmented. The accuracy of segmentation can be
measured by comparing the predicted regions with the actual, final
regions.
Another way of thinking about segmentation is the correlation between intersections of
the Go board. Segmentation attempts to cluster together highly
correlated intersections:
- Stones of the same colour are correlated if they will be
connected together at the end of the game (for example strings, chains
or groups).
- Empty intersections are correlated if they will belong to the
same enclosed region at the end of the game (for example eyes or
territories).
Types of segmentation:
Hard segmentation divides
the Go board up into a disjoint set of regions. Each intersection of
the Go board can only belong to a single region [for each segmentation
- we may choose to apply separate segmentations at e.g. string, chain,
group level]. This corresponds to a 'definite' view of the Go board,
where regions are well-defined and should be calculable.
Soft segmentation divides
the Go board up into an overlapping set of regions. Each intersection
of the Go board can belong to multiple regions. This corresponds to an
'uncertain' view of the Go board, where regions are badly defined,
fuzzy, and difficult to calculate accurately.
Explicit segmentation
generates a labelled set of regions during segmentation. The labelled
regions can then be referred to elsewhere in the Go program (for
example to ask the status of a particular group).
Implicit segmentation
doesn't actually generate a set of regions, and does not provide any
mechanism to refer to individual regions elsewhere in the program.
Instead segmentation is considered an implicit part of the question
asking process (see questions),
and a scope must be specified for
each question asked (see below).
Scope:
The scope M
of
a policy restricts the set of moves that will be considered by that
policy. We can define different scopes:
MD(x) is the set of moves
at intersections within a fixed distance D from an intersection x.
Mσ(x,g) is the set of moves
at intersections which are correlated
with x above a correlation threshold value of σ, using the correlation
function g. For example, if σ = 0.99 then the scope about a black stone
would only consider those intersections
that are 'definitely' connected with the stone.
MD,σ(x,g)
is the set
of moves at intersections within a fixed
distance D from any intersections that are correlated with x above a
correlation threshold value of σ, using the correlation function g. For
example, if σ = 0.99 then the scope about a black stone would only
consider
those intersections that are within D of an intersection that is
'definitely' connected with the black stone.
The scope operator assumes that we can estimate the correlation between
any two intersections.
