Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Hideki Kato]

Hi Erik,

My program is very based on MoGo's report and the paper.  Yes, I 
used FPU of 1.15.

-Hideki

Erik van der Werf: <[EMAIL PROTECTED]>:
>Hi Hideki,
>
>Your results look similar to those of Mogo as reported in their icml
>paper. When you ran this experiment, did you use anything like FPU or
>progressive widening, or did you use Levente's original design which
>always selects unvisited moves first?
>
>Regards,
>Erik
>
>
>On Wed, Feb 6, 2008 at 3:42 PM, Hideki Kato <[EMAIL PROTECTED]> wrote:
>> I found some data.  GGMC Go v2r6, against GNU Go 3.7.10 level 10, 9x9,
>>  komi 7.5, 3000 playouts/move, 2000 games match:
>>
>>  Without RAVE:   winning rate was 23.1 +- 0.9% (-209 +- 9 ELO)
>>  With RAVE:  winning rate was 65.3 +- 1.1% (+110 +- 8 ELO)
>>
>>  Though this includes some other improvements, most come from RAVE.
>>  Unlike MoGo, my best 'K' was 1000.
>>
>>  Following is my implementation of RAVE for GGMC v2r6.
>>  1) Each playout returns the score and all moves with colors played.
>>  2) While back-propagating the value (degitized score), computes the
>>  mean and the variance according to UCB1 and do the same for RAVE
>>  seperatelly.  For RAVE, the values of all (legal) moves, except played
>>  one, in a node are updated.
>>  3) In the computation of values for RAVE, the point is that there
>>  appeares three colors (as someone, I remember GCP, mentioned before).
>>  If the players' colors aren't the same then skip.  Count the value as
>>  is or negate (1 - score, for me), depending on the color of the player
>>  at the position and the color for the score.
>>  4) Before back-propagating the value of each playout, I setup a color
>>  table for all intersections of the board for speed-up, in fact
>>  (initialized with EMPTY). That is, fill the board (table[move] =
>>  color) by tracing the moves and the colors returned by the playout
>>  forward (from leaf node to end of the game). Then, by tracing the
>>  path from root to the leaf node, clear the table[move] (table[move] =
>>  EMPTY), in order to avoid duplicate counting with UCB1.
>>  5) While descending the tree, merge the values come from UCB1 and
>>  RAVE with 'K' according to the formula in the paper.
>>
>>  #Though I'm writing this by reading my source code, this description
>>  may include some errors.
>>
>>  Hope this helps,
>>
>> Hideki
>>
>>  Gian-Carlo Pascutto: <[EMAIL PROTECTED]>:
>>
>> >> I also implemented RAVE in Mango. There was a few points of improvements
>>  >> (around 60 Elo points with gnugo as reference), but as much as in the
>>  >> paper of Gelly and Silver :( (around 250 Elo points if I remember well)
>>  >>
>>  >> It might be that the effect of RAVE depends a lot on the simulation
>>  >> strategy. Indeed, sometimes my RAVE was playing very good moves but also
>>  >> very bad ones.
>>  >
>>  >I don't think the simulation strategy is the key.
>>  >
>>  >I suspect the improvement is largest when you don't do progressive 
>> widening.
>>  >
>>  >Nevertheless it would be quite interesting to see the implementation
>>  >details of ggmc's RAVE. RAVE performance is quite dependent on exact
>>  >implementation and parameters.
>>  --
>>
>> [EMAIL PROTECTED] (Kato)
>>  ___
>>
>>
>> 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/
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Sylvain Gelly]

Hi Erik,

> In the ICML version of UCT without RAVE, you did not use your First
> Play Urgency, right?
>
> I think that using FPU has an effect similar to what others reported
> with their progressive widening. From what I've seen it looks like
> plain UCT, without FPU or progressive widening, has more to gain from
> RAVE.
>
> Am I wrong to assume that the strongest version of Mogo before you
> introduced RAVE used something like FPU or progressive widening?

You are right, but the effect of terms which were before is by far
negligeable. It may definitely be possible that stronger use of
knowledge like the progressive widening make the effect of RAVE much
less interesting. It was not our case at that time. I am also not sure
that it is the main reason of failure for people who tried and report
a small improvement. Of course, there can be so many reasons that it
is difficult to find out without looking at the implementation in
details :/.

Best,
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Erik van der Werf]

Hi Hideki,

Your results look similar to those of Mogo as reported in their icml
paper. When you ran this experiment, did you use anything like FPU or
progressive widening, or did you use Levente's original design which
always selects unvisited moves first?

Regards,
Erik


