Re: [computer-go] Reference Montecarlo TreeDecision Bot.

[Sylvain Gelly]

I am not good at term definition, but I would say RAVE is the algorithm
extending AMAF in MCTS, including how to accumulate the counts at each node
 (trivial extension even though implementation can be tricky), how to
combine with UCT (or other move choice), and how to integrate with priors
(based on expert knowledge or previous learning).

Sylvain

On Tue, Dec 15, 2009 at 10:31 PM, Mark Boon wrote:

> I took AMAF as the process to consider all the moves regardless when
> they were played in the sequence (although a slight discount for later
> in the sequence seems to help a little) whereas RAVE is using an
> undefined method to favour some nodes over others prior to expanding
> them. The reason (as far as I understood so far) they get confused is
> because a popular method to use in RAVE is in fact using AMAF values.
>
> Mark
>
> On Tue, Dec 15, 2009 at 2:12 AM, Magnus Persson 
> wrote:
> > Quoting Petr Baudis :
> >
> >> On Mon, Dec 14, 2009 at 10:37:24PM -0800, Peter Drake wrote:
> >>>
> >>> It's easy to get confused -- different researchers use the terms
> >>> slightly differently.
> >>>
> >>> They both gather data on moves other than a move made from the
> >>> current board configuration. I would say that AMAF stores statistics
> >>> on every move played from any position, while RAVE only stores info
> >>> on moves played from descendants of the current position.
> >>> Consequently, AMAF uses a global table, whereas RAVE data must be
> >>> stored at every node.
> >>
> >> I guess that is a good definition; I assume this difference to arise
> >> from the fact whether you use tree or flat MC, so for me, AMAF in tree
> >> always means "from descendants of the current position". Instead, to me
> >> AMAF is the data collected, while RAVE is the way to apply the data in
> >> the node urgency computation (which furthermore splits to what I call
> >> for myself Sylvain Gelly's RAVE vs David Silver's RAVE, of course...).
> >
> > This also how I have interpreting AMAF and RAVE after being confused
> > initially thinking it was just two names for one thing.
> >
> >> I think it's because I haven't seen this approach evolve and I'm not too
> >> familiar with the pre-RAVE AMAF, so perhaps I underestimate how
> >> revolutionary the "descendants only" idea was.
> >
> > AMAF was first used with programs that did not build a tree. Perhaps this
> is
> > why Peter Drake makes this interpretation. When I implemented AMAF in
> > Valkyria it was always self evident that "descendants only" is only the
> only
> > good way of making use of it, since search was so deep that the positions
> > cannot be compared.
> >
> > Best
> > Magnus
> > ___
> > computer-go mailing list
> > computer-go@computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Rave coefficient

[Sylvain Gelly]

On Tue, Jun 30, 2009 at 12:47 AM, Peter Drake wrote:
> A while back, Sylvain Gelly posted this code:
>
> ChooseMove(node, board) {
>  bias = 0.015  // I put a random number here, to be tuned
>  b = bias * bias / 0.25
>  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
> }
>
> From this, it appears that each node knows about its own counts and wins, as
> well as the rave counts and wins of its children.
>
> I understand (correct me if I'm wrong!) that the "value" line is a weighted
> sum of the win rate among actual moves and the win rate among RAVE moves.
>
> My question is: what is the meaning of this line?
>
>    coefficient = 1 - rc / (rc + c + rc * c * b)
>
> Why this formula?

You can look at a thread on this list
http://computer-go.org/pipermail/computer-go/2008-February/014095.html
and better the attachment explaining the formula.
http://computer-go.org/pipermail/computer-go/attachments/20080208/6519e9c5/rave.pdf

Hoping it helps,
Sylvain
>
> Thanks for any help you can offer,
>
> Peter Drake
> http://www.lclark.edu/~drake/
>
>
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGo and passing

[Sylvain Gelly]

Obviously I should read better the emails before answering. Olivier
rightly answered for all versions.

Sorry,
Sylvain

On Tue, Jun 30, 2009 at 7:59 PM, Sylvain Gelly wrote:
> Hi,
>
> Olivier answered for the new version.
> On the downloadable version, I don't remember exactly (almost 2 years
> back now...), but I think Mogo will still pass if all the other moves
> are clearly loosing. So it should "understand" somehow Seki
> situations.
> If that is correct, the sentence is not completely accurate.
> It should more be:
> "MoGo never consider a pass unless you pass first or all other moves
> are obviously loosing the game."
>
> Sylvain
>
> On Wed, Jun 24, 2009 at 10:11 PM, Seth Pellegrino wrote:
>> Hello all,
>>
>> On http://www.lri.fr/~gelly/MoGo_Download.htm , under the FAQ section,
>> I found the bullet point:
>>
>> "MoGo continues playing after the game is over?": MoGo never consider
>> a pass unless you pass first. If you think the game is over, simply
>> pass.
>>
>> Is this still true? If so, how does MoGo deal with situations where
>> the best move is to pass (e.g. seki).
>>
>> Thanks,
>>
>> Seth Pellegrino
>> ___
>> computer-go mailing list
>> computer-go@computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGo and passing

[Sylvain Gelly]

Hi,

Olivier answered for the new version.
On the downloadable version, I don't remember exactly (almost 2 years
back now...), but I think Mogo will still pass if all the other moves
are clearly loosing. So it should "understand" somehow Seki
situations.
If that is correct, the sentence is not completely accurate.
It should more be:
"MoGo never consider a pass unless you pass first or all other moves
are obviously loosing the game."

Sylvain

On Wed, Jun 24, 2009 at 10:11 PM, Seth Pellegrino wrote:
> Hello all,
>
> On http://www.lri.fr/~gelly/MoGo_Download.htm , under the FAQ section,
> I found the bullet point:
>
> "MoGo continues playing after the game is over?": MoGo never consider
> a pass unless you pass first. If you think the game is over, simply
> pass.
>
> Is this still true? If so, how does MoGo deal with situations where
> the best move is to pass (e.g. seki).
>
> Thanks,
>
> Seth Pellegrino
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Incorporating a prior estimate

[Sylvain Gelly]

2009/5/1 Brian Sheppard :
> In reading Sylvain Gelly's thesis, it seemed that incorporating a prior
> estimate of winning percentage is
> very important to the practical strength of Mogo.
>
> E.g., with 1 trials, Mogo achieved 2110 rating on CGOS, whereas my
> program attempts to
> reproduce existing research and is (maybe) 1900 rating with 2 to 3
> trials. The use of a
> prior is an important difference, so I want to understand it more deeply.
>
> Some questions:
>
> 1) When you create a node, do you initialize
>
>     number of simulations = C
>     number of wins = C * PriorEstimate()
>
> where C is a constant > 0? In Sylvain's thesis, the optimal C = 50,
> suggesting that
> incorporating a prior estimate was the equivalent of 50 UCT-RAVE trials.
Yes, but for "number of RAVE simulations" and "number of RAVE wins".
I think the optimal range was between 20 and 50 (you can test values
in that range). The actual value certainly depends on your actual
prior.

> 2) Two variations were suggested. In one variation, the prior was
> incorporated into the UCT
> statistics of the node. In the other, the prior was incorporated into the
> RAVE statistics. Charts
> in the thesis do not confirm which was actually being measured. In some
> cases it appears to
> be the UCT version, but elsewhere it seems to be the RAVE version. Does
> anyone know
> what was really done?

Doing it on the RAVE statistics is what is working best.

> 3) Elsewhere I have seen information suggesting that Mogo initializes RAVE
> statistics to
> implement progressive widening. Does that conflict with the use of a prior
> for RAVE initialization,
> or is it in addition to the use of a prior for RAVE initialization?

Progressive widening and prior for RAVE initialization serve the same
purpose. The prior is maybe smoother but they should be more or less
equivalent in practice.

> 4) When creating a node, do you estimate the prior for that node , or for
> that node's children?

I estimated the prior for all move for that node (I stored the RAVE
values in the node, not in the children).

Sylvain

> Thanks in advance,
> Brian
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Fast ways to evaluate program strength.

[Sylvain Gelly]

On Wed, Apr 8, 2009 at 10:46 AM, Darren Cook  wrote:
>> End game is another issue. MC programs only aim on winning, so they
>> endgame is nor perfect in sense human would define it, but perfect
>> enough to win if the game is winnable.
>
> You can modify komi to get the human expert and MC program in agreement.
>
> This suggests how you could automate a set of endgame problems: run Mogo
> (or similar) with lots of time and keep increasing/reducing the komi
> until you get a sudden swing in winning probability (e.g. from 60% to
> 20% for side to play). That should tell you the komi to use, and at
> least one of the winning moves.
>
> To find alternative winning moves you'd need to have some way to tell
> Mogo, or whatever, it cannot choose the existing winning move you have,
> and must choose a different move. Once winning probability suddenly
> drops again it tells you there are no more winning moves left.
>
> If a program can generate the test set, why bother? I think it is useful
> because you can tune against it. E.g. if you give Mogo 120s per move to
> generate the test suite moves, then you tune until it can find the
> correct moves for the whole test suite on 1s per move.
>
> Tuning the endgame play is very important for MCTS search, because every
> playout always goes to the endgame. Strong endgame play in the playouts
> should make a program stronger at all stages of a game.
>
> What do you think? Is such a endgame problem suite useful?

What I did to generate a test suite was to make Mogo play against
itself (on 9x9, 10s per move) and stop the game when it thinks was
clearly won for one of the player. That created a few hundred end game
positions where the result were clear enough, and I used that test
suite to evaluate the playouts. It was not precise enough (or I did
not have enough positions?) to actual optimize details of the
playouts, but it could make the difference between a clearly
better/worse policy.
However, I don't think it would be suitable to test the strength of
the actual player, but only the playout policy.

Sylvain

> Darren
>
> --
> Darren Cook, Software Researcher/Developer
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
>                        open source dictionary/semantic network)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/blogs.html (My blogs and articles)
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Transpositions in Monte-carlo tree search

[Sylvain Gelly]

Hi Mattew,

I cannot answer for the current version of Mogo but I can for the one
1.5 years ago. Maybe it still holds.
We had a transposition table as it was designed like that from the
beginning. However the prior value of the node, was initialized when
the node was created and indeed was depending of the previous move
played in the current sequence.
In practice, I think it does not change much.

Sylvain

On Mon, Mar 30, 2009 at 11:36 PM, Matthew Woodcraft
 wrote:
> How are transpositions normally handled in monte-carlo tree search?
>
> I have been assuming that the natural thing would be to have a single
> shared node for each board position, so that simulations which reach the
> same position will use the same set of statistics (but when backing up
> the result, to only update the nodes for the simulation actually
> played).
>
> But I see in some of the Mogo papers that some of the contributions to
> the heuristic value of a node depend on the position of the previous
> move.
>
> So do MCTS programs not recognise transpositions at all? Or are the
> heuristics from the time when the node was first created allowed to
> stand, no matter what the simulation route is next time?
>
> -M-
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

On Sun, Feb 8, 2009 at 1:42 PM, Petr Baudis  wrote:

> On Sat, Jan 17, 2009 at 08:29:32PM +0100, Sylvain Gelly wrote:
> > A small point: in "PlayoutOutTree", just after "if
> > (!played.AlreadyPlayed(move)) {", there should have a
> "played.Play(move)".
> > I believe it does not change the final result (as the check is also done
> in
> > the backup, and the move played in the backup), but I simply forgot that
> > line (that should make moves_played_out_tree smaller).
> >
> > To avoid confusion, I repost the pseudo code with that correction (and
> > hoping the indentation is not broken by the email editor once again).
>
> Thank you so much for this! I have switched my RAVE implementation to
> this formula and the bot has gotten noticeably stronger, though I
> apparently still have some bugs to chase, since it seems to have trouble
> considering strongest opponent's responses and frequently focuses on
> unreasonable opponent's replies instead of the obvious (e.g. keeping a
> group of stones in atari). Maybe I need better prior hinting...
>
> I have few questions. Of course, please feel free to skip questions
> about particular constants if you feel that's giving away too much. :-)
>
> > ChooseMove(node, board) {
> >   bias = 0.015  // I put a random number here, to be tuned
> >   b = bias * bias / 0.25
>
> Maybe it would be cleaner to define b = 1 / rave_equiv, where rave_equiv
> is the number of playouts RAVE is thought to be equivalent of? Or is the
> meaning of this constant actually different?
>

The meaning is supposed to be the difference between the expected value of
AMAF and the expected value of the tree. But at that point it is just a
constant, so I am not sure there is a "good" interpretation.


>
> What value works best for people? I did not do much tuning yet, but I
> use b=1/3000. I see Fuego uses b=1/5000. (This example b=1/.)


I believe the actually value depends on the other parts of your
implementation, namely the playouts, the prior you use in the tree and the
exploration term (there was none in the pseudo code I posted, but you might
use one).


>
>
> >   best_value = -1
> >   best_move = PASSMOVE
> >   for (move in board.allmoves) {
> > c = node.child(move).counts
> > w = node.child(move).wins
> > rc = node.rave_counts[move]
> > rw = node.rave_wins[move]
> > coefficient = 1 - rc / (rc + c + rc * c * b)
> > value = w / c * coef + rw / rc * (1 - coef)  // please here take care
> of
> > the c==0 and rc == 0 cases
> > if (value > best_value) {
> >   best_value = value
> >   best_move = move
> > }
> >   }
> >   return best_move
> > }
>
> I have two questions here:
>
> * Is the FPU concept abandoned? Or what values are reasonable? It seems
>  to me 1.0, which is usually recommended, is obviously too big here
>  since that's the upper bound of the value already. So far I have tried
>  0.6 and 0.7 but both just make my bot slightly weaker.



>
> * How to accomodate prior knowledge? (I'm using grand-parent heuristics,
>  atari liberties, and few patterns.) Do you use it to fill normal
>  counts, RAVE values or both? What count values work best for you?
>  I have settled on 50 playouts.


The FPU concept is here replaced by the prior value. I used
node.rave_wins[move]
and node.rave_counts[move] when the node is initialized. If you don't want
to use go knowledge, you can initialize those values to something like 7 and
14 respectively. Grand-parent heuristics did not work at all in my
experiments (was even very bad). The heuristics I was using were:
  - save a chain (positive prior)
  - self atari (negative prior)
  - match a simple 3x3 pattern (hane, cut, and a few others I don't
remember) (positive prior).

For node.rave_counts[move], 50 seems a little high. I think I was using
values around 15, but it was not very sensitive (50 was working almost as
well as 15). I give those numbers from memory, they may be quite off.

