Re: [computer-go] Efficiently selecting a point to play in a random playout
I've been messing around with where to apply heuristics. Candidates include: 1) In the UCT tree, since this is earliest in each playout. 2) In the moves beyond the tree (heavy playouts), since this is where most of the moves happen. Because this part is so speed-critical, ... Remi (using learned patterns instead of heuristics, but should be the same) got dramatic improvements doing both (see quote below). It is also my understanding that in Crazy Stone the patterns are being used at every ply in the playouts; given that the program is being given a constant time it seems the overhead of this is more than made up for by the increase in strength. Darren -- In the computer-go Amsterdam 2007 paper thread, on 2007-05-18: Here are tests of Crazy Stone at 90s/game 1CPU against GNU 3.6 level 10, measured over about 200 games: no pattern: 38.2% (version available on my web page) patterns in simulations:68.2% patterns for pruning and simulations:90.6% I found these number in my history of Crazy Stone versions, so they may not be extremely accurate, because other things have changed in between. I will run cleaner tests for the final version of the paper. I will also try to test what each feature brings. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Darren Cook wrote: I've been messing around with where to apply heuristics. Candidates include: 1) In the UCT tree, since this is earliest in each playout. 2) In the moves beyond the tree (heavy playouts), since this is where most of the moves happen. Because this part is so speed-critical, ... Remi (using learned patterns instead of heuristics, but should be the same) got dramatic improvements doing both (see quote below). It is also my understanding that in Crazy Stone the patterns are being used at every ply in the playouts; given that the program is being given a constant time it seems the overhead of this is more than made up for by the increase in strength. Darren Interestingly, I got no overhead when I added 3x3 patterns. It even made simulations faster, because detecting illegal moves or moves into eyes came for free. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Peter Drake wrote: On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote: Also, if you have a clever probability distribution, the range of values for each move will be very large. For instance, here are two 3x3 shapes used by Crazy Stone (# to move): O O # # . . # O # Gamma = 143473; . # # . . . . . . Gamma = 20; Playing in the empty corner has gamma = 1. So that would be a lot of tickets to distribute. Is this distribution something like the number of times a given move was played in your training set? No. It is explained in my Amsterdam paper: http://remi.coulom.free.fr/Amsterdam2007/ Doesn't the play in empty space pattern swamp everything else? No. Gamma = 214 for that one. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Jacques Basaldúa wrote: Rémi, are your values the result of learning in masters games? Yes. I took data from a learning experiment based on very few games. So there may be a little overfitting. Still, the ratio between the strongest and the weakest patterns is always very big. I'll run some experiments with more random simulations (by exponentiating the gammas by a constant 1). Maybe it would produce better play. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
This sounds a lot like the roulette wheel selection scheme used in genetic algorithms. The idea is that each candidate has a different slice of a roulette wheel, with better candidates getting bigger slices. Peter Drake http://www.lclark.edu/~drake/ On Jun 6, 2007, at 2:07 AM, Jacques Basaldúa wrote: I created something I call a ticket based lottery. Moves (legal in my case) buy tickets. An average move buys, say 10 tickets, the worst possible move buys just 1 and the most urgent buys 100. Of course these numbers should be tested empirically, because, the higher, the slower. (About 20 clockcycles per ticket. ~6ns·n is the difference between allocating 1 and allocating n (5 asm instructions)). And tickets are allocated in something similar to Don's idea. I have also considered doing multiple tickets just like coins. Having tickets of x1 and a separate tickets of x5 or some other value. Any ideas ? Jacques. ___ 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] Efficiently selecting a point to play in a random playout
Álvaro Begué wrote: Actually, John had a better idea to do this. In two words: binary tree. The root represents the whole board, and it contains the sum of the probabilities of all the points (you don't need to force this to be 1, if you use non-normalized probabilities). This node points to two nodes, each of which represents about half the board and contains the sum of the probabilities of all the points in its half. You keep going down the tree until eventually you get to nodes that represent individual points, with their probabilities. Picking a random move according to the desired distribution now takes O(log(board_size)) (just toss biased coins at each level of the tree to decide whether to follow the left subtree or the right subtree). Updating the probability of a point also takes O(log(board_size)). I wonder if other people had thought about this before... Álvaro. Yes, I did it in the beginning. But I found that it is faster to divide by more than two. Currently, I keep the probability of the whole board, each line, and each point. It is simple, and more efficient than a binary tree. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On 6/6/07, Rémi Coulom [EMAIL PROTECTED] wrote:
I wonder if other people had thought about this before...
Álvaro.
Yes, I did it in the beginning. But I found that it is faster to divide
by more than two. Currently, I keep the probability of the whole board,
each line, and each point. It is simple, and more efficient than a
binary tree.
Rémi
I'm not clear on how you efficiently index into which line to select. I
think the discussion here is still relevant to that. If we take a simple
example of a 5x5 board where the line weights are {15,10,30,20,25}, and I
roll the dice and compute 44 (out of 100), I don't know to jump instantly to
the 3rd entry; other information is needed if a sequential check is to be
avoided. Tokens of 5 could make it easy to pick a number from 1 to 20 and
then jump to the row owned by that token, and a binary tree could result in
~3 comparisons... not much better than a sequential check at such a small
number of lines.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
I would be weary of using java.util.Random - it is not that random: http://alife.co.uk/nonrandom/. A drop in Mersenne Twister replacement for java.util.Random is available at http://cs.gmu.edu/~sean/research/. Cheers, Graham. On 05/06/07, Peter Drake [EMAIL PROTECTED] wrote: Oddly, there doesn't seem to be much effect on speed whether I use a single random number generator (i.e., instance of java.util.Random) or one for each thread. Peter Drake http://www.lclark.edu/~drake/ On Jun 5, 2007, at 11:59 AM, Jason House wrote: On 6/5/07, Peter Drake [EMAIL PROTECTED] wrote: On a multithreaded program like Orego (running on a multicore machine), it moves the nontrivial random number generation out of the synchronized part of the program and into the threads. I'm surprised to hear this. Do you have a single random number generator? In housebot, Each thread has its own random number generator instance. Besides avoiding a bottleneck as each thread generates random numbers, it also opens the door for repeatable behavior in a single worker thread. ___ 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] Efficiently selecting a point to play in a random playout
Jason House wrote:
On 6/6/07, *Rémi Coulom* [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
I wonder if other people had thought about this before...
Álvaro.
Yes, I did it in the beginning. But I found that it is faster to divide
by more than two. Currently, I keep the probability of the whole board,
each line, and each point. It is simple, and more efficient than a
binary tree.
Rémi
I'm not clear on how you efficiently index into which line to select. I
think the discussion here is still relevant to that. If we take a
simple example of a 5x5 board where the line weights are
{15,10,30,20,25}, and I roll the dice and compute 44 (out of 100), I
don't know to jump instantly to the 3rd entry; other information is
needed if a sequential check is to be avoided. Tokens of 5 could make
it easy to pick a number from 1 to 20 and then jump to the row owned by
that token, and a binary tree could result in ~3 comparisons... not much
better than a sequential check at such a small number of lines.
I do a sequential check.
It is important to understand that it is worthless to be able to pick a
move extremely rapidly, if updating the related data takes a lot of
time. With 3x3 patterns, 8 points have their urgencies updated after
each move. Updating the probability distribution is the time-critical
part of the algorithm, not picking one move at random. With my
algorithm, I have to update 3 values each time the urgency of a move
changes. With a binary tree, I would have to update 8 in 9x9, and 10 in
19x19.
Also, if you have a clever probability distribution, the range of values
for each move will be very large. For instance, here are two 3x3 shapes
used by Crazy Stone (# to move):
O O #
# . .
# O #
Gamma = 143473;
. # #
. . .
. . .
Gamma = 20;
Playing in the empty corner has gamma = 1. So that would be a lot of
tickets to distribute.
Simple straightforward algorithms often work well. I do not do anything
extraordinary in Crazy Stone, and, on 9x9 from the empty board, it still
runs 21,700 simulations per second on a 2.6 GHz opteron (20,400 with the
tree-search logic).
I am sure it could be made significantly faster, but adding knowledge
and high-level algorithmic improvements is tremendously more profitable
in terms of playing strength than finding tricks to accelerate playouts.
Rémi
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Thanks for the tip. It does seem a bit faster (5% speedup of the program overall), and I'm willing to accept the consensus that the randomness is better. Peter Drake http://www.lclark.edu/~drake/ On Jun 6, 2007, at 2:15 PM, Graham Thomson wrote: I would be weary of using java.util.Random - it is not that random: http://alife.co.uk/nonrandom/. A drop in Mersenne Twister replacement for java.util.Random is available at http://cs.gmu.edu/~sean/research/. Cheers, Graham. On 05/06/07, Peter Drake [EMAIL PROTECTED] wrote: Oddly, there doesn't seem to be much effect on speed whether I use a single random number generator (i.e., instance of java.util.Random) or one for each thread. Peter Drake http://www.lclark.edu/~drake/ On Jun 5, 2007, at 11:59 AM, Jason House wrote: On 6/5/07, Peter Drake [EMAIL PROTECTED] wrote: On a multithreaded program like Orego (running on a multicore machine), it moves the nontrivial random number generation out of the synchronized part of the program and into the threads. I'm surprised to hear this. Do you have a single random number generator? In housebot, Each thread has its own random number generator instance. Besides avoiding a bottleneck as each thread generates random numbers, it also opens the door for repeatable behavior in a single worker thread. ___ 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] Efficiently selecting a point to play in a random playout
On Jun 6, 2007, at 2:41 PM, Rémi Coulom wrote: Also, if you have a clever probability distribution, the range of values for each move will be very large. For instance, here are two 3x3 shapes used by Crazy Stone (# to move): O O # # . . # O # Gamma = 143473; . # # . . . . . . Gamma = 20; Playing in the empty corner has gamma = 1. So that would be a lot of tickets to distribute. Is this distribution something like the number of times a given move was played in your training set? Doesn't the play in empty space pattern swamp everything else? Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Tue, 2007-06-05 at 10:23 -0700, Peter Drake wrote: While there is a bias in theory, I suspect that you are right that it is not significant in practice if you maintain a list of vacant points (as Orego now does), because almost all vacant points are legal. In any case, switching to your technique (generating one random starting point in the list when it's time to choose a random move rather than shuffling the list at the beginning of the run) is a big speed win. This is horribly non-random.To illustrate, imagine that only 2 move are legal and they are right next to each other. ALL random choices except one would choose the move earliest in the list. - Don On a multithreaded program like Orego (running on a multicore machine), it moves the nontrivial random number generation out of the synchronized part of the program and into the threads. This one change instantly got me 25-30% more playouts per second. Thanks for the tip! Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 11:39 AM, Łukasz Lew wrote: Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) ... Best Regards, Lukasz Lew ___ 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] Efficiently selecting a point to play in a random playout
On 6/5/07, Peter Drake [EMAIL PROTECTED] wrote: On a multithreaded program like Orego (running on a multicore machine), it moves the nontrivial random number generation out of the synchronized part of the program and into the threads. I'm surprised to hear this. Do you have a single random number generator? In housebot, Each thread has its own random number generator instance. Besides avoiding a bottleneck as each thread generates random numbers, it also opens the door for repeatable behavior in a single worker thread. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
But if you are taking the vacant points out it is probably not too biased as you say. But what I do is pretty fast. Always choose a random point but keep shrinking the list. When a point is occupied move it out of the way so it's never selected again. You have to do some simple bookeeping - basically swapping the position of elements and shrinking the list (in your terminology, maintaining a set of empty points.) I don't think this is any slower than what you are proposing. I start a random game by collect vacant points - but after a capture move you have to re-do this operation. Still, it's 2X faster to collect vacant points together like (even if you are doing everything else this way.) - Don On Tue, 2007-06-05 at 14:45 -0400, Don Dailey wrote: On Tue, 2007-06-05 at 10:23 -0700, Peter Drake wrote: While there is a bias in theory, I suspect that you are right that it is not significant in practice if you maintain a list of vacant points (as Orego now does), because almost all vacant points are legal. In any case, switching to your technique (generating one random starting point in the list when it's time to choose a random move rather than shuffling the list at the beginning of the run) is a big speed win. This is horribly non-random.To illustrate, imagine that only 2 move are legal and they are right next to each other. ALL random choices except one would choose the move earliest in the list. - Don On a multithreaded program like Orego (running on a multicore machine), it moves the nontrivial random number generation out of the synchronized part of the program and into the threads. This one change instantly got me 25-30% more playouts per second. Thanks for the tip! Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 11:39 AM, Łukasz Lew wrote: Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) ... Best Regards, Lukasz Lew ___ 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] Efficiently selecting a point to play in a random playout
Oddly, there doesn't seem to be much effect on speed whether I use a single random number generator (i.e., instance of java.util.Random) or one for each thread. Peter Drake http://www.lclark.edu/~drake/ On Jun 5, 2007, at 11:59 AM, Jason House wrote: On 6/5/07, Peter Drake [EMAIL PROTECTED] wrote: On a multithreaded program like Orego (running on a multicore machine), it moves the nontrivial random number generation out of the synchronized part of the program and into the threads. I'm surprised to hear this. Do you have a single random number generator? In housebot, Each thread has its own random number generator instance. Besides avoiding a bottleneck as each thread generates random numbers, it also opens the door for repeatable behavior in a single worker thread. ___ 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] Efficiently selecting a point to play in a random playout
On Tue, 2007-06-05 at 12:28 -0700, Peter Drake wrote: Don't maintain the list of legal moves -- maintain the list of vacant points (almost all of which are legal). When it's time to pick a move, pick a random point in the list and iterate through checking each move for legality. As soon as you find a legal one, play it. But you can do both. It's simpler than it sounds. I'm essentially doing what you suggest, but it's perfectly random, no bias. And I doubt there is any cost that can be easily measured. So I'm only temporarily maintaining a list of illegal but unoccupied points - this list gets discarded as soon as a legal move is tried. What you are doing is to avoid the call to the random number generator by trying the moves as a circular list. This may be faster, but it's biased, perhaps the bias is insignificant enough that it doesn't have an impact on the strength. You might improve the bias by shuffling on the fly, perhaps when you find a legal move in the un-occupied point section of the list you could do a swap with the first move and a random move. I'm wondering if the biased ordering of the list persists from move to move? Maybe I benchmark your idea at some point. - Don (My legality check does eliminate playing in a probable eye.) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Tue, 2007-06-05 at 15:58 -0400, Don Dailey wrote: You might improve the bias by shuffling on the fly, perhaps when you find a legal move in the un-occupied point section of the list you could do a swap with the first move and a random move. I'm wondering if the biased ordering of the list persists from move to move? With the presence of illegal moves, this is always biased even with some shuffling (there is always some move more likely to be chosen that some other move), but on the first pass (starting from a random list) it doesn't matter, the bias itself is random (if that makes any sense.) If the bias changes from move to move, then the whole thing is effectively random.But it's not time-effective to scramble the un-occupied points section after every move. Interesting stuff. If avoiding RNG is a big saver, then I don't know if my incremental shuffle slows it down too much. I also am not sure whether it introduces enough randomness to make a big difference (because it still doesn't make it truly random, it just introduces some chaos to helps the situation.) - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Tue, 2007-06-05 at 13:12 -0700, Peter Drake wrote: So I'm only temporarily maintaining a list of illegal but unoccupied points - this list gets discarded as soon as a legal move is tried. Does that mean you have to regenerate the list every move? I keep the list of un-occupied points - but the tiny list of illegal points gets regenerated from move to move. However, this list is so tiny that it rarely amounts to more than 0 moves. Near the end of the game it could get bigger, but if it does it is starting to save some real time. I think this is win/win. What you are doing is to avoid the call to the random number generator by trying the moves as a circular list. This may be faster, but it's biased, perhaps the bias is insignificant enough that it doesn't have an impact on the strength. No, I pick a random point in the list every time, so there's still a call to the random number generator. Just proceeding through the list would be horribly biased (unless the list were pre-shuffled, as I was doing previously). So it's possible that in a degenerate case you could pick many illegal moves over and over again. Technically, you could get into an infinite loop if the period of your RNG was such that a legal move could not get seen. But I'm being really picky :-) I am perhaps being too anal making sure I don't choose the same illegal move twice. However the code is trivial and it's not a major difficulty managing. But I'm wondering if starting at a random point in a list of unoccupied points and searching sequentially is really that terrible?Another idea I have is that when you do hit an illegal point, swap it with a random element so that this particular bias point is changed for the next move, then continue to search sequentially for a legal move. You could eliminate most of the RNG calls and the swaps. But there are probably not that many anyway. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Jun 5, 2007, at 12:58 PM, Don Dailey wrote: On Tue, 2007-06-05 at 12:28 -0700, Peter Drake wrote: Don't maintain the list of legal moves -- maintain the list of vacant points (almost all of which are legal). When it's time to pick a move, pick a random point in the list and iterate through checking each move for legality. As soon as you find a legal one, play it. But you can do both. It's simpler than it sounds. I'm essentially doing what you suggest, but it's perfectly random, no bias. And I doubt there is any cost that can be easily measured. So I'm only temporarily maintaining a list of illegal but unoccupied points - this list gets discarded as soon as a legal move is tried. Does that mean you have to regenerate the list every move? What you are doing is to avoid the call to the random number generator by trying the moves as a circular list. This may be faster, but it's biased, perhaps the bias is insignificant enough that it doesn't have an impact on the strength. No, I pick a random point in the list every time, so there's still a call to the random number generator. Just proceeding through the list would be horribly biased (unless the list were pre-shuffled, as I was doing previously). You might improve the bias by shuffling on the fly, perhaps when you find a legal move in the un-occupied point section of the list you could do a swap with the first move and a random move. I did something like this in an earlier version. I'm wondering if the biased ordering of the list persists from move to move? Maybe I benchmark your idea at some point. Feel free... Peter Drake http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
-ansi -Wall -pedantic Why not add -Werror so gcc rejects to compile code with warnings ? Regards Martin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
When writing C/C++ for multi-platform student assignments using gcc, we always used the args: -ansi -Wall -pedantic Literally use the ANSI standard turn all warnings on and be pedantic about warnings. This, of course, won't help with libraries not being found. cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Hello, When writing C/C++ for multi-platform student assignments using gcc, we always used the args: -ansi -Wall -pedantic Maybe it depends on the gcc versions, but I always use -Wall -W rather than only -Wall. -W turns on (important) warnings which are not turned on with only -Wall, and as usual warnings are much more important than errors :-). I agree that it is not related to what is reported here, sorry :). Cheers, Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Hola, Álvaro: Álvaro Begué wrote: Could not compile libego is not a very helpful error message. What exactly did the compiler complain about? My guess is that you don't have the required boost libraries installed. Yes. It must be that. I didn't know about boost libraries. Where can I find that? Actually, in order to get the content of a particular point, we ask its neighbor on the right :) . My biggest patterns are up to 40 neighbors (Manhattan distance = 4) because that includes all nobi, iken tobi, niken tobi, keima and ogeima relations (+ more) and because it makes a difference between the third and the fourth line and between the fourth line and above. But, as you do, I use the nearest neighbors in the lower bits as indices of many LUTs that give immediate answers to lots of questions. Oh, I would be curious to see how you remove a captured string with no loops. So would I. I did not say that the whole program is in assembly language. The assembly language parts are rather short and straightforward. I change conditional jumps by table xlat or by conditional moves. For instance, a function that computes a Zobrist hash of a mask, cmoves a zero and xors zero rather than jumping around the xor instruction if there is no stone. And of course, rather than writing something ridiculously academic, like: Function DoWhateverWith40neighbors(x, y : integer) for dx := -4 to 4 do begin for dy := -4 to 4 do begin if (x + dx = 0) and (x + dx 19) and (y + dy = 0) and (y + dy 19) and (ABS(dx - dy) = 4) do whatever end everything I keep 81 different asm functions for each possible mapping of the borders Instead of calling a function: MyFun(x, y, a, b, c) I call MyFun[wMv9x9](a, b, c) where MyFun[wMv9x9] is a array of pointers to functions and x, y are implicit in the function called. Example: UpNeib_NI[wMv9x9](byte(bijNP), longint(pS), CardinalsBPR); is compiled to: mov esi,[esi*4+UpNeib_NI] xor eax, eax mov al, bl mov ecx, [CardinalsBPR} mov edx, [ebp-$30] call esi (It wouldn't be better with a call to a fixed address.) And the function, instead of the ridiculous loops and conditions is, (say 150 lines) of: or [edi + 2], al shl al, 4 or [edi + 1 + 12], al mov al, [edx + ecx*2 - SizeOf_bccCell + 3] xlat shl al, 2 or [edi + 1 + 12], al shl al, 4 or [edi + 2], al mov al, [edx + ecx*4 + 3] xlat or [edi + 4], al or [edi + 4 + 12], al add edx, ecx mov al, [edx + ecx*2 + SizeOf_bccCell + 3] xlat shl al, 2 or [edi + 4], al shl al, 4 or [edi + 6 + 12], al mov al, [edx + ecx + 2*SizeOf_bccCell + 3] xlat shl al, 4 Now you understand why the board has over 80 000 lines of asm source. Typical 40 neighbor functions have 81 clones and 150 lines. It is only in these functions where there are no conditional jumps or loops, not in the program. But I keep trying ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Lukasz Lew wrote: Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? I only wanted to compare performance ( and see what good ideas you had ;-) ) but could not compile libego. Neither with Microsoft Visual Studio nor with Borland Turbo C++. I am 100% Borland because of the ease of assembly language implementation. Borland passes parameters in CPU registers in a documented way and has an extremely straightforward use of local variables and record structure from asm source code to write things easily that work on the first run. At least for Windows programmers, providing a solution that compiles with major IDEs would help. I assume what you do is standard in Linux, but the things the compiler did not understand neither did I, and I could not find the time for googleing. Anyway, I think a go board system is way too important to be universal. I already have a board system in GoKnot that surely outperforms most of the current programs and my new board system I call HBS (Hologram Board System) does not copy a single line from the old one. I call it a hologram because, as in a hologram, each part contains information about the whole picture. In my board, each cell contains a mask of its nearest neighbors. When you place a stone, everything is updated by automatically written assembly language functions. These functions do not have variables except CPU registers and the board, do not have conditional jumps or loops, of course, no stack frames, of course support multi-threading, etc. The board is *never* rescanned whatever happens. Placing a stone on a 31x31 board is not a clockcycle slower than on a 9x9 board (these are my limits) assuming it finds the same chains. Every bit of info on the board is only updated if it may have changed and only once. With this board I will be able to try things that cannot be tried with libego, but as Don said, If you have a hammer, everything looks like a nail., for lots of methods not using shapes my board is way too heavy, (although possibly faster than most in small pattern modes) so I will write engines with shapes (and Statistics) for a while. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On 5/30/07, Jacques Basaldúa [EMAIL PROTECTED] wrote: Lukasz Lew wrote: Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? I only wanted to compare performance ( and see what good ideas you had ;-) ) but could not compile libego. Neither with Microsoft Visual Studio nor with Borland Turbo C++. I am 100% Borland because of the ease of assembly language implementation. Borland passes parameters in CPU registers in a documented way and has an extremely straightforward use of local variables and record structure from asm source code to write things easily that work on the first run. At least for Windows programmers, providing a solution that compiles with major IDEs would help. I assume what you do is standard in Linux, but the things the compiler did not understand neither did I, and I could not find the time for googleing. Could not compile libego is not a very helpful error message. What exactly did the compiler complain about? My guess is that you don't have the required boost libraries installed. Anyway, I think a go board system is way too important to be universal. I already have a board system in GoKnot that surely outperforms most of the current programs and my new board system I call HBS (Hologram Board System) does not copy a single line from the old one. I call it a hologram because, as in a hologram, each part contains information about the whole picture. In my board, each cell contains a mask of its nearest neighbors. When you place a stone, everything is updated by automatically written assembly language functions. These functions do not have variables except CPU registers and the board, do not have conditional jumps or loops, of course, no stack frames, of course support multi-threading, etc. The board is *never* rescanned whatever happens. Placing a stone on a 31x31 board is not a clockcycle slower than on a 9x9 board (these are my limits) assuming it finds the same chains. Every bit of info on the board is only updated if it may have changed and only once. Funny that. We store 16 bits per point, where the contents of the 8 neighbours is encoded. Actually, in order to get the content of a particular point, we ask its neighbour on the right :). John came up with this and other ideas, like a method to detect if a string is in atari and to find its last liberty in constant time. We don't rescan the board either. Well, only once per simulation, but that's not in the critical section. The only thing you are doing that we are not is using assembly, but I'd rather keep things flexible and portable at this point. Oh, I would be curious to see how you remove a captured string with no loops. With this board I will be able to try things that cannot be tried with libego, but as Don said, If you have a hammer, everything looks like a nail., for lots of methods not using shapes my board is way too heavy, (although possibly faster than most in small pattern modes) so I will write engines with shapes (and Statistics) for a while. The reason we don't use libego either is similar. We need a completely different underlying structure to be able to pick random moves following the distribution we want. I don't think Lukasz can do anything to his library so it would satisfy a significant fraction of programmers, since we all have different needs. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Álvaro Begué wrote:
At least for Windows programmers, providing a solution that
compiles with major IDEs would help. I assume what you do is
standard in Linux, but the things the compiler did not understand
neither did I, and I could not find the time for googleing.
With 1.08 version of lego and Turbo C++, there are too many errors
related to namespaces, system libraries etc.
With *wx-Devcpp* http://wxdsgn.sourceforge.net/ windows compilation is
relatively straightforward. Create a new project file (main.cpp and
gtp.cpp is enough for benchmarking), Replace get_seconds(), install
boost library (a package is available at devpaks.org if you don't want
to compile the library) and you are done.
---
float get_seconds () {
return double(clock()) / double(CLOCKS_PER_SEC);
}
I know this is not a precise way of calculating time, but if it is good
enough for fruit, it is good enough for me.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On 5/30/07, Berk Ozbozkurt [EMAIL PROTECTED] wrote: Álvaro Begué wrote: At least for Windows programmers, providing a solution that compiles with major IDEs would help. I assume what you do is standard in Linux, but the things the compiler did not understand neither did I, and I could not find the time for googleing. Hey, I didn't write that! :) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Sun, 27 May 2007, ?ukasz Lew wrote: Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? I am a C-programmer and I don't like the GPL license. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
But I remember thinking that it might still be useful for evaluation. I remember thinking that that if you compared pseudo liberties to real liberties it might tell you something. If the ratio was high (a lot more pseudo liberties) it might indicate that the liberties are easy to protect. But there was a definite negative response to the idea that they were useful in any way. - Don On Sun, 2007-05-27 at 23:54 -0400, Jason House wrote: Don Dailey wrote: I remember that conversation and the negative response. But to be fair to the ones who were negative, you presented this as an evaluation feature that could be calculated quickly, not as a pure performance optimization. The negative response was in response to the suggestion that it might be used as an evaluation feature instead of true liberties. At least that is how I remember it. Oh, I definitely didn't mean to say or imply that those who gave a negative reaction were wrong. I apologize if anyone took my post that way! At the time, MC wasn't a big push in computer go, and I know I wasn't thinking about rapid random games. You're absolutely right that I was looking to use it as some kind of quick and dirty evaluation feature. Honestly, I think the feedback was helpful too. I ended up making a concept of local liberties that were slightly smarter than pseudo liberties and were much more useful for non-MC computations. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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] Efficiently selecting a point to play in a random playout
i'd need to write a C interface for it, then try to maintain compatibility through new releases. (AKA i'd effectively end up rewriting it). it might seem like less of a burden for me to just write my code in C++, but i guess i'm just a caveman who is stuck in his old ways and would rather reinvent the wheel than switch language horses just to save some effort. s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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/ Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Yeah, I suffer from this, too. (There's also the fact that using someone else's code would disqualify you from the formal division of the KGS tournaments.) Here's a heroic tale of not-invented-here syndrome for your amusement: http://worsethanfailure.com/Articles/slammerSCR.aspx Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 12:55 PM, steve uurtamo wrote: i'd need to write a C interface for it, then try to maintain compatibility through new releases. (AKA i'd effectively end up rewriting it). it might seem like less of a burden for me to just write my code in C++, but i guess i'm just a caveman who is stuck in his old ways and would rather reinvent the wheel than switch language horses just to save some effort. s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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/ __ __Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ 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] Efficiently selecting a point to play in a random playout
Here is what I do, don't know if it's best Basically you want a list of empty points, since most of them are legal. When I apply a move to the board I then do any needed legality testing. At the beginning I start with a list of ALL points on the board. When a non-empty point is encountered I put it away, placing it behind a point in the list that represents all the occupied points. To find a random move I choose an index at random among the set of untested points. If that point is occupied, it gets put away, if it's not it's the next move (and it still get's put away since it will not be occupied.)If the point is not occupied but illegal, it gets set aside until a legal move is found - then it is good again. When a capture occurs, I have found nothing much faster than just starting all over, due to my very simplistic data structure.One could take the time to restore those points but this is expensive with naive data structures. It's often not productive to play to points that have been captured - often a complete waste of time for either side. There may be some enhancements where this fact is used to advantage, but I'm not sure how to reliably test when this should and shouldn't be done. Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. - Don On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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] Efficiently selecting a point to play in a random playout
I'm a language caveman too then. I really avoid C++ even though I learned the basics long ago. I really hate it. It's not like I'm an old dog that can't learn new tricks - I have experimented and explored many computer languages and I am versatile in many. It's one of those languages that to me feels wrong - like a big ugly hack on top of something that isn't that pretty to start with.I tolerate C because it's the best at speed. I don't have a good reason to tolerate C++. Don't want to start a language flame war though. I love object oriented but I always reach for something else when I'm compelled to go that way. Maybe it's caveman of me, but I don't associate object oriented with super high performance programming. Of course I realize that c++ can be almost as fast as C if you know what you are doing and avoid certain things - but it seems like an insane combination to me - OOP is high level, C is low level. C++ seems like a bad marriage. I'm sure you can get used to anything. If you get really familiar and comfortable with C++ you probably can live with it and even believe it to be a wonderful thing. But that's no shocker - no matter how awful a language is you will get many fanatics who seem to believe it's the most wonderful thing ever invented! - Don On Sun, 2007-05-27 at 13:02 -0700, Peter Drake wrote: Yeah, I suffer from this, too. (There's also the fact that using someone else's code would disqualify you from the formal division of the KGS tournaments.) Here's a heroic tale of not-invented-here syndrome for your amusement: http://worsethanfailure.com/Articles/slammerSCR.aspx Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 12:55 PM, steve uurtamo wrote: i'd need to write a C interface for it, then try to maintain compatibility through new releases. (AKA i'd effectively end up rewriting it). it might seem like less of a burden for me to just write my code in C++, but i guess i'm just a caveman who is stuck in his old ways and would rather reinvent the wheel than switch language horses just to save some effort. s. - Original Message From: Łukasz Lew [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout Hi, I've tested many approaches, and the one I implemented is clearly the best. The bias that Peter Drake talks about is negligible and doesn't have a noticeable impact on playout results. (and uniformity of playout isn't something to fight for in MC Go) Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? Best Regards, Lukasz Lew On 5/27/07, Jason House [EMAIL PROTECTED] wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ 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/ Yahoo! oneSearch: Finally, mobile search that gives answers, not web links. http://mobile.yahoo.com/mobileweb/onesearch?refer=1ONXIC ___ 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] Efficiently selecting a point to play in a random playout
On Sun, 2007-05-27 at 13:21 -0400, Jason House wrote: As I get into the home stretch of rewriting the core of my bot, I want to add a monte carlo player. I've realized that picking a random move to play is non-trivial since it's such a key element in playout speed. An array of legal positions has easy lookup, but may not be easy to maintain... I guess it'd require storing a mapping between board position and index into the legal positions array so that a move that becomes illegal can be quickly removed (by moving the item from the tail of the array into the empty location). Looking at libego, I see it does a variant on this where it maintains an array of empty points. If the random index it picks is disallowed, it'll scan through the array (with wrapping around the end) until it either finds an allowed move or returns to its starting point. Which methods have people tried and what works best? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ If I had it to do over again, knowing what I know now, I would not spend a lot of time optimizing random games. These optimizations don't make much difference for heavy playouts and heavy playouts are better. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
?ukasz Lew wrote: Jason, can You tell me why You don't want to use libego instead? Actually this is open question to all comp-go readers. Is libego too complicated? Do You have problems with compilation? Or You are not comfortable with the GNU license? Any other reason? I probably have a lot of little reasons. When it first came out, I already had my own C++ based framework and didn't really worry about switching or not. Of course, now that I'm rewriting my bot, using someone else's framework would make more sense. When I look at libego, the big turn offs would be the lack of documentation, coding style (the use of #defines, global variables, hard coding to a set board size, etc...), and lack of a collaborative environment such as sourceforge (repository access, bug tracking, etc...). My rewrite is using a little known language D. Here are some items that have been developed in the housebot rewrite that I really like: * Multi-threaded core routines * Inter-process communication with delegates (function objects) instead of fixed data structures and special handlers (like the MPI uses I've seen) * Decentralized GTP command registration. I originally used the GTP from Gnu Go but didn't like how many places in the code I had to modify when adding new (debug) functions. * Variable board sizes and shapes (currently, rectangular boards). Instead of just supporting one best implementation, I want to have a flexible framework that supports the interests of many programmers. Eventually, the core will allow a variety of plug and play components/algorithms... I want to support different types of boards (such as bit boards and 3D boards), different types of chain tracking (such as the disjoint set data structure or gnu style int chain ID), and different search methods (UCT, alpha beta, PN, df-PN, etc...). I'm always recruiting people to help if that inspires anyone ;) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
I struggled with unto a lot, too. In the current version of Orego, there is no undo, just a way to copy a board relatively quickly. This falls under keep the common case fast again: you only undo once per playout, so it's faster to make a copy. (For the real board, where actual games moves are played, maintain a stack of board state copies for undoing.) Peter Drake http://www.lclark.edu/~drake/ On May 27, 2007, at 5:28 PM, Jason House wrote: Don Dailey wrote: Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. Both pseudo liberties as well as disjoint set chain tracking. Curiously enough, they're both things I independently came up with when I was designing HouseBot the first time around, but included neither in the open source version. Pseudo liberties had a very negative response on the computer go mailing list at the time, so I chose something closer to real liberty tracking. When I implementing undo's I figured the disjoint set stuff was too complex and might scare away developers on an open source project (simple, easy to read code is a big plus). I still wonder if I was the original creator of either concept... ___ 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] Efficiently selecting a point to play in a random playout
Darren Cook wrote:
Jason House also mentioned hard coding to a set board size, I think
libego can be used at least up to 19x19, just by changing the
board_size setting in board.cpp (it also supports hexagonal boards).
Or did you mean being able to make one binary for all board sizes? I
feel that that flexibility doesn't justify the performance hit.
One binary for many board sizes is pretty easy and comes at nearly zero
runtime cost... Templates could at least allow common cases such as
running on KGS to work well (19x19, 13x13, 9x9)
template int boardsize
class board{
}
or the D equivalent...
class board(int boardsize){
}
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
On Sun, 2007-05-27 at 19:31 -0400, [EMAIL PROTECTED] wrote: If I had it to do over again, knowing what I know now, I would not spend a lot of time optimizing random games. These optimizations don't make much difference for heavy playouts and heavy playouts are better. - Dave Hillis Yes, I absolutely agree with this. It's probably best to save the optimizations for specific versions - when you know what you want. With a program in constant development, it's not so easy to decide at what point this makes sense. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
I remember that conversation and the negative response. But to be fair to the ones who were negative, you presented this as an evaluation feature that could be calculated quickly, not as a pure performance optimization. The negative response was in response to the suggestion that it might be used as an evaluation feature instead of true liberties. At least that is how I remember it. - Don On Sun, 2007-05-27 at 20:28 -0400, Jason House wrote: Don Dailey wrote: Lukasz Lew does something far more sophisticated and very fast using the concept of pseudo liberties which you might want to look into. Both pseudo liberties as well as disjoint set chain tracking. Curiously enough, they're both things I independently came up with when I was designing HouseBot the first time around, but included neither in the open source version. Pseudo liberties had a very negative response on the computer go mailing list at the time, so I chose something closer to real liberty tracking. When I implementing undo's I figured the disjoint set stuff was too complex and might scare away developers on an open source project (simple, easy to read code is a big plus). I still wonder if I was the original creator of either concept... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Efficiently selecting a point to play in a random playout
Don Dailey wrote: I remember that conversation and the negative response. But to be fair to the ones who were negative, you presented this as an evaluation feature that could be calculated quickly, not as a pure performance optimization. The negative response was in response to the suggestion that it might be used as an evaluation feature instead of true liberties. At least that is how I remember it. Oh, I definitely didn't mean to say or imply that those who gave a negative reaction were wrong. I apologize if anyone took my post that way! At the time, MC wasn't a big push in computer go, and I know I wasn't thinking about rapid random games. You're absolutely right that I was looking to use it as some kind of quick and dirty evaluation feature. Honestly, I think the feedback was helpful too. I ended up making a concept of local liberties that were slightly smarter than pseudo liberties and were much more useful for non-MC computations. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