On Wed, Feb 6, 2008 at 3:42 PM, Hideki Kato <[EMAIL PROTECTED]> wrote:
> I found some data.  GGMC Go v2r6, against GNU Go 3.7.10 level 10, 9x9,
>  komi 7.5, 3000 playouts/move, 2000 games match:
>
>  Without RAVE:   winning rate was 23.1 +- 0.9% (-209 +- 9 ELO)
>  With RAVE:  winning rate was 65.3 +- 1.1% (+110 +- 8 ELO)
>
>  Though this includes some other improvements, most come from RAVE.
>  Unlike MoGo, my best 'K' was 1000.
>
>  Following is my implementation of RAVE for GGMC v2r6.
>  1) Each playout returns the score and all moves with colors played.
>  2) While back-propagating the value (degitized score), computes the
>  mean and the variance according to UCB1 and do the same for RAVE
>  seperatelly.  For RAVE, the values of all (legal) moves, except played
>  one, in a node are updated.
>  3) In the computation of values for RAVE, the point is that there
>  appeares three colors (as someone, I remember GCP, mentioned before).
>  If the players' colors aren't the same then skip.  Count the value as
>  is or negate (1 - score, for me), depending on the color of the player
>  at the position and the color for the score.
>  4) Before back-propagating the value of each playout, I setup a color
>  table for all intersections of the board for speed-up, in fact
>  (initialized with EMPTY). That is, fill the board (table[move] =
>  color) by tracing the moves and the colors returned by the playout
>  forward (from leaf node to end of the game). Then, by tracing the
>  path from root to the leaf node, clear the table[move] (table[move] =
>  EMPTY), in order to avoid duplicate counting with UCB1.
>  5) While descending the tree, merge the values come from UCB1 and
>  RAVE with 'K' according to the formula in the paper.
>
>  #Though I'm writing this by reading my source code, this description
>  may include some errors.
>
>  Hope this helps,
>
> Hideki
>
>  Gian-Carlo Pascutto: <[EMAIL PROTECTED]>:
>
> >> I also implemented RAVE in Mango. There was a few points of improvements
>  >> (around 60 Elo points with gnugo as reference), but as much as in the
>  >> paper of Gelly and Silver :( (around 250 Elo points if I remember well)
>  >>
>  >> It might be that the effect of RAVE depends a lot on the simulation
>  >> strategy. Indeed, sometimes my RAVE was playing very good moves but also
>  >> very bad ones.
>  >
>  >I don't think the simulation strategy is the key.
>  >
>  >I suspect the improvement is largest when you don't do progressive widening.
>  >
>  >Nevertheless it would be quite interesting to see the implementation
>  >details of ggmc's RAVE. RAVE performance is quite dependent on exact
>  >implementation and parameters.
>  --
>
> [EMAIL PROTECTED] (Kato)
>  ___
>
>
> 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] cgosview on iPhone?

[Christoph Birk]

On Wed, 6 Feb 2008, Mark Boon wrote:
At the moment it's not possible to develop iPhone applications. An SDK comes 
out this months and we have to wait and see what it supports.


http://developer.apple.com/iphone/devcenter/

Christoph

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is Rémi correct?

[Weston Markham]

I know that other people have mentioned this sort of thing already,
but the result of level 8 being better than level 10 matches my own
experience with slightly older versions of gnugo.  As I recall, 8 was
the best, 9 a little worse, and 10 worse again.  Increasing the level
seems to improve play after that, but it dramatically increases the
time.

Weston

On Feb 6, 2008 12:48 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
> Here is an update from the new 1000 game test using gungo at level 8
> instead of 10.
>
> Rank Name   Elo+- games score oppo. draws
>1 Gnugo-3.7.11  1800   34   30  2186   97%  11370%
>2 Mogo_03   1507   48   56   186   16%  18000%
>3 Mogo_02   1202   43   51  10003%  18000%
>4 Mogo_01   1003   70   96  10001%  18000%
>
> The test, at this point, seems to indicate that gnugo at level 8 is
> stronger than at level 10 because mogo is not doing as well as in the
> previous test.It will be more meaningful when we get to levels close
> to gnugo's strength.
>
> - Don
>
>
> > As promised,  to answer Rémi, I did a study with mogo vs Gnu at various
> > levels.   There is NO self play involved, Gnugo-3.7.11 is the only
> > opponent for progressively higher rated version of Mogo.
> >
> > Here are the raw results so far:
> >
> > Rank Name   Elo+- games score oppo. draws
> >1 Mogo_10   2319   72   60   500   95%  18000%
> >2 Mogo_11   2284   94   74   259   94%  18000%
> >3 Mogo_09   2234   57   49   500   92%  18000%
> >4 Mogo_08   2124   43   39   500   87%  18000%
> >5 Mogo_07   2016   35   33   500   78%  18000%
> >6 Mogo_06   1961   32   30   500   72%  18000%
> >7 Mogo_05   1814   28   28   500   52%  18000%
> >8 Gnugo-3.7.11  1800   13   13  5259   44%  18230%
> >9 Mogo_04   1711   29   29   500   37%  18000%
> >   10 Mogo_03   1534   35   38   500   18%  18000%
> >   11 Mogo_02   1281   60   72   5005%  18000%
> >   12 Mogo_01   1004  115  178   5001%  18000%
> >
> >
> > The issue is whether self-play results distort the rating of programs.
> > In this case, we are only testing whether it distorts the ratings of
> > Mogo since no other programs were tested.
> >
> > In the following table,  I played up to 500 games between Gnugo and Mogo
> > at various levels.   The levels are the exact levels that correspond to
> > the big scalability study.  In the middle column I listed the
> > ratings as computed by bayeselo in games against  ONLY Gnugo and set the
> > default rating of Gnugo to 1800, just as in the study.
> >
> > Unfortunately,  I used level 10 in the gnugo only games but in the big
> > study we use level 8.   It's my understanding there is little difference
> > between these 2 but we can probably assume Mogo might be a little better
> > than indicated relative to the big scalability study.
> >
> > It looks like there indeed is a lot of distortion at the low end of the
> > scale.  Mogo seems much stronger at low levels than the larger
> > scalability study indicated.
> >
> > At the higher levels,  we also get a mismatch,  where Mogo's rating
> > doesn't seem as high when playing only Gnugo.   This is as Rémi
> > claims.
> >
> > One thing to note is that at higher levels it's more difficult to get an
> > accurate rating.  Mogo_10 is winning 95% of it's games against Gnugo,
> > and an extra win or loss every few games can make a lot of difference.
> > However I am inclined to believe this is real since it seems to hold for
> > several upper levels.   At level 7 it's only 42 ELO, but at levels
> > beyond this it's over 100 ELO.
> >
> > I've never doubted that there is some intransivity between programs, but
> > I am a little surprised that it is this much.  Even if the comparison is
> > slightly unfair due to Mogo playing a stronger version of Gnugo in this
> > study,  it's still seems like it must be at least 100 ELO.
> >
> >
> > vers  vs Gnu  Study
> >   --  -
> >   011004688
> >   021281   1093
> >   031534   1331
> >   041711   1554
> >   051814   1751
> >   061961   1971
> >   072016   2058
> >   082124   2270
> >   092234   2347
> >   102319   2470
> >
> >
> > My suggestion to improve this situation is to play a few thousands games
> > against a well rated Gnugo and set up mogo as a second anchor.
> >
> > - Don
> >
> >
> >
> > ___
> > 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/c