Sylvain

>
>
> --
>Petr "Pasky" Baudis
> The average, healthy, well-adjusted adult gets up at seven-thirty
> in the morning feeling just terrible. -- Jean Kerr
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Hi Issac,
You should be more in the range of +200-300 ELO, at least with pattern based
playouts.

Sylvain

2009/2/1 Isaac Deutsch 

> By the way, I got about 75 ELO points (1650->1720) with light playouts out
> of RAVE. Do you think this is in the expected range? It's not really similar
> to the 20%->60% win rate rise vs. GnuGo described in some papers...
>
> > At the moment I'm also tuning the bias in the range 0.001-0.1. Given
> > uniformly random (light) playouts, is the bias expected to be bigger than
> > with
> > heavy playouts, meaning the constant has to be bigger aswell?
>
> Cheers, ibd
> --
> Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> http://www.gmx.net/de/go/multimessenger01
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

On Fri, Jan 30, 2009 at 9:29 AM, Magnus Persson wrote:

> Quoting Sylvain Gelly :
>
>  On Wed, Jan 28, 2009 at 10:01 PM, Isaac Deutsch  wrote:
>>
>>  And a final question: You calculate the (beta) coefficient as
>>> c = rc / (rc+c+rc*c*BIAS);
>>> which looks similar to the formula proposed by David Silver (If I recall
>>> his name correctly). However, in his formula, the last term looks like
>>> rc*c*BIAS/(q_ur*(1-q_ur))
>>> Is it correct that we could get q_ur from the current UCT-RAVE mean
>>> value,
>>> and that it is used like that?
>>>
>>
>>
>> Yes the formula looks very similar (David proposed that formula to me in
>> the
>> beginning of 2007). However my implementation did not contain
>> the (q_ur*(1-q_ur) factor, that I approximated by a constant, taking q=0.5
>> so the factor=0.25.
>> I did not try the other formula, maybe it works better in practice, while
>> I
>> would expect it is similar in practice.
>>
>
> Valkyria uses an even more complicated version of what David Silver
> proposed (I really did not understand it so I came up with something that
> looked plausible to me that actually estimated the bias for each candidate
> move rather than assuming it constant).
>
> When Sylvain proposed this simple version I tested that version against my
> own interpretation. On 9x9 my complicated version might have a win rate 3%
> better than the simple version for 3 data points (700 games each) near the
> maximum. The standard error according to twogtp is 1.9.
>
> On 19x19 I got results where there no difference at all but with much
> higher uncertainty because there was not many games played.


Did you try to tune the bias constant at all or just took the one I posted?
I wrote it from memory and I believe it is in the range of possibly good
values, but it is certainly not optimal, I can be off by a significant
factor in both directions.


> But the term is important for sure, the constant BIAS used should be larger
> than 0 but you should be careful to not set it too high. For Valkyria the
> 0.015 value Sylvain posted here worked fine. But if it is higher for example
> 0.15 leads to bad performance on 9x9 and catastrophic performance on 19x19.
> Initially I thought this parameter should be something like 1 and that was
> completely wrong. I was just lucky to get it right, just by visual
> inspection of the search behavior when I played around with the parameter.


The bias can't possibly be 1 because by definition it is the difference
between the expected value of the normal tree search and the expected value
of AMAF. As those two values are in [0,1] anyway, the bias is certainly not
1, and in most cases very small.

>
>
> The reason is that the bias term of the denominator should be close to zero
> initially is to allow AMAF to have strong impact on the search but at some
> point (which is delayed by having a small BIAS constant) there is a quick
> shift towards using the real win rate instead.
>
> -Magnus
>
>
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

On Wed, Jan 28, 2009 at 10:01 PM, Isaac Deutsch  wrote:

> Hi again ;)
>
> I found some time to actually implement this stuff. And, this has raised
> some small questions. In this part of the code:
>
>  for (j = index; j < moves_played_in_tree.size(); j += 2) {
> //stuff
>   }
>  for (j = 0; j < moves_played_out_tree.size(); ++j) {
> //more stuff
>
>// If it is either not the right color or the intersection is
>// already played we ignore that move for that node
>if (move < 0 || already_played.AlreadyPlayed(move)) continue
>
>already_played.Play(move)
> //stuff
>  }
>
> 1. Shouldn't the first loop start at j=index+1? Starting at j=index would
> mean that the RAVE value of the node is updated with the move of the node
> itself, wouldn't it? It makes more sense to me to actually start at the
> first child of the node that is being back-upped. Correct me if I'm wrong.

No, you need to update the RAVE value of the node for the first move (move
taken in the position of the node itself). So it is j=index, and that is
important to make the algorithm work.


>
> 2. Shouldn't the order in the second loop be:
> -if (already played): continue;
> -update already played;
> -if (wrong color): continue;
> Otherwise, moves that are the wrong color don't get counted as already
> played (because they never get updated). I'm not sure if it makes a
> difference in this case because you check in the playouts, too, but maybe
> it does.


I think it is ok like that because indeed the check is already done in the
playout. The "already_played.Play(move)" is actually also unnecessary in the
second loop (not really rechecked as I speak, but I think so as far as I
remember).


> And a final question: You calculate the (beta) coefficient as
> c = rc / (rc+c+rc*c*BIAS);
> which looks similar to the formula proposed by David Silver (If I recall
> his name correctly). However, in his formula, the last term looks like
> rc*c*BIAS/(q_ur*(1-q_ur))
> Is it correct that we could get q_ur from the current UCT-RAVE mean value,
> and that it is used like that?


Yes the formula looks very similar (David proposed that formula to me in the
beginning of 2007). However my implementation did not contain
the (q_ur*(1-q_ur) factor, that I approximated by a constant, taking q=0.5
so the factor=0.25.
I did not try the other formula, maybe it works better in practice, while I
would expect it is similar in practice.

Sylvain

>
>
> Regards,
> Isaac Deutsch
> --
> Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> http://www.gmx.net/de/go/multimessenger
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

2009/1/21 Olivier Teytaud 

>
> Of course you can do put much more clever prior if you are a player and
>> know the subtleties of the game.
>>
>
> E.g. patterns extracted from databases - but it's not enough, carefully
> tune the coefficients for "empty triangles" (important!) and various other
> importants patterns/rules (don't just keep the empirical probabilities from
> datasets as coefficients). I'm afraid the coefficients are very
> implementation-dependent unless the bandit and the random player are
> specified with
> a lot of details.
>
> You can put an exploration term, but the cases where it is needed are rare.
>> I did a lot of experiments on that, and even at long thinking time, no
>> exploration term was always better (statistically).
>>
>
> Well, now mogo has an exploration term - but not at all UCB-like.
>

I was talking about times where I was still there ... ages ago :)

Sylvain
___
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?

[Sylvain Gelly]

Hi,

I did not mention here the prior initialization that is done in each node.
When you create a node, you can look at all possible move and if a pattern
matches (the exact same as in the playout) you initialize rw and rc to 14.
If the move saves a capture (same as in the playout), same initialization,
rw and rc to 14. If it is a self atari, you initialize rw to 0 and rc to 14.
Else you initialize rw to 7 and rc to 14.
Of course you can do put much more clever prior if you are a player and know
the subtleties of the game.

You can put an exploration term, but the cases where it is needed are rare.
I did a lot of experiments on that, and even at long thinking time, no
exploration term was always better (statistically).

Sylvain

2009/1/21 Mark Boon 

>
> On Jan 21, 2009, at 10:23 AM, Magnus Persson wrote:
>
>  Quoting Thomas Lavergne :
>>
>>   - the best play is a good only if played immediatly and very bad if
>>>   played later in the game :
>>>  - the first playout for this play resulted in a lost.
>>> score and RAVE score will be very low and this play will never be
>>> considered again until a very long time.
>>>
>>
>>
>> You raise an interesting concern.
>>
>> The simple solution to your question is to add an exploration term using
>> UCT for example. Then it becomes an empirical question what parameter for
>> exploration gives the strongest play. My experience is that the best
>> parameter is so small it can be set to zero.
>>
>
> Well, empirically, when I set the exploration component to zero it starts
> to play a lot worse. Like I wrote: the winning percentage drops to 24% vs.
> the same program with the exploration component, which is a huge difference.
>
> So if you have a different experience, you must have something else that
> overcomes this hurdle that's not part of a simple MCTS-RAVE implementation.
> I'd be very interested to learn what that is. Sylvain didn't take the bait
> ;-)
>
> Mark
>
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] RAVE and memory allocation considerations

[Sylvain Gelly]

Hi,
You should really look into never deallocate memory (by calling delete/free)
but keeping it in some memory pool. I did that for the main objects that you
deal with: nodes and "small vectors" (the one you create on the fly to keep
the moves that have been played in the playout). It really speeds up things
a lot.

Apart from that, I did the same as you, creating the thread after the
genmove and joining them at the end of the thinking time.

Sylvain

2009/1/20 Isaac Deutsch 

> Thanks again for your pseudo-implementation, Sylvain.
>
> At the moment I have a program that uses plain MCTS. With every genmove, it
> creates a certain number of
> threads (2), gives them some starting data, and lets them think for a
> while, then rejoins them, extracting the
> best move. During the thinking, the threads build a normal UCT tree. At the
> beginning, they allocate a
> certain number of nodes (100'000 as of now) and delete the nodes when
> thinking has finished.
>
> To add RAVE to this, each node would need up to size*size additional values
> for RAVE. I thought about
> allocating this memory when children are added (which seems logical to me),
> and deleting it also at the end
> of the thinking time. However, this seems (I don't have any data) *slow* to
> me , to allocate up to ˜50 MB of
> RAM every time, then destroying it again afterwards.
>
> Do you think the spent allocating could be critical?
> What do you think would be a good way to deal with this? I think to avoid
> the continuous allocation/deallocation,
> it's necessary to keep the threads running instead of creating/joining them
> for each genmove. This would
> allow them to only have to alloc/dealloc when the board size is changed.
>
> Regards,
> Isaac
> --
> Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> http://www.gmx.net/de/go/multimessenger
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Good catch :)Indeed it makes no sense with the "*", sorry...

Sylvain

2009/1/17 Magnus Persson 

> I think I found a bug in ChooseMove
>
> Quoting Sylvain Gelly :
>
> coefficient = 1 - rc * (rc + c + rc * c * b)
>>
>
> I think this has to be
>
> coefficient = 1 - rc / (rc + c + rc * c * b)
>
> thus when c is 0 (initially) the coefficient is 0
> when c goes towards infinity the coefficent goes 1
>
> which is how this function should behave.
>
> Magnus
>
> --
> Magnus Persson
> Berlin, Germany
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Hi Issac,
You are welcome, and I am happy there is finally a clearer of implementing
RAVE out there. I believe I should have done it much earlier, sorry for
that, but "better late than never", no? :)

Best,
Sylvain

2009/1/17 Isaac Deutsch 

> > Hi,
> >
> > Sorry for the slow reply.
>
> Hi
>
> I'd prefer quality over speed anytime. ;)
> Your pseudo code is excellent and helped me to understand some of the
> trickier things. Thanks again!
> I think I will now be able to implement my own version. :)
>
> Regards,
> Isaac
> --
> Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> http://www.gmx.net/de/go/multimessenger
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Hi Mark,
For the first difference you mention, as far as I remember it makes a small
but significant difference and is one of the main reason I was talking about
"tricky details".
For the second difference, I also don't want to "count a move if the
opposite color played on that point first", and, unless I am mistaken, I
indeed don't count them in the part of the playout which is outside the
tree.
However you are right for the part inside the tree, due to the "j+=2". I am
a little confused and now believe it should not be a j+=2 but a j++,
updating the "already_played" map for each move inside the tree during the
backup, but doing the backup only once every too moves (to match the color).

It may be a bug in what I proposed, I cannot test it anymore. However, what
I am sure about is that this "j+=2" is what I was using and gave very good
results. If what you point out is indeed a bug and makes a difference, then
it can only be even better :). I prefer not modifying the pseudo code I
posted until someone verifies it becomes better.

Thanks,
Sylvain

2009/1/17 Mark Boon 

