Hmmm, that's interesting but for random playouts seems a bit overkill.
In a random playout kos will only consistently happen if they are the
last legal positions in the board, at which point it might be better
just waiting for a few more plays, reaching the max depth and calling
the score as it is. Testing simple kos should be faster too. Did you
benchmark the difference between your method and just prohibiting play
at the last eaten position (if one stone only)? What max depth (if any)
did you use to limit the playouts?
For hashing I use 64 bit Zobrist hashes of the board contents without
last played/eaten information, so it is not changed by passing. On
collision I memcmp the whole board; if I didn't play legality would be
off in false eyes, kos, suicides, etc and I store that in the node
statistics. Btw does anyone have a good initialization vector for the
Zobrist table?
Gonçalo
On 16/10/2015 13:50, Ben Ellis wrote:
My go playing program mostly just does random play outs so I don't claim to
be an expert, but I check for super KO in my go program and it doesn't seem
to slow it down too much. I use the same algorithm for checking for simple
KO as well.
*This doesn't catch 100% of super KO but it is good enough to prevent
looping in your play-outs.*
From memory, the high-level algorithm,
At the start of the play out, start with
- HashSet of board hashes
- HashSet of board intersections (pre-populated with all board
intersections)
After each move has been played and captured stones removed,
1. If the played intersection has not been played on before,
- empty the board hashes set. O(1)
2. If any stones were captured and the intersection has not been played
before,
- Generate hash O(1)
- Insert hash into set of board hashes. O(1)
3. If the intersection has been played on before,
- Generate hash O(1)
- Insert hash into set of board hashes and check for duplicate O(1)
- If duplicate, KO or super KO detected O(1)
4. Remove intersection from set of intersections not yet played. O(1)
Conditions at 2 and 3 are infrequent and tend to only happen in the end
game.
Zobrist hash is common I'm not sure of any alternatives.
If you want to check for all moves that would result in a KO or super KO,
you can iterate through all the empty intersections that have already been
played (there usually aren't many unless a big dragon is captured), and see
if they would cause a duplicate hash.
I'm sure someone more academic than me on this list will be able to pick
plenty of holes out of this :)
On 31 August 2015 at 09:18, <valky...@phmp.se> wrote:
I once tried to use 32bit hashes only. It might work for super ko
detection, but if you use it for transposition detection storing a lot of
poisitions you will get collisions now and then. So my reasoning is: if 32
bits almost works then using another 32 bits will work.
Best
Magnus
On 2015-08-31 06:26, Minjae Kim wrote:
Is 64 bits really enough?
I may be wrong but there are 3^361 possible board positions in 19x19.
log2(3^361) gives me 572.171..., which means I need at least 573 bits
to record all possible board positions. This still doesn't mean that a
2048 bit Zobrist hash for example will never collide for a 19x19
board, but the odds will be significantly lesser.
Do you have some source about the probability of Zobrist hash
collision on a go board for different bit string sizes?
On Mon, Aug 31, 2015 at 12:37 PM, Peter Drake <dr...@lclark.edu>
wrote:
64 bits seems to be enough. As I understand it, the convention is to
simply _ignore_ the possibility of collisions; you're more likely to
have a hardware error.
On Sun, Aug 30, 2015 at 8:27 PM, Minjae Kim <xive...@gmail.com>
wrote:
To my understanding, you need a sufficiently large bitstring to
minimize possible hash collisions when using Zobrist hashing. When a
hash collision does occur, it can possibly generate an illegal move.
What is an acceptable size of the hash bitstring for a 19x19 board?
On Mon, Aug 31, 2015 at 10:52 AM, Jason House
<jason.james.ho...@gmail.com> wrote:
There are longer cycles that can occur but I have never encountered
any that didn't naturally resolve themselves in the playout.
Zobrist having is cheap to compute (one xor if no stones were
captured). Comparing the resulting number against the others is also
cheap. The hash is also helpful for handling transpositions in the
search tree.
https://en.m.wikipedia.org/wiki/Zobrist_hashing [1]
On Aug 30, 2015 9:17 PM, "Minjae Kim" <xive...@gmail.com> wrote:
Yes, but to 'remember' the prior board state, doesn't the program
have to store the whole board position per every turn by whatever
means including Zobrist hashing that you suggested?
After that, the program has to search whether the current position
matches any of the previous ones. You said 3 is enough for triple
kos, but as far as I know aren't there some rare repeating positions
with a cycle longer than 3?
But anyway solving the problem this way seems too expensive to me.
2015. 8. 31. 오전 9:59에 "Jason House"
<jason.james.ho...@gmail.com>님이 작성:
Triple ko can be detected by remembering the prior three board
states. A zorbist hash value should be good enough to detect a
repeat.
On Aug 30, 2015 8:46 PM, "Minjae Kim" <xive...@gmail.com> wrote:
I finally managed to build a program that can produce a sequence of
random legal go moves. One problem I found recently is that it
rarely never ends a game because of triple ko, especially on small
boards.
One possible solution would be saving every board position that has
occurred and searching for a match before generating a move. But
this doesn't sound like an efficient solution at all.
How do you handle this problem?
Also as a side question, white constantly seems to have a better
winning rate in any board size larger than 9x9 with komi greater
than 6 under area scoring in completely random games; is this
natural?
_______________________________________________
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
