Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC))
-Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Wed, 7 Feb 2007 5:34 AM Subject: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)) On Wed, Feb 07, 2007 at 12:06:40PM +0200, Tapani Raiko wrote: Let my try again using the handicap example. Let's say MC player is given a huge handicap. In the simulations, it is winning all of its games, so there is no information helping to select the next move. This situation happens in normal games too, once one player is so much ahead that it wins almost no matter what. It leads into really stupid-looking endgames, where live groups are allowed to die, and dead ones are allowed to be rescued. All this could be avoided by a simple rule: Instead of using +1 and -1 as the results, use +1000 and -1000, and add the final score to this. The purpose of the large constant (1000) is to make sure that it prefers any win to any loss (so that large_win + small_loss small_win + small_win). One could even add another term in the result, favouring games that end early (for the winner) or postpone them (for the looser), in hope of allowing the opponent more chances to make mistakes. As far as I can see, this ought to fit straight in to any MC or UCT program. It may not improve the winning chances, but it sure should make the programs play look more reasonable. Just my humble idea. Feel free to shoot down (with serious arguments), and/or use where ever you like. I would like to hear if this makes any practical difference, if anyone tries. Intuitively, it seems like this should work. You only give the winning margin a small weight, or only use it to break ties, or only apply it after the game is already decided. I've tried many variations, as have others, including your exact algorithm above. It can make some moves look a little prettier, but it always causes problems and I have to take it out. I have my theories as to why that is, but for brevity's sake, in my experience, giving any consideration to winning margin is detrimental. After the game is decided, there are more elegant ways to bring it to a close. I came to this conclusion reluctantly. - Dave Hillis Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC))
I should have mentioned that I have only tested on 9x9. For larger boards, I don't know. - Dave Hillis ` Intuitively, it seems like this should work. You only give the winning margin a small weight, or only use it to break ties, or only apply it after the game is already decided. I've tried many variations, as have others, including your exact algorithm above. It can make some moves look a little prettier, but it always causes problems and I have to take it out. I have my theories as to why that is, but for brevity's sake, in my experience, giving any consideration to winning margin is detrimental. After the game is decided, there are more elegant ways to bring it to a close. I came to this conclusion reluctantly. Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC))
If I recall correctly, someone spoke of constraining the opening moves to the 3rd,4th,and 5th lines in the absence of nearby stones, or something to that effect. What was the impact of this experiment? I notice the recent discussion of the need for a lot of thinking time to find good opening moves; would this thinking time be reduced with a better-than-random selection of opening moves during the playouts? If fuseki and joseki databases were used to bias the playouts, would the speed and quality of opening play improve? One concern about using expert knowledge of this sort - what happens when one's opponent plays out of book? Human players often find this frustrating - we sense that moves which deviate from joseki are wrong, but finding the correct refutation under time pressure is not always easy. To address this concern: at least one MC player uses an opening book; would it be profitable to automatically analyze past losses, and devote a few 100k playouts to look for better replies to plays which were favored by opponents in past games? This would be the analogue to advice often given to human players: study your own lost games; look for improvements. Unfortunately, an opening book does not generalize well; learning a better move for position Xi won't help with position Xj which differs by even one stone from Xi. What sort of move generators would cope with the vast number of similar positions? A single stone ( a ladder-breaker or a key point which makes or denies a second eye, for instance ) can make a large difference in the score, but one hopes that MC playouts would discover the negative consequences of moves which are almost but not quite right. Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. http://autos.yahoo.com/new_cars.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC))
What sort of sampling was used for the playouts? For this variable ( incorporating some information about the score vs only the win-loss variable ), does it make a difference whether playouts are totally random or incorporate varying degrees of similitude to good play? From: [EMAIL PROTECTED] [EMAIL PROTECTED] I should have mentioned that I have only tested on 9x9. For larger boards, I don't know. - Dave Hillis ` Intuitively, it seems like this should work. You only give the winning margin a small weight, or only use it to break ties, or only apply it after the game is already decided. I've tried many variations, as have others, including your exact algorithm above. It can make some moves look a little prettier, but it always causes problems and I have to take it out. I have my theories as to why that is, but for brevity's sake, in my experience, giving any consideration to winning margin is detrimental. After the game is decided, there are more elegant ways to bring it to a close. I came to this conclusion reluctantly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Get your own web address. Have a HUGE year through Yahoo! Small Business. http://smallbusiness.yahoo.com/domains/?p=BESTDEAL___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC))
terry mcintyre wrote: If I recall correctly, someone spoke of constraining the opening moves to the 3rd,4th,and 5th lines in the absence of nearby stones, or something to that effect. What was the impact of this experiment? For what it's worth, I tried a number of experiments along these lines and none of them produced any improvement in play whatsoever. I'm still baffled by this. Sylvain says, both in his paper and in a message posted here, that it seems that one must try to constrain moves based on sequences of moves rather than individual moves in isolation. All rather mysterious to me. -Richard ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC))
The tests that involved factoring in the margin of victory while the game was still in play, used pure random playouts (or relatively close to it.) Later, I did some tests with esthetics as a goal in itself, and for these, I used what I call a heavy playout. I doubt that the playout type makes a difference but I don't know that for sure. If there was significant curiosity on this list about a specific configuration, I could probably run a quick test. - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Wed, 7 Feb 2007 12:42 PM Subject: Re: [computer-go] MC approach (was: Monte Carlo (MC) vs Quasi-Monte Carlo (QMC)) What sort of sampling was used for the playouts? For this variable ( incorporating some information about the score vs only the win-loss variable ), does it make a difference whether playouts are totally random or incorporate varying degrees of similitude to good play? From: [EMAIL PROTECTED] [EMAIL PROTECTED] I should have mentioned that I have only tested on 9x9. For larger boards, I don't know. - Dave Hillis ` Intuitively, it seems like this should work. You only give the winning margin a small weight, or only use it to break ties, or only apply it after the game is already decided. I've tried many variations, as have others, including your exact algorithm above. It can make some moves look a little prettier, but it always causes problems and I have to take it out. I have my theories as to why that is, but for brevity's sake, in my experience, giving any consideration to winning margin is detrimental. After the game is decided, there are more elegant ways to bring it to a close. I came to this conclusion reluctantly. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Any questions? Get answers on any topic at Yahoo! Answers. Try it now. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
