Re: [computer-go] MC approach
Quoting Heikki Levanto [EMAIL PROTECTED]: On Wed, Feb 07, 2007 at 04:42:01PM -0500, Don Dailey wrote: In truth the only thing that matters is to increase your winning percentage - not your score. There seems to be no point in tampering with this. I guess I must accept the wisdom of those who have tried these things. Still, it hurts my intuition that it could be better for a program to choose a line where it seems to win by 2 points, when another line seems to end in a 100 point win. What if the opponent can improve his play from what I expected, and gain an extra 3 points somewhere? Maybe all this shows that we have not (yet?) understood all the complications of the MC evaluation, and that more research is needed? No, it is actually quite simple although of course more reseacrh is needed for MC but not on this topic. Here I mght repeat what others already said but I will try to make it clear out of how I understand it. The line that ends in a 100 point win is often only a win if the opponent makes a mistake, otherwise you lose some points or even the game. The fallacy here (I have been there too) is that you think of specific situations where all lines ends with victory. But in real games many lines often exists that wins big but are also risky. You are of course safe when all moves are valued 1000 each. But before that there might be some evaluated for example 998 because the MC eval knows that something may go wrong (a 7ply deep tactical defect exists) if you then add the average score of 2 to 1000 and an average score of 10 to 998 then the program makes a mistake. It is all about eliminating uncertainty. The average score can contain a very large proportion of losees if it is compensated by bigger wins. Since mc eval is based on random games it will always have scores less than the maximum 1000, in won positions that can still be lost by greedy moves. And there is no way of securely determine the point when greedy play. Not even when all moves are evaluated as sure wins, there can be bugs in the program that inflates the win score of moves that leads to a tactical disaster. The solution is to improve the simulation part so that real sure wins are evaluated as sure wins early and among these one can bias the selected moves toward profitable moves. Valkyria does something like this, although I have forgotten the exact details now. This problem I think become less important when the program become stronger in other areas. The reason is that the simulation part plays a very bad endgame. Thus a strong MC/UCT program realizes that more territory is also an insurance against a bad endgame. I have no solid backing for this but my impression is that Valkyria used to win with 0.5 points almost always but now often wins with much more. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Quoting Don Dailey [EMAIL PROTECTED]: Doing 8 searches is time-consuming, but I really prefer a book that has a LOT of variety. This is also one reason I now hand edit my book. Every time I correct a bad move there are often several ways of playing that I cannot tell which is better or worse and then I add all of them, and often moves that Valkyria would never consider. The idea is that humans on KGS will find Valkyria less predictable and other programs will have a harder time adapting to the book of Valkyria. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Paper presents results on proximity heuristic
Thanks, Peter! I have a question or two regarding the opening book, based on a collection of 3000 9x9 games provided by Nici Schraudolph. Who played the games in this collecton - pros, strong amateurs, or go programs? Second, were any statistics on the number of game moves in book versus out of book collected? Lastly, it was assumed that the book moves were winning moves; was this hypothesis ever tested on a move-by-move basis, whether against GnuGo or itself? Many thanks for an informative paper! - Original Message From: Peter Drake [EMAIL PROTECTED] By the way, the paper was rejected on first submission, largely because we were just testing Orego against itself. We're now testing Orego against GNU Go and have a revised version: https://webdisk.lclark.edu/xythoswfs/webui/_xy-2352013_1-t_Gct7yJ5s%22 (Markus, could you change the link and title? This was DPSV07.) Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ On Feb 7, 2007, at 12:36 PM, Chris Fant wrote: In this paper, you say that you limit the number of moves to BoardArea*2 during the playouts. For me, this barely increases the playout rate and slightly reduces the strength (perhaps not statistically significant). Your paper does not mention suicide. Prohibiting single-stone suicide during playout gave me a nice increase in playout rate and strength. On 11/28/06, Peter Drake [EMAIL PROTECTED] wrote: Here it is: https://webdisk.lclark.edu/xythoswfs/webui/_xy-2115826_1-t_OX34gnaB Bored stiff? Loosen up... Download and play hundreds of games for free on Yahoo! Games. http://games.yahoo.com/games/front___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
Magnus Persson wrote: This is not a problem for scalability for MC/UCT. It just means that a program .. You are right. I didn't mean it is not scalable, of course it is. What I mean is complexity is not, as one could expect, about ~boardsize^4. (The square of legal moves times the square of simulation length.) But even more due to the increase in variance. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
The average score can contain a very large proportion of losees if it is compensated by bigger wins. yes, it is easy to see how this might cripple the play of an MC player. that 90% territory win that requires 3 opponent blunders is tempting enough to ignore the fact that all other non-blundering lines lead to 0.5 point losses. i wonder if this kind of greediness might, however, be useful for selecting, say, the first move or two in a 9x9 game. the thinking here is that since the endgame is essentially noise at this point, you might as well be greedy before tactics become an issue. that's probably faulty intuition, though. on another note, has anyone just let their MC code rip for a day or two (or maybe a week or more) on the first move alone? i would think that if you ordered the distribution of the resulting list, it would give very good information about how well MC acts as a board-eval function. (i.e. turn off all book lines, turn off all rules about not playing on the first line or two early in the game, etc. etc. turn off all heuristics related to the opening and then print the distribution over the board). what are the top, say, 10 moves on a 9x9 board and how are they distributed, and the top, say, 40 moves on a 19x19 board along with their distribution? if you fold board symmetries into your search, i suppose that you can get a factor of 8 here. my thinking is that if it's anything other than a very smooth distribution among the top moves, that's a good indicator. s. It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
I think there are 15 first moves in 9x9 go if you factor out the symetries. UCT isn't good at evauating all the moves, it will pick one of them and spend most of it's time on it.But you could search each 1 at a time. The UCT programs are memory bound, so you could search each of these 15 moves 1 at a time and study the scores. - Don On Thu, 2007-02-08 at 04:41 -0800, steve uurtamo wrote: The average score can contain a very large proportion of losees if it is compensated by bigger wins. yes, it is easy to see how this might cripple the play of an MC player. that 90% territory win that requires 3 opponent blunders is tempting enough to ignore the fact that all other non-blundering lines lead to 0.5 point losses. i wonder if this kind of greediness might, however, be useful for selecting, say, the first move or two in a 9x9 game. the thinking here is that since the endgame is essentially noise at this point, you might as well be greedy before tactics become an issue. that's probably faulty intuition, though. on another note, has anyone just let their MC code rip for a day or two (or maybe a week or more) on the first move alone? i would think that if you ordered the distribution of the resulting list, it would give very good information about how well MC acts as a board-eval function. (i.e. turn off all book lines, turn off all rules about not playing on the first line or two early in the game, etc. etc. turn off all heuristics related to the opening and then print the distribution over the board). what are the top, say, 10 moves on a 9x9 board and how are they distributed, and the top, say, 40 moves on a 19x19 board along with their distribution? if you fold board symmetries into your search, i suppose that you can get a factor of 8 here. my thinking is that if it's anything other than a very smooth distribution among the top moves, that's a good indicator. s. It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/ ___ 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] MC approach
I thought that the memory boundedness was completely fixed by not expanding a UCT node until it has been visited X number of times. Just increase X until you are no longer memory bound. I don't recall anyone reporting a loss in playing strength by doing this. On 2/8/07, Don Dailey [EMAIL PROTECTED] wrote: I think there are 15 first moves in 9x9 go if you factor out the symetries. UCT isn't good at evauating all the moves, it will pick one of them and spend most of it's time on it.But you could search each 1 at a time. The UCT programs are memory bound, so you could search each of these 15 moves 1 at a time and study the scores. - Don On Thu, 2007-02-08 at 04:41 -0800, steve uurtamo wrote: The average score can contain a very large proportion of losees if it is compensated by bigger wins. yes, it is easy to see how this might cripple the play of an MC player. that 90% territory win that requires 3 opponent blunders is tempting enough to ignore the fact that all other non-blundering lines lead to 0.5 point losses. i wonder if this kind of greediness might, however, be useful for selecting, say, the first move or two in a 9x9 game. the thinking here is that since the endgame is essentially noise at this point, you might as well be greedy before tactics become an issue. that's probably faulty intuition, though. on another note, has anyone just let their MC code rip for a day or two (or maybe a week or more) on the first move alone? i would think that if you ordered the distribution of the resulting list, it would give very good information about how well MC acts as a board-eval function. (i.e. turn off all book lines, turn off all rules about not playing on the first line or two early in the game, etc. etc. turn off all heuristics related to the opening and then print the distribution over the board). what are the top, say, 10 moves on a 9x9 board and how are they distributed, and the top, say, 40 moves on a 19x19 board along with their distribution? if you fold board symmetries into your search, i suppose that you can get a factor of 8 here. my thinking is that if it's anything other than a very smooth distribution among the top moves, that's a good indicator. s. It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/ ___ 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] MC approach
Quoting Don Dailey [EMAIL PROTECTED]: I think there are 15 first moves in 9x9 go if you factor out the symetries. UCT isn't good at evauating all the moves, it will pick one of them and spend most of it's time on it.But you could search each 1 at a time. The UCT programs are memory bound, so you could search each of these 15 moves 1 at a time and study the scores. It is perhaps better to do this experiment on 7x7 where it is actually known what the best moves in the opening are so it is possible to judge the quality. I am now not thinking about the first move mut more of finding a high quality principal variation. I did some experiments long time ago with t least several hours of computing time for some opening positions, but found that there were some serious problems for many positions. Improvements or changes to the program seemed to change the evaluation of opening positions almost randomly. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC approach
On Thu, 2007-02-08 at 08:59 -0500, Chris Fant wrote: I thought that the memory boundedness was completely fixed by not expanding a UCT node until it has been visited X number of times. Just increase X until you are no longer memory bound. I don't recall anyone reporting a loss in playing strength by doing this. There is a loss of playing strength as X grows, but the loss grows very slowly. Obviously, if you set X really high, it would not build much of a tree and it would play very weak. I have been planning to make this dynamic in Lazarus, but I have not done so yet. The idea is that X starts at 1 but when the table fills up there is a consolidation pass where the table is rebuilt, child nodes may fold back into their parents and X gets reset to a higher value. As the search proceeds this may happen a few time, perhaps doubling the value of X each time. In this way the program continues to scale smoothly. There is never a sudden out of memory wall and you can set the table initiallly to any size that suits you. I haven't bothered because I cannot detect a loss of strength in values up to 100 but it's on my todo list - I know there is a small loss of strength even if I cannot measure it. Right now, Lazarus simply stops searching and returns a move when this happens, but I have X set high enough that it can think for many minutes. - Don On 2/8/07, Don Dailey [EMAIL PROTECTED] wrote: I think there are 15 first moves in 9x9 go if you factor out the symetries. UCT isn't good at evauating all the moves, it will pick one of them and spend most of it's time on it.But you could search each 1 at a time. The UCT programs are memory bound, so you could search each of these 15 moves 1 at a time and study the scores. - Don On Thu, 2007-02-08 at 04:41 -0800, steve uurtamo wrote: The average score can contain a very large proportion of losees if it is compensated by bigger wins. yes, it is easy to see how this might cripple the play of an MC player. that 90% territory win that requires 3 opponent blunders is tempting enough to ignore the fact that all other non-blundering lines lead to 0.5 point losses. i wonder if this kind of greediness might, however, be useful for selecting, say, the first move or two in a 9x9 game. the thinking here is that since the endgame is essentially noise at this point, you might as well be greedy before tactics become an issue. that's probably faulty intuition, though. on another note, has anyone just let their MC code rip for a day or two (or maybe a week or more) on the first move alone? i would think that if you ordered the distribution of the resulting list, it would give very good information about how well MC acts as a board-eval function. (i.e. turn off all book lines, turn off all rules about not playing on the first line or two early in the game, etc. etc. turn off all heuristics related to the opening and then print the distribution over the board). what are the top, say, 10 moves on a 9x9 board and how are they distributed, and the top, say, 40 moves on a 19x19 board along with their distribution? if you fold board symmetries into your search, i suppose that you can get a factor of 8 here. my thinking is that if it's anything other than a very smooth distribution among the top moves, that's a good indicator. s. It's here! Your new message! Get new email alerts with the free Yahoo! Toolbar. http://tools.search.yahoo.com/toolbar/features/mail/ ___ 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 computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Suicide in MC playouts
When I added code to by bot to prohibit single-stone suicide in the MC playouts, I saw about a 200 ELO point gain plus an increase in pps due to the shorter games. I did not need to limit game length to 2x board area. When I added code to also prohibit multi-stone suicides in the MC playouts, I saw the appearance of infinitely long games due to unrestricted board repetition. So I then had to add the 2x board area limit. But I also saw a significant drop in strength and a significant drop in pps. I understand that allowing multi-stone suicide seems like a bad idea, but because it makes board repetition much more unlikely, it seems like a good idea. Do I have a bug? Has anyone else actually tried prohibiting single-stone suicide while allowing multi-stone suicide? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
Quoting Chris Fant [EMAIL PROTECTED]: I understand that allowing multi-stone suicide seems like a bad idea, but because it makes board repetition much more unlikely, it seems like a good idea. I do not understand how you get a problem of board repetition, and how multi-stone suicde help with that. Do you not prohibit ko recaptures? If you do then more legal moves would prevent situation where ko are the only possibility. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
Sounds like a bug. The randomness of the moves should make infinite loops fairly rare (though not impossible) and your average game length should be close to 100 moves. It's a good idea to step through playout games one move at a time. Also to run a lot of games, stopping to look at the final game state. And also to switch to step-at-a-time mode when/if a game has run more than 120 moves to examine what is causing the repetition. I've caught quite a few mystifying bugs this way. Are you implementing simple ko? Have you added some tactical rule like always make a capture if you can? - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 8 Feb 2007 10:45 AM Subject: [computer-go] Suicide in MC playouts When I added code to by bot to prohibit single-stone suicide in the MC playouts, I saw about a 200 ELO point gain plus an increase in pps due to the shorter games. I did not need to limit game length to 2x board area. When I added code to also prohibit multi-stone suicides in the MC playouts, I saw the appearance of infinitely long games due to unrestricted board repetition. So I then had to add the 2x board area limit. But I also saw a significant drop in strength and a significant drop in pps. I understand that allowing multi-stone suicide seems like a bad idea, but because it makes board repetition much more unlikely, it seems like a good idea. Do I have a bug? Has anyone else actually tried prohibiting single-stone suicide while allowing multi-stone suicide? ___ 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/
Re: [computer-go] Monte-Carlo Go Misnomer?
Hello, Is there any known (by theory or tests) function of how much a increase in the strength of the simulation policy increases the strength of the MC/UCT Program as a whole? I think that is a very interesting question. In our work on MoGo we found that there could be a decrease of the strength of the MC/UCT program while using a stronger simulation policy. It is why in MoGo it is more the sequence idea, than the strength idea. Our best simulation policy is quite weak compared to others we tested. But we have further experiments, in a work with David Silver from the university of Alberta. We found out that the relation strong simulation policy = strong MC program is wrong at a much larger scale. So the intransivity is true even with much much stronger simulation policies. Of course there is the simple counter example of a deterministic player. But our results hold even if we randomise (in a lot of manners, and tuning as best as we can the parameters) the much stronger policy. I have some theory about this phenomenon in general, but not enough polished for the moment. I really think that understanding deeply this experimental evidence, deeper than some intuition, would help going further. But maybe some already did. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
This makes no sense to me. Most of us are working on how to improve the quality of the quasi random simulations and you are considering to allow the worst moves. Your eye rule probably keeps this from getting completely out of control, but I would say allowing any suicide should greatly increase the games lengths, not reduce it. - Don On Thu, 2007-02-08 at 10:45 -0500, Chris Fant wrote: When I added code to by bot to prohibit single-stone suicide in the MC playouts, I saw about a 200 ELO point gain plus an increase in pps due to the shorter games. I did not need to limit game length to 2x board area. When I added code to also prohibit multi-stone suicides in the MC playouts, I saw the appearance of infinitely long games due to unrestricted board repetition. So I then had to add the 2x board area limit. But I also saw a significant drop in strength and a significant drop in pps. I understand that allowing multi-stone suicide seems like a bad idea, but because it makes board repetition much more unlikely, it seems like a good idea. Do I have a bug? Has anyone else actually tried prohibiting single-stone suicide while allowing multi-stone suicide? ___ 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] Paper presents results on proximity heuristic
On 2/7/07, David Doshay [EMAIL PROTECTED] wrote: On 7, Feb 2007, at 1:35 PM, Don Dailey wrote: Although suicide can occasionally be the best move in some rule-sets, I think it weakens your program to include it, At best you are going to get a ko threat, so it requires a pretty sophisticated program to know how and when to use it. There are weird cases where suicide is more than just a ko threat. http://www.goban.demon.co.uk/go/bestiary/rule_challenge.html (Just picking nits.) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
In our work on MoGo we found that there could be a decrease of the strength of the MC/UCT program while using a stronger simulation policy. It is why in MoGo it is more the sequence idea, than the strength idea. Our best simulation policy is quite weak compared to others we tested. Could you elaborate on the sequence idea? Or point me to somewhere where you have already done so? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go Misnomer?
Could you elaborate on the sequence idea? Or point me to somewhere where you have already done so? Sure. We already describe it in our research report that you can find there: http://hal.inria.fr/inria-00117266 or there if you prefers the web interface in english but with a longer URL :-) http://hal.inria.fr/index.php?halsid=f72d067037f3b8f161448b400d117210view_this_doc=inria-00117266version=3 Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
Last one, I promise :) If your eye rule doesn't allow the defender to fill in behind the ko stone (the one in atari), that can set up infinite loop triple kos. - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 8 Feb 2007 12:19 PM Subject: Re: [computer-go] Suicide in MC playouts This one's a long shot. If you get the simple ko rule a little bit wrong, you can run into a situation where a move that was illegal for black doesn't get reset correctly and white isn't allowed to move there either. This can lead to endless triple kos. _ Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 8 Feb 2007 11:24 AM Subject: Re: [computer-go] Suicide in MC playouts Sounds like a bug. The randomness of the moves should make infinite loops fairly rare (though not impossible) and your average game length should be close to 100 moves. It's a good idea to step through playout games one move at a time. Also to run a lot of games, stopping to look at the final game state. And also to switch to step-at-a-time mode when/if a game has run more than 120 moves to examine what is causing the repetition. I've caught quite a few mystifying bugs this way. Are you implementing simple ko? Have you added some tactical rule like always make a capture if you can? - Dave Hillis -Original Message- From: [EMAIL PROTECTED] To: computer-go@computer-go.org Sent: Thu, 8 Feb 2007 10:45 AM Subject: [computer-go] Suicide in MC playouts When I added code to by bot to prohibit single-stone suicide in the MC playouts, I saw about a 200 ELO point gain plus an increase in pps due to the shorter games. I did not need to limit game length to 2x board area. When I added code to also prohibit multi-stone suicides in the MC playouts, I saw the appearance of infinitely long games due to unrestricted board repetition. So I then had to add the 2x board area limit. But I also saw a significant drop in strength and a significant drop in pps. I understand that allowing multi-stone suicide seems like a bad idea, but because it makes board repetition much more unlikely, it seems like a good idea. Do I have a bug? Has anyone else actually tried prohibiting single-stone suicide while allowing multi-stone suicide? ___ 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/ ___ 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/
Re: [computer-go] MC approach
On 2/8/07, steve uurtamo [EMAIL PROTECTED] wrote: i wonder if this kind of greediness might, however, be useful for selecting, say, the first move or two in a 9x9 game. the thinking here is that since the endgame is essentially noise at this point, you might as well be greedy before tactics become an issue. that's probably faulty intuition, though. I believe that I have had some success with an approach like this, actually. I believe that I initially only tally games that are won by a certain margin, and reduce that margin to zero as the game progresses. I am pretty sure that this improves upon straight Monte Carlo. I think that I can get some numbers on it, if anyone is interested. Weston ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go simulation
One simple explaination could be that a random player shamelessly tries all moves (very bad ones but also very nice tesuji) whereas the stronger player is restricted by its knowledge and will always miss some kind of moves. Here we are not speeking about the pruning in the tree, but the simulation player. The tree must explore every move, to avoid missing important ones. However we totally don't care if all possible games can or not be played by the simulation player. What we care about is the expectation of the wins by self play. If the simulation player sometimes play meaningful sequences but with a very small probability, then it has very little influence on the expectation. It seems to me that the explanation may be more complicated. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
This sounds backwards. If multi-stone suicides ARE allowed then it opens up board areas that can then be replayed. This could lead to infinitely long games. Cheers, David On 8, Feb 2007, at 7:45 AM, Chris Fant wrote: When I added code to also prohibit multi-stone suicides in the MC playouts, I saw the appearance of infinitely long games due to unrestricted board repetition. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
On Thu, 8 Feb 2007, Chris Fant wrote: When I added code to also prohibit multi-stone suicides in the MC playouts, I saw the appearance of infinitely long games due to unrestricted board repetition. So I then had to add the 2x board area limit. But I also saw a significant drop in strength and a significant drop in pps. My program has this limit too, but there are VERY few games (1 in 10) that have to be stopped. The typical game is more like 100 moves. There must be a bug in the program if it plays better with suicide. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go simulation
It seems i was ambiguous: I was speaking of the simulation player too. What i meant is a random simulation player is not biased, whereas a better simulation player is biased by its knowledge, and thus can give wrong evaluation of a position. I think we have to start defining what the bias. For me the bias is the difference between the expected value of the outcomes of playouts by the simulation player and the real minimax value. In this definition the uniform random simulation player is VERY biased and gnugo much less. A trivial example is GNU Go: its analyze is sometimes wrong. Of course, if not computer go would be solved :-). Even if it is obviously much stronger than a random player, it would give wrong result if used as a simulation player. Hum, are you sure? I think that GnuGo with randomisation, (and much faster of course) would make a very good simulation player (much better than any existing simulation player). But a weaker player than GnuGo can make an even better simulation player. David Doshay experiments with SlugGo showed that searching very deep/wide does not improve a lot the strength of the engine, which is bound by the underlying weaknesses of GNU Go. Yes, this a similar non trivial result. I think there are more existing experimental and theoritical analysis of this, though. Perhaps such an analysis already exist for MC also, it is just that I don't know. Or maybe i just understood nothing of what you explained ;) It was not really explanations, just thoughts. I have no the solution, just think that it is an interesting question, and that it may be discussed. May be from a strong explanation of this phenomenon could come new ideas. I understand all these counter examples, I just think that it is more complicated than that. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re[2]: [computer-go] Why not forums?
Actually this is all I ever wanted! Now if only I could convince the whole Computer Go community to use it, but that seems unlikely :) -Original Message- From: Joshua Shriver [EMAIL PROTECTED] To: Dmitry Kamenetsky [EMAIL PROTECTED], computer-go computer-go@computer-go.org Date: Wed, 7 Feb 2007 09:35:54 -0500 Subject: Re: [computer-go] Why not forums? I've had a computer go forum running for a while but has low traffic. http://www.olympuschess.com/phpBB2 -josh On 2/4/07, Dmitry Kamenetsky [EMAIL PROTECTED] wrote: Hello everyone, Why can't we use proper forums instead of this outdated list? Forums are easier to keep track of and search for messages. As a start we can use Yahoo groups. What do you think? Cheers, Dmitry ___ 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: Re[2]: [computer-go] Why not forums?
Now that's low traffic! One post in May of 2006, and since then, nada. No spambots, no griefers. :) Terry McIntyre -Original Message- From: Joshua Shriver [EMAIL PROTECTED] To: Dmitry Kamenetsky [EMAIL PROTECTED], computer-go computer-go@computer-go.org Date: Wed, 7 Feb 2007 09:35:54 -0500 Subject: Re: [computer-go] Why not forums? I've had a computer go forum running for a while but has low traffic. http://www.olympuschess.com/phpBB2 -josh On 2/4/07, Dmitry Kamenetsky [EMAIL PROTECTED] wrote: Hello everyone, Why can't we use proper forums instead of this outdated list? Forums are easier to keep track of and search for messages. As a start we can use Yahoo groups. What do you think? Cheers, Dmitry ___ 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/ Have a burning question? Go to www.Answers.yahoo.com and get answers from real people who know.___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:55 -0500, Don Dailey wrote: The children of one parent almost certainly will have different 64 bit keys than the children of the other parent. Not if the parents collide. (apart from symmetry/canonical considerations): if H(A)==H(B), then after applying move 'm' -- H(A) ^ some_constant == H(B) ^ some_constant So if you use Zobrist[move] as a some_constant value (which I understand you do), then if both parent moves A,B have a successor move (coordinate+color) in common, the resulting hashes for the successors will also collide. I don't see how you can conclude that I'm not getting much extra safety. By the way, I use zobrist hashing with XOR to generate these keys and do all the rotations - choosing the smallest key of the 8 possible tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... hash to this same key but the positions are symetrically equivalent. You mean: _after the canonisation_ they hash to the same key. You could of course look at it backwards, what are the odds that 2 child keys will match? If you can find 2 that do match, what are For two children of the same parent, this is (given an adequate Zobrist table) impossible. After canonisation, this is unclear (but can be guaranteed by careful construction of the Zobrist tables). the odds that their parents will also have a matching key? I think this is very unlikely. I think this is just as likely as the other way around, since the ^ is its own inverse function. HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Go simulation
I think that the bias Alain meant is the choice of moves that control the branching factor. If I understand correctly, this can happen differently in two places in MoGo: once in the branching below a node in the UCT tree, and either the same or differently in the random playouts. In some ways this is like SlugGo, where branching at the first level (our move) may or may not be determined in the same way as at the next (their guessed reply). If SlugGo is set for multiple levels of branching in the lookahead we do the same thing but from the other perspective. But for deeper linear lookahead things are different, just like in your random playouts. Alain's point, that knowledge can both help narrow the search to good moves and at the same time steer you away from the best move is absolutely true in SlugGo's case. This is the primary reason we have always wanted to have multiple Go engines making move suggestions, not just multiple instantiations of the same engine like we have now. But we could get up and running faster with one engine, so that is where we are now. Hopefully not much longer ... Cheers, David On 8, Feb 2007, at 2:09 PM, Sylvain Gelly wrote: It seems i was ambiguous: I was speaking of the simulation player too. What i meant is a random simulation player is not biased, whereas a better simulation player is biased by its knowledge, and thus can give wrong evaluation of a position. I think we have to start defining what the bias. For me the bias is the difference between the expected value of the outcomes of playouts by the simulation player and the real minimax value. In this definition the uniform random simulation player is VERY biased and gnugo much less. A trivial example is GNU Go: its analyze is sometimes wrong. Of course, if not computer go would be solved :-). Even if it is obviously much stronger than a random player, it would give wrong result if used as a simulation player. Hum, are you sure? I think that GnuGo with randomisation, (and much faster of course) would make a very good simulation player (much better than any existing simulation player). But a weaker player than GnuGo can make an even better simulation player. David Doshay experiments with SlugGo showed that searching very deep/wide does not improve a lot the strength of the engine, which is bound by the underlying weaknesses of GNU Go. Yes, this a similar non trivial result. I think there are more existing experimental and theoritical analysis of this, though. Perhaps such an analysis already exist for MC also, it is just that I don't know. Or maybe i just understood nothing of what you explained ;) It was not really explanations, just thoughts. I have no the solution, just think that it is an interesting question, and that it may be discussed. May be from a strong explanation of this phenomenon could come new ideas. I understand all these counter examples, I just think that it is more complicated than that. Sylvain ___ 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] MC Go Effectiveness
We had this same problem and wasted a huge amount of time and energy on trying to determine the right canonical key. I felt both proud and stupid when I realized: it really does not make any difference which is the canonical key, so we just declare the first one that we find to be the canonical. The rest are the transformed versions. Cheers, David On 8, Feb 2007, at 3:18 PM, Unknown wrote: Don wrote: - choosing the smallest key of the 8 possible tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... It's not quite as good as using 64 bits free and clear because there is compression towards the lower bits. i must be missing something here -- the whole point of canonicalization is that you want to be able to recognize a 'book line' when it appears, even if you have to rotate and/or reflect your board in order to match the book line, right? you save 8x the space by only stashing one copy of the book line, and by using some canonical version of the hash key and doing 8 transforms on every board position when the game move is less than the longest known line length, or somesuch. if you're only storing a few hundred lines, or a few thousand, why not store all 8 copies? then it's just a lookup with no extra transforms. s. Need a quick answer? Get one in minutes from people who know. Ask your question on www.Answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re[2]: [computer-go] Why not forums?
On Fri, 2007-02-09 at 01:35 +0300, Dmitry Kamenetsky wrote: Actually this is all I ever wanted! Now if only I could convince the whole Computer Go community to use it, but that seems unlikely :) Smiley aside, wouldn't it be more constructive to do as somebody else suggested, and use the email list as a feed into whatever interface you prefer? Why ask everybody to switch? -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide in MC playouts
Okay, I found the bug. There was actually two. I won't bore you with the details. Sorry for wasting everyone's time. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:58 -0800, steve uurtamo wrote: tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... It's not quite as good as using 64 bits free and clear because there is compression towards the lower bits. i must be missing something here -- the whole point of canonicalization is that you want to be able to recognize a 'book line' when it appears, even if you have to rotate and/or reflect your board in order to match the book line, right? you save 8x the space by only stashing one copy of the book line, and by using some canonical version of the hash key and doing 8 transforms on every board position when the game move is less than the longest known line length, or somesuch. Yes. But Don's confusion was independent of the canonicalization, though it was probably caused by it. if you're only storing a few hundred lines, or a few thousand, why not store all 8 copies? then it's just a lookup with no extra transforms. Sure. It is just an engineering decision: do you want to waste the RAM-space, or only the CPU-time. For a few hundred records, optimising for space is probably not worth the effort. For a larger fuseki / joseki /pattern book, it probably is. CPU is cheaper than RAM, and a cache miss is worth tens of instructions. It depends. (though travel light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) BTW: once you choose the /8 gain by implementing canonicalization, you'll probably want to implement /2 color-swaps, too. (but this will only be profitable for libraries, not for 'history' such as in Don's case.) HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] MC Go Effectiveness
light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) More like 10 bits per move to store the joseki DAG, moves, pointers, and good/bad/trick flags. I would never do anything like that now, but back then the entire go program including joseki library had to fit in about 300 KB of memory (DOS) on PCs that typically only had 512 KB to 1 MB total memory. The library fit about 50K positions in about 60 KB. David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:36 -0800, David Doshay wrote: We had this same problem and wasted a huge amount of time and energy on trying to determine the right canonical key. I felt both proud and stupid when I realized: it really does not make any difference which is the canonical key, so we just declare the first one that we find to be the canonical. The rest are the transformed versions. Yes, that would work here perfectly. You just search all 8 until you find it or you don't. Cheers, David On 8, Feb 2007, at 3:18 PM, Unknown wrote: Don wrote: - choosing the smallest key of the 8 possible tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... ___ 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] MC Go Effectiveness
It depends. (though travel light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) this reminds me of an old-school optimized piece of scrabble-playing code. there was a routine that would take an ascii list of words and create a DAG out of them, as a ready-made object file, with headers and everything. the makefile linked the playing routine against it, creating a ready-made array that existed at runtime. http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt truly an awesome piece of software. it requires some minor modification to work on a modern machine, but it's well worth the effort. s. Food fight? Enjoy some healthy debate in the Yahoo! Answers Food Drink QA. http://answers.yahoo.com/dir/?link=listsid=396545367 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 15:58 -0800, steve uurtamo wrote: tranforms as the cannonical key. In most cases 8 positions will IIRC, choosing the smallest may cause some unwanted effects. Not sure... It's not quite as good as using 64 bits free and clear because there is compression towards the lower bits. i must be missing something here -- the whole point of canonicalization is that you want to be able to recognize a 'book line' when it appears, even if you have to rotate and/or reflect your board in order to match the book line, right? you save 8x the space by only stashing one copy of the book line, and by using some canonical version of the hash key and doing 8 transforms on every board position when the game move is less than the longest known line length, or somesuch. if you're only storing a few hundred lines, or a few thousand, why not store all 8 copies? then it's just a lookup with no extra transforms. Well then my collision rate would go up signficantly. I don't think it's a big issue with 64 bits but there is no performance issues with lookup speed and the routine to do the tranforms has to be there no matter what - it's now isolated to one routine. And why waste the memory if there is no performance issues? I current keep the book sorted in memory and I would prefer to keep it reasonably small in the case I may someday have tens of thousands of moves. Of course by then I probably would have chosen a different storage scheme.This discussion has generated enough ideas that I may consider some changes. - Don s. Need a quick answer? Get one in minutes from people who know. Ask your question on www.Answers.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On Thu, 2007-02-08 at 18:43 -0800, steve uurtamo wrote: It depends. (though travel light is always a good adagium, see David Fotlands hilarious compression of a joseki library into 12 bits/move, IIRC ;-) this reminds me of an old-school optimized piece of scrabble-playing code. there was a routine that would take an ascii list of words and create a DAG out of them, as a ready-made object file, with headers and everything. the makefile linked the playing routine against it, creating a ready-made array that existed at runtime. http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt truly an awesome piece of software. it requires some minor modification to work on a modern machine, but it's well worth the effort. I wrote a scrabble program demo in perl with Tk because someone told me it would be too slow to be practical (several years ago.) Even then it found a good move within a second or two. The way I stored the dictionary was interesting, but I can't quite remember the details. I think each word was stored several times in the dictionary, a hash of each starting prefix. a,ap,app,appl,apple something like that. I was fun and it was pretty but it wasn't good, it basically maximized it's choices which isn't a good strategy against good players. - Don s. Food fight? Enjoy some healthy debate in the Yahoo! Answers Food Drink QA. http://answers.yahoo.com/dir/?link=listsid=396545367 ___ 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[4]: [computer-go] Why not forums?
I was only joking. Ofcourse I will do as you suggested. I just didn't realize that it was possible to use the email list as a feed. Thank you everyone for your constructive feedback and suggestions. Consider this topic closed. -Original Message- From: Jeff Nowakowski [EMAIL PROTECTED] To: Dmitry Kamenetsky [EMAIL PROTECTED], computer-go computer-go@computer-go.org Date: Thu, 08 Feb 2007 19:13:09 -0500 Subject: Re: Re[2]: [computer-go] Why not forums? On Fri, 2007-02-09 at 01:35 +0300, Dmitry Kamenetsky wrote: Actually this is all I ever wanted! Now if only I could convince the whole Computer Go community to use it, but that seems unlikely :) Smiley aside, wouldn't it be more constructive to do as somebody else suggested, and use the email list as a feed into whatever interface you prefer? Why ask everybody to switch? -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Go Effectiveness
On 8, Feb 2007, at 6:42 PM, Don Dailey wrote: On Thu, 2007-02-08 at 15:36 -0800, David Doshay wrote: We had this same problem and wasted a huge amount of time and energy on trying to determine the right canonical key. I felt both proud and stupid when I realized: it really does not make any difference which is the canonical key, so we just declare the first one that we find to be the canonical. The rest are the transformed versions. Yes, that would work here perfectly. You just search all 8 until you find it or you don't. No, we opted to store all 8 and have every hash jump to its canonical hash for the followup. You either get a hash hit with whatever you calculate off of the board or it is the first time you have seen it. After you have the followup then you transform that move back. We chose this method because we do all of our book storage while NOT in a game, but offline at another time. I also took this path because I feel that RAM is free. Cheers, David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