Re: [computer-go] cgosview on iPhone?

[terry mcintyre]

I googled up the screensize: 480x320 pixels, or the reverse, depending on the 
orientation of the screen.
 
Terry McIntyre <[EMAIL PROTECTED]> 
“Wherever is found what is called a paternal government, there is found state 
education. It has been discovered that the best way to insure implicit 
obedience is to commence tyranny in the nursery.”
 
Benjamin Disraeli, Speech in the House of Commons [June 15, 1874]

- Original Message 
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wednesday, February 6, 2008 12:31:46 PM
Subject: Re: [computer-go] cgosview on iPhone?



On Feb 6, 2008 3:21 PM, Don Dailey <[EMAIL PROTECTED]> wrote:

What is the screen size?


2x3.5 inches?  I'm unsure about the 2...



-Inline Attachment Follows-

___
computer-go 
mailing 
list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/







  

Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  
http://tools.search.yahoo.com/newsearch/category.php?category=shopping___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cgosview on iPhone?

[Jason House]

On Feb 6, 2008 3:39 PM, Don Dailey <[EMAIL PROTECTED]> wrote:

> I asked that question wrong -  what is the resolution of the screen?
> Does it scroll to simulate higher resolution?


Poking around online, I see 480x320.  The web browser allows a zoom/unzoom
and also scrolling...  Two nice ways to handle stuff that is too big to
view.  I don't know if that carries over to other stuff or not.  Some of the
menus allow you to scroll left and right in discrete chunks.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cgosview on iPhone?

[Don Dailey]

I'm a palm fan and palm is working on linux devices now. 

My face is turning purple from holding my breath.

- Don


Mark Boon wrote:
> At the moment it's not possible to develop iPhone applications. An SDK
> comes out this months and we have to wait and see what it supports.
>
> Mark
>
> On 6-feb-08, at 18:21, Don Dailey wrote:
>
>>
>>
>> Jason House wrote:
>>> Just curious if anyone knows if this is possible.  cgosView has a mac
>>> (universal) binary that I'd expect to be runnable.  I just don't know
>>> if the iPhone is restricted or has any other special requirements.  I
>>> believe it runs Mac OSXI may have an iPhone in my future and it'd be
>>> cool if I could put simple stuff like cgosview on it.  I know there's
>>> a mac (universal) binary, but I believe the iPhone has some
>>> restrictions.
>>>
>>> Are there any clever people out there who have already worked through
>>> this?  I don't actually have an iPhone (yet).
>>>
>> If  iPhone handles the standard tcl/tk we can make it work - unless
>> there are some limitations.   The binary is really a tcl/tk runtime with
>> a script attached to a single file and some libraries built in.
>>
>> What is the screen size?
>>
>> - Don
>>
>>> 
>>>
>>>
>>> ___
>>> 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] cgosview on iPhone?

[Mark Boon]

At the moment it's not possible to develop iPhone applications. An  
SDK comes out this months and we have to wait and see what it supports.


Mark

On 6-feb-08, at 18:21, Don Dailey wrote:




Jason House wrote:

Just curious if anyone knows if this is possible.  cgosView has a mac
(universal) binary that I'd expect to be runnable.  I just don't know
if the iPhone is restricted or has any other special requirements.  I
believe it runs Mac OSXI may have an iPhone in my future and it'd be
cool if I could put simple stuff like cgosview on it.  I know there's
a mac (universal) binary, but I believe the iPhone has some  
restrictions.


Are there any clever people out there who have already worked through
this?  I don't actually have an iPhone (yet).


