Re: On Game Space Size

[John Aspinall <jga@xxxxxxx>]

>Question :
>What exactly do you mean by "biased samples" ?
>I suppose it is about creating board situations that cannot be created
>during a real game ?
>My hypothesis is that, since passing is allowed although not recommended,
>any boardsituation in which there are no stones without liberties can be
>reached.
>Of course it is usefull to know how many board situations there are that
>are reachable through "common sense" but that is an extremely hard thing
>to do.

Monte Carlo is a way of sampling from a very large space.  The idea is that
you want some integral, or sum, over that large space, but the space is
much too large to exhaustively cover the space.  So you sample from the
space instead of trying to visit every point.  You know this, obviously.

Markov Chain Monte Carlo is a type of Monte Carlo technique where a Markov
process generates a random walk through the space.  It's used when
generating points from the space is hard, but once you have one point, you
can easily find a neighboring point.  There's a lot of work right now on
Markov Chain Monte Carlo.  A web search will give you lots of good hits.

So if our space is: the space of all possible assignments of {black, white,
empty} to each element of a 19x19 array; then sampling from this space is
easy.  The procedure you've described is a fine sampler.  You are not doing
a random walk, and my comment doesn't apply.  Sorry for misleading, but
perhaps this is useful for further work.

But note that the definition of the space above knows NOTHING about the
rules of Go.  The expectation value - number of legitimate board positions
- does refer to the rules of Go.  But the total space doesn't use the rules
of Go in its definition.  Now various members of this list have brought up
questions like "what about ko?" and "what about games where the number of
white stones on the board is significantly different from the number of
black stones on the board?" and your own point about "it is useful to know
how many board situations there are that are reachable through `common
sense'".

One way to interpret these questions is that the questioners want a
different sample space.  If the definition of the space from which we
sample employs the rules of Go, then it may be that a sampling procedure
might want to employ a random walk.

In case you're still interested, here's the answer to your question:

Nearly every Markov process has a single equilibrium distribution.  An
UNbiased sample is where the sample distribution equals the equilibrium
distribution.  A biased sample is where there's a difference between the
two.


John Aspinall
IS Robotics, Inc.
http://www.isr.com/