Re: [computer-go] Re: What's happening at the European Go Congress?
On 13-aug-08, at 00:18, David Fotland wrote: I don't know that joseki knowledge mad Many Faces stronger. Go Intellect always used to turn off the joseki libraries in tournaments against Many Faces, since it had a better win rate if it avoided joseki moves. I suppose that's some evidence that joseki knowledge helps. I think that's not exactly right. Joseki's may help. But another important feature of joseki is it makes the game a lot shorter. Since both sides potentially are going to agree on a long line of play, the whole joseki becomes as if it's one choice. If you play a weaker opponent, your chances improve as the game becomes longer. If I remember well this was exactly the reason Ken Chen sometimes turned joseki off, because he thought the contribution of strength of the joseki was smaller than the longer game-length against opponents he perceived weaker. Against Goliath he turned joseki on, for exactly the same reason. So if anything this is an argument against josekis, apparently it doesn't really add much strength. Against people they helped. But probably also because it helped make the game shorter against what was by then almost by defintition a stronger opponent. And it made people think better of the programs if they saw it play well-known joseki. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: What's happening at the European Go Congress?
Here is my take on joseki and fuseki in computer programs. My older program Viking, had a quite nice patternmatching feature which matched the entire board or smaller parts of it towards a database of 50k games or so. It makes it play nice but as far as I could tell it had no impact on the strength of the program. With 9x9 I have used many systems learned or handmade, but it all boils down to that as been said earlier. It only works for a program that does not change, since it overfits its own strengths and weaknesses. -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: mogo beats pro!
I want to correct my statement in view of a private discussion with Gian-Carlo. It turns out that in theory, with a perfectly ordered search tree, Gian-Carlo is correct that a parallel alpha beta searcher would search the same number of nodes as a serial searcher. It's not what David Fotland was talking about and not what the intent of my response was to him, but I DID make a technically inaccurate statement because I was only right in the case of actual real life programs that do not have perfectly ordered trees. It turns out that a hypothetical program with perfect move ordering would be inefficient for other reasons, but they would not do wasted work. So my correction to the statement I made is this: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. So the point is that real programs do not have perfectly ordered move trees and if they did, they still wouldn't speed up in linear fashion with the number of processors. - Don On Mon, 2008-08-11 at 23:45 -0400, Don Dailey wrote: On Mon, 2008-08-11 at 20:39 -0700, David Fotland wrote: Yes, my alpha-beta searcher still has the big slow evaluation function (about 50 to 100 evaluations a second). When I get some free computer time I'll put it on the 19x19 server. I think it will be much closer to the 1 cpu uct many faces than to the older version 11 many faces. Uct also has the advantage that it is much easier to use with multiple CPUs. I know parallel alpha-beta exists, but my evaluation function is not designed to be thread safe. If I put a big lock around it, there will be almost no SMP scaling, since almost all the time is in the evaluation, not in the search. This is not the case with alpha-beta. With additional processors, alpha-beta always does wasted work, and the more processors the more wasted work. It still always benefits from additional CPU's. - Don David -Original Message- From: [EMAIL PROTECTED] [mailto:computer-go- [EMAIL PROTECTED] On Behalf Of Don Dailey Sent: Monday, August 11, 2008 8:31 PM To: computer-go Subject: RE: [computer-go] Re: mogo beats pro! On Mon, 2008-08-11 at 20:10 -0700, David Fotland wrote: Sorry, but I can�t let this statement go past. The go programs in the 90s did local search, but not much global search. For example Many Faces did a one ply global search, with a variable depth quiescence search. I added an alpha-beta search to Many Faces last year, and it made a huge improvement in strength. So it is not true that alpha-beta pruning hit a roadblock. I never doubted alpha-beta but when you say alpha-beta and GO in the same sentence, people automatically believe the program is going from 99% evaluation to 1% evaluation and 99% stupid. In fact you are still spending most of your time evaluating positions. I'm still not convinced that you can't make a strong alpha beta GO program if you have some imagination. It cannot just be a converted chess program, it has to be different, but still alpha beta at heart. It would have to be extremely selective. - Don For me, the big advantage of UCT/MC is that it eliminates the huge, slow, buggy evaluation function. Simple playouts are much much easier to make bug free. Bugs in the evaluation function caused many losses, and are almost impossible to eliminate in traditional programs, since the evaluation functions are so complex. David It seems that alpha/beta pruning hit a roadblock a long time ago in go. Now we have MC... which as you increase the number of samples.. you start to get closer to an equivalent alpha/beta. But... there are still huge groups of samples that are not checked... and if you want to somehow prove you have the best move... how will you do it? Will you make the sample size equivalent to the number of possible samples? How will you do this practically? You can only state with a certain confidence that you did make the best move and this would be bound by our computational resources. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list
Re: [computer-go] Re: What's happening at the European Go Congress?
On Wed, 2008-08-13 at 14:38 +0200, Magnus Persson wrote: Here is my take on joseki and fuseki in computer programs. My older program Viking, had a quite nice patternmatching feature which matched the entire board or smaller parts of it towards a database of 50k games or so. It makes it play nice but as far as I could tell it had no impact on the strength of the program. With 9x9 I have used many systems learned or handmade, but it all boils down to that as been said earlier. It only works for a program that does not change, since it overfits its own strengths and weaknesses. Yes, even in chess it seems to be best if you match the book to the program.In go it is perhaps not good to even try with a rapidly changing program. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: mogo beats pro!
Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Re: mogo beats pro!
I don't know the answer, but it wouldn't surprise me if it turned out that the same theoretical issues exist for most reasonable tree search schemes. So it is possible that UCT has no superiority over alpha-beta when it comes to making a parallel program. But I don't really know. - Don. On Wed, 2008-08-13 at 16:58 +0200, Magnus Persson wrote: Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. It wouldn't surprise me if it turned out that UCT has no superiority over alpha-beta when it comes to making a parallel program. It has it's own issues, maybe they reduce to the same issue but just in a different context? I don't really know. - Don -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] Re: mogo beats pro!
Not an expert on AB-search or UCT search but there's a subtle difference I think. In AB search, if some processors have been searching in a branch that is subsequently cut off, the work is 100% wasted. In UCT there's no such black-and-white cutting. If you do sampling in what then turns out not to be the optimal branch, further sampling in the optimal branch may cause the UCT-value to drop to a point where you'd otherwise start sampling the sub-optimal branch again. So in that case you gain back part of the 'wasted' work. I'm also inclined to think that the 'chunks' of work that are wasted tend to be larger for AB-search than for UCT. But I'm not 100% sure. Mark On 13-aug-08, at 12:07, Don Dailey wrote: I don't know the answer, but it wouldn't surprise me if it turned out that the same theoretical issues exist for most reasonable tree search schemes. So it is possible that UCT has no superiority over alpha- beta when it comes to making a parallel program. But I don't really know. - Don. On Wed, 2008-08-13 at 16:58 +0200, Magnus Persson wrote: Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. It wouldn't surprise me if it turned out that UCT has no superiority over alpha-beta when it comes to making a parallel program. It has it's own issues, maybe they reduce to the same issue but just in a different context? I don't really know. - Don -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] Re: What's happening at the European Go Congress?
From: Don Dailey [EMAIL PROTECTED] On Wed, 2008-08-13 at 14:38 +0200, Magnus Persson wrote: Here is my take on joseki and fuseki in computer programs. My older program Viking, had a quite nice patternmatching feature which matched the entire board or smaller parts of it towards a database of 50k games or so. It makes it play nice but as far as I could tell it had no impact on the strength of the program. With 9x9 I have used many systems learned or handmade, but it all boils down to that as been said earlier. It only works for a program that does not change, since it overfits its own strengths and weaknesses. Yes, even in chess it seems to be best if you match the book to the program. In go it is perhaps not good to even try with a rapidly changing program. So far, all experience with programs and joseki on 19x19 boards has been with kyu-level programs, since heretofore there have been no dan-level programs on the 19x19 board. The proverb learn joseki, lose three stones may apply to programs, for much the same reason - the program does not know how to exploit bad moves, nor how to preserve the advantages of playing good moves. An approach used for beginners is to learn simpler joseki which are easier to get right, and learn how to deal with common overplays. A common strategy by stronger players is to throw in an overplay which will baffle the beginner, causing him to make an inferior move. These overplays won't ever appear in professional game records, nor in most joseki books; they seem to be passed along by a secret fraternity. Many joseki depend upon an exact calculation of liberties and tesuji; in the recent demo game between Mogo and Myungwan Kim, Mogo won a capturing race by exactly one liberty. Any deviation from correct play would have cost Mogo a considerable number of points. It's hard to be sure with so few sample games, but I guess that Mogo with a ten-minute clock would have failed to find the correct line of play. Hence, any experiments with smaller resources available might have found knowledge of that joseki to be of little or negative value. With the current scarcity of supercomputers devoted to playing Go, it may be impossible to take proper advantage of a pro-level opening book - now. The takeaway for humans and computers seems to be to learn those joseki which you can understand and use well at your current level of skill. Can playouts as presently implemented efficiently exploit joseki knowledge? Can they be designed to do so? ___ 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...
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/
Re: [computer-go] Re: mogo beats pro!
Magnus Persson: [EMAIL PROTECTED]: Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay #po winsgames winning rateELO 1 sigma of wr 0 1,000 721 2,000 36.05% -99.6 1.07% 1 1,000 721 2,000 36.05% -99.6 1.07% 2 1,000 690 2,000 34.50% -111.4 1.06% 3 1,000 663 2,000 33.15% -121.8 1.05% 5 1,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% Hideki Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
this is interesting! perhaps i misunderstand the setup of the experiment -- what is the unit of measure for the delay, or how is delay being implemented? the FIFO queue is doing what, and where is the delay being introduced? thanks, s. On Wed, Aug 13, 2008 at 9:20 AM, Hideki Kato [EMAIL PROTECTED] wrote: Magnus Persson: [EMAIL PROTECTED]: Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay #po winsgames winning rateELO 1 sigma of wr 0 1,000 721 2,000 36.05% -99.6 1.07% 1 1,000 721 2,000 36.05% -99.6 1.07% 2 1,000 690 2,000 34.50% -111.4 1.06% 3 1,000 663 2,000 33.15% -121.8 1.05% 5 1,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% Hideki Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. -Magnus ___ 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] What was the specific design of the Mogo version which beat the pro...
I thought Mogo was written in RPG? - Don On Wed, 2008-08-13 at 09:19 -0700, steve uurtamo wrote: 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] Re: mogo beats pro!
Quoting Hideki Kato [EMAIL PROTECTED]: Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay #po winsgames winning rateELO 1 sigma of wr 0 1,000 721 2,000 36.05% -99.6 1.07% 1 1,000 721 2,000 36.05% -99.6 1.07% 2 1,000 690 2,000 34.50% -111.4 1.06% 3 1,000 663 2,000 33.15% -121.8 1.05% 5 1,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% If I understand this correctly this simulation for delay 50 computes 50 playouts and then updates the tree. In Valkyria I do the following. Every simulation from the root with their own thread updates all nodes as visited down the tree before entering the heavy playout. This means that all moves made in the tree are temporarily updated as losses. When a playout has finished, half of the moves were winners and updated accordingly. The idea behind this is that this hopefully avoids searching the same path over and over again. Have tried anything like this? Also your results shows clearly that there is inefficency. But do you also have results where for example delay 50 also computes 50x1000 simulations so that we can see if what it means in practise? Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
steve uurtamo: [EMAIL PROTECTED]: this is interesting! perhaps i misunderstand the setup of the experiment -- what is the unit of measure for the delay, or how is delay being implemented? the FIFO queue is doing what, and where is the delay being introduced? The UCT searcher pushes a position to the FIFO queue upon the end of each search but the MC simulator does not get the position until the queue overflows. So, the searcher selects optimal arcs based on the older results of simulations by delay times. Especially at beginning, the searcher does blind search and pushes the same positions delay times. Hideki On Wed, Aug 13, 2008 at 9:20 AM, Hideki Kato [EMAIL PROTECTED] wrote: Magnus Persson: [EMAIL PROTECTED]: Quoting Don Dailey [EMAIL PROTECTED]: Yes, UCT is easier to use with multiple CPU's because with additional processors alpha-beta programs do wasted work, unless you are talking about theoretical programs with perfect move ordering, which you aren't. Nice that all is clear about alpha-beta programs. But... does not UCT with additional processors waste a lot of simulations because what would be the optimal path through the search tree depends on the threads that have not finished yet? Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay #po winsgames winning rateELO 1 sigma of wr 0 1,000 721 2,000 36.05% -99.6 1.07% 1 1,000 721 2,000 36.05% -99.6 1.07% 2 1,000 690 2,000 34.50% -111.4 1.06% 3 1,000 663 2,000 33.15% -121.8 1.05% 5 1,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% Hideki Some people reported that more processors helps a lot on large boards, whereas on smaller one there is not much gain. -Magnus ___ 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/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Some thoughts on the event in Leksand
For the European Go Congress computer Go tournaments, I required programs to be actually present. This was a debatable decision, but is not what I propose to discuss now. I did allow people to send in their programs; I think this was a mistake, and the purpose of this email is to explain why. I encouraged programmers to be present in person to run their programs. Those who could not be present in person, I encouraged to appoint operators for their programs. To those who could neither be present, nor find someone in Leksand to operate it for them, I promised to find a volunteer from among the operators already present, to operate it for them. I anticipated, correctly, that it would be easy for me to find such people. Four people sent in their programs, as zip files in emails to my gmail address which I could use in Leksand. On the day before the tournaments I installed and tested these programs on the machines in the playing room; and on the day of the tournaments I persuaded volunteers (Esa Seuranen and Gunnar Farnebäck) to operate them. All of this went smoothly, and there was no problem with any of it, so far as I am aware. However, something easily could have gone wrong. Not all the programs sent as enclosures arrived at the first attempt: gmail seems to reject some types of enclosure. The unzipping was not all trivial, and I was hampered by being unable to read Swedish, which the operating system of all the computers was using. Not all the programs ran first time, and I had to make changes to batch files. Not all the configuration files were correctly set for the tournaments. I was, perhaps, lucky in having two very competent programmers available as volunteer operators. In fact they had to do little more than click on batch files, but things might have been different. So, all the tasks I undertook were easy, and I performed them right. But there was a significant risk of something going wrong. If I had been less competent, or had left less time for preparation, we might now have an entrant complaining Nick, it's entirely you fault my program didn't get to play. All you had to do was edit the batch file to refer to the correct drive letter for where you chose to install the program. Surely you could have managed that? You even did it right for one of the other programs. I don't mind the work, though it took far longer than I had expected. What I want to avoid is the responsibility. If someone messes up the settings of his own program (as happens often enough in the monthly KGS events) it is unfortunate, but he has only himself to blame. If he appoints an operator who messes up, that is also unfortunate, but it is still no concern of the organisers. But if the tournament organiser agrees to help, and then fails to do it right, he has to accept the blame for running an unfair tournament. I would advise all tournament organisers to avoid any risk of this. Nick That all sounds a bit serious, so here's an irrelevant anecdote to lighten the tone. When I first came across microcomputers, in 1981, there was a chess program that ran on them. It played so badly that even I could beat it; so I looked for other challenges, such as to stalemate it. I was surprised by its behaviour when stalemated, which I assume was caused by its being programmed to make the best move it could manage, where being legal was an overriding, but not essential, feature of best move. When it was stalemated, it couldn't find a legal move, so it would make the best illegal move it could find. This was typically to pick up my queen, change its colour, and capture my rook with it. -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
Magnus Persson: [EMAIL PROTECTED]: Quoting Hideki Kato [EMAIL PROTECTED]: Yes, UCT does. From my recent experiments with a delay line (a fixed size FIFO queue) between a UCTsearcher and an MC simulator with RAVE against GNU Go 3.7.11 level 0 on 9x9 (single thread): delay#po winsgames winning rateELO 1 sigma of wr 01,000 721 2,000 36.05% -99.6 1.07% 11,000 721 2,000 36.05% -99.6 1.07% 21,000 690 2,000 34.50% -111.4 1.06% 31,000 663 2,000 33.15% -121.8 1.05% 51,000 642 2,000 32.10% -130.1 1.04% 10 1,000 522 2,000 26.10% -180.8 0.98% 20 1,000 412 2,000 20.60% -234.4 0.90% 50 1,000 82 2,000 4.10% -547.6 0.44% If I understand this correctly this simulation for delay 50 computes 50 playouts and then updates the tree. Not exactly, if I understand correctly. The UCT searcher and the MC simulator is connected by a delay line of fixed size. So, except initial time, the tree is updated on every playout. The playout is sperated in two parts here, the search (descend) of the tree and the simulation, and there is a delay between them. That is, at time T, the tree is updated by the result of the simulation of the position at (T - 50) if the delay is 50. In Valkyria I do the following. Every simulation from the root with their own thread updates all nodes as visited down the tree before entering the heavy playout. This means that all moves made in the tree are temporarily updated as losses. When a playout has finished, half of the moves were winners and updated accordingly. The idea behind this is that this hopefully avoids searching the same path over and over again. Have tried anything like this? I use modifying fpu method (fpu was introduced in the first report of MoGo). It's very simple. Before simulating an optimal arc at a leaf node, the value (fpu) of the arc is decreased a little (value *= 0.99). This avoids simulating the same node if all arcs have the same value or no value (ie. at beginning of UCB1 algorithm) but does not avoid repeated simulations of significantly better arcs. Also your results shows clearly that there is inefficency. But do you also have results where for example delay 50 also computes 50x1000 simulations so that we can see if what it means in practise? As my implementation expands one node on each simulation like MoGo, this happens in practice. NB: this experiment is for a network environment where MC simulation servers return results to a UCT searcher client with very long delay. Hideki -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 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/
[computer-go] MoGo beats pro: The website
Dear all, There were details that were unclear about the victory of MoGo. Hence I created a website to gather useful information about this game: http://www.cs.unimaas.nl/g.chaslot/muyungwan-mogo/ Cheers, Guillaume Message d'origine De: [EMAIL PROTECTED] de la part de Sylvain Gelly Date: mer. 8/13/2008 19:54 À: computer-go Objet : Re: [computer-go] What was the specific design of the Mogo versionwhich 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/ winmail.dat___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo beats pro: The website
If this is aimed at clearing up ambiguity, you should state which way the handicap was given. Sent from my iPhone On Aug 13, 2008, at 2:08 PM, Chaslot G (MICC) [EMAIL PROTECTED] wrote: Dear all, There were details that were unclear about the victory of MoGo. Hence I created a website to gather useful information about this game: http://www.cs.unimaas.nl/g.chaslot/muyungwan-mogo/ Cheers, Guillaume Message d'origine De: [EMAIL PROTECTED] de la part de Sylvain Gelly Date: mer. 8/13/2008 19:54 À: computer-go Objet : Re: [computer-go] What was the specific design of the Mogo versionwhich 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/ winmail.dat ___ 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 beats pro: The website
From: Jason House [EMAIL PROTECTED] If this is aimed at clearing up ambiguity, you should state which way the handicap was given. Oops! Now I need to clean off my keyboard! rotflmao! Mmmm, we already have a hotly-contested estimate that computer programs will play pros on an even basis in ten years time. Shall we now open the pool for computer offers pro a 9 stone handicap and wins? On Aug 13, 2008, at 2:08 PM, Chaslot G (MICC) [EMAIL PROTECTED] wrote: Dear all, There were details that were unclear about the victory of MoGo. Hence I created a website to gather useful information about this game: http://www.cs.unimaas.nl/g.chaslot/muyungwan-mogo/ Cheers, Guillaume ___ 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...
steve uurtamo wrote: 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? MoGo is written in C++. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
Mark Boon wrote: Not an expert on AB-search or UCT search but there's a subtle difference I think. In AB search, if some processors have been searching in a branch that is subsequently cut off, the work is 100% wasted. In UCT there's no such black-and-white cutting. If you do sampling in what then turns out not to be the optimal branch, further sampling in the optimal branch may cause the UCT-value to drop to a point where you'd otherwise start sampling the sub-optimal branch again. So in that case you gain back part of the 'wasted' work. I'm also inclined to think that the 'chunks' of work that are wasted tend to be larger for AB-search than for UCT. But I'm not 100% sure. The problem is that the optimal settings for UCT appear to be much stronger on the exploitation side than on the exploration side, making it much more likely that such work is really wasted. It is not so obvious to me any more what the differences are between a state of the art UCT searcher (i.e. with nearly no exploration) and a state of the art alpha-beta searcher (i.e. with heavy late move reductions). They both just hammer out the mainline deeper until the score drops a bit, or an alternative rises strongly. UCT without exploration is just minimax, no? -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
On Wed, Aug 13, 2008 at 5:00 PM, Gian-Carlo Pascutto [EMAIL PROTECTED] wrote: The problem is that the optimal settings for UCT appear to be much stronger on the exploitation side than on the exploration side, making it much more likely that such work is really wasted. I'm not sure it's that clear. In a node where one move is the clear favorite, and exploitation repeatedly selects it, then the selection of this move would be the same even with slightly outdated information. But in a node with many equal moves, it's more likely that new information will make the best move (by UCT) change. IMO it's pretty hard to waste work in UCT, as each playout adds some information. The question is, how much, and the UCB part of UCT is there to maximize the information we do get. Of course I'm talking about a shared memory model, where the information available to any processor is equal, but might be outdated by at most a few playouts. If you have a MoGo-style distributed model, you are indeed correct. I can see bad moves high up in the tree being explored many times by different processors. I think their distributed model has a lot of room for improvement (but it is of course quite an achievement to get a big improvement on such hardware at all from my perspective). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: mogo beats pro!
On Thu, Aug 14, 2008 at 12:00 AM, Gian-Carlo Pascutto [EMAIL PROTECTED] wrote: Mark Boon wrote: Not an expert on AB-search or UCT search but there's a subtle difference I think. In AB search, if some processors have been searching in a branch that is subsequently cut off, the work is 100% wasted. In UCT there's no such black-and-white cutting. If you do sampling in what then turns out not to be the optimal branch, further sampling in the optimal branch may cause the UCT-value to drop to a point where you'd otherwise start sampling the sub-optimal branch again. So in that case you gain back part of the 'wasted' work. I'm also inclined to think that the 'chunks' of work that are wasted tend to be larger for AB-search than for UCT. But I'm not 100% sure. The problem is that the optimal settings for UCT appear to be much stronger on the exploitation side than on the exploration side, making it much more likely that such work is really wasted. It is not so obvious to me any more what the differences are between a state of the art UCT searcher (i.e. with nearly no exploration) and a state of the art alpha-beta searcher (i.e. with heavy late move reductions). One might consider heuristics like AMAF, pattern knowledge, etc. to be simply a more effective way to guide exploration. The UCB term has no domain-specific knowledge. It works surprisingly well but it should be no surprise that one can do better with domain-specific knowledge. They both just hammer out the mainline deeper until the score drops a bit, or an alternative rises strongly. UCT without exploration is just minimax, no? The move/path selection behaves like a best-first minimax, but where are the min/max operators in the updates? Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Arc vs. Move
Hideki Kato wrote: queue overflows. So, the searcher selects optimal arcs based on the older results of simulations by delay times. Especially at Hi Hideki, You have used the word arc a few times, and it seems to mean move, but I wondered if there was some nuance intended. (E.g. maybe an arc can be a forced sequence of more than one move, or something like that)? 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://darrendev.blogspot.com/ (blog on php, flash, i18n, linux, ...) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Arc vs. Move
Hi Darren,
Darren Cook: [EMAIL PROTECTED]:
Hideki Kato wrote:
queue overflows. So, the searcher selects optimal arcs based on the
older results of simulations by delay times. Especially at
Hi Hideki,
You have used the word arc a few times, and it seems to mean move, but
I wondered if there was some nuance intended. (E.g. maybe an arc can be
a forced sequence of more than one move, or something like that)?
No, the reason I use arc is just because it's one of the pair {node,
arc} in mathematics (at least in my mind :-). In contrast, I use
move for the people who are more familiar with Go than
mathematics.
Hideki
--
[EMAIL PROTECTED] (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts on the event in Leksand
On Thu, Aug 14, 2008 at 5:05 AM, Nick Wedd [EMAIL PROTECTED] wrote: When I first came across microcomputers, in 1981, there was a chess program that ran on them. It played so badly that even I could beat it; so I looked for other challenges, such as to stalemate it. I was surprised by its behaviour when stalemated, which I assume was caused by its being programmed to make the best move it could manage, where being legal was an overriding, but not essential, feature of best move. When it was stalemated, it couldn't find a legal move, so it would make the best illegal move it could find. This was typically to pick up my queen, change its colour, and capture my rook with it. Now there's a feature that would make a tournament interesting... cheers stuart ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: Some thoughts on the event in Leksand
This was typically to pick up my queen, change its colour, and capture my rook with it. Now there's a feature that would make a tournament interesting... If this appeals to you, try Martian Chess or Shogi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
