Some algorithms are special-purpose by nature. What I sketched is an approximation of my understanding of how strong players defeat weaker players with large handicaps. When Myungwan Kim faced off against MFG a few days ago, with a 7 stone handicap, he had to come up with a strategy which would ultimately win a theoretically unwinnable game.
When two pros face off, and one has a 7 stone handicap, the expectation is that the one with the handicap will not merely win, but win by 70 points. A pro with such a large handicap would be satisfied with nothing less. The Nihon Ki'in has published a book of pro-pro handicap games, where black exploits the full power of the handicap stones to give white a very thorough drubbing. David Fotland might have some insights into how MFG viewed that game. Perhaps MFG thought it was so far ahead that it was indifferent about the various opening moves. Who cares if the win rate is 99.9998 or 99.99997? But there are differences, which weaker players use to hang on to as much of their advantage as possible, and stronger players use to wear down that advantage. It becomes a war of attrition - whoever runs out of troops or ammo first loses the war. Terry McIntyre <terrymcint...@yahoo.com> “We hang the petty thieves and appoint the great ones to public office.” -- Aesop ________________________________ From: Don Dailey <dailey....@gmail.com> To: computer-go <computer-go@computer-go.org> Sent: Wednesday, August 12, 2009 2:11:58 PM Subject: Re: [computer-go] Dynamic komi at high handicaps The problem with MCTS programs is that they like to consolidate. You set the komi and thereby give them a goal and they very quickly make moves which commit to that specific goal. Commiting to less than you need to actually win will often involve sacrificing chances to win. Sometime it won't, but you cannot have a scalable algorithm which is this arbitrary. However, if the handicap is too high, the program thinks every line is a loss and it plays randomly. That's why we even consider doing this. Dynamically changing komi could be of some benefit in that situation if there is no alternative reasonable strategy, but it does not address the real problem - which is what I call the "committal consolidation" problem. You are giving the program an arbitrary short term goal which may, or may not be compatible with the long term goal of winning the game. Whether it's compatible or not is based on your own credulity - not anything predictible or that you can scale. And as the base program gets stronger this aspect of the program becomes more and more of a wart. If this can be made to work in the short term, it should be considered a temporary hack which should be fixed as soon as possible. We have to think about this anyway sooner or later because if programs continue to develop and the predictive ability of the playouts and tree search gets several hundred ELO better, these programs may start to see more and more positions as either dead won or dead lost. I'm sure we will want some kind of robust mechanism for dealing with this which is better at estimating chances that the opponent will go wrong as opposed to doing something that is a random benefit or hindrance. - Don 2009/8/12 terry mcintyre <terrymcint...@yahoo.com> Ingo suggested something interesting - instead of changing the komi according to the move number, or some other fixed schedule, it varies according to the estimated winrate. > >It also, implicitly, depends on one's guess of the ability of the opponent. > >An interesting test would be to take an opponent known to be weaker, offer it >a handicap, and tweak the dynamic komi per Ingo's suggestion. At what handicap >does the ratio balance at 50:50? Can the number of handicap stones be >increased with such an adaptive algorithm? > >Even better, play against a stronger opponent; can one increase the win rate >versus strong opponents? > >The usual range of computer opponents is fairly narrow. None approach high-dan >levels on 19x19 boards - yet. > > Terry McIntyre > <terrymcint...@yahoo.com> > > >“We hang the petty thieves and appoint the great ones to public office.” -- >Aesop > > > ________________________________ From: Brian Sheppard <sheppar...@aol.com> >To: computer-go@computer-go.org >Sent: Wednesday, August 12, 2009 12:33:13 PM >Subject: [computer-go] Dynamic komi at high handicaps > > >>>The small samples is probably the least of the problems with this. Do you >>actually believe that you can play games against it and not be subjective >in >>your observations or how you play against it? > >These are computer-vs-computer games. Ingo is manually transferring moves >between two computer opponents. > >The result does support Ingo's belief that dynamic Komi will help programs >play high handicap games. Due to small sample size it isn't very strong >>evidence. But maybe it is enough to induce a programmer who actually plays >in such games to create a more exhaustive test. > >_______________________________________________ >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/
