Hi all,
I am planning a fuseki database.
Now I got the following problem: how to rotate/mirror the board for a
unique representation.
$$c
$$ +---+
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . .
Hi,
I'm currently writing a UCT based go program in Clean to see if it is
feasible to write one in a functional language. This is my first attempt
at functional languages, and I'm having trouble with random numbers.
A mersenne twister module is available for Clean. Once initialized it is
Probably the reason that it is so slow is that it's aiming for a
cryptographically random number sequence. These are usually derived
ultimately from kernel timings (often via /dev/random on linux
systems) and it can take a while to establish a degree of confidence
in the randomness of these bits.
A couple of things I did:
I edited the Mersenne Twister code I'm using to get it's seed from the
system time in nanoseconds rather than in miliseconds to fix the problem of
wanting to generate more than one random number in a millisecond.
Instead of generating a new random number every time I
On Dec 19, 2007 3:08 AM, Ben Lambrechts [EMAIL PROTECTED]
wrote:
Hi all,
I am planning a fuseki database.
Now I got the following problem: how to rotate/mirror the board for a
unique representation.
$$c
$$ +---+
$$ | . . . . . . . . . . . . . . . . . .
That was not the problem, as the source code is available and it doesn't
call system libraries at all. I was initializing with known seed in my
tests anyway.
Thanks though, in the process of composing a reply demonstrating the
problem, I found a partial solution. Now random number generation
Ben Lambrechts wrote:
Now I got the following problem: how to rotate/mirror the board for a
unique representation.
Both are the same board, but has anyone made an algorithm that rotates
the board or an area of the board in a unique way?
I don't need the move order, just the snapshot of the
A sorry about that. Glad to hear you fixed the problem. What was your
solution?
It seems you mentioned the global list approach in your email which I
missed too. Why did you think this was an ugly approach? I just put my
random array in a Singleton object (call it MyRandomNumberGenerator) which
Your solution would still be way faster, as I still have to generate a
new random number every time I need one.
The problem is lack of side effects in Clean. If I stick to functional
programming paradigm -and that is the whole point of my effort- I can't
write function which returns a
Now I got the following problem: how to rotate/mirror the board for a
unique representation.Both are the same board, but has anyone made an
algorithm that rotates the board or an area of the board in a unique
way?
I don't need the move order, just the snapshot of the board.
Compute the the
Say you represent the content of each point with 0 for empty, 1 for black
and 2 for white. Start by creating a table of 19x19x3 random 64-bit numbers.
unsigned long long zobrist_table[19][19][3];
...
unsigned long long zobrist_key=0;
for(int row=0;row19;++row){
for(int col=0;col19;++col){
I only use 2 random numbers per point, one for black and one for white. I
xor another random number indicating the side to move.
David
_
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Álvaro Begué
Sent: Wednesday, December 19, 2007 4:15 AM
To: computer-go
Subject:
On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote:
I just witnessed CrazyStone defend a fairly long ladder, resulting in
a dead 17-stone block. Why not use a ladder reader at the root of the
UCT tree to prevent provably bad ladder moves from being considered?
I don't know for sure,
On Dec 19, 2007 9:27 AM, David Fotland [EMAIL PROTECTED] wrote:
I only use 2 random numbers per point, one for black and one for white.
I xor another random number indicating the side to move.
What about ko? I use another number for points that are illegal due to ko.
I think I define a hash
Berk,
Why do you need to initialize the seed more than 1 time?You should
use zobrist hashing.
Initialize the random number generator once when you start the programs.
Fill an array with random numbers from the generator at program startup
too. The array looks something like this for a
Yes, you can set all the values in the table that correspond to empty points
to 0 or, equivalently, only have 2 numbers per point. Actually, that's what
our code does too. But that's a very minor optimization, and I think the
concept is easier to understand without it.
On Dec 19, 2007 9:33 AM,
On Dec 19, 2007 9:40 AM, Heikki Levanto [EMAIL PROTECTED] wrote:
On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote:
I just witnessed CrazyStone defend a fairly long ladder, resulting in
a dead 17-stone block. Why not use a ladder reader at the root of the
UCT tree to prevent
On Dec 19, 2007 10:24 AM, Don Dailey [EMAIL PROTECTED] wrote:
Why do you need to initialize the seed more than 1 time?You should
use zobrist hashing.
By design, my program reinitializes the random seeds. This is done at the
start of each genmove and is intended for repeatability.
I actually have a routine in Lazarus that rotates a full board. It's
called transformBoard() and it takes 2 arguments - a board to rotate and
a transformation (0 through 7) and returns a new rotated board.
I don't use it much except for debugging or stuff done at the root,
because there are
Another thing about Zobrist hashes... after you select the canonical
hash, you will end up with a non-uniform distribution. If this value
is going to be used in binary tree, you may wish to swap the low-order
bits with the high-order bits to keep the tree more balanced.
On Dec 19, 2007 10:44
Instead of generating a new random number every time I want to pick a
move in a random playout, I fill a large circular array with random
numbers when my go program launches (before it is actually playing a
game) and I have a method that just gets the next number out of the
array instead of
Hold on, I just re-read this.Do you think you must initialize the
generator after each number? You only need to initialize MT once, when
your program starts and then it will provide very good numbers for the
next several billion years.
- Don
Imran Hendley wrote:
A couple of things I
Imran Hendley wrote:
A sorry about that. Glad to hear you fixed the problem. What was your
solution?
It seems you mentioned the global list approach in your email which
I missed too. Why did you think this was an ugly approach? I just put
my random array in a Singleton object (call it
Excellent idea Chris! Of course you could also hash the hash! But
then we are talking about using even more CPU time.
- Don
Chris Fant wrote:
Another thing about Zobrist hashes... after you select the canonical
hash, you will end up with a non-uniform distribution. If this value
is
It's also possible to select hash keys such that transformations of
the board's key is the same as recomputing the key for a symmetrical
board position. This will be *much* faster. I came up with a
scheme to do this and documented it on my website, but haven't
actually
The basic idea is this: 90 degree rotation (to the right) is represented as
a circular shift (to the right) by 1/4 of the key length. mirroring the
board (swap left and right) is done as reversing the order of the bits in
the key.
Distinct hash values around the board would have to share
Hi,
I have not had time to study it in details, but I found this:
http://fragrieu.free.fr/zobrist.pdf
A Group-Theoretic Zobrist Hash Function
Antti Huima
September 19, 2000
Abstract
Zobrist hash functions are hash functions that hash go positions to
fixed-length bit strings. They work so that
This should help:
http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653
Erik
On Dec 19, 2007 5:58 PM, Rémi Coulom [EMAIL PROTECTED] wrote:
Hi,
I have not had time to study it in details, but I found this:
http://fragrieu.free.fr/zobrist.pdf
A Group-Theoretic Zobrist
On Dec 19, 2007 1:00 PM, Jeff Nowakowski [EMAIL PROTECTED] wrote:
On Tue, 2007-12-18 at 15:04 -0500, John Tromp wrote:
See the Haskell implementation of my connect-4 solver, Fhourstones, at
http://www.cwi.nl/~tromp/c4/fhour.html
You say on that page: On my machine, the Java version is
On Dec 19, 2007 11:25 AM, Don Dailey [EMAIL PROTECTED] wrote:
Imran Hendley wrote:
A sorry about that. Glad to hear you fixed the problem. What was your
solution?
It seems you mentioned the global list approach in your email which
I missed too. Why did you think this was an ugly
Yes, the large amount of state in a playout will probably enable you
to safely get away with what you are doing, but I would certainly want
to test the overall strength of the engine using this method this
versus using the straight-forward method of seeding the RNG once and
generating a new random
I probably go through my entire array 5 times per second during a UCT
search. So far I have been relying on the hope that I do not come back
to the beginning of my array at exactly the same position in a random
playout which would cause a bad cycle. If I come back at a different
position
I'm not sure if everyone does this already, but I realized that at the end
of a random playout there are no territories bigger than one intersection,
so you don't really need to call your area score method in most cases.
Let D = blackStonesOnBoard - whiteStonesOnBoard + whiteStonesCaptured -
Depending on your rule set, you might not want to use stones captured.
I use more-or-less Tromp-Taylor rules; same as CGOS.
- Some form of mercy rule: if whiteStonesOnBoard == 0, I know who won. Early in
the game, blowouts are *very* comon.
- I maintain an array of empty spaces. At scoring
On Dec 19, 2007 5:55 PM, [EMAIL PROTECTED] wrote:
Depending on your rule set, you might not want to use stones captured.
Oh wow, thanks for the tip. I guess that's what happens when you learn the
rules of go the same day you start writing your program. And I take back
everything I yelled at
You are in for quite a learning curve! But we welcome you. I did it
exactly the same as you, I decided to write a go program and the first
thing I had to do was figure out what the rules of the game were!
Tromp/Taylor is really the way to go on this to get started with
computer go.
This
36 matches
Mail list logo