If  iPhone handles the standard tcl/tk we can make it work - unless
there are some limitations.   The binary is really a tcl/tk runtime  
with

a script attached to a single file and some libraries built in.

What is the screen size?

- Don

- 
---


___
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] cgosview on iPhone?

[Don Dailey]

I asked that question wrong -  what is the resolution of the screen?   
Does it scroll to simulate higher resolution?

- Don


Jason House wrote:
>
> On Feb 6, 2008 3:21 PM, Don Dailey <[EMAIL PROTECTED]
> > wrote:
>
> What is the screen size?
>
>
> 2x3.5 inches?  I'm unsure about the 2...
> 
>
> ___
> 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] cgosview on iPhone?

[Jason House]

On Feb 6, 2008 3:21 PM, Don Dailey <[EMAIL PROTECTED]> wrote:

> What is the screen size?


2x3.5 inches?  I'm unsure about the 2...
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cgosview on iPhone?

[Don Dailey]

Jason House wrote:
> Just curious if anyone knows if this is possible.  cgosView has a mac
> (universal) binary that I'd expect to be runnable.  I just don't know
> if the iPhone is restricted or has any other special requirements.  I
> believe it runs Mac OSXI may have an iPhone in my future and it'd be
> cool if I could put simple stuff like cgosview on it.  I know there's
> a mac (universal) binary, but I believe the iPhone has some restrictions.
>
> Are there any clever people out there who have already worked through
> this?  I don't actually have an iPhone (yet).
>   
If  iPhone handles the standard tcl/tk we can make it work - unless
there are some limitations.   The binary is really a tcl/tk runtime with
a script attached to a single file and some libraries built in.

What is the screen size?   

- Don

> 
>
> ___
> 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] cgosview on iPhone?

[Jason House]

Just curious if anyone knows if this is possible.  cgosView has a mac
(universal) binary that I'd expect to be runnable.  I just don't know if the
iPhone is restricted or has any other special requirements.  I believe it
runs Mac OSXI may have an iPhone in my future and it'd be cool if I could
put simple stuff like cgosview on it.  I know there's a mac (universal)
binary, but I believe the iPhone has some restrictions.

Are there any clever people out there who have already worked through this?
I don't actually have an iPhone (yet).
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] bayelo ELO ratings

[Don Dailey]

If anyone is interested, I adapted the bayeselo program to GO.   
bayeselo can take pgn chess files and rate the players.   

The problem with bayeselo for go is:

1.  Rémi's program is interactive - not command line parameter driven.  
So it's not easy to use inside of scripts.

2.  It doesn't  understand SGF files - I think it was designed primarily
for chess.


What I did is wrap everything up into a script that tries to do the
right thing.   It's a tcl script and probably only works on linux
machines, but that would probably be easy to fix.

The script assumes you have Rémi's bayeselo program in your path.   It
will compute ELO ratings by pointing it to any directory that has sgf
files and it will read all the sgf files in the directory you point it
too.   You can cat many sgf files together and it will know what to do.  

With wrapper, everything is automated, but not as flexible as Rémi's
program.   It needs some work to make it more flexible such as the
ability to change some parameters via the command line or point to just
certain sgf files.Right now you must edit the top 10 lines or so to
change any key parameters (such as "prior") that you feel needs to be
changed.   

It probably has bugs, but it is working well for me.   If anyone wants a
copy, let me know.

It's very convenient to use with my autotester too.   You just dump the
SGF into a single big file and run the script.

If I get a burst of energy I may take the source code (subject to any
licensing issues) and fix it directly to do the basic thing as a command
line parameter driven utility. 

- Don

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is Rémi correct?

[Don Dailey]

Here is an update from the new 1000 game test using gungo at level 8
instead of 10.

Rank Name   Elo+- games score oppo. draws
   1 Gnugo-3.7.11  1800   34   30  2186   97%  11370%
   2 Mogo_03   1507   48   56   186   16%  18000%
   3 Mogo_02   1202   43   51  10003%  18000%
   4 Mogo_01   1003   70   96  10001%  18000%

The test, at this point, seems to indicate that gnugo at level 8 is
stronger than at level 10 because mogo is not doing as well as in the
previous test.It will be more meaningful when we get to levels close
to gnugo's strength.  

- Don

