[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
On Game Space Size
I will try to answer the questions I got in the last few mails now...
----------------------------------------------------------------------------------
Avijit: How are you generating your configurations ?
Answer:
I define the number of black and white stones and the boardsize.
After that I make an empty board of boardsize x boardsize.
Then I randomly pick a specified number of vertices to put the black stones on.
Then I randomly pick a specified number of vertices to put the white stones on.
Futhermore there are no 'moves' involved when trying to estimate the game space.
In my definition the game space is the number of states a go-board can be in. Every legal configuration of stones on the board that theoretically can be created using the rules of go is a board state.
For the people who didn't lose me yet:
This definition does not hold anymore if Ko is involved (because the fact whether a Ko may be recaptured depends on history and would need two states per Ko (namely one in which recapturing is legal and one in which it is not.) Also should the number of board positions be doubled because it is white or black his turn.
----------------------------------------------------------------------------------
Avjit: Do you have to flood the board or just check to see if there are pieces on the board that have no liberties.
Answer: Flooding the board is one way to check whether there are pieces that have no liberties :-) But that is indeed the only thing you need to do.
----------------------------------------------------------------------------------
Imrich: I have a contra-example - the position with only one white stone. This is legal according to logic above, but it is not possible to get it because black starts move.
Answer: In theory it is possible to get it since black is allowed to pass on the first move and since all black stones just may have been captured... (Indeed those positions will never occur but they belong to the Game Space.)
----------------------------------------------------------------------------------
In response to the map I create (Imrich and Mousheng)
It is indeed 4Dimensional
Size of the board
number of black stones
number of white stones
percentage of legal states
This can be transformed to many other maps ofcourse.
----------------------------------------------------------------------------------
Imrich: Generating of config. For each place pick randomly (-1,0,1)
This would (considering a uniform distribution of random picks) give
a board with about the same number of black white and empty positions and would therefore not be fit for generating a map. As explained in an earlier email I suppose one may use it to estimate the total Game Space.
----------------------------------------------------------------------------------
Imrich Evaluation of configuration.
Comments:
> Generate random configuration 'C'
> In 'C' flood empty positions into white positions
> If any white stays
> 'C' is illegal (1)
> else
> In (initial !)'C' flood empty positions into black positions
The initial is not nescessary because if initial 'C' <> 'C' the position
is regarded illegal by (1)
> If any black stays
> 'C' is illegal (2)
> else
> 'C' is considered as legal (3) // I will have note for this
> end if;
> notes:
> Some configurations can be legal for black on move but
> illegal for wihe on move.
As I already (tried to) explained in the answer to Avjit
I consider the Game Space to be the set of board positions and
do not regard Ko. Indeed if a configuration arises that (based on history) has a different set of legal moves for black and white this would enlarge the Game Space.
i.e. One Ko board-configuration would mean Two states in Game Space.
---------------------------------------------------------------------------------
Imrich:
> Also there could be configurations diferent numbers of stones
> for each color but with no mark of capturing (enclosed path...).
Let's assume Chinese (?) rules so that the number of captured stones is not important.
---------------------------------------------------------------------------------
Imrich:
>I think we can use results of Pietar's method as upper bound
>and try to found some additional validations fo reduce (3).
since the number of game space states will rise if Ko is accounted for my method will probably not give an upper bound :-(
-----------------------------------------------------------------------------------------------
John Aspinall
> (1) How can I get unbiased samples from my Monte Carlo simulation?
> Question 1 is the hard one. The danger is that the way you initialize your
> Monte Carlo sampler will bias the samples. The best answer is to use Propp
> and Wilson's "coupling from the past" technique to produce unbiased
> samples. You can get copies of their articles from
> http://www-math.mit.edu/~propp/articles.html .
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.
------------------------------------------------------------------------------------------------
Mousheng
> Just a minor question: when do you know you can stop while doing random
> sampling in Monte Carlo? Suppose I know a little about statistics. :)
Well, I'm not a great statistician either ;-) but I stop when the calculated percentage doesn't change anymore. (i.e. if the current percentage doesn't differ more than 'dp' from the 'x' previously calculated values.)
Remember that it is just an estimate.
Is there anyone who knows a decent link to a good explanation of Monte Carlo-Methods ?
------------------------------------------------------------------------------------------------