Re: [computer-go] Re: computer-go Digest, Vol 43, Issue 8

[Petr Baudis]

On Mon, Feb 18, 2008 at 09:03:17PM +0100, Alain Baeckeroot wrote:
> Le lundi 18 février 2008, Michael Williams a écrit :
> > But as was pointed out before, these high levels of MoGo are probably still 
> > not pro level, right?
> > 
> 
> On 9x9 Big_slow_Mogo is near pro level, maybe more.
> 6 monthes ago or so it was able to regurlarly beat pro without komi on 9x9.

But no komi on 9x9 is quite a handicap.

It would be quite interesting to see how well the high level Mogos fare
against high dans unhandicapped.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [EMAIL PROTECTED]: Re: [computer-go] Should 9x9 komi be 8.0 ?]

[Petr Baudis]

On Thu, Feb 28, 2008 at 01:01:08PM -0500, Don Dailey wrote:
> It's naive to think some simplistic deception imposed upon the program
> is going to correct the error when you don't even know if the program is
> erring in the first place. How can you say,  "the program thinks it
> is losing, but it MUST be in error and I'm going to change the komi so
> that it will 'play better'?"You must have some basis for knowing the
> program is in error before you can lower it's goal.  

I think there is a misunderstanding here, this was (I suppose) never to
correct error in program's perception of the board. (From watching MoGo
and such, it often overestimates its board position, but rarely
underestimates it. :-)

The point here is to prevent the program from playing the "MC-hamete"
moves that in most cases have no hope of working, but instead still aim
at a close game and wait for some opponent's yose mistake. This closely
matches human approach to the game as well - if you are confident in
yose and see you are only little behind, you frequently don't start
overplaying hopelessly, but instead still play the best you can and hope
for an overturn in yose.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Should 9x9 komi be 8.0 ?]

[Petr Baudis]

On Mon, Mar 03, 2008 at 11:01:52AM -0800, Christoph Birk wrote:
> On Sun, 2 Mar 2008, Don Dailey wrote:
>> My feeling is that in lost positions,  the only thing we are trying to
>> accomplish is to make the moves more cosmetically appealing (normal) and
>> at best improve the programs chances of winning against weak players.
>> After all, if the program is in bad shape,   then to be completely
>> realistic it's probably going to lose to the player that put it in this
>> bad shape.
>
> I think you are wrong here.
> If there are two lines of play from the viewpoint of the MC program:
>  a) leads to a 0.5 pt loss
>  b) may win if the opponent makes a stupid (!) mistake, but otherwise
> leads to a bigger loss.
>
> It is generally better to play for the 0.5 point loss as the oppoenent
> may make a end-game mistake and loses 1 point.
> But naive MC programs typically go for (b) which will lead to a
> devastating loss because the opponent usually does not make the 10 point
> mistake, but may have made the 1 point mistake.

I think there is one other important area of "virtual komi" usage that
has been neglected here - handicap games. Make your UCT bot play
with/against 6 handicaps, I think you are likely to see quite some early
second-line moves etc. With/against 9 handicap, you will see first-line
moves too! At least I see that with CzechBot MoGo instance. These are
obviously slow and/or nonsensical, and are created by I think the high
noise when all the winrates are within top/bottom 10%.

  When playing against high handicap, the bot still can win a lot
because of its raw fighting power. But against stronger opponents, it
seems to me that it has a lot of trouble to properly handle its handicap
stones and will play some very slow moves that step by step throw away
the advantage gained by handicap stones. (Sorry, I have no raw numbers
here, though it should be possible to gather them from the KGS web.)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])

[Petr Baudis]

On Tue, Mar 04, 2008 at 12:01:02PM -0500, steve uurtamo wrote:
> cool.  do you have any examples from a 19x19 game?  that's what
> i was referring to when i said that i've never seen an MC player
> play out a ko fight.

MoGo can indeed play out some rather spectacular ko fights;
unfortunately, I couldn't find any quickly, so here is at least an
example of a shorter one. Unfortunately, the 5d it is playing a
six-stones game against plays a non-working threat in the end and loses.

The ko fight starts at move 158.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe


pasky-8.sgf
Description: application/go-sgf
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])

[Petr Baudis]

On Wed, Mar 05, 2008 at 08:02:10PM +, Matthew Woodcraft wrote:
> Petr Baudis wrote:
> > MoGo can indeed play out some rather spectacular ko fights;
> > unfortunately, I couldn't find any quickly, so here is at least an
> > example of a shorter one.
> 
> I see you made the following comment in that game record, which seems
> relevant to recent discussions here.
> 
> | mogo excels at reducing clear winning positions to close games they
> | lose because of botched up tsumego
> 
> Is it mogo botching up the tsumego or its opponents? Do you have any
> example game records for this?

MoGo, typically because of nakade. Note that it was kind of
tongue-in-cheek comment since I can't really prove that MoGo would win
any particular game if it did see the nakade, but here is an example
where it wasted several dying-in-gote moves in a corner throughout the
game.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe


pasky-10.sgf
Description: application/go-sgf
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])

[Petr Baudis]

On Thu, Mar 06, 2008 at 12:55:53PM +, Jacques Basaldúa wrote:
> A 4-6 kyu human is behind by 10-15 points in the midgame (at that stage the
> probability of winning is correlated with territory, so the MC bot is
> building fine.) He creates a 12-16 point worth nakade trick in a corner
> and does not solve it.The bot is happy, it thinks a bulk five is alive or
> something like that. Perhaps the human sacrificed another 15 points
> somewhere to create the trick so he should be dead lost. But, he only
> has to play on, reduce, etc. As the endgame approaches, the MC bot
> allows the reduction only until the territorial balance would change the
> winner. The player is happy, he turned a 25 points loss into a 1.5 point
> loss (assumed by the program) and has a 12 point surprise.
> At the end, when the whole board is decided, the player kills
> the bot's group and the bot turns a sure win into a sure loss and resigns.

I honestly don't think at all that these "tricks" are created by the
opponents meaningfully, in 90% of the cases I think they arise from
perfectly natural corner situations; the nakade weakness is not that
well known, I believe.

> Because the trick can only be played by similar strength players (much
> weaker players can't build something like that, much stronger don't need 
> it)
> it affects the rating of the bots. I guess CrazyStone could be near KGS 
> 1dan
> with that solved. It is 2k now. But, of course, the solution may not come 
> at
> the price of making the program weaker. That is the difficult part.

(Note that I believe CrazyStone played way too few games to have a
precise rank. I think it could still be 3k and it could still be 1d as
it is now, if it played more games. CzechBot has played thousands of
games now I think, and its rank is _still_ evolving, though I don't
think it will reach 2k.)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: komi argument = silly

[Petr Baudis]

On Thu, Mar 06, 2008 at 04:33:16PM -0800, Dave Dyer wrote:
> 
> To a first order approximation, would changing the komi change the
> rankings?  Presumably, programs are playing the same number of games
> as black and white, so any "unfair" advantage or disadvantage black 
> has would balance out.
> 
> Komi only matters when there is only one game between a pair of opponents.

This has nothing to do with black/white distinction. The idea is to
dynamically adjust the komi to make UCT to aim at higher and potentially
less sure win or lower and potentially more sure loss. Of course,
depending on whether it takes black or white you would adjust the komi
in the correct direction.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: komi argument = silly

[Petr Baudis]

On Fri, Mar 07, 2008 at 08:04:37AM -0500, Thomas Wolf wrote:
> I assume that when you change komi dynamically, all that was learned
> by MC so far under the different komi value is useless/wrong.

But what are actually your reuse rates? With the standard UCB1 formula,
I find reusing branches from earlier trees give relatively insignificant
number of extra playouts, at least with p=0.2 (I find that using lower p
values leads to very deep UCT trees, but the choice of moves being read
out is _very_ noisy). Maybe this is much better with RAVE or such?

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: komi argument = silly

[Petr Baudis]

On Fri, Mar 07, 2008 at 12:43:42PM -0500, Don Dailey wrote:
> I honestly think there are better ways to handle this, if you must,
> other than changing the goal to a losing goal. At least give the
> computer the right goal (winning) and adjust from there.  
> 
> If I were trying to solve this "problem",   the solution I would look at
> first  would be to pre-process the moves in advance of the search,   and
> just impose a very slight bias on the root move list. The idea is
> that all other things being equal,  it will play a patterned or "normal"
> move instead of a random move when the game is virtually over.  
> 
> If you do it right,  you can probably make it play more like like it has
> an ego without making it weaker.

Was making it play "nicer" moves anyone's goal here, actually? I always
wanted to make it stronger by dynamic komi, not just to make it play
moves that look nicer to humans.

Of course, there is still the argument whether dynamic komi would help
this goal against human players, and I have nothing new to bring into
that discussion. But the bots playing ugly moves is not a big issue for
anyone, I believe; also the stronger the UCT bots get, the less silly
looking moves they seem to play even when the game is over.

-- 
Petr "Pasky the one who increased his bot's
strength probably by several hundred
ELO today by fixing few simple bugs" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Making playouts heavier

[Petr Baudis]

  Hi,

  I'm wondering about how to best make my Monte Carlo playouts within
UCT heavier and which pieces of domain knowledge to better use to bias
the tree and which ones to apply during the playouts, so I would like to
ask about previous experiences.

  Currently, I do three basic hints that I check the previous move and
its immediate neighbors against when deciding on next move:

  (i) If the last move or any of its neighbors is in atari, play the
last liberty (either captures or escapes; do not try to escape if
it does not add any liberties).

  (ii) If the last move or any of its neighbors can be ataried, play
one of the atari-ing moves (either makes atari or prevents it; again
there is extra check so that the prevention isn't itself self-atari,
it turns out that a bot that always fills one eye of surrounded
two-eyed group is not very strong).

  (iii) If the last move creates cut shape, cut with 50% probability.

  (iv) There was also hint to make a random move in direct vincinity of
the last move, but it seemed to just generate a lot of horrible shapes.


  My main question is about the rules (i) and (ii) (I'm not sure about
(ii) actually), other bots seem to do that as well - I wonder, do you
_always_ make the move hinted by these rules during the playout, or only
with some probability? For example, the RR MoGo paper says that
"it looks for the moves capturing stones on the Go board, plays one if
there is any" - does it really _always_ capture a group in atari
anywhere on the board before considering a random move?

  Also, do you use the (i), (ii) rules in the tree search in any way?
What about the ladder checking - do you do it in the tree search, or
during the playouts?

  Thanks a lot,

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Automated genetic parameters tuning

[Petr Baudis]

  Hi,

  does anyone know of any pre-made open framework using genetic
algorithms that one could use to tune various parameters of a bot? I
have about 6 independent parameters for my bot so far that I would like
to find best values for (from domain-specific knowledge hint rates to p
parameter of the UCB1 formula), and I would hate to do redundant work
implementing such a framework on my own.

  Thank you,

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] CGOS client

[Petr Baudis]

  Hi,

  is there source code available for the binary CGOS client, please? I'm
using the 32bit linux version on four computers, with two sets of
users, and on the computers using the same set I often hit a conflict,
with one of the computers offline with:

10:15:43S->C protocol
10:15:43C->S e1 cgosGtp 0.98 alpha - engine client for CGOS Linux-x86 by 
Don Dailey
10:15:43S->C username
10:15:43C->S pachi1-p0.2-light
10:15:43S->C Error: You are already logged on!  Closing connection.
10:15:43Connection to server has closed.  Will try to reconnect shortly.

The trouble is that it does not try different username but keeps
trying with the original one.

  (By the way, pachi1-*-light are UCT bots with completely light
playouts with various UCB1 c values, if anyone wants to use that as
reference. Surprisingly, it seems that my heavy playouts do not make big
difference so far, though the rating is still very unstable.)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CGOS client

[Petr Baudis]

On Sat, Mar 08, 2008 at 09:03:47AM -0500, Don Dailey wrote:
> 
> 
> Moi de Quoi wrote:
> > On Sat, 2008-03-08 at 07:41 -0500, Don Dailey wrote:
> >
> >   
> >> But the problem you are seeing is a bug in the server.   I am restarting
> >> the server which will be a temporary cure.  It seems there are
> >> situations where a program loses it's connection or logs off and the
> >> server still thinks it is logged on.   I think I can fix this without
> >> too much trouble - I will put this on my todo list.
> >> 
> >
> > NNGS handles this situation by: "you are already logged in; kicking the
> > *other* copy out."
> > Which of course must be done *after* verifying the password ;-)
> >   
> 
> That's probably the easiest fix - thanks for the idea.

But that will make my problem even worse, right? If I start another
instance of the bot set on another computer and one of the users is
playing a game, there is a chance it will get kicked off by the newly
connected bot, AIUI.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CGOS client

[Petr Baudis]