> As promised,  to answer Rémi, I did a study with mogo vs Gnu at various
> levels.   There is NO self play involved, Gnugo-3.7.11 is the only
> opponent for progressively higher rated version of Mogo.
>
> Here are the raw results so far:
>
> Rank Name   Elo+- games score oppo. draws
>1 Mogo_10   2319   72   60   500   95%  18000%
>2 Mogo_11   2284   94   74   259   94%  18000%
>3 Mogo_09   2234   57   49   500   92%  18000%
>4 Mogo_08   2124   43   39   500   87%  18000%
>5 Mogo_07   2016   35   33   500   78%  18000%
>6 Mogo_06   1961   32   30   500   72%  18000%
>7 Mogo_05   1814   28   28   500   52%  18000%
>8 Gnugo-3.7.11  1800   13   13  5259   44%  18230%
>9 Mogo_04   1711   29   29   500   37%  18000%
>   10 Mogo_03   1534   35   38   500   18%  18000%
>   11 Mogo_02   1281   60   72   5005%  18000%
>   12 Mogo_01   1004  115  178   5001%  18000%
>
>
> The issue is whether self-play results distort the rating of programs. 
> In this case, we are only testing whether it distorts the ratings of
> Mogo since no other programs were tested.
>
> In the following table,  I played up to 500 games between Gnugo and Mogo
> at various levels.   The levels are the exact levels that correspond to
> the big scalability study.  In the middle column I listed the
> ratings as computed by bayeselo in games against  ONLY Gnugo and set the
> default rating of Gnugo to 1800, just as in the study.
>
> Unfortunately,  I used level 10 in the gnugo only games but in the big
> study we use level 8.   It's my understanding there is little difference
> between these 2 but we can probably assume Mogo might be a little better
> than indicated relative to the big scalability study. 
>
> It looks like there indeed is a lot of distortion at the low end of the
> scale.  Mogo seems much stronger at low levels than the larger
> scalability study indicated. 
>
> At the higher levels,  we also get a mismatch,  where Mogo's rating
> doesn't seem as high when playing only Gnugo.   This is as Rémi
> claims.  
>
> One thing to note is that at higher levels it's more difficult to get an
> accurate rating.  Mogo_10 is winning 95% of it's games against Gnugo, 
> and an extra win or loss every few games can make a lot of difference.  
> However I am inclined to believe this is real since it seems to hold for
> several upper levels.   At level 7 it's only 42 ELO, but at levels
> beyond this it's over 100 ELO.  
>
> I've never doubted that there is some intransivity between programs, but
> I am a little surprised that it is this much.  Even if the comparison is
> slightly unfair due to Mogo playing a stronger version of Gnugo in this
> study,  it's still seems like it must be at least 100 ELO.
>
>
> vers  vs Gnu  Study
>   --  -
>   011004688
>   021281   1093
>   031534   1331
>   041711   1554
>   051814   1751
>   061961   1971
>   072016   2058
>   082124   2270
>   092234   2347
>   102319   2470
>
>
> My suggestion to improve this situation is to play a few thousands games
> against a well rated Gnugo and set up mogo as a second anchor.  
>
> - Don
>
>
>
> ___
> 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] More UCT / Monte-Carlo questions (Effect of rave)

[Hideki Kato]

Gian-Carlo Pascutto: <[EMAIL PROTECTED]>:
>Hideki Kato wrote:
>
>> 4) Before back-propagating the value of each playout, I setup a color 
>> table for all intersections of the board for speed-up, in fact 
>> (initialized with EMPTY). That is, fill the board (table[move] = 
>> color) by tracing the moves and the colors returned by the playout 
>> forward (from leaf node to end of the game). Then, by tracing the 
>> path from root to the leaf node, clear the table[move] (table[move] = 
>> EMPTY), in order to avoid duplicate counting with UCB1.
>
>I don't understand this. What and how would you be double counting?

I mean the values of such moves are updated in both UCB and RAVE.  
That is, the moves in the path are updated by UCB and all moves in 
the nodes in the path are updated by RAVE.  As UCB values and RAVE 
values will be averaged later, perhaps I thought not updating the 
values of such moves in RAVE would be _natural_.

As this code was written last Oct. and I've been working on other 
staffs, I'm not sure I remember the idea correctly.  But I believe 
this improved some.

-Hideki
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Jason House]

On Feb 6, 2008 11:39 AM, Gian-Carlo Pascutto <[EMAIL PROTECTED]> wrote:

> Hideki Kato wrote:
>
> > 4) Before back-propagating the value of each playout, I setup a color
> > table for all intersections of the board for speed-up, in fact
> > (initialized with EMPTY). That is, fill the board (table[move] =
> > color) by tracing the moves and the colors returned by the playout
> > forward (from leaf node to end of the game). Then, by tracing the
> > path from root to the leaf node, clear the table[move] (table[move] =
> > EMPTY), in order to avoid duplicate counting with UCB1.
>
> I don't understand this. What and how would you be double counting?


Let's a set of stones played in the playout get captured and then the void
gets filled again.  The key is to count only the first move at a set board
position.  If you don't, you can end up counting a particular move more than
once.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Gian-Carlo Pascutto]

Hideki Kato wrote:

4) Before back-propagating the value of each playout, I setup a color 
table for all intersections of the board for speed-up, in fact 
(initialized with EMPTY). That is, fill the board (table[move] = 
color) by tracing the moves and the colors returned by the playout 
forward (from leaf node to end of the game). Then, by tracing the 
path from root to the leaf node, clear the table[move] (table[move] = 
EMPTY), in order to avoid duplicate counting with UCB1.


I don't understand this. What and how would you be double counting?

--
GCP
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Erik van der Werf]

Hi Sylvain,

On Wed, Feb 6, 2008 at 4:41 PM, Sylvain Gelly <[EMAIL PROTECTED]> wrote:
>  Do you want to come? ;)

Well, I have a nice job, but one can always try to make me an offer I
can't refuse ;-)

> I just can't do too many things at the same  time.

Sounds familiar...

