Re: [computer-go] Suicide question
Hi Michael Another cost is undo. Superko requires undo, unless you want store a hash value with each chain of stones. I am not sure exactly what undo costs, but lets say 5% to 10%. Well, every implementation is different. In its slowest mode, my board stores information about neighbor stones in each cell. It has a stack of boards and each board has a pointer to its parent. In that mode superko can be detected. There is also a faster mode for MC playouts that does not support superko. But it could also be possible to maintain a stack of previous hashes i.o. complete boards, that would not be very expensive. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
Mark Boon wrote: I'm fairly new on the subject of Monte Carlo and am in the process of catching up on reading, so I hope you guys have some patience with me while I get into this and ask a lot of questions. I got side-tracked away from computer-Go programming for quite a while for various reasons but have been at it again full-time recently. Good! You are one of the best. Let me start by saying I haven't followed the whole Monte-Carlo / UCT story all that well. Although it was clear it did well on 9x9 I wasn't all that convinced it would scale up to 19x19. That it did well on 9x9 didn't surprise me much as I've always felt 9x9 is susceptible to see strong play using some extreme brute-force method using today's computing power. The surprise is that random play-outs without tree search actually plays a reasonable (certainly not strong) game. At least much better than the toy programs. I think this single fact was just enough to keep people interested enough to try more sophisticated things like you mention next. Combining Monte-Carlo methods with what's generally called heavy playouts changes things a lot however and this is where it piqued my interest. I often see reference to Monte-Carlo programs as opposed to traditional Go programs. But what I'm seeing with the heavy playouts is deja-vu all over again. It seems to me the evolution of the heavy playouts is following a similar course of that of the first rule-based Go programs in the early 1980's. To use another famous quote history doesn't repeat itself but it rhymes. I see it the same way. I have noticed this in other fields, at some point the different methods start to actually converge - all borrowing ideas from things that are known to work. So I wouldn't be surprised at all if at some point you'll see a marriage of the best ideas of traditional Go programs and Monte-Carlo / UCT. In fact, this is most likely already happening as these Monte-Carlo programs use algorithms / ideas from the traditional programs for tactics, pattern-matching and possibly others.. And I go out on a limb to predict that at some point heavy playouts will use information like territory, eye-space and group-strength to guide their playouts just like the traditional programs do. And that using fixed 3x3 patterns will be a passing fad. I believe there is a knowledge bottleneck that cannot easily be passed through.Even with patterns there is only so far you can go with 3x3 patterns for instance.I agree with you that play-outs will probably continue to get thicker and thicker until the point of diminishing returns makes it counter-productive. There comes a point where it takes an incredible amount of effort to add a little bit of raw knowledge that will actually translate to a stronger program. Of course this goes back to the argument of search vs knowledge. One can always be bought with the others. Knowledge is so useful that a piece of it can save enormous search effort. But the converse is equally true - some things are so difficult to discover statically that you need to use imagination which is what I consider the closest A.I. analogy to search - i.e. search IS imagination, we do it when we plan our day, considering what we will do and how long it will take, who we might talk to and what we will say.Go program do not have this if they don't do use imagination (seeing in their minds what will happen and imagining how they will response, having a dialogue with themselves so to speak via search.) I think what has made tree search combined with monte carlo so successful is that is so dynamic. Traditional programs have little coping power - they either have the answer (in a pattern or a routine) or they don't. Now of course it turns out that you can still help them along signficantly by letting them have imagination, but also forcing them to be realistic with some knowledge so they don't go out of control! Anyway, as it is I have made a few initial forrays into Monte-Carlo algorithms. I hereby thank Peter Drake on his work on Orego, which is a fine package to learn about Monte-Carlo. I used it to make my own implementation. Not that there was much wrong with Orego but the best way to understand and internalize a concept is to actually implement it. Moreover I felt I needed a framework that is a bit more generalized than Orego. Lastly I was convinced of course that I'd be able to make it faster. That last part didn't turn out to be true though. On my iMac, which is a 2Ghz Core Duo, I get a little under 30K playouts on 9x9. A little over 50K when using both cores. Orego is in the same ball-park. At least making a more generalized implementation didn't hurt performance so I'm OK with this first attempt. I think there's still room for optimizations, if I thought it was important at this stage. This comes to my first point. Optimizing early in a project is like listening to the devil.
Re: [computer-go] Suicide question
Self-atari is never referred to as suicide. Let's not start now. But you're right self-atari in the playouts is a more interesting topic. You have to allow it sometimes because it is the correct move sometimes. John Fan wrote: A question on this topic. When we discuss about suicide, are we referring to the real suicide, or self-atari? I think in some discussions it is referring to the real suicide. In other discussions, seems to be referring to self-atarai. If we are talking about real suicide, I do not see any point to allow the real suicide in the play out. What would be the gain if we allow the real suicide in the play out. I think its only effect is to introduces more board repetition and more moves in the playout. In very very rare cases a real suicide move is beneficial. If we are talking about the self-atari, that's a more interesting topic. I find it is very hard to tune. A lot of games of my engine are lost due to completely insane self-atari moves in the early games. Even I have policy to disfavor the self-atari moves, those moves just keep surfacing out. On Jan 18, 2008 9:28 AM, Michael Williams [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: So it's possible to create a triple-ko repetition, take that move sequence and find a non-triple-ko situation that uses the exact same repeated move sequence? A van Kessel wrote: An alternative to matching board hashes is to test for repeated move sequences. No. repeated position != repeated sequence. Since one stone is added to the board with each move, a repetition can only exist between two moves if exactly that number of stones was captured inbetween (+- pass moves) So you only have to check the positions in the game-stack where exactly the same number of black,white stones is on the board HTH, AvK ___ computer-go mailing list computer-go@computer-go.org mailto:computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org mailto: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] Suicide question
So it's possible to create a triple-ko repetition, take that move sequence and find a non-triple-ko situation that uses the exact same repeated move sequence ? I am afraid I don't follow. Please rephrase. In my words: you have a sequence of moves (M0) leading, to a certain position (P0). After P0 , you continue with a sequence of moves (M1) leading to position (P1) Now if P0==P1, this means that the move leading to P1 (the last move of M1 is invalid. If the sequence M1 would occur anywhere inside of M0, it would cause no harm, EXCEPT when it would be the final part of M0. But in that case, P0 would itself would be a repetition of some position length(M1) *before* P0. Am I missing something ? AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
On 18-jan-08, at 12:47, Don Dailey wrote: I recently read an interesting blog on this, where it was claimed that early optimization SHOULD be done when performance is actually a consideration (and sometimes it isn't.) The idea is that if ignore performance consideration early, you basically box yourself into a corner and suddenly it's very painful to fix a performance problem. The blog seemed fairly balanced to me, he didn't claim that you should go to herculean efforts to obfuscate your code with optimizations but that you should always be thinking about performance, especially early on when you can do something about it. So I understand the classical wisdom about early optimization but I believe there needs to be some balance and I'm open minded on the subject. Well, my own experience is that it helps a great deal to have performance in the back of your mind at all times when working on parts of code that you know are going to be critical when it comes to speed. But you don't need to do a great deal with it immediately. Only when there are easy decisions in terms of performance do you make them. This conforms nicely to the Agile Programming paradigm that one should never do more than strictly necessary. Don't program features that are not needed now for some possible future. Because more often than not that future never comes to pass (or is it past?). I think this also holds for performance to a great extent. One other problem with focusing on performance early on is that one tends to become blind for completely different approaches that are much more efficient. Not that I live strictly by this rule. Over the years I have acquired a large number of programming rules, but the only rule carved in stone is that no rule is to be carved in stone and that rules are for those who don't know what they're doing. There! ;-) Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
A question on this topic. When we discuss about suicide, are we referring to the real suicide, or self-atari? I think in some discussions it is referring to the real suicide. In other discussions, seems to be referring to self-atarai. If we are talking about real suicide, I do not see any point to allow the real suicide in the play out. What would be the gain if we allow the real suicide in the play out. I think its only effect is to introduces more board repetition and more moves in the playout. In very very rare cases a real suicide move is beneficial. If we are talking about the self-atari, that's a more interesting topic. I find it is very hard to tune. A lot of games of my engine are lost due to completely insane self-atari moves in the early games. Even I have policy to disfavor the self-atari moves, those moves just keep surfacing out. On Jan 18, 2008 9:28 AM, Michael Williams [EMAIL PROTECTED] wrote: So it's possible to create a triple-ko repetition, take that move sequence and find a non-triple-ko situation that uses the exact same repeated move sequence? A van Kessel wrote: An alternative to matching board hashes is to test for repeated move sequences. No. repeated position != repeated sequence. Since one stone is added to the board with each move, a repetition can only exist between two moves if exactly that number of stones was captured inbetween (+- pass moves) So you only have to check the positions in the game-stack where exactly the same number of black,white stones is on the board HTH, AvK ___ 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] Some thoughts about Monte Carlo
So I wouldn't be surprised at all if at some point you'll see a marriage of the best ideas of traditional Go programs and Monte- Carlo / UCT. In fact, this is most likely already happening as these Monte-Carlo programs use algorithms / ideas from the traditional programs for tactics, pattern-matching and possibly others.. And I go out on a limb to predict that at some point heavy playouts will use information like territory, eye-space and group-strength to guide their playouts just like the traditional programs do. And that using fixed 3x3 patterns will be a passing fad. You don't even have to go out on a limb ;-) One detriment to this is still that increasing the strength of playouts does not make them necessarily better. This might cause a schism in the kind of information that is needed between classical approaches and Monte Carlo. So I do not think both approaches will totally converge. This comes to my first point. Optimizing early in a project is like listening to the devil. It eats up a lot of time, the visible progress is gratifying but in the grand scheme of things it's not all that important to do early. I implemented it using pseudo-liberties because... uh, well, because that's what everyone seemed to be doing to get high numbers of playouts per second. But I already start to doubt using pseudo-liberties are all that useful. Is anybody still using pure-random playouts for anything? As soon as you start to do anything more, pseudo-liberties are pretty useless. I agree here, and I made the same mistake. But the speed of the random playout becoms less and less important with heavy playouts. This I don't understand at all. The improvement curve for being faster isn't different with heavy than with light playouts. Next I was thinking about another subject that got some attention on this list, the mercy rule. It seems to save about 10% in the number of moves per game (on 19x19) and result in about 20% gain in performance. This discrepancy is most likely due to the fact that the administration, whether using pseudo-liberties or real, is much slower towards the end of the game because you have more moves that merge chains. And those 10% moves it saves are of course always at the end. So is it relevant? I don't know whether heavy playouts will be slower towards the end of the game or not. Possibly yes, as more moves made will have a small number of liberties that will need tactical analysis. I'd say that generally reducing the move-count is a good thing whichever method one uses. Possibly at a later stage more sophisticated methods can be developed to abort a game early. Possibly the mercy rule is a premature optimization just like psuedo- liberties :-) Next I allowed suicide only for White. You allowed single-stone suicide too, I guess? This is obviously bad since it will happen constinously near the end of an MC playout. It will be like one side is forced to pass 50% of the time and the other side not. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Heikki Levanto wrote: On Thu, Jan 17, 2008 at 10:36:09PM -0500, Michael Williams wrote: I have not tried it myself, but I'm guessing it will not improve your engine. The cost of testing for simple ko is negligible and allowing it will probably prolong the playouts. I am not far enough with my engine to test yet, but my guess is that allowing a simple ko can lead to pretty long endgames, if the ko has the only playable moves left. It sounds that some sort of way to detect that would be good. If we only test for a simple ko, it is possible to get into an endgame with two kos on board, repeating for ever. My own experience when experimenting with random playouts were that without ko checking at all, around 30% of games ended in infinite loop with both sides having one (non-eye-filling) move possible, to retake the ko. With simple ko checking, around 3% of games ended in infinite loop with double ko. As long as you have some cheap way (beyond doing ko checking) of getting out of the infinite loop, either might be preferable. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] KGS bot tournaments: poll
It is two years and six months since I chose the format that we use for the monthly bot tournaments on KGS. Since then, things have changed: UCT has been invented, processing power has increased, pondering has been implemented in more programs, and CGOS is running. I get occasional requests for changes to the format of the KGS tournaments; I generally think, yes, that's a good idea, and then forget to do anything about it. So I have decided to poll the members of this list, about what changes they think desirable. HOW THINGS ARE NOW The current settings for the tournaments are listed at http://www.weddslist.com/kgs/future.html Each event consists of two tournaments, one Formal (with entry restrictions) and one Open. The events go in a cycle: 19x19+19x19, 9x9+13x13, 13x13+9x9. For each board size, the time limits (which are all sudden death) also cycle. The cycles are: 19x19 - 58m, 28m, 18m; 13x13: 13m, 18m, 28m; 9x9: 8m, 13m, 28m. All events are Swiss, with fixed numbers of rounds. WHY THEY ARE LIKE THIS The Formal/Open restriction was created to encourage commercial programs to compete. These programs' authors were wary of entering them in events in which they might have to play a whole bunch of GNU Go versions, so the Formal division was set up with the restriction that no more than one copy of GNU Go (or of anything else) could compete. But this has had only limited success in attracting entries from commercial programs. However running two tournaments at once is not a bad idea. While I am running a bot tournament, I am forced to be sitting at my computer and watching what is happening on KGS, but I am rarely overworked. So it quite suits me to be also running another bot tournament. I imagine that competitors may feel the same way. A snag with running two tournaments at once is that people may wish to enter both, but have access to only limited processing power. This involves a time hit on both programs. If the programs do not ponder, the time hit is only about 25% (assuming their opponents play at they same speed as they do; but if they ponder it is 50%. Absolute time settings are used so that I can know when each round will begin, and when the event will end. For shorter events (fewer rounds, or faster time limits) these issues are less important. My presence to administer these events is, unfortunately, still necessary, though I am required to intervene much less than in the early days. In the most recent event, I had to score the SimpleBot vs. scottbot game manually, and then terminate the game: I believe that if I had not done so, these bots would never have left the game, and would have failed to play in the next round. I am not willing to devote more than eight continuous hours to an event. However, for an event with slow time limits, I only really need to be present around the start and end of each round, so I could manage a 16-hour event (it would have to start at about 09:00 GMT) ISSUES TO VOTE ON (1.) Do we want to keep separate Formal and Open divisions? Keep two divisions [] Just have one [] (I might restrict entry to the Formal division, to programs that have already competed in the Open division, behaved well, and won at least one game there.) (2.) Do we want to keep three board sizes? Or to get rid of 13x13? Keep 19x19, 13x13, and 9x9 [] Just have 19x19 and 9x9[] (3.) Do we want to continue with three different time settings for each board size? Keep three time settings [] Just have two settings [] (4.) Do we want the time settings to be as they are now [] faster [] slower [] Note that faster time settings give more flexibility. They allow more rounds, and they reduce the need for a pre-established schedule, allowing time systems other than absolute time. (5.) Should we continue to use Absolute (sudden death) time [] change to using Canadian [] change to using byo-yomi [] (6.) Do we want the events to take longer [] be about as long as they are now [] be over sooner [] (7.) Do we want to stay with fixed-length Swiss [] switch to Round Robin[] HOW TO VOTE You can vote by responding here, if you want everyone to read your opinions; or by email to me, at the address this message was posted from. I shall not reveal the way anyone voted, nor who made the comments and suggestions made in emails to me; but I will report on the total votes, and on the comments and suggestions. As well as simply voting (by indicating your order of preference for each set of alternatives), you may explain your reasons, and suggest other possibilities. I promise to read these, and to put all the responses into a folder where I won't lose them. Nick -- Nick Wedd[EMAIL PROTECTED]
Re: [computer-go] Suicide question
John Fan wrote: If we are talking about real suicide, I do not see any point to allow the real suicide in the play out. What would be the gain if we allow the real suicide in the play out. The answer to this question has been given at least 3 times: Speed. It can take time to disallow a certain kind of move. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Some thoughts about Monte Carlo
I'm fairly new on the subject of Monte Carlo and am in the process of catching up on reading, so I hope you guys have some patience with me while I get into this and ask a lot of questions. I got side-tracked away from computer-Go programming for quite a while for various reasons but have been at it again full-time recently. Let me start by saying I haven't followed the whole Monte-Carlo / UCT story all that well. Although it was clear it did well on 9x9 I wasn't all that convinced it would scale up to 19x19. That it did well on 9x9 didn't surprise me much as I've always felt 9x9 is susceptible to see strong play using some extreme brute-force method using today's computing power. Combining Monte-Carlo methods with what's generally called heavy playouts changes things a lot however and this is where it piqued my interest. I often see reference to Monte-Carlo programs as opposed to traditional Go programs. But what I'm seeing with the heavy playouts is deja-vu all over again. It seems to me the evolution of the heavy playouts is following a similar course of that of the first rule-based Go programs in the early 1980's. To use another famous quote history doesn't repeat itself but it rhymes. So I wouldn't be surprised at all if at some point you'll see a marriage of the best ideas of traditional Go programs and Monte- Carlo / UCT. In fact, this is most likely already happening as these Monte-Carlo programs use algorithms / ideas from the traditional programs for tactics, pattern-matching and possibly others.. And I go out on a limb to predict that at some point heavy playouts will use information like territory, eye-space and group-strength to guide their playouts just like the traditional programs do. And that using fixed 3x3 patterns will be a passing fad. Anyway, as it is I have made a few initial forrays into Monte-Carlo algorithms. I hereby thank Peter Drake on his work on Orego, which is a fine package to learn about Monte-Carlo. I used it to make my own implementation. Not that there was much wrong with Orego but the best way to understand and internalize a concept is to actually implement it. Moreover I felt I needed a framework that is a bit more generalized than Orego. Lastly I was convinced of course that I'd be able to make it faster. That last part didn't turn out to be true though. On my iMac, which is a 2Ghz Core Duo, I get a little under 30K playouts on 9x9. A little over 50K when using both cores. Orego is in the same ball-park. At least making a more generalized implementation didn't hurt performance so I'm OK with this first attempt. I think there's still room for optimizations, if I thought it was important at this stage. This comes to my first point. Optimizing early in a project is like listening to the devil. It eats up a lot of time, the visible progress is gratifying but in the grand scheme of things it's not all that important to do early. I implemented it using pseudo-liberties because... uh, well, because that's what everyone seemed to be doing to get high numbers of playouts per second. But I already start to doubt using pseudo-liberties are all that useful. Is anybody still using pure-random playouts for anything? As soon as you start to do anything more, pseudo-liberties are pretty useless. Yes, using real liberties slows things down a lot. But the speed of the random playout becoms less and less important with heavy playouts. Next I was thinking about another subject that got some attention on this list, the mercy rule. It seems to save about 10% in the number of moves per game (on 19x19) and result in about 20% gain in performance. This discrepancy is most likely due to the fact that the administration, whether using pseudo-liberties or real, is much slower towards the end of the game because you have more moves that merge chains. And those 10% moves it saves are of course always at the end. So is it relevant? I don't know whether heavy playouts will be slower towards the end of the game or not. Possibly yes, as more moves made will have a small number of liberties that will need tactical analysis. I'd say that generally reducing the move-count is a good thing whichever method one uses. Possibly at a later stage more sophisticated methods can be developed to abort a game early. Lastly (for this post anyway) I looked at the multiple-suicide question. Whether allowing it or not seems to have negligable effect on performance. What I did first was to tune the komi until the win- ratio for Black and White is as close to 50% as possible using random playouts. The number ended up being 2. Next I allowed suicide only for White. This pushed Black's winning percentage up to 65%. I think this pretty much settles the matter and it's clear allowing suicide is very detrimental to quality of play in a Monte-Carlo program. That's all for today :)
Re: [computer-go] KGS bot tournaments: poll
Hi, My vote would be to keep everything like it is. Maybe use round robin when the number of participants is close to the number of planned rounds. Also, don't hesitate to make the time control shorter if it would be necessary to fit enough rounds within a reasonable time, so we can play round-robin instead of Swiss. Swiss would be good if Bill Shubert could fix it. Main problems that need fixing are: in the last round, if the two top players have not yet played against each other, they must play against each other. Also, use seeding in the first round. This would improve a lot. Thanks for organizing these tournaments. I am not sure I will participate in February, but I will participate in March. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question (Repost)
I'm sorry but I have no fixed global ip (my pcs are at my home, not at univ). But I strongly believe 32 bit applications can run on 64 bit OS. I will try to run currently running four bots and your clients as many as possible simultaneously because I've just built up an additional 2 core pc. Now I have 4+4+2 cores of Intel Core2 at 3GHz and one Athlon64 boxes in total, all running 64bit Linux. Could you send me the tar ball? Thanks. Hideki Don Dailey: [EMAIL PROTECTED]: Can you give me a login account on your machine? Then I could compile the binaries and get everything working on 64 bit linux. The you can revoke the account if you wish - I just want to build a 64 bit version. But I have it all complete (at least for 32 bit linux). All you do is unpack the tarball and run a script from the unpacked directory and everything else is automatic - including hourly upload of whatever data is produced. There is even a kill script for when you want your computer back. I would prioritize running bots on CGOS. I will eventually get the data. Right now I'm running 2 copies on my core 2 duo. I will have an automatic update soon. Hopefully by tonight but I will be in and out today and probably won't be able to work on it for a while. - Don Hideki Kato wrote: Yes, Fedora Core 5-64bit for AMD and Ubuntu 7.10-64bit for Intel. Which is better do you think, however, to stop current running bots on cgos and run your clients instead OR to keep current bots runnig? As Terry already answered to you. -Hideki Don Dailey: [EMAIL PROTECTED]: Do you run linux? I already have a tarball which has almost everything you need - and it includes the binaries and has each player set up in the registry. The only thing missing is an automated scheme to get the result files to me. I'm looking to see if I can get an ftp server working. It will be flexible enough that you can run multiple instances if you want - and stop them when you want and restart without hassle. However, if one of the long players is playing, you might lose several hours if you kill it! Of course you can use nice to run these at low priority. Are you willing?I can send you a test package now which will determine if it will run without hassle. - Don Hideki Kato wrote: Hi Don, I'm now running mogo-pr-1cpu on my quad core box, Intel Q6600 3GHz with 4GB RAM and gnugo-3.7.11-l10F, gnugo-3.7.10-l10F and FatMan-1 on an AMD athlon64 2GHz with 1GB RAM, as reference programs on cgos 9x9. I can provide these two boxes for your experiment. Then, how long will it take? Hideki Don Dailey: [EMAIL PROTECTED]: Michael Williams wrote: It is a very nice graph. I wish we could see the next 11 doublings. With some help, I could redo this experiment and add: 1 or 2 more levels. A version of gnugo with known strength. and/or some fixed version of mogo - which we could simultaneously test on CGOS. I would need an enormous amount of power to complete this with a good sample in less than a few months. Anybody have any linux machines lying around? They need to be relatively powerful and probably need at least 1 gig of memory due to the large tree size I would have to set up. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- [EMAIL PROTECTED] (Kato) ___ 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/ -- [EMAIL PROTECTED] (Kato) ___ 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/ -- [EMAIL PROTECTED] (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
Jason House wrote: On Jan 18, 2008 11:30 AM, Raymond Wold wrote: With simple ko checking, around 3% of games ended in infinite loop with double ko. Double ko's should not have an infinite loop. black takes ko A. White takes ko B. Black can't retake ko B, so must fill ko A. White then fills ko B. No infinite loop... The only time I've had issues with this stuff was when my anti-eye-filling rule was broken. Hmm, you're right, must have been triple ko actually. That fits with the percentages better as well. Perhaps there were other possible looping situations as well, I didn't actually check what it was that looped, only that it did, and that my idea for breaking-the-loop (stopping playouts after X moves) was on average slower than just always checking for superko in a hash table. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KGS bot tournaments: poll
Hello All, First, Thanks to Nick for doing these tournaments and for asking what we would like. Sticking with most of the replies I have seen so far, I will send my votes on the form directly to Nick, but will comment here on a few points. First, I am wondering about the 2-out-of-3 bias for smaller boards. Given that CGOS is now a regularly used resource, could simple back and forth 19x19 one month, and the 9-13 parings the next be a better choice? With so many stronger programs are we now ready for more regular 19x19 tournaments? I think so. The Formal/Open structure has always had a distinct possibility of impacting us because SlugGo is a GNU Go wrapper (not the much feared clone) which significantly uses GNU Go code, but often makes moves that GNU Go would not (for better and for worse). So far it has not been a problem sharing the Formal division with the GNU folks. I have asked them a few days in advance of the tournament if I can take the Formal spot and except for a few times when I did not get any answer in a timely way (it happens on open source projects) they said OK, or if they wanted the Formal spot to check something new, SlugGo went into the Open division. It has worked fine for us. But the reason for the divide (what if there are a whole slew of GNU clones?) never did materialize. SlugGo has not been in a KGS tournament in a while, but we hope to get some things done and be able to bring some new software to a tournament soon. Cheers, David On 18, Jan 2008, at 9:41 AM, Nick Wedd wrote: It is two years and six months since I chose the format that we use for the monthly bot tournaments on KGS. Since then, things have changed: UCT has been invented, processing power has increased, pondering has been implemented in more programs, and CGOS is running. I get occasional requests for changes to the format of the KGS tournaments; I generally think, yes, that's a good idea, and then forget to do anything about it. So I have decided to poll the members of this list, about what changes they think desirable. HOW THINGS ARE NOW The current settings for the tournaments are listed at http://www.weddslist.com/kgs/future.html Each event consists of two tournaments, one Formal (with entry restrictions) and one Open. The events go in a cycle: 19x19+19x19, 9x9+13x13, 13x13+9x9. For each board size, the time limits (which are all sudden death) also cycle. The cycles are: 19x19 - 58m, 28m, 18m; 13x13: 13m, 18m, 28m; 9x9: 8m, 13m, 28m. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] New scalability study progress report
The new scalability study is in progress. It will be very slow going, only a few games a day can be played but we are trying to get more computers utilized. I will update the data a few times a day for all to see. This includes a crosstable and ratings graphs. The games will be made available for anyone who wants them. Although it's not on the graph itself, Gnugo-3.7.11 level 10 is set to be 1800.0 ELO.The bayeselo program is used to calculate ratings. Results can be found here: http://cgos.boardspace.net/study/index.html bayeslo assumes all players are equal strength until significant evidence proves otherwise, and with only a few games played each, the graph will look truly strange, but this will correct itself in time. Each data point in the x axis represent a doubling in power. There are 13 doublings represented and mogo was set to approximate FatMan in strength at each point - at least at the lower level but only with a very crude and rough estimate. Since I don't know how well mogo scales compared to FatMan, we can only wait and see how this works out at the top levels. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
On Jan 18, 2008 11:30 AM, Raymond Wold [EMAIL PROTECTED] wrote: My own experience when experimenting with random playouts were that without ko checking at all, around 30% of games ended in infinite loop with both sides having one (non-eye-filling) move possible, to retake the ko. My experience is that without simple ko checking, games ended in infinite loops where the ko was the only move left. They'd just go back and forth capturing the lone stone... With simple ko checking, around 3% of games ended in infinite loop with double ko. Double ko's should not have an infinite loop. black takes ko A. White takes ko B. Black can't retake ko B, so must fill ko A. White then fills ko B. No infinite loop... The only time I've had issues with this stuff was when my anti-eye-filling rule was broken. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
An alternative to matching board hashes is to test for repeated move sequences. No. repeated position != repeated sequence. Since one stone is added to the board with each move, a repetition can only exist between two moves if exactly that number of stones was captured inbetween (+- pass moves) So you only have to check the positions in the game-stack where exactly the same number of black,white stones is on the board HTH, AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
On 18-jan-08, at 12:01, Gian-Carlo Pascutto wrote: But the speed of the random playout becoms less and less important with heavy playouts. This I don't understand at all. The improvement curve for being faster isn't different with heavy than with light playouts. I see I didn't word this very clearly. I mean the speed of updating the administration during playout, like liberties or pseudo-liberties becomes less important. Possibly the mercy rule is a premature optimization just like psuedo- liberties :-) I don't know yet... Next I allowed suicide only for White. You allowed single-stone suicide too, I guess? This is obviously bad since it will happen constinously near the end of an MC playout. It will be like one side is forced to pass 50% of the time and the other side not. No, I did not allow single-stone suicide for either side as I see no reason to allow it and it would lead to lots of potential problems (like many board repetitions). Just allowing multiple-suicide for White is enough to push up Black's winning percentage that much. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study progress report
On Fri, 2008-01-18 at 20:31 -0500, Don Dailey wrote: Although it's not on the graph itself, Gnugo-3.7.11 level 10 is set to be 1800.0 ELO. On the web page it says you are using --min-level 8 --max-level 8. Each data point in the x axis represent a doubling in power. There are 13 doublings represented This is a bit confusing. I think it's clearer to say there is 1 baseline and 12 doublings. It's also confusing on the web page that Mogo_01 actually corresponds to 0 doublings in the graph. So if I understand correctly: Mogo_13 = 64 * 2^12 = 262,144 simulations FatMan_13 = 1024 * 2^12 = 4,194,304 simulations Sorry for the minor nitpicks. Looking forward to the results! -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KGS bot tournaments: poll
On Jan 18, 2008, at 9:41 AM, Nick Wedd wrote: The Formal/Open restriction was created to encourage commercial programs to compete. These programs' authors were wary of entering them in events in which they might have to play a whole bunch of GNU Go versions, so the Formal division was set up with the restriction that no more than one copy of GNU Go (or of anything else) could compete. But this has had only limited success in attracting entries from commercial programs. So the commercial programs are not showing anyway, what about the 2nd reason of having 2 division: how many GNUGO-clones are there typically; would it really be a problem? Christoph ps. Like Jason I will send my vote separately, after the weekend. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study progress report
I wish I had named the weakest players _00 instead of _01 and expressed everything as you are suggesting, it would indeed be clearer. I could actually fix this by reprogramming the scripts without changing the running programs. If I get a burst of energy perhaps ... The tarball is slightly interesting. I have it so that you untar into a directory, run a script and there is nothing left to have to do - every hour a summary of the results so far is ftp'd to my computer. This is so others can help me with the study.You can stop or restart the script at any time. So far, I am running two instances and I am running another instance on a friends computer remotely. Here is a simple riddle which I had to solve but made me think for a moment: It involves how to keep track of various versions of the result files which each user would send me every hour. Do you put a version number on it? How do you track which file belongs to which user and which is the latest version without mixing things up and duplicating data? My first reaction was to somehow label or stamp each file, perhaps with the hostname or something and a version number.But none of this is necessary. - Don Jeff Nowakowski wrote: On Fri, 2008-01-18 at 20:31 -0500, Don Dailey wrote: Although it's not on the graph itself, Gnugo-3.7.11 level 10 is set to be 1800.0 ELO. On the web page it says you are using --min-level 8 --max-level 8. Each data point in the x axis represent a doubling in power. There are 13 doublings represented This is a bit confusing. I think it's clearer to say there is 1 baseline and 12 doublings. It's also confusing on the web page that Mogo_01 actually corresponds to 0 doublings in the graph. So if I understand correctly: Mogo_13 = 64 * 2^12 = 262,144 simulations FatMan_13 = 1024 * 2^12 = 4,194,304 simulations Sorry for the minor nitpicks. Looking forward to the results! -Jeff ___ 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] Suicide question
An alternative to matching board hashes is to test for repeated move sequences. You need a separate test for each sequence length, but the most common one should be the shortest one. Heikki Levanto wrote: On Thu, Jan 17, 2008 at 10:36:09PM -0500, Michael Williams wrote: I have not tried it myself, but I'm guessing it will not improve your engine. The cost of testing for simple ko is negligible and allowing it will probably prolong the playouts. I am not far enough with my engine to test yet, but my guess is that allowing a simple ko can lead to pretty long endgames, if the ko has the only playable moves left. It sounds that some sort of way to detect that would be good. If we only test for a simple ko, it is possible to get into an endgame with two kos on board, repeating for ever. It might make sense to test for (super)ko only in the endgame, when there are not so many possible moves left. As long as there are many choices, a random playout will not get stuck in a loop anyway. Then again, testing for the game state may be as expensive as testing for ko... I guess it is early for me to speculate on that, as my engine isn't even playing legal moves yet... Premature optimizing, and all that. - Heikki ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
So I wouldn't be surprised at all if at some point you'll see a marriage of the best ideas of traditional Go programs and Monte-Carlo / UCT. In fact, this is most likely already happening as these Monte-Carlo programs use algorithms / ideas from the traditional programs for tactics, pattern-matching and possibly others.. And I go out on a limb to predict that at some point heavy playouts will use information like territory, eye-space and group-strength to guide their playouts just like the traditional programs do. And that using fixed 3x3 patterns will be a passing fad. My first MC-Program actually used the code from my knowledge intensive program Viking. Then I rewrote everything from scratch which is Valkyria2.7. And I am now working with rewriting the search part in order to allow threaded search and that is Valkyria3. Since Viking used territory, eye-space etc to compute groupstrength, I guess I could comment on what I believe can and cannot be used in heavy playouts. Valkyria uses eye-space calculations, which prunes really bad moves in the playouts. My board representation keeps track of all liberties, and surrounding stones for all chains. It is designed for playouts (undo is not possible) but a lot of information is computed so that at it is easy to write knowledge-algorithms. It is faster than my old Vikingcode but still it is much easier to work with. Valkyria does not do explicit 3x3 patternmatching, but uses handcoded patternmatching which often are equivalent to 3x3 patterns. But sometimes the code will look at a larger area. It also computes ladders in playouts. The ladders are fast and sloppy, that is, in some situations they make mistakes, but in the playouts one makes (and should make) compromises with correctness all the time. It is the UCT-search that should find out how to play correctly not the playouts. My program as a consequence is probably the slowest in terms of playouts/second. It does about 1200/sec on 9x9 on Pentium-M 1.4Ghz. The good thing is that the code is so bloated I do not slow it down so much when I add new stuff to the playouts. I recently found a lot of bugs working with version 3 so I added that to the 2.7.8 which has been rated about 40-60 Elo higher than 2.7.7. I do not think that territory and groupstrength will ever be included into heavy playouts. Because this is implicitly computet by the MC-evaluation. Several MC-programs today collects statistics such as the probability that each position on the board is assigned to black in the end of playouts. I recently added a colored graph of such statistics to Valkyria3 and it looks really pretty. You can easily see what is safe territory or not and which groups are weak and not. Actually this visualisation is good to hunt for bugs in the playouts. If a groups is almost dead despite having plenty of eyspace then something can probably be fixed in the playouts. These kind of statistics looke quite nice already after as little as 100 playouts, and are in my opinion better than what I ever achieved with Viking evaluation function. Most importantly one sees that although MC-evaluation often misjudges positions, the effect of moves is almost always goes in the right directions. Traditional statical evaluation has the problem of being brittle. It does 90% right but 10% completely wrong. MC-eval does 80 % right and 20% slightly wrong. (I made up those numbers of course but hope you get the idea) So computing territory and groups strength in playouts appears to me as reinventing the wheel because this is what MC-eval actually is doing implicitely. An open question is to what extent these statistcs can be used to improve performance in UCT-search or biasing playouts. I have no clear idea about it because, in some versions of my programs it was good and sometime it did not. It may be that UCT-search itself is so efficient that whenever you have reliable statistics for a position the search does not benefit from that knowledge anymore. I also agree that some really old techniques do come back. In my first goporgram for the Amiga I wrote 18 years ago approximately I first implemented the following pattern ?B? W+W ?B? and variations thereof. When I first made the playouts heave this was the first patterns I added, and it worked really well. So the irony is that my current programs have more in common with my very first completely stupid program than the versions in between... -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Some thoughts about Monte Carlo
Mark Boon wrote: On 18-jan-08, at 12:01, Gian-Carlo Pascutto wrote: But the speed of the random playout becoms less and less important with heavy playouts. This I don't understand at all. The improvement curve for being faster isn't different with heavy than with light playouts. I see I didn't word this very clearly. I mean the speed of updating the administration during playout, like liberties or pseudo-liberties becomes less important. I agree. No, I did not allow single-stone suicide for either side as I see no reason to allow it and it would lead to lots of potential problems (like many board repetitions). Just allowing multiple-suicide for White is enough to push up Black's winning percentage that much. Thanks for the info. I guess I need to retest to see if the tradeoff I made still makes sense. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study progress report
Jeff Nowakowski wrote: On Fri, 2008-01-18 at 20:31 -0500, Don Dailey wrote: Although it's not on the graph itself, Gnugo-3.7.11 level 10 is set to be 1800.0 ELO. On the web page it says you are using --min-level 8 --max-level 8. I realized after I started the study that I was using the wrong level - I had intended to start with level 10 but it's actually level 8. I kicked myself for that - but I don't want to change it now. It's just a point of reference anyway. Each data point in the x axis represent a doubling in power. There are 13 doublings represented This is a bit confusing. I think it's clearer to say there is 1 baseline and 12 doublings. It's also confusing on the web page that Mogo_01 actually corresponds to 0 doublings in the graph. So if I understand correctly: Mogo_13 = 64 * 2^12 = 262,144 simulations FatMan_13 = 1024 * 2^12 = 4,194,304 simulations I'm still tweaking the web page.Take a look at it now and tell me what you think. Your formula is correct, Mogo_01 is 64 simulation and FatMan_01 is 1024 simulations. I ran off a few fast games before I started to get a rough idea of equivalence and it's an amazing 16 to 1 at the low levels.Have no idea how each programs scales to higher levels. It will take many games for the ratings to have any meaning. - Don Sorry for the minor nitpicks. Looking forward to the results! -Jeff ___ 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/