On Sat, Mar 08, 2008 at 04:56:16PM +0100, Moi de Quoi wrote:
> Well, it depends on the server's policy, whether you are allowed to be
> logged in more than once under the same name. (I can see no good reason
> to allow it, but it's Don's server...)

I do not want to be logged in more than once, I would like the client to
try logging in as another user when it hits this error; that seems as
the most sensible behaviour to me.

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: endgame (Was [computer-go] Re: Should 9x9 komi be 8.0 ?])

[Petr Baudis]

On Mon, Mar 10, 2008 at 02:33:03AM -0400, Michael Williams wrote:
> Jonas Kahn wrote:
>> out, kos can go on for long. I don't know what depth is attained in the
>> tree (by the way, I would really like to know), but I doubt it is that
>
> MoGo displays the depth of the principle variation in the stderr stream.

I have been wondering, does that include _any_ nodes, or only these
above certain number of playouts?  What is the playout threshold?

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

  Hi,

On Sat, Mar 08, 2008 at 10:18:34AM +0100, Petr Baudis wrote:
>   (By the way, pachi1-*-light are UCT bots with completely light
> playouts with various UCB1 c values, if anyone wants to use that as
> reference. Surprisingly, it seems that my heavy playouts do not make big
> difference so far, though the rating is still very unstable.)

  after two days of play, it seems the ratings are fairly settled now.
For clarity, here is the UCB1 formula I use:

UCB1 = X_i + sqrt(log(N) * c / n)

Specifically, the c is withing the sqrt(); some of the papers put it in
front of the sqrt.

  Also, I expand UCT leaves at the second hit. This retains conservative
memory usage but it is important for strength - I saw huge strength
increase when I lowered this to 2 from the original value of 5.

  With 110k playouts per move and no domain knowledge in the playouts,
the ratings are now:

c=0.2  (pachi1-p0.2-light)  ELO 1627 (285 games)
c=1.0  (pachi1-p1.0-light)  ELO 1590 (120 games)
c=0.05 (pachi1-p0.05-light) ELO 1531 (286 games)
c=2.0  (pachi1-p2.0-light)  ELO 1511 (118 games)

  The main two messages of this post are: If you are developing own UCT
bot, with this number of playouts you should be aiming at least at 1600
ELO on CGOS. And choosing the right c can easily make a 100 ELO
difference! In particular, the "default" UCB1 c=2.0 appears to be very
unsuitable choice.

  I'm pretty sure my code is fairly well debugged now, but of course
there may be still bugs lurking; when I have put my bots on CGOS for the
first time it was awfully bug-ridden (and about 800 ELO worse ;-). What
ELO rating did pure UCT bots get historically with how many playouts?


P.S.: Looks like the heavy playouts I described in my other mail bring
no improvement to the bot strength at all, and mostly make it few ELO
weaker. :-( I'm rethinking my approaches now.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Mon, Mar 10, 2008 at 03:40:53PM -0700, Christoph Birk wrote:
> On Mon, 10 Mar 2008, Petr Baudis wrote:
>>  With 110k playouts per move and no domain knowledge in the playouts,
>> the ratings are now:
>>
>>  c=0.2  (pachi1-p0.2-light)  ELO 1627 (285 games)
>>  c=1.0  (pachi1-p1.0-light)  ELO 1590 (120 games)
>>  c=0.05 (pachi1-p0.05-light) ELO 1531 (286 games)
>>  c=2.0  (pachi1-p2.0-light)  ELO 1511 (118 games)
>
> I have two "light" UCT bots on CGOS:
> Name  #playouts c (*) CGOS-ELO
> myCtest-V-00035 0.25  1508
> myCtest-10k-UCT   1 0.25  1246
>
> (*): I use c=0.5 outside the sqrt()
>
> What is your 'create-new-node' threshold? I use 50.

I actually added that to my mail at the last minute: "Also, I expand UCT
leaves at the second hit. This retains conservative memory usage but it
is important for strength - I saw huge strength increase when I lowered
this to 2 from the original value of 5."

Even with just threshold 2, for 110k playouts I need only about 20M of
memory for the tree, so I'm actually wondering about how to improve my
program by spending more memory usefully. ;-)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Mon, Mar 10, 2008 at 06:57:07PM -0400, Don Dailey wrote:
> I think you may still have a bug.  You should get well over 1700 with
> 110,000 playouts, even if they are light playouts.  

Hmmm... That is going to be some tough debugging I suspect.

> >   I'm pretty sure my code is fairly well debugged now, but of course
> > there may be still bugs lurking; when I have put my bots on CGOS for the
> > first time it was awfully bug-ridden (and about 800 ELO worse ;-). What
> > ELO rating did pure UCT bots get historically with how many playouts?
> >   
> FatMan does 20k playouts and has heavy play-outs, very similar to the
> first paper where mogo described it's play-out strategy - basically
> playing a random out of atari move or a local move that fits one of
> their patterns.   It is rated 1800 on CGOS.The tree expansion policy
> for nodes is based on the parent count,   not the child itself.So
> once the parent has 100 play-outs children are expanded regardless of
> the number of games they have seen.(Near the end of the game in 9x9
> go some moves could be tried a few times before being expanded.) 

Oh, interesting! I must have misread libEGO code which seems to use
similar thresholds.

What is the justification of using the parent playout count instead of
the node playout count itself?

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

  Hi,

On Mon, Mar 10, 2008 at 08:07:14PM -0400, Don Dailey wrote:
> > What is the justification of using the parent playout count instead of
> > the node playout count itself?
> >
> >   
> I don't know if it makes much difference how this is done, and I don't
> know how everybody else is doing it.  I allocate all the children at
> once and do not have to store pointers to each child,  just one pointer
> to the first child and a counter so that I know how many children there
> are.   On average I'm probably expanding every other time in the middle
> of the game. 

I really so far use just a completely unoptimized

struct tree_node {
/*
 *+--+
 *| node |
 *+--+
 *  / <- parent
 * +--+   v- sibling +--+
 * | node |  | node |
 * +--+  +--+
 *| <- children  |
 * +--+   +--+   +--+   +--+
 * | node | - | node |   | node | - | node |
 * +--+   +--+   +--+   +--+
 */
struct tree_node *parent, *sibling, *children;

coord_t coord;
int playouts; // # of playouts coming through this node
int wins; // # of wins coming through this node
float value; // wins/playouts
};

even with no memory pools, every node allocated separately. This is one
of the things I'm likely to optimize when I get to that again, but so
far my feeling is that I'm fast and small enough not to really bother.
;-) And I can be sure that there are no bugs at least in this part of
the code.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Mon, Mar 10, 2008 at 05:36:14PM -0700, Christoph Birk wrote:
> On Mon, 10 Mar 2008, Christoph Birk wrote:
>> On Tue, 11 Mar 2008, Petr Baudis wrote:
>>> On Mon, Mar 10, 2008 at 06:57:07PM -0400, Don Dailey wrote:
>>>> I think you may still have a bug.  You should get well over 1700 with
>>>> 110,000 playouts, even if they are light playouts.
>>
>> I will run myCtest with 110k-playout, c=0.25 and node creation
>> after the 2nd visit ... let's see what its ELO rating will be
>> in a couple of days.
>
> Sorry, I just realized I cannot do 110k playouts because my
> implementation is too slow.
> I suggest you run a 'pachi-0.25-light-50k' that just uses
> 5 playouts. That way you can compare it to 'myCtest-V-0003'.

Sure, it now won its first game as pachi1-p0.25-li50k. It will be
interesting how much difference number of playouts makes for me too.

> BTW: I count the new-node threshold like Don from the parent
>  node, so 50 not far from your '2'.

Hmm, I really wonder where this comes from, the idea seems quite
unnatural to me.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Mon, Mar 10, 2008 at 10:04:18PM -0400, Don Dailey wrote:
> Your method is to allocate 1 node when it's been visited once or twice -
> very natural I agree.   My method is to allocate all the children at
> once, and wait until the parent has been visited some number of times
> (currently 100).   If there are 50 legal moves, that gives on average
> about 1 node allocation every 2 visits, which is what you said you do.  

I _expand_ 1 node when it's been visited twice, not allocate.

To clarify further:

...
if (tree_leaf_node(n)) {
if (n->playouts >= u->expand_p /* 2 */)
tree_expand_node(t, n, &b2);
/* Just now occured to me that I should probably
 * descend to one of the children now yet. */

result = play_random_game(&b2, stone_other(color), u->gamelen);
break;
}
...

void
tree_expand_node(struct tree *t, struct tree_node *node, struct board *b)
{
tree_add_child(node, tree_init_node(pass));
for (int i = 1; i < t->board->size; i++)
for (int j = 1; j < t->board->size; j++)
if (board_atxy(b, i, j) == S_NONE)
tree_add_child(node, tree_init_node(coord(i, 
j)));
}

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Tue, Mar 11, 2008 at 11:41:41AM -0700, Christoph Birk wrote:
> On Tue, 11 Mar 2008, Don Dailey wrote:
>> I am going to keep the 25k playouts running and add a 10k play-out
>> version of UCT. I want to establish a standard testing size so that
>
> Great! That way Jason can also participate.
>
> myCtest-10k-UCT has a long-term rating of about 1250.
> For the 50k version I have just started a test series that experiments
> with various thresholds before creating a new node.

My engine is now playing as pachi1-p0.25-li10k and pachi1-p0.25-li50k.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Thu, Mar 13, 2008 at 09:19:58AM -0400, Don Dailey wrote:
> 
> > If it is agreed,  I will start a 25k test.My prediction is that this
> > will finish around 1600 ELO on CGOS.   
> >   
> Looks like it's currently around 1485,  so I am 115 ELO off from my
> prediction at the moment.
> 
> 2 more doublings would probably get you to 1700 -  perhaps I will test
> this later,  I think I can handle 100,000 nodes without a problem timing
> out.  If it's too much I think I can solve it by playing quickly
> when the score is extreme - and it will have little impact on the strength.

I stop playouts when the best candidate has probability >= 0.95 and has
seen at least 500 playouts; this seems also much friendlier to humans
when playing on KGS. Watching many games, I didn't see any fluke about
this when raising the bar to 500 playouts (it was 100 playouts before
and I have seen one or two), then again my bot has lower ELO on CGOS
than it should for its number of playouts, so... ;-)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Thu, Mar 13, 2008 at 09:19:58AM -0400, Don Dailey wrote:
> If you look at the table,  drdGeneric 10k is rated 1228 and 25k is
> rating 1485 which is 257 ELO for doing 2.5 x more play-outs.  If
> this holds, I would expect 100,000 play-outs to give well over 1700
> ELO. Of course there could be a lot of error in each of these
> ratings so it's difficult to predict just from these 2 points.

I got kind of lost in the thread and lost track about which bots should
I actually compare myself to. ;-)

So I have created this page:

http://senseis.xmp.net/?CGOSBasicUCTBots

and summed up what I could find in the thread about the various bots.
Please clarify if anything there is wrong / unknown, and add your bots
if they aren't there. I wanted to add Fluke too, but I do not know which
of the many incarnations should I choose. :-)

Curiously, while pachi1 with 10k playouts is 30 ELO weaker than
drdGeneric-10k and myCtest-10k-UCT (it seems like ~1230 is _the_ rating
for 10k UCT), with 50k playouts it is 60 ELO stronger than
myCtest-V-0003 - is that one really just UCT with 50k playouts?

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Thu, Mar 13, 2008 at 11:25:04AM -0700, Christoph Birk wrote:
> On Thu, 13 Mar 2008, Petr Baudis wrote:
>> So I have created this page:
>>
>>  http://senseis.xmp.net/?CGOSBasicUCTBots
>>
>> and summed up what I could find in the thread about the various bots.
>> Please clarify if anything there is wrong / unknown, and add your bots
>> if they aren't there. I wanted to add Fluke too, but I do not know which
>> of the many incarnations should I choose. :-)
>
> I am not sure if we have an understanding of node expansion. myCtest
> does not really the parent node ... let me explain what I am doing:
>
> During decending (root at the top) the UCT tree:
>  if current-node is a leaf
>if number of visits is at least MIN_VISITS then
>  determine all legal moves and create children nodes
>  choose a random child and descend
>endif
>run a random playout and propagate score upwards
>  else
>calculate UCT score = win-ratio + C * sqrt(log(n)/m)
>decend to "best" child
>  endif

Oh - then you are doing exactly what I do! I have suspected that there
indeed is a misunderstanding here. :-)

Does anyone actually do something different than the above, or is the
whole "count parent playouts / count node playouts" difference just a
misunderstanding?

>> Curiously, while pachi1 with 10k playouts is 30 ELO weaker than
>> drdGeneric-10k and myCtest-10k-UCT (it seems like ~1230 is _the_ rating
>> for 10k UCT), with 50k playouts it is 60 ELO stronger than
>> myCtest-V-0003 - is that one really just UCT with 50k playouts?