> Thanks for taking the time Sylvain. I took a quick look to see how your
> pseudo-code compared to the reference implementation I made. There are a few
> small differences, and I think the place(s) where I deviated is exactly what
> confused Daniel Waeber.
>
> The first difference is that when I check whether a point has been played,
> I always start from the position of the root-node, whereas you start from
> the position of the node where the moves_played_in_tree is played. The
> second difference is I also don't count a move if the opposite color played
> on that point first. The result is I only need to compute the alreadyPlayed
> map once (in my code these are called weightMap and colorMap, I need two
> maps because I use decreasing weights) instead of computing it at each step
> back up in the tree.
>
> The only time these 'deviations' make a difference is in case of ko and
> ishi-no-shita. When I have a little spare time I'll check to see if this
> actually makes a difference in playing strength. If there's any noticeable
> difference I'll try to modify the code in my reference implementation to
> reflect the 'correct' method.
>
> Mark
>
>
>
> On Jan 17, 2009, at 11:48 AM, Sylvain Gelly wrote:
>
>  Hi,
>>
>> Sorry for the slow reply.
>> After those discussions, I figured out that pseudo code was the
>> fastest clear and not ambiguous way to describe how to precisely
>> implement the algorithm. I needed to find some time to write it.
>> Note that I did not write only the backup phase because to clearly
>> describe the backup you have to see the playouts as well. I also
>> describe the choice of the best move.
>> Note also the fact that the backup from the moves in the tree and from
>> the moves out of the tree is different. That is the somehow more
>> tricky part to check that a move has not been already played (that is
>> different for each node in the tree and we obviously don't want to
>> keep a vector of already played moves for each node).
>>
>> Please forgive the mistakes that are in that code, of course I did not
>> make any test, and it has been quite a long time I am not in the
>> computer go trip anymore :). Please correct any mistake,
>> I hope it makes things clearer.
>>
>> Best,
>> Sylvain
>>
>> class AmafBoard {
>>  AmafBoard() {
>>   offset = 0
>>   fill(alread_played, 0)
>>  }
>>  Clear() {
>>   offset++;
>>  }
>>  Play(move) {
>>   already_played[move] = offset
>>  }
>>  AlreadyPlayed(move) {
>>   return already_played[move] == offset
>>  }
>>  vector already_played
>>  int offset
>> }
>>
>> ChooseMove(node, board) {
>>  bias = 0.015  // I put a random number here, to be tuned
>>  b = bias * bias / 0.25
>>  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
>> }
>> PlayoutInTree(board, moves_played_in_tree, nodes_seen_in_tree) {
>>  node = tree.root
>>  while (node) {
>>   move = ChooseMove(node, board)
>>   moves_played_

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

[Sylvain Gelly]

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

Sylvain


class AmafBoard {
  AmafBoard() {
offset = 0
fill(alread_played, 0)
  }
  Clear() {
offset++;
  }  Play(move) {
 already_played[move] = offset
  }
  AlreadyPlayed(move) {
 return already_played[move] == offset
  }
  vector already_played
  int offset
}

ChooseMove(node, board) {
  bias = 0.015  // I put a random number here, to be tuned
  b = bias * bias / 0.25
  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
}


PlayoutInTree(board, moves_played_in_tree, nodes_seen_in_tree) {
  node = tree.root
  while (node) {
move = ChooseMove(node, board)
moves_played_in_tree.append(move)
nodes_seen_in_tree.append(node)
board.PlayMove(move)
node = node.child(move)
  }
}


PlayoutOutTree(board, AmafBoard played, moves) {
  int pass = 0
  while (pass < 2) {
move = board.ChooseMoveAndPlay()
if (move == PASSMOVE) {
  pass ++
  continue
} else {
  pass = 0
}
if (!played.AlreadyPlayed(move)) {
  played.Play(move)
  if (!board.last_move_was_black()) {
move = -move
  }
  moves.append(move)
}
  }
  return board.black_wins()
}


BackupNode(node, index, black_wins, moves_played_in_tree,
moves_played_out_tree, already_played) {
  already_played.Clear()
  win = node.is_black_to_play ? black_wins : !black_wins
  // normal backup
  node.wins += win
  node.counts ++
  // rave backup
  for (j = index; j < moves_played_in_tree.size(); j += 2) {
move = moves_played_in_tree[j]
if (already_played.AlreadyPlayed(move)) continue
already_played.Play(move)
node.rave_wins[move] += win
node.rave_counts[move] ++
  }
  for (j = 0; j < moves_played_out_tree.size(); ++j) {
move = moves_played_out_tree[j]
if (!node.is_black_to_play) move = -move

// If it is either not the right color or the intersection is
// already played we ignore that move for that node
if (move < 0 || already_played.AlreadyPlayed(move)) continue

already_played.Play(move)
node.rave_wins[move] += win
node.rave_counts[move] ++
  }
}


Backup(black_wins, nodes_seen_in_tree, moves_played_in_tree,
moves_played_out_tree, already_played) {
  for (i = 0; i < nodes_seen_in_tree.size(); ++i) {
node = nodes_seen_in_tree[i]
BackupNode(node, i, black_wins, moves_played_in_tree,
moves_played_out_tree, already_played)
  }
}


OneIteration(board_position, AmafBoard already_played) {
  board = board_position.Copy()
  already_played.Clear()

  vector moves_played_in_tree
  vector nodes_seen_in_tree
  PlayoutInTree(&board, &moves_played_in_tree, &nodes_seen_in_tree)

  vector moves_played_out_tree
  bool black_wins = PlayoutOutTree(&board, &already_played,
 &moves_played_out_tree)
  Backup(black_wins, nodes_seen_in_tree, moves_played_in_tree,
      moves_played_out_tree, &already_played)
}

2009/1/17 Sylvain Gelly :
> Hi,
>
> Sorry for the slow reply.
> After those discussions, I figured out that pseudo code was the
> fastest clear and not ambiguous way to describe how to precisely
> implement the algorithm. I needed to find some time to write it.
> Note that I did not write only the backup phase because to clearly
> describe the backup you have to see the playouts as well. I also
> describe the choice of the best move.
> Note also the fact that the backup from the moves in the tree and from
> the moves out of the tree is different. That is the somehow more
> tricky part to check that a move has not been already played (that is
> different for each node in the tree and we obviously don't want to
> keep a vector of already played moves for each node).
>
> Please forgive the mistakes that are in that code, of course I did not
> make any test, and it has been quite a long time I am not in the
> computer go trip anymore :). Please correct any mistake,
> I hope it makes things clearer.
>
> Best,

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

[Sylvain Gelly]

Hi,

Sorry for the slow reply.
After those discussions, I figured out that pseudo code was the
fastest clear and not ambiguous way to describe how to precisely
implement the algorithm. I needed to find some time to write it.
Note that I did not write only the backup phase because to clearly
describe the backup you have to see the playouts as well. I also
describe the choice of the best move.
Note also the fact that the backup from the moves in the tree and from
the moves out of the tree is different. That is the somehow more
tricky part to check that a move has not been already played (that is
different for each node in the tree and we obviously don't want to
keep a vector of already played moves for each node).

Please forgive the mistakes that are in that code, of course I did not
make any test, and it has been quite a long time I am not in the
computer go trip anymore :). Please correct any mistake,
I hope it makes things clearer.

Best,
Sylvain

class AmafBoard {
  AmafBoard() {
offset = 0
fill(alread_played, 0)
  }
  Clear() {
offset++;
  }
  Play(move) {
already_played[move] = offset
  }
  AlreadyPlayed(move) {
return already_played[move] == offset
  }
  vector already_played
  int offset
}

ChooseMove(node, board) {
  bias = 0.015  // I put a random number here, to be tuned
  b = bias * bias / 0.25
  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
}
PlayoutInTree(board, moves_played_in_tree, nodes_seen_in_tree) {
  node = tree.root
  while (node) {
move = ChooseMove(node, board)
moves_played_in_tree.append(move)
nodes_seen_in_tree.append(node)
board.PlayMove(move)
node = node.child(move)
  }
}
PlayoutOutTree(board, AmafBoard played, moves) {
  int pass = 0
  while (pass < 2) {
move = board.ChooseMoveAndPlay()
if (move == PASSMOVE) {
  pass ++
  continue
} else {
  pass = 0
}
if (!played.AlreadyPlayed(move)) {
  if (!board.last_move_was_black()) {
move = -move
  }
  moves.append(move)
}
  }
  return board.black_wins()
}

BackupNode(node, index, black_wins, moves_played_in_tree,
moves_played_out_tree, already_played) {
  already_played.Clear()
  win = node.is_black_to_play ? black_wins : !black_wins
  // normal backup
  node.wins += win
  node.counts ++
  // rave backup
  for (j = index; j < moves_played_in_tree.size(); j += 2) {
move = moves_played_in_tree[j]
if (already_played.AlreadyPlayed(move)) continue
already_played.Play(move)
node.rave_wins[move] += win
node.rave_counts[move] ++
  }
  for (j = 0; j < moves_played_out_tree.size(); ++j) {
move = moves_played_out_tree[j]
if (!node.is_black_to_play) move = -move
// If it is either not the right color or the intersection is
already played we ignore that move for that node
if (move < 0 || already_played.AlreadyPlayed(move)) continue

already_played.Play(move)
node.rave_wins[move] += win
node.rave_counts[move] ++
  }
}

Backup(black_wins, nodes_seen_in_tree, moves_played_in_tree,
moves_played_out_tree, already_played) {
  for (i = 0; i < nodes_seen_in_tree.size(); ++i) {
node = nodes_seen_in_tree[i]
BackupNode(node, i, black_wins, moves_played_in_tree,
moves_played_out_tree, already_played)
  }
}
OneIteration(board_position, AmafBoard already_played) {
  board = board_position.Copy()
  already_played.Clear()

  vector moves_played_in_tree
  vector nodes_seen_in_tree
  PlayoutInTree(&board, &moves_played_in_tree, &nodes_seen_in_tree)

  vector moves_played_out_tree
  bool black_wins = PlayoutOutTree(&board, &already_played,
&moves_played_out_tree)
  Backup(black_wins, nodes_seen_in_tree, moves_played_in_tree,
moves_played_out_tree, &already_played)
}
___
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?

[Sylvain Gelly]

2009/1/10 Isaac Deutsch 

> Hi Sylvain,
>
> I think it's starting to make sense now. :-)
>
>
> > Sorry to be unclear. I wish we have a white board where we could discuss
> > and
> > that would sorted out in a few minutes :).
>
> Several results turn up in a google search ;p
> http://www.google.com/search?q=online+white+board
>
>
> > What I tried to mean is that when you do the backup for a given node, you
> > look at the part of the playout that happen after that node (including
> > that
> > node), and you do a normal AMAF backup for that part of the playout.
> > Does it make sense?
> > I hope we make progress and I am not making things more confusing :).
> > I should write a pseudo code I guess, but for today I am too lazy :).
> >
> > Sylvain
>
> I tried putting this into pseudo code, but it already looks like C. ;p
> http://pastie.org/357231
> If you could look at it, I would be most grateful.

It sounds good but it seems to lack the check of whether a given move is
first played in a given intersection. When you add that, it because a little
more tricky to update in the tree. You also update the value of each move
independently of the color, i.e. a position in which it is black turn will
be update with white moves. You should restrict the update.

Hopes that helps,
Sylvain


>
>
> -Isaac
>
> --
> Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> http://www.gmx.net/de/go/multimessenger
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Hi Isaac,

2009/1/9 Isaac Deutsch 

> Hi Sylvain,
>
> Thanks for your quick answer.
>
>
> > in a nutshell RAVE is basically AMAF adapted for Monte Carlo Tree Search.
> > The original paper describing it is
> > http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf and a
> > paper for "broader audience" can be found here:
> > http://www.lri.fr/~gelly/paper/MoGoNectar.pdf (the picture you posted
> > comes
> > from that paper).
>
> Yes, I took a screenshot. Another paper I looked at was
> http://www.lri.fr/~teytaud/eg.pdf
>
>
> > There are two important parts in the algorithms: the backup and the use
> of
> > the RAVE value. The second is the hardest to tune and to make it right.
> > The
> > proposed way of using the values in the original paper is not optimal
> > (while
> > already very useful). A much better way (especially in 19x19) has been
> > described on that list by David Silver.
>
> Do you mean the calculation of the factor beta that the RAVE value is
> multiplied with?
>
>
> > For the backup (as it is your original question), for each node traversed
> > by
> > the simulation, back up the values exactly as it would be done in AMAF
> > *if*
> > the playout began at that node. Note that I call playout the whole
> > simulation starting from the root and going to the end of the game.
>
> I see what you mean with the playout going from the root to the end of the
> game.
> How do you mean "back up the values ... if the playout began at that node"?
> Since every playout starts
> at the root (in my program, the root is the (previous) move of the opponent
> player), wouldn't that mean
> only updating the RAVE statistics for the root? I'm sorry if this question
> sounds stupid.


Sorry to be unclear. I wish we have a white board where we could discuss and
that would sorted out in a few minutes :).
In the quote of my sentence you did not put the "as" of the "as if the
playout began..." (the "as" and the "if" where separated by a part of the
sentence, which did not make things clearer, sorry...)
What I tried to mean is that when you do the backup for a given node, you
look at the part of the playout that happen after that node (including that
node), and you do a normal AMAF backup for that part of the playout.
Does it make sense?


> >   - Count only moves that happen after the node.
>
> How do you measure if a move is "after" another move? The amount of moves
> taken from the root (i.e. the depth of the node in the tree/the playout)? Or
> do you mean that the node is effectively a (grand-grand-...) father of the
> move, so the playout has visited that node?

By "after" I mean after in the sequence.
If the playout is E5, A7, C4, D8, by "after" I mean that C4 is after E5, but
not after D8.

I hope we make progress and I am not making things more confusing :).
I should write a pseudo code I guess, but for today I am too lazy :).

Sylvain

> I hope it will help you write a correct implementation. Don't hesitate to
> > ask for precisions.
>
> I really appreciate your help.
>
> -ibd
> --
> Pt! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
> http://www.gmx.net/de/go/multimessenger
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Hi Isaac,
in a nutshell RAVE is basically AMAF adapted for Monte Carlo Tree Search.
The original paper describing it is
http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf and a
paper for "broader audience" can be found here:
http://www.lri.fr/~gelly/paper/MoGoNectar.pdf (the picture you posted comes
from that paper).

I think your description of RAVE is not completely correct, or at least I
don't understand it completely :). If I understand that sentence "only the
siblings of the last node in the tree are updated accordingly", then it is
wrong.

There are two important parts in the algorithms: the backup and the use of
the RAVE value. The second is the hardest to tune and to make it right. The
proposed way of using the values in the original paper is not optimal (while
already very useful). A much better way (especially in 19x19) has been
described on that list by David Silver.
For the backup (as it is your original question), for each node traversed by
the simulation, back up the values exactly as it would be done in AMAF *if*
the playout began at that node. Note that I call playout the whole
simulation starting from the root and going to the end of the game.

Things you have to take care about, for each node, including the root,
including the last node in the tree (most of them obvious, but believe it is
really easy to forget small details and get something totally useless):
  - Count only moves that happen after the node.
  - Count only a move if it is played first on the intersection.
Be careful with captures, especially if they occur within the tree. It is
really easy to mess up the statistics.
  - Count only a move if it is the same color of the node (if in the
position of the node, black is to play, count only black moves for that
node)
  - Count all moves that happen after the node, including those happening
within the tree, and including the move that happen just after the node.

I hope it will help you write a correct implementation. Don't hesitate to
ask for precisions.

Sylvain

2009/1/9 Isaac Deutsch 

> I'm a bit confused about the difference between AMAF and RAVE (if there's
> one).
> As far as I understand, with AMAF, you sample in each playout (after it
> leaves
> the tree) the moves played (by both players), but only the first move at
> any
> position, then you reward all moves played either by a win or loss,
> depending on
> their colors.
>
> I tried comparing this to RAVE, as described in many papers. There might be
> multiple definitions of RAVE, but the one that seems the most clear to me
> is
> this one (picture used because of math stuff):
>
> http://img352.imageshack.us/img352/443/bild1pb3.png
>
> Is it correct that with RAVE, after a playout (after the tree), only the
> siblings of the last node in the tree are updated accordingly? The main
> difference to AMAF would be that instead of a single array with values of
> AMAFsumReward and AMAFnumPlayed, each node keeps for each of its children
> separate variables that hold these values. When a playout is finished, only
> the
> values of these children are updated instead of the single array.
>
> I hope you're able to make any sense out of this, sometimes a text can be
> confusing when the writer is confused. ;p
>
> Cheers, ibd
> --
> Sensationsangebot verlängert: GMX FreeDSL - Telefonanschluss + DSL
> für nur 16,37 Euro/mtl.!* http://dsl.gmx.de/?ac=OM.AD.PD003K1308T4569a
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Monte-Carlo Tree Search reference bot

