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
I'm currently using random numbers ensuring they are not 0 or repeated
in the table, for obvious reasons. I suspect the next step for those
interested would be ensuring each bit has a similar ratio of
occurrences, or bruteforcing it.
On 16/10/2015 14:51, Álvaro Begué wrote:
Btw does anyone
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
And your method, although I didn't understand it completely, seems very
similar to having one big hash table with an entry for the Zobrist hash
of every state of the match, with the advantage of also stopping
superkos. I used this when I had neural networks playing and they
absolutely could
> Btw does anyone have a good initialization vector for the Zobrist table?
The obvious thing to try is random numbers. Another idea is turning your
Zobrist key into CRC64, which I think is what you get if you generate your
numbers like this:
#include
int main() {
unsigned long long const P =
That sounds kind of obsessive. I think the probability of having a 0 or
repeated numbers in the table is about 3.18*10^-15 (someone else please
check my math). To generate some intuition for how small this number is, if
you did this a thousand times per second, the expected time to finding a
We are talking about initialization of the Zobrist table. That will happen
once per execution of the program; or even just once ever, if he just
generates the table and hard-codes it into the program --which is what I do.
Álvaro.
On Fri, Oct 16, 2015 at 10:29 AM, Igor Polyakov
Heh you got me there. I guess I do it because there's not really any
drawback to it, better be safe than sorry, even if only every 10,000 years.
On 16/10/2015 15:21, Álvaro Begué wrote:
That sounds kind of obsessive. I think the probability of having a 0 or
repeated numbers in the table is
If you're only getting 1000 table generations a second, you should look
into your algorithm. You should get at least 100,000 table generations a
second!
On 2015-10-16 7:21, Álvaro Begué wrote:
That sounds kind of obsessive. I think the probability of having a 0
or repeated numbers in the
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
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
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
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
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
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
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
16 matches
Mail list logo
