Re: [computer-go] Reference Montecarlo TreeDecision Bot.
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 tesujisoftw...@gmail.comwrote: 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 magnus.pers...@phmp.se wrote: Quoting Petr Baudis pa...@ucw.cz: 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] MoGo and passing
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 Pellegrinose...@lclark.edu 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
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 Gellysylvain.ge...@m4x.org 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 Pellegrinose...@lclark.edu 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] Rave coefficient
On Tue, Jun 30, 2009 at 12:47 AM, Peter Drakedr...@lclark.edu 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] Incorporating a prior estimate
2009/5/1 Brian Sheppard sheppar...@aol.com: 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.
On Wed, Apr 8, 2009 at 10:46 AM, Darren Cook dar...@dcook.org 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
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 matt...@woodcraft.me.uk 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?
On Fri, Jan 30, 2009 at 9:29 AM, Magnus Persson magnus.pers...@phmp.sewrote: Quoting Sylvain Gelly sylvain.ge...@m4x.org: On Wed, Jan 28, 2009 at 10:01 PM, Isaac Deutsch i...@gmx.ch 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?
On Wed, Jan 28, 2009 at 10:01 PM, Isaac Deutsch i...@gmx.ch 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?
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 tesujisoftw...@gmail.com On Jan 21, 2009, at 10:23 AM, Magnus Persson wrote: Quoting Thomas Lavergne thomas.laver...@reveurs.org: - 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] How to properly implement RAVE?
2009/1/21 Olivier Teytaud olivier.teyt...@lri.fr 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] RAVE and memory allocation considerations
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 i...@gmx.ch 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?
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?
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 sylvain.ge...@m4x.org:
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
Re: [computer-go] How to properly implement RAVE?
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 tesujisoftw...@gmail.com
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_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
Re: [computer-go] How to properly implement RAVE?
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 i...@gmx.ch 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?
Good catch :)Indeed it makes no sense with the *, sorry... Sylvain 2009/1/17 Magnus Persson magnus.pers...@phmp.se I think I found a bug in ChooseMove Quoting Sylvain Gelly sylvain.ge...@m4x.org: 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?
2009/1/10 Isaac Deutsch i...@gmx.ch 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?
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...@gmx.ch 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] How to properly implement RAVE?
Hi Isaac, 2009/1/9 Isaac Deutsch i...@gmx.ch 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] Monte-Carlo Tree Search reference bot
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 computer-go@computer-go.org 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...
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...
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?
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] What Do You Need Most?
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.htmhttp://www.lri.fr/%7Egelly/MoGo_Download.htm http://www.lri.fr/~gelly/MoGo_Download.htmhttp://www.lri.fr/%7Egelly/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] Representation of state-action pairs
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
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
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)
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
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.
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
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
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
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] MoGo 64 bits, mogo double
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] Re: computer-go Digest, Vol 43, Issue 8
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] More UCT / Monte-Carlo questions (Effect of rave)
Hi Erik, (1) They compared Rave to plain UCT. If they would have compared it to a more sophisticated implementation (like the best Mogo before Rave) they probably could not have shown a spectacular improvement. The best Mogo before Rave was very close to plain UCT with the sequence-like simulations. And indeed we exactly compared the best Mogo before and after Rave. There is a table (I don't remember which number), which show the incremental improvements from plain UCT, to Rave, passing by plain UCT with sequence-like simulations. All experiments have been done with MoGo's code, all other parts of the code staying constant. There were not secret part of MoGo disabled to make the improvement of Rave more interesting. One discrepancy between our results and the one some of you observe, as Gian-Carlo stated, is likely to come from the parameters and detail of implementation. We heavily tuned those parameters and details against gnugo, and that makes quite a big difference. I chatted more closely with some of you about details and it did make a difference. Maybe some of you can share what made a change, if you want. Note as well that the current implementation of MoGo (not the one at the time of the ICML paper) use a different tradeoff between UCT and Rave value, thanks to an idea of David Silver, which brought improvements in 19x19 (where the Rave values are the most useful), while it was marginal (still better) in 9x9. But anyway we here are talking about 9x9, so it can't explain what you are talking about. (2) () Depending on the playout policy, adding an upper confidence bound to the rave values can push some terrible bad moves up (like playing on 1-1). The reason seems to be that such moves are normally sampled very infrequently (so the UCB will be higher), and when they are selected (...) That could be an explanation, but there are two points: - the prior you put on top of Rave often avoid to first sample 1-1, and even when you do, you very often loose just 1 playout because of the UCT value you get right away. - I never observed a big discrepancy between the number of Rave samples for each move. Best, Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More UCT / Monte-Carlo questions (Effect of rave)
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] 19x19 Study
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] 9x9 study rolloff
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
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 computer-go@computer-go.org 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] Sylvain Gelly thesis in english
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
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] MoGoRel3_3550pps
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
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
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
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
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] RAVE in MoGo paper
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!
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
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 computer-go@computer-go.org 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 Mailhttp://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
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
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
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
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] Update of MoGo binary release, and windows version available!
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] Re: Update of MoGo binary release, and windows version available!
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] Re: Update of MoGo binary release, and windows version available!
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] Update of MoGo binary release, and windows version available!
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!
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
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] Re: Binary release of MoGo
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: [spam probable] Re: [computer-go] Binary release of MoGo
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] Binary release of MoGo
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: [computer-go] Binary release of MoGo
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
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
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] Re: Binary release of MoGo
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
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] Binary release of MoGo
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] Re: Binary release of MoGo
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/
[computer-go] Re: Binary release of MoGo
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
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/
Re: Solved! Re: [computer-go] Re: Binary release of MoGo
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: Solved! Re: [computer-go] Re: Binary release of MoGo
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: [computer-go] Binary release of MoGo
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/
[computer-go] Binary release of MoGo
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] Binary release of MoGo
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/
Re: [computer-go] Re: Binary release of MoGo
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] Slides for Villach-EC Lecture
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] Slides for Villach-EC Lecture
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] Why are different rule sets?
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.
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] 9x9 games wanted and the next big challenge
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
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
2007/6/23, Yamato [EMAIL PROTECTED]: Using prior knowledge on normal uct, and this was the use of prior knowledge brought about the same improvement. You mean, there is more improvement when using both? I mean that there is no need to have AMAF to get improvement by using prior knowledge. It was gnugo default level, and we thought default was 8, but default is actually 10. I don't see why it is so surprising, I guess it does not change really the level of gnugo. Because I have tested my program against GNU Go level 8 to compare the winning rate with MoGo. Now I see surely there is almost no change. Ok, I understand. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] MoGo paper at ICML
Hello all, We just presented our paper describing MoGo's improvements at ICML, and we thought we would pass on some of the feedback and corrections we have received. (http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf) The way that we incorporate prior knowledge in UCT can be seen as a bayesian prior, and corresponds exactly to the dirichlet prior (more precisely to the beta prior as we here get binomials). The cumulative result is only given using the prior knowledge on top of RAVE, but it could have been done the other way round and give the same type of results. Each particular improvement is somehow independent of the others. On figure 5, the legend of horizontal axis should be m_prior rather than n_prior. All experiments (except the default policy) were played against GnuGo level 10, not level 8. Any other comments are welcome! Sylvain David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] ICGA 2007 MoGo-Steenvreter
Hello all, thank you all for all your precise comments. It becomes pretty complicated and technical for me, I'll try to find out everything :). Bye, Sylvain 2007/6/15, Łukasz Lew [EMAIL PROTECTED]: This is my analysis. It may be flawed but I hope it has some value. It would be very interesting to see what mogo thinks on those variations. Best Regards, Lukasz On 6/14/07, Sylvain Gelly [EMAIL PROTECTED] wrote: Hello Sanghyeon, thank you for your comments. After white (mogo) H2, MoGo was estimating 74%, and expecting: H2 G1 H3 B1 A1 B3 H1 F8 B5 H4 This is far too optimistic. Why would black play H2? :-) Sorry, white played H2. The sequence I gave starts with white move :). Black was expecting to play G1 :). Black played H3, and estimation increased to 81%, white B3 and expecting: B3 B1 A1 B4 C5 C4 A3 C6 B6 B5 After B3 B1 A1, black G1 and then B1 F1 D1 B4 and white is dead. Ok thanks. So good white actually played G1 instead of A1 after black B1 then. Actually during pondering MoGo realized that it was lost then, because black played the expected move (B1), but the estimation was then 50%. MoGo realized too. Actually G1 is an interesting move. After white 48, all groups on the board is alive and white actually wins by my counting. So I think that white 50 is a losing move. Oh, so contrary to what I believed, you say (if I understand you correctly) that the mistake was done in the upper left group and not in the bottom center group? Thank you, 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] ICGA 2007 MoGo-Steenvreter
Hello Sanghyeon, thank you for your comments. After white (mogo) H2, MoGo was estimating 74%, and expecting: H2 G1 H3 B1 A1 B3 H1 F8 B5 H4 This is far too optimistic. Why would black play H2? :-) Sorry, white played H2. The sequence I gave starts with white move :). Black was expecting to play G1 :). Black played H3, and estimation increased to 81%, white B3 and expecting: B3 B1 A1 B4 C5 C4 A3 C6 B6 B5 After B3 B1 A1, black G1 and then B1 F1 D1 B4 and white is dead. Ok thanks. So good white actually played G1 instead of A1 after black B1 then. Actually during pondering MoGo realized that it was lost then, because black played the expected move (B1), but the estimation was then 50%. MoGo realized too. Actually G1 is an interesting move. After white 48, all groups on the board is alive and white actually wins by my counting. So I think that white 50 is a losing move. Oh, so contrary to what I believed, you say (if I understand you correctly) that the mistake was done in the upper left group and not in the bottom center group? Thank you, Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Amsterdam 2007 paper
Hello John, Thank you for your interest. Figure 3 in your UCT paper shows the accuracy of different simulation policies. Could you repeat these experiments for accuracy of win/loss determination only? Actually the labelled positions are rather end game positions, and are labelled as 0/1 (loss/win). So we already are in the case you propose. BTW, experiments in actual play using the best simulation policy with RLGO (by best I mean giving the best MSE) has also been done (given in one table, I don't remember which) and showed the relevance of the MSE measure. (winning rate vs gnugo was around 9% against 8% with random simulation policy). Sylvain So for each test position, you determine if it's won or lost under perfect play, and then see how close each policy gets to either 0% or 100% wins. One might think that this measure of accuracy is what actually matters to UCT, since it is not concerned with margin of victory. Is the advantage of Mogo's policy still as pronounced? regards, -John ___ 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] Efficiently selecting a point to play in a random playout
Hello, When writing C/C++ for multi-platform student assignments using gcc, we always used the args: -ansi -Wall -pedantic Maybe it depends on the gcc versions, but I always use -Wall -W rather than only -Wall. -W turns on (important) warnings which are not turned on with only -Wall, and as usual warnings are much more important than errors :-). I agree that it is not related to what is reported here, sorry :). Cheers, Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Amsterdam 2007 paper
Hi Rémi, Thank you for this paper. I found the work very interesting, well written, and the paper is clear and pleasant to read. As two things are modified in the same time (simulation policy and tree search), I wonder what is the contribution of each part in the overall improvement. For example I wonder what is the exact improvement of the new policy simulation on itself (without modifying UCT) over the one of MoGo. I guess you already have those results, but don't have enough room to put it on this paper. For example, if I remember correctly plain UCT with MoGo's simulation policy at 70k per move was 83% against gnugo 3.6. What is the result with your simulation policy? 85%/90%/95 %/ more? That would help to know where this approach is more usefull: simulation, tree or even both. I mean it is possible that combining the two improvements makes a stronger player that taking the sum of each improvement. If so, that would mean that some win-win effect arises, and the tree search part type has to be related to the simulation type. Again, very interesting work. Sylvain 2007/5/17, Rémi Coulom [EMAIL PROTECTED]: Hi, I first thought I would keep my ideas secret until the Asmterdam tournament, but now that I have submitted my paper, I cannot wait to share it. So, here it is: http://remi.coulom.free.fr/Amsterdam2007/ Comments and questions are very welcome. Rémi ___ 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: Amsterdam 2007 paper
Hi Rémi, 2007/5/17, Rémi Coulom [EMAIL PROTECTED]: to Sylvain: Here are tests of Crazy Stone at 90s/game 1CPU against GNU 3.6 level 10, measured over about 200 games [...] Thank you for your answer. These numbers are interesting. The improvement in the tree search is really huge. It is what I expected and is consistent with my own experiments (different of course, but comparing in the same class). That is good to be consistent, at least we have a chance to understand something :-p. Unfortunately I don't have time in the next weeks to read it really carefully and make (I hope) more interesting comments. But there are already so many interesting comments on the list ;-). Again thank you for this interesting work. Cheers, Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Go, scalability with time vs handicap
Hello Daniel, With the addition of fuseki and joseki library will its rating increase? Especially a fuseki library. Will a fuseki library be consistent with its playing style? That is an interesting and not trivial question. The problem is that the player has somewhere to understand the opening not to destroy it after. The problem is not that MoGo is playing some strange moves, it is that it is happy with them :-). For human players a difference of 2 kyu means that the winning ratio of the stronger player is almost 100%. Is it? Do you have some statistics? If so, that is interesting, because that means that neither MoGo nor GnuGo exploit well (comparing to humans) the handicap stones (see results of handicaps with settings which make them even at H0). My feeling is that it's going to take more than double of speed for MoGo to reach 3kyu. Actually my goal was not to argue about how to reach some rating, but what happens when giving more time against a fixed player with handicap. Also, I feel like the KGS rating is not well adapted to bots rating, because of the inertia. Bots are playing so many games a week that once they reach one stable rating, the rating will change very slowly. Also, strange results happen in MoGo vs human games: white almost always wins! That means the stronger player, no matter the handicap, manages to win the game. That is quite asymetrical. BTW it was one of the reason I launch those experiments, expecting asymetrical results when playing black or white with handicap. This did not appears in those experiments. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
2007/4/11, [EMAIL PROTECTED] [EMAIL PROTECTED]: I watched MoGo playing with different rank of players. Usually 5d players has no problem winning. Starting from 4d begin to lose games. However, part of it is due to most players are not familar with 9x9 Go. Taking this into consideration I place MoGo at about amateur 2d. For professional players consider 9x9 is solved. This is all my opinion. Gnu plays at about 5k on 19x19. Let's place MoGo at 4k on 19x19. Besides the 32 times, it also need to make up the difference between 4k and 2d. I just reported precise and objective experiments which may be interesting results for some. I have no opinion watching the program play, and no way to measure it precisely by subjective opinions. However, maybe it lacks some numbers in my report. On KGS, 9x9, MoGo uses about 40s per move, and on 19x19 (when rated 4kyu) used 15s per move. So it almost 3 times less and I reported that it should be 32 times more (so around 21 minutes per move). In the other way, these 15s per move would be 0.5s per move on 9x9. Maybe it does not continue to scale so well with time, I don't know. However with the times I tested, the scale with the board size is what I reported, and at least the number are precise (many dozen thousands of games). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] (no subject)
Hello, I'm curious to know, how many playouts (in Sensei's 100k is mentioned for CGOS) MoGoBot plays, i.e., how serious version is it? This version plays on a intel core2 duo, and on a 10 minutes game, it makes between 40 and 5 playouts per move (more at the beginning). The current version is the one which participated to last KGS tournament this sunday, and is called MoGo_G3.4bb on the new CGOS. BTW, on CGOS it is rated incredibly weaker than the G3.4 version (lesson n°1 never try new untested parameters on a tournament :-p). I still don't understand how it can change so much between G3.4 and G3.4bb, maybe it is not noticeable for humans? It is really a surprise for me. BTW Don, is it possible to have access to crosstables of old standings on old CGOS (http://cgos.boardspace.net/9x9.html), it may useful for some in some situations to see old versions (at least for some time). I hope I answer here your questions. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
I also find this kind of information very interesting and useful. Now I have a better feel for what kind of scaling is realistic to try for and how to measure it. Putting some recent data points together, it look like giving Mogo 2 orders of magnitude more computer power would result in low dan level 19x19 play? Not the sort of thing one can pull out of a back pocket, but tantalizing. That is quite an large extrapolation. I would rather conclude that we have to find new improvements in the algorithms. But keeping in mind that the scalability with the board size is not impossible. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Hello, 2007/4/6, Tom Cooper [EMAIL PROTECTED]: My guess is that the complexity of achieving a fixed standard of play (eg 1 dan) using a global alpha-beta or MC search is an exponential function of the board size. (...) To some extent, this is testable today by finding how a global search program's strength scales with board size and with thinking time I have experiments of MoGo's playing strength against a fixed player (Gnugo 3.7.10 level 8) on different board sizes and different thinking times. Of course, to meet your statement we have here to assume that the level of gnugo level 8 is a constant with the board size. The results are that in order to keep the same winning rate, you have to increase the number of simulations by something a little larger than linear in the board area. From 9x9 to 13x13, you need something like 3 times more simulations for the same winning rate. Same thing from 13x13 to 19x19. As the time of one simulation is linear in the board area, to keep the same level you have to give a time which increases as power ~2.5 of the board area. So between 9x9 and 19x19, you have to give 32x more time per move for the same play level (always defined as winning rate against gnugo). This is far from being exponential. (maybe if it was exponential, there would be little interest to work on 9x9 go). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The dominance of search (Suzie v. GnuGo)
Here's another way to test this sort of thing that is completely intrinsic to the engine (doesn't require gnugo): Start with and empty board and zero komi. Analyze using UCT until the winning percentage at the root reaches X. Note the number of simulations required (or the amount of time). Repeat for a larger board size. One should probably average N trials at each board size for more reliable numbers. Is that a better measure of playing strength? I don't think so. And if the only advantage is that it does not require gnugo, I don't see the point as gnugo is a marvellous tool, why avoid it? Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [spam probable] [computer-go] MoGo
I can turn the difficulty settings way down so that I have a chance to actually win a game or two. You can always decrease the time per move and at some limit, you'll reach random play. Even if I can't win against MoGo with 300 playouts per move (I am so bad :-( ), but can I beat a random player? :-) Are there any plans for a commercial version of MoGo? No, at least in near future. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