[Sylvain Gelly]

What I did (was a "long" time ago, I don't know if it is still used in
Mogo), is to compute the m best moves every so often and most of the
time just do the max over those m moves.
m was on the order of 5, and "every so often" was an increasing
function like sqrt or log (I don't remember).
That speeds up quite a lot (when the max becomes the bottleneck), and
if you tune the parameters well you almost don't loose any strength at
a fixed number of playouts.

Sylvain

2008/12/3  <[EMAIL PROTECTED]>:
> There is another speedup trick that might interest you. IIRC Lukasz Lew came
> up with it, but I forget what he called it. After calculating the selected
> move for an internal node (going through UCT and RAVE and whatnot) store
> that move. Then, for the next N visits to that node (where N is 5 or 10 or
> so), just repeat that move without having to calculate what the move would
> be.
>
> - Dave Hillis
>
> -Original Message-
> From: Mark Boon <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Tue, 2 Dec 2008 11:17 pm
> Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot
>
> I have made some minor performance improvements and this is as far as I
> intend to take this particular project. I might make some small changes if
> necessary, but most likely I'll leave this largely unchanged from now.
>
> I had set myself as an arbitrary goal that it should do at least 20K
> playouts. But with real liberties, AMAF and a RAVE formula I got stuck in
> the 16K-17K range. According to my profiler that is mostly due to the
> expensive formula used to compare nodes, where it says it spends 25% of
> total time. The formula I'm using is:
>
>   beta * (virtual-win-ratio + RAVE) + (1-beta) * (win-ratio + UCT)
>
>   beta = 1 - log(parent-visits) / 20
>   UCT = exploration-factor *sqrt( log(parent-visits) / (nr-visits+1) )
>   RAVE = exploration-factor *sqrt( log(parent-visits) /
> (nr-virtual-visits+1) )
>
> There are probably quite a few possibilities still to tune this program with
> regards to playing strength and performance. But I felt it doesn't help to
> obscure the implementation by too many details.
>
> The implementation of the search algorithm was entirely game-independent,
> until I introduced AMAF. I didn't see how to fix that, as there's no way
> getting around that it's based on the fact that a move is represented by a
> single coordinate, which is mapped to an array to store the statistical
> values. But strip the AMAF part, which is a block of 30 odd lines of code,
> and I think it can be used for other games basically as-is. I did this not
> because I ever see myself program another game, but because in my experience
> in doing so I get a cleaner separation between modules.
>
> At 2,000 playouts, it's still quite a bit weaker than the plain MC-AMAF
> refbot. It wins only about 33%. But that's probably because the 1,000-2,000
> playouts range is the sweet-spot for that particular type of playing engine.
> It doesn't scale from there, whereas the MCTS ref-bot only just gets warmed
> up with 2,000 playouts.
>
> This leads me to a question. I suppose it might be of some interest to put
> this bot up on CGOS. But what parameters to use? The main one being the
> number of playouts, naturally.
>
> Mark
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
> 
> Tis the season to save your money! Get the new AOL Holiday Toolbar for money
> saving offers and gift ideas.
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] What was the specific design of the Mogo version which beat the pro...

[Sylvain Gelly]

C++ on linux (with a port on windows using cygwin libraries for the binary
release)

Sylvain

2008/8/13 steve uurtamo <[EMAIL PROTECTED]>

> > And what language/platform is Mogo written in; C/C++, Java, Assembly,
> PHP,
> > etc.?
>
> This made coffee spray out of my nose (PHP).
>
> I think that C is most likely, based upon how they parallelized it.  Did
> you
> read the list posting that mentioned (briefly) how they scaled it up?
>
> s.
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Correction in AGA eJournal...

[Sylvain Gelly]

> the mistaken comment (9 stones in a year, computer superiority real soon)
> is getting repeated a huge number of times.
>

As one of my computer science teacher said: "if your editor has the
copy/paste feature, throw it away".

It obviously applies to programming and apparently to publication as well :)

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

Re: [computer-go] What Do You Need Most?

[Sylvain Gelly]

>
> You can download for free an "old" version of MoGo (which reached 2k on KGS
>> on a 4 CPU machine) at:
>>
>> 
>> >http://www.lri.fr/~gelly/MoGo_Download.htm
>>
>
> the exe just sits there. iirc, i need some sort of gui ? can you tell me
> what that is?
>
Yes you need some sort of gui. In the section "Installation and use
instructions" I give some name and links to some available gui. Did you try
the 2 first?
Drago gives specific instructions for MoGo at:
http://www.godrago.net/Engines.htm
GoGui should not be more difficult to use either.

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

Re: [computer-go] What Do You Need Most?

[Sylvain Gelly]

2008/7/28 Ray Tayek <[EMAIL PROTECTED]>

> At 07:53 PM 7/27/2008, you wrote:
>
>> The traditional programs are around 10 kyu, but the new ones are 2 to 4
>> kyu,
>> at least on KGS.  I've seen some handicap games against dan players that
>> are
>> consistent with these ratings.
>>
>
> wow. that's impressive. can one buy these or just play the on kgs?


You can download for free an "old" version of MoGo (which reached 2k on KGS
on a 4 CPU machine) at:
 http://www.lri.fr/~gelly/MoGo_Download.htm

Enjoy,
Sylvain


>
>  It wouldn't surprise me to see 1 dan from an MC program before 2010,
>> running
>> on an 8 processor mainstream system.
>>
>> David
>>
>
> 1-dan in two years? i must give your opinion a lot a weight, but i remain
> skeptical.
>
> how strong will the next version of manyfaces be? (and when can i buy it).
>
>
>
>  > -Original Message-
>> > From: [EMAIL PROTECTED] [mailto:computer-go-
>> > [EMAIL PROTECTED] On Behalf Of Ray Tayek
>> > Sent: Sunday, July 27, 2008 7:09 PM
>> > To: computer-go
>> > Subject: Re: [computer-go] What Do You Need Most?
>> >
>> > At 06:23 PM 7/27/2008, you wrote:
>> > >I have a strong interest in seeing a 19x19 computer go program that is
>> > >at least 3-dan by 2010.
>> >
>> > we all do. but as the programs are only about 10-kyu these days, we
>> > will be lucky to get to the small kyu ratings by 2010 and then you
>> > will hit a hard wall.
>> >
>> > i think michael is correct when he mentions incentive. there are not
>> > to many $'s out there to go after.
>> >
>> > some of us try to get the programs into tournaments (like
>> > http://www.cotsengotournament.com/), but the aga refuses to allow the
>> > games for credit. ...
>>
>
> ---
> vice-chair http://ocjug.org/
>
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Representation of state-action pairs

[Sylvain Gelly]

MoGo has a notion of "internal" node in the tree (as most of the UCT
programs I think) and the state-action pairs are only kept for those.

Sylvain

2008/7/2 Jason Galbraith <[EMAIL PROTECTED]>:
> I've been looking at RAVE (Rapid Action Value Estimate), which MoGo uses.  The
> score of states during simulation is stored in state-action pairs, which are
> all updated with the playouts, rather than just those states visited in the
> tree.  How would you store these scores?  The number of potential states
> visited seems prohibitively large.
>
> Jason Galbraith
> Orego research group
>
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] batch size and impact on strength

[Sylvain Gelly]

>
> This seems to be the case and I still do not really on some level
>> understand why. Since with the chinese go rules the board should be
>> effectively stateless (exempting ko information) all the information be
>> contained in the the current position. Why additional information is needed
>> i.e. an annotation of the last played move is required on some level is a
>> mystery to me.
>>
>
> One can build nice examples of that for some artificial games: the
> knowledge of the last move helps *for finite computational cost*.
> Sylvain has shown interesting elements around that, but as far as I know
> this was not in his ph.D. thesis and this is not published.


If I understand correctly what it is about, I do have something in my thesis
about that.
p153:" 4.4.3 Mathematical insights: strength VS accuracy", and more
precisely "Theorem 4.4.1 (Accurate simulation player without memory is
strong)"
It is certainly not of direct practical application though.

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

Re: [computer-go] MoGo/professional challenge

[Sylvain Gelly]

It was 2 cores 2.6GHz. (intel core2 duo).

2008/3/21, Olivier Teytaud <[EMAIL PROTECTED]>:
> > What computing power did have that MoGo at its disposal?
>
>
> 4 cores, 2.4 GHz.
>
> ___
>  computer-go mailing list
>  computer-go@computer-go.org
>  http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] f(score) instead of sign(score)

[Sylvain Gelly]

> So MoGo may be
>  using a floating point function to estimate the score of a playout,
>  otherwise there would be no reason to use floating point. But I may be
>  guessing wrong. Maybe they can tell us ?

We don't (at least up to the release, I don't know everything they are
doing now). Using the floats was for flexibility, because we did try
transformation as suggested and we also tried decays. We wrote things
before knowing what will work so the choices were always "does it
allow us to experiment ideas?".

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

Re: [computer-go] 13x13 study. Time and memory

[Sylvain Gelly]

2008/2/22, Alain Baeckeroot <[EMAIL PROTECTED]>:
> Le jeudi 21 février 2008, Don Dailey a écrit :
>  > If you look at the table you will notice that going from level 4 to
>  > level 11 (which is 7 doublings  and should take 128X longer)  only takes
>  > 59.43 X longer.
>  >
>
>  So if we plot 9X9 rank vs time, maybe we have a straight line :)
It would indeed be very interesting to see that plot!

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

Re: [computer-go] 13x13 study.

[Sylvain Gelly]

Hi Don,

2008/2/21, Don Dailey <[EMAIL PROTECTED]>:
>
>  If you look at the table you will notice that going from level 4 to level
> 11 (which is 7 doublings  and should take 128X longer)  only takes 59.43 X
> longer.

> Mogo's "stop early" heuristic works better at longer levels.

That is actually very interesting, and may be a new hypothesis for the
scalability limits we saw in 9x9. There are two kind of "stop early
heuristics"
- a safe one, in the following case: if we began to always simulate
the second best move, it would not have more simulations that the
first best move at the end of the time limit. As the chosen move is
the one with the maximum number of simulations, there is no point to
continue thinking.
- a risky one, in the following case: if the first best move have more
than x% of all simulations, and the ratio first best move/second best
move (in number of simulations) is more than y, and the total number
of simulations is greater than expected total of simulations / 2, then
we stop.
There is also a "hard" stop early in the following case: if the first
best move have more than 1-(1-x%)/2 of all simulations, and the ratio
first best move/second best move (in number of simulations) is more
than 2 * y, and the total number of simulations is greater than
expected total of simulations / 4, then we stop

Maybe x and y are not adapted to long thinking time (stop too early in
a loosing move).
Or maybe they are, and it worth saving time :).

Anyway, it is normal that we longer thinking time, even the first
heuristic arrives much more often.

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

Re: [computer-go] Re: MoGo 64 bits, mogo double

[Sylvain Gelly]

Hi Hideki,

Isn't possible to just redirect stderr?

Best,
Sylvain

2008/2/14, Hideki Kato <[EMAIL PROTECTED]>:
> Hi Olivier,
>
>  New versions of MoGo don't put log files, which was very useful to
>  study.  Don't you have plan to release such versions put log files?
>
>  -Hideki
>
>  Olivier Teytaud: <[EMAIL PROTECTED]>:
>
> >For people requesting mogoRelease3 without the bug for long computation
>  >times due to a float instead of a double:
>  >
>  >http://www.lri.fr/~teytaud/mogo (32 bits version, with double instead of
>  >   float)
>  >
>  >http://www.lri.fr/~teytaud/mogo64 (64 bits version, double also)
>  >
>  >Just compiled, almost untested, sorry;
>  >please email me in case of troubles.
>  >
>  >Best regards,
>  >Olivier
>  >___
>  >computer-go mailing list
>  >computer-go@computer-go.org
>  >http://www.computer-go.org/mailman/listinfo/computer-go/
>
> --
>  [EMAIL PROTECTED] (Kato)
>
> ___
>  computer-go mailing list
>  computer-go@computer-go.org
>  http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

> >Thinking a little more about it, I think we have to add an hypothesis
> >which is that, for a given move, the number of AMAF updates if < alpha
> >(nb total UCT updates), with alpha < 1. That seems to hold for most of
> >the updates (with alpha close to 0.5), but there may be cases where it
> >does not hold.
> >
> >
> If I understand well, you say that, in order to ensure consistency,
> we need some assumptions on the AMAF updates,
> i.e. the MC simulations which decide which move will have AMAF updates.

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

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

[Sylvain Gelly]

> As far as I see,
> if RAVE gives constant value 0 to one move, it will never be tested if
> other moves
> have non-zero AMAF values.
>
> A move
> with "real" empirical probability 0 of winning and AMAF value of 0.01
> will always be preferred to a non-simulated move with AMAF 0.0, whatever
> may be
> the number of simulations.
I agree, it is why I added a statement about the prior, which implies
that the AMAF value is never 0.0 but at worst decreases like 1/m if m
is the number of AMAF updates for that move.

Thinking a little more about it, I think we have to add an hypothesis
which is that, for a given move, the number of AMAF updates if < alpha
(nb total UCT updates), with alpha < 1. That seems to hold for most of
the updates (with alpha close to 0.5), but there may be cases where it
does not hold.
Maybe I am confused and say unsound things, sorry for that. It is the
kind of things we should discuss in front of a black (or white) board.

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

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

[Sylvain Gelly]

A new position is always visited unless the leaf of the tree is the
end of the game. In that case, one player always win, so the other
always win. Then, the losing player will explore all the other moves
to avoid the sure loss. If all moves are still loosing, that will
propagate to the move before, and the exploration will begin and so
on.
There is indeed no forced exploration, but there is exploration as
soon as a move is loosing.
I can totally be wrong, but currently I don't see where this does not
hold. Does it?


Sylvain

2008/2/10, Olivier Teytaud <[EMAIL PROTECTED]>:
> > - at "each" (or every n) iteration you add one node.
>
> As far as I see, new nodes are created only if new nodes are visited;
> if
> score(visited nodes) > score(unvisited nodes)
> why would mogo visit new nodes ?
>
> But (before the recent PDF file) I never understood completly
> the bandit in mogo, so you are probably right :-)
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

> So:
> - theoretically, I don't see any reason for mogo to be asymptotically
>consistent

