Re: [computer-go] How to "properly" implement RAVE?
On Sun, Feb 8, 2009 at 1:42 PM, Petr Baudis wrote:
> On Sat, Jan 17, 2009 at 08:29:32PM +0100, Sylvain Gelly wrote:
> > A small point: in "PlayoutOutTree", just after "if
> > (!played.AlreadyPlayed(move)) {", there should have a
> "played.Play(move)".
> > I believe it does not change the final result (as the check is also done
> in
> > the backup, and the move played in the backup), but I simply forgot that
> > line (that should make moves_played_out_tree smaller).
> >
> > To avoid confusion, I repost the pseudo code with that correction (and
> > hoping the indentation is not broken by the email editor once again).
>
> Thank you so much for this! I have switched my RAVE implementation to
> this formula and the bot has gotten noticeably stronger, though I
> apparently still have some bugs to chase, since it seems to have trouble
> considering strongest opponent's responses and frequently focuses on
> unreasonable opponent's replies instead of the obvious (e.g. keeping a
> group of stones in atari). Maybe I need better prior hinting...
>
> I have few questions. Of course, please feel free to skip questions
> about particular constants if you feel that's giving away too much. :-)
>
> > ChooseMove(node, board) {
> > bias = 0.015 // I put a random number here, to be tuned
> > b = bias * bias / 0.25
>
> Maybe it would be cleaner to define b = 1 / rave_equiv, where rave_equiv
> is the number of playouts RAVE is thought to be equivalent of? Or is the
> meaning of this constant actually different?
>
The meaning is supposed to be the difference between the expected value of
AMAF and the expected value of the tree. But at that point it is just a
constant, so I am not sure there is a "good" interpretation.
>
> What value works best for people? I did not do much tuning yet, but I
> use b=1/3000. I see Fuego uses b=1/5000. (This example b=1/.)
I believe the actually value depends on the other parts of your
implementation, namely the playouts, the prior you use in the tree and the
exploration term (there was none in the pseudo code I posted, but you might
use one).
>
>
> > best_value = -1
> > best_move = PASSMOVE
> > for (move in board.allmoves) {
> > c = node.child(move).counts
> > w = node.child(move).wins
> > rc = node.rave_counts[move]
> > rw = node.rave_wins[move]
> > coefficient = 1 - rc / (rc + c + rc * c * b)
> > value = w / c * coef + rw / rc * (1 - coef) // please here take care
> of
> > the c==0 and rc == 0 cases
> > if (value > best_value) {
> > best_value = value
> > best_move = move
> > }
> > }
> > return best_move
> > }
>
> I have two questions here:
>
> * Is the FPU concept abandoned? Or what values are reasonable? It seems
> to me 1.0, which is usually recommended, is obviously too big here
> since that's the upper bound of the value already. So far I have tried
> 0.6 and 0.7 but both just make my bot slightly weaker.
>
> * How to accomodate prior knowledge? (I'm using grand-parent heuristics,
> atari liberties, and few patterns.) Do you use it to fill normal
> counts, RAVE values or both? What count values work best for you?
> I have settled on 50 playouts.
The FPU concept is here replaced by the prior value. I used
node.rave_wins[move]
and node.rave_counts[move] when the node is initialized. If you don't want
to use go knowledge, you can initialize those values to something like 7 and
14 respectively. Grand-parent heuristics did not work at all in my
experiments (was even very bad). The heuristics I was using were:
- save a chain (positive prior)
- self atari (negative prior)
- match a simple 3x3 pattern (hane, cut, and a few others I don't
remember) (positive prior).
For node.rave_counts[move], 50 seems a little high. I think I was using
values around 15, but it was not very sensitive (50 was working almost as
well as 15). I give those numbers from memory, they may be quite off.
Sylvain
>
>
> --
>Petr "Pasky" Baudis
> The average, healthy, well-adjusted adult gets up at seven-thirty
> in the morning feeling just terrible. -- Jean Kerr
> ___
> 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] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
Hello, today MoGo (with 7 handicap stones) played two games against the top Taiwan pro Jun-Xun Zhou (9p). MoGo won the first game, Jun-Xun Zhou the second one. Time must have been with about 40 seconds per move in the average. sgf are under http://www.gokgs.com/gameArchives.jsp?user=mogo It are the two "handicap 7" games from February 10, 2009. Cheers, Ingo. -- Jetzt 1 Monat kostenlos! GMX FreeDSL - Telefonanschluss + DSL für nur 17,95 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K11308T4569a ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
> > Time must have been with about 40 seconds per move > in the average. > MoGo plays in 30s on the client machine - the 40s for KGS is for ensuring that there's no problem with net lag. Info on the game in chinese: http://www.cdnews.com.tw/cdnews_site/docDetail.jsp?coluid=121&docid=100661355 Translation by a friend of the comment given by the human after the first game at the end of this email. Info about Zhou Junxun:http://en.wikipedia.org/wiki/Zhou_Junxun The second game was lost very quickly after a semeai in the upper-right part. Best regards, Olivier english translation = He said during the first match(19L), Mogo appeared a high unprofessional level(dan) in the middle of match and some times did professionals maneuvers . Mogo win the game easily and this is the first time the computer defeat the professional player [[[Zhou Junxun won easily a few months ago against mogo]]]. This made him a little sad when he was still amazed. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
Do you need a full 10s margin for netlag? Terry McIntyre -- Libertarians Do It With Consent! From: Olivier Teytaud To: computer-go Sent: Tuesday, February 10, 2009 9:42:04 AM Subject: Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p) Time must have been with about 40 seconds per move in the average. MoGo plays in 30s on the client machine - the 40s for KGS is for ensuring that there's no problem with net lag. Info on the game in chinese: http://www.cdnews.com.tw/cdnews_site/docDetail.jsp?coluid=121&docid=100661355 Translation by a friend of the comment given by the human after the first game at the end of this email. Info about Zhou Junxun:http://en.wikipedia.org/wiki/Zhou_Junxun The second game was lost very quickly after a semeai in the upper-right part. Best regards, Olivier english translation = He said during the first match(19L), Mogo appeared a high unprofessional level(dan) in the middle of match and some times did professionals maneuvers . Mogo win the game easily and this is the first time the computer defeat the professional player [[[Zhou Junxun won easily a few months ago against mogo]]]. This made him a little sad when he was still amazed. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
Do you need a full 10s margin for netlag? > We have to take care of the variance of the lag more than of the mean of the lag I guess. But I have not tested this myself, Arpad was the operator in Taiwan and decided himself. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Vacation reply
Thanks to massive amounts of spam, I no longer monitor this account. Please update your address book with my new address (joe.hebl at gmail.com). Thanks, Joe ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
Wow! Do you happen to have measurements of the lag? Terry McIntyre -- Libertarians Do It With Consent! From: Olivier Teytaud To: computer-go Sent: Tuesday, February 10, 2009 9:52:00 AM Subject: Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p) Do you need a full 10s margin for netlag? We have to take care of the variance of the lag more than of the mean of the lag I guess. But I have not tested this myself, Arpad was the operator in Taiwan and decided himself. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
On Feb 10, 2009, at 12:42 PM, Olivier Teytaud wrote: Time must have been with about 40 seconds per move in the average. MoGo plays in 30s on the client machine - the 40s for KGS is for ensuring that there's no problem with net lag. Info on the game in chinese: http://www.cdnews.com.tw/cdnews_site/docDetail.jsp?coluid=121&docid=100661355 Translation by a friend of the comment given by the human after the first game at the end of this email. Info about Zhou Junxun:http://en.wikipedia.org/wiki/Zhou_Junxun The second game was lost very quickly after a semeai in the upper- right part. SGF files? I looked at the gokgs archives for MoGoTitan, but didn't see anything recent. Best regards, Olivier english translation = He said during the first match(19L), Mogo appeared a high unprofessional level(dan) in the middle of match and some times did professionals maneuvers . Mogo win the game easily and this is the first time the computer defeat the professional player [[[Zhou Junxun won easily a few months ago against mogo]]]. This made him a little sad when he was still amazed. ___ 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] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
> SGF files? I looked at the gokgs archives for MoGoTitan, but didn't see > anything recent. > They are archived under Mogo, aren't they? http://www.gokgs.com/gameArchives.jsp?user=mogo The games that we've been talking about were the H7 games, I believe. Eric Dunham — Ricky1, Owner and Administrator of the KGS Enclave and the Enclave Magazine ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
The game can be found here http://www.lri.fr/~teytaud/H7.sgf or on KGS, for user "mogo". I'm posting these results, but I must precise that I was not operating myself - Arpad Rimmel did operate, and Guillaume Chaslot was also very involved in the preparation. MoGo was running on Huygens (in Amsterdam) as usual. The lag is probably conservatively estimated (it's better to be too much conservative than not enough conservative :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GPGPU
- Original Message > From: Petr Baudis > There has been some talk about implementing monte-carlo playouts on > GPUs in the past, I have heard rumours about Polish bachelor student > doing libego -> GPGPU conversion as a project, etc. but I know of > nothing concrete ever materializing - is anybody aware of anything? > > We have recently bought very high-end nVidia card at our university > department for trying out GPGPU and I'm thinking of a little project for > myself, maybe... > > I'm not much skilled in this kind of programming though, so I'm not > quite sure what the best design approach to take would be... my current > ideas so far are either > > (i) Have one game per pipeline, and in each cycle, take a board and > transform it by playing a random move (or possibly have an extra cleanup > cycles if capturing stones would take too long); you should be able to > do some neat pattern matching and so too > > (ii) Have one intersection per pipeline, in one cycle play a random > move, then have board_height cycles for captures and liberty updates > to ripple through to all the neighbors. The code would be much more > streamlined, but I'm not sure yet if there is a good way to do the > rippling - ORing bitmaps? > > I guess there is a lot of things to try out. There may be ways to implement monte carlo effectively on GPUs - but some other algorithms might make more effective use of the different capabilities of the GPU. For instance, neural networks might map well to a GPU. It might also be possible to collect a lot of useful information about shapes using cellular automata. The GPU might be the main engine, or it might be deployed to collect information about the current board situation ( such as the most interesting plays ) which is then fed to the CPU for creation of a tree structure. Hard to say a priori -- lots of room for experimentation! ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GPGPU
Maybe it's possible to rewrite the playout such that there is no branching. Álvaro Begué wrote: I've thought about this a bit, although I haven't implemented anything. I think one has to try for (i), but given the huge penalties you pay for branching if not all processors in a group follow the same path, I can't see how to make it work. (ii) would be a lot easier, and one can then do quite a bit of work at each intersection, but the end result might not be much better than with a traditional single core. It's unclear to me how cleaning up captured stones would be implemented in either case, and I don't see why you think that board_height cycles would be enough. If you make any progress with either approach, I would love to hear about it. Álvaro. On Mon, Feb 9, 2009 at 7:44 PM, Petr Baudis wrote: Hi! There has been some talk about implementing monte-carlo playouts on GPUs in the past, I have heard rumours about Polish bachelor student doing libego -> GPGPU conversion as a project, etc. but I know of nothing concrete ever materializing - is anybody aware of anything? We have recently bought very high-end nVidia card at our university department for trying out GPGPU and I'm thinking of a little project for myself, maybe... I'm not much skilled in this kind of programming though, so I'm not quite sure what the best design approach to take would be... my current ideas so far are either (i) Have one game per pipeline, and in each cycle, take a board and transform it by playing a random move (or possibly have an extra cleanup cycles if capturing stones would take too long); you should be able to do some neat pattern matching and so too (ii) Have one intersection per pipeline, in one cycle play a random move, then have board_height cycles for captures and liberty updates to ripple through to all the neighbors. The code would be much more streamlined, but I'm not sure yet if there is a good way to do the rippling - ORing bitmaps? I guess there is a lot of things to try out. -- Petr "Pasky" Baudis The average, healthy, well-adjusted adult gets up at seven-thirty in the morning feeling just terrible. -- Jean Kerr ___ 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] GPGPU
I don't know if that's what you're already looking at, but recently Apple announced their new version of OS X called 'Snow Leopard' which supposedly focuses mostly on improvements in the use of multiple processing. And that includes the GPU. The module that binds it all together is called 'Grand Central'. I don't know much of the details, just picked up some buzz-words from articles like these: http://gizmodo.com/5017615/giz-explains-mac-os-106-snow-leopard-parallel-processing-and-gpu-computing If you google around a bit you may easily find more information about it. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] GPGPU
Mark Boon wrote: I don't know if that's what you're already looking at, but recently Apple announced their new version of OS X called 'Snow Leopard' which supposedly focuses mostly on improvements in the use of multiple processing. And that includes the GPU. The module that binds it all together is called 'Grand Central'. I don't know much of the details, just picked up some buzz-words from articles like these: http://gizmodo.com/5017615/giz-explains-mac-os-106-snow-leopard-parallel-processing-and-gpu-computing If you google around a bit you may easily find more information about it. The most relevant part for GPU programming is OpenCL, which is expected to have about the same expressive power as nvidia's CUDA. But it won't change the processing and communication characteristics of the GPU. You still need to come up with some really clever vectorization tricks yourself, if you want to make good use of the GPU for go algorithms. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
