Re: [computer-go] Dynamic Komi's basics
On Thu, Feb 11, 2010 at 01:06:34PM +0100, Petr Baudis wrote: extra_komi = 7.5 * handicap_stones_count Then it is linearly decreased until it hits 0 at move 200. All this discussion made me think - has anyone tried to adjust the komi between the simulations. Run (say) 10% of the simulations you expect to run for a move, and see how many of the moves ended in a win. If there are many moves, adjust the komi to make winning harder. If there no moves at all, adjust the komi to make winning easier. Repeat after a small number of simulations (maybe after every one). Yes, this will add noise to the results, when a reasonably good move gets a loss marked against it when the komi gets too hard, but then again, the whole system is noisy already, with random simulations at the leaves of the tree... This sounds like such a simple and obvious idea that someone must have tried it already. If I had a working implementation to play with, I might try it myself, but I don't, and I don't have the time to set one up and try. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
On Wed, Nov 25, 2009 at 09:01:22AM -0500, Don Dailey wrote: You could of course just play games where you choose each player randomly. If you have 256 feature you have a ridiculous number of combinations, more than you could possibly test but before each test game you just pick a combination of features randomly for each player.In this way about 1/4 of the games will be relevant for each feature, regardless of how many features you are testing.(1/2 will have the feature on and half of those games will be against opponents who have the feature off.) Wouldn't it be more effective to choose one player randomly, and make the other a mirror image of it? That way, every game would give some information of the relevance of one setting. At least in the very beginning... -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Neural networks
On Wed, Oct 14, 2009 at 03:34:59PM +0300, Petri Pitkanen wrote: Neural network tend to work well in those cases where evaluation function is smooth, like backgammon. Even inbackgammon neural networks do give good results if situation has possibility of sudden equity changes like deep backgames and deep anchor games. Top backgammon programs 3-ply search on top neural network to handle these problems. I do not know wher neural nets would fit well, perhaps finding invasion spots? I have been speculating about a NN evaluation function for go, feeding it a lot of preprocessed information about the position, like number of strings with 1,2,3,4, or more liberties, number of stones in same, number of separate groups, number of obviously dead stones, strings, and groups, number of points clearly controlled by each player, etc, etc. This should be possible to train from existing games where we know the result (in the beginning it is 50-50, in the end one or the other has won 100-0. Assume some simple function in between). I have never had the time nor the patience to pursue this any further - I have more interesting ideas, and far too little time... If anyone wants to play with it, I'd love to hear of any results. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CUDA and GPU Performance
Interesting stuff. I don't have the skills nor the time to make such experiments myself, but here is a simple idea: When using a bitmap representation of the board, it is quite possible to find all eye-like points with a constant number of bit-shifting operations. That should reduce the number of branches. It might even be possible to check liberties and remove captured stones with constant number of loopings, at least for most reasonable board positions (the number would have to be unreasonably large for pathological positions with very long and narrow groups). This still leaves a few places where the code will have to branch, most notably choosing a random legal move. And the ending of the simulation, of course. If we solve all these, it should be possible to run simple playouts in parallel, taking full advantage of the SIMD nature of the GPU. Of course, each playout would be slower than necesary, but maybe that would even out with many enough done in parallel. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
On Sat, Aug 15, 2009 at 10:03:11AM -0600, w...@swcp.com wrote: There are many ways to track the liberties of a chain And there are many different implementations of each: * none * count pseudo liberties * simple count * do count, sum, and sum squared, which can detect atari * array of liberties * store all liberties * store first k liberties * linked list of liberties * doubly linked list, fixed locations for liberties (needs many nodes) * doubly linked list, also store liberty (needs only 1600 nodes) You can also use board-sized bitmaps. Merging is a trivial OR operation. -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Really basic question
On Tue, Jul 07, 2009 at 09:16:25AM +0200, Oliver Lewis wrote: You should also read up on the all moves as first (AMAF) technique. This is even more surprising because it attributes the outcome of a random game to every move of that colour during the random game, as if that was the move that had been played first. This generates information to help rank the moves even more quickly. Actually, it is not so surprising. Since the playouts are random, they have no idea of urgency - they leave large groups in atari for many moves, and it is a toss of a coin who plays to the crucial point first. Most likely it does not happen on the first move. But if that is the game-deciding point, it makes sense to give credit to who ever got to play it. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 1x1 patterns?!
On Mon, Jun 22, 2009 at 11:33:25AM -0700, Peter Drake wrote: I've seen reference in some papers to 1x1 patterns. What does that even mean? A point is either black, white, or vacant, and it's illegal to play there unless it's vacant. I haven't seen the papers, so I can only speculate. But I can immediately think of patterns like the following, which all depends on having a sufficiently complex representation of the board: - if I play there, I will be in atari - if I play there, I put an enemy in atari - That's an eye-like point, don't play there - Playing here connects to two previosl-unconnected groups - and one of them is unconditionally alive and the other is not - Playing here affects some local fight far away (ladder break) - Playing here is legal, but has no chance of ending up as my point, so makes no sense But has anyone seen any good 0x0 patterns ;-) -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New CGOS
On Fri, Jun 05, 2009 at 03:49:11PM -0400, Don Dailey wrote: Handicap games opens a can of worms. Of course, any program is free to give its opponent any handicap it wants, by passing in the opening (if the opponent didn't pass last). It is up to the operator of the bot to decide when and how much handicap to give, and how to analyze the results. The handicap-giving program can play under a different name, so that for CGOS it looks like a totally separate entry, with its own rating. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New CGOS (was:Negative result on using MC as a predictor)
On Fri, Jun 05, 2009 at 11:19:51AM -0400, Don Dailey wrote: When I complete the new server, I hope that it will be easier to collect larger samples of games. I think this will help the situation a little. There will be multiple time controls, but they will be in sync, so that your program can always play in a shorter time control game without missing a game at the longer time control.The idea is to keep your bot busy while waiting for future rounds.You play in the longest time control, but when you are finished you can play fast games while waiting. I will have 2 or 3 levels of this, I haven't decided yet. If I have 3 levels, the slowest time control will probably need to be a little slower than CGOS uses now. That sounds fine for those bots that have implemented time controls. Simple-minded bots that just play a given number of simulations, or do other things in (more or less) constant time will loose the too fast games straight out. I suppose your server can ask the bot if it supports time controls, and only then let it play fast games. I will also have a test mode for new bots. The server itself will play test games with your bot while you debug it. Good idea! I have used cgos to debug my half-finished bots before, and felt a bit bad about wasting the time of more serious bots. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New CGOS (was:Negative result on using MC as a predictor)
On Fri, Jun 05, 2009 at 12:38:22PM -0400, Don Dailey wrote: You will be able to select which time controls you are willing to play - the server will not force you to play in all of them. Some may choose to play only fast games and other may not be able to play in the fast games, such as perhaps sluggo. Fine! -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Simple MC implementations
Hi, I have some ideas I would like to play with, but too little time to write a whole program from scratch. So I am looking for a decently written MC program for a starting point. (Later I may want to look at some tree search too, so it it has UCT or similar, it would be a bonus). I am fluent in C and C++, can manage Java, and a number of other languages. I work on a Linux system. I know there are a number of reference implementations around, but are they all listed on a single page, so I could quickly take a look at a handful, before deciding where to go? Simple googling didn't get me to sucha list... At this point I don't care for performance, multi-threading, or even time controls. All I want is a simple implementation of MC that is easy to read and to tweak, so I can see if my idea works at all. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] time measurement
On Tue, Feb 03, 2009 at 10:41:53AM +, Nick Wedd wrote: Providers of Go servers claim that it would be pointless to try to implement client-side time, as players would be able to cheat by hacking their clients and fiddling with the clock. I don't doubt that they would try to cheat, indeed I know that they would; but providers of chess servers have been able to prevent cheating. As I understand it, their clients perform CRC checks on themselves to ensure that they have not been hacked, and the packets they send are CRC-checked by the server to ensure that the packets have not been hacked. Sorry, I don't buy that. It may work with an audience of human players who are not good programmers. But for a person who is already writing a go-playing program, and the whole time management in it, adding what ever cheats sounds trivial. Besides, this would add an extra layer of complexity to be programmed, with new chances for mistakes. All in all, I think this is a messy and unreliable solution to a problem I have not seen happening. For what it is worth I vote against client-side time controls. - Heikki who admittedly doesn't even have a functional program at the moment -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] time measurement
On Tue, Feb 03, 2009 at 03:51:14PM -0200, Mark Boon wrote: On Feb 3, 2009, at 2:34 PM, Heikki Levanto wrote: All in all, I think this is a messy and unreliable solution to a problem I have not seen happening. For what it is worth I vote against client-side time controls. Maybe you haven't seen it. That doesn't mean it doesn't exist. True enough. I always thought that security-certificates, signed applications and public-key encryption were well equipped to tackle a problem like this. But I'm certainly no security expert. No amount on crypto-mumbo-jumbo will solve the problem that the server will have to trust the program, and its author. Signing can provide some little assurance that the program running today is the same as was running yesterday, but that's about all. As long as we can write our own programs, there is no way to stop us from cheating in them, intentionally or by accident. I still think the that such time controls would take too much work to implement, make it easier to cheat, and offer no reasonable solution to a problem that may not warrant it. But that is, of course, my opinion. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re: [computer-go] 3-4-5 rule
On Wed, Dec 31, 2008 at 12:25:01PM +, p...@tabor.com wrote: I think Heikki makes a valid point here. I am not a particularly strong player (about 1-2 dan european), but I have learned that playing defensively is generally detrimental to the final result, whereas taking the initiative is more likely to lead to a win. If moves close to the existing position are given much greater weight than those further away, this may result in more defensive play than otherwise. Actually, as I undersand it, the rule was not to play close to the opponent's last move, but to limit play to either - 3rd, 4th, or 5th row - near any stone already played. This makes much more go-sense to me, even though I am a weak player (something like 5 kyu in Denmark). This rule will allow most of the common side extensions, invasions, etc, as well as answering any move locally or not. It will disallow some few moyo-reducing moves, but not too many. I guess in most cases those moyos can also be reduced by playing close enough to other stones, and/or on the 4th or 5th line. Of course a clever player who knows about this can direct the game so that he ends with a moyo, where the optimal reduction move does not get considered. That sounds tricky, and the advantage from such is slight, he can be a tiny bit more confident of keeping his moyo... - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, Dec 30, 2008 at 02:01:29PM -0500, Don Dailey wrote: It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) So sorry, but as far as I can see, three games don't prove very much. Could you please run at least 10 games more, before jumping into conclusions. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, Dec 30, 2008 at 08:01:27PM +0200, Berk Ozbozkurt wrote: I think such a change may make engine objectively stronger while making it more vulnerable against humans. Even if the human opponent isn't aware of the move pruning logic initially, it wouldn't take a lot of games to figure out that the computer never makes a move away from the last move to the center or to the sides. So sorry, but I think you have misunderstoodthe rule being tested here. It has nothing to do with the last move played, it is all about *not* playing to a point that is more than 3 (or 2) poitns away from any stone on the board, *or* that is on the 3th 4th, or the 5th row from the edge. This still leaves open a possibility of setting up two ladders, so that a ladder break somewhere in the center would be the right move. But even then, the random nature of the MC playouts would make such a position look pretty bad, and direct the program away from it - which would most often be good playing style anyway. - H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Wed, Dec 31, 2008 at 12:25:10AM +0100, Rémi Coulom wrote: If you'd like to try a simple pruning scheme that improves playing strength on 19x19, then I'd suggest progressive widening. It only works in the tree, not in the playouts. You don't need complex patterns for progressive widening to work. You can simply use distance to the previous move. Search moves at distance 1 from the previous move for N playouts. Then add moves at distance 2 for N*x playouts. Moves at distance 3 for N*x*x. So, you'd be playing like a beginner, with a local answer to every move the opponent makes. Never taking sente to play elsewhere. Sounds like a receipe for a disaster to me. But then again, I am only a kyu-level player, so I may be wrong... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 results (so far)
On Wed, Dec 24, 2008 at 01:27:46PM -0500, Don Dailey wrote: Basically, in the playouts or move choice I veto any move to the 3rd 4th or 5th line unless there is a stone of either color within distance 2 manhattan distance. Another version does 3 manhattan distance. I hope you mean that you veto any move *not* on the 3rd, 4th, or 5th line, unless there is a stone within the limit distance. Or, to phrase it in other words: - Any move on 3-4-5 line is OK - Any move close than 2 or 3 points from any stone is OK - All other moves are not OK -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
On Wed, Dec 10, 2008 at 12:39:55PM -0800, terry mcintyre wrote: I once heard a simple rule which seems to cover just about everything interesting: consider only moves which are on the 3rd and 4th lines, and/or within a manhattan distance of n, for some small n, of some other stone already on the board. If memory serves, David Fotland mentioned this at the Portland Congress. Some players favor opening moves on the fifth line, however. And the occasional funny guy playing the center point... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MC Opening stage
On Wed, Dec 10, 2008 at 09:57:18PM +0100, [EMAIL PROTECTED] wrote: And 6-7 every now and then (humans imitating MC bots?). Well, didn't Bruce Wilcox recommend an opening that built a line across the board, starting at 4-10 (middle of the side). Was supposed to be effective against people who didn't expect it, and not too bad even against those who knew it... Not something I would dare to play in a serious tournament, but then again, I don't play serious tournaments these days. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On Wed, Dec 03, 2008 at 09:55:07AM -0200, Mark Boon wrote: I thought about that, but I was afraid the code would become too obscure. After all, this is supposed to be a reference implementation. But maybe I should actually give it a try to see what it would look like. I agree that the reference implementation should be maximally clear code. Performance is not all that important here, correctness is. Having said that, I can't help responding to one detail: I had seen people write about memory usage of the tree, but never understood the concerns. One thing to remember is that more memory use means more cache misses, and more access to the main memory. On modern computers, those can cost as much as executing a thousand instructions! So memory optimizing can often pay off, also with respect to time! Of course, Java does a lot of memory management behind the scenes, so optimizing such can be harder... But when writing in C or C++, it does make sense. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Tree Search reference bot
On Wed, Dec 03, 2008 at 11:24:22AM -0200, Mark Boon wrote: Heikki wrote: One thing to remember is that more memory use means more cache misses, and more access to the main memory. On modern computers, those can cost as much as executing a thousand instructions! So memory optimizing can often pay off, also with respect to time! I've seen this stated often. But color me skeptical. Maybe I was quoting common wisdom without having checked it personally. I only remember one case - not related to go at all - where optimizing the memory stuff made a noticeable difference. I would also like to see hard evidence. But not badly enough to put in the necessary work to get some ;-) - H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] FW: computer-go] Monte carlo play?
On Sat, Nov 15, 2008 at 11:38:34PM +0100, [EMAIL PROTECTED] wrote: Being a computer scientist but new to go, i can grasp some of the theory. The question I was trying to get across was: In a game of self play, if both parties are employing only monte carlo, surely its not a good conceptual representation of a human, and if the reinforcement learning is based on random simulations wouldnt it be very weak when playing a real human? Here is another amateur answering. The way I understand it, modern Monte Carlo programs do not even try to emulate a human player with a random player - obviously that would not work. What they do is that they build a quite traditional search tree starting from the current position. They use a random playout as a crude way to evaluate a position. Based on this evaluation, they decide which branch of the tree to expand. This is the way I understand the random playouts: If, in a given position, white is clearly ahead, he will win the game if both parts play perfect moves. He is also likely to win if both parts play reasonably good moves (say, like human amateurs), but there is a bit more of a chance that one player hits upon a good combination which the other misses, so the result is not quite as reliable. If the playouts are totally random, there is still a better chance for white to win, because both parts make equally bad moves. The results have much more variation, of course. So far it does not sound like a very good proposal, but things change if you consider the facts that we don't have perfecr oracles, and good humans are slow to play out a position, and can not be integrated into a computer program. Whereas random playouts can be done awfully fast, tens of thousands of playouts in a second. Averaging the reuslts gives a fair indication of who is more likely to win from that position, just what is needed to decide which part of the search tree to expand. The 'random' playouts are not totally random, they include a minimum of tactical rules (do not fill own eyes, do not pass as long as there are valid moves). Even this little will produce a few blind spots, moves that the playouts can not see, and systematically wrong results. Adding more go-specific knowledge can make the results much better (more likely to be right), but can also add some more blind spots. And it costs time, reducing the number of playouts the program can make. Hope that explains something of the mystery Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] FW: computer-go] Monte carlo play?
On Sun, Nov 16, 2008 at 11:46:28AM +, D Gilder wrote: This is the way I understand the random playouts: If, in a given position, white is clearly ahead, he will win the game if both parts play perfect moves. He is also likely to win if both parts play reasonably good moves (say, like human amateurs), but there is a bit more of a chance that one player hits upon a good combination which the other misses, so the result is not quite as reliable. If the playouts are totally random, there is still a better chance for white to win, because both parts make equally bad moves. The results have much more variation, of course. So far it does not sound like a very good proposal, but things change if you consider the facts that we don't have perfecr oracles, and good humans are slow to play out a position, and can not be integrated into a computer program. Whereas random playouts can be done awfully fast, tens of thousands of playouts in a second. Averaging the reuslts gives a fair indication of who is more likely to win from that position, just what is needed to decide which part of the search tree to expand. Do you know what use (if any) is made of the standard deviation of the results? Now statistics isn't my strong point, but one of the first and most successfull systems was called UCT for Upper Confidence Bound. It calculated some sort of expected error, and added that to the winning ratio. Then it expanded the branch that had the highest value. If that expansion was a win, the error margin would get smaller, but the average result would get higher. Perhaps some other branch would be tried next, but this one would still be a good candidate. If the result was a loss, the average would drop, and so would the error, so this move would become much less likely to be expanded. I am sure someone who understands statistics will soon jump in and correct my explanation :-) - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Publishing source for (yet another) MC simulator
On Tue, Nov 04, 2008 at 09:48:35AM -0500, Don Dailey wrote: My personal preference might be C, but at work I have to learn more Java... Anyway, I don't want to start a language war here, not again... Oh, you want a war :-) Seriously, Java has it's place but if you really get serious about developing the highest performance strong playing bot I think you pretty much are forced into a low level language. I see only a very few reasonable choices if you want to go that way: yes, but my reason for considering Java has nothing to do with how good a language it is, nor how well it suits the task at hand. The main argument is that in my day work I need to code java, and any practice I can get with it is useful - and may even be an excuse to do some of the stuff at work time. If I didn't have enough C-coding to do at work now, I would write C on my spare time, but as things are now, I get that need satisfied all right. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Publishing source for (yet another) MC simulator
On Mon, Nov 03, 2008 at 03:40:42PM -0800, Zach Tellman wrote: There are a number of these floating around already, but I've noticed that their source code tends to be somewhat opaque. I have noticed the same. Is there a centralized list of available engines and toolkits? With that in mind, I've written a simulator that tries to keep a balance between performance and clarity. It has comprehensive error checking, and achieves 30k+ playouts/sec with light heuristics (naive move weighting and exploitation of atari). Adding more sophisticated move selection should be relatively straight-forward. Sounds interesting. Source code can be found at http://github.com/iucounu/ergo . If anyone finds a use for it, or has any questions, don't hesitate to contact me. I took a quick look, mostly to see what language you had written it in. (That's c++, in case others are interested). Some day real soon now I will have some time to play around with a go program. Instead of writing my own from scratch (how many times have I started), I could well start from a ready-made thing, to get quickly to the point where I can try out various ideas. Yours look like a good candidate, from what little I could see - provided that I want to work in C++, which is something I haven't decided yet. My personal preference might be C, but at work I have to learn more Java... Anyway, I don't want to start a language war here, not again... Once again thanks for releasing your code. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] symmetry optimizations vs statistics?
On Tue, Sep 30, 2008 at 04:29:12PM +0200, A van Kessel wrote: There have been discussions about handling symmetry in the past. See for instance Heikki Levanto's group theoretic hashing paper. I'm afraid you must have misattributed that - I don't know much about hashing, less about group theory, and not being in the academia, I am not publishing papers. I am just a programmer who likes to dabble with programming Go, when other interests don't claim all of my spare time. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
On Wed, May 14, 2008 at 03:47:55PM +0200, Norbert Gábor Papp wrote: I want to remove dead-stones which means : [...] I'm interested in the function dead(), which is true when a stone is dead after both player pass,and the game is ended. The simple answer is that there is no such function! Most Monte-Carlo programs play the game out to the bitter end, when they can assume that all stones on board are alive, and all territory is segmented into one-point eyes. Then it is trivial to see who owns what. The alternative is to collect the stones into groups, and check which groups have (or can make) two eyes. This gets quite complex. Even humans make the occasional mistake in evaluating the position after both have passed, especially beginners. Some say that the game should never reach the point of counting, since at some point the loosing part will see that he can not win, and will resign on the spot. I think it will be a long time before programs can do that with confidence... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 10k UCT bots
On Tue, May 13, 2008 at 01:34:37PM -0400, Don Dailey wrote: The point after an illegal move is quite a bit more likely to be selected. If the list had just 1 illegal point, then the point after it in the list is twice as likely to be selected as any other point. Perhaps if you added a little noise after each move (perhaps swapping to points at random) you could minimize any seriously bad effects? I think the problem becomes more pronounced near the end of the simulation, when most of the boars is filled with stones or 1-point eyes. If, at that time, there are two legal moves left, one near the beginning of the list, and one near the end, then the second one can end up as much more likely to be chosen. And if the first one is the key point to the position, it may never even be noticed. No idea how likely this scenario is in real games, but at least it is possible. And if your search tree is large enough, once-in-a-thousand situations occur all the time... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS comment field. wasTest position set for MC programs
On Sun, Apr 27, 2008 at 11:10:07PM -0400, [EMAIL PROTECTED] wrote: I have a CGOS feature request. Something complementary to the CGOS information on Senseis. I would like the client to have an optional field to designate a comments text file. The file would contain a sentence or two describing the particular version of the engine running: the kind of information that we try to cram into the name, but less cryptic. The engine's Crosstable page?on the CGOS web site?might be a good place to display the comment. I think the threshold for editing a comment file on one's own computer is lower then for editing a wiki page. Seconded. While we are at it, could we also add a separate command for the URL of the home page of the program, if any. That is useful information, and if it is not hidden in a free-form text comment, programs can easier get to it and display the link to the user. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 13x13 scalability study continued ...
On Mon, Apr 14, 2008 at 12:25:15PM -0400, Don Dailey wrote: Gian-Carlo provided a light version of Leela, and we are extending the scalability study in order to answer the question, Do light play-outs scale similarly to heavy play-outs? In other words, can we expect to see a parallel line on the graph? http://cgos.boardspace.net/study/13/index.html Interesting. By now the corner of Mogo's curve around 4/1600 must be pretty well established. It looks like Leela has a slight corner around 6/1800. I still stand by my suspicion that this point happens near the playing strength of the raw playouts. So I predict that a Leela with very weak playouts will show a slight turn of the curve somewhat lower, possibly around 1200-1300 elo. Would be fun to know how well these programs do with just MC playouts, without any tree search. With some decent large number of playouts... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimal explore rates for plain UCT
On Thu, Mar 13, 2008 at 06:31:19PM +0100, Petr Baudis wrote: I got kind of lost in the thread and lost track about which bots should I actually compare myself to. ;-) So I have created this page: http://senseis.xmp.net/?CGOSBasicUCTBots Good idea! Would it make sense to have a similar page for pure MC programs (without uct), so that we beginning developers could check that portion of our code against known results? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Should 9x9 komi be 8.0 ?]
On Mon, Mar 03, 2008 at 12:15:36PM -0800, Christoph Birk wrote: On Mon, 3 Mar 2008, Don Dailey wrote: What you are trying to do is more in the category of opponent modeling.You want to optimize for the case that you might occasionally salvage a game against an opponent that is much weaker than you but is beating you anyway. No, absolutely not. The idea of following the 0.5 pt loss is always true, even if the opponent is of comparable strength. I agree with this, 100% strength level. If your program KNOWS it is losing by 0.5 points, then it's reasonable to expect that your opponent does too, especially given the fact that he just outplayed you. I think you are too much of chess player :-) The fact that he is 0.5 point in the lead does not imply he is (much) stronger. Any player, in particular a human player, is capable of the making a mistake. So it is important to stay on the 'small' losing line. That might a difference to chess, where there is no 'small' loss. Even the top professionals make the occasional small mistake in the end game. I expect our programs will be playing (much) lesser opponents for the foreseeable future, and thus have a good hope of seeing slightly suboptimal play in the end game. So at best you hope your opponent will make a stupid mistake in an obviously lost position for you. No, the opposite. Not a stupid mistake; I am hoping for the subtle mistake. But you throw that opportunity away If you play desparate moves just because you think you will lose the game by 0.5 points. Indeed! And there still is a (non-zero) risk that the program is estimating wrong, and actually has a small lead. Playing tight will preserve that, with a chance of improving it a bit, whereas playing desperate moves will throw it all away. Of course, if a program knows it is going to loose, it might as well resign. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] How to use CGOS ?
On Tue, Feb 26, 2008 at 07:51:40PM +1300, Stuart A. Yeates wrote: Adding authentication to GTP is a stunning bad idea. If we really need an authenticated GTP, wrap the GTP we have in an SSH connection. What a stunningly bad idea! So anyone running a server would either have to take the trouble to exchange keys and set things up manually for everyone who wants to play, or give strangers a login access. And every go program would have to add the ssh libraries and the trouble of establishing such connections. Some platforms may have easily usable libraries for that, but can you guarantee that all do? I have so little time for go programming that I would not like to waste my time on unnecessary 'security'! - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] How to use CGOS ?
On Tue, Feb 26, 2008 at 12:57:28PM -0500, Don Dailey wrote: What I got out of that was his main point that building authentication into GTP is a bad idea. Agreed! And slapping on a security library, be it SSH, SSL, GPG, or something else, without much though is only going to add hazzle and give no extra security for anyone. Sorry, I am in a bad mood today. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 13x13 study.
On Thu, Feb 21, 2008 at 04:08:56PM -0500, Don Dailey wrote: It's also interesting how the graph up to level 11 seems to form 2 very straight lines, almost as if they were connected at an angle. This must be a by-product of how we started the test. We played only the first 4 levels as we were testing the system and that is where the bend point is.Then I added levels gradually.I cannot figure out why this would cause such strange behavior. I noticed the same angle in the 9x9 study, more on Fatman, but also on Mogo. To me it still seems to be an interesting coincidence (if that what it is) that it happens about the level where a MC program (without a tree search) levels off. On 9x9, it was around 1400 elo for Fatman and 1600 for Mogo. The same seems to apply here. It would be interesting to see a similar study with pure MC programs (no tree search of any kind). And/or to get a few 'in-between' data points near the corner. Or to make the MC simulations weaker/stronger, and see how that affects the performance of the UCT programs... If I had all the machine power, and nothing better to do... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gpugo
On Wed, Feb 13, 2008 at 09:59:28PM +0100, Gunnar Farnebäck wrote: Second, as other people have pointed out, the strength of individual playouts does not have a strong connection with the strength of an UCT program. I would go as far as to conjecture that it's entirely irrelevant. (Patterns are indeed useful but for other reasons than playout strength.) Third, if you want to get any kind of speed from the GPU you must go massively parallel. Think in terms of a big texture filled by lots of go boards side by side and try to operate on all of them simultaneously in a reasonably uniform manner. Forget everything about group status and other complicated concepts. If you can just implement an UCT engine with uniformly random playouts on the GPU and get significantly better performance than on CPU it's a major achievement in my book. I admit I have no experience with GPU programming, so take all this with more than a grain of salt. Still, I would not even worry about patterns, UCT, or anything fancy, until I would have a fast and reliable MC-simulation code. And I would write the first (many?) versions on a normal PC, with all the good tools, just to understand the problem well. I would have them playing on cgos to see that they do all right. If I remember right, the ceiling is around 1500 ELO, which can be reached with something like 5000 simulations. The next step would be to rewrite everything for the GPU, sweet and simple. Then (and only then!) optimize a little bit (and only a little bit!). If you can not make that outperform LibEgo on a simple modern PC, there is not much point in trying to go further. It sounds like it would be a good idea to handle multiple MC simulations in parallel - if you have seriously vectorized bitmap operations, it might be quite effective. Once you have that, it should be (relatively!) trivial to make a UCT main program that pipes a number of positions into the GPU for MC simulations, and picks up the results. Once that plays well, it might make sense to consider moving some of that into the GPU, and/or improve the algorithms. But don't try to solve two problems at a time. If you want to play with the GPU, go for that with known algorithms. If you want to invent better ways to play go, don't waste your time programming fancy chips unless you know where you need the extra speed. Still, it sounds like quite a programming job! Wish I had the time and energy for that! - H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
On Wed, Jan 30, 2008 at 04:35:18PM -0500, Don Dailey wrote: Heikki Levanto wrote: On Wed, Jan 30, 2008 at 03:23:35PM -0500, Don Dailey wrote: Having said that, I am interested in this. Is there something that totally prevents the program from EVER seeing the best move? Someone, I think it was Gunnar, pointed out that something like this: 5 | # # # # # # 4 | + + + + + # 3 | O O O O + # 2 | # # + O + # 1 | # + # O + # - a b c d e f Here black (#) must play at b1 to kill white (O). If white gets to move first, he can live with c2, and later making two eyes by capturing at b1. You are totally incorrect about this. First of all, saying that no amount of UCT-tree bashing will discover this move invalidates all the research and subsequent proofs done by researchers. You may want publish your own findings on this and see how well it flies. You probably don't understand how UCT works. UCT balances exploration with exploitation. The UCT tree WILL explore B1, but will explore it with low frequency.That is unless the tree actually throws out 1 point eye moves (in which case it is not properly scalable and broken in some sense.) It was my understanding that most UCT programs would not consider b1, since they use the same move-generation for the MC playouts as for the UCT tree, and that forbids filling your own eyes. Broken in some sense, as you say, although probably playing a bit stronger for it. If the move is considered at all, I have no problems believing that UCT will eventually find it. That much I understand of UCT. Sorry if I confused practical implementations and the abstract. As to publishing my findings, I need to make some real ones first, and then be sure of them. I have some ideas I am pursuing, but things go slowly when I only have some of my spare time for this project. When I do, it may be on a web page, or maybe just on this list - I am not in the game to publish academic papers. More to learn things myself, and if possible to add my small contribution to a field I find interesting. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] More generic GTP
On Wed, Jan 30, 2008 at 01:15:39PM -0200, Mark Boon wrote: There's one bit that so far thwarts my effort to obtain maximum modularization. And that is I have a GoEngine interface that is kind of mirroring GTP, since GTP is the preferred communication method between Go-playing engines. My design could be a lot cleaner however if this could be a GameEngine. What stands in the way of this are the commands that are really Go specific like 'komi' and in a lesser way 'board_size' that are part of the 'required' section of GTP. Sorry, I don't see any big difference between having a mandated game-specific command, and having a general set-parameter command with a mandated game-specific parameter name. Sooner or later you need to get down from the fancy abstractions and actually declare that it is go you are playing! And with that comes a number of specific needs you have to support. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study
On Wed, Jan 30, 2008 at 03:23:35PM -0500, Don Dailey wrote: Having said that, I am interested in this. Is there something that totally prevents the program from EVER seeing the best move?I don't mean something that takes a long time, I mean something that has the theoretical property that it's impossible to every find the best move, even given eternity? Someone, I think it was Gunnar, pointed out that something like this: 5 | # # # # # # 4 | + + + + + # 3 | O O O O + # 2 | # # + O + # 1 | # + # O + # - a b c d e f Here black (#) must play at b1 to kill white (O). If white gets to move first, he can live with c2, and later making two eyes by capturing at b1. Depending on the definitions, b1 can be seen as an 'eyelike' point, and will not be considered in any playouts. No amount of UCT-tree bashing will make the program play it. In random playouts, it is 50-50 who first egts to c2. But it does not matter, as white lives in any case (at least as long as he has some outside liberties, I think). As I mentioned earlier, it is possible to get around that by allowing even eye-filling suicide moves in the UCT tree, even if not allowing them in the playouts. Even then, the UCT tree has to extend to the point where this kind of situation can occur, before the program can see it. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scalbility study: low end
On Thu, Jan 24, 2008 at 03:19:52PM +0100, Magnus Persson wrote: As a rule of thumb I want 300 games for each datapoint and at least 500 if I am going to make any conclusions. Ok, I think we start to have those 500 games. To my eyes, FatMan shows a clear turn in the curve at FatMan_03. Before that point the curveis practically a straight line, and after that it is pretty well linear too, but with a considerably lower scope. For MoGo, there may or may not be such transition around MoGo_04. I still find it an odd coincidence that these turns happen around 1400-1600 ELO, which is close to the limit of what a pure MC-program can reach. So, I have two questions for the list. 1) I am not much of a statistician, so I can still not judge how much I could trust this thing I see in the curves. 2) Assuming there is something in it, what can we conclude from it? That having a better evaluation function helps an UCT program, but more on lower levels of play, where its effects are greater. That there can be changes in the scalability of UCT programs. We (may) have identified one. Will there be another lurking somewhere? - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Scalbility study: low end
Everyone is looking at the top end of the scalability study http://cgos.boardspace.net/study/ But what happens in the low end? Both programs show linear progress to begin with, then a corner, and more (almost?) linear development. Fatman's curve has a clear break at 3 doublings, when it suddenly starts to improve much slower than before. This goes on until 12 doublings, after which we get the mysterious decline. Mogo's curve is pretty well linear to 4 doublings, after that there is more variation (I suppose random), but the overall scope is clearly not what it was below 4. It is possible that both programs have a subtle bug that starts to disturb results around this point, but I find it quite unlikely. The breaks happe at 1350 - 1550 ELO points. Isn't that about the level where plain MC stops improving with more playouts? Would be fun to see if we could isolate the playout parts of those programs, and let them play pure MC. My guess is that they would end up around this level. Could it be that there are other limiting factors higher up? Perhaps Fatman is hitting the next one around 12 doublings, and Mogo will follow at 14 or 15... We will see that in a few days, when the new Mogos join the study and start producing results. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scalbility study: low end
On Thu, Jan 24, 2008 at 10:34:42PM +0900, Hideki Kato wrote: The numbers of games are about 200 and their ratings' standard deviations (right of Elo) are 70 to 100, right now. To get 95% of reliability, you have to double them. Don't you think it's too early to conclude any? Well, I am just a programmer - statistics is not my strong point. But to me the curves definetly look like they are converging towards linear segments, with a definitive break. With Mogo I might perhaps accept it all as random variations, since the middle of the curve is still so uneven. But Fatman clearly shows two (almost) straight lines and a corner at _03. Of course we can wait until we get more data. I just wanted to share my observation that the curves seem to change around the level where MC playouts tend to flatten out, and hear if anyone would have some insightful comments to that. Even with the risk that more data may invalidate my observation... - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scalbility study: low end
On Thu, Jan 24, 2008 at 03:19:52PM +0100, Magnus Persson wrote: Nothing wrong with that, I do it myself all the time for my own tests. But I have tricked myself at lot of time plotting curves like this. Ok, when three people all tell me that I am jumping to conclusions, I am willing to believe that, and wait for more data. It is coming in at a good speed, even with the new strong (and slow) Mogos... But if my guess holds, I was the first to notice it (or at least to point it out on this list)! Interestingly the column of opponent rating indicate that many of the programs has played against harder or weaker opposition than expected, meaning that a lot of games played might have had a very predictable outcome. Thus the number of games played are probably to some extent misleading for how accurate the results are. Of course they have! The strongest program can only play weaker opponents, and weakest one can only play stronger ones. The programs near the top are still likely to meet weaker opponents (and vice versa). Still, that is one possible explanation for the change I see in the curves. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Scalbility study: low end
On Thu, Jan 24, 2008 at 06:07:30PM -0500, Don Dailey wrote: FatMan is a CPU hog, I think it would be good to get a lot of data first, and then perhaps see what happens with FatMan 14.I would not put 15 in unless 14 showed an improvement. Fair enough! Although it is too early to say yet (as I have recently learned), it looks a bit like Mogo could be suffering from a 'bad number' at _15. Might still be the effect of one or two unlucky losses... Having two programs in the study seems like a good idea, otherwise it would be just self-play, with the uncertainties that gives. I will do some statistics later on win/loss results for white and black at various ELO windows.It would interesting if we discovered that one color was winning a LOT of games - it would indicated that the play is getting really strong as David Fotland suggested. Good idea! - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study : show uncertainty ?
On Tue, Jan 22, 2008 at 09:51:11PM +0100, Alain Baeckeroot wrote: Le mardi 22 janvier 2008, Michael Williams a écrit : ... perhaps only uniformly random playouts will scale to perfection. The reason that MC/UCT scales to perfection is because of the UCT part, not the MC (playout) part. People seems to forget this a lot. I agree on this _only_ if the UCT check all possible moves. If not one can be limited by the quality of the playout. I think we may be confusing two different things here: a) Using all possible moves in the playouts to evaluate a leaf in the UCT tree b) Making the UCT search all possible moves in a position These two are related, and I suspect often people use the same code for listing the possible moves, so they tend to be the same in many programs. Theoretically speaking, errors and bias in those two may well result in different things. Most MC implementations (that I know of) avoid playing in one-point eyes. That is alrady a deviation from all legal moves, but one that makes perfectly good sense. Yet there is at least one exception, where playing into an one-point eye can create a nakade, and kill a surrounding group... The selection of possible moves for a node in the UCT tree can be somewhat slower, since it is not done nearly as often. Also, adding bad moves here costs less than in the MC playout, since the UCT algorithm can see that they will not lead anywhere, and not give them so much attention. I don't (yet?) have an UCT program, so I can not test this. Some day when I have one, I will try to see how much it will help or hurt to try all legal moves in the UCT portion... If someone else tries it before, let us all know! - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable ... is a troll
On Tue, Jan 22, 2008 at 05:17:48PM -0500, [EMAIL PROTECTED] wrote: Don't make too much of it. A 2-Dan program will play 2-Dan games, not just occasionally generate a 2-Dan move. :) True. Most weak beginners start the game with a move that is often seen in professional play. Usually 3-3, 3-4, or 4-4. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study : show uncertainty ?
On Wed, Jan 23, 2008 at 11:18:37AM +0100, Magnus Persson wrote: Indeed, Valkyria, uses the same code to prune move in both the playouts and in the UCT-tree. This pruning is supposed to be 100% safe and applies to really bad and ugly moves. But you still prune moves like filling a one-point eye. We know that there is a pthological case where that indeed is a correct move. So Valkyria will never converge to perfect play even with unlimited CPU power. But it is really hard to do this right and I still find a lot of bugs of this kind. There is an advantage of using the same code in the UCT-part because when I watch the program play I can see mistakes in pruning which otherwise only would be unseen in the playouts. That is a valid point. Not to the theoretical discussion, but in practical everyday life! -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] New scalability study : show uncertainty ?
On Tue, Jan 22, 2008 at 12:33:26PM -0500, Michael Williams wrote: The reason that MC/UCT scales to perfection is because of the UCT part, not the MC (playout) part. People seems to forget this a lot. For some level of perfection, of course. Although UCT is a new search algorithm, it just one example of best-first search. It is quite possible that some other form of search might perform equally good, or even better. -H (yes, I have some ideas. I will need to test them before I say much more here. Unfortunately I have a daytime job, and other hobbies getting in the way of go programming. Progress is slow, but it does happen!) -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
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 -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
On Wed, Jan 16, 2008 at 01:30:59PM +0100, Gian-Carlo Pascutto wrote: There are no advantages to allowing suicide, it is simply expensive for me in terms of speed to forbid it in playouts. If this is not the case for your board structure then you will probably want to forbid suicide. I do not see how that can be! You need to check if the move was a suicide, and if so, remove it from the board anyway. That must be the expensive part, calling the move illegal if that happens ought not to be very expensive. But then again, I do not know the internals of your program... Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Suicide question
On Wed, Jan 16, 2008 at 04:12:26PM -0500, Don Dailey wrote: There is no question that there are positions where suicide or eye filling are correct. I know suicide can be used as a ko-threat, but are there *any* other positions where it would be a correct move? If not, then it makes sense to forbid that in a random playout, since it is just a forcing move, and the (equally) random opponent is quite unlikely to answer the right way anyway. So the suicide move may look like a better move than it really is. I can not think of any situation where filling a one-point eye would be a correct move (provided that it is a real eye and not a false one). Can anyone come with concrete examples? - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How does MC do with ladders?
On Wed, Dec 19, 2007 at 12:21:18AM -0500, Chris Fant wrote: I just witnessed CrazyStone defend a fairly long ladder, resulting in a dead 17-stone block. Why not use a ladder reader at the root of the UCT tree to prevent provably bad ladder moves from being considered? I don't know for sure, but I suspect that even if it means that it would not play out a bad ladder, the UCT would still see it as a desirable thing, and direct the game towards one - and then not play it. Plus, it is not quite trivial to recognize a bad ladder - some times it pays off to extend a stone that is in atari, and then sacrifice two stones. Some nakade shapes also require sacrificing more than one stone... - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Lisp time
On Sat, Dec 15, 2007 at 03:00:02AM +1800, Nick Apperson wrote: In theory, and ONLY in theory, assembly is the fastest programming language. I do agree with most of what you said, but I have to squeeze in a comment that assembly is not necessarily the most optimized way to write code, when it really comes to it. If you *really* have to go for it, you need to be aware of the binary expression of every instruction... I have (once!) - many many years ago - optimized some assembly code where I reused the same bytes as instructions, jump offsets, and data, carefully placing the code on the right address so that this trick would work. This might have been possible with a good assembler, but at that time I did no have one for that CPU, so I was working directly in hexadecimal. With modern processors, assemblers, and compilers, things are different. And today, nobody will take the time to optimize on that level - which is good enough. But in theory... - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] winning a won game
On Thu, Dec 06, 2007 at 06:39:17PM -0500, Chris Fant wrote: I propose a far more powerful and correct set of rules: 1. Play the move that gives you the best chance of winning. That would be lovely - if we had a good way of estimating those chances. It is (should be) well known that MC playouts are not perfect. They seem to be good enough to use as an evaluation function in a tree search, but if you look at programs that uses only MC evaluation, you can see that they don't play very strong. There are some things MC just can not see. It only sees groups as unconditionally alive if they have two separate eyes, not if it has one large eye - no matter if that is clearly alive (say five points in a row). It sees a definite risk of getting cut through a bamboo joint. All this comes naturally from playing random moves, and not reacting to forcing moves that for us humans look all too obvious. Having said that, I am not trying to rake down MC techniques. In fact, I am writing my own MC-based program (although I am too short of time to see any real progress. Don't expect anything new on cgos the next few months!). I have some ideas I want to explore, maybe I am lucky and one of them turns out to be useful. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] speeding up testing of computer go programs
On Sun, Nov 25, 2007 at 11:52:14AM -0500, Don Dailey wrote: I know that most go programmers don't concern themselves with small improvements because of the sense that there is bigger fish to fry. But this is wrong thinking. If you can get 10 small improvements it can be equivalent to one very large improvement. This is frong thinking *for you*. Wasn't it yourself who said that people program go for various reasons, only one of them being making the strongest possible program. A person with a more theoretical approach might lament that all that speed optimizing indeed improved the play considerably, but has not produced any new insight or theory on how best to approach the problem. A mere amateur like me could complain about the time invested in those small improvements, that I did not gain any new knowlege for myself, it was just routine programming. I humbly suggest that none of us (including you :-) is guilty of wrong thinking. Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Drunken sailor on payday
On Wed, Nov 21, 2007 at 12:07:03PM -0500, Don Dailey wrote: My advice when this question comes up (which language for go programmer) is to first ask, what do you hope to achieve?If you want to build a high performance go program, anything other than C or assembler is like tying your hand behind your back. If you do this only as a hobby and have no aspirations (just for fun and pleasure) then by all means, you will be much happier in a high level language. Interesting approach. I like C myself, so even as an amateur just dabbling in the field, I have used it, and will do so again. But of course teh choice is never so black and white. If I had unlimited amount of time (or some student labour available ;-), I would make a good C library available from higher-level languages, so that the parts that matter could be fat and efficient C, and those that don't matter, or where lots of experimentation is useful, could be done in (say) python. There just isn't much point in optimizing much out of the 'list_commands' routine of the gtp interpreter, it is used at msot once per game, and communicating teh result over a network is going to be much slower than what ever is done to find the commands... - Heikki who does not plan to do much more in the language war... -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Tue, Nov 13, 2007 at 10:46:23AM -0500, Jason House wrote: I never went down the road of bitmap based go because I had not clever way to efficiently track captures. How did you get around this hurdle? When I was thinking of this - long time ago - I defined a 'shake' operation that expands a bitmap one bit in each direction rowX= ( rowX 1 ) or ( rowX 1) or (rowX-1) or (RowX+1) Now you can define stones_that_have_a_liberty as mystones and ( shake(empties) and not enemystones) Then you can do something like Remove my stones the enemy may have captured: deadstones = mystones liberties = emptypoints repeat liberties = liberties or ( shake(liberties) and not enemystones) deadstones = deadstones and not liberties until deadstones does not change. There are pathological cases where this has to loop many times, flood filling the one liberty to a long chain of stones, but those should be rare. In the end, if you have any bits set in deadstones, those are your captured stones. So you must emptypoint = emptypoints or deadstones mystones = mystones and not deadstones This checks that *all* stones have liberties, not just the neighbours of the last played stone. This sounds wasteful, but I am not sure if it would not be slower to isolate the neighbouring strings first, and then test only those. One more experiment where I didn't get very far... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Tue, Nov 13, 2007 at 11:35:43AM -0500, Jason House wrote: On Nov 13, 2007 11:23 AM, Heikki Levanto [EMAIL PROTECTED] wrote: There are pathological cases where this has to loop many times, flood filling the one liberty to a long chain of stones, but those should be rare. This was my big turn-off. I would expect the average case in mid-game to require several shakes (maybe 4?). Even with 64 bit numbers, 9x9 bit boards don't fit... requiring lots of operations per shake. With aspirations of 19x19, I figured the overhead would be too much. I never did any formal proof or disproof of that. Not me either. I gave up when I realized that at some point I would be needing each individual group anyway, and extracting them from the bitmaps started to get uninteresting. Now that I know of MC and related techniques, it might pay off anyway to see if a bitmap machine could play reasonably fast simulations. I can see two problems remaining: A quick test to sort out all eyelike points, to get a bitmap of moves to try. And a quick way to pick a legal move, when the set of legal moves are expressed as a bitmap. And the bitmap reprsentation itself. I did my experiments with an array of 32-bit words, one for each row. Left enough room to shift left and right, and not fall off the board. But I had to loop through every row. I would expect a tighly packed bitmap ought to be faster, but how do you handle overflows when shifting up/down? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Mon, Nov 12, 2007 at 05:31:11PM +0100, Petr Baudis wrote: I may be wrong, but I suspect most of bots specify the total number of simulations to play, not per move candidate. Thus, your '1000' should be compared against a '81000' in the beginning of the game. That sounds like an overly large number to me. Oh! I must have misunderstood the Monte Carlo algorithm description in that case. It could also be me who is wrong! I am just an amateur hanging at the fringe of the computer go world, programming small experiments with go when I am not too tired from my daily programming job... I intentially tried to come up with the simplest MonteCarlo-like algorithm possible - it is supposed to be an example engine, after all. Are there other possible algorithms for the MonteCarlo approach? (Apart of UCT; that's the next step.) There is the all moves as first (AMAF), that counts a win or loss not only to the move that started the random playout, but to every move that was played in that playout. Somewhat weaker, they say, but gets good results quicker (in a smaller number of simulations). I have had it play games on KGS over the day but I still don't have much idea about its strength. I would say maybe around 15k, but mostly too strong people play it and the weaker ones escape or undo (I have disallowed that now). Why don't you play it on cgos, that is where most go programs meet? http://cgos.boardspace.net/ It used to be nice code; as I desperately tried to optimize it, the code got somewhat uglier in some parts. (I got it from initial 650 games per second to 2500 gps, though!) You might not like the foreach macros. ;-) I have to live with such macros in the libego code as well. As long as I don't have to use them everywhere in my own code, I don't mind. And as long as there are decent interfaces to the functions, I don't really care how ugly the insides are coded. The framework and the example engines are MIT-licensed (almost public domain); I believe this is just something that noone should have to reimplement yet another time, no matter how evil they are. If I get some really well-performing engine built on top of it, I might license that one under GPL or keep the code for myself, depending how evil *I* will feel. GPL is fine with me. I only want to be able to make my experiments and show the world how I did it, in case I get some interesting results. Since I have a nice number of my university department machines available at night, I'm currently working on support for low-level parallelization over many hosts in the infrastructure. I wonder if I can dig out shells on at least 81 machines... ;-) Interesting. But since those are not going to be equally powerful, nor equally close to your master machine, I suspect there could be a more efficient way to distribute the job among them, than just giving one candidate move to each. Why not let each of them try all possible moves, and report their results back after a given time. Simply sum up the results, and choose the best. That way you can use as many or as few machines as you happen to have at hand, and the fast ones don't need to wait for the slower ones. But I think MC is so fast that this will not pay off. I seem to recall that the quality of play does not improve much over 5000 play-outs, anyway. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Speed of generating random playouts
On Mon, Nov 12, 2007 at 06:10:21PM +0100, Petr Baudis wrote: Sorry, it's http://repo.or.cz/w/zzgo.git I've had a quick look at it, and have already two comments: 1) You seem to use struct {x,y} for coordinates all the way. I think using a single int is usually faster. I was involved with GNU Go when we made that change, and it did make sense. Gives some speed, but costs a bit of work, and some readability. 2) It looks like your montecarlo algorithm tries to pick random points and discards those that are not empty or legal to play in. It ought to be faster to make a list of legal points in advance (or at least empty ones), and pick from that list. This list can be maintained incrementally during the MC simulation. Still, I like your style, and may yet decide to take advantage of your library instead of LibEGO at least in some of my experiments. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Language
On Mon, Nov 12, 2007 at 10:20:23PM -0500, Jason House wrote: My use of D has not all been positive. It's rarely the fault of the compiler itself, but stems from the immaturity of the libraries and supporting tools. I think that highlights an often-ignored problem in language discussions. There are only relatively small differences between most modern languages, btu their libraries tend be vary more. Also, learning the language basics should not take long for any experienced programmer, but to learn the proper way to use the libraries, that can take much longer. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Python bindings for libego?
On Tue, Nov 13, 2007 at 03:11:40PM +0900, Darren Cook wrote: On Oct 2nd 2007 Heikki wrote: I was thinking that it could be quicker to do prototyping in something like python, while having fast low-level functions in C. Since we already have Lukasz Lew's ego library, I wonder if anyone has written a wrapper around it to call it from python (or ruby, perl, or some other scripting language). And I wondered: I think if you used swig then we could use your work for any scripting language, not just python: http://www.swig.org/exec.html Rather than join in the current language war thread I thought I'd bump this one. Heikki I wondered if you looked into this any further? I gave it up pretty quickly. I came to the conclusion that I have so little time for mesing around, that the idea of learning a new language (say python), and how to build swig interfaces to it, and getting all that to work, it would probably take me so long that I wouldn't get around to doing any go experiments for a long time. I have a feeling that although swig is probably a good toolkit, most people avoid using it if they only need to interface to one or two languages. But no hard facts to prove this... P.S. I'm especially interested if you found some problems with swig - I'm reading up on making php extensions at the moment and wondering if swig is easier or harder than going the php-only route. I have seen some php extensions (our company makes one, but I am not directly involved). I seem to recall that making an extension to php was not all too hard. But as one who has to program some php for living, I wonder why would you like to use a language like that? I am *so* tired of the way it happily declares a new variable when you mistype one, or finds mistyped function names only at run time, if you happen to call that function... As a C-programmer, I want my compiler to catch silly mistakes for me, when ever possible. Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Locating day-old games on CGOS
On Fri, Nov 09, 2007 at 06:00:58PM -0500, Jason House wrote: Is there any way to look up fairly recent games on CGOS? All too frequently, I kick off a bot at night from one location and notice (in another location) the following afternoon that the bot crashed. I then try to look at the offending game and can't. Is there any relatively simple way to overcome this? I proposed (a long time ago) that the web page that shows the cross-reference table for a bot should also show the last many games that bot has played. May I hereby renew that suggestion? Of course I understand that it would take a bit of programming work to implement, so I am not making any demands... Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Small wish for Cgos (was: use for Monte Carlo on 19X19?)
On Wed, Nov 07, 2007 at 09:03:22AM -0500, Jason House wrote: I've been thinking about the same feature. I wasn't specifically thinking a hyperlink, but certainly a string with far more than 18 characters. Another candidate is to have commands that query the engine and display it as comments in the games Actually, gtp already has a command 'name' that returns the program name. It would be helpful if the cgos script would ask the programs name (if it supports it), and pass that to the server. The server could then display it on the cross-table page for that program. Or maybe we could simply define an extension to gtp - optional of course - for the same kind of purpose, because the 'name' command is already used by GUIs for a displayable name. 'program_comment' perhaps? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Small wish for Cgos (was: use for Monte Carlo on 19X19?)
On Wed, Nov 07, 2007 at 03:26:37PM -0800, Christoph Birk wrote: CGOS already uses the 'name' feature. You send it (along with a password) at login. No, I am talking of two different things. What I send at login is the name cgos uses for my program. This is what I put on the cgos command line. I don't want to change the way that one is used. But GTP also has a 'name' command. I was suggesting using that for passing extra information about the program, to be displayed about the program, perhaps a link to a page that describes the program. The reasoning for this is the repeated discussions here about what does program-X do, or what is the difference between programs X-1 and X-2. I guess many of us already have a page of our programs (I don't yet, but I am only beginning to play with the stuff). Many programs are open source, and could even include the whole source on that page, so that people can see it all... I still think using the gtp 'name' command for this is not optimal, as it is also used in GUIs to set the program name. Hope I clarified things more than I confused... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS on sourceforge
On Thu, Nov 01, 2007 at 08:57:38PM -0400, Joshua Shriver wrote: In that case I stand happily corrected. I once was going to release and one of the stipulations what that it had to be reassigned to the FSF. Couldn't remember if it was sourceforge, gnu, or what... GNU Go has this requirement. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
On Wed, Oct 31, 2007 at 01:00:07PM -0400, Don Dailey wrote: I think the right approach was mentioned just recently, add a very tiny incentive that cannot effect any bits of the main calculation as a kind of tie-breaker. I doubt this will buy much, but it might help just slightly and make it appear to play more natural by our standards. But I know trying to fix this any other way reduces the playing strength significantly. Yes, I did experiment that the last time I was playing with computer go. It does work. I did not see any decrease in strength, and I did see an improvement in the look of the game. But I did not run systematical tests to prove that there was no negative effects. The extra benefit has to be so small that it can not affect the result when there is a single game difference in the MC scores, of course. -H P.S. I am about to start playing with a go program again, I have some more ideas to improve simple MC things. UCT etc will have to wait until I can see what happens with those... -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
On Tue, Oct 30, 2007 at 12:43:35PM -0400, Joshua Shriver wrote: There has been a lot of talk about monte carlo and while I have the jist not sure exactly what it is? Would someone explain it? Here is my (amateurish) understanding: Evaluation of a go position is very difficult. Monte Carlo (MC) is one way to shortcircuit this. The idea is to play the game to the bitter end, very quickly, and badly, on the assumption that if the position favours white, then white is likely to win, even if both players play equally bad quality moves. Taken to the extreme, they play pure random games. This can be done very quickly, and doing it many times gives some sort of measure of how good the position is. Now all is left for a pure MC player is to try every legal move, evaluate them with enough MC playouts, and choose the one that is most likely to win. This works surprisingly well, although there are some drawbacks. Evaluating positions this way prefers safe, solid groups. And in the end game, when the result is decided, the programs play unnatural moves, since all moves lead to the same result - the resulting score is usually not considered, so to the program it is the same if it wins by 0.5 points or the whole board... On its own MC is not all too strong, but it solves the evaluation problem. This can be included in some tree-search based programs, most commonly UCT or similar. And the results are surprisingly good. Lukasz Lew has written a simple C library that makes it easy to experiment with the thing. Google on 'Lew libEGO' and you should find him. - Heikki P.S. If any of the above is not right, I am sure the better informed people will rush in to correct me. I welcome that! -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Definition for monte carlo
On Tue, Oct 30, 2007 at 01:33:07PM -0400, Jason House wrote: I don't think MC evaluation favors stable groups. I guess I didn't really say what I meant here. MC evaluation sees weaknesses in groups that can be killed by random play, even if they are safe enough in the eyes of human players. For example a group with one long eye, 4 points long, is considered unconditionally alive, but a MC evaluator sees some chance in killing it, because the defending side plays pure random, and is as likely to shorten it to 3-space eye as to split it in two independent eyes. In real games this may not make much of a difference, but it is possible to construct positions that get evaluated wrong by MC. Perhaps a clever program might even take advantage of such... It's really a function of the perceived chances of winning. When behind, it'll play bold moves since it's the only real way to win. An MC bot that is behind in endgame (even if by 1/2 point) plays so wildly, it frequently loses all of its stones! When an MC bot is ahead, it'll play safe moves that help guarantee a coast to victory (many times by 1/2 point). I think you are reading a bit too much intention into its play. When the game is already decided, it makes no difference where to play. So a pure MC program will end up playing totally random. If it is winning, it will happily let parts of a group die, as long as that does not change the result. If behind, it will not try to collect small points here and there, but just play where ever - often leading to death and destruction among its own groups. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] XML alternatives to SGF
On Mon, Oct 22, 2007 at 10:03:56PM -0700, Phil G wrote: To my surprise, GoGui can already read SGF with standard coordinates! :) I think you are muddying the waters by calling non-standard extensions 'standard' coordinates. I don't see any reason why [C4] should be harder to read than [cd]. Not for humans, and not for computers. I see many good reasons for sticking to *one* standard, and everyone using the same. At least for exchange of data - what you use internally in your programs is of course your own business. Even if a new proposed standard would have many benefits, obvious to everyone (which I have not yet seen), I would stuill urge people to consider those benefits carefully, and to weigh them against the problems that arise from having two incompatible standards. Just my personal opinion, of course. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] best approach forward
On Thu, Oct 11, 2007 at 01:32:44PM -0400, Don Dailey wrote: But what I had in mind in some kind of ratings agency where the conditions are controlled and everything is completely open. Here is what is required: 1. Someone with at least 2 equal DEDICATED computers plus a server. 2. Someone willing to do the work. 3. Software to manage the testing. [...] My point is that this probably won't happen in computer Go but it happened long ago in computer chess. So, how did it happen in computer chess? Who is willing to invest time hardware and time to run such an agency, and what do they get out of it? If it has happened once, it might happen again. What would help the idea along the way? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, Oct 02, 2007 at 12:27:28PM -0400, Don Dailey wrote: I don't believe null move pruning will be effective in Go. The basic principle of null move pruning has been described in a couple of ways: 1. threat analysis 2. bounds checking. In go terms, doesn't that translate to something like understanding sente? And to the problems of local sente vs. global sente? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, Oct 02, 2007 at 06:02:53PM +0200, Alain Baeckeroot wrote: Unless i missed something in this 4 pages article, there is nothing in it ! Just vague phrase, and assumption that brute force (ala deep blue) _may_ give a strong go machine. I think classical, MC and UCT programmers have contributed much more to computer go than this respectable researcher. I wouldn't put it as strongly, but I also noticed that MC and UCT and suclike techniques were not mentioned at all. I am not sure how that affects the predictions. On one hand, the article seems overly optimistic, but on the other hand, it does not consider the latest techniques that have shown some real promise, indicating that it may be underestimating the future programs... Maybe there are other inventions coming up in the near future that make the optimism more justified? -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] IEEE Spectrum article by Deep Blue creator
On Tue, Oct 02, 2007 at 10:33:09AM -0700, Phil G wrote: Also, is it just me that a good evaluation function early in the game is difficult to write? No, it is not you. The rest of people can be divided in two groups. Some believe such a function is easy to write. Let them come forth and show their results! The rest of us believe such a function is (almost?) impossible to write. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Python bindings for libego?
Hi, I was thinking that it could be quicker to do prototyping in something like python, while having fast low-level functions in C. Since we already have Lukasz Lew's ego library, I wonder if anyone has written a wrapper around it to call it from python (or ruby, perl, or some other scripting language). If not, I may consider doing something like that myself. No point in duplicating such work, if it is already done, and easily available, though. Regards Heikki P.S. Not trying to start any sort of language war here... -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Python bindings for libego?
On Mon, Oct 01, 2007 at 03:27:55PM -0400, Don Dailey wrote: P.S. Not trying to start any sort of language war here... Why use any of those highly inferior languages you mentioned when you could do it Lua, the best language ever invented and highly superior (in every possible way) to all else? Well, I considered writing it in ETA [1], but my work situation is such that soon I am expected to know python, so I might as well use computer go as an excuse to learn it. - Heikki [1] http://www.miketaylor.org.uk/tech/eta/doc/index.html -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] repeat postings
On Mon, Aug 27, 2007 at 04:22:08PM -0400, Don Dailey wrote: On Mon, 2007-08-27 at 21:35 +0200, Heikki Levanto wrote: Some mail servers are starting to use greylisting, which intentionally delays mails that have sender-recipient pairs they have not seen before - this fouls a lot of spamming programs (I do that at my place of work). How does this foul spamming programs? Does it prevent a spammer from sending out a lot of email or just delay the receiving of it? Many spam programs are not fully capable mail programs, and have not implemented any sort of retry mechanism. I was sceptical about it too, until I installed it. Perhaps the spammers are catching up now, but a year ago, it dropped more than 75% of incoming spam - enough that our mail server could afford to do proper filtering on the rest. And it is not like all mail gets delayed, the filter keeps a hash of sender-address, receiver-address, and connecting IP-address. If it has accepted one mail with a matching hash in the past 45 days, no delays are imposed. But this is getting off topic. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] CGOS down?
On Tue, Aug 21, 2007 at 01:20:49PM -0400, Jason House wrote: Also, what is the best way to capture the output to stderr from the engine while running on CGOS? My script does the simple thing: ./cgos3.tcl $NAME $PASS $PGM 2/dev/stderr $STOP This works on Linux, and puts stderr back to /dev/stderr, no matter how much cgos3.tcl tries to redirect it. Of course you can also capture it in a file, and perhaps run a tail -f on it... -Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] scalability study - final results
On Wed, Jun 27, 2007 at 04:03:09PM -0400, Don Dailey wrote: My program wouldn't do well as it would not understand dame and other Japanese complexities. It should not do too badly - if you play by the chinese rules, you will do quite well by the japanese as well. Perhaps some of the opponents will find you silly not passing earlier, but so be it. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] evalgo autotesting system
On Mon, Jun 25, 2007 at 03:17:06PM -0400, Don Dailey wrote: However I'm releasing my testing system to the public if anyone is interested. It may have some features in it that you will be interested in. Thanks. Looks promising. It DOES require having sqlite3 and a little bit (but not much) sql knowledge. You DO have to manually insert registry records into the database to specify who the players are and how they should be invoked, but no other sql knoweldge is required beyond this - a report is furnished by the program or if you want you can manually query the database to find out anything you want about the games. I have it running, but at the moment I have no idea how to specify my program for it. sqlite3 seems not to understand the describe command that I normally use to sort out the table layouts before inserting anything. Maybe you could add a one-line example to the README, on how to add a program (say GNU Go) as a player. Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] evalgo autotesting system
On Mon, Jun 25, 2007 at 04:33:47PM -0400, Don Dailey wrote: Here is how you might set up gnugo: Thanks! that certainly looks enough to get me going. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to GNU and to MoGoBot19!
On Tue, Jun 19, 2007 at 04:18:20PM -0700, steve uurtamo wrote: true, and a good point. time management other than attempting to equally divide remaining time among the expected number of remaining moves (which itself isn't so easy to estimate) is complicated. Even that has the complication of estimating the expected length of the game. Much easier to use something like 2% of the remaining time on each move. -Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to GNU and to MoGoBot19!
On Wed, Jun 20, 2007 at 11:55:47AM +0100, Jacques Basaldúa wrote: Computers feel comfortable with any time settings, and no matter how naif the scheduling algorithm is, it will always be far better than human scheduling. Computers can safely approach using 99.999% of their time (asymptotically) and there is no other reason why a computer should lose on time than net lag. Depends on the program. Programs based on MC, UCT, or other such things can use as much or little time as they please. Programs like Gnu Go can only adjust some overall parameters, and then it does its thinking. The best it can do, is to adjust those again for the next move, if this one turned out to take more or less time. -Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Opening
On Mon, Jun 18, 2007 at 10:09:31AM -0700, terry mcintyre wrote: Is it possible to recognize and exploit symmetry to improve the quality of the move estimation process with minimal expenditure of effort? For the first few moves perhaps, but after that, symmetric positions must be awfully rare, and worrying about them probably costs more than it can ever give. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Opening
It seems generally accepted that MC or UCT programs are weakest in the opening. My own experience matches this too. Some times I get the idea that my program doesn't know at all what it is doing the first few moves. I propose a simple test to see if that is the case. Before doing it, I'd like to hear if other programmers are willing to make a similar test, and agree on the particulars. The idea is simple: We know that the empty board is symmetrical. How many iterations does it take before the program gets values for the first move that are symmetrical too. For example, if the program prefers the 3-3 point in one corner, but 4-4 in the other corner, then I would say that it doesn't know much about the situation. I am sure there is a mathematically sound way to measure how symmetric the evaluation is, but my math is a bit rusty, so I am asking if someone can come up with a good way. After that, I'm asking if various programmers would be willing to run this test, and publish the results? - Heikki (who has no time to debug his own program...) -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19 CGOS
On Thu, Jun 07, 2007 at 09:20:35AM -0400, Don Dailey wrote: Someone could also run a weak Gnugo - perhaps with level set from 1-3 or something. I have put up GnuGo on level 2 as GnuGo-3.7.10-H2. It looks like it is not eating much of my cpu power, so my home server seems to be able to handle both it and the anchor GnuGo. For some reason it starts at a rating of 1800, which may be a bit too much for it. Some day (soon?) when I get my Halgo debugged, I may put it up on 19x19 as well, just to see how badly it does there. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] KO in Hashtable-UCT?
On Wed, May 23, 2007 at 06:47:58AM -0300, Eduardo Sabbatella wrote: In my experience adding a captured stoned limit per game biases the results. strongly. In which direction? The limit was a constant number. Perhaps it could be good to define it as a function of current move number. I don't make any tests for the first 20 moves. Thereafter, I resign if - I have no stones left on board - I have less than half the number of stones my opponent has I also pass if my opponent has no stones left on board. I should do these in the MC simulations too, but so far I have been using Lew's libego unmodified. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] cgos3: Small fix
I noticed that the simple tcl client outputs many lines like this: 09:21:30S-C info Estimated time until next round: 06:53 09:21:30Estimated time until next round: 06:53 As those scroll interesting info out of my screen, I disabled the line that outputs the second line. All the info is already in the first one. Maybe the server could send those messages a bit less often too? Thanks again for cgos, it has turned out to be a fun thing. I am again playing with my 'halgo' series, going for some sort of search next... Regards Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 9x9 vs 19x19 (was: computer-go Digest)
On Mon, May 21, 2007 at 10:46:24AM -0600, David Silver wrote: But... in practice, I haven't got good results on larger boards. But to be honest, I've focused much more on 9x9, so perhaps I've missed some simple tricks. I think there has been a marked change of interest since the introduction of UCT, and - around the same time - the cgos 9x9 tournament page. I understand that most people do their experiments on 9x9, the results are available so much faster. Still, I think it might be time to loosen the focus on 9x9, and have some more things happening on other sizes. Would there be interest in a tournament system for 19x19 programs? Something like 30 mins / player sounds like a reasonable extrapolation. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 vs 19x19 (was: computer-go Digest)
On Mon, May 21, 2007 at 03:13:09PM -0400, Chris Fant wrote: Why not 13x13 before 19x19? Because the next step would be 15x15, and then 17x17, and when (if) we get to 19x19, there are so few competitors around that the whole tournament won't make any sense. I think it is better to stick to 9x9 as the beginners tournament, where it is easy to test new ideas in quick games, and 19x19 as the serious tournament where we can see how good computers are at playing the game like we humans do. Just my humble opinion, of course. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] On expanding the UCT tree
On Tue, May 01, 2007 at 11:42:46PM -0400, Chris Fant wrote: [...] memory-saving technique of not expanding a leaf until you have been through it many times (100, for example). I have been wondering about this: If it pays off not to expand a node until it has been visited 100 times, why not bite the bullet and make those 100 simulations in one go? That should save a bit of time traversing the tree up and down. Of course, it means that they all do get a full 100 simulations, even if the first 90 show a bad result. But it would make it easier to distribute the job to another thread, processor, or even another computer. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] The physics of Go playing strength.
On Mon, Apr 16, 2007 at 09:40:46AM +0900, Darren Cook wrote: I have one interesting test that I do, which I take with a grain of salt, but I use as a first guess estimate. I search from the opening position a few hundred times and average the time required to find the move e5. ... Yes, I noticed libego usually switches to e5 at some point between 100K and 200K playouts. Like Don, though, I'd take that with a grain of salt; it is quite possible that there is no single best first move (e.g. 5-5, 4-4 and 3-4 might all be joint best). That's true - but all the 3-4 points should get about equal scores on an empty board, as should all 4-4 points, etc. Would that not be a good indication that the program 'understands' the situation, instead of just randomly hitting on a good move? - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo
On Sun, Apr 08, 2007 at 08:48:03AM -0400, Don Dailey wrote: On Sun, 2007-04-08 at 11:24 +0200, Heikki Levanto wrote: Weaker players can not estimate the score until very late in the game. Not with enough precision, anyway. Thus, most of the time they have no idea if they are winning or loosing by 0.5 points. But the whole idea is to take you PAST this level of understanding. I bet most of the go-playing population (humans and computer programs alike) are quite incapable of estimating the final score on a 19x19 board except in the yose. Perhaps dan-level amateurs can do it in the late middle game. But show me the player who can say at move 30 that playing here will lead to 0.5 point victory, and playing there will loose the game by a point and a half! Or show me any professional who claims to know the final score before the tenth move! Such people don't need to play go, they have already solved the game! - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo
On Thu, Apr 05, 2007 at 10:49:05AM +0100, Jacques Basaldúa wrote: Many users feel stolen by UCT programs. I have read that in the KGS chatrooms. Normal users do not count with +/- 0.5 point precision. They have the impression the program blundered and they caught up. But when the program counts, surprise!, it wins by 0.5 points Chinese. The users were thinking Japanese even if they accepted Chinese rules. In fact, they did not have the choice. They get the impression the game was stolen by technicalities after they saw the engine blunder many times. As I have posted here before, this is easy to avoid, by counting the result of teh game not as +/- 1, but as +/- (1+epsilon), where epsilon is so small that it can not change the order of the averaged-out results. If you first normalize the matrgin of victory to 0..1 by dividing by boardsize, and then divide by by the number of playouts you do, you get a suitably small epsilon, that only affects the sorting of games that get as many wins. Of those the program will prefer the moves that win by a larger margin. This should not have any effect on the strength, because even one playout difference is greater than all teh epsilons summed up, but in the endgame, when all moves lead to a certain victory, the program prefers a win by a larger margin. My Halgo does that (in a otherwise regular MC), and the feel of the endgame is clearly more reasonable than without. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] cgosview viewing client.
On Mon, Apr 02, 2007 at 02:34:47PM -0400, Don Dailey wrote: On Mon, 2007-04-02 at 14:26 -0400, Chris Fant wrote: Does the new cgos have a standby player that fills in when an odd number of engines are logged-in? I want it to have that, but it doesn't yet. But it will. I was thinking of building a simple player right into the server that would fulfill this function. If there were an odd number of players he would come alive to fill out the pairings. Wouldn't that be a good job for a clone of the anchor bot, like you used to have (was it called ControlBoy?). Same strength as the anchor, but floating freely. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re:[computer-go] Time Control for the new CGOS
On Tue, Mar 27, 2007 at 08:43:23PM -0400, Don Dailey wrote: On Tue, 2007-03-27 at 16:02 -0700, Christoph Birk wrote: On Wed, 28 Mar 2007, Heikki Levanto wrote: P.S. How about starting a new round when (say) 75% of the players are free? That introduces a bias towards pairing faster programs against each other. I've really struggled with this one. In the end, scheduling is far easier and has far less side effects if I make them discreet. [...] A little analysis shows that this does not decrease the playing rate much at all for programs that use most of their time. For the really fast programs, you will clearly get scheduled less often. I usually make decisions, where there is an issue, in favor of the stronger programs as long as it doesn't introduce gross unfairness to the weaker programs.In this case I don't want to introduce a scheduling algorithm that encourages random players to play zillions of games. Fair enough, it was just a lose thought - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Help me test CGOS
On Mon, Mar 26, 2007 at 10:06:47PM -0400, Jason House wrote: I don't see any games that have an outcome other than winning by points or resignation. Any forfeits or games that are on hold? I see a few games with B+Illegal, or suchlike. But I remember when I was fooling with my stderr problem, I started a few games that were rejected because illegal moves. yet the listing shows no Illegal games for Halgo. Something wrong there? -Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Help me test CGOS
On Tue, Mar 27, 2007 at 12:14:37PM -0400, Don Dailey wrote: On Tue, 2007-03-27 at 15:31 +0200, Heikki Levanto wrote: I see a few games with B+Illegal, or suchlike. But I remember when I was fooling with my stderr problem, I started a few games that were rejected because illegal moves. yet the listing shows no Illegal games for Halgo. Something wrong there? sqlite select gid, w, b, res from games where w like %Halgo% and res like B+Illegal ; gid w bres -- - --- -- 333 halgo-1.7-10k gnugo_3.7.9 B+Illegal 336 halgo-1.7-10k gnugo_3.7.9 B+Illegal Ok! Those games must have scrolled off the list of games when I came to think of them today. Those 2min games happen fast... Seems like your system works as expected. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Time Control for the new CGOS
On Tue, Mar 27, 2007 at 12:33:36PM -0400, Don Dailey wrote: I am considering to change the time control when I change over officially to 5 minutes instead of 10. 5 minutes seems more than adequate for the Monte Carlo programs which play quite strongly even at 2 minutes per game. What does everything think about that? Fine by me. The server adds 1 second gift to each move silently, in order to allow for server overheads and network lags and glitches. This is pretty generous and actually adds a minute or more the the length of the games. I think this should probably be cut to 1/2 second instead of a full second and I will make that change. Quite fine by me. My quick program halgo-1.7-10k always seemed to have 120 seconds left, no matter what happened. Maybe even 0.1 seconds would be sufficient. In fact I don't quite see the point in adding the extra time. Both players get as much, and both are supposed to have the same amount of time available, so it should not make much of a difference. I can se an argument for it, in the case the opponent plays silly moves just to kill time, and hope to win on time. But we already play the games to the bitter end, so that should not matter so much. Maybe the time should only be added after a player has passed once? I am still not sure about all the consequences of this, but I don't see it as a major problem, one way or the other. - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/