I think it is still asymptotically consistent:
- at "each" (or every n) iteration you add one node.
- if the node is at the end of the game, the evaluation is perfect.
- you play the move with the highest combination of UCT/Rave

So starting from the end of the game, I think by induction we can show
that it is consistent (without forgetting that we start with a prior,
== 0.5 if no pattern, so the RAVE value is never 0).
Am I wrong?

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

Re: [computer-go] MoGo 64 bits, mogo double

[Sylvain Gelly]

Hi all,

I added those downloads on the MoGo's download page:
http://www.lri.fr/~gelly/MoGo_Download.htm

Cheers,
Sylvain

2008/2/9, Olivier Teytaud <[EMAIL PROTECTED]>:
> For people requesting mogoRelease3 without the bug for long computation
> times due to a float instead of a double:
>
> http://www.lri.fr/~teytaud/mogo (32 bits version, with double instead of
> float)
>
> http://www.lri.fr/~teytaud/mogo64 (64 bits version, double also)
>
> Just compiled, almost untested, sorry;
> please email me in case of troubles.
>
> Best regards,
> Olivier
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Sylvain Gelly]

Hi Erik,

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

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

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

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

[Sylvain Gelly]

Hi Erik,

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

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

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

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

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


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

It is definitely a sensible hypothesis.

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

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

[Sylvain Gelly]

Hi Erik,

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

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

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

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

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

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

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

Re: [computer-go] 9x9 study rolloff

[Sylvain Gelly]

Hi Don,

As I said it is confusing :). limitTreeSize does not make much sense
since collectorLimitTreeSize, so it is more or less historical. Just
put limitTreeSize to something bigger to collectorLimitTreeSize, and
just forget about it. collectorLimitTreeSize is the size where the
garbage collection occurs, it is the only interesting variable, but if
limitTreeSize is smaller than that, then the garbage collection will
not occur. Sorry for the confusion.


Sylvain

2008/2/1, Don Dailey <[EMAIL PROTECTED]>:
> Sylvain,
>
> These 2 parameters are confusing to me.   --collectorLimitTreeSize
> sounds like it limits the tree size to whatever your setting are,  but
> so does  --limitTreeSize. What is the difference between a tree and
> a collector tree?
>
> I assume the collector is a garbage collector of some sort?My guess
> is that the collector limit is the largest tree allowed after collection
> and the --limitTreeSize is how big it must get before collection?
>
> - Don
>
>
>
>
> Sylvain Gelly wrote:
> > Hi,
> >
> > With such a large number of playouts, the tree size limit (and so
> > heavy pruning) is certainly a possible hypothesis. The simplest way to
> > test it would be to run the same MoGo_17 or _18 with a much bigger
> > tree (taking more memory). --collectorLimitTreeSize is by default
> > 40 (number of nodes). If you want to increase beyond 100, you
> > should also add --limitTreeSize 200 (this limitTreeSize does not
> > make much sense with the pruning, but it is a hard limit which,
> > whatever happens, will not be reached... modulo bugs ;))
> >
> > Sylvain
> >
> > 2008/1/31, Janzert <[EMAIL PROTECTED]>:
> >
> >> I haven't seen anyone else mention this, although I may have missed it
> >> in one of the previous discussions.
> >>
> >> I find it pretty amazing that both Mogo and Fatman are leveling off at
> >> exactly, or almost exactly, the same number of playouts (i.e. Fatman lvl
> >> 14 == Mogo lvl 18 == 8388608 playouts). Could it simply be that they
> >> have run out of memory to build a larger tree and are starting to prune
> >> branches that would become critical if they had the space to explore them?
> >>
> >> Janzert
> >>
> >> ___
> >> computer-go mailing list
> >> computer-go@computer-go.org
> >> http://www.computer-go.org/mailman/listinfo/computer-go/
> >>
> >>
> > ___
> > computer-go mailing list
> > computer-go@computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> >
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 9x9 study rolloff

[Sylvain Gelly]

Hi,

With such a large number of playouts, the tree size limit (and so
heavy pruning) is certainly a possible hypothesis. The simplest way to
test it would be to run the same MoGo_17 or _18 with a much bigger
tree (taking more memory). --collectorLimitTreeSize is by default
40 (number of nodes). If you want to increase beyond 100, you
should also add --limitTreeSize 200 (this limitTreeSize does not
make much sense with the pruning, but it is a hard limit which,
whatever happens, will not be reached... modulo bugs ;))

Sylvain

2008/1/31, Janzert <[EMAIL PROTECTED]>:
> I haven't seen anyone else mention this, although I may have missed it
> in one of the previous discussions.
>
> I find it pretty amazing that both Mogo and Fatman are leveling off at
> exactly, or almost exactly, the same number of playouts (i.e. Fatman lvl
> 14 == Mogo lvl 18 == 8388608 playouts). Could it simply be that they
> have run out of memory to build a larger tree and are starting to prune
> branches that would become critical if they had the space to explore them?
>
> Janzert
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 19x19 Study

[Sylvain Gelly]

No problem for me. I did not want to multiply the number of versions not to
confuse people. With the double version, don't forget it will increase the
memory footprint for a given number of nodes.

Sylvain

2008/1/30, Olivier Teytaud <[EMAIL PROTECTED]>:
>
> I can provide a new release with double instead of float.
> (unless the other mogo-people reading this mailing-list do not agree for
> this; Sylvain, no problem for you ?).
>
> > I don't know exactly when it begins to do bad moves. However, I know
> that
> > after several hours, the estimated winning rate converges to 1 or 0,
> with
> > crazy principal variations, and the cause is low resolution of single
> > floats. In this study, it should no be a big factor of unscalability
> given
> > the number of simulations.
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 19x19 Study

[Sylvain Gelly]

Hi,
I don't know exactly when it begins to do bad moves. However, I know that
after several hours, the estimated winning rate converges to 1 or 0, with
crazy principal variations, and the cause is low resolution of single
floats. In this study, it should no be a big factor of unscalability given
the number of simulations.

Sylvain

2008/1/29, terry mcintyre <[EMAIL PROTECTED]>:
>
> Sylvain, in the download notes, you mention that Mogo has some troubles
> with "very long" timescales, due to the low resolution of single floats. Do
> you have any estimate of how many simulations would lead to this situation?
>
>
>
> Terry McIntyre <[EMAIL PROTECTED]>
> - Original Message 
> From: Sylvain Gelly <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Tuesday, January 29, 2008 10:36:38 AM
> Subject: Re: [computer-go] 19x19 Study
>
> but not linearly and you can see a nice gradual curve in the plot.
> >
> > Now we have something we can argue about for weeks.   Why is it not
> > mostly linear?   Could it be the memory issue I just mentioned?
> >
>
> Hi Don and all participants to that study, that is very interesting!
>
> The memory constrains are certainly a valid hypothesis, especially the
> default settings of the release are rather conservative on that side,
> because it seemed better to have a weaker player than begin to make the
> player's machine swapping... Those settings are rather fitting your memory
> constrains as well, so it is fine.
>
> Reading your email and looking at the curve, I wonder if one possible
> explanation could be an artifact on how the ratings are computed? My
> question is: what curve would we see for that study if the involved players
> were exactly linearly scalable? That seems silly, but I wondered if there
> were an underestimating of higher levels, because of the way the bayeselo
> works. I am also looking at the curve after the 5-6th level (~gnugo), as
> behavior may be different for very low levels.
>
> I don't know if my hypothesis makes sense.
> Sylvain
>
>
> --
> Never miss a thing. Make Yahoo your 
> homepage.<http://us.rd.yahoo.com/evt=51438/*http://www.yahoo.com/r/hs>
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 19x19 Study

[Sylvain Gelly]

>
> between pairs
> of programs, you can get a more and more confident belief about
> the actual ELO.  so they'll converge to the correct values, and
> should do so reasonably rapidly.
>

You are right. My point was that here we have only 1 fixed rating, which is
very low, and all the higher levels depends on the levels just below them.
So I wondered if the underestimate was propagating and cumulating, making
the top, as you add doublings, more and more far from the "real" values. It
is why I wondered about the curve if we made "virtual games" between players
with fixed "linear" ratings, to see what the current method would predict
(note that all players are being rated at the same time).

It was just an hypothesis, it may be totally irrelevant :)

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

Re: [computer-go] 19x19 Study

[Sylvain Gelly]

>
> but not linearly and you can see a nice gradual curve in the plot.
>
> Now we have something we can argue about for weeks.   Why is it not
> mostly linear?   Could it be the memory issue I just mentioned?
>

Hi Don and all participants to that study, that is very interesting!

The memory constrains are certainly a valid hypothesis, especially the
default settings of the release are rather conservative on that side,
because it seemed better to have a weaker player than begin to make the
player's machine swapping... Those settings are rather fitting your memory
constrains as well, so it is fine.

Reading your email and looking at the curve, I wonder if one possible
explanation could be an artifact on how the ratings are computed? My
question is: what curve would we see for that study if the involved players
were exactly linearly scalable? That seems silly, but I wondered if there
were an underestimating of higher levels, because of the way the bayeselo
works. I am also looking at the curve after the 5-6th level (~gnugo), as
behavior may be different for very low levels.

I don't know if my hypothesis makes sense.
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGoRel3_3550pps

[Sylvain Gelly]

Hi,

Nothing strange here. You tell MoGo to play 19x19 and you tell him that
there is only 60 s left. It can be understood that it takes only 1s for this
move...
BTW, if you see him play in 9x9, it is because while you told him to set his
parameters for a 19x19, by default the boardsize is 9x9 and MoGo expects a
gtp command to override it.

Cheers,
Sylvain

2008/1/13, Michael Williams <[EMAIL PROTECTED]>:
>
> Sylvain Gelly wrote:
> >
> > The reason I said that was this behavior from mogo.  If I start it
> > without that switch and as for a move, it allocates 20 seconds.  If
> > I then issue a small
> > time_left command and ask for another move, it allocates a much
> > smaller amount of time.  Here is the output:
> >
> > Because you give a time_left < 20, so MoGo is in "fast end mode", just
> > playing randomly to avoid loosing by time.
>
> OK, here it is with 60 seconds (still no command-line switch):
>
>
> [EMAIL PROTECTED]:~/go$ ./mogo --19
> initiateNodeUrgencyForShisho at root node!
> Load opening database openingValues_19 succeed (nbEntries=60629)
> (nbIllegalMoves removed 0)
> tried to open openingValues_19, success 1
> time_left b 60 0
> =
>
> genmove b
> time left: 60 secs
> time given for this move:  1.0 sec time
> shishoCheck is called. Now we have 0 shishoLocations: and 0
> attackShishoLocation
>
> initiateNodeUrgencyForShisho at root node!
> Self train initiation time: 0.00
> 0.443380(83%) ||   1148/ 1(11%)(93%)(58%/0.60) ||47 |12 || B2 C3
> D3 D4 E4 E3 D2 F4 E5||SSP:B2 C3 A1 H8 J1 ||PSP:B2 C3 A1 H8 J1
> earlyCut : max1 1364; max2 1120; sum 12061  max1/sum 0.113082 ; max1/max2
> 1.216771 (hard 0)
> 0.435484(16%) ||   1364/ 12061(11%)(82%)(65%/0.60) ||53 |12 || B2 C3
> D3 D4 E4 E3 D2 F4 E5||SSP:B2 C3 A1 H8 A6 ||PSP:B2 C3 A1 H8 A6
> 12061 simulations(average length:0) done, time used:   0.96 seconds.(
> 12563.5 games/sec)
>
>
> A  B  C  D  E  F  G  H  JABCD 
>EFGHJ
>   +---+
> +-+
>   9   | .  .  .  .  .  .  .  .  . | |  0.0001   2.4427   2.4315
> 0.0001   0.2353   0.3509   0.3750   0.3204   0.3867 |
>   8   | .  .  .  .  .  .  .  .  . | |  2.4245   0.4698   2.4267
> 0.0001   2.4426   0.5111   2.4430   0.4303   0.3468 |
>   7   | .  .  .  .  .  .  .  .  . | |  0.5000   2.4244   2.4167
> 2.4193   0.5317   2.4296   2.4360   0.4259   2.4463 |
>   6   | .  .  .  .  .  .  .  .  . | |  0.4343   2.4323   2.4267
> 0.5000   2.4398   2.4261   0.0001   0.3043   0.3857 |
>   5   | .  .  .  .  .  .  .  .  . | |  0.3961   2.4463   2.4310
> 2.4306   0.4898   0.5248   2.4324   0.4249   0.3109 |  Black to play
>   4   | .  .  .  .  .  .  .  .  . | |  0.3663   0.0001   2.4404
> 2.4231   2.4280   2.4326   2.4394   0.4268   0.3033 |  Black eaten
> stone(s): 0
>   3   | .  .  .  .  .  .  .  .  . | |  0.3582   0.3846   0.4429
> 0.5417   2.4329   2.4407   2.4381   2.4381   0.3387 |  White eaten
> stone(s): 0
>   2   | .  .  .  .  .  .  .  .  . | |  0.2000   0.4355   0.5000
> 0.4000   0.3438   2.4395   2.4387   0.3760   0.3895 |
>   1   | .  .  .  .  .  .  .  .  . | |  0.4284   0.4000   0.3867
> 0.3780   0.4011   0.3805   0.3782   0.4040   0.4129 |
>   +---+
> +-+
>
> A  B  C  D  E  F  G  H  J A  B  C  D  E  F  G  H  J
>   +---+ +---+
>   9   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0 |
>   8   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0 |
>   7   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0 |
>   6   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0
> |  Move 1: B2
>   5   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0
> |  White to play
>   4   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0
> |  Black eaten stone(s): 0
>   3   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0
> |  White eaten stone(s): 0
>   2   | . (@) .  .  .  .  .  .  . | | 0  1  0  0  0  0  0  0  0 |
>   1   | .  .  .  .  .  .  .  .  . | | 0  0  0  0  0  0  0  0  0 |
>   +---+ +---+
> B2
> = B2
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGoRel3_3550pps

[Sylvain Gelly]

> The reason I said that was this behavior from mogo.  If I start it without
> that switch and as for a move, it allocates 20 seconds.  If I then issue a
> small
> time_left command and ask for another move, it allocates a much smaller
> amount of time.  Here is the output:
>
> Because you give a time_left < 20, so MoGo is in "fast end mode", just
playing randomly to avoid loosing by time.

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

Re: [computer-go] Sylvain Gelly thesis in english

[Sylvain Gelly]