>  > Well, since you say the improvement is marginal on 9x9 then I think we
>  > are actually in agreement. I also get an improvement, but it's just
>  > not that much. When I wrote 'spectacular' I meant the reported jump
>  > from 25% to over 55% winrate against gnugo.
>
>  I am sorry, I was unclear. When I said marginal in 9x9, I was talking
>  of the differences between the current MoGo (well, at least when I
>  left it 6 months ago :)) and the algorithm described in the ICML
>  paper. The change is only on how to balance the two values you get
>  (UCT and Rave).
>  Rave in 9x9, as described in the paper, gives a big jump in
>  performance, and the numbers reported in the paper are accurate: those
>  are computed with many thousands games against gnugo and I carefully
>  did the experiments multiple times.
>  In addition, Hideki for example report the same order of improvements.
>  I have to point out that it is really easy to make a mistake in the
>  updates making Rave much less interesting. I am definitely not saying
>  that you or anyone else made a mistake, but it can just happen,
>  sometimes :).

In the ICML version of UCT without RAVE, you did not use your First
Play Urgency, right?

I think that using FPU has an effect similar to what others reported
with their progressive widening. From what I've seen it looks like
plain UCT, without FPU or progressive widening, has more to gain from
RAVE.

Am I wrong to assume that the strongest version of Mogo before you
introduced RAVE used something like FPU or progressive widening?

Best,
Erik
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Sylvain Gelly]

Hi Erik,

> Thanks for your reply! How do you like your new job? Do you miss CompGo? ;-)
I like it very much thanks. Do you want to come? ;). I miss computer
go and all of you, but I read the list (not all) time to time, so I
have some remembers :). I just can't do too many things at the same
time.

> Well, since you say the improvement is marginal on 9x9 then I think we
> are actually in agreement. I also get an improvement, but it's just
> not that much. When I wrote 'spectacular' I meant the reported jump
> from 25% to over 55% winrate against gnugo.

I am sorry, I was unclear. When I said marginal in 9x9, I was talking
of the differences between the current MoGo (well, at least when I
left it 6 months ago :)) and the algorithm described in the ICML
paper. The change is only on how to balance the two values you get
(UCT and Rave).
Rave in 9x9, as described in the paper, gives a big jump in
performance, and the numbers reported in the paper are accurate: those
are computed with many thousands games against gnugo and I carefully
did the experiments multiple times.
In addition, Hideki for example report the same order of improvements.
I have to point out that it is really easy to make a mistake in the
updates making Rave much less interesting. I am definitely not saying
that you or anyone else made a mistake, but it can just happen,
sometimes :).

> >  That could be an explanation, but there are two points:
> >  - the prior you put on top of Rave often avoid to first sample 1-1,
> >  and even when you do, you very often loose just 1 playout because of
> >  the UCT value you get right away.
>
> Yes, using more prior knowledge will probably reduce the problem.

You don't even need "more", already save atari, atari, hane and cut
gives you enough in many cases to avoid 1-1. Of course more good
knowledge is better :). My point is just that you don't need so much
to avoid to try first 1-1. And even without prior knowledge that is
not terrible. If you see at the numbers in the paper, adding this very
simple prior knowledge does not improve so much.


> >  - I never observed a big discrepancy between the number of Rave
> >  samples for each move.
>
> I guess this is because your playout policy is more uniform than mine?
> The problem tends to disappear with uniform random playouts.
> My program has some hard-reject patterns to discard moves that are
> strictly inferior to adjacent alternatives, so in some situations I
> can easily get a large difference between the number of Rave samples
> for each move.

It is definitely a sensible hypothesis.

Best,
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Hideki Kato]

I found some data.  GGMC Go v2r6, against GNU Go 3.7.10 level 10, 9x9, 
komi 7.5, 3000 playouts/move, 2000 games match:

Without RAVE:   winning rate was 23.1 +- 0.9% (-209 +- 9 ELO)
With RAVE:  winning rate was 65.3 +- 1.1% (+110 +- 8 ELO)

Though this includes some other improvements, most come from RAVE.  
Unlike MoGo, my best 'K' was 1000.

Following is my implementation of RAVE for GGMC v2r6.
1) Each playout returns the score and all moves with colors played.
2) While back-propagating the value (degitized score), computes the 
mean and the variance according to UCB1 and do the same for RAVE 
seperatelly.  For RAVE, the values of all (legal) moves, except played 
one, in a node are updated.
3) In the computation of values for RAVE, the point is that there 
appeares three colors (as someone, I remember GCP, mentioned before).  
If the players' colors aren't the same then skip.  Count the value as 
is or negate (1 - score, for me), depending on the color of the player 
at the position and the color for the score.
4) Before back-propagating the value of each playout, I setup a color 
table for all intersections of the board for speed-up, in fact 
(initialized with EMPTY). That is, fill the board (table[move] = 
color) by tracing the moves and the colors returned by the playout 
forward (from leaf node to end of the game). Then, by tracing the 
path from root to the leaf node, clear the table[move] (table[move] = 
EMPTY), in order to avoid duplicate counting with UCB1.
5) While descending the tree, merge the values come from UCB1 and 
RAVE with 'K' according to the formula in the paper.

#Though I'm writing this by reading my source code, this description 
may include some errors.