> myCtest-V-0020 | 1459 | 50k  | 0.5  | 50 in node   |
> myCtest-V-0021 | 1483 | 50k  | 0.5  | 25 in node   |
> myCtest-V-0022 | 1467 | 50k  | 0.5  | 10 in node   |
> myCtest-V-0023 | 1523 | 50k  | 0.5  | 5 in node|
> myCtest-V-0024 | ?| 50k  | 0.5  | 2 in node|

I have added these bots to the table.

> My explanation is that with fewer playouts the reduced noise with
> a larger MIN_VISITS is better, while with more playouts the
> deeper search-tree with a smaller MIN_VISITS improves play.

I thought so too. I will try pachi with 10k playouts and MIN_VISITS 50.
Maybe I don't have many bugs in this part of code after all. ;-)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Thu, Mar 13, 2008 at 08:01:57PM +0100, Heikki Levanto wrote:
> On Thu, Mar 13, 2008 at 06:31:19PM +0100, Petr Baudis wrote:
> > I got kind of lost in the thread and lost track about which bots should
> > I actually compare myself to. ;-)
> > 
> > So I have created this page:
> > 
> > http://senseis.xmp.net/?CGOSBasicUCTBots
> > 
> 
> Good idea!
> 
> Would it make sense to have a similar page for pure MC programs (without
> uct), so that we beginning developers could check that portion of our code
> against known results?

I think so - I would have quite appreciated that when my bot was pure
MC, to weed out my board implementation bugs.

I have linked the page to [UCT] and [CGOS] articles.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGo/professional challenge

[Petr Baudis]

  Hi,

On Fri, Mar 21, 2008 at 10:14:49AM +, Nick Wedd wrote:
> Saturday:
> 3/23/08 3:00 PM
> Game I (9x9)
> Game II 9x9
> Game III 9x9
> Played with 1.5 hours from the start of one round to the next

  will this be with komi 7.5?

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGo/professional challenge

[Petr Baudis]

On Fri, Mar 21, 2008 at 05:07:01PM +0100, Olivier Teytaud wrote:
>>  will this be with komi 7.5?
>
> Yes. Previous records against Guo Juan, as far
> as I know:
> - 1/3 wins with komi 7.5
> - 9/14 wins with komi 0.5 (mogo black,
>  i.e. komi in favor of mogo)

What computing power did have that MoGo at its disposal?

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGo/professional challenge

[Petr Baudis]

On Fri, Mar 21, 2008 at 08:35:25PM +0100, Olivier Teytaud wrote:
>> What computing power did have that MoGo at its disposal?
>
> 4 cores, 2.4 GHz.

Thank you! That also puts the strength of CzechBot into some
perspective.  :-)

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Optimal explore rates for plain UCT

[Petr Baudis]

On Thu, Mar 13, 2008 at 06:31:19PM +0100, Petr Baudis wrote:
> On Thu, Mar 13, 2008 at 09:19:58AM -0400, Don Dailey wrote:
> > If you look at the table,  drdGeneric 10k is rated 1228 and 25k is
> > rating 1485 which is 257 ELO for doing 2.5 x more play-outs.  If
> > this holds, I would expect 100,000 play-outs to give well over 1700
> > ELO. Of course there could be a lot of error in each of these
> > ratings so it's difficult to predict just from these 2 points.
> 
> I got kind of lost in the thread and lost track about which bots should
> I actually compare myself to. ;-)
> 
> So I have created this page:
> 
>   http://senseis.xmp.net/?CGOSBasicUCTBots
> 
> and summed up what I could find in the thread about the various bots.
> Please clarify if anything there is wrong / unknown, and add your bots
> if they aren't there. I wanted to add Fluke too, but I do not know which
> of the many incarnations should I choose. :-)
> 
> Curiously, while pachi1 with 10k playouts is 30 ELO weaker than
> drdGeneric-10k and myCtest-10k-UCT (it seems like ~1230 is _the_ rating
> for 10k UCT), with 50k playouts it is 60 ELO stronger than
> myCtest-V-0003 - is that one really just UCT with 50k playouts?

Please note that pachi1 had a rather embarassing bug of starting the
random playouts with wrong color (so if the last tree node was black,
the playout would start with black as well). pachi2 has this bug fixed;
the ELO rating is still not settled, but so far it seems that the impact
of this has been about 20-30 ELO in the 110k playouts area, which seems
surprisingly little to me.

(-moggy is playout policy that so far comprises merely of capturing or
escaping of random stone in atari, with some ladder reading; I'm happy
that I managed to get as high as 1750 with just this addition! I'm not
sure how much strength the ladder reading actually adds, it did not seem
that much of an improvement (relatively to the time spent debugging it)
from playing it; I will test that later.)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Ing Challenge

[Petr Baudis]

On Wed, Mar 26, 2008 at 08:50:28PM -0700, David Fotland wrote:
> > You are right.
> 
> Well, I did compete for this prize about 15 times, so I hope so :)

Are there any current prized computer tournaments or does anyone know
about Ing foundation or anyone else planning to resume the challenge?
What was the reason that it got interrupted, lack of fast enough
progress or simple reallocation of funds within the foundation?

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] State of the art of pattern matching

[Petr Baudis]

On Thu, Mar 27, 2008 at 12:14:06PM -0700, terry mcintyre wrote:
> Suppose a group can be defended - four liberties in a
> row, for example. If the opponent plays inside those
> four liberties, you play to divide the area into two
> eyes - unless the situation is such that the group has
> a second eye elsewhere. Game records won't show such
> frivolous plays, but it is essential to know how to
> respond to programs which do make such plays. 

Such plays that "almost work" are often played as ko threats. I'm not
sure if you get enough samples of these patterns though; and the
opponent might tenuki from the play often to connect the ko, I'm not
sure if that helps you either.

I think this is one reason why people seem to often include some sample
of lower-level games during pattern learning.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] State of the art of pattern matching

[Petr Baudis]

On Mon, Mar 31, 2008 at 03:12:39PM -0700, Christoph Birk wrote:
>
> On Mar 31, 2008, at 1:05 PM, Don Dailey wrote:
>>
>>
>> Christoph Birk wrote:
>>>
>>> On Mar 31, 2008, at 10:48 AM, Mark Boon wrote:
 I don't know about this. I'm pretty sure MoGo checks if the stone can
 make at least two liberties (ladder problem) in which case it can
 still be horrible but very seldomly worse than random.
>>>
>>> I would expect playing a "not-working" ladder to be worse than random
>>> most
>>> of the time.
>> Of course this is true, but presumably a move that answers a direct
>> atari threat would classify as being better than random.
>
> Not if it's a working ladder.

I think this is not obvious, since there is still about 50% chance on
who gets the second move there. The original MoGo pattern describes only
capture-possibility check, not atari-possibility check, so even if you
play out the ladder, the opponent will most likely tenuki. So I think
not playing out working ladders as white is actually better because it
saves _black_ from getting a bad result!

I implemented a naive ladder check (that does not catch a lot of cases,
especially when you have to decide whether to "slide" the stones in
ladder along border or some of your friendly stones) and tested its
efficiency in UCT-driven playouts with only a 50% probability
capture-possibility check heuristic.

Against GNUGo Level8, I get 37% +-5.7% wins with ladder check, 28%
+-4.6% without ladder check. Unfortunately, the numbers are not very
precise and the difference is probably much smaller in reality - 37%
seems overinflated given later measurements; I will redo the test with
newer codebase and more games.

(I plan to post detailed measurements of effects of various heuristics
and parameters anyway; so far it seems my code is still too buggy
though: AMAF, prior knowledge and FPU all make my program weaker :-(.)

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Paper for AAAI

[Petr Baudis]

  Hello,

On Sun, Apr 06, 2008 at 08:55:26PM -0600, David Silver wrote:
> Here is a draft of the paper, any feedback would be very welcome :-)
>
> http://www.cs.ualberta.ca/~silver/research/publications/files/MoGoNectar.pdf

  you are saying that in minimax, opponent moves are selected by
minimizing the lower confidence bound - this seems novel, is that so? I
always got the impression that for the opponent moves, you reverse the
mean value but still use UCB.

  Is the FPU heuristics not mentioned in the paper only for space
reasons, or did it prove not to be so useful in practice in the end?

  I see three unclear details about the RAVE algorithm: Are only nodes
in the tree considered for the inclusion, or also moves in the following
random playout? And one of the sentences hints that there is a separate
period of playouts purely seeding the RAVE value before the UCT-RAVE
linear combination takes over - is that so? And it does not follow from
the paper that that the UCB formula is used for the RAVE value as well,
while the ICML paper states that.

  I am surprised on the bad effect of the grandfather heuristic and the
good effect of the even game heuristic. I assume that the effect of the
heuristics should accumulate when several of them are combined in the
prior value?

  The paper looks very nice otherwise.

  By the way, has anyone measured how big influence different weight of
playouts has on the various heuristics? For example, I'm still
struggling to get any improvement from RAVE whatsoever myself, but I
don't know if it is because I'm getting it wrong or whether it might
manifest only when making the playouts stronger (I randomly use only
three hardcoded patterns in the playouts).

  Thanks,

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Paper for AAAI

[Petr Baudis]

On Mon, Apr 07, 2008 at 08:36:25AM -0400, Jason House wrote:
> On Apr 7, 2008, at 8:22 AM, Petr Baudis <[EMAIL PROTECTED]> wrote:
>
>>  Hello,
>>
>> On Sun, Apr 06, 2008 at 08:55:26PM -0600, David Silver wrote:
>>> Here is a draft of the paper, any feedback would be very welcome :-)
>>>
>>> http://www.cs.ualberta.ca/~silver/research/publications/files/MoGoNectar.pdf
>>
>>  you are saying that in minimax, opponent moves are selected by
>> minimizing the lower confidence bound - this seems novel, is that so? I
>> always got the impression that for the opponent moves, you reverse the
>> mean value but still use UCB.
>
> I think both methods are equivalent. The UCB for one player is 1-LCB for 
> the other player...

Hmm, you are right, but this can get rather hairy considering things
like FPU; perhaps the formulation is simply unnecessarily confusing.

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CG'2008 paper: Whole-History Ratings

[Petr Baudis]

On Wed, Apr 09, 2008 at 03:40:28PM -0700, Christoph Birk wrote:
> On Wed, 9 Apr 2008, Matthew Woodcraft wrote:
>> It might be that most of those games aren't visible to the rating
>> system.
>
> That might explain why a rating system may have a hard time
> to follow.
> Bad data in ... bad data out :-)

But the point is that bad data is what you have in the real life. :-)

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Black/White winning rates with random playout?

[Petr Baudis]

On Sun, Jan 11, 2009 at 01:24:32PM +, Nick Wedd wrote:
> I suggest that instead of getting your neural players to play Go, you get 
> them to play a very slightly different game, in which, when both players 
> pass in turn, all stones remaining on the board are deemed alive.  It is 
> not difficult to write a scoring algorithm for this game.

Or you can rephrase this to say that your neural players should play Go
using the Tromp-Taylor ruleset. Scoring is pretty much trivial to
implement in these rules, and they approximate the traditional chinese
counting relatively well - all my bots always played on KGS using just
the Tromp-Taylor counting and discrepances are rare.

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

Re: [computer-go] Re: Hardware limits

[Petr Baudis]

On Sat, Jan 10, 2009 at 02:21:17PM +0100, Gian-Carlo Pascutto wrote:
> Mark Boon wrote:
> > So it seems arbitrary to put limitations on the hardware. However, if
> > two programs are essentially the same, but one side manages to bring
> > a more powerful computer than the other, is it fair to award one
> > program a prize and not the other?
> 
> If the programmer has done the needed work to make use of that,
> obviously he deserves to be rewarded for that.

However, how do you account for the other way, which seems far more
likely to me, that a team has better program but not enough resources
to buy high-end hardware to run it on, therefore losing anyway? The
concern being, not only the quality of the program is rewarded, but also
the amount of resources available to the team, which seems unfair to me
if the goal of the competition would be to choose the best program.

This scenario seems to me far more likely than the other way around, but
I am not familiar with the actual practice and scenarios of Chess and Go
tournaments.

Maybe what should be qualified is really what kind of competitions are
we talking about, and name them appropriately. Is it a _Go program_
competition? Or _Go-playing computer_ competition? I think in the former
case it would make most sense to just run all the programs on the same
hardware provided by the organizers. In the latter case, you do not have
to worry about any restrictions on hardware at all.

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

Re: [computer-go] How to "properly" implement RAVE?

[Petr Baudis]

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?

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

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

-- 
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] GPGPU

[Petr Baudis]

  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] Fuego performance

[Petr Baudis]

  Hi!

  Just FYI, someone might find interesting that latest SVN of Fuego