> > >Google finds it:
> > >http://tao.lri.fr/Papers/thesesTAO/SylvainGellyThesis.pdf
>
That is NOT the latest version. Please at least let me put the latest
version on my web site, it took me so long to correct it :).

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

Re: [computer-go] MoGoRel3_3550pps

[Sylvain Gelly]

2008/1/10, [EMAIL PROTECTED] <[EMAIL PROTECTED]>:
>
> Hi Sylvain,
>   Have you finished your thesis? We are eager to read it:-)


Hi,

Yes I did! :).It is not on my website, but will (soon?).
However, you should not be so eager to read it :)

Cheers,
Sylvain


On 1/10/08, Sylvain Gelly <[EMAIL PROTECTED]> wrote:
> > Hi,
> >
> > I guess the public version of MoGo was designed with a
> > > focus on 9x9 and not 19x19.
> >
> > It was not more on 9x9 that 19x19, it was more or less the best settings
> of
> > MoGo against gnugo at the moment I left the developpement (early
> september)
> > for both 9x9 and 19x19.
> >
> >
> > Or is there something else I should be
> > > including on the command line?
> >
> > As other said, but just to confirm:
> > --playsAgainstHuman 0
> > Also you have to specify
> > --totalTime 300
> >
> > if 300 is the number of seconds of the games. If not, MoGo does not care
> > about the time left, and will just play a constant time per move,
> loosing by
> > time with no other worry :).
> >
> > The release is designed to play against human on a server/client which
> > supports a scoring taking into account the dead stones. On cgos you have
> to
> > capture all dead stones.
> > As for the rating, I don't know all the changes that has been done on
> CGOS
> > since then, but on the old 19x19 one, the rating should be more than
> 2100 or
> > 2200.
> >
> > Hoping this helps,
> > Sylvain
> >
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MoGoRel3_3550pps

[Sylvain Gelly]

>
> It looks like MoGo does respect the time_left commands from GTP, so I
> don't think the totalTime parameter is required in this case.
>
What do you mean? If you don't put --totalTime, then MoGo indeed ignores
time_left. If you put --totalTime, then it respect the time_left.

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

Re: [computer-go] MoGoRel3_3550pps

[Sylvain Gelly]

Hi,

I guess the public version of MoGo was designed with a
> focus on 9x9 and not 19x19.

It was not more on 9x9 that 19x19, it was more or less the best settings of
MoGo against gnugo at the moment I left the developpement (early september)
for both 9x9 and 19x19.


Or is there something else I should be
> including on the command line?

As other said, but just to confirm:
--playsAgainstHuman 0
Also you have to specify
--totalTime 300

if 300 is the number of seconds of the games. If not, MoGo does not care
about the time left, and will just play a constant time per move, loosing by
time with no other worry :).

The release is designed to play against human on a server/client which
supports a scoring taking into account the dead stones. On cgos you have to
capture all dead stones.
As for the rating, I don't know all the changes that has been done on CGOS
since then, but on the old 19x19 one, the rating should be more than 2100 or
2200.

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

Re: [computer-go] low-hanging fruit

[Sylvain Gelly]

>
> You should be using area scoring only and if you are playing handicap
> games then either YOU or MOGO is not counting them the same. Or
> perhaps Mogo has a bug in the handicap code.
>

MoGo uses KGS handicap counting (add 1 point to white for each handicap
stone) if the GTP set_handicap_stones (approximate spelling) is called.
MoGo never passes when it looses, it resign instead. So if MoGo passes, that
means that you lost :) (there are also sometimes bad interpretations of
nakade but that is not the case from what you describe).

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

Re: [computer-go] MoGo pondering

[Sylvain Gelly]

Hi,

It just build the tree as usual, thinking as the opponent.

2007/11/6, Chris Fant <[EMAIL PROTECTED]>:
>
> Could Sylvain (or anyone who knows) talk about MoGo's pondering
> strategy?  Does it just build the tree as usual or does it speculate
> on some number of moves and hope that the opponent choses one of
> those?
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] RAVE in MoGo paper

[Sylvain Gelly]

Hi,


2007/10/8, Benjamin Teuber <[EMAIL PROTECTED]>:
>
> Hi everybody - especially Sylvain =)
>
> I'm wondering whether the formula to determine the balance between RAVE
> and UCT,
> beta = sqrt(c / 3 * parentVisits + c),
> has any mathematical background - or is it just a best guess for something
> that starts at 1 and is 1/2 after a certain number of visits?


No it is just a tuning :)


Another question is about the prior integration. Apparently the prior, RAVE
> and UCT values are three different estimators for the winning probability.
> So why not use the above formula for prior vs. RAVE balancing, too, instead
> of initializing RAVE with it?
>

Our prior is actually classical and equivalent to a Dirichlet prior for the
RAVE value. Of course we could put the prior in other ways, put I strongly
believe that at this point the relevance of the prior is more important that
the way you use it.

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

Re: [computer-go] Update of MoGo binary release, and windows version available!

[Sylvain Gelly]

Hi,

Yes you can:
--nbTotalSimulations 3000

Once you set this option it ignores all other time settings.

Cheers,
Sylvain

2007/10/7, Yamato <[EMAIL PROTECTED]>:
>
> Sylvain,
>
> Can I set the number of the simulations per move instead of the
> thinking time? (like "--simulations 3000")
> If possible, it is very useful for the benchmark.
>
> --
> Yamato
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Mogo: nakade

[Sylvain Gelly]

Hi,

ok I understand.
Unfortunately MoGo is not multithreaded on windows due to the bad
performance of pthread. So it actually use only 1 thread.

However a side effect of "--nbThreads x" is that the time per move is
multiplied by x, because the time is computed as CPU time.
In your setting that means that MoGo actually uses twice as much time, ie 60
s.

Sorry for the confusion for you, and for other people who may have run into
it.

Cheers,
Sylvain

2007/10/6, [EMAIL PROTECTED] <[EMAIL PROTECTED]>:
>
> I used --19 --time 30 --nbThreads 2
>
> DL
>
>
> -Original Message-
> From: Sylvain Gelly <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Fri, 5 Oct 2007 5:48 am
> Subject: Re: [computer-go] Mogo: nakade
>
>  > I set 30 second playing
> > time, but often it takes up to couple minutes for a move.
> That is not normal, could you post the command line you use?
>
> Cheers,
> Sylvain
> ___
> computer-go mailing list
> [EMAIL PROTECTED]://www.computer-go.org/mailman/listinfo/computer-go/
>
>  --
> Email and AIM finally together. You've gotta check out free AOL 
> Mail<http://o.aolcdn.com/cdn.webmail.aol.com/mailtour/aol/en-us/index.htm?ncid=AOLAOF0002000970>
> !
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Mogo: nakade

[Sylvain Gelly]

> I set 30 second playing
> time, but often it takes up to couple minutes for a move.
That is not normal, could you post the command line you use?

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

Re: [computer-go] Mogo: nakade

[Sylvain Gelly]

Hi Darren,
Thank you for playing (I hope you enjoyed :)) and your report.

> Sylvain, can you explain more about why it has this particular weakness?
What you describe is exactly the issue I describe in the FAQ.
>From my analysis this come from the fact that the simulations are more
likely to make the dead group to live than to die. It happens only on
some situations, but when it happens, and you are in a part which is
not explored by the tree, the probability for the group to die is low
so MoGo simply consider that there is more important part of the board
to analyse. Of course you can be more agressive on exploration and
then get rid of this problem, but what I want is the best playing
level in average, not solve some particular positions.
I guess an overall fix of the simulation would be the best way to go for that.

> Also, is there a plan to fix it?
Not by me at least ;). As I said earlier I am not working on it anymore...

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

Re: [computer-go] IEEE Spectrum article by Deep Blue creator

[Sylvain Gelly]

Hi,

> Has anyone else done scaling experiments with 19x19 and UCT?
>

I did some months ago, and reported them in that list with the title
"19x19 Go, scalability with time vs handicap"
(http://www.mail-archive.com/computer-go%40computer-go.org/msg02775.html)

The results are "old", but now everyone can do those experiments as
you all have the newest binaries ;) (you can only do the experiments
with "time" but not "number of simulations", so you would have to run
on the same type of machines).

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

Re: [computer-go] Mogo: tree preservation

[Sylvain Gelly]

Hi Darren,

It preserves the tree if and only if you add:
--pondering 1

If you don't want to use pondering, but you still want to keep the tree
between moves, add
--keepTreeIfPossible 1

(not documented, and from my memory, it may be not the right option :p)

Hoping this helps,
Sylvain

2007/9/28, Darren Cook <[EMAIL PROTECTED]>:
>
> Hi Sylvain,
> I've had chance to play Mogo a fair bit recently, and have a couple of
> questions. The 2nd requires I make a diagram so I'll just ask the easy
> first one: is Mogo preserving the tree between moves, or does it start
> fresh each time?
>
> Surprisingly it seems to be the latter. E.g. we're mostly following its
> prime variation, but after my move in that line its first 20-30,000
> nodes are sometimes spent re-exploring the lines we both know won't work
> before it rediscovers the variation we were following.
>
> (If it is in fact preserving part of the tree is there any number in the
> debug output that says how many nodes it is carrying over?)
>
> Darren
>
>
> --
> Darren Cook
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese free dictionary)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/work/charts/  (My flash charting demos)
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Update of MoGo binary release, and windows version available!

[Sylvain Gelly]

Dear Hideki, Dear all,

I addressed some of the issues some of you mentioned. Thank you very much
for the reports. Now the collision between time management and --time xx in
19x19 is no more here (while you assuming there is no time_left sent).
There is also now a --13 option.
The "--dontDisplay 1" removes all the displays (rather than "most of").

For the issues reported by Gilles for Drago concerning the "final_status"
and "final_status_list alive" gtp commands, I read the GTP doc, and I
understand now :).
MoGo implements a subset of GTP which is sufficient for CGOS, KGS and gogui,
so the "final_status_list dead" works well, and should be enough to compute
the score. The others are simply unfortunately not supported.
I am very sorry for the inconvenience.

Best,
Sylvain




2007/9/20, Hideki Kato <[EMAIL PROTECTED]>:
>
> Hi Sylvain,
>
> Thank you for the releases of the Windows version and the Linux
> version for older processors.
>
> The Windows version, however, seems much weaker than MoGo that running
> on KGS these days on 19x19, even giving much longer time setting such
> as "--time 300" for example.  I guess some other settings than time
> are necessary.
>
> So, my question is what setting allows Windows version being the same
> strength as KGS version?
>
> Regards,
> Hideki
>
> Sylvain Gelly: <
> [EMAIL PROTECTED]>:
> >Hi all,
> >
> >you can find here:
> >http://www.lri.fr/~gelly/MoGo_Download.htm
> >
> >an update of MoGo's release, especially binary for non pentium4
> >compatible processors, some other options explained, and maybe more
> >interesting, an option for time management (I stupidly did not think
> >that people would use MoGo with frontend sending "time_left"). It is
> >basically adding simple interface to what existed before, but I hope
> >it will be useful for you.
> >
> >In the same time of this update, you can finally download a windows
> >version! Unfortunately, it is not multithread, and still 30% slower
> >than the linux version, but at least it works :).
> >
> >Hopefully a Mac version will come.
> >
> >Please feel free to share the link to any player you know who may be
> interested.
> >
> >Best,
> >Sylvain
> >
> >PS: I had no time to check everything. Hopefully it works, but if you
> >find problems please report (and don't be upset ;-))
> >___
> >computer-go mailing list
> >computer-go@computer-go.org
> >http://www.computer-go.org/mailman/listinfo/computer-go/
> --
> [EMAIL PROTECTED] (Kato)
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Update of MoGo binary release, and windows version available!

[Sylvain Gelly]

Hi Hideki,


The Windows version, however, seems much weaker than MoGo that running
> on KGS these days on 19x19, even giving much longer time setting such
> as "--time 300" for example.  I guess some other settings than time
> are necessary.
>

Sorry, you are right the 19x19 settings always put the time management "on".
So either play with "--totalTime xx" (instead of "--time xx") and use some
frontend sending the time_left command, or add "--timeManagementMode 0", or
wait for me to fix ;).
The 9x9 is not affected by that.

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

Re: [computer-go] Update of MoGo binary release, and windows version available!

[Sylvain Gelly]

Hi Gilles,


yes they are some problems to use MoGo with Drago. The main issue is the
> initial message written to stderr as guessed by Dave. Actually, Drago
> handles incorrectly stdout and stderr in the same way but this is easily
> corrected.


Good news!

I have uploaded a patch for using MoGo with Drago:
> www.godrago.net/DragoForMogoPatch.zip. The zip contains an exe file which
> should replace the one from the current Drago install.


Why is it only a patch for MoGo? Is it only a change to handle stderr in a
good way?


As MoGo does not implement the GTP command final_result, an error message is
> displayed at the end of the game and the user must count the result. (By
> the
> way, is there a problem with 'final_status_list alive' ?)


I don't about all those GTP commands. MoGo implements a subset of GTP which
is enough for cgos, KGS and gogui.
For the scoring, of course cgos is the minimal :), but the scoring works
very well on KGS and gogui. I don't know which commands they send, but it
seems enough :).
Yet, it would be good for MoGo to support Drago as it seems pretty trivial
to do so, I will at some point look into it (without giving a date :)).

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

Re: [computer-go] Update of MoGo binary release, and windows version available!

[Sylvain Gelly]

Hi Dave and thanks,

>  Drago works well for Gnugo and also for my program. Mogo starts but then
> exits prematurely with a message from Drago "abnormal termination of
> engine".
:-(

>   One thing, when I run it from the command line, it spits out a lot of
> non-gtp format diagnostic information even with the setting "--dontDisplay
> 1". That would upset some clients, including probably Drago, although I'd
> expect different symptoms if that were the only problem.

Normally not, the diagnostic information are sent to stderr, and
should not be a problem. So shall I understand MoGo at least works for
you on command line?

>  I put an extra copy of cygwin1.dll in the "WINDOWS\system32" directory, so
> mogo can find it from anywhere and I used "--9 --time 12
> --useOpeningDatabase 0 --dontDisplay 1". That got it connected to Drago and
> actually set up a game.
You mean that with the .dll in WINDOWS\system32 that goes further? I
thought that the .dll in the same directory as the .exe was enough.

> But it terminates as soon as it gets a genmove
> comand.
:-(
With no error message?

> It creates a logfile in the directory where it is supposed to be
> running. There is one line that says
>  "MoGo GTP log file."
Lol. That means it did not get very far :)

>  My best guess, right now, is that the non-gtp diagnostic messages are
> causing trouble. I'll look at it some more when I have time.
Sorry for the trouble.
I'll look at it as soon as I find some time, ie I don't know when :).

