[computer-go] simple MC reference bot and specification
-- Don SAID : -- David Fotland suggested another rule, tell me what you think. His rule is to stop the game at or beyond move N*N*2 where N is the board size and score the board no matter what. But in the play-outs he first plays 1 move before making this test. If a game actually lasts that long, the play-outs are not worth much but the game is probably over anyway and the board gets scored as is. My own implementation depends on there being no eyes bigger than 1 point, because it's fast and easy to score a board that has only 1 point eyes. But a simple modification makes it work without any appreciable speed sacrifice: If a game ends beyond move N*N*2 then use the slow scoring routine that doesn't assume the board is complete. It should be very rare that this routine has to be used. - Don - Answer : - I like the principle, however the value you propose seems a bit low ... that would mean 81*2=162 for 9x9 right ? I traced the histogram of game size, counting pass On the left the length of the game on the right the number of games that fall into this category. I think you can use a higher value then like N*N*3. Wich may work for larger board as well. (maybe i should try out to get the distribution out of 19x19 ? :) ) -- There are two reason why i do not like counting one stone captures. The first one is that i'm not 100% sure it'll set things right. Obviously limiting game size can hardly have pathological behavior to it, in term of missing an infinite loop case. The second things, is that i tryed at one point to implement some board implementation with bitmaps. I don't remember all the details so maybe i'm wrong. But i'm quite sure i had a way of notplaying ko wrong, while i didn't counted the number of stone captured. Anyway the implementation at this time didn't showed much promise it was like 3k sim/sec while the goal at the time was to get a way to produce between 100K and 200k simulations/sec per processor. Anyway i do not think i really exhausted all the possibilities with bits maps, and i want to give it another shot in the future. Then when considering the size problem, i think it definitely is easier to get an implementation which is 9x9 tuned with bitMaps :) So my suggestion is to make the black box test aimed at 9x9. It may also be a bit easier to give hard values to help people make sure they are bug-free before they try the black box test suite. -- FOR 9X9 : mean score =2.164072737304306 85775.89950308551 Playout/sec Time=11.663847372 Number of playout=1000477.0 Mean moves per sim 111.06255716023456 Game length : number of games in that category 74 : 1 75 : 5 76 : 14 77 : 31 78 : 82 79 : 159 80 : 333 81 : 596 82 : 1063 83 : 1676 84 : 2352 85 : 3529 86 : 4708 87 : 6323 88 : 7840 89 : 9899 90 : 11773 91 : 14314 92 : 16021 93 : 18832 94 : 20376 95 : 22754 96 : 24179 97 : 26590 98 : 27447 99 : 29852 100 : 29532 101 : 31527 102 : 30818 103 : 32565 104 : 3 105 : 31795 106 : 29896 107 : 30761 108 : 28561 109 : 28786 110 : 26408 111 : 26316 112 : 23620 113 : 22981 114 : 20407 115 : 20034 116 : 17571 117 : 16794 118 : 14478 119 : 13761 120 : 11977 121 : 10898 122 : 9505 123 : 8833 124 : 7626 125 : 7494 126 : 6306 127 : 6766 128 : 5661 129 : 7020 130 : 5862 131 : 7856 132 : 6427 133 : 9115 134 : 7349 135 : 10021 136 : 8230 137 : 10263 138 : 8299 139 : 9514 140 : 7923 141 : 8382 142 : 7106 143 : 7183 144 : 5908 145 : 5667 146 : 4894 147 : 4545 148 : 3855 149 : 3424 150 : 2856 151 : 2524 152 : 2022 153 : 1673 154 : 1505 155 : 1295 156 : 1061 157 : 908 158 : 724 159 : 644 160 : 510 161 : 427 162 : 345 163 : 286 164 : 255 165 : 205 166 : 156 167 : 125 168 : 109 169 : 76 170 : 66 171 : 62 172 : 54 173 : 37 174 : 30 175 : 25 176 : 27 177 : 19 178 : 19 179 : 15 180 : 8 181 : 6 182 : 6 183 : 3 184 : 6 185 : 3 187 : 2 188 : 1 189 : 1 193 : 1 FOR 19x19 --- mean score =1.907221916712493 17337.6306463181 Playout/sec Time=57.686659752 Number of playout=1000150.0 Mean moves per sim 455.3779143128531 Komi = 0,5 Amaf Result : ||,000 ||,493||,503||,500||,503||,504||,504||,503||,503||,504||,504||,504||,503||,503||,504||,504||,503||,501||,500||,492 ||,502||,510||,513||,513||,515||,514||,514||,515||,514||,514||,515||,514||,514||,514||,514||,514||,512||,510||,501 ||,500||,512||,515||,516||,516||,516||,516||,517||,516||,515||,517||,516||,516||,517||,517||,516||,514||,512||,500 ||,502||,515||,516||,517||,517||,518||,517||,517||,516||,517||,517||,517||,517||,517||,517||,516||,517||,514||,503 ||,503||,514||,517||,517||,518||,518||,517||,516||,516||,516||,516||,515||,516||,517||,517||,519||,515||,513||,504 ||,504||,514||,517||,518||,517||,517||,516||,516||,516||,516||,516||,516||,517||,516||,517||,517||,516||,513||,503
Re: [computer-go] Anyone With Measures for MiniMax LightSimulations
I've always had this idea that the best way to build a book might also be the best way to build a game playing program. For instance we have done these big studies to determine based on games of Leela and others what the best main line of play is.Computer Chess programs analyze huge databases of games and make tree's sometimes to build opening books. But it seems like this resembles to a remarkable degree a Monte Carlo Tree Search program. - Don On Sun, 2008-10-12 at 11:35 +0200, Denis fidaali wrote: Hi. I recall somehow that don ran some experiments with min-max(alpha-beta) algorithms a while ago. So i wonder if anyone had hard-data about some min-max equivalent algorithms using winrate, and light-simulations. I'd like to know what parameters were used back then, and as much of the actual experiments results as possible (Games against gnugo, scaling, games against amaf bot, cgos rating etc.. as long as it concerns min-maxlight-playout) Thank you in advance. I have made a few tests with AMAFmin-max in the past few days, all giving terrible results. My assumption is that my implementations where faulty. So i have to design a path for getting it right somehow ... Any hard data would help me a lot there in knowing how close i am to having it right. _ Téléphonez gratuitement à tous vos proches avec Windows Live Messenger ! Téléchargez-le maintenant ! http://www.windowslive.fr/messenger/1.asp___ 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] Anyone With Measures for MiniMax LightSimulations
On Sun, 2008-10-12 at 11:35 +0200, Denis fidaali wrote: Hi. I recall somehow that don ran some experiments with min-max(alpha-beta) algorithms a while ago. So i wonder if anyone had hard-data about some min-max equivalent algorithms using winrate, and light-simulations. I'd like to know what parameters were used back then, and as much of the actual experiments results as possible (Games against gnugo, scaling, games against amaf bot, cgos rating etc.. as long as it concerns min-maxlight-playout) Thank you in advance. I tried all kinds of different things and don't have numbers. The basic idea was to use a bunch of MC sims directly as an evaluation function.For instance 1000 simulations. You can use tricks to cut many of these off early when it looks like they will be futile. But I'm sorry I can't report much on them. I found that the best strength/effort ratio seemed to come from reducing the number of play-outs as depth increased. I think such a thing has a chance to succeed if the idea was more fully developed. There are many opportunities for tree pruning and so on that I barely touched on. There is this thing in computer chess called Late Move Pruning which I believe could be applied aggressively, but I barely got into this kind of things. MCTS boils down to highly selective searches with very low branching factors. Modern day chess programs also have very low branching factors compared to a few years ago - so I don't believe alpha/beta is completely out of the question if done right. - Don I have made a few tests with AMAFmin-max in the past few days, all giving terrible results. My assumption is that my implementations where faulty. So i have to design a path for getting it right somehow ... Any hard data would help me a lot there in knowing how close i am to having it right. _ Téléphonez gratuitement à tous vos proches avec Windows Live Messenger ! Téléchargez-le maintenant ! http://www.windowslive.fr/messenger/1.asp___ 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] Anyone With Measures for MiniMax LightSimulations
From: Don Dailey [EMAIL PROTECTED] I've always had this idea that the best way to build a book might also be the best way to build a game playing program. For instance we have done these big studies to determine based on games of Leela and others what the best main line of play is.Computer Chess programs analyze huge databases of games and make tree's sometimes to build opening books. But it seems like this resembles to a remarkable degree a Monte Carlo Tree Search program. Yes, there are analogies. The databases of games in Chess include many high-quality grandmaster-level games, do they not? I hope that Go databases also sample professional Dan-level games, otherwise we're just diving into a pool of ignorance and drawing up a sample. Joseki databases are brittle in a sense. Playing the almost right move is often a failure. I was just reading a particular line in 38 Basic Joseki, where the author commented that if White plays A in a certain diagram, Black should reply with B; a difficult semeai follows, which Black wins by one move if he plays correctly. The result is a gain for Black. On the other hand, if Black does not know how to play that dificult semeai, Black should not start down that path at all; it will be a gain for White. Imagine a program analyzing such a position. Is the program smart enough to figure out the correct way for Black to win the semeai? If so, the program will evaluate White A as a dubious move, and avoid it; if playing Black, will respond correctly and win the battle - and probably the game. But if the program is not smart enough to play the semeai correctly, it will believe that White A is a good move. That's what I mean when I say that evaluation can be brittle. Playing a semeai properly might mean evaluating the exact min-max (local) outcome of a chain of 20 moves, assuming best play by both sides. Any mis-step will lose the battle. Any mistake will lead to an evaluation which is off not by a fraction of a percent, but off by nearly 50% - the difference between balancing at the edge, 50% win/loss, and losing abjectly. Many joseki are that finely balanced - make the wrong move and your position collapses. Fail to follow up on your advantage, and your opponent gains at your expense. In short, I'd say that including joseki and fuseki databases is a Good Thing, but they must be as complete as possible, and integrated properly into the move evaluation function. Traps, spoilers, and blunders should be part of the knowledge base, signposts for the unwary to avoid deep pits. There are many well-known trick plays which are actually unsound against correct play, but gain an advantage against weaker players. Imagine the fool's mate multiplied hundreds of times; the field is liberally sown with such trick plays. Eradicating such blunders will require qualitative analysis; statistical comparisons of one fool's winrate against another won't help much. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Anyone With Measures for MiniMax LightSimulations
On Sun, 2008-10-12 at 08:08 -0700, terry mcintyre wrote: From: Don Dailey [EMAIL PROTECTED] I've always had this idea that the best way to build a book might also be the best way to build a game playing program. For instance we have done these big studies to determine based on games of Leela and others what the best main line of play is.Computer Chess programs analyze huge databases of games and make tree's sometimes to build opening books. But it seems like this resembles to a remarkable degree a Monte Carlo Tree Search program. Yes, there are analogies. The databases of games in Chess include many high-quality grandmaster-level games, do they not? I hope that Go databases also sample professional Dan-level games, otherwise we're just diving into a pool of ignorance and drawing up a sample. The downside is of course that little exploration is done. In chess it is still common to find theoretical novelties or previously unknown moves that turn out to be be interesting or even good. So mini-maxing the choices of Grandmasters is not going to be innovative. Even MCTS depends on a certain amount of exploration (as opposed to exploitation.) I guess you could view chess opening theory as this huge tree built up over decades of time by very intelligent agents. Joseki databases are brittle in a sense. Playing the almost right move is often a failure. I was just reading a particular line in 38 Basic Joseki, where the author commented that if White plays A in a certain diagram, Black should reply with B; a difficult semeai follows, which Black wins by one move if he plays correctly. The result is a gain for Black. On the other hand, if Black does not know how to play that dificult semeai, Black should not start down that path at all; it will be a gain for White. I've always thought Joseki for computers is pretty dicey, but I'm not really qualified to judge this well as I don't play go.But perhaps joseki is nothing more that a pattern database to suggest moves and you still just combine it with MCTS? - Don Imagine a program analyzing such a position. Is the program smart enough to figure out the correct way for Black to win the semeai? If so, the program will evaluate White A as a dubious move, and avoid it; if playing Black, will respond correctly and win the battle - and probably the game. But if the program is not smart enough to play the semeai correctly, it will believe that White A is a good move. That's what I mean when I say that evaluation can be brittle. Playing a semeai properly might mean evaluating the exact min-max (local) outcome of a chain of 20 moves, assuming best play by both sides. Any mis-step will lose the battle. Any mistake will lead to an evaluation which is off not by a fraction of a percent, but off by nearly 50% - the difference between balancing at the edge, 50% win/loss, and losing abjectly. Many joseki are that finely balanced - make the wrong move and your position collapses. Fail to follow up on your advantage, and your opponent gains at your expense. In short, I'd say that including joseki and fuseki databases is a Good Thing, but they must be as complete as possible, and integrated properly into the move evaluation function. Traps, spoilers, and blunders should be part of the knowledge base, signposts for the unwary to avoid deep pits. There are many well-known trick plays which are actually unsound against correct play, but gain an advantage against weaker players. Imagine the fool's mate multiplied hundreds of times; the field is liberally sown with such trick plays. Eradicating such blunders will require qualitative analysis; statistical comparisons of one fool's winrate against another won't help much. 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] Anyone With Measures for MiniMax LightSimulations
From: Don Dailey [EMAIL PROTECTED] On Sun, 2008-10-12 at 08:08 -0700, terry mcintyre wrote: Yes, there are analogies. The databases of games in Chess include many high-quality grandmaster-level games, do they not? I hope that Go databases also sample professional Dan-level games, otherwise we're just diving into a pool of ignorance and drawing up a sample. The downside is of course that little exploration is done. In chess it is still common to find theoretical novelties or previously unknown moves that turn out to be be interesting or even good. So mini-maxing the choices of Grandmasters is not going to be innovative. I'd certainly encourage blending existing knowledge with exploration. I've always thought Joseki for computers is pretty dicey, but I'm not really qualified to judge this well as I don't play go.But perhaps joseki is nothing more that a pattern database to suggest moves and you still just combine it with MCTS? If joseki databases are nothing more than a pattern database to suggest moves, they will probably be brittle, not knowing how to continue in the face of novel moves. Assuming a dan-level opponent, the difference between knowing the right continuation and not is the difference between a game at the knife edge of 50% win/loss probability, and a certain loss - but any program which doesn't know the continuation will believe it is still in the game. It's like not seeing a looming scholar's mate - but in Go, the consequence of a mistake is not so obvious just 4 moves into the future; it can be a capturing race 15, 20, 30 moves deep, but as inexorable and certain as a looming train wreck. The pro, seeing the result, evaluates the game as a certain win. The program, not able to peer that far into the future, would think it's still in the game. You mentioned that chess programs now use very narrow branching trees. Go players likewise use narrow trees; they use a lot of rules of thumb and stored experience with joseki and fuseki to eliminate a large percentage of legal moves as uninteresting. They also use short and focused trees, to study particular objectives: capture this group, defend that group, threaten the other, escape to the center, Life-and-death issues sometimes require a tree 20 or 30 moves in depth; many joseki involve intricate life-and-death problems at their heart; some cutting plays are rejected because they can be captured. Ladders are a common feature of joseki and fusekil; a play may be good only if a certain ladder works, otherwise the same play becomes a liability. A joseki pattern database needs to know the details, in depth, accurately; otherwise it can actually be a liability. It needs to know how to correctly handle out-of-book plays as well as the main lines. Given that caveat, yes, such a database should be combined with MCTS. Pros do not follow joseki and fuseki blindly; they choose a particular joseki based on how it works with the other stones on the board. Better to build a wall which faces one's stones than facing one's opponent, for instance. Looking at http://eidogo.com, one often sees several choices, MCTS could help select one depending upon the likely outcomes. Best not to neglect handicap openings. The Nihon Ki-in has an excellent book on handicap play; one chooses joseki which work well with the existing handicap stones, dividing and confining white's forces. ( ISBN 1889554-28-6 ) Look at http://senseis.xmp.net/?Hamete and http://senseis.xmp.net/?TrickPlay for examples of how stronger opponents use overplays to trick weaker players ( and programs ) into doing foolish things. Knowing how to respond to such plays would enable programs to defeat stronger opponents; not knowing will often lead to certain defeat. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
