Re: [computer-go] Mogo Opening, Building Strategy ?
Is there any theoretical reasons for the Mogo Opening being built out of self play, rather than by spending time increasing the number of simulations at the root, and after a time, keeping what seems to be the best ? There are practical reasons: our approach can be used with humans or other programs as opponent as well; we can benefit from games launched for other purposes than opening-building; and we can easily parallelize the algorithm on grids. No other reason, at least for me - but these reasons are enough I guess. The alternate approach is nice, but is difficult to use for tenths of years of CPU - whereas using preemptable mode in grids, we can have access to a huge computational power. From a more technical point of view, I think that the idea of using results of games of strong versions of mogo is better for avoiding biases in the MC. But it's only a conjecture. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Mogo Opening, Building Strategy ?
Thanks a lot for your quick answer. By conjecture, i suppose you mean that no experiments yet has been ran as to assess this hypothesis ? I think Sylvain (and maybe just everyone else) has tried at some point to use a UCT decision bot, as a way to get the simulation done. Then using those high level simulations in an other UCT decision tree (or AMAF, or FirstMove wining stats) From what i recall, the results were disappointing. Also don dailey tried to build an AMAF over a bot that would use AMAF as a decision with very little expectation that this would lead to anything worthy. I don't know how hard Sylvain tried at his time. Yet you have this feeling that using High level mogo games as a way to get a simulation done could lead to interesting results. I also have this feeling. For example, it is well known that Mogo-style decision (or crazy stone) lead to very poor understanding of seki (and/or semeai ?) Would'nt the use of high level game as simulation get to better understanding of those really nasty situations ? Then, i guess that if nobody has ever run any experiments, as to get measure of the efficiency of increasing the UCT tree against using high-level-simulation, there must be a reason ... Is it that that it is known it would consume to much time and resources ? Is it that knowing the results of this measure would prove of little value ? If there is a point where high-level-simulations really give a stronger evaluation function, wouldn't it be good to know about it ? Date: Sun, 30 Nov 2008 10:10:14 +0100 From: [EMAIL PROTECTED] To: computer-go@computer-go.org Subject: Re: [computer-go] Mogo Opening, Building Strategy ? Is there any theoretical reasons for the Mogo Opening being built out of self play, rather than by spending time increasing the number of simulations at the root, and after a time, keeping what seems to be the best ? There are practical reasons: our approach can be used with humans or other programs as opponent as well; we can benefit from games launched for other purposes than opening-building; and we can easily parallelize the algorithm on grids. No other reason, at least for me - but these reasons are enough I guess. The alternate approach is nice, but is difficult to use for tenths of years of CPU - whereas using preemptable mode in grids, we can have access to a huge computational power. From a more technical point of view, I think that the idea of using results of games of strong versions of mogo is better for avoiding biases in the MC. But it's only a conjecture. Olivier _ Email envoyé avec Windows Live Hotmail. Dites adieux aux spam et virus, passez à Hotmail ! C'est gratuit ! http://www.windowslive.fr/hotmail/default.asp___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
By conjecture, i suppose you mean that no experiments yet has been ran as to assess this hypothesis ? Yes. The other reasons were sufficient :-) I think Sylvain (and maybe just everyone else) has tried at some point to use a UCT decision bot, as a way to get the simulation done. Then using those high level simulations in an other UCT decision tree (or AMAF, or FirstMove wining stats) From what i recall, the results were disappointing. At least, it has been clearly established that replacing the random player by a stronger player does not imply the Monte-Carlo program built on top of the random player becomes stronger (even with fixed number of simulations) But, it is also clearly established that the building of the opening book by self-play clearly works, whereas it is roughly the same idea. I guess the reason is the difference of strength of the player - a MCTS (Monte-Carlo Tree Search - I don't write UCT here as it is not UCT in mogo) built on top of a perfect player should be a perfect player (this is formally obvious). So perhaps for huge computational power, this approach (building MCTS on top of MCTS) is consistent. For example, it is well known that Mogo-style decision (or crazy stone) lead to very poor understanding of seki (and/or semeai ?) Would'nt the use of high level game as simulation get to better understanding of those really nasty situations ? I hope so, at least for 9x9 and with really huge computational power. (by the way I'm afraid we have to patch semeai manually) Is it that that it is known it would consume to much time and resources ? I think it is really difficult to do that - you have to dump your results unless you have a machine for a huge time without any reboot, also if you want to have a huge computational effort you have to parallelize it - I think this is really hard. But perhaps trying mogo against mogo built on top of a mogo with e.g. 1s/move would be fine... this is easy to organize. Well, it requires some time, and time is always expensive :-) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
On Sun, 2008-11-30 at 13:38 +0100, Olivier Teytaud wrote: But, it is also clearly established that the building of the opening book by self-play clearly works, whereas it is roughly the same idea. I guess the reason is the difference of strength of the player - a MCTS (Monte-Carlo Tree Search - I don't write UCT here as it is not UCT in mogo) built on top of a perfect player should be a perfect player (this is formally obvious). So perhaps for huge computational power, this approach (building MCTS on top of MCTS) is consistent. I've always had this idea that the best way to build an opening book is the best way to build a general playing engine. You are trying to solve the same exact problem - what is the best move in this position? - Don signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
From: Don Dailey [EMAIL PROTECTED] I've always had this idea that the best way to build an opening book is the best way to build a general playing engine. You are trying to solve the same exact problem - what is the best move in this position? When building an opening book, you have the advantage of not playing against the clock. In fact, a good opening book ( one which your game-playing engine knows how to use ) can shave time during the game itself. Knows how to use can be subtle; many joseki depend on knowing the exact line of play, the move choices depend on knowing the exact ( not approximate ) results of ladders and semeai. Against better players, approximate answers tend toward disaster. A book move might work sometimes, not others, and the program won't know the difference. I think the opening book and general playing engine solve similar problems: what is the best move which can be discovered with finite resources? The opening problem must solve an additional side constraint: it must suggest moves which can be correctly exploited by the playing engine, which may have less time and computational power available. A sufficiently broad and deep book can make up for lack of computational resources during the game; such a book needs to know the best refutations for each of many possible plays. Joseki and fuseki books for humans are full of annotations: move a is used when the ladder works; otherwise, b is recommended; c is a mistake, which can be exploited by ... A book for computer programs might need similar annotations. Some programs may need different books, depending on whether they have a fast or slow clock, one or many processors. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
It's true that building an opening book in an automated way can be done off-line which gives us more resources. That's really the basis for this thought that we are trying to solve the same problem. As a thought experiment, imagine some day in the future, when computers are 1 thousand times faster. What would you do with that extra time to make your program more scalable?You might be able to use your book building algorithm, whatever it might be, to find moves for you. If there is a better way, then you would use it instead. But if there is a better way why are you not using it for creating book moves? Of course the details of how to do it may not be exactly the same - because we may be forced to simulate in memory hash tables with disk space for instance, or to deal with other real-world constraints. However I think that at least in principle, we should be doing the same thing. MCTS really feels to me like a superb book building algorithm. Computer Chess books (at least the automated part) are built essentially by taking millions of games from master play and picking out the ones that seem to work best. Those games are like playouts. The moves that score the best are played the most. We have a kind of MCTS here. - Don On Sun, 2008-11-30 at 09:15 -0800, terry mcintyre wrote: From: Don Dailey [EMAIL PROTECTED] I've always had this idea that the best way to build an opening book is the best way to build a general playing engine. You are trying to solve the same exact problem - what is the best move in this position? When building an opening book, you have the advantage of not playing against the clock. In fact, a good opening book ( one which your game-playing engine knows how to use ) can shave time during the game itself. Knows how to use can be subtle; many joseki depend on knowing the exact line of play, the move choices depend on knowing the exact ( not approximate ) results of ladders and semeai. Against better players, approximate answers tend toward disaster. A book move might work sometimes, not others, and the program won't know the difference. I think the opening book and general playing engine solve similar problems: what is the best move which can be discovered with finite resources? The opening problem must solve an additional side constraint: it must suggest moves which can be correctly exploited by the playing engine, which may have less time and computational power available. A sufficiently broad and deep book can make up for lack of computational resources during the game; such a book needs to know the best refutations for each of many possible plays. Joseki and fuseki books for humans are full of annotations: move a is used when the ladder works; otherwise, b is recommended; c is a mistake, which can be exploited by ... A book for computer programs might need similar annotations. Some programs may need different books, depending on whether they have a fast or slow clock, one or many processors. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
- Original Message From: Don Dailey [EMAIL PROTECTED] MCTS really feels to me like a superb book building algorithm. Computer Chess books (at least the automated part) are built essentially by taking millions of games from master play and picking out the ones that seem to work best. Those games are like playouts. The moves that score the best are played the most. We have a kind of MCTS here. Interesting, the book moves are not generated by random playouts, but by professional ( or highly skilled ) players. In the Chess world, what is meant by picking out the ones that seem to work best? My impression is that computer go programs do not, at this stage in their evolution, make good use of professional book moves; too much professional knowledge is actually in the part of the tree which is almost never played in pro-pro games - the how to beat up on mistakes and what not to do when playing against a pro parts of the tree. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
On Sun, 2008-11-30 at 14:33 -0800, terry mcintyre wrote: - Original Message From: Don Dailey [EMAIL PROTECTED] MCTS really feels to me like a superb book building algorithm. Computer Chess books (at least the automated part) are built essentially by taking millions of games from master play and picking out the ones that seem to work best. Those games are like playouts. The moves that score the best are played the most. We have a kind of MCTS here. Interesting, the book moves are not generated by random playouts, but by professional ( or highly skilled ) players. Many chess opening books are created by a statistical analysis of lots of human games. Some books are created by hand. Very tediously. Even the ones created with the aid of human games are sometimes modified by hand, at least the top notch books. But in the context of this discussion we note that books can and are created solely from databases of top quality games. You can get a reasonable book that way. In the Chess world, what is meant by picking out the ones that seem to work best? What I mean is that you look at the statistics of the moves and base your opening book on the moves that gave the best results. You can also go by the moves that are played the most - with the assumption that if they are played a lot they must be good. It is typical to do a combination of both - if it's played a lot and also scores good, use it. I think some have tried mini-max too. It's possible that a move seems to has great success in general, but not if it's responded to in a certain way. It could be that in recent months or years a refutation has been found, and that a move that used to work really well has been found to be bad. My impression is that computer go programs do not, at this stage in their evolution, make good use of professional book moves; too much professional knowledge is actually in the part of the tree which is almost never played in pro-pro games - the how to beat up on mistakes and what not to do when playing against a pro parts of the tree. Even in chess, despite the awesome strength of the programs, human knowledge of the openings still reigns supreme, although it's now the case that computers are helping to build opening theory by finding new moves - in chess these are called theoretical novelties and computers have produced many of them from what I understand. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ signature.asc Description: This is a digitally signed message part ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
You can read about some such novelties found using Rybka here: http://www.rybkachess.com/index.php?auswahl=Rybka+3+book Don Dailey wrote: On Sun, 2008-11-30 at 14:33 -0800, terry mcintyre wrote: - Original Message From: Don Dailey [EMAIL PROTECTED] MCTS really feels to me like a superb book building algorithm. Computer Chess books (at least the automated part) are built essentially by taking millions of games from master play and picking out the ones that seem to work best. Those games are like playouts. The moves that score the best are played the most. We have a kind of MCTS here. Interesting, the book moves are not generated by random playouts, but by professional ( or highly skilled ) players. Many chess opening books are created by a statistical analysis of lots of human games. Some books are created by hand. Very tediously. Even the ones created with the aid of human games are sometimes modified by hand, at least the top notch books. But in the context of this discussion we note that books can and are created solely from databases of top quality games. You can get a reasonable book that way. In the Chess world, what is meant by picking out the ones that seem to work best? What I mean is that you look at the statistics of the moves and base your opening book on the moves that gave the best results. You can also go by the moves that are played the most - with the assumption that if they are played a lot they must be good. It is typical to do a combination of both - if it's played a lot and also scores good, use it. I think some have tried mini-max too. It's possible that a move seems to has great success in general, but not if it's responded to in a certain way. It could be that in recent months or years a refutation has been found, and that a move that used to work really well has been found to be bad. My impression is that computer go programs do not, at this stage in their evolution, make good use of professional book moves; too much professional knowledge is actually in the part of the tree which is almost never played in pro-pro games - the how to beat up on mistakes and what not to do when playing against a pro parts of the tree. Even in chess, despite the awesome strength of the programs, human knowledge of the openings still reigns supreme, although it's now the case that computers are helping to build opening theory by finding new moves - in chess these are called theoretical novelties and computers have produced many of them from what I understand. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