Sorry again for the trouble :-/
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Update of MoGo binary release, and windows version available!

[Sylvain Gelly]

Hi all,

you can find here:
http://www.lri.fr/~gelly/MoGo_Download.htm

an update of MoGo's release, especially binary for non pentium4
compatible processors, some other options explained, and maybe more
interesting, an option for time management (I stupidly did not think
that people would use MoGo with frontend sending "time_left"). It is
basically adding simple interface to what existed before, but I hope
it will be useful for you.

In the same time of this update, you can finally download a windows
version! Unfortunately, it is not multithread, and still 30% slower
than the linux version, but at least it works :).

Hopefully a Mac version will come.

Please feel free to share the link to any player you know who may be interested.

Best,
Sylvain

PS: I had no time to check everything. Hopefully it works, but if you
find problems please report (and don't be upset ;-))
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

Hi Jacques,

2007/9/17, Jacques Basaldúa <[EMAIL PROTECTED]>:
> Hi Sylvain,
>
> Any news about the Windows release?
The release time is closer now than before :)

> It doesn't need to be fast. It
> doesn't even need
> to be multithreaded. It is for research only. We can believe that on a
> quad core it takes 1/4 of the time, that's not important.
You are right that is not important for the research community, but
for the players that is actually important. I wish go players can use
MoGo, not only computer go people. As it is difficult to make the
difference between computer go people and players on a web page :), I
prefer things to be a little better on windows. I now have a version
which is "only" 25% slower on windows compared to linux. But things
happen slowly because I can only dedicate very very little time to
MoGo, so please be patient :).

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

Hi Hideki,

> Some computer-go friends in Japan have reported that even current
> binary of MoGo doesn't work on Athlon XP or Celeron.  Both (and
> Pentium III) have no SSE2 instructions while Pentium 4 has.

Ok, I have to compile for older processor too then (I did not expect
so old proc were still existing :))

> Could you please try -march=athlon-xp, pentium3 or generic?
I will.
I do it ASAP and let you know.

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

Hi Edward and all,

>  I am very interested in a windows binary to use MoGo as an
>  extra sparring partner, (I cannot use linux at this moment),
>  I do not mind if the binary is slower,

Maybe distributing a windows version only for known people is
possible. I will do it ASAP, but I have to reboot on windows, so not
tonight :-).

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

Hi Markus, Hi all,

I updated the package to fix the issues you get and some other minor
ones. Please update before reporting a problem, and please report any
further problem :-).

> I don't know about Ubuntu, but the default GCC configuration on Fedora
> does not set CPU-specific compiler options, so an executable should
> run on the whole family of i386 processors.
I don't use the default gcc options, you can make it significantly
faster tuning the options.

> If you add some Intel-Core 2 specific options yourself, I would be
> interested, what they are, and in what speedup they really result.
> For Athlons, I never found a significant difference between enabling
> AMD architecture or just using the default configuration.
I used --march=opteron, and that gives a +3% on a core2duo compared to
--march=pentium4, while working on all recent machines (but apparently
not on your Athlon XP :) ). I switched back to --march=pentium4

Tell me if it works now (hopefully),
Cheers,
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> I didn't know you HAD to type a level option.

Yes, sorry for that user NON-friendly behavior. It is simply an
historical behavior, and I wanted to change the less number of things
for this release.
I will at some point add that to the FAQ :).

> This is all quite a bit confusing
Sorry again about that. Actually I wanted to make it much more
user-friendly, but I really ran out of time, and so I have to decide
to do what I could do in the time I had, which is not what I wanted to
do ultimately

> but I think I have a working version of mogo.
That is a good news then :)

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> It doesn't matter - if I do --19 the same behavior,  I can not longer
> type gtp commands in a shell - it goes into self-training.

That is not normal.
You mean you typed:

./mogo  --19

and it does not go to gtp mode?

> If I start like this:   ./mogo --nbThreads 2
>   It ALSO goes into self-training and gtp commands do not work.
That is normal. First option as to be either --9 or --19.

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

Re: Solved! Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> auto-numbering in GoGui prepends all commands with an integer ID,
> which is sent to the program and should be used by the program in
> its response, see the GTP specification.

Ok, I did not know that, thanks. So that part of GTP is simply not
supported in MoGo :).

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

Re: Solved! Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

Ah, now that makes sense, the additional number you posted on your
email was actually sent to MoGo, and I understand now why it did not
work.

Thank you for having solving it, and let us know :)

Sylvain

2007/9/10, Hideki Kato <[EMAIL PROTECTED]>:
> It's just setting of Gogui.  When I turned off the auto-number
> feature, mogo worked fine.
> # Settings -> Configure Shell -> Auto number
>
> Cheers,
> Hideki
>
> Sylvain Gelly: <[EMAIL PROTECTED]>:
> >> I guess the search path you've coded is something wrong or different
> >> depends on the distributions.
> >The "search path" is simply "."
> >
> >> I'd like to suggest to use some
> >> environment variable dedicated to mogo.
> >I think the recent version of gogui let you define the "working
> >directory". Also, as Guillaume, said, you can simply copy the files
> >into gogui/bin, or not play with database :p.
> >
> >
> >> I think it's not so strange.  It's just depending on the distribution
> >> or dynamic libraries mogo uses, I guess.
> >It should not depend!! I simply use fprintf, which is standard!
> >
> >> Are you flushing stdout and stderr explicitly with or without lock?  If 
> >> so, when and from
> >> what thread?
> >The communication is not multithreaded, and everything is flushed.
> >The strangest thing is that it works almost everywhere but not on your
> >machine. That is really confusing :(.
> >
> >Best,
> >Sylvain
> >___
> >computer-go mailing list
> >computer-go@computer-go.org
> >http://www.computer-go.org/mailman/listinfo/computer-go/
> --
> [EMAIL PROTECTED] (Kato)
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> I guess the search path you've coded is something wrong or different
> depends on the distributions.
The "search path" is simply "."

> I'd like to suggest to use some
> environment variable dedicated to mogo.
I think the recent version of gogui let you define the "working
directory". Also, as Guillaume, said, you can simply copy the files
into gogui/bin, or not play with database :p.


> I think it's not so strange.  It's just depending on the distribution
> or dynamic libraries mogo uses, I guess.
It should not depend!! I simply use fprintf, which is standard!

> Are you flushing stdout and stderr explicitly with or without lock?  If so, 
> when and from
> what thread?
The communication is not multithreaded, and everything is flushed.
The strangest thing is that it works almost everywhere but not on your
machine. That is really confusing :(.

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

[computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

Hi all,

Thank you for all your comments and reports, and I am pleased some of
you are happy to use it. Please feel free to share the links,
especially for players who do not read this list.

I am sorry it does not work for some of you. I will look into it as
soon as I can.
BTW, I tried to answer everyone question, but as there were many
emails, maybe I missed some. Please don't be offended, and ask again
the question ;).

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

Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> I think gogui is in fact looking for files in the directory from which
> it is launched. Try this to copy the opening database in this directory.
Yes exactly, thank you Guillaume for explaining better than I can :p


> It runs perfectly on an Opteron 2.6GHz.
Good!
> But not on a Power5+ processor.
What is that? Never heard about such a processor :).
What is the error?

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> Is there a option like gnugo's "--capture-all-dead"?
> In my test(./mogo --9 --time 1),  seems mogo  passed when not  capture 
> alldead stones.

As this release is mainly for humans to play, it is set to play
against humans, so passing as soon as the opponent passes and it is
"safe" to pass.
If you really want it not to pass, you should add a
"--playsAgainstHuman 0"

(I am not exactly sure of the exact spelling of the option and I can't
test from here. Let me know if it does not work).

> By the way, is "--time 0.1" valid?
Yes


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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> when I run the Linux exeutable on my Fedora 8/Athlon XP, I get a
> coredump:
>
> $ mogo --9 --time 12
> Load opening database opening succeed (nbEntries=618) (nbIllegalMoves removed
> 0)
> tried to open opening, success 1
> Illegal instruction (core dumped)
>
> could it be that it is compiled for specific CPU architecture?

Of course it is :).
Ok, good (well, rather sad :)), to know that it does not work on
Athlon XP. I should rebuild with an older architecture then (but it
will be slower :-( ).

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

Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> >> tried to open opening, success 0<-- in grey
> >Here it does not find the file, because the file is with the binaries
> >and gogui (at least your version) looks into the gogui/bin directory.
> >But that does not prevent MoGo to work.
>
> I guess so, as when I added "--useOpeningDatabase 0" it's almost the
> same except the message.

As I read my sentence, it was not clear :). I meant "because the
opening file is in the same directory as the mogo binary"

> MoGo works fine with command line. Say,
> genmove b
> = E5
> genmove w
> = G6
> with lots of trace messages and the board in ascii.

Ok, so obviously it is something in the communication with gogui, that
is so strange, especially that it does not happen for me...

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> Well, I'm hoping for a Mac version someday...

Hopefully it will happen. As I don't have a Mac, I rely on external
help. I'll let you know :).

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> I'm a little confused.   If I operate with no parameters it works ok,

No parameters means --19

> but if I do ./mogo --7  (for instance) it goes into some kind of 
> self-training mode.

Did you see a --7 option on the manual? :-p
There is no "--7" option, nor a "--13" one. You should put a --9 or a --19.
BTW, I am not sure this version can actually play in 7x7 (maybe, maybe
not). For the 13x13, I guess the --19 is more appropriate.

> If I go with no command line options, I can set any board using gtp
> commands but I can't change the number of processes used.

The number of processes can only set using --nbThreads x in the
command line. It really does not work for you? That is puzzling!

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

2007/9/10, Don Dailey <[EMAIL PROTECTED]>:
> The command line parameter to change board size does nothing.
>
> I tried:
>
>./mogo --19
>./mogo  -19
>
> and it only seemed to want to play on 9x9 boards.Am I doing
> something wrong?


As I explained earlier in an answer, the command line parameters only
affects some tuning, but MoGo trusts the GTP commands. You have to
specify at some point "boardsize xx"

> A similar problem with the levels - it doesn't seem to matter what time I set.
Ah, that would be a problem. I can't test from here, I will test tonight.

> Does the command line parsing work?
It would be a shame if it does not work, does it ;)

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

> Have you tried Visual C++?
> http://msdn2.microsoft.com/en-us/express/aa975050.aspx

The thing is that VC++ does not have the pthread library.

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

Re: [spam probable] Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

2007/9/10, David Stafford <[EMAIL PROTECTED]>:
> What are the options for someone who would like a dan-level opponent (even if 
> it's 9x9)
> but doesn't have a Linux system currently?  Are there choices other than 
> MoGo?  If not,
> I'm willing to build a Linux box but I have some questions:
>
> - Is a quad-core Xeon better for MoGo than a higher-clocked Core 2 Duo?
> - How much RAM?
> - Which Linux distribution has it been tested with?
It has been tested by myself on Mandriva 2006, Mandriva 2007, debian
"a recent one", ubuntu "a recent one", and be others on this list
which reported a working MoGo :).

For the hardware question, 512 Mo RAM is enough in common use, and the
"tree garbage collector" is by default set to use less than 400 Mo
RAM. Of course you can change it to use more RAM.
For the speed, it is difficult to say, but let's say that you loose
20% to go from 2 CPUs to 4 CPUs at same clock. It is an approximate
rule, and it also depends on how long you let him think: the longer it
thinks, the bigger is the tree, the more time it spends in the tree,
the less efficient is the multihreading.

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

Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> I had a similar issue where pthread/gcc/cygwin combination produced a very
> slow application. I had better success with Visual C++ and Boost (for
> portable threads).

You are right, I should have used Boost for the threads...
Unfortunately, I used pthread, and that mean that the threading part
have to be rewritten to use boost instead :-(.

> Where and when can we read your paper?
You mean my thesis? I defend the 25th september, and then I have to
make some corrections to it, so let's say beginning of november?
Yet, you can read our papers, available on MoGo's page, which contain
almost everything.

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

Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> BTW, MoGo doesn't work well with gogui 0.9, Fedora Core 5 and Core 2
> Quad system.
Really? Argh :'(

> 00:00 1 name
> tried to open opening, success 0<-- in grey
Here it does not find the file, because the file is with the binaries
and gogui (at least your version) looks into the gogui/bin directory.
But that does not prevent MoGo to work.

> ? error_message <-- in red
> The arguments to MoGo are "--9 --time 12".
> This seems that MoGo sends extra linefeeds to gogui or some I/O
> sync problem, but it's just my guess.

That is so strange, everything works perfectly for me, with exactly
the same version of gogui! It also works on windows with the latest
gogui. Also it had always worked with cgos and kgsGtp without any
problem of this type.
Does it at least works for you using gtp in command line? Could you
open me an access to your machine, so that I can test and find what
happens? Sorry for that. Does anyone else have a problem?

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

Re: [computer-go] Re: Binary release of MoGo

[Sylvain Gelly]

> Try MinGW (and MSYS).  MinGW has GCC ver. 4.2.1.
> http://sourceforge.net/project/showfiles.php?group_id=2435

Yes, I saw that and tried. But the thing is that MoGo use pthread
library for multitreading, and, as far as I know, MinGW does not
provide pthread (does it?). It is why I needed cygwin. It seems that
some succeed in compiling gcc 4.2 on cygwin, but it seems really
painful, and I can't allocate so much time to do that... I guess that
cygwin will eventually release a modern compiler :-).

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

Re: [computer-go] Binary release of MoGo

[Sylvain Gelly]

2007/9/9, Brian Slesinsky <[EMAIL PROTECTED]>:
> Are there any plans to release the source?
I don't think so. Plus, some will work on MoGo source code, so it is
their decision, not mine.

> Perhaps someone else will figure out how to port it.
Well, it actually builds and work on windows, "only" the speed is an
issue. I should try if the speed is the same on linux with such an old
compiler. My guess is that it is really a matter of compiler version.
(even if it seems incredible to have a +100% speed only with the
compiler!).
Maybe it is also a question of libc version?

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

[computer-go] Binary release of MoGo

[Sylvain Gelly]

Hi all,

I am pleased to announce a binary release of current version of MoGo.
It is specially designed for players but of course it may be
interesting for some of you as a benchmark.
You download it and see the instructions there:
http://www.lri.fr/~gelly/MoGo.htm