Hope this helps,
Hideki

Gian-Carlo Pascutto: <[EMAIL PROTECTED]>:
>> I also implemented RAVE in Mango. There was a few points of improvements
>> (around 60 Elo points with gnugo as reference), but as much as in the
>> paper of Gelly and Silver :( (around 250 Elo points if I remember well)
>>
>> It might be that the effect of RAVE depends a lot on the simulation
>> strategy. Indeed, sometimes my RAVE was playing very good moves but also
>> very bad ones.
>
>I don't think the simulation strategy is the key.
>
>I suspect the improvement is largest when you don't do progressive widening.
>
>Nevertheless it would be quite interesting to see the implementation
>details of ggmc's RAVE. RAVE performance is quite dependent on exact
>implementation and parameters.
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Erik van der Werf]

Hi Sylvain,

Thanks for your reply! How do you like your new job? Do you miss CompGo? ;-)


On Wed, Feb 6, 2008 at 2:20 PM, Sylvain Gelly <[EMAIL PROTECTED]> wrote:
>  > (1) They compared Rave to plain UCT. If they would have compared it to
>  > a more sophisticated implementation (like the best Mogo before Rave)
>  > they probably could not have shown a spectacular improvement.
>
>  The best Mogo before Rave was very close to plain UCT with the
>  sequence-like simulations. And indeed we exactly compared the best
>  Mogo before and after Rave. There is a table (I don't remember which
>  number), which show the incremental improvements from plain UCT, to
>  Rave, passing by plain UCT with sequence-like simulations. All
>  experiments have been done with MoGo's code, all other parts of the
>  code staying constant. There were not "secret part" of MoGo disabled
>  to make the improvement of Rave more interesting.
>
>  One discrepancy between our results and the one some of you observe,
>  as Gian-Carlo stated, is likely to come from the parameters and detail
>  of implementation. We heavily tuned those parameters and details
>  against gnugo, and that makes quite a big difference. I chatted more
>  closely with some of you about details and it did make a difference.
>  Maybe some of you can share what made a change, if you want.
>
>  Note as well that the current implementation of MoGo (not the one at
>  the time of the ICML paper) use a different tradeoff between UCT and
>  Rave value, thanks to an idea of David Silver, which brought
>  improvements in 19x19 (where the Rave values are the most useful),
>  while it was marginal (still better) in 9x9. But anyway we here are
>  talking about 9x9, so it can't explain what you are talking about.

Well, since you say the improvement is marginal on 9x9 then I think we
are actually in agreement. I also get an improvement, but it's just
not that much. When I wrote 'spectacular' I meant the reported jump
from 25% to over 55% winrate against gnugo. I only got such an
improvement when I first dumbed down my implementation to a plain UCT
without a good move-ordering (and always expanding all unvisited nodes
first).


>  > (2) () Depending on the playout
>
> > policy, adding an upper confidence bound to the rave values can push
>  > some terrible bad moves up (like playing on 1-1). The reason seems to
>  > be that such moves are normally sampled very infrequently (so the UCB
>  > will be higher), and when they are selected (...)
>
>  That could be an explanation, but there are two points:
>  - the prior you put on top of Rave often avoid to first sample 1-1,
>  and even when you do, you very often loose just 1 playout because of
>  the UCT value you get right away.

Yes, using more prior knowledge will probably reduce the problem.


>  - I never observed a big discrepancy between the number of Rave
>  samples for each move.

I guess this is because your playout policy is more uniform than mine?
The problem tends to disappear with uniform random playouts.
My program has some hard-reject patterns to discard moves that are
strictly inferior to adjacent alternatives, so in some situations I
can easily get a large difference between the number of Rave samples
for each move.

Best,
Erik
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Sylvain Gelly]

Hi Erik,

> (1) They compared Rave to plain UCT. If they would have compared it to
> a more sophisticated implementation (like the best Mogo before Rave)
> they probably could not have shown a spectacular improvement.

The best Mogo before Rave was very close to plain UCT with the
sequence-like simulations. And indeed we exactly compared the best
Mogo before and after Rave. There is a table (I don't remember which
number), which show the incremental improvements from plain UCT, to
Rave, passing by plain UCT with sequence-like simulations. All
experiments have been done with MoGo's code, all other parts of the
code staying constant. There were not "secret part" of MoGo disabled
to make the improvement of Rave more interesting.

One discrepancy between our results and the one some of you observe,
as Gian-Carlo stated, is likely to come from the parameters and detail
of implementation. We heavily tuned those parameters and details
against gnugo, and that makes quite a big difference. I chatted more
closely with some of you about details and it did make a difference.
Maybe some of you can share what made a change, if you want.

Note as well that the current implementation of MoGo (not the one at
the time of the ICML paper) use a different tradeoff between UCT and
Rave value, thanks to an idea of David Silver, which brought
improvements in 19x19 (where the Rave values are the most useful),
while it was marginal (still better) in 9x9. But anyway we here are
talking about 9x9, so it can't explain what you are talking about.

> (2) () Depending on the playout
> policy, adding an upper confidence bound to the rave values can push
> some terrible bad moves up (like playing on 1-1). The reason seems to
> be that such moves are normally sampled very infrequently (so the UCB
> will be higher), and when they are selected (...)