still does not seem to be on par with Mogo public release 1 (not that it
would claim to be - I was just curious where do they stand against each
other).

  I ran 86 19x19 games with both on the same hardware (single core of
A64 X2 6000+, 2G RAM) with 20 minutes S.D. each, the rate is MoGo win
83.3% (+-4.1).

  Kind regards,

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

Re: [computer-go] Fuego performance

[Petr Baudis]

On Mon, Feb 16, 2009 at 10:27:51AM +0900, Yamato wrote:
> >  I ran 86 19x19 games with both on the same hardware (single core of
> >A64 X2 6000+, 2G RAM) with 20 minutes S.D. each, the rate is MoGo win
> >83.3% (+-4.1).
> 
> How did you set the time to 20 minutes S.D.?  MoGo doesn't update the
> clock if you don't send time_left, and Fuego does.

Oops, good point. I used just:

../gogui-1.1.4/bin/gogui-twogtp -black './mogo' -white './fuego'
-auto -size 19 -komi 7.5 -alternate -games 100 -sgffile "mogo-vs-fuego"
-verbose -time 20

But apparently MoGo doesn't honor the time settings completely this way.
I will rerun it with --totalTime 1200.

Thanks,

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

Re: [computer-go] April KGS bot tournament: results

[Petr Baudis]

  Hi!

On Mon, Apr 06, 2009 at 03:52:14PM +0100, Nick Wedd wrote:
> The results of yesterday's KGS bot tournament are now available at
> http://www.weddslist.com/kgs/past/46/index.html
>
> As usual, I expect there are mistakes, and I will welcome corrections.
>
> Congratulations to the winner, CzechBot!

  I'm sorry, I forgot to update the CzechBot hardware information;
currently it again plays on my (almost all the time fairly idle) desktop
computer, thus double-core AMD Athlon(tm) 64 X2 Dual Core Processor
4800+ (2.5GHz).

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] MoGo - ManyFaces

[Petr Baudis]

  Hi!

  Today there was a short discussion about the strongest bot currently
online on KGS and I got curious whether ManyFaces or CzechBot (bleeding
edge MoGo) is stronger, so I made it play against ManyFaces.

  CzechBot is running as dual-thread pondering MoGo on slightly loaded
dual-core Athlon64 4800+ with 4G RAM, so perhaps slightly better hardware
than ManyFaces; it was reading slightly above 3kpps. Since CzechBot is
ranked one stone lower than ManyFaces, all the games were played josen:
with ManyFaces white taking no komi. The time was 30:00 SD. The ruleset
was Japanese and CzechBot was assuming Chinese rules, but in practice it
never mattered.

  13 games were played and the total score was 8-5 for CzechBot. I wonder
how would they play if on even grounds. The general game pattern was the
usual wild middlegame wrestling typical of MC, with CzechBot usually
getting large edge initially (70% winning probability and seemingly
unshakeable position), but then in the lost games making a careless
blunder or two when it got too much ahead, and panicking subsequently.
Overlooking ladders seemed to happen to it several times.

  This is just a FYI if anyone is interested in the relative strength or
would find the games interesting.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGo - ManyFaces

[Petr Baudis]

  Hi!

>   Today there was a short discussion about the strongest bot currently
> online on KGS and I got curious whether ManyFaces or CzechBot (bleeding
> edge MoGo) is stronger, so I made it play against ManyFaces.
> 
>   CzechBot is running as dual-thread pondering MoGo on slightly loaded
> dual-core Athlon64 4800+ with 4G RAM, so perhaps slightly better hardware
> than ManyFaces

  Turns out that ManyFaces is running on a quad-core, so the hardware
difference is bigger than I thought and in favor of ManyFaces.

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] representing liberties

[Petr Baudis]

On Sat, Aug 15, 2009 at 08:33:31AM -0400, Jason House wrote:
> On Aug 15, 2009, at 8:22 AM, Don Dailey  wrote:
> 
> >
> >
> >2009/8/15 Jason House 
> >On Aug 14, 2009, at 11:02 PM, "David Fotland"  >games.com> wrote:
> >
> >>Moves often merge two groups.
> >>
> >>I count liberties incrementally as I make moves, so no need to
> >>search to count.
> >>
> >
> >How do you detect shared libreties to avoid double counting.
> >Simple addition does not work for real liberties (and I think
> >you've said previously that you track real liberties.
> >
> >I don't know how David does it or if there are special tricks,
> >but you get real updates without that much extra work - you just
> >have to look at a few points around the newly placed stone.
> >
> 
> 
> It's not that simple. Shared liberties can occur far away with
> longer changes. I've come up with a scheme that looks a few points
> around, but only works for chains up to about seven stones. Consider
> two parallel, linear chains of 5 stones each, separated by a space.
> A stone placed at one end to connect them is likely miss the more
> distant shared liberties.
> 
> X
> +
> X
> 
> It's also possible to construct more complicated cases (with non-
> linear chains) where there are no locally shared liberties, but some
> exist further away.

Isn't it easier to use the gnugo way, keeping just up to 4 or 5
liberties listed explicitly? This covers many common cases and makes you
do hard work _only_ in case the chain has many liberties and one of the
explicitly listed ones disappears. All else including merging or
1,2-liberty patterns is trivial.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Interesting endgame case

[Petr Baudis]

On Sat, Aug 15, 2009 at 09:13:02AM -0600, Brian Sheppard wrote:
> >assuming komi 7.5 and Chinese rule, playing at J3 white will win. After J3,
> >white has 35. It only needs to win the ko or takes two dames. If black
> fills
> >the dame, it loses the ko. If it fills the ko, white can take two dames.
>  
>  
> Yes, Chinese and 7.5.
>  
> I basically figured that J3 was just another in a long series of stupid
> moves by Pebbles, but when it insisted that J3 was winning no matter how
> long it searched then I decided to look into it.
>  
> J3 looks stupid because it fills territory that O already owns.
>  
> J3 wins because it is "reverse sente" (I think this is the right
> terminology) because H4 is no longer sente for X. It also gains a
> move in the semeai against X's dead stones on the left, so O gains *two* ko
> threats.
>  
> Just curious: how did you find J3?
>  
>  
> >>  1 2 3 4 5 6 7 8 9
> >> A - - O - - - - - -
> >> B X X X O X - - - -
> >> C O O X O X X - - -
> >> D O - O X X - X X -
> >> E - O O O X X O X X
> >> F - X O - X O O O X
> >> G - X O - X O O - O
> >> H O X O - X X O O -
> >> J - - - O X - X O -
> >> O to play

I don't see how J3 works, black still can win the ko, can't he?

J3 - H4 - G4 - F4 - J6
now they play the ko:
H9 - J9 - J5 black takes
A4 - A5 - J6 white takes
F1 - J2 - J5 black takes
A2 - A1 - J6 white takes
E1 - G1 - J5 black takes
and white has no threats.

I admit I didn't see F1 immediately and went at E1 right away, maybe
that's the hard part for the bots?

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Exact dates for Chou vs Bots ?

[Petr Baudis]

On Thu, Aug 20, 2009 at 10:47:12AM +0200, "Ingo Althöfer" wrote:
> Does someone here know the exact starting times (in "common"
> time zones) for the 19x19 exhibition games
> 
> * Chou(9p) vs MFoG (Fr, August 21)
> * Chou(9p) vs Zen  (Sa, August 22)
> ?

Hi!

Where were these announced? On what server will they be played?

Thanks,

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] CUDA implementation of the per-intersection GPGPU approach

[Petr Baudis]

  I have written a quick CUDA implementation of the per-intersection
GPGPU apprach; Christian's e-mail finally made me polish it up to
a somewhat presentable form.

  In this implementation, each GPU thread maintains a single
intersection.

  The implementation uses 9x9 board (10x11 internally); expanding to
19x19 would probably mean either moving some data to global memory
or splitting the playout of single board to multiple blocks or waiting
for GPUs with larger shared memory. ;-)

  The speed is unfortunately very disappointing; on GTX260, I see
17,300 playouts per second, with 50 playouts running in parallel.
There are several "but"s:

  - With some further obvious optimizations, I'm thinking it should be
possible to get it to at least 22,000 playouts per second easily.

  - Bit boards are an obvious thing to try, but I'm quite doubtful
they will be an improvement

  - The playouts are uniformly random now, but they have been
implemented in a way to make heavier playouts easy; precise liberty
count is maintained and it should be easy to add pattern matching;
the move selection can deal with arbitrary probabilities for
different intersections (I wonder, what are the standard
high-performance numbers for heavier playouts with pattern matching?)

  - Christian is playing 2650 games in parallel; I'm playing only 50
games in parallel, in the meantime the CPU can pick next games to
play from the tree

  - My code already accounts for transferring board images from CPU to
the GPU (different one for each playout) and getting scores back

  - Christian's GPU seems quite better than mine

  - Apparently I still suck at CUDA optimizations; this has been my
first real small CUDA project, it would be awesome if someone more
experienced could look at the code and suggest obvious improvements

  Still, I'm pretty unhappy with the slowness; I wonder how Christian
achieved such a high speed. One problem with my approach is that I have
to make use of a lot of atomic instrinsics (some of them could be worked
around) and __syncthreads() all the time to ensure that all threads have
consistent board image at each stage.

  I think with pattern matching, the per-intersection approach could
shine more, since I can easily match patterns everywhere on the board
at once. Still, I wonder if it will become at least on par with good
CPU implementations.

On Wed, Sep 09, 2009 at 04:54:23PM +0100, Christian Nentwich wrote:
> In other words: no tree search is involved, and this is the lightest
> possible playout. The raw numbers are as follows:
>  - CPU Search: 47,000 playouts per CPU core per second, on an Intel
> 6600 Core-2 Duo
>  - GPU Search: 170,000 playouts per second, on an NVidia Geforce 285 card

  I still find this quite astonishing; since you consider this
experiment a failure anyway, would you mind publishing the source code?
:-)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
// CUDA implementation of random go player
// (c) Petr Baudis   2009
// MIT-style licence; please credit me if you make use of this
// thanks to ibd for some nice ideas


// This code tries to make use of the extra-high parallelism by giving
// each board intersection a single thread; all the __device__ functions
// are run in parallel for each intersection.

// nvcc -arch sm_13 -o board_move board_move.cu

// Still, many random playouts are played in parallel on the GPU as well.
// Each one is played independently and can have a different starting
// position. Good value on my GTX 260 is 50. Careful, if you specify this
// too high, the computation will get _extremely_ slow.

// So you'd call this like: ./board_move 42 10 50


// FIXME: No ko detection
/* Actually, I don't think ko detection is so important; it will mud down
   playouts somewhat, but eventually all the moves to be made except one
   ko fight are made anyway and MAX_MOVES catches the last ko. */

#include 
#include 
#include 
#include 

#define RS 9
#define S (RS + 1) // line with delimiter from neighbors
#define S2 (S*(S+1)+1) // square with border on top, left, bottom (plus an 
extra for S_EDGE SW of SWest S_NONE)
#define MAX_MOVES (RS * RS * 2)