Of course, please feel free to talk of it around you, share the link,
and put the link on your webpage :). Please distribute the link but
not the package directly, so that I keep track of the distribution,
and maybe put some fixes, so that people always get the latest
version.

Unfortunately, only the linux version is available (for the moment?).
I wanted to wait for the windows version to be available at the same
time, but it is 2 times slower than the linux version(!!), so I
decided not to distribute it for the moment. I use cygwin for that,
and maybe the reason is that cygwin has only gcc 3.4.2, and which
produce a much slower binary. If anyone has a solution, I would be
pleased to put the windows version as soon as possible.

I would also take this occasion to say "goodbye" to you all, and thank
you for all the discussions. I now finished (and almost defended :))
my PhD, and my work on MoGo is finished. So it is very likely that I
will not make any further contribution to MoGo. I would like to say
that I spent a very good year in the computer Go community, with of course a
warm special thank to Yizao. Of course, I will follow the future
discussions on this list with pleasure.

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

Re: [computer-go] Slides for Villach-EC Lecture

[Sylvain Gelly]

Hi Chrilly,

It was always the goal of McCarthy and his followers to simulate and to surpass
the human mind. (...)
UCT has nothing to do with human Go. It has some similarity to the behaviour
of ant-collonies (its not in the technical sense an ant-colony algo). It was
never the goal of AI to explain ants.


Ok I understand your point. For me the goal of AI is not to explain
the human mind, and even less to try to imitate it. Intelligence is
not about how it works, but what it does. If it seems intelligent,
then it is. Are animals and human intelligent? They seem so they are:
it is simply an ill-defined question.



How would you define modern AI? Obviously it is not the classic approach to
mimic humans anymore. But what is it?

For me it is when "we" (I was not there :-)) become less philosophical
and more precise about what we want. We want a system which use data
to improve itself in order to adapt to unseen situations. What is a
good learning? In supervised learning we have some answers, as what is
over-fitting, how to avoid it, how to handle well non linear and
structured data (e.g. with kernel methods). In control problem, ie
reinforcement learning, which is for me the big challenge, and were
big applications are, many questions are still fuzzy, but modern AI is
for me trying to make them well-posed, not doing philosophy on how
intelligence could arise, or how it works in human mind (which is so
complicated).



What do we learn about the human mind from UCT?

Nothing and that's not the goal, I simply don't care. If you really
want to learn from human mind, do cognitive science, not AI. Maybe one
interesting thing we can learn is that there is not only one way to
make things intelligent, but many.

Sorry to have been somehow philosophical here, I'll stop :-).
Sylvain
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Slides for Villach-EC Lecture

[Sylvain Gelly]

Hi Chrilly,

I am sorry about your fight with a dog, and I hope you are ok!

I read your slides: interesting point of view, whereas you seem a
little frustrated. Thank you for sharing your opinion.

However, I have to disagree with this statement:
"UCT: Complete Antithesis to AI-approach"

I really thing it is exactly a modern AI approach!! Also it is a
general algorithm applied to many different domains (and many are not
two player games, ie max-max problems and not min-max).

I think it is exactly the bad example for the "anti-drosophila thesis"...

Cheers,
Sylvain

2007/7/21, chrilly <[EMAIL PROTECTED]>:

Attached are Powerpoint-Slides for a computer-Go-lecture I should have given
tomorrow (Sunday 21.07.07) at the European-Championship in Villach/Austria.
I think the final conclusion fits to the cancellation of the Gifu
tournament. I did not know this when preparing the slides.

Unfortunately I had to cancel the lectures, because at an attempt to stop
the fighting between my dog Bello and his village-rival Max I was
considerable bitten by Max. Normally the owner of Max and myself let them
fight. It looks like they would kill each other, but in fact nothing serious
happens. But this time I wanted to play the hero and Max was not pleased
that I interferre into dog-internal affairs (neither was Bello).

Maybe the slides are of interest.

Chrilly

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



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

Re: [computer-go] Why are different rule sets?

[Sylvain Gelly]

Hi Chrilly,

Take a look at this list, there are already maybe more than 100 posts
on this subject. While I agree with you, just don't worry, almost all
computer go games are with the same set of rules, just ignore the
rest.

Cheers,
Sylvain

2007/7/12, chrilly <[EMAIL PROTECTED]>:

I am playing competitive tennis-table. There were for years a heated debatte
if the ball-diamater should be increased from 38 to 40mm and if the set
shall go to 11 instead of to 21. A few years ago, the decision was taken to
play with the 40mm ball to make the game slower and in turn to reduce the
set to 11.
Since then Chinese, Japanese, Korean and the rest of the world play with
40mm and stop at 11. After a short transition time, there is no discussion
at all about the new rules. Tennis, soccer, chess  is played all over
the world in the same way.
Why is it not possible to establish uniform rules in Go? Is there not
something like a FIDE or a FIFA ?

Chrilly

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


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

Re: [computer-go] Explanation to MoGo paper wanted.

[Sylvain Gelly]

Hi David,


>> (...) I cannot imagine that progress will be
>> made without a great deal of domain knowledge.
> Depending on what you exactly mean I disagree.
I mean progress by the standard usually applied to computer Go:
programs that can beat 1D humans on a full board, and then get
better.


For me progress meant an improvement, not a goal :-).
Anyway, very few months ago almost everyone in this list said that
UCT/MC was only suitable for 9x9 Go, which was said not representing
the Real Game Of Go, and will never (in near future, or even in far
future) do well in 19x19. Today, some UCT/MC based programs, e.g.
MoGo, can give 5 stones to gnugo on 19x19 in 30 minutes game, without
any additional go knowledge. For me it is an evidence that progress
can be made very quickly without "great deal of domain knowledge". Why
we (by "we" I mean the all community) could not imagine other
improvements? 1D humans on a full board is not so far, contrary as you
seem to say...



I am less sure that knowledge representation in the
classical programs is the right expertise for its representation in the MC
playouts.

Yes, maybe you are right, I don't know. But I think it is not a bad
expertise :-). And also it is a very "expensive" expertise (in the
sense that it takes a lot of time to get).


So many thing yet to do!

To me it sounds like a good news, don't you think? :-)

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

Re: [computer-go] Explanation to MoGo paper wanted.

[Sylvain Gelly]

Hi,


> I'm on the other side of this issue. In my opinion all kinds of go
> knowledge are fair game and I'm rather disappointed that so small
> amounts of domain specific knowledge have been merged with the UCT
> search approaches.
>



I agree. I really do not understand why using domain knowledge would
be a problem for some people.


Maybe one big reason is that domain knowledge is really hard to get
right. A lot of man power is needed to have a program with non
ridiculous go knowledge, higher than any other ideas that have been
successful in UCT.


It seems to me that this opinion is held
by programmers with less Go knowledge who hope that pure search is
an answer.

Maybe they believe that there is a lot of room for improvement without
go knowledge, and other will put the go knowledge because they are
stronger in that part. Isn't it the way research goes forward?


(...) I cannot imagine that progress will be
made without a great deal of domain knowledge.


Depending on what you exactly mean I disagree. Progress has been made
without "a great deal of domain knowledge" and there are many
improvements in the algorithms we can make. That does not prevent
using domain knowledge!


I think that the
next big trick will be in getting the domain knowledge into the form
that the MC methods can use efficiently.


I agree that it is ONE OF the next big trick. But people with
experience in the "classical" programs are much more suited for that
than "new comers". On the other side, there are plenty of other ways
to improve.
My point is that there are not mutually exclusive.

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

Re: [computer-go] 9x9 games wanted and the next big challenge

[Sylvain Gelly]

Hi Chrilly,

1) there are database of thousands of professional games for few
dollards. There are not 9x9, but (i) making database is not making
progress in the field, it is just having some temporary advantage in
tournaments. (ii) Opening is much less important in Go than in Chess,
it is why we are not so crazy about opening. At least at the current
level of programs. (iii) 19x19 Go is the real game, and you can get as
many games as you want, just clicking on three links.
2) interfaces are good enough for what we need, and tournaments as
CGOS or KGS are good tools to take the current temperature of field.
3) seriousness can't be measured as the short term money you can make
directly selling your work. I understand that you think that
researchers are paid just to play writing useless papers for themself.
But there are not more stupid than others, and maybe they think they
are doing something useful, even if it can't be measured by the direct
sell of what they produce.
4) I guess people that sell commercial programs are making money.

All that said, I agree that computer go is certainly much less mature
than computer chess.

Sylvain


I have read dozens of times that computer-Go is the next big challenge.
But in fact it is a completly amateuristic field where even the most basic
things are missing. As a chess programmer I did not even think about, that
it is a problem to get a good game collection. There are no proper
interfaces, no serious tournaments, a wired data standard...
AND there is no money involved:  For professional programming I get 60Euro/h
(1Euro=1.35$).
2.000h x 60 = 120.000 Euro.
This equation is of course completly wrong. One can not make in 2000h a very
strong Go programm and one can not earn 120.000 Euro with it.
A more realistic equation is;
20.000 Euro/5000h = 4Euro/h.

The minimum wage (by law) is in Austria 6Euro/h. Obviously Go programming is
even more unqualified than washing dishes in a restaurant.

If it would be really a big challenge, there would be some money. In chess
nowadays there is also no money. But once it was a good business and there
was some considerable money for Deep Blue and on a smaller scale also for
Hydra, there was Don's project at MIT, one got a big Cray for Cray-Blitz,
Ken Thompson build a chess engine
Its like some hobbyst engineers and hobby-pilots would try to fly to the
moon.
Its probably only good for to write some academic papers. In this case its
even an advantage that everything is so amateuristic. The general level is
low and one can be the one-eyed king under blind ones.

Its clear to me that things are as they are in the West. Go is played only
by a small freak community. But if it is so important in China/Korea/Japan
why is'nt there something like Fritz and ChessBase? Or does it exist and we
are living in a completly other Go-world?

Chrilly

P.S.: I do not want to offend anyone in this list. Everybody here does his
best. I am just feed up with the things as they are.



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

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


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

Re: [spam probable] [computer-go] scalability study - final results

[Sylvain Gelly]

Hi Don,

This is a very interesting study!

Sylvain

2007/6/25, Don Dailey <[EMAIL PROTECTED]>:


Someone just reminded me of the scalability study I did a few months
back and I reported that I would continue to run it for perhaps a few
more weeks.

I did run about 20% more games, but the data was quite useful because
it increased the number of games sampled for the highest levels.  I had
started the highest level program late but the auto-tester is designed
to try to equalize the number of games played for each player.

As a reminder, the study was designed to test the improvement of
modern UCT programs as the number of play-outs increase.  In the
study, I had two basic versions, each testing at 12 different levels.

The L series is Lazarus running with "lite play-outs" and the H series
is Lazarus running with "heavy play-outs."  Since the study, Lazarus
has actually improved significantly, so these are both older versions
of Lazarus - still relatively strong and perhaps better candidates for
a study of this type since the older programs tend to be more
universal (less prone to serious intransitives.)

I don't have a graph like I did before, but one can easily be
constructed by the data:

--- Player Key ---

   H_  is heavy play-out version of Lazarus
   L_  is light play-out version of Lazarus

   The numeric portion of the player name describes how
   many play-outs were executed to play each move.


PLAYERTIME/GME   RATING  GAMES   Total games: 2895
    ---  -
H_204813350.17   2830.2168
H_1024 6693.84   2768.0169
H_0512 3147.28   2547.3168
H_0256 1547.30   2399.3168
L_2048 4549.37   2375.5168
H_0128  758.64   2315.7168
L_1024 2203.88   2287.8169
H_0064  381.00   2240.3339
L_0512 1064.80   2174.1168
H_0032  214.12   2129.2318
L_0256  523.12   2105.7168
L_0128  258.54   2097.8170
gg-3.7.9 68.97   2000.0307Standard GnuGo 3.7.9
L_0064  134.17   1981.7293
H_0016  125.93   1950.2284
L_0032   72.72   1941.5284
H_0008   62.27   1872.4276
L_0016   43.49   1758.6261
H_0004   31.22   1679.1253
L_0008   21.07   1556.2248
H_0002   14.90   1402.1250
L_0004   10.55   1347.0248
L_00025.03   1123.6248
H_00017.44   1031.6249
L_00012.49863.6248



Observations:

If you look at the entire range of the HEAVY player, you will notice
that each doubling (on average) was worth 164 ELO points.

You will also notice a gradual falloff in improvement as the levels
increase.

As a general rule of thumb, there is about 150 ELO per doubling.  I
figured this by throwing out the highest and lowest rated HEAVY player
and averaging the increase per doubling.  It seems pragmatic to throw
out the 2 extremes based on empirical observation - I have always
noticed that in a pool of players the highest and lowest often have
at least somewhat distorted ratings.

After throwing out the low and high ratings the top 5 players average
about 132 ELO per doubling and the bottom 5 average an increase of
about 210 per doubling.

So there is a definite decrease per doubling, but it's quite gradual.


I did a similar study with 7x7 and found that the tapering is extremely
pronounced.  It was quite obvious which komi to use, because if it was
too low black won every games, if it was too high white won every
game.  The tapering was pronounced because at higher levels the play
was very close to perfect.  If you are playing perfect, there is no
improvement to be had by doubling.

It appears as a general rule of thumb, (and is supported by empirical
evidence in similar studies of other games) that the rating/resource
curve is almost linear when you are far away from perfect play but
gets pronounced as you approach perfect play.  I suspect Lazarus at
the highest level I tested is within a few hundred ELO points of
perfect play.  It's still a long way off, especially considering that
Lazarus at the highest level was spending almost 4 hours on each 9x9
game!

My auto-tester stores all data, including configuration in a single
sqlite3 database.  In it are the SGF game records, individual results
and even time spent on each move and it's available to anyone who
wants it upon request - so you can analyze the results for yourself
and come to your own conclusions!

- Don



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

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

Re: [computer-go] MoGo paper at ICML

[Sylvain Gelly]

Hi,


In the paper you only present results of UCT_RAVE with the MoGo

default policy. Did you run tests with UCT_RAVE using "pure" random
playouts too?



Yes we did, and the improvement was also huge, but I don't remember the
exact results.

I'm curious because I've tried millions ( well, it feels that way ) of

uses for AMAF in my code... but so far all of them have been proven
useless, often yielding worse results.



I have to admit that it took me several weeks to make the RAVE algorithm
actually work, although the idea is so simple. That maybe explain your
previous results.
The description in the paper should be sufficient to make it work well.

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