That could be an explanation, but there are two points:
- the prior you put on top of Rave often avoid to first sample 1-1,
and even when you do, you very often loose just 1 playout because of
the UCT value you get right away.
- I never observed a big discrepancy between the number of Rave
samples for each move.

Best,
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Erik van der Werf]

Hi Guillaume,

I think we talked about this before, but others may be interested as
well. In my opinion the ICML paper on Rave has several weaknesses.
It's been a while since I read the paper, but here are some I
remember:

(1) They compared Rave to plain UCT. If they would have compared it to
a more sophisticated implementation (like the best Mogo before Rave)
they probably could not have shown a spectacular improvement.

(2) The paper suggest that you should add an upper confidence bound to
the rave values. Although they didn't actually make this explicit,
because IIRC the paper failed to provide an actual value for the
constant c, I guess most people naturally assume it to be positive.
However, Rave is already a greedy heuristic, so if anything you should
probably subtract the confidence bound. Depending on the playout
policy, adding an upper confidence bound to the rave values can push
some terrible bad moves up (like playing on 1-1). The reason seems to
be that such moves are normally sampled very infrequently (so the UCB
will be higher), and when they are selected (e.g. for a big capture
deep in the playout) they correlate more with winning (so the value
will also be higher) without generalizing to earlier positions.

Best,
Erik



On Wed, Feb 6, 2008 at 10:47 AM, Chaslot G (MICC)
<[EMAIL PROTECTED]> wrote:
> I also implemented RAVE in Mango. There was a few points of improvements 
> (around 60 Elo points with gnugo as reference), but as much as in the paper 
> of Gelly and Silver :( (around 250 Elo points if I remember well)
>
>  It might be that the effect of RAVE depends a lot on the simulation 
> strategy. Indeed, sometimes my RAVE was playing very good moves but also very 
> bad ones.
>
>  Guillaume
>
>  -Original Message-
>  From: [EMAIL PROTECTED] on behalf of Magnus Persson
>  Sent: Wed 06/02/2008 00:42
>  To: computer-go@computer-go.org
>  Subject: Re: [computer-go] More UCT / Monte-Carlo questions
>
>  Quoting Gunnar Farnebäck <[EMAIL PROTECTED]>:
>
>  > I have never managed to implement RAVE successfully. It made my
>  > program significantly slower but no stronger even at a fixed number of
>  > simulations.
>
>  I get a small effect from RAVE, My rationalisation is that if the
>  program is rich with other features to improve performance RAVE may
>  not add that much.
>
>  -Magnus
>
>
>  ___
>  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] More UCT / Monte-Carlo questions (Effect of rave)

[Hideki Kato]

You are right.  I don't do progressive widening.

-Hideki

Gian-Carlo Pascutto: <[EMAIL PROTECTED]>:
>> I also implemented RAVE in Mango. There was a few points of improvements
>> (around 60 Elo points with gnugo as reference), but as much as in the
>> paper of Gelly and Silver :( (around 250 Elo points if I remember well)
>>
>> It might be that the effect of RAVE depends a lot on the simulation
>> strategy. Indeed, sometimes my RAVE was playing very good moves but also
>> very bad ones.
>
>I don't think the simulation strategy is the key.
>
>I suspect the improvement is largest when you don't do progressive widening.
>
>Nevertheless it would be quite interesting to see the implementation
>details of ggmc's RAVE. RAVE performance is quite dependent on exact
>implementation and parameters.
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

RE: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Gian-Carlo Pascutto]

> I also implemented RAVE in Mango. There was a few points of improvements
> (around 60 Elo points with gnugo as reference), but as much as in the
> paper of Gelly and Silver :( (around 250 Elo points if I remember well)
>
> It might be that the effect of RAVE depends a lot on the simulation
> strategy. Indeed, sometimes my RAVE was playing very good moves but also
> very bad ones.

I don't think the simulation strategy is the key.

I suspect the improvement is largest when you don't do progressive widening.

Nevertheless it would be quite interesting to see the implementation
details of ggmc's RAVE. RAVE performance is quite dependent on exact
implementation and parameters.

-- 
GCP
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

RE: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)

[Chaslot G (MICC)]

I also implemented RAVE in Mango. There was a few points of improvements 
(around 60 Elo points with gnugo as reference), but as much as in the paper of 
Gelly and Silver :( (around 250 Elo points if I remember well)

It might be that the effect of RAVE depends a lot on the simulation strategy. 
Indeed, sometimes my RAVE was playing very good moves but also very bad ones.

Guillaume

-Original Message-
From: [EMAIL PROTECTED] on behalf of Magnus Persson
Sent: Wed 06/02/2008 00:42
To: computer-go@computer-go.org
Subject: Re: [computer-go] More UCT / Monte-Carlo questions
 
Quoting Gunnar Farnebäck <[EMAIL PROTECTED]>:

> I have never managed to implement RAVE successfully. It made my
> program significantly slower but no stronger even at a fixed number of
> simulations.

I get a small effect from RAVE, My rationalisation is that if the  
program is rich with other features to improve performance RAVE may  
not add that much.

-Magnus


___
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/