struct board {
#define S_NONE 0
#define S_BLACK 1
#define S_WHITE 2
#define S_EDGE 3
int stone[S2];

/* >0: coordinate of "group center"
 * 0: no stone there
 * -1: eye forbidden for black to play
 * -2: eye forbidden for white to play
 * -3: eye forbidden for both to play */
int group[S2];
int libs[S2];

float p[S2]; /* probability of play; sum = 1 */

int random;
int free_spots[2]; /* free spots # for black and white */
int to_play;
int moves;
int komi; /*

Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach

[Petr Baudis]

  Hi!

On Thu, Sep 10, 2009 at 12:26:06PM +0100, Christian Nentwich wrote:
> I strongly suspect the low performance in the per-intersection case
> is down to two reasons - please let me know what you think:
>  - A big proportion of moves place one stone on an empty
> intersection. In this case 80 of your 81 threads are asleep doing
> nothing. This means GPU time is wasted.

  This is mostly true, though only through part of the loop body; I
think this is the biggest reason my approach is slower than your,
though, and it will be much worse on 19x19.

  It would be interesting to have N threads running independently and
getting contracted to various boards for massive tasks like capturing
and merging groups. But that would be quite complex task, not sure if
even practical to consider with the current state of the CUDA sandbox.

>  - In quite a few other cases, we get to the old problem with Go:
> that the intersections are not independent. Thus when you process
> captures or merges, you possibly have to lock 80 of 81 threads.

  I do no locking, actually being able to do large captures and merges
very quickly was always my primary motivation in even entertaining this
way of parallelism.

  However, I do a lot of atomicAdd()s which have quite an overhead and
in some cases basically just serialize many threads.  Mainly:

  (i) When counting score. This is totally unoptimized and in O(N) now;
should be trivial to rewrite this as parallel summing in O(logN). This
is one of the easy optimizations I mentioned, in fact the most obvious
one.

  (ii) When recalculating liberties. All intersection threads adding
extra liberty to the same group will get serialized. Avoiding this
seems difficult.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach

[Petr Baudis]

On Thu, Sep 10, 2009 at 01:54:49PM +0200, Magnus Persson wrote:
> This is very interesting. Here is a crazy idea, maybe it the same as
> Marks but I want to take it to its extreme.
> 
> Since AMAF values are so helpful, perhaps one can let go of the idea
> of sequential play following the rules of go, and basically play
> moves in parallel on all empty intersection. Compute new state (do
> captures) and repeat a fixed number of times and evaluate.
> 
> Since I do not understand GPU programming at all I cannot judge
> whether this would make things easier to implement.
> 
> Also a lot of weird thing will happens when you do things in
> parallel. What happens when two adjacent blocks are captured at the
> same time. Are both removed? Are there tricks to remove the one that
> was most likely to captured to begin with.

Well, after one iteration, _all_ blocks should be captured since there
will be no empty intersections, right? (Even if you don't play in
eye-like spaces, you will have this situation until some of these
actually form.)

The easiest heuristic would seem to be to capture the smallest group,
but I have hard time imagining this working well, _and_ how to choose
the smallest group efficiently (other than that, modifying my source to
do this should be fairly easy).

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach

[Petr Baudis]

On Thu, Sep 10, 2009 at 08:29:31AM -0400, Jason House wrote:
> I've thought of something similar in the past, but with a twist:
> pre-compute a subset of moves that could be safely played in
> parallel. Even if you can only play 285 moves in parallel on an
> empty 19x19, it could still be a huge speed boost.

Hmm, do you have some ideas how this pre-computation could be done in
less than O(N)?

I'm gonna think about this now during some travelling... ;-)

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach

[Petr Baudis]

On Thu, Sep 10, 2009 at 09:18:40AM -0400, Jason House wrote:
> Somewhat... One could generate a random number (r) and combine it
> with the move mask (m) as follows:
> black moves = m & r
> white moves = m & ~r
> 
> This has the drawback that the number of black and white moves may
> not be equal. It can be modified to give an equal number of moves
> such as requiring that each subset of n intersections generates the
> same number of black and white moves, or doing some kind of looping
> until the condition is met.
> 
> For looping, you could keep some subset of the generated moves in
> order to guarantee convergence. For example, if there are 14 more
> white moves than black moves, keep all generated moves except for 14
> white moves. Then you only have to pick 14 moves in the next loop
> iteration.

As a quick test mainly to test the speedup, I have made a simple hack
that takes every other intersection (creating an X-pattern) and
assigns it a randomized value (S_NONE,S_BLACK,S_WHITE). No check
on number of stones is made.

Now it thinks black has 46% win probability on empty board with no komi,
for a speedup of 1000 playouts/s. So the speedup seems totally
disappointing, and the bottleneck is in fact in the latter phases of the
game (merging groups and capturing). Hmm, something to dig into.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA and GPU Performance

[Petr Baudis]

On Sun, Sep 13, 2009 at 01:02:40AM +0200, Vincent Diepeveen wrote:
> 
> On Sep 10, 2009, at 12:55 AM, Michael Williams wrote:
> 
> >Very interesting stuff.  One glimmer of hope is that the memory
> >situations should improve over time since memory grows but Go
> >boards stay the same size.
> >
> 
> Well you first have to figure out how fast or slow shifting is on
> the nvidia's before actually going for it :)

Just read the nVidia docs. Shifting has the same cost as addition.

P.S.: The PTX assembler is also documented. Or have you meant some
secret undocumented instruction goodies?

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA and GPU Performance

[Petr Baudis]

On Sun, Sep 13, 2009 at 10:48:12AM +0200, Vincent Diepeveen wrote:
> 
> On Sep 13, 2009, at 10:19 AM, Petr Baudis wrote:
> >Just read the nVidia docs. Shifting has the same cost as addition.
> >
> 
> Document number and url?

http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf

> >P.S.: The PTX assembler is also documented. Or have you meant some
> >secret undocumented instruction goodies?

http://www.nvidia.com/object/io_1213955209837.html

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] rave and patterns

[Petr Baudis]

On Tue, Sep 15, 2009 at 08:49:15AM -0700, David Fotland wrote:
> Simple playouts with no eye fills and mogo 3x3 patterns and basic uct beat
> Gnugo 40% (at version 120)
..snip..
> All win rates are on 9x9 vs gnugo 3.7.20 level 10 with 5000 playouts.  After
> this I switched to testing 19x19, and stopped tuning for 9x9.  

Wow, are you sure there's no mistake in this? It is enough to have only
_5000 playouts_ in basic uct (do you use any priors?), playouts using
mogo 3x3 patterns (hane, cut1, cut2 and the four side patterns?) to beat
gnugo _level 10_?

I'm getting 10% at most with just 5k playouts, and I'm finding this
performance rather hard to believe... but maybe I'm suffering some
very bad bug that distorted my perception since the very beginning.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] rave and patterns

[Petr Baudis]

On Sun, Sep 20, 2009 at 10:06:01PM -0700, David Fotland wrote:
> Depends on what you mean by basic UCT.  I think I had no UCT priors then,
> just a 1.1 or 1.2 K.  The playouts included no self atari, no eye filling,
> no retake ko, and some simple rules for saving group adjacent to last move
> if it was in atari.  I don't have time to dig up the old source so I'm just
> going by my test notes.

Ah, thanks for all the details! I'm sure they will be very useful for
all the future bot writers too, to know what to expect. Just last question,
what is "1.1 or 1.2 K"?

I'm personally getting around 30% success rate only with 50k playouts
(and RAVE makes no difference for me, still)... I guess I have some
grave bug to hunt.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] rave and patterns

[Petr Baudis]

On Mon, Sep 21, 2009 at 08:18:37AM -0700, David Fotland wrote:
> In the original Mogo paper it's the initial value for the children, rather
> than try every child once.

Ah, you mean the First Play Urgency! Thanks, I will try that.

Anyway, I'm happier; after fixing many bugs and improving my playouts
just slightly more, with RAVE, I'm getting around 50% performance against
GNUGo even with only 5k playouts.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] AMAF collection experience

[Petr Baudis]

  Hi!

  Pachi has two RAVE/AMAF modes - in one, it counts as RAVE wins only
moves made by the player further down in the tree. In the other, it also
counts in the moves made in the playout phase.

  I think most people collect AMAF statistics only from the tree phase,
at least that's what I've been told.

  In the past, the "playout AMAF" mode was not performing good at all
for me either.  However, recently I have added 3x3 Mogo-like patterns
and now I have made some major tactical improvements to the playout
engine (and it still doesn't even implement that much, e.g. no 2-liberty
tactical moves are made yet, only atari/3x3 pattern handling).

  Now, with 400-800 games of 5k playouts against GNUGo --level 10,
I get a jump from 60% to 80% in winrate if I enable AMAF statistics
from playout phase.

  One crucial thing that has cost me a lot of time to find is _not_ to
count nakade moves from the playout phase into the AMAF statistics -
just totally ignore nakade moves and take the first owner for AMAF on
that intersection.  Nakade apparently adds a lot of noise and largely
annihilates the effect.  Properly handling nakade AMAF during the tree
phase is slightly (74+-1.9% vs 78.2+-1.7%) beneficial.


  So my guess is, if your playouts are heavy enough in the right way,
this can be a good bonus. On the other hand, by observing play on KGS,
the bot does not seem to be that much stronger, so maybe this has much
larger effect with 5k playouts than in slower games - I need to measure
the difference for higher playout counts as well.

  (Note that I also use my playout policy to seed the tree with prior
values (6 wins/losses), so this is does not just supplement this missing
information, somehow.)


  P.S.: By now, I should probably find better reference opponent than
gnugo... I wonder if to pick fuego or mogo... ;-) Strength is probably
not _as_ important as the variety of techniques used in order to avoid
selective blindness (that's why I also don't like tuning by self-play),
does anyone have a tip? Or do higher gnugo levels make much strength
difference?

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] October KGS bot tournament: 19x19 boards, slow

[Petr Baudis]

  Hi!

On Tue, Sep 29, 2009 at 11:02:17AM +0100, Nick Wedd wrote:
> and hope to receive one from
>   MoGousing the name 'CzechBot', operated by Petr Baudiš.

  Yes, you can count on that. I would like to also enlist my own bot
'pachi'; I hope that doesn't create a conflict of interest, especially
since it's currently probably around 12k-14k on 19x19. ;-)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] public test suite

[Petr Baudis]

On Tue, Sep 29, 2009 at 12:12:07PM +0200, Stefan Kaitschick wrote:
> Every now and then somebody submits an interesting 9*9 problem,
> usually rendered in X and O.
> Wouldn't it be great to have a public suite, lets say a directory
> with "black to play and win" sgf problems.
> For quick testing there should be only one correct first move.
> There could also be subdirectories for problem types.
> Maybe CGOS could be expanded to send bots through the test batch.

Fuego has a regression suite, which you can use together with
gogui-regress tool. I have been meaning to run my bot through it
for some time... :-)

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] cgosview?

[Petr Baudis]

  Hi!

  How do I use cgosview-linux-x86_32? By default it connects to the
19x19 server and that "works" (displays empty game list window), but
I can't find out how to tell it to connect to 9x9; the moment I try
to pass it any parameter, I get:

pa...@pixie:~/src> ./cgosview-linux-x86_32 -server cgos.boardspace.net -port 
6819
could not execute
pa...@pixie:~/src> ./cgosview-linux-x86_32 -port 6819
could not execute


-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Testing Process

[Petr Baudis]

  Hi!

On Mon, Sep 28, 2009 at 04:09:31PM -0600, Brian Sheppard wrote:
> >By now, I should probably find better reference opponent than
> >gnugo... I wonder if to pick fuego or mogo... ;-) Strength is probably
> >not _as_ important as the variety of techniques used in order to avoid
> >selective blindness (that's why I don't like tuning by self-play),
> >does anyone have a tip? Or do higher gnugo levels make much strength
> >difference?
> 
> Pebbles doesn't follow the norms, but I am very happy with my solution: just
> play constantly on CGOS.
> 
> CGOS provides a range of opponents of different styles, including non-MCTS
> opponents that use neural networks or alpha-beta. You can play 140 games per
> day, which is plenty.

  I agree CGOS is great, and you prompted me to run my bot there again
;-) - I wonder how much ELO it will get.

  But CGOS is for a different purpose I think - finding out where your
bot stands in the long term; what I'm using my gnugo testing for is
quickly assessing value of various minor changes and many variants.
Getting pretty reliable estimate (400 games) takes just about 3-5 hours;
getting that on CGOS would take few days, which is a lot less
convenient. I don't even almost ever look at the test games with gnugo,
just the overall percentage is all I care about.

> Fifth, Pebbles saves two positions from every loss: the last position in
> which it thought it was winning (eval of the selected move >= 50%), and the
> position in which it thought it had the greatest advantage.
> 
> Pebbles regularly (~1 or 2 games per day) loses games where it thinks it
> will win >90% of the time. I always learn something by analyzing those
> games.

  This is pretty interesting idea!

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cgosview?

[Petr Baudis]

  Hi!

On Tue, Sep 29, 2009 at 01:45:40PM +0200, Lars Schäfers wrote:
> I remeber a version where the call was just
> 
> ./cgosview-linux-x86_32  cgos.boardspace.net  6819

  Ahh, thanks, that works. I think the website should be fixed then. :-)

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Progressive widening vs unpruning

[Petr Baudis]

  Hi!

  I'm a little unclear on this, so I'd like to make sure I'm not missing
any important technique - is "progressive widening" and "progressive
unpruning" synonymous?

  I have looked both into the pMCTS and the CrazyStone papers and it
seems that "widening" differs from "unpruning" in that certain number of
simulations is first made before limiting the number of searches. Which
of the variants is commonly used? What "speed" of widening works for you
best?

  Thanks,

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Progressive widening vs unpruning

[Petr Baudis]

I guess I'm not really appreciating the difference between node value
prior and progressive bias - adding a fixed small number of wins or
diminishing heuristic value seems very similar to me in practice. Is the
difference noticeable?

On Tue, Sep 29, 2009 at 08:25:56AM -0700, David Fotland wrote:
> I start with one move, and slowly add moves to the pool of moves to be
> considered, peaking at considering 30 moves.
> 
> My current schedule looks like:
> 
> visits0   2   5   9   15  24  38  
> 59
> 90100  ...  2142
> moves 1   2   3   4   5   6   7   8
> 9 10   ...20
> 

Thanks!

On Tue, Sep 29, 2009 at 08:49:22PM +0200, Olivier Teytaud wrote:
> I don't know to which extent my terminology is commonly used, but it seems
> to be close to the distinction by Dave (but not exactly equal).
> 
>  For me I use "progressive widening" when we add moves, progressively,
> to the pool of moves which are to be considered;
> 
> whereas I use "progressive unpruning" when a score is computed for all
> moves, with a weight depending on the number of simulations; typically, I
> consider the Rave formula in Gelly&Silver as a progressive unpruning (with,
> for "prior" value, the Rave value).

Ah, I see; so "progressive widening" is what David described, modifying
the process of choosing node with highest urgency, while what you describe
as "progressive unpruning" is actually "just" what RAVE and priors are,
adding extra terms to the urgency calculation, with diminishing value as
the simulation count raises.

> * with progressive unpruning, if your prior is bad, you might have
> situations
>in which the score of the only good move is 0, whereas all bad moves have
> 
>values going to 0 but >0 and therefore the good move is never simulated
>(this can, however, easily be patched by a lower bound on the value given
>by the prior)

I found the "even game prior" (3/6) effective for this problem.

> Progressive unpruning, if you use the same terminology as me, has the
> advantage that the number of moves to be considered is adapted depending on
> the score; if you have three reasonnable moves and 300 bad moves, with
> progressive unpruning you'll visit all moves, whereas progressive unpruning
  * progressive widening you'll?
> will stay on the three reasonnable moves as long as they provide a better
> score than the prior score for the 300 bad moves.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] Progressive widening vs unpruning

[Petr Baudis]

On Tue, Sep 29, 2009 at 10:25:40PM +0200, Olivier Teytaud wrote:
> I think someone pointed out a long time ago on this mailing list that
> initializing the prior in terms of Rave simulations was far less efficient
> than initializing the prior in terms of "real" simulations, at least if you
> have classical "rave" formulas - at least, we had an improvement when adding
> a prior in the "real" simulations, but we had also an improvement when
> adding one more term, which is not linear. Sorry for forgetting who :-(

I'm wondering, are these tunings about squeezing single-percent
increases with very narrow confidence bounds, or something that gives
immediately noticeable 10% boost when applied? I'm curious about how the
top bots improve, if it's accumulating many tiny increases or long
quests for sudden boosts.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] RAVE tips

[Petr Baudis]

On Thu, Oct 01, 2009 at 04:50:26PM -0400, dhillism...@netscape.net wrote:
> For 9x9 games, when I added progressive widening to AntiGo (before I added 
> RAVE), it was low hanging fruit. I used my old program Antbot9x9 for the move 
> ranking and got a very nice strength increase for very little effort. Then, 
> with a bit of tweaking, I got more improvement. RAVE, on the other hand, 
> gives me a small improvement, and it comes at the cost of having to fuss with 
> it endlessly.

I couldn't ever get RAVE to give any big improvement in the past. Two
things made big difference to me:

(i) Switching to the beta RAVE formula.

(ii) Making playouts much heavier - elaborate tactical check whether a
move is a self-atari, and full set of Mogo 3x3 patterns.

(iii) Collecting AMAF from the playouts too, but not from very late
playout stage (cutting out last 1/n of the playout and a simple
heuristic to just ignore nakade within playout proved to be equivalently
strong for me).

I think there is a lot of interaction between RAVE and the AMAF move
distribution your playouts give you. What is crucial is that (ii) may
give strong bias to some moves, but (a) it should still be slightly
randomized, not making the same move _always_ in the situation (b) it is
*CRUCIAL* that it does not _prohibit_ a move completely if it can be
good in any situation; it will not be explored in the tree search either.

My (otherwise already rather strong on 9x9) bot was not seeing snapbacks
in the actual game because I had a bug in my self-atari detection. My
self-atari detection is now extremely complicated to single-out the best
possible set of moves (including snapbacks, nakade moves, eye
falsification and false eye throw-ins); I would probably benefit from
simplifying it a lot, gaining much speed for the cost of sometimes
allowing nonsensical self-ataris.

If your policy never allows to make some move, try disabling that part.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] Progressive widening vs unpruning

[Petr Baudis]

On Fri, Oct 02, 2009 at 08:27:23PM +0200, Olivier Teytaud wrote:
> >
> > >What's your general approach?  My understanding from your previous posts
> > is
> > >that it's something like:
> >
> > Your understanding is right.
> >
> >
> By the way, all the current strong programs are really very similar...
> Perhaps Fuego has something different in 19x19 (no big database of patterns
> ?). I'm not at all sure of this conjecture on Fuego.

Yes, Fuego uses just the 3x3 patterns; its strength is surprising. :-)
Someone conjenctured it is because of how well-tuned its constants are.
I also think large part of it is that it seems to use perfect nakade
solver in playouts, so it should be very strong at playout tsumego; at
least in my experiments I'm finding that crucial to strength of my
bot...

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] Progressive widening vs unpruning

[Petr Baudis]

On Fri, Oct 02, 2009 at 06:49:46PM -0400, Jason House wrote:
> On Oct 2, 2009, at 2:24 PM, Olivier Teytaud 
> wrote:
> 
> >
> >4) regularized success rate (nbWins +K ) /(nbSims + 2K)
> >(the original "progressive bias" is simpler than that)
> 
> I'm not sure what you mean here. Can you explain a bit more?

It looks a lot like the "even game" prior put in another term too.
And it seems to me that this can implement progressive bias well;
as long as simulations are too noisy (nbSims < K), the effect
of this term is very small.

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Conjectures on Fuego

[Petr Baudis]

On Fri, Oct 02, 2009 at 09:52:35PM -0600, Martin Mueller wrote:
> >Yes, Fuego uses just the 3x3 patterns; its strength is surprising. :-)
> >Someone conjenctured it is because of how well-tuned its constants
> >are.
> >I also think large part of it is that it seems to use perfect nakade
> >solver in playouts, so it should be very strong at playout tsumego; at
> >least in my experiments I'm finding that crucial to strength of my
> >bot...
> 
> It is true that Fuego has no larger patterns. However, playouts also
> use a number of other rules, e.g. for low liberty and selfatari.
> 
> Regarding parameter tuning, I am not so sure. This may have been
> true in the past. However, there have been many changes to Fuego in
> recent months, but the parameters have not been re-tuned, so there
> is probably room for improvement.
> 
> Fuego is unfortunately also far from perfect in nakade playouts. It
> only implements a simple but effective rule of moving single stone
> selfataries to the adjacent point. This "solves" most stretched
> nakade shapes. However, "bulky" shapes are misplayed with high
> probability (and some with 100% probability...)

Interesting! I got confused by GoUctUtil::IsMutualAtari, but now I'm not
sure if it is even really used, nor exactly what is it supposed to
actually test in that condition. :-)

Then it turns out that I'm already implementing pretty much all the
tests in Pachi as Fuego is, just probably way too mistuned and buggy,
ah well... ;-) The strange thing is, I don't seem to be getting any
noticeable gain from 2-liberty tactics and checking the pattern at two
last moves instead of just the last one; did you get a big gain from
these?

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] [Fwd: Announcement ICGA Events 2010]

[Petr Baudis]

Hi!

On Tue, Oct 06, 2009 at 12:08:06AM +0900, Hideki Kato wrote:
> Nick Wedd: :
> >I wonder if anyone here has a URL for either the Tainan Computer Go 
> >Tournament, to take place on October 30th and 31st, or the GPW Cup, 
> >November 13th and 14th?  I cannot read Chinese or Japanese, and so have 
> >failed to find anything by using a search engine.
> 
> http://ai.csie.ndhu.edu.tw:9898/eng/ is the URL.  It's not Tainan
> but Taichu tournament this year.  It's not two day but one day
> tournament at 30th.  MoGoTW, Zen and some (six?) domestic
> programs have registered, I've heared.  I'll attend and operate
> Zen via KGS.
> 
> GPW Cup will be held in November 14th and 15th at Hakone, Japan as
> usual.  9x9 only, Chinese rules, komi is 7 points (thank you, Erik).
> Since I'm the director of the tournament, please freely ask me if you
> have any question.

Is it possible to participate in these tournaments remotely? I think I
would like to start participating in these, but I certainly have no
budget (or time) to travel outside of Europe. :-(

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Congratulations to AyaMC!

[Petr Baudis]

On Tue, Oct 06, 2009 at 05:13:17PM +0100, Nick Wedd wrote:
> In message , Nick Wedd
>  writes
> >Congratulations to AyaMC, winner of Sunday's KGS Computer Go
> >tournament! My report is at
> >http://www.weddslist.com/kgs/past/52/index.html
> >
> >Two people had bots crash after receiving the message
> >"FINEST: Still an outstanding command".  I do not know what this
> >means, and am reporting it to wms.
> 
> I have heard back from wms:
> 
> > The "still an outstanding command" message means that a
> > command has been sent to the engine, but the engine hasn't yet
> > answered it. That's probably a bug in the engine, because GTP
> > requires all commands to be answered with an acknowledgement
> > or an error.
> 
> So it seems that CzechBot (=MoGo) and Fuego need to implement
> something, I don't know what.  It's strange that this has never come
> up before.

This is caused by the fact that both CzechBot and Fuego (probably) were
stuck up in reading, probably either getting dead-locked or stuck in
some infinite loop; so in fact the outstanding command was genmove, and
neither of these ever chose which move to play. CzechBot wasn't even
printing out any progress lines.

I think the problem here is that when kgsGtp reconnects, it does not
restart the engine; I think doing that would help a lot in these
situations, since a stuck engine would be restarted by the reconnect.
Right now, after reconnecting, kgsGtp was still waiting for the original
genmove command from "old" connection to finish.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Rating variability on CGOS

[Petr Baudis]

On Thu, Oct 08, 2009 at 01:48:05PM -0600, Brian Sheppard wrote:
> About two weeks ago I took Pebbles offline for an extensive overhaul of its
> board representation. At that time Valkyria 3.3.4 had a 9x9 CGOS rating of
> roughly 2475.
> 
> When I looked today, I saw Valkyria 3.3.4 rated at roughly 2334, so I
> wondered what was going on.
> 
> I found a contributing factor: Valkyria has massively different results
> against Pachi than against Pebbles. It happens that Pachi started playing a
> day or two after Pebbles went offline.
> 
> Pebbles and Pachi are both rated around 2200, but Valkyria shreds Pebbles a
> lot more often than Pachi:
> 
> Pachi:   185 / 273 = 67.8%
> Pebbles: 429 / 503 = 85.3%
> 
> There are a lot of lessons here...

So, I'm curious how well Pachi will do against Pebbles. ;-) I'm hoping
that I'm nearing another major improvement in strength soon, so the
current version may not stay on CGOS much longer.

(Curiously, the two identical Pachi instances were even after many games
very far apart in ELO points (about 100 ELO), somehow one of the
instances was winning against the other in about 80% of games; it
corrected itself after few more days without me doing anything, though.
Stochastic environments are funny.)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] [Fwd: Announcement ICGA Events 2010]

[Petr Baudis]

On Tue, Oct 06, 2009 at 01:33:10AM +0900, Hideki Kato wrote:
> The tournament in Taiwan allows playing through KGS but according to 
> the rules , it's 
> preferred to participate at least one person from each team.  If not, 
> the entry fee will be doubled.  Please ask the organizer for detail 
> (Click "Contact us" on ).

Thanks both to you and Jacques for all the information! I will yet see
if I come up with something on par with MoGoTW or Zen until the
tournament. ;-)

> In addition to above, UEC Cup will allow remote participants, though 
> the rules are not open yet.  The registration will start Oct 9th.  See 
>  for detail.

Interesting!

It now says that Japanese rules will be used; this is a severe problem
for me, I wonder how will other cope - can any of the strong MonteCarlo
programs play with Japanese rules?

Reading further, it says "we do not permit to play through the Internet,
because it is important for us to meet together in the venue"; so maybe
remote participation is not possible after all...

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Generalizing RAVE

[Petr Baudis]

On Fri, Sep 25, 2009 at 11:51:21AM +0200, Łukasz Lew wrote:
> I tried CRAVE in my master thesis 4 years ago. The context was a
> growing decision tree.
> It didn't work as well.

This sounds similar to one idea of mine; is your thesis available
anywhere? (Or any other material published on CRAVE.)

Thanks,

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Neural networks

[Petr Baudis]

  Hi!

  Is there some "high-level reason" hypothesised about why there are
no successful programs using neural networks in Go?

  I'd also like to ask if someone has a research tip for some
interesting Go sub-problem that could make for a nice beginner neural
networks project.

  Thanks,

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Neural networks

[Petr Baudis]

On Wed, Oct 14, 2009 at 02:45:18PM +0200, Erik van der Werf wrote:
> In my opinion NeuroGo was quite succesful with neural networks.
> Magog's main strength came from neural networks. Steenvreter uses
> 'neural networks' to set priors in the Monte Carlo Tree.

Ah, you are right, that sounds like fairly natural idea, I think I will
experiment with that too. Steenvreter is fairly strong, so I take my
words back. :-)

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Neural networks

[Petr Baudis]

On Wed, Oct 14, 2009 at 05:12:58PM +0200, Heikki Levanto wrote:
> On Wed, Oct 14, 2009 at 03:34:59PM +0300, Petri Pitkanen wrote:
> > Neural network tend to work well in those cases where evaluation function is
> > smooth, like backgammon. Even inbackgammon neural networks do give good
> > results if situation has possibility of sudden equity changes like deep
> > backgames and deep anchor games. Top backgammon programs 3-ply search on top
> > neural network to handle these problems.
> > 
> > I do not know wher neural nets would fit well, perhaps finding invasion
> > spots?
> 
> I have been speculating about a NN evaluation function for go, feeding it a
> lot of preprocessed information about the position, like number of strings
> with 1,2,3,4, or more liberties, number of stones in same, number of separate
> groups, number of "obviously" dead stones, strings, and groups, number of
> points "clearly" controlled by each player, etc, etc. This should be possible
> to train from existing games where we know the result (in the beginning it is
> 50-50, in the end one or the other has won 100-0. Assume some simple function
> in between). 

Interesting idea, but I think MCTS programs already handle quite fine
the part where there is some simple function in between. Most of the
problematic games seem to be when MCTS is chasing and trying to kill a
single group, and the question is whether it succeeds; IOW, I think the
problem is tactical rather than strategical in MCTS (I have few of my
own ideas to try to deal with that, non-related to NN ;-).

I like Magnus' ideas, though the 3x3 problem seems to be a bit of a
special case of what Remi did, and I don't really have an idea how to
well train the "in-UCT NN".

Another idea I received was actually not related to computers _playing_
Go, but maybe that's all the more interesting in current times - a NN
that could identify the player's "playing style" by looking at few of
her games and deciding which well-known player they look like (e.g.
Takemiya, Cho Chikun, Lee Sedol, TheCaptain ;-). Of course it is quite
an interesting problem what set of features to choose...

Thank you all for your ideas so far!

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Great Wall Opening by Bruce Wilcox

[Petr Baudis]

On Fri, Oct 16, 2009 at 08:55:34PM +0200, "Ingo Althöfer" wrote:
> In the year 2000 I bought the book
> "EZ-GO: Oriental Strategy in a Nutshell",
> by Bruce and Sue Wilcox. Ki Press; 1996.
> 
> I can only recommend it for the many fresh ideas.
> A few days ago I found time again to read in it.
> 
> This time I was impressed by Bruce Wilcox's strange 
> opening "Great Wall", where Black starts with a loose 
> wall made of 5 stones, spanning over the whole board.
> 
> Bruce proposes to play this setup as a surprise weapon,
> even against stronger opponents.
> 
> Now I made some autoplay tests, starting from the end position
> given in the appendix of this mail.
> * one game with Leela 3.16; Black won.
> * four games with MFoG 12.016; two wins each for Black and White.
> So there is some indiciation that the Great Wall works even
> for bots, who are not affected by psychology.

In general, especially in environment so stochastic as MCTS, these are
awfully small samples. To get even into a +-10% confidence interval, you
need at least 100 (that is, ONE HUNDRED) games. Otherwise, the results
aren't statistically meaningful at all, as I have myself painfully
discovered so often ;-) - they can be too heavily distorted.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] monte carlo

[Petr Baudis]

  Hi!

On Sat, Oct 17, 2009 at 05:02:33PM +0200, Folkert van Heusden wrote:
> I'm trying to implement a monthecarlo algorithm in my go program. Now
> the results are dramatic: the elo-rating of my go program drops from
> 1150 to below 700. I tried:
>  - evaluate the number of captured stone
>  - evaluate strategic elements (without MC this strategic eval gives
>that 1150 elo).
> Currently my program can evaluate 500 scenes per second and I let it
> "think" for 5 seconds.
> What could be the cause of this dramatic results? Wrong evaluation? Not
> enough nodes processed?

  It's not clear what do you mean by the "evaluation", and how do you
integrate montecarlo to the rest of your program, so it's hard to
comment. But it takes some time to weed out some pretty basic bugs which
make your program play horribly but yet not make it lose every single
game - watch your program's evaluation and the montecarlo playouts
closely for anything fishy.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Great Wall Opening by Bruce Wilcox

[Petr Baudis]

On Sat, Oct 17, 2009 at 08:36:13AM -0400, Don Dailey wrote:
> 2009/10/17 Petr Baudis 
> 
> > On Fri, Oct 16, 2009 at 08:55:34PM +0200, "Ingo Althöfer" wrote:
> > > In the year 2000 I bought the book
> > > "EZ-GO: Oriental Strategy in a Nutshell",
> > > by Bruce and Sue Wilcox. Ki Press; 1996.
> > >
> > > I can only recommend it for the many fresh ideas.
> > > A few days ago I found time again to read in it.
> > >
> > > This time I was impressed by Bruce Wilcox's strange
> > > opening "Great Wall", where Black starts with a loose
> > > wall made of 5 stones, spanning over the whole board.
> > >
> > > Bruce proposes to play this setup as a surprise weapon,
> > > even against stronger opponents.
> > >
> > > Now I made some autoplay tests, starting from the end position
> > > given in the appendix of this mail.
> > > * one game with Leela 3.16; Black won.
> > > * four games with MFoG 12.016; two wins each for Black and White.
> > > So there is some indiciation that the Great Wall works even
> > > for bots, who are not affected by psychology.
> >
> > In general, especially in environment so stochastic as MCTS, these are
> > awfully small samples. To get even into a +-10% confidence interval, you
> > need at least 100 (that is, ONE HUNDRED) games. Otherwise, the results
> > aren't statistically meaningful at all, as I have myself painfully
> > discovered so often ;-) - they can be too heavily distorted.
> >
> 
> 100 Games doesn't even tell you much unless the difference is pretty large.

Well, this is simple math. With 100 bernoulli trials, your
95%-confidence interval is at ~ +-10% if your rates are around 50%.
Of course, if the results you want to compare are closer than within
20%, you will need more trials. :-)

When I'm too lazy to compute this for myself or for some reason don't
use gogui-twogtp that computes the error (confidence_interval/1.96) for
me, I find http://statpages.org/confint.html pretty handy for quick
calculations.

(To convert win rates to ELO differences, I found
http://www.chesselo.com/probabil.html useful, but I don't find ELO too
useful for basic improvements testing, since I compare only winrates
against a single reference player.)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Great Wall Opening by Bruce Wilcox

[Petr Baudis]

On Tue, Oct 20, 2009 at 08:10:47AM +0100, Christian Nentwich wrote:
> Go has been played long enough, and the proposed "great wall"
> opening is simple enough, that is should be more than valid to argue
> that "if it was a good opening, it would be played more often".

A possible explanation I have read some time ago in pro commentaries of
some of the very first shin-fuseki experiments about opening on tengen:
pros don't think it is inferior at all, in fact it may well be the best
opening move for black, but pros avoid it simply because it is way too
complex and complicated - they explained that the corner sequences are
much easier to read (this includes tuning them in accord with the
whole-board strategy) and much better explored than a complex fight
in center, making for a surer winning strategy.

So while black opening on tengen may well be _the_ winning strategy for
black, it simply is too difficult to play it out correctly.

> One could try and plonk down those openings and see whether the
> engine has a significantly better result. I would conjecture that
> current engines are not strong enough to use them correctly, and it
> won't make any difference where you place the first three stones, as
> long as it's reasonable distributed and not on the second line.

This has been my observation from watching pachi closely playing on KGS;
the fuseki matters very little, it may make a difference when pachi is
6d and is going to play drawn-out even games with strong humans, but then
again e.g. High55 does not have that bad a record either. ;-)

> I may extend my conjecture to amateur players under about 3 kyu :)

(So I extend it even further; but to even out bad fuseki, of course you
need to be exceptionally good (for your level) in other parts of the
game and have very fighting playing style.)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Handicap games collection?

[Petr Baudis]

  Hi!

  Does anyone know of any handicap games collection? For MCTS handicap
play research, I'm looking for at least 500 games of any handicap (1-9),
ideally of reasonable strength (KGS 2k-9d).

  Thanks!

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Handicap games collection?

[Petr Baudis]

On Tue, Oct 20, 2009 at 03:06:20PM +0200, Ben Lambrechts wrote:
> You can filter them from the following collections:
> 
> http://u-go.net/gamerecords/
> http://u-go.net/gamerecords-4d/

Thanks! I didn't want to use the main collection, but I wasn't aware of
the 4d+ collection, which looks perfect!

Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] NVidia Fermi and go?

[Petr Baudis]

Hi!

On Fri, Oct 23, 2009 at 10:21:07AM +0100, Christian Nentwich wrote:
> ah  - I missed the white paper, I will read that later so I can form
> a real opinion. I must say, the mere fact that there will be C++
> support and a proper development environment (even if only for
> Windows) is a big relief. Working with CUDA at the moment is a
> nightmare, straight back to the 80s.

I don't think it's so bad. :) The only annoying thing is that the
applications are extremely hard to debug (especially concurrency issues
which don't show up in the CPU emulation mode). I'm not sure if Fermi
will improve that significantly (at least some way to log debug prints
in a ring-buffer or such), but other than that I didn't find the CUDA
development particularly difficult.

Another great thing would be fine-grained profiling support...

> Darren Cook wrote:
> >>these articles are still somewhat short on detail, so it's hard to tell.
> >
> >Yes the linux mag article was a bit empty wasn't it, but did you take a
> >look at the 20-page whitepaper:
> >http://www.nvidia.com/content/PDF/fermi_white_papers/NVIDIA_Fermi_Compute_Architecture_Whitepaper.pdf

I haven't got time to read it yet either, but the thing that took my
interest was the multiple kernel support, I think that could achieve
much better GPU utilization, but it depends on implementation details.

I would love if there would be native support for extremely fast
parallel summing of array contents; for my intersection model, that
would help immensely, I guess.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] NVidia Fermi and go?

[Petr Baudis]

On Fri, Oct 23, 2009 at 01:34:29PM -0600, Brian Sheppard wrote:
> I have not done any GPU experiments, so readers should take my guesswork
> FWIW. I think the code that is "light" is the only piece that parallelizes
> efficiently. Heavy playouts look for rare but important situations and
> handle them using specific knowledge. If a situation is "rare" then a warp
> of 32 playouts won't have many matches, so it will stall the other cores.
> 
> I have no data regarding the probability of such stalls in heavy playouts,
> but I think they must be frequent. For example, if the ratio of heavy to
> light playouts is a four-fold increase in CPU time, then a sequential
> program is spending 75% of its time identifying and handling rare
> situations.

My experiment used light playouts, but ready for increasing weight by
picking a move according to probability distribution (which is easy to
do without any branch stalls itself).

I think adding that to the other experiment (playout-per-thread instead
of intersection-per-thread) wouldn't be too difficult, and then as long
as you track liberty counts, CrazyStone-style playouts are already just
a single step away, I'd guess; I think then the problem is not branch
stalls, but getting the bandwidth for pattern matching; then I'm
wondering if you could actually use some clever GPU-specific texture
tricks for that, but I haven't looked at that in depth (yet)...

> BTW, it occurs to me that we can approximate the efficiency of
> parallelization by taking execution counts from a profiler and
> post-processing them. I should do that before buying a new GPU. :-)

I wonder what do you mean by that.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] MoGo Zones

[Petr Baudis]

  Hi!

  (Sylvain et al. 2006) describes the use of CFG-based zones in random
simulations to simulate only the local position and tune the score based
on few thousands of simulations of outside of the zone. It doesn't seem
the idea is too practical (especially with RAVE, but there seem to be
more problems), but I'm wondering if MoGo or anyone is still using it,
perhaps in a modified form?

  Thanks,

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] monte carlo

[Petr Baudis]

On Sun, Oct 25, 2009 at 06:52:56PM +0100, Folkert van Heusden wrote:
> What method are you guys using for the monte carlo search? What do you
> do?
> I pick at random a move, then for the resulting board that comes out of
> that pick another move and so on.
> Then, after that I evaulate the number of stones etc.

Do you mean you count the score? Make sure you actually count the stone
right, and (quite important) that you are picking out moves really at
random, not skewed in any way.

> What do you guys look at to select a move using monte carlo?

People use heuristics to prefer captures, escaping atari, play local
moves that match certain 3x3 patterns etc. - there is plenty of papers
covering this, I recommend you look at them. It's fairly important to
have all the heuristics somewhat randomized (depending on other parts of
my engine, I've found any value between 60% to 90% probability of
applying each heuristic optimal).

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] monte carlo

[Petr Baudis]

On Sun, Oct 25, 2009 at 10:16:58PM +0100, Folkert van Heusden wrote:
> > > What method are you guys using for the monte carlo search? What do you
> > > do?
> > > I pick at random a move, then for the resulting board that comes out of
> > > that pick another move and so on.
> > > Then, after that I evaulate the number of stones etc.
> > 
> > Do you mean you count the score? Make sure you actually count the stone
> > right, and (quite important) that you are picking out moves really at
> > random, not skewed in any way.
> 
> Yes, the score indeed. Well, only the number of stones removed from the
> board. I did not implement an algorithm to count areas belonging to a
> color yet.

That would seem to have only quite limited correlation with winning the
game.

> May I ask: how many board-settings (one move + all evaluation) do your
> programs calculate per second?

Depends on the hardware. ;-) We usually count in number of complete
playouts per second.

On 9x9, libego can play i think about 100k playouts per second on decent
CPU, but is very light. Pachi can do 35k light playouts per second and
15k heavy playouts per second on the same CPU (single-threaded). Both
Pachi and libego are written in a compiled language; when your speed is
in the right order of magnitude, I've found playout move selection
improvements much more profitable than further optimizing for speed.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

Hi!

On Mon, Oct 26, 2009 at 07:19:45PM +0100, Olivier Teytaud wrote:
>  For information, our Taiwanese partners(**) for a ANR grant have organized
> public demonstration games between

Thanks for the information!

> MoGoTW (based on MoGo 4.86.Soissons + the "TW" modifications developped
> jointly with our Taiwanese colleagues)
>  and
> C.-H. Chou 9P, top pro player winner of the LG Cup 2007.

Could you give us at least a general picture of improvements compared to
what was last published as www.lri.fr/~teytaud/eg.pdf ? Is it "just"
further tuning and small tweaks or are you trying out some exciting new
things? ;-)

> c) My feeling is that blitz games are not favorable to computers...
> Statistics
> are in accordance with this I guess. Humans are stronger for short time
> settings.

Maybe in high-level 9x9 games that's true, but as a general statement
I'd dispute this, at least in watching 5k-1k-level 19x19 MCTS games on
KGS I got a completely different impression; humans are much more

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Mon, Oct 26, 2009 at 04:20:24PM -0400, Don Dailey wrote:
> Peter,   did your comment get cut off?

Oops, indeed. "Prone to tactical mistakes in high time pressure" is what
I meant to say.

> Anyway,  I agree with you on this.   Humans are not stronger on short time
> settings.  I believe that SOME humans could be better if they have a
> problem staying interested for a longer period of time and the longer time
> control upsets their rhythm or something.   But I don't believe it's a
> general rule.

Well, of course most humans play better with more time, the question is
whether they or the computer gain more from the extra time.

And I think while between, let's say 30s/move and 10min/move the curve
of such advantage could be pretty straight, I think it would behave
quite differently at the extreme ends.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Tue, Oct 27, 2009 at 08:47:41AM +0100, Olivier Teytaud wrote:
> > Could you give us at least a general picture of improvements compared to
> > what was last published as 
> > www.lri.fr/~teytaud/eg.pdf? Is it 
> > "just"
> > further tuning and small tweaks or are you trying out some exciting new
> > things? ;-)
> >
> 
> There is one important improvement, for which I must check with coauthors if
> they agree for me to explain it. Below the other recent improvements in 9x9.
> 
> We have also recently encoded some (very simple) tricks against bad cases as
> we had
> against Fan Hui (i.e. cases in which the only good move is not simulated).
> Roughly,
> is the value of the node is very bad, then simulate randomly among the sons.
> We can
> show (mathematically) that with such tricks, we have the consistency (as
> UCT),
> plus some frugality (i.e. we do not simulate all the tree, even with
> infinite computation time whereas UCT simulates all the tree AND simulates
> all the tree infinitely often).
> It gives very little improvement in self-play, but it understands better at
> least the situation seen in the game with Fan Hui. What I like in this
> improvement is that it's
> the first time there is something which was mathematically developped for
> mogo and
> which leads to a positive result. Well, maybe this changes only 1% of games,
> but maybe it makes mogo more robust for complicated ko fights which do not
> occur in self-play.

Interesting! Conceptually, I don't like this that much since it just
work-arounds RAVE bias instead of solving it in more general way, but I
can see its technical value.

AIUI, once upon N simulations in a node you take let's say the node with
the lowest value, pick one son of it at random within the tree and start
a simulation?

> Finally, there was a GP-based development of new patterns. However, this is
> quite minor I guess - I like the fact that this GP-based module works in a
> somehow stable manner, but maybe it would only be worth using it on an
> implementation which is not
> yet optimized.

Wow - one of my planned little projects was genetic development of the
3x3 patterns... To evaluate patterns, do you use tournaments or some
smarter method? I feared one generation would take awfully long...

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MC hard positions for MCTS

[Petr Baudis]

  Hi!

On Tue, Oct 27, 2009 at 12:05:57PM +0200, Petri Pitkanen wrote:
> Are there more peculiar situation that will cause problems for MCTS apart
> from the three I know.
> 1. Nakade (this is partuially solved in most of the programs)
> 2. Semeais
> 3. Double Ko.

  Yes, these are all just particular instances of a general class; it
shows up in fights at many points. They all manifest as a problem where
the simulations introduce a massive bias in the particular situation,
misjudging life of certain group, usually where there is one right move
and many bad ones in the position (right one will be played only with
small probability).

  This causes what I call the "horizon effect" which prevents the
tree exploration to work properly - the moment the tree finds a sequence
that unbiases the simulations, it is horrified by the bad results [*] and
switches to a different branch, until it finds the same; thus, the bot
pushes the resolution (unbiasing) of the situation over the tree horizon
for as long as possible. This shows in actual games as the bot playing
random throwins and obviously pass moves before resigning.

  In case of nakade, the bias is introduced by anti-self-atari
heuristics in the playouts and is probably indeed largely solved by
smarter self-atari detection. In case of various kos, perhaps a
simulation bias for re-taking the ko could help, but this is probably
fairly simple. In case of semeai, the bias is obvious and the solution
is currently totally unobvious.

  There are two ways to deal with this - removing the bias from the
simulations by increasing the intelligence within cautiously, and
finding a way to deal with the bias in the tree. I'd say so far all
improvements of simulations since uniform playout could be described
as trying to solve this problem, and to a certain point it greatly
helps increase the convergence to good result, but I think we are behind
that point now and making the simulations smarter is now only pushing
away the inevitable.

  I don't know how much hidden ongoing research is being done about
dealing with the bias in the tree, the only result so far I'm aware of
is Remi Coulom's criticality heuristic, and it wasn't that effective;
I personally have some clear ideas I want to start experimenting with as
soon as possible - I think we need a top-down counterpart for the
bottom-up propagation function of RAVE. IMHO a substantial progress
in this direction is the next big thing to happen in computer go.


  [*] "Bad results" for the parent node owner - I have seen the bias
as being both unduly positive _and_ unduly negative, though the latter
seems fairly rare - I think I saw it only once in a rather complicated
large temporary seki fight and while the bot obviously won it, the
percentages were horrible, it was lucky they stayed above the resign
threshold until the situation finally got resolved.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Designing coefficient functions

[Petr Baudis]

  Hi!

  Does anyone have some tips about designing effeciently-computable
coefficient functions that would have similar properties to the "eg
paper"?

  I.e. something like:

  a + b + c = 1
  n(d) = 0  a ~ 0, b ~ 0, c ~ 1
  n(d) smallb >> a
  n(d) -> infty a ~ 1

  It sounds simple, but I'm a bit lost about embedding the c term to my
RAVE equation. :) (Currently I use the Silver beta formula, same as
in Fuego.)

  Thanks,

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Tue, Oct 27, 2009 at 06:32:44PM +0200, Olivier Teytaud wrote:
> >
> >
> > AIUI, once upon N simulations in a node you take let's say the node with
> > the lowest value, pick one son of it at random within the tree and start
> > a simulation?
> >
> 
> I'll try to write it clearly (for binary deterministic games, extensions can
> be shown but they are too long and out of topic in this mailing list I guess
> :-) ):
> 
> If (average value of father < threshold )
> then
> randomly pick up one son
>else
>pick up the son with maximum score
> end
> 

Aha, thanks for clearing that up.

> If the score is asymptotically equivalent to the success rate, and if the
> threshold is >0 and < 1, then this ensures
> consistency (convergence to optimal move). If the score is well done, then
> this is consistent without visiting all the tree.

But is it shown that "the score is well done" for these properties to
hold in case of RAVE-guided exploration? Since it massively perpetuates
any kind of MC bias...

> > Wow - one of my planned little projects was genetic development of the
> > 3x3 patterns... To evaluate patterns, do you use tournaments or some
> > smarter method? I feared one generation would take awfully long...
> >
> 
> We use a stupid method, i.e. the success rate. The pattenrs are bigger than
> 3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are
> used
> for distributing the computational effort among the tested patterns.

Thank you for pointing me to more study material. :-)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MC hard positions for MCTS

[Petr Baudis]

On Tue, Oct 27, 2009 at 01:10:09PM +0100, Stefan Kaitschick wrote:
> 
> >But, has anyone gathered stats on positions, from real games, that
> >require precise play by the defender/attacker/both/neither? Is defending
> >really easier than attacking?
> >
> >Darren
> 
> 
> Who is the defender?
> One side is defending his territory, the other side is defending his group.
> I think the general bias is towards overestimating the chance of killing.
> Thats what makes MCTS programs such an aggressive lot :-)

I think they are agressive mainly since killing big group is much surer
way of victory than drawn-out close game, they want to maximize the
advantage the quickest way possible.

Also my collected anectodal evidence suggests MCTS might be actually
quite lousy at counting score in tight games (at least on 19x19, and
that fact makes a lot of sense to me) - I'm not completely sure of this
though, did anyone do some extensive testing of modern MCTS on hard
endgame problems?

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[Petr Baudis]

On Thu, Oct 29, 2009 at 12:00:32PM -0400, Don Dailey wrote:
> That is exactly as it should be and is not a barrier.   I don't think you
> know the difference between a wall and a point that is just far away.

I'd phrase this positively - the point is extremely far away with the
current way MCTS will succumb to blunders because of the way it is
completely unable to compensate for systematic bias (the amount of
computation required to overcome the bias is extreme), but some
clever algorithmic improvement could put the point much closer.

This is just a discussion how steep a slope we will already call a wall,
I think it's more productive to talk about how to make the slope less
steep. :)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MPI vs Thread-safe

[Petr Baudis]

On Thu, Oct 29, 2009 at 12:40:26PM -0600, Brian Sheppard wrote:
> And now my question: what do you actually do: MPI, thread-safe, both, or
> something else?

Have you read the Parallel Monte-Carlo Tree Search paper? It sums up the
possibilities nicely. I personally just use root parallelization
(similar to what you probably mean by MPI, though without resyncs) in
Pachi, confirming the paper's finding that the play improvement is
larger than multiplying number of sequential playouts appropriately.
I have a suspicion that this scales only to very small number of
threads, though.

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MPI vs Thread-safe

[Petr Baudis]

On Fri, Oct 30, 2009 at 07:53:15AM -0600, Brian Sheppard wrote:
> >I personally just use root parallelization in Pachi
> 
> I think this answers my question; each core in Pachi independently explores
> a tree, and the master thread merges the data. This is even though you have
> shared memory on your machine.

Yes.

> You also have possibilities for largely lockless thread safety. For
> instance, the Intel architecture has atomic memory access instructions that
> allow lockless data safety. Remi Coulom published a paper on this subject.
> 
> I am not even sure that "leaf" parallelization is really ruled out. For
> example, if GPU-based implementation works, then leaf parallelization must
> be reconsidered.

Fuego is probably prime example of well-working leaf parallelization,
using atomic memory operations and virtual losses; see the TR for
details and measurements.

> > similar to what you probably mean by MPI, though without resyncs
> 
> MPI is "message passing interface" an industry standard API for supporting
> high performance computing.
> 
> It is used for sharing data among multiple processes (that is, no shared
> memory). I recall that MoGo published that their massively scalable strategy
> is based on this approach.

Yes, I know what MPI is, I just wasn't sure what "_the_ MPI method"
would neccessarily be.

> >confirming the paper's finding that the play improvement is
> >larger than multiplying number of sequential playouts appropriately.
> 
> Well, this is another reason why I doubt the results from the Mango paper.
> Parallelization *cannot* provide super-linear speed-up. The existence of
> super-linear speed-up proves that the underlying single-threaded program is
> flawed.

I don't see that at all. It seems quite logical to me that the results
could be better when threads vote on resulting move instead of spending
appropriately more in single search. I think the explanation that this
compensates better for various (short-term?) biases popping within the
UCT tree is logical.

It's some time since I last measured the multi-threading gains and I
made quite a lot of tweaks in the UCT exploration since, maybe I should
re-measure again; it's just that measuring this takes a lot of CPU
resources, thus is a pain. :-)

-- 
Petr "Pasky" Baudis
A lot of people have my books on their bookshelves.
That's the problem, they need to read them. -- Don Knuth
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/