[computer-go] rotate board
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 $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ 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. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] random numbers with functional languages
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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 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 generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. On Dec 19, 2007 3:51 AM, Stuart A. Yeates [EMAIL PROTECTED] wrote: 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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ 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. You can compute all rotated versions of the board (8 of them) and pick the minimum, in some sense. For instance, you can compare boards lexicographically, or you can compute a zobrist key and pick the minimum of that. Does that help? Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: 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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 board. Compute the the min(8 Zobrist hashes for all mirror/rot combinations) (x, y), (inv Y, x), (inv X, inv Y), (y, inv X), (inv X, y), (inv Y, inv X), (x, inv Y), (y, x). Call the smallest of the 8 hashes the canonical hash. Make a database of canonical hashes. Since Zobrist hashes can be updated incrementally, checking over the legal moves is just xoring the 8 hashes of the each legal move (with a given mirror/rot) to the hashes of the current position in that same mirror/rot. You store 8 hashes for the current position (=without the move) and compute the 8 hashes of the next position. The smallest of these is the canonical of the next position. This is repeated for each legal move. Its simple, but perhaps my explanation makes it sound more complicated than it is ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 internally stores the next index and has a method for getting the next random number. So I just replace all my calls to Random.getNextInt() with MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of people would still call this ugly... But it's just a lookup so I think it will beat any other solution that involves generating a new random number by a reasonable margin. On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED] wrote: 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 takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: 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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 different number each time it is called. A function is supposed to return same result every time it is called with same parameters so I can't/shouldn't write an analogue of getNextInt() (whether or not getNextInt() returns a number from a list or from a random number generator.) I just shaved off time by not initializing a new random generator each time a node is visited. Instead, when a leaf node is visited, first maxMoves terms of random list is sent to MC evaluation, and remaining terms are used to create a new list. Sharing this list across whole search tree would be ugly and complicated. So I still initialize a new random list for each new tree node but reuse it for subsequent MC evaluations from that node. Berk. 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 MyRandomNumberGenerator) which internally stores the next index and has a method for getting the next random number. So I just replace all my calls to Random.getNextInt() with MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of people would still call this ugly... But it's just a lookup so I think it will beat any other solution that involves generating a new random number by a reasonable margin. On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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 takes 3% of running time, compared to 60% of older version and ~1% of a hypothetical ideal solution. Berk. Stuart A. Yeates wrote: 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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 min(8 Zobrist hashes for all mirror/rot combinations) (x, y), (inv Y, x), (inv X, inv Y), (y, inv X), (inv X, y), (inv Y, inv X), (x, inv Y), (y, x). Call the smallest of the 8 hashes the canonical hash. Make a database of canonical hashes. Since Zobrist hashes can be updated incrementally, checking over the legal moves is just xoring the 8 hashes of the each legal move (with a given mirror/rot) to the hashes of the current position in that same mirror/rot. You store 8 hashes for the current position (=without the move) and compute the 8 hashes of the next position. The smallest of these is the canonical of the next position. This is repeated for each legal move. Its simple, but perhaps my explanation makes it sound more complicated than it is ;-) This is going to sound really stupid. How do I compute the Zobrist Hash? What is the Zobrist Hash of the following board? $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X X O . . . . . . . . . . . . . . | $$ | . . X O O X . O . . O . . . . . . . . | $$ | . . X O . . . . . , . . . . . X . . . | $$ | . . . O . . . . . . . . . . . X X . . | $$ | . . X . . . . . . . . . . . O X O . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . O . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . O O O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . O . . . . . . . . . . . O O O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . O O . . . . . X . . X . . , X . . | $$ | . . O X . X . . . . . . . . . X . . . | $$ | . . X . X . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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){
int point_content = board[row][col];
zobrist_key ^= zobrist_table[row][col][point_content];
}
}
The result is the zobrist key. In practice, you would make the zobrist key
part of your representation of the board, and when you modify the board, you
just incrementally update the zobrist key. Just remember that when you
change the content of a point,
new_zobrist_key = old_zobrist_key ^
zobrist_table[row][col][old_point_content] ^
zobrist_table[row][col][new_point_content];
Get that working first and then reread Jacques's post.
Álvaro.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] rotate board
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: Re: [computer-go] rotate board
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){
int point_content = board[row][col];
zobrist_key ^= zobrist_table[row][col][point_content];
}
}
The result is the zobrist key. In practice, you would make the zobrist key
part of your representation of the board, and when you modify the board, you
just incrementally update the zobrist key. Just remember that when you
change the content of a point,
new_zobrist_key = old_zobrist_key ^
zobrist_table[row][col][old_point_content] ^
zobrist_table[row][col][new_point_content];
Get that working first and then reread Jacques's post.
Álvaro.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
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, but I suspect that even if it means that it would not play out a bad ladder, the UCT would still see it as a desirable thing, and direct the game towards one - and then not play it. Plus, it is not quite trivial to recognize a bad ladder - some times it pays off to extend a stone that is in atari, and then sacrifice two stones. Some nakade shapes also require sacrificing more than one stone... - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 key indicating illegal for black and another as illegal for white, but that's not needed ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 9x9 board: zob[3][81] Basically xor each point of the 9x9 board with the random number on the point. The first index is 3 because I assume you have white/black/empty points.So xor the appropriate one for each point. A major enhancement is that you can do this incrementally. You have a master key that you keep up to date. If you add a stone to the board, you can update the key with only 2 xor operations.Since the point is no longer empty you must undo the xor with the empty point.XOR is great because you can undo it with the same xor operation.So you get: if mv is the move you are about to make with a black stone then: master_hash = master_hash ^ zob[EMPTY][ mv ] master_hash = master_hash ^ zob[BLACK][ mv ] and you are done. Of course if a white group is captured, you must undo all the white stones that were captured in some kind of loop, but it still runs rings around updating the entire board on each move. There is a variation of this - you can choose to hash only 2 colors: (black and empty), (white and empty), or (black and white) and so the other color is inferred.The natural expression of this in a program is to hash only white and black because you never change state from black to white in a single move. - Don Berk Ozbozkurt wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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, Jason House [EMAIL PROTECTED] wrote: 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 key indicating illegal for black and another as illegal for white, but that's not needed ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
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 provably bad ladder moves from being considered? I don't know for sure, but I suspect that even if it means that it would not play out a bad ladder, the UCT would still see it as a desirable thing, and direct the game towards one - and then not play it. Still better than actually playing it out. Another idea I had was to do a tactical analysis of a block whenever the UCT node has been hit X number of times. When the move is provably pointless (e.g. adding to a dead block), prevent that line from continuing to be explored. If X is large enough and the tactical analysis is restricted enough, hopefully it won't significantly affect the overall speed. And it has the nice trait that it can be used not only at the root but at any level in the tree. Plus, it is not quite trivial to recognize a bad ladder - some times it pays off to extend a stone that is in atari, and then sacrifice two stones. Some nakade shapes also require sacrificing more than one stone... But this was the trivial kind and it cost the game. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 faster ways to do things. I also have a routine called canHash() which returns a canonical hash of the board by trying all 8 transformations and returning the lowest valued one. It is more efficient (but not efficient) because it doesn't actually produce a new board - it just builds 8 hashes of the board from scratch without touching anything.This routine is only used at the root for storing opening book moves. You can use zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. It depends on how fat or lean your program is. Even 8 keys may not be noticeable if your program does a lot of work at each move (or an end nodes.)If you are not, then it doesn't really matter how you do it. I typically have 2 routines for everything - I have a slow_make() and a fast_make() and the fast_make() doesn't care about superko (although it checks for simple-ko) or anything that fast play-outs doesn't care about. So the fast make doesn't even try to update zobrist keys. - Don Ben Lambrechts 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 $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ 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. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 AM, Don Dailey [EMAIL PROTECTED] wrote: 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 faster ways to do things. I also have a routine called canHash() which returns a canonical hash of the board by trying all 8 transformations and returning the lowest valued one. It is more efficient (but not efficient) because it doesn't actually produce a new board - it just builds 8 hashes of the board from scratch without touching anything.This routine is only used at the root for storing opening book moves. You can use zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. It depends on how fat or lean your program is. Even 8 keys may not be noticeable if your program does a lot of work at each move (or an end nodes.)If you are not, then it doesn't really matter how you do it. I typically have 2 routines for everything - I have a slow_make() and a fast_make() and the fast_make() doesn't care about superko (although it checks for simple-ko) or anything that fast play-outs doesn't care about. So the fast make doesn't even try to update zobrist keys. - Don Ben Lambrechts 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 $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ 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. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. That could affect your caches. This is generally the type of thing that can create unexpected problems if you are not very careful. You have essentially just created a very low period RNG. I would not play long autotest matches unless you re-initalize this before each game.I would also hope that you have enough to get you through a complete game (or nearly so.) Then you might get away with it. Years ago a wrote a rummy card game player and was testing different strategies against each other. I discovered that the RNG was low period and was getting consistently biased results (where identical programs were not scoring 50/50 but more like 52/48 over thousands of games.)It turned out to be the short period of the RNG causing the problem.It's very difficult if not impossible to predict how this will affect the period of your application. You could fall into a winning or losing cycle against another similarly deterministic player and it could be short or fairly long. (A cycle where you will lose or win more games than you should and games will repeat.) This behavior is guaranteed, it's a just a matter of how long or short the cycle will be. I improved the problem with the card game by adding more chaos. It wasn't the ideal solution but it was an improvement.Instead of re-initializing a new pack of cards, I kept the old pack around and re-shuffled it. Effectively, this is like creating a slightly more sophisticated RNG with a longer period. So each new game began with a deck of cards that were in chaos from the previous game (similar to real card games.) I'm surprised that this represents a large speedup. How long does it take to initialize a new set of random numbers? I would think this would happen very quickly. However long it takes, I would think that an upper bound on how much time you can save (minus some caching effects perhaps) would be this same time spent building a new set of numbers. So if it takes about 5 seconds, you should only lose about 5 seconds for the whole game assuming you initialized just enough numbers to play a full game. - Don On Dec 19, 2007 3:51 AM, Stuart A. Yeates [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go
Re: [computer-go] random numbers with functional languages
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 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 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 generating a new random number in real time. Actually I have a different array for each possible board size, since I need a random integer from a different range for each. Sure the array repeats after 500,000 numbers or however many you use, but this is not a big deal when your playouts are only 100 moves long each - and it is unlikely to start repeating from the same position. This approach was much faster than generating random numbers on the fly. On Dec 19, 2007 3:51 AM, Stuart A. Yeates [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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. If you want a sequence of numbers that is very unlikely to repeat but that doesn't have to be cryptographically random, standard practice is to initialise the random number generator with the current time (usually a long expressed in milliseconds). This naturally fails if you ever create more than one sequence per millisecond. cheers stuart On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: 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 reasonably fast to extract a new random number from the generator. However, it is about a hundred times slower to initialize it with a new random seed. Therefore my first attempt at generating random numbers by storing seeds at tree nodes and creating a new random list and a new seed each time random numbers are required for mc evaluation is very slow. The alternative seems to be passing around an index to a global random list, which is both ugly and complicated. Is there another way? ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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
MyRandomNumberGenerator) which internally stores the next index and
has a method for getting the next random number. So I just replace all
my calls to Random.getNextInt() with
MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of
people would still call this ugly... But it's just a lookup so I think
it will beat any other solution that involves generating a new random
number by a reasonable margin.
You are spending time before the game to save time during the game - a
good principle in general but you do have a few issues:
1. How does this affect cache? (probably not much but you have to
consider it.)
2. Can you get enough numbers to last a complete game?
If this is so slow, then there would be a long delay each time you
generate a new set of random numbers and I really think you should do
this between games. I wonder how long the delay is?
If the delay is unduly long (it must be, otherwise you wouldn't have to
do this) then an alternative is to change a fraction of the numbers
between games:
// code to randomly change 1000 values:
for (i=0; i1000; i++) {
ix = randomInt( RANDOM_ARRAY_SIZE );
randArray[ ix ] = newRandomNumber();
}
In other words, pick a few array locations at random and change their
value.
This will prevent any serious cycles with long testing sequences.
You could also perform such a routine between moves. You only need to
change a few so change as many as you can in a fraction of a second.
- Don
On Dec 19, 2007 5:15 AM, Berk Ozbozkurt [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
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
takes
3% of running time, compared to 60% of older version and ~1% of a
hypothetical ideal solution.
Berk.
Stuart A. Yeates wrote:
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.
If you want a sequence of numbers that is very unlikely to
repeat but
that doesn't have to be cryptographically random, standard
practice is
to initialise the random number generator with the current time
(usually a long expressed in milliseconds). This naturally fails if
you ever create more than one sequence per millisecond.
cheers
stuart
On 19/12/2007, Berk Ozbozkurt [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
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
reasonably fast to extract a new random number from the generator.
However, it is about a hundred times slower to initialize it
with a new
random seed. Therefore my first attempt at generating random
numbers by
storing seeds at tree nodes and creating a new random list and
a new
seed each time random numbers are required for mc evaluation is
very
slow. The alternative seems to be passing around an index to a
global
random list, which is both ugly and complicated. Is there
another way?
___
computer-go mailing list
computer-go@computer-go.org mailto:computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 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 AM, Don Dailey [EMAIL PROTECTED] wrote: 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 faster ways to do things. I also have a routine called canHash() which returns a canonical hash of the board by trying all 8 transformations and returning the lowest valued one. It is more efficient (but not efficient) because it doesn't actually produce a new board - it just builds 8 hashes of the board from scratch without touching anything.This routine is only used at the root for storing opening book moves. You can use zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. It depends on how fat or lean your program is. Even 8 keys may not be noticeable if your program does a lot of work at each move (or an end nodes.)If you are not, then it doesn't really matter how you do it. I typically have 2 routines for everything - I have a slow_make() and a fast_make() and the fast_make() doesn't care about superko (although it checks for simple-ko) or anything that fast play-outs doesn't care about. So the fast make doesn't even try to update zobrist keys. - Don Ben Lambrechts 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 $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ 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. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 implemented it yet. I can't find your website. Can you give me a link? - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 the same rules. Picking a somewhat arbitrary example (on 19x19), here's some candidate keys (kept simple for manual typing) A2 = 0x 01 02 03 04 B19 = 0x 04 01 02 03 T18 = 0x 03 04 01 02 U1 = 0x 02 03 04 01 T2 = 0x 20 c0 40 80 B1 = 0x 80 20 c0 40 A18 = 0x 40 80 20 c0 U19 = 0x c0 40 80 20 Points on lines of symmetry (such as C3 with 4 equivalent points or the unique tengen) need more care with how they're selected). That's the same system I used in my first Go program, and it appears to also be the same as what is in the paper that Remi linked. I didn't use it for full-board hashes, I used it for patterns. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 every intersection i on a go board is associated with two values Bi and Wi. To hash a position, all those values of Bi are XORed together that correspond to an intersec- tion with black stone on it. Similarly, all Wi’s are XORed together for those intersections that have a white stone. Then the results are XORed together. We present a Zobrist hash function with the extra property that if z is the hash value of a position p, then the values z′ for the positions p′ that are obtained from p by exchanging the colors, by rotating the position and my mirroring can be efficiently calculated from z alone. Still, z and z′ are different. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
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 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 every intersection i on a go board is associated with two values Bi and Wi. To hash a position, all those values of Bi are XORed together that correspond to an intersec- tion with black stone on it. Similarly, all Wi's are XORed together for those intersections that have a white stone. Then the results are XORed together. We present a Zobrist hash function with the extra property that if z is the hash value of a position p, then the values z′ for the positions p′ that are obtained from p by exchanging the colors, by rotating the position and my mirroring can be efficiently calculated from z alone. Still, z and z′ are different. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: language efficiency
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 75% slower than the C one, which I find hard to explain. Try running with -server, which enables aggressive JIT. On my machine that made it nearly the same speed as the C version. It needs more memory, though, and the first test case will be slow. tromp java -version java version 1.4.2_15 Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_15-b02) Java HotSpot(TM) Client VM (build 1.4.2_15-b02, mixed mode) tromp javac -O SearchGame.java tromp java -server -Xmx100m SearchGame inputs Fhourstones 3.1 (Java) Boardsize = 7x6 Using 8306069 transposition table entries. Solving 8-ply position after 45461667 . . . score = 5 (+) work = 14 51596 pos / 172 msec = 299.977 Kpos/sec - 0.281 0 = 0.001 0.001 + 0.716 Solving 8-ply position after 35333571 . . . score = 1 (-) work = 21 8716732 pos / 4696 msec = 1856.204 Kpos/sec - 0.271 0.036 = 0.02 0.089 + 0.584 Solving 8-ply position after 1111 . . . score = 3 (=) work = 26 169704432 pos / 89157 msec = 1903.434 Kpos/sec - 0.216 0.144 = 0.021 0.242 + 0.377 tromp gcc -O3 -m64 -o SearchGame SearchGame.c tromp ./SearchGame inputs Fhourstones 3.1 (C) Boardsize = 7x6 Using 8306069 transposition table entries. Solving 8-ply position after 45461667 . . . score = 5 (+) work = 15 105896 pos / 29 msec = 3651.6 Kpos/sec - 0.285 0.000 = 0.000 0.000 + 0.714 Solving 8-ply position after 35333571 . . . score = 1 (-) work = 23 26134620 pos / 4777 msec = 5470.9 Kpos/sec - 0.280 0.047 = 0.022 0.105 + 0.546 Solving 8-ply position after 1111 . . . score = 5 (+) work = 23 37058374 pos / 6561 msec = 5648.3 Kpos/sec - 0.263 0.065 = 0.026 0.133 + 0.513 Huge difference (almost 3x faster) Can someone try with a more up-to-date JVM, like the latest from Sun and IBM, and with 64-bit opteron support? regards, -John ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 approach? I just put
my random array in a Singleton object (call it
MyRandomNumberGenerator) which internally stores the next index and
has a method for getting the next random number. So I just replace all
my calls to Random.getNextInt() with
MyRandomNumberGenerator.getNextInt(). Actually I can see how a lot of
people would still call this ugly... But it's just a lookup so I think
it will beat any other solution that involves generating a new random
number by a reasonable margin.
You are spending time before the game to save time during the game - a
good principle in general but you do have a few issues:
1. How does this affect cache? (probably not much but you have to
consider it.)
2. Can you get enough numbers to last a complete game?
If this is so slow, then there would be a long delay each time you
generate a new set of random numbers and I really think you should do
this between games. I wonder how long the delay is?
If the delay is unduly long (it must be, otherwise you wouldn't have to
do this) then an alternative is to change a fraction of the numbers
between games:
// code to randomly change 1000 values:
for (i=0; i1000; i++) {
ix = randomInt( RANDOM_ARRAY_SIZE );
randArray[ ix ] = newRandomNumber();
}
In other words, pick a few array locations at random and change their
value.
This will prevent any serious cycles with long testing sequences.
You could also perform such a routine between moves. You only need to
change a few so change as many as you can in a fraction of a second.
- Don
Don,
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 then I
will not start replaying the same set of playouts in the search of that
particular game position, and I will also play a different sequence of moves
in this run through the array because I will reject different numbers I
get because they correspond to illegal board positions but didn't last time
through the array and vice versa.
I think the chance of a bad cycle is very small. I just did some more
analysis of this just now and it got a little complicated, so I'll leave it
out. However, I do think making a bad cycle impossible is important. Your
idea of reinitializing some random positions in the array looks really good.
Unfortunately there is no way I can do this each time through the array for
any meaningful portion of the whole array...since just resetting my index to
0 when I get to the end is pretty expensive in terms of average cost, and if
I'm going through the array a few times a second I can't do much more than
that each time. What do you think of resetting my index to a random position
between 0 and some small n every time to make the probability of getting
stuck in a cycle forever go to zero, and then finding some free time to
reset the numbers like right after playing a move and before starting to
ponder for example?
And about the cache...I've never really thought about it. How do think the
cache would be affected? I don't really know much about cache's to be
honest. Are you saying that the numbers in my array would get stored in the
cache? Is this good or bad?
Imran
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 number anytime you need it. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] random numbers with functional languages
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 then I will not start replaying the same set of playouts in the search of that particular game position, and I will also play a different sequence of moves in this run through the array because I will reject different numbers I get because they correspond to illegal board positions but didn't last time through the array and vice versa. I think the chance of a bad cycle is very small. Hopefully that is true. I just did some more analysis of this just now and it got a little complicated, so I'll leave it out. However, I do think making a bad cycle impossible is important. Your idea of reinitializing some random positions in the array looks really good. Unfortunately there is no way I can do this each time through the array for any meaningful portion of the whole array...since just resetting my index to 0 when I get to the end is pretty expensive in terms of average cost, and if I'm going through the array a few times a second I can't do much more than that each time. What do you think of resetting my index to a random position between 0 and some small n every time to make the probability of getting stuck in a cycle forever go to zero, and then finding some free time to reset the numbers like right after playing a move and before starting to ponder for example? Certainly that's better than nothing. I assume you will use the random number generator to do this? If so, it will be an improvement. And about the cache...I've never really thought about it. How do think the cache would be affected? I don't really know much about cache's to be honest. Are you saying that the numbers in my array would get stored in the cache? Is this good or bad? If you use a lot of memory to store something that could be generated on the fly, you could slow your whole program down due to caching issues between the processor and memory.When you use a piece of data for the first time, it is slow. But after that it is much faster because it is stored in super-fast memory. But you only have so much of that super-fast memory. I don't think it's likely to be an issue for you, but it's something to keep in mind. I have created cache unfriendly software by going too crazy with tables but modern processors are pretty well designed and generous. - Don Imran ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] A small optimization for scoring random playouts
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 - blackStonesCaptured - komi. If abs(D) K for some small threshold K (I use size/2 = 4 for a 9x9 board, but you can use size if you want to be super safe) then D0 means black wins, white wins otherwise. The only problem is when D is close to 0, since the real area score also counts each eye as one point and this is not reflected in D. So depending on how many eyes each side has, the result might go one way or another. We can either keep track of the number of eyes and update D accordingly, or we can just call the area score method for these borderline cases. If we do the latter we are still saving a lot of time in most cases if we choose K small enough. This gave me a nice speedup of 10% or so if I remember correctly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A small optimization for scoring random playouts
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 time, Every empty space should be a single point eye. I just check the eyes/empty spaces?to find a neighbor and I know who owns it. - white terr = whiteStonesOnBoard?+ whiteEyes It's fast. If you are using a different rule set for playouts, my suggestions are worthless-ignore them. Is anyone using a different scoring system for playouts? -Dave Hillis -Original Message- From: Imran Hendley [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Wed, 19 Dec 2007 5:18 pm Subject: [computer-go] A small optimization for scoring random playouts 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 - blackStonesCaptured - komi. If abs(D) K for some small threshold K (I use size/2 = 4 for a 9x9 board, but you can use size if you want to be super safe) then D0 means black wins, white wins otherwise. The only problem is when D is close to 0, since the real area score also counts each eye as one point and this is not reflected in D. So depending on how many eyes each side has, the result might go one way or another. We can either keep track of the number of eyes and update D accordingly, or we can just call the area score method for these borderline cases. If we do the latter we are still saving a lot of time in most cases if we choose K small enough. This gave me a nice speedup of 10% or so if I remember correctly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ More new features than ever. Check out the new AIM(R) Mail ! - http://webmail.aim.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A small optimization for scoring random playouts
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 GNU Go when it didn't count the captured stones in its area score. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] A small optimization for scoring random playouts
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 page will save you a great deal of aggravation: http://homepages.cwi.nl/~tromp/go.html - Don Imran Hendley wrote: On Dec 19, 2007 5:55 PM, [EMAIL PROTECTED] mailto:[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 GNU Go when it didn't count the captured stones in its area score. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
