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

Re: [computer-go] Efficiently selecting a point to play in a random playout

Thank you for your ideas. The shapes Rémi is using have values as high as 143473. Of course, that would invalidate my idea. But I planned trimming the upper probability to a reasonable number, say 100 as scaling everything to a 1..100 scale (in the runtime database). I don't know yet if that make

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; . # # .

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, ..

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 (

Heavy playouts (was Re: [computer-go] Efficiently selecting a point to play in a random playout)

Let me mildly retract this and say that method 2 appears to be better than method 1. Peter Drake http://www.lclark.edu/~drake/ On Jun 6, 2007, at 2:51 PM, Peter Drake wrote: I assume you mean "...than finding tricks to accelerate RANDOM playouts". I've been messing around with where to

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 =

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

On 6/6/07, Rémi Coulom <[EMAIL PROTECTED]> wrote: Á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

Re: [computer-go] Efficiently selecting a point to play in a random playout

I assume you mean "...than finding tricks to accelerate RANDOM playouts". 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 o

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] > 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. Currentl

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, ther

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

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

On 6/6/07, Jacques Basaldúa <[EMAIL PROTECTED]> wrote: For the problem in which moves have probability in {0, 1/n} of being selected (n = number of legal moves or empty points depending on the approach), what Don does, i.e.: Keeping a vector of selectable/not selectable points with a moving limi

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 Ba

Re: [computer-go] Efficiently selecting a point to play in a random playout

For the problem in which moves have probability in {0, 1/n} of being selected (n = number of legal moves or empty points depending on the approach), what Don does, i.e.: Keeping a vector of selectable/not selectable points with a moving limit: When you have to fill a gap, do it immediately by mov

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

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

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

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

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

On Tue, 2007-06-05 at 15:18 -0400, Jason House wrote: > Do you eliminate all illegal/stupid positions? Filling eyes? Suicide > plays? Disallowing suicides likely means you need a list for each > color. Sadly, if a move was rejected because it was an illegal > suicide and then the enemy chain put

Re: [computer-go] Efficiently selecting a point to play in a random playout

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. (My "legality" check do

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 PROT

Re: [computer-go] Efficiently selecting a point to play in a random playout

On Jun 5, 2007, at 11:57 AM, Don Dailey wrote: But if you are taking the vacant points out it is probably not too biased as you say. Yes, that's the key point -- almost all vacant points are legal. But what I do is pretty fast. Always choose a random point but keep shrinking the list. When

Re: [computer-go] Efficiently selecting a point to play in a random playout

On 6/5/07, Don Dailey <[EMAIL PROTECTED]> wrote: 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

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

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 - ba

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

On Thu, 2007-05-31 at 12:44 +0100, Jacques Basaldúa wrote: > I keep 81 different asm functions for each possible mapping of the > borders I had a really fast all-at-once move generator for chess that worked like this. For each piece type of each color on each square was a separate move generator.

Re: [computer-go] Efficiently selecting a point to play in a random playout

>> "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? http://boost.org/

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 f

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",

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 __

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

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 l

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 c

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 Stud

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

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

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

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 us

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 Hil

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 t

Re: [computer-go] Efficiently selecting a point to play in a random playout

> 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've been studying and experimenti

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

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

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 o

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

t; effort. > > > > > > s. > > > > > > - Original Message > > From: Łukasz Lew <[EMAIL PROTECTED]> > > To: computer-go > > Sent: Sunday, May 27, 2007 2:39:55 PM > > Subject: Re: [computer-go] Efficiently selecting a p

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 encounter

Re: [computer-go] Efficiently selecting a point to play in a random playout

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

nd 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 Sent: Sunday, May 27, 2007 2:39:55 PM Subject: Re: [computer-go] Efficiently selecting a point to play in a random playout

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

Re: [computer-go] Efficiently selecting a point to play in a random playout

I've spent a lot of time struggling with this; it can have a huge impact on performance. The key thing to remember is to keep the common case fast. Orego currently maintains a list (technically a stretchable array, analogous to the java.util.ArrayList class) of vacant points. I shuffle th

[computer-go] Efficiently selecting a point to play in a random playout

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...