Re: [computer-go] Re: Dynamic Komi at 9x9 ?
On Thu, Feb 18, 2010 at 7:28 AM, Ingo Althöfer 3-hirn-ver...@gmx.dewrote: Hello Don, several very good points by you! Does anyone have data based on several thousands games that attempts to measure the effect of dynamic komi? I would like to see results that are statistically meaningful. I had eight handplayed (4 + 4) games on 19x19 with very high handicap, where the version with dynamic komi (rule 42) gained a 3-1 score and the version with static komi performed 0-4 versus the same opponent. This is evidence in the 95% region that the version with dynamic komi is not weaker than the static version. Were these games against humans or other computer players?If the games were against a human player, were they blind? Did the player know he was participating in an experiment?Did he know what results you hoped to see?And were the games alternated so that the result was not skewed too much by his experience with the program? Don We need to see a few thousand games played A few hundreds or even a few dozens may be sufficient when the outcome is very clear. against a fixed opponent WITH dynamic komi, and then the same program without dyanmic komi playing against the same opponent with the same number of games. The number of games must be decided before the test is run, or the error margin calculation is meaningless. I am willing to provide the statistical part, when programmers run the experiments. As far as I can tell, nobody has yet to produce anything more than anecdotal evidence that this works. I have. See the 4 + 4 games mentioned above, played with my rule 42. Having a person manually adjusting this after every game is completely non-sceientific, unless they are doing it in a fixed way with no decision making on their part Right. and they are playing thousands of games (or at least enough to get statistically significant results.) Right, especially also the bracket part of your sentence. I'm not trying to rain on anyone's parade, but I cannot understand why no one has produced a statistically meaningful result on this subject - I would have. Unfortunately I am not a programmer, and am also not fit in modifying a program code to include dynamic komi. But, to repeat it, I am willing to do statistical home work. I am genuinely interested in this since I never was able to make it work when I spent about one intense week on it. (I did not do this with handicap games, but with normal games.) Your sentence in brackets is crucial. I only proposed to use dynamic komi in games with high handicap. Especially I had in mind the situation where the stronger side (giving high handicap) is MC-based. Perhaps, 9x9 instead of 19x19 makes it easier for some programmer to start test series with dynamic komi. Ingo. -- Sicherer, schneller und einfacher. Die aktuellen Internet-Browser - jetzt kostenlos herunterladen! http://portal.gmx.net/de/go/atbrowser ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic Komi at 9x9 ?
I'm not being critical of anything that has already been presented, I just have not seen it myself and I've been pretty busy working on chess so my focus is not currently on this. But I look forward to reading the paper if it's public. (I'm not going to buy the paper.) Don 2010/2/18 Petr Baudis pa...@ucw.cz On Wed, Feb 17, 2010 at 05:29:36PM -0500, Don Dailey wrote: Does anyone have data based on several thousands games that attempts to measure the effect of dynamic komi?I would like to see results that are statistically meaningful. We need to see a few thousand games played against a fixed opponent WITH dynamic komi, and then the same program without dyanmic komi playing against the same opponent with the same number of games.The number of games must be decided before the test is run, or As far as I can tell, nobody has yet to produce anything more than anecdotal evidence that this works. In pretty much all of my original dynamic komi mails, I have pointed at the presentation I've sent here earlier - if you have reservations against that, I'll be happy to hear about them; the paper I'm preparing should be ready in couple of weeks. For extra convenience, here is the graph from the presentation, including 95% error bars; I'm sorry, I don't have data about exact numbers of games anymore. The y-axis is winrate against GNUGo Level10. -- Petr Pasky Baudis A great many people think they are thinking when they are merely rearranging their prejudices. -- William James ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic Komi at 9x9 ?
2010/2/18 dhillism...@netscape.net Ingo, I'm not a proper statistician, but I believe there's a crucial second step that's missing in your analysis of significance. Even if this were the only computer-go test that you personally had ever conducted, we would nevertheless need to take into account all of the other tests being conducted within the community. On any given day, some high number of similar tests are carried out by members of this list. They are testing different hypotheses to be sure, but that doesn't get us off the hook at all. What it boils down to is this: how frequently does *somebody* get a 95% confidence result about *something* that isn't going to hold up under further testing? This issue comes up all the time in epidemiology (e.g. cancer clusters near power lines), medical studies, bioinformatics, etc.. When such results are reported, it is usually because the experimenter felt that he had a good result. When the same experimenter has a bad result and he is motivated to believe that what is trying will work, he will probably conclude that the bad result is a result of his running the experiment incorrectly and try something else. So what you are going to get is a random sampling of (mostly) good results. You can never be sure that the experimenter did not subconsciously accumulate good results either, tweaking the experiment as he goes (and throwing out the bad tweaks.) I'm not suggesting that bad results should be reported and factored in, but what should happen is that if someone believes they have found a good algorithm and have results to report, the experiment should be repeatable and needs to be verified by the entire community. This does not suggest any dishonesty, it just needs to be done that way.I have conducted experiments myself that returned results well ahead of statistical significance, only to discover that my setup was flawed. For instance I remember one case where the improved version accidentally corrected a bug which was not supposed to be part of the experiment. I'm not trying to refute any of what has been reported, but I don't see any science here yet.I would like to see a serious study based on a specific proposal or algorithm and I have yet to see that. Don't forget that when you report results with error bars, the test length has to determined in advance. You cannot just stop the test when you feel the confidence interval satisfies you, you have to have determined in advance that you are going to run N games and then interpret what you see based on exactly N games. Don - Dave Hillis -Original Message- From: Ingo Althöfer 3-hirn-ver...@gmx.de To: computer-go@computer-go.org Sent: Thu, Feb 18, 2010 7:28 am Subject: [computer-go] Re: Dynamic Komi at 9x9 ? Hello Don, several very good points by you! Does anyone have data based on several thousands games that attempts to measure the effect of dynamic komi? I would like to see results that are statistically meaningful. I had eight handplayed (4 + 4) games on 19x19 with very high handicap, where the version with dynamic komi (rule 42) gained a 3-1 score and the version with static komi performed 0-4 versus the same opponent. This is evidence in the 95% region that the version with dynamic komi is not weaker than the static version. We need to see a few thousand games played A few hundreds or even a few dozens may be sufficient when the outcome is very clear. against a fixed opponent WITH dynamic komi, and then the same program without dyanmic komi playing against the same opponent with the same number of games. The number of games must be decided before the test is run, or the error margin calculation is meaningless. I am willing to provide the statistical part, when programmers run the experiments. As far as I can tell, nobody has yet to produce anything more than anecdotal evidence that this works. I have. See the 4 + 4 games mentioned above, played with my rule 42. Having a person manually adjusting this after every game is completely non-sceientific, unless they are doing it in a fixed way with no decision making on their part Right. and they are playing thousands of games (or at least enough to get statistically significant results.) Right, especially also the bracket part of your sentence. I'm not trying to rain on anyone's parade, but I cannot understand why no one has produced a statistically meaningful result on this subject - I would have. Unfortunately I am not a programmer, and am also not fit in modifying a program code to include dynamic komi. But, to repeat it, I am willing to do statistical home work. I am genuinely interested in this since I never was able to make it work when I spent about one intense week on it. (I did not do this with handicap games, but with normal games.) Your sentence in brackets is crucial. I only proposed to
Re: [computer-go] Dynamic Komi at 9x9 ?
Does anyone have data based on several thousands games that attempts to measure the effect of dynamic komi?I would like to see results that are statistically meaningful. We need to see a few thousand games played against a fixed opponent WITH dynamic komi, and then the same program without dyanmic komi playing against the same opponent with the same number of games.The number of games must be decided before the test is run, or the error margin calculation is meaningless. As far as I can tell, nobody has yet to produce anything more than anecdotal evidence that this works. Having a person manually adjusting this after every game is completely non-sceientific, unless they are doing it in a fixed way with no decision making on their part and they are playing thousands of games (or at least enough to get statistically significant results.) I'm not trying to rain on anyone's parade, but I cannot understand why no one has produced a statistically meaningful result on this subject - or if I'm wrong please point me to the paper or data and games that were played. I am genuinely interested in this since I never was able to make it work when I spent about one intense week on it.(I did not do this with handicap games, but with normal games.) Don On Wed, Feb 17, 2010 at 4:57 PM, Isaac Deutsch i...@gmx.ch wrote: Fuego_9x9_1h (or a variation of this name) played on OGS a couple of handicap 9x9 games. It used dynamic komi. I think it was manually adjusted after every move, and worked well. -ibd Am 17.02.2010 um 22:51 schrieb Ingo Althöfer: Hello, I informed the German go scene that there is (some) progress at KGS bots with dynamic komi. Based on this, a friend told me that they would have an open afternoon for go beginners in the middle of March - and they expect many newbies with strengths between 17k and 30k. His question is if a bot with dynamic komi might be a suitable opponent for such beginners on 9x9 (with high handicap). Does someone here have already experience with non-static komi for handicap games on 9x9? Or would someone be willing to test something with his bot? Ingo. -- NEU: Mit GMX DSL über 1000,- ¿ sparen! http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gongo: Go in Go
That's pretty impressive for the go language if this is an apples to apples comparison. Is it pretty much? On Wed, Dec 16, 2009 at 9:50 PM, Brian Slesinsky br...@slesinsky.orgwrote: Oops, you're right. Here it is with -server: Plug-and-Go refbot:17857 CRef bot (-O3) 12500 Gongo 1 Java bot: 1 CRef bot (no optimization) 5882 On Tue, Dec 15, 2009 at 1:40 PM, Mark Boon tesujisoftw...@gmail.com wrote: The relative values look about right. But I remember getting much higher numbers. Did you run the Java versions with or without the -server parameter? Mark On Mon, Dec 14, 2009 at 11:00 PM, Brian Slesinsky br...@slesinsky.org wrote: Okay, I added a few more timings (playouts / second, very rough): Plug-and-Go refbot:14700 CRef bot (-O3) 12500 Gongo 1 Java bot: 6500 CRef bot (no optimization) 5882 Note that Gongo and Plug-and-Go are using different board data structures than the others. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Reference Montecarlo TreeDecision Bot.
That same statement baffles me. AMAF gives a huge boost with light playouts for me. As the number of playouts increase, AMAF gives less and less. After a few thousand playouts it's almost nothing but if it's worse than not doing AMAF it is difficult to measure. Of course MCTS never does thousands of playouts from a single node. What is the definition of light playouts? I am referning only to purely random playouts and perhaps that is where the discrepency is. Don 2009/12/14 Olivier Teytaud teyt...@lri.fr I've found that AMAF gives very little boost with light playouts, Thanks for this interesting comment. I would (erroneously) have believed that AMAF gives better results with non-optimized implementation (e.g. in Havannah with no expertise Amaf provides huge improvements). In particular, I believed it was moderately efficient in 19x19 due to the patterns which already provide relevant informations - but I could never test it (testing properly this assumption requires the tuning of the version without Rave, which would be time consuming and boring :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gongo: Go in Go
That's awesome! Do you have performance numbers on the same hardware for the C refbot? - Don On Sat, Dec 12, 2009 at 7:39 PM, Brian Slesinsky br...@slesinsky.orgwrote: Thought I'd announce that I've ported the Java refbot to the Go language (with some modifications). I'm getting about 10,000 random playouts/second on 9x9 using a single thread on a 32-bit iMac, using the gc compiler, which doesn't do any optimization. I suspect that a board structure that tracked pseudo-liberties could do better. I probably won't have a chance to work on this for a while, but I think the next step might be some kind of tree search. I'd be interested in a particularly simple, standard, and easy-to-port implementation to use as reference. Source code: http://github.com/skybrian/Gongo Previous discussion on the Go language list: http://groups.google.com/group/golang-nuts/browse_thread/thread/99ab46f5b7219a5b/22e58d9223db10ef - Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kinds of Zobrist hashes
The empty value is not needed. In some games it's easier to have it because it can be a simplification - everything handled uniformly for instance and it can avoid a conditional branch but I don't think that is an issue with Go. - Don On Tue, Dec 8, 2009 at 5:49 PM, Petr Baudis pa...@ucw.cz wrote: Hi! In most papers I've read, three-valued Zobrist hashes are used - per intersection, values for empty, black and white coloring [1]. I'm not clear on why is the empty value needed, however, shouldn't only black, white values work just fine? Is the hash behaving better with extra values for empty intersections? Has anyone measured it? [1] In pattern-matching, it is desirable to also use edge coloring. Thanks, Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
A few months ago there was a post in the computer chess forums about optimizing combinations of features. It was called orthogonal multi-testing. Did I mention that on this forum already? If not, here is a brief on how it works: Suppose you have 1 feature you want to test - you might normally play 2 versions of the program a 1,000 game match for instance, one version with the feature on and one with the feature off. However, if you have 6 features, there are 64 combinations.What you can do is play every combination of feature in a round robin tournament. For every feature, half the games played have that feature on, and the other half have this feature off. So you can get a separate score for each feature by considering only the games played between opponents with this feature ON and OFF. This idea of course assumes that each feature is independent (there is no interaction between features.) This is probably not true but it's amazing how often it works despite this and we find that methods such as naive bayes classifiers work surprisingly well even when the attributes of the thing being classified is not independent. It reminds me a lot of all-moves-as-first, which assumes the order of the moves is not relevant but is a wonderful cheat because you multiply your sample size by an order of magnitude.So you can play a few thousand games with a huge number of features and get a huge amount of data by reusing the same samples for different things. 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.) Even if the lack of independence bothers you, one might use this as an approximation or a way to get a little closer to the appropriate feature set, in the same way all-moves-as-first nicely approximates the value of much larger samples. On Tue, Nov 24, 2009 at 11:35 PM, Brian Sheppard sheppar...@aol.com wrote: What do you do when you add a new parameter? Do you retain your existing 'history', considering each game to have been played with the value of the new parameter set to zero? Yes, exactly. If you have 50 parameters already, doesn't adding a new parameter create a rather large number of new parameter sets, most of which there will never be time to investigate? Yes. So the new parameter will drift to its optimal value against the existing parameter values. But here's the thing: declining epsilon greedy policies are zero regret starting from any initial state. So if the setting of the new parameter affects old parameter settings, then the established parameters will start to move as well. If the objective function is a convex function of the parameters (which is generally the case, based on the curves that I have seen) then the whole system will drift to a global optimum. I have been using UCB and UCT to tune engine settings, but I don't think these methods work well to tune more than a handful of parameters at the same time. Such systems have trouble because their exploration is a *deterministic* function of the sequence of wins. That is, all parameters will lock into the same set of feedback. If you use UCT, then you have to optimize *combinations* of parameters, which is unwieldy. Declining epsilon greedy is a randomized exploration strategy, but still zero-regret. Now the same sequence of wins/losses can be used to tune all parameters concurrently. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
I know there are heuristics for trying to understand the interactions and without looking too hard I assume this package is just a more comprehensive version of this. On Wed, Nov 25, 2009 at 9:11 AM, steve uurtamo uurt...@gmail.com wrote: the way to do all of this exactly is with experimental design. to design experiments correctly that handle inter-term interactions of moderate degree, this tool is quite useful: http://www2.research.att.com/~njas/gosset/index.htmlhttp://www2.research.att.com/%7Enjas/gosset/index.html s. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
On Wed, Nov 25, 2009 at 10:44 AM, Heikki Levanto hei...@lsd.dk wrote: 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... That would not be effective at all. With 256 features you are (for all practical purposes) never going to see that exact combination of features again. In very general terms, you are probably going to be more interested in how a few terms interact than how many interact. Of course this method only tries to understand each feature independently, but I think this has some validity. I don't claim it will cover all the bases however but it might be a good place to start. Of course there is nothing that prevents you from observing from the data the interaction of any specific combination of features, but the amount of data you will get for specific combinations of feature is going to be drastically reduced with the number of features you wish to look at. I will assert that looking at each feature independently is half the battle, and looking at combinations of 2 features is going to cover a higher percentage of the remaining cases, and so on. And if you find interesting interactions, you can COMBINE them in a separate test - by basically considering feature x and y together as a single compound feature. You would only do this when you have a high degree of confidence that these 2 features definitely have some kind of synergy. You might even do this with features that have a negative interaction, perhaps taking care that they are never tested together. - Don -- 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 mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mathematical Go
Berlekamp came to MIT and gave a talk for us, and after that we talked about Go and Chess and other things and took him out to eat. I can vouch for the fact that he is a truly humble and modest person and is a real joy to talk to. It was all thoroughly enjoyable. - Don On Wed, Nov 25, 2009 at 12:54 PM, Richard Brown batma...@gmail.com wrote: On Wed, Nov 25, 2009 at 11:13 AM, Álvaro Begué alvaro.be...@gmail.com wrote: [... Read Winning Ways first...] On Wed, Nov 25, 2009 at 11:53 AM, Aldric Giacomoni ald...@trevoke.net wrote: Has anyone read this book? http://www.amazon.com/gp/aw/d.html/ref=redir_mdp_mobile/176-9930046-0953944?a=1568810326 What do you think of the contents? You can see and hear Elwyn Berlekamp delivering a 2006 talk about Mathematics and Go (culminating in a discussion of coupon go) at: http://www.youtube.com/view_play_list?p=005B561126D6A51E . The content of that video is interesting for at least one reason: Berlekamp was speaking to a crowd of non-go-players, and so his historical fluff is well-designed for giving such an audience a quick introduction to the historical significance of go in Asian culture, comparing it to the letters and science of Europe over the same time period. Berlekamp spoke to the Letters and Science Faculty Forum of the UC-Berkeley Faculty Club. Among other things, he also analyzes the endgame from a go game between Jujo Jiang and Rui, Naiwei. Perhaps it was false modesty on his part, but it seemed to me that Berlekamp knows full well that his own work is just a drop in the bucket, and that future go-mathematicians would ultimately, inevitably, go far beyond his meager efforts. As Álvaro notes: The whole theory is fascinating, but in the case of go it's only relevant when the game has been reduced to a number of completely independent small regions (if at all). I don't have the book with me to check, but I think they didn't have a good way to analyze kos. I think that Berlekamp would admit to the irrelevance and incompleteness of his own work, if you pressed him on it. The video is definitely worth a look. -- Rich ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Optimizing combinations of flags
On Wed, Nov 25, 2009 at 2:00 PM, Matthew Woodcraft matt...@woodcraft.me.ukwrote: steve uurtamo wrote: the way to do all of this exactly is with experimental design. to design experiments correctly that handle inter-term interactions of moderate degree, this tool is quite useful: http://www2.research.att.com/~njas/gosset/index.htmlhttp://www2.research.att.com/%7Enjas/gosset/index.html That doesn't seem to directly support deriving information from random trials. For computer go tuning, would you play multiple games with each parameter set in order to get a meaningful figure? That seems likely to be less efficient than treating it as a bandit problem. This does not replace bandit, it's a way to tune parameters. You might have 50 parameters and so you play a few thousand games using random combinations of these parameters for instance. And then you have data based on the win/loss records of the different parameters and use this to settle on a good set of parameters to be used. - Don -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 1:58 AM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: this simplification of the rules Simplification? It does not even simplify strategy. I am asserting that a properly modified bot is going to better at this variant of the game. It's way easier to play go like a beginner who is focused more on not losing points on the board. If you remember, we started programming MC that way and it was harder to beat them by high scores but it was easier to beat them.Then it was discovered that scoring wins and losses made a huge difference in their ability to win.This is pretty much a proof that playing for score is a significantly DIFFERENT strategy. It almost certainly has to be a simpler strategy because it's more like how weaker players play the game. - Don -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 9:34 AM, Alain Baeckeroot alain.baecker...@laposte.net wrote: Le 23/11/2009 à 15:04, Don Dailey a écrit : On Mon, Nov 23, 2009 at 1:58 AM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: this simplification of the rules Simplification? It does not even simplify strategy. I am asserting that a properly modified bot is going to better at this variant of the game. It's way easier to play go like a beginner who is focused more on not losing points on the board. If you remember, we started programming MC that way and it was harder to beat them by high scores but it was easier to beat them. Yes, but the aim was to win, not to win by a lot, this is NOT the same rules. I don't think we can guess if the bot are weaker or stronger with this new rules (i guess it's about the same :-) ) Of course you can guess, and that's what I am doing. I am estimating that this is a simpler game but I could be wrong. I think simpler games favor computers.I think it's simpler because I am a weak player and I think more in terms of total points rather than winning games (in my beginners mind there is no difference even though objectively I know better, but it's too much for me to process.) Even strong players do this as a shortcut to make it easier to think about their next move, but they are more aware of concepts like, I MUST win this chunk of the board or I will lose the game. So it seems pretty evident to me that this is a simpler concept to grasp and play by and thus one that computers would do better at relative to good human players who are much better at risk assessment than computers. I won't go so far as to say that this eliminates the element of risk from the game, but it seems obvious to me that it is an easier way to think about the game. Then it was discovered that scoring wins and losses made a huge difference in their ability to win.This is pretty much a proof that playing for score is a significantly DIFFERENT strategy. It almost certainly has to be a simpler strategy because it's more like how weaker players play the game. http://www.suomigo.net/wiki/HahnSystem says it forces players to fight more. and improves reading skill. All that really means is that the game is longer. You have to fight for points even if 350 points have already been decided and there are 11 left to fight over. I think it's a stretch to claim this means it takes a lot more skill to play with the Hahn system. - Don For sure it would be fun for people to watch a kgs hahn tournament, with bots fighting hard and crushing the weaker one. (with R.Jasiek rule : 1 point on board gives 1 point for tournament) btw, gnugo would be better at this, as it tries to maximise score. Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
I have repeatedly stated that the Hahn system is a simplification, but this is just a guess on my part and I might have it backwards.I'm not sure whether that invalidates the idea that computers will play this better or not. Here is a thought experiment.Imagine an omniscient player or program which is capable of always playing the very best move according to either criteria that you configure.You can configure it maximize the score, or to win the game. In win game mode it will play ANY move randomly that is good enough. Since it is omnicient there is no point in talking about risk, or chances in any context. In a lost game it would play a move at random. In maximize score mode it would choose the move that maximizes the total points taken on the board. It would be the perfect Hahn system player for instance. The more difficult strategy is to maximize total points on the board.In fact, this is a superset of the other strategy because maximizing the points taken will always be a valid way to implement the try to win game strategy, but the reverse is not true. This is no doubt why computers play stronger with the goal to win the game - it is a much less distracting concept for a computer to grasp. So I am not sure, but I might be reversing my point of view on this.I have to think about it some more. It's clear that computers play weaker with this strategy, but I'm still pretty sure they will play the Hahn system better with the maximize points taken strategy but it may not follow that they will play this better relative to humans.Especially if it is a more challenging goal. What I cannot decide is if it is really more challenging - I just know it's more challenging to do it perfectly. - Don On Mon, Nov 23, 2009 at 11:00 AM, Robert Jasiek jas...@snafu.de wrote: steve uurtamo wrote: the idea that i like about keeping track of number of points won or lost by is that not only could you find the winner, but you could find how absolutely dominant, on average, they were against their opponents. Under normal Go: no! E.g., some players have the style to let every game be close. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 11:07 AM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: I think it's simpler because I am a weak player and I think more in terms of total points rather than winning games Many weak players have told me (and for me when I was a beginner it was the same) that they do not count territories at all...! Simpler than what you are suggesting:) I'm not claiming that weak players count up the board, I am saying the opposite.Weak players don't care about what they have already won or lost, they are just trying to grab up what they can with little concern about what they actually NEED. There is a huge difference in what you think I said and what I was trying to communicate. it seems obvious to me that [very rough positional counting] is an easier way to think about the game. The actual step of counting may be easier but every strategic consequence becomes harder because all decision making has to take into account an error range, i.e., per decision many more follow-up decisions remain valid and thus still have to be considered. Are you on my side now?I think I am saying what you just said.Really good players are constantly estimating their chances and doing this harder calculation (if I am understanding your correctly) while weaker players are pretty much not concerned with anything but trying to win points, regardless of any assessment of the winning chances. In other words strong players are more likely to secure the win or take the risk when it's needed to win, while weaker players are just trying to pick off points. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
I avoided using the title God because I wanted to avoid issues such as god looking into your brain and playing in such as way as to befuddle the opponent or specially playing against your weaknesses or changing the laws of physics in order to win a game. So to keep it simple I am imagining an infinite speed computer with no special programming other than a brute force approach to omniscience! And such a computer is not calculating risk and such and doesn't know or care about the opponent and his foibles. My primary point is that playing to win as many points on the board is also a winning strategy, but trying to win the game is not a good strategy for winning as many points on the board as possible. But if such a powerful machine were available there would be no need to program the win game strategy, we could just program the win points strategy and get both all rolled up into one. - Don On Mon, Nov 23, 2009 at 12:01 PM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: In win game mode [God] will play ANY move randomly that is good enough. If God is set to play any randomly chosen winning move, yes. Since it is omnicient there is no point in talking about risk, or chances in any context. For a simple definition of God applied to a single game, yes. For an entity in strength between God and Devil (who knows also the opponent's strategy in hindsight), possibly no. For God without hindsight during a tournament, no. For Devil in a single game or Devil with tournament hindsight, yes. In a lost game it would play a move at random. Why random? In maximize score mode it would choose the move that maximizes the total points taken on the board. It would be the perfect Hahn system player for instance. Wrong, since Hahn system has an upper score rewarding boundary. (The thing that punishes me for having taken a too great risk when killing 70 stones groups.) What I cannot decide is if it is really more challenging - I just know it's more challenging to do it perfectly. More challenging for whom? For God, it is equally boring. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
What I cannot decide is if it is really more challenging - I just know it's more challenging to do it perfectly. More challenging for whom? For God, it is equally boring. More challenging in the sense that more work must be done. - Don -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 12:01 PM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: In win game mode [God] will play ANY move randomly that is good enough. If God is set to play any randomly chosen winning move, yes. Since it is omnicient there is no point in talking about risk, or chances in any context. For a simple definition of God applied to a single game, yes. For an entity in strength between God and Devil (who knows also the opponent's strategy in hindsight), possibly no. For God without hindsight during a tournament, no. For Devil in a single game or Devil with tournament hindsight, yes. In a lost game it would play a move at random. Why random? I don't understand the question. If all moves lose, how would YOU select? Did you get the point that I'm defining 2 separate strategies?One is to maximize the points on the board and the other is to not make any distinction whatsoever between moves except whether they win or lose the game. And I'm trying to make the point that maximizing the points on the board is a superior strategy because it is a super-set of the strategy to be only concerned with winning. Let's call this strategy A and strategy B.Strategy A is to maximize the points on the board and strategy B is to only distinguish winning moves. If you play strategy A, then a strategy B player would see those moves as a perfectly valid B strategy. But a strategy A player would frown on many of the moves a strategy B player would play. - Don In maximize score mode it would choose the move that maximizes the total points taken on the board. It would be the perfect Hahn system player for instance. Wrong, since Hahn system has an upper score rewarding boundary. (The thing that punishes me for having taken a too great risk when killing 70 stones groups.) What I cannot decide is if it is really more challenging - I just know it's more challenging to do it perfectly. More challenging for whom? For God, it is equally boring. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 1:39 PM, Robert Jasiek jas...@snafu.de wrote: GoGod and GoDevil are objective technical terms referring to the game tree. They were defined roughly on rec.games.go quite some years ago but I do not recall the definition details by heart. They have nothing to do with psychology or probabilistic playing. So why then did you start talking about knowing the opponetns strategy in hindsight? I don't like using the term GoGod and GoDevil personally because it carries the extra baggage of a being with supernatural powers to influence the game. Of course if it's understood that this is no part of the equation I am ok with it. Ok, I'll use that terminology from now on. - Don -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 3:23 PM, Nick Wedd n...@maproom.co.uk wrote: In message 5212e61a0911231136t1e83ce37i9375a033fe3e0...@mail.gmail.com, Don Dailey dailey@gmail.com writes On Mon, Nov 23, 2009 at 12:01 PM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: In win game mode [God] will play ANY move randomly that is good enough. If God is set to play any randomly chosen winning move, yes. Since it is omnicient there is no point in talking about risk, or chances in any context. For a simple definition of God applied to a single game, yes. For an entity in strength between God and Devil (who knows also the opponent's strategy in hindsight), possibly no. For God without hindsight during a tournament, no. For Devil in a single game or Devil with tournament hindsight, yes. In a lost game it would play a move at random. Why random? I don't understand the question. If all moves lose, how would YOU select? Did you get the point that I'm defining 2 separate strategies?One is to maximize the points on the board and the other is to not make any distinction whatsoever between moves except whether they win or lose the game. And I'm trying to make the point that maximizing the points on the board is a superior strategy because it is a super-set of the strategy to be only concerned with winning. Superior in what sense? Your bang neki strategy is superior if you are playing bang neki, and inferior if you are playing Go. The Go strategy employed by MC-UCT programs is superior for playing Go and inferior for bang neki. I don't know what bang neki means but it's superior against fallible opponent, but against perfect opponent it's not inferior.You can argue that it's not superior agianst perfect opponents and I would agree, but it's not inferior either. In other words it's greater than or equal to playing for the win if you are god. If you are NOT god, then it's easier to play for the win because there is simply less to think about. You only distiguish between wins and losses and not the magnitude of them, which is a simplification for us mere mortals. In chess, it is said that WHITE has an advantage, but that is probably only true for falliable players, since it's probably a draw from gods point of view. But for us it's easy to win when we have the white pieces. Let's call this strategy A and strategy B.Strategy A is to maximize the points on the board and strategy B is to only distinguish winning moves.If you play strategy A, then a strategy B player would see those moves as a perfectly valid B strategy. But a strategy A player would frown on many of the moves a strategy B player would play. Are you assuming that the players can examine the entire game tree? Yes. I'm saying that strategy A is = strategy B if you are God (it will not help against another God but it won't hurt either. But it will help you win against a mortal, therefore I say A = B) If you are NOT god, then strategy B apparently is better. It's better for computers for sure. If you are, I do not understand your paragraph above, the whole issue seems undefined. But if you assume that they (like me) cannot read everything out with certainty, I disagree with your conclusion. I think you actually agree with me. Strategy A is = B if you are God, otherwise strategy B appears to be best. Indeed, I often see players using strategy A in a poor position, by trying to play out the yose well, when I can see that their only hope of winning the game is to start a messy fight (which none of us knows who will win). I do not consider their strategy A as perfectly valid. If you are fallible, I agree that strategy B is best. Strategy A is just as good for winning as strategy B but only if you are God. However, if you ARE god, then strategy A is better than strategy B against fallible players and against another God player it doesn't matter. I think this has been confusing because there are too many frames of reference here and I probably didn't explain it very well. I really only set out to explain why I think the Hahn tournaments may be harder to play after all because it seems to require strategy A, which is harder for fallible players to do as well.(Humans and computers have not mastered either strategy of course but I think strategy B is easier to handle.) Nick In maximize score mode it would choose the move that maximizes the total points taken on the board. It would be the perfect Hahn system player for instance. Wrong, since Hahn system has an upper score rewarding boundary. (The thing that punishes me for having taken a too great risk when killing 70 stones groups.) What I cannot decide is if it is really more challenging - I just know it's more challenging to do it perfectly. More challenging for whom? For God, it is equally
Re: [computer-go] Re: Hahn system tournament and MC bots
On Mon, Nov 23, 2009 at 4:51 PM, Robert Jasiek jas...@snafu.de wrote: Don Dailey wrote: If all moves lose, how would YOU select? E.g., I choose some that creates the most ready traps. Did you get the point that I'm defining 2 separate strategies?One is to maximize the points on the board and the other is to not make any distinction whatsoever between moves except whether they win or lose the game. Sure. And I'm trying to make the point that maximizing the points on the board is a superior strategy because it is a super-set of the strategy to be only concerned with winning. Nonsense. Maximizing the points often means huge dragons with lots of bad aji. A sure lose-a-won-game strategy;) If you lose a won game that is not maximizing the points on the board, so what you are saying is nonsense. We are supposed to be taking about GoGod strategy. What is happening here is that we keep shifting back and forth between contexts.It's like you are only half-way following the conversation but keep speaking up anyway. -- robert jasiek ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Shodan Go Bet: Nov '09 Update
It's too early for computers to win bets like this - but it will eventually happen. We just need to wait a few more years which will come and go before you realize it. - Don 2009/11/22 terry mcintyre terrymcint...@yahoo.com Any hardware which can be brought to the playing site would presumably include today's baby supers, which include a few dozen cores in a desktop box. Would it include whatever fits into Sun's datacenter-in-a-shipping-container? I am less optimistic about the computer's prospects now than I was two years ago. Terry McIntyre terrymcint...@yahoo.com Anarchism is founded on the observation that since few men are wise enough to rule themselves, even fewer are wise enough to rule others. - Edward Abbey ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Hahn system tournament and MC bots
I'm pretty sure that this simplification of the rules would favor computers. Of course that would require some program modifications, primarily counting points on the board instead of wins and losses. These rules basically takes out some (or at least reduces) elements of the game that humans are better at, such as knowing how to judge risk, knowing when to go for it, etc. Go is still way too complex for computers to process well so any simplification like this is going to help computers. - Don On Sun, Nov 22, 2009 at 6:23 PM, Alain Baeckeroot alain.baecker...@laposte.net wrote: A Go tounrmaent with Hahn system has been retransmeted on kgs/eurogo TV With these rules, the actual count makes a difference (as opposed to just win/lose) Winning by 40.5gets 100 points ...... Losing by 40.5gets 0 point see http://senseis.xmp.net/?Bangneki http://www.suomigo.net/wiki/HahnSystem How current MCx bots can handle this kind of rules ? The traditional safe way would ensure 60 points, but trying crazy things (when losing) would cost a lot if the result ends by losing by resignation or -40.5 What is the impact for chosing the best move ? (choose the greediest amongst several with highest winning rate ?) Alain. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: First ever win of a computer against a pro 9P as black (game of Go, 9x9).
There is no question that computers play better at longer time controls even though this has been disputed on this group. Is there any issues with parallelism at short searches?In the old days when I competed in computer chess with many processors, the program could out-search the single processor version many times over at long enough time controls, but the first few ply of search were quite a bit slower, so I would have been better off using 1 CPU for speed chess games. What this meant of course is that at long time controls the CPU advantage for the computer was exaggerated and it may have even been the case that a human had a better chance at fast time controls in order to suppress the big advantage of all those CPU's.I probably could have tuned some of this effect away but we were not competing at short time controls. Is there anything like that going on? - Don 2009/10/29 Olivier Teytaud olivier.teyt...@lri.fr Some elements around blitz: - My feeling that blitz games are harder for computers is based on our games against humans: we always lost games with short time settings. Even in 9x9, Motoki Noguchi or Pierre Audouard could win plenty of fast games, whilst playing strange openings for fun. This is for sure on a small sample. - The newspapers don't take into account or even report the difference between blitz games and standard games on the 29th of october, and they use the not very relevant complexity comparisons based on the number of possible boards or games. But they have nice photos for promoting computer-go :-) Best regards, Olivier Dear all (in particular for your question, Hideki!), please find enclosed some newspapers about the games played on October 29th. Most of them are in chinese. I don't read chinese, if some people can extract some elements... I'll try to have some translations here with our chinese students. Best regards, Olivier -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
2009/10/29 Olivier Teytaud olivier.teyt...@lri.fr Yes, this group does not have a consensus at all on this. On the one hand we hear that MCTS has reached a dead end and there is no benefit from extra CPU power, and on the other hand we have these developers hustling around for the biggest machines they can muster in order to play matches with humans! And Olivier claims that computers benefit more from additional thinking time than humans! Thanks for this comment. I agree that something is strange here :-) Olivier I'm being a bit sarcastic - I recognize that most of the statements made about this general issue are not based as much on logic as they are on emotional feelings or just making rash interpretations of tiny data samples. Almost always with us humans (myself included) when we try to interpret data we lean way in the direction of our own subjective biases. Even our own interpretations are in conflict sometimes.I myself have said things that upon close examination prove to be in conflict with something else I believed, they both could not be true! And then to add insult to injury we try to explain the conflict away with amazingly creative skill instead of just admitting that we might need to adjust our belief system. As far as this subject is concerned, I honestly don't think we fully understand it, myself included. We have a lot of conflicting evidence and I'm going to take a step backwards until we know more. With go it is extremely frustrating. The evaluation (rating/ranking) system is non-standard and rather kludgey and we would need thousands of games to settle this under controlled conditions unless the man/machine difference was enormous. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
2009/10/29 Olivier Teytaud olivier.teyt...@lri.fr Just curious, who actually claimed that and what was it based on? I don't know who claimed it first, and who agreed for it, but I agree with it :-) But you always seek the most hardware when you play against a human it seems. I think you realize it does help a lot to do this, otherwise your team would not be so foolish as to procure the big iron when it comes time to compete. You also are painfully aware that there are problems to be solved that will not easily succumb to just a few more doublings in power. That is exactly as it should be and is not a barrier. I don't think you know the difference between a wall and a point that is just far away. More precisely, I think that increasing time and computational power makes computers stronger, but not for some particular things like long-term life-and-death in corners, or semeai situations. This makes a big limitation on what is possible with MCTS algorithms, in particular against humans. We made a lot of efforts for online learning of Monte-Carlo simulations, in order to improve this, but there's no significant improvement around that. You are thinking with a very limited perspective here. Think in terms of 2 or 3 decades of Moores Law.We had those same barriers in chess that people said were impossible because we usually don't think in terms of getting 10,000 X more computing power, we are stuck in the present and just realize that getting 10X more is not nearly enough to solve some problem as you are observing here.And if 2 decades are not enough wait 2 more. I hope no one responds about Moores Law not holding any longer. That has nothing to do with my argument.My argument is that it takes a huge amount of extra CPU power to make a dent in big problems, just like it was in chess. No big surprise here.If Moores law doesn't hold then we are in trouble and it will take about twice as long. Why twice? I don't really know but by analogy the progress in chess software has been on par or slightly greater than the advances in hardware. (Most people don't realize this and think chess is 95% about hardware, but that is a complete misconception. In very rough terms there has been about the same increase in ELO due to software as to hardware over the last several years.) The combination of software and hardware is the potent combination if Moore's law will hold out for us.Just because it may not happen within the next 2 or 3 years doesn't mean it's a wall or that anything odd is going on here. - Don Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
On Thu, Oct 29, 2009 at 12:40 PM, Petr Baudis pa...@ucw.cz wrote: On Thu, Oct 29, 2009 at 12:00:32PM -0400, Don Dailey wrote: That is exactly as it should be and is not a barrier. I don't think you know the difference between a wall and a point that is just far away. I'd phrase this positively - the point is extremely far away with the current way MCTS will succumb to blunders because of the way it is completely unable to compensate for systematic bias (the amount of computation required to overcome the bias is extreme), but some clever algorithmic improvement could put the point much closer. This is just a discussion how steep a slope we will already call a wall, I think it's more productive to talk about how to make the slope less steep. :) I don't see it as a slope at all, just a matter of distance. So to me it's just a matter of continuing to put one foot in front of the other. But using different terminology than you, we should talk about how to get closer faster. As software people we have to attack it from the software end and not worry about the hardware end so much because that is out of our hands anyway (unless of course we are in hardware.) - Don -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Yes, I agree with you on most of this. However, I believe that Go is a very simple domain in some sense and that we romanticize it too much. I am not saying there is not amazing depth to it, but it's represented very compactly and it's a game of perfect information with very limited choices. Having said that, I do fully appreciate that even if Moores law could hold indefinitely, there are still problems that will take decades to overcome if there are no software advances. - Don On Thu, Oct 29, 2009 at 1:14 PM, Mark Boon tesujisoftw...@gmail.com wrote: Roger Penrose thinks the human brain can do things a Turing machine cannot. (Note: I don't say 'computer'.) He claims it's due to some quantum-physical effects used by the brain. I doubt his ideas are correct, but he did have a few interesting chess-positions to support his theory. Typically, they would contain a completely locked position, say a V-shaped pawn position and bishops on the wrong color to pass the pawn-ranks. These types of positions are very easily analyzed by even mediocre players, yet a computer never gets the right answer. Basically what it shows is that the human brain is able to conceptualize certain things that enable it to reason about situations that cannot be calculated by brute force. I don't claim that a Turing machine cannot do such things as well if programmed well, but it's very easy to see that there could be barriers to computers, no matter how much computing power you give them, if they solely rely on a simple method with brute force. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
What is interesting is not the fact that intrasitivity exists, that is not in doubt. But it quite interesting that this much intransitivity can be created with non-trivial and strong programs. I would like to see the data though, specifically the number of games between each player at each level and of course the scores that go with this. Such a differece indicates to me that the program (or MC programs in general) may be too brittle and needs some knowledge that gnuo has. - Don 2009/10/29 Olivier Teytaud olivier.teyt...@lri.fr BTW, recently I've measured the strength (win rate) vs time for a move curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board. Without opening book, it saturates between +400 and +500 Elo against GNU but doesn't upto +800 Elo in self-play. That's somewhat interesting (detail will be open soon at GPW-2009). Just a post to say that I find this remark extremely interesting :-) Thanks a lot Hideki. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
2009/10/26 Richard J. Lorentz lore...@csun.edu How things changes. You would never hear a comment like Remark c) below concerning the old alpha-beta chess engines. Yes, this group does not have a consensus at all on this. On the one hand we hear that MCTS has reached a dead end and there is no benefit from extra CPU power, and on the other hand we have these developers hustling around for the biggest machines they can muster in order to play matches with humans! And Olivier claims that computers benefit more from additional thinking time than humans! - Don Olivier Teytaud wrote: Dear all, For information, our Taiwanese partners(**) for a ANR grant have organized public demonstration games between MoGoTW (based on MoGo 4.86.Soissons + the TW modifications developped jointly with our Taiwanese colleagues) and C.-H. Chou 9P, top pro player winner of the LG Cup 2007. This was during a press conference at Taipei around a French-Taiwanese grant for joint research. Details: a) MoGoTW was running on 32 quad-cores(*) in Taiwan. b) There were two blitz games (15 minutes per side), won by the pro. c) There was one non-blitz game (45 minutes per side). MoGo was unlucky as it was black, but it nonetheless won the game. This game is enclosed. All games can be found on KGS (account nutngo) Remarks: a) Fuego won as white against a 9P a few months ago. Therefore computers have won both as white and black against top players :-) We now should win on a complete game like 4 out of 7 games and the job would be completly done for 9x9 Go :-) b) MoGo already won a game as black, against Catalin Taranu, but I guess the pro, at that time, had played an original opening somehow for fun (I'm not sure of that, however). c) My feeling is that blitz games are not favorable to computers... Statistics are in accordance with this I guess. Humans are stronger for short time settings. d) If I understand well, MoGo won a final semeai in the upper right part. But, nearly everybody on this mailing (except you, Sylvain, maybe, if you still read this mailing-list :-) ?) reads go games better than me, so don't trust this comment :-) e) The game was longer than most important games I've seen (59 moves). All comments welcome. Best regards Olivier (*) mogoTW was supposed to run on this 32x4 system, but other platforms were prepared in case of trouble on this cluster. I'll publish a correction if I see that the game was not played on this machine. (**) contributors include all the mogo-people, plus Mei-Hui Wang, Chang-Shing Lee, Shi-Jim Yen, and people that I only know by their nicknames (Coldmilk, TomTom...) - sorry for the people I've forgotten, names in Chinese are difficult for me :-) -- ___ computer-go mailing listcomputer...@computer-go.orghttp://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Peter, did your comment get cut off? Anyway, I agree with you on this. Humans are not stronger on short time settings. I believe that SOME humans could be better if they have a problem staying interested for a longer period of time and the longer time control upsets their rhythm or something. But I don't believe it's a general rule. I did know a chess player who was a weak expert and all he did was play speed chess all day long. In tournaments with long time controls, he still played speed chess. It was crazy, finishing his games after only having used 5 or 10 minutes. He claimed that he did not need longer to think because he was always sure the move he played was the best. Of course this is completely ridiculous since he was hundreds of ELO below the best human players and even further from perfect play. - Don On Mon, Oct 26, 2009 at 3:58 PM, Petr Baudis pa...@ucw.cz wrote: Hi! On Mon, Oct 26, 2009 at 07:19:45PM +0100, Olivier Teytaud wrote: For information, our Taiwanese partners(**) for a ANR grant have organized public demonstration games between Thanks for the information! MoGoTW (based on MoGo 4.86.Soissons + the TW modifications developped jointly with our Taiwanese colleagues) and C.-H. Chou 9P, top pro player winner of the LG Cup 2007. Could you give us at least a general picture of improvements compared to what was last published as www.lri.fr/~teytaud/eg.pdfhttp://www.lri.fr/%7Eteytaud/eg.pdf? Is it just further tuning and small tweaks or are you trying out some exciting new things? ;-) c) My feeling is that blitz games are not favorable to computers... Statistics are in accordance with this I guess. Humans are stronger for short time settings. Maybe in high-level 9x9 games that's true, but as a general statement I'd dispute this, at least in watching 5k-1k-level 19x19 MCTS games on KGS I got a completely different impression; humans are much more -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Yes, you understood me right. I disagree with Olivier on this one.To me it is self-evident that humans are more scalable than computers because we have better heuristics. When that is not true it is usually because the task is trivial, not because it is hard. - Don On Mon, Oct 26, 2009 at 6:14 PM, Mark Boon tesujisoftw...@gmail.com wrote: 2009/10/26 Don Dailey dailey@gmail.com: 2009/10/26 Richard J. Lorentz lore...@csun.edu Yes, this group does not have a consensus at all on this. On the one hand we hear that MCTS has reached a dead end and there is no benefit from extra CPU power, and on the other hand we have these developers hustling around for the biggest machines they can muster in order to play matches with humans! And Olivier claims that computers benefit more from additional thinking time than humans! Well, we had this discussion a while back on this list. I (and some others) argued that humans play fast extremely well and that more time provides a rapidly decreasing benefit. If I remember well it was you who was arguing this not being the case and that pros benefit greatly with more time. So it seems we're starting to see some support for the argument that at least in Go professional players don't benefit as much from more time than computers do at the moment. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Neural networks
On Wed, Oct 14, 2009 at 10:21 AM, Álvaro Begué alvaro.be...@gmail.comwrote: We should let go of this idea that artificial neural networks have anything to do with the brain. ANNs are just a family of parametric functions (often with too many parameters for their own good) and associated tuning algorithms (learning is a bit pretentious). Perhaps they took vague inspiration in a cartoonish version of the brain, but that's about it. People tried to make flying machines by imitating birds for a long time. Planes and helicopters fly, but not like birds do it. Similarly, I believe that whenever we figure out how to make machines that play go well, they will not do it like a brain does it. Álvaro. Yes, I agree. It's very common in my opinion to try to bend the program too much to how we do it. It's natural to try to imitate humans because humans are indeed superior.But our hardware is so different that it does not always make sense to imitate us. Even among humans we do not always try to imitate each other, if we recognize that something is missing.For instance a short basketball player will need to play a different kind of game than a very tall basketball player.He would choose a style that emphasized his strengths and minimized his weaknesses. In fact it's likely that we would be placing limitations on the computer if we tried to imitate people too much.Right now chess programs are superior to human players, but nobody has ever suggested that perhaps we should try to imitate them! Having said all of that, it's still important to analyze what works for humans that perhaps could be effectively used for our programs. We just don't want to take this too far if it's doesn't work. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Rating variability on CGOS
One must be very careful about proclaiming wild transitivity issues. I'm not saying it's not an issue, there is some going on with every program on CGOS, but with less than 500 games between any two players you are going to get error margins of +/- 30-50 ELO or something like that. And CGOS ratings are always going to have high error margins because they are incrementally rated.You should go by the bayeselo rating to get something more stable and you really need to have over 1000 games to begin trusting the ratings within 20 or 30 ELO. - Don On Thu, Oct 8, 2009 at 4:50 PM, Petr Baudis pa...@ucw.cz wrote: On Thu, Oct 08, 2009 at 01:48:05PM -0600, Brian Sheppard wrote: About two weeks ago I took Pebbles offline for an extensive overhaul of its board representation. At that time Valkyria 3.3.4 had a 9x9 CGOS rating of roughly 2475. When I looked today, I saw Valkyria 3.3.4 rated at roughly 2334, so I wondered what was going on. I found a contributing factor: Valkyria has massively different results against Pachi than against Pebbles. It happens that Pachi started playing a day or two after Pebbles went offline. Pebbles and Pachi are both rated around 2200, but Valkyria shreds Pebbles a lot more often than Pachi: Pachi: 185 / 273 = 67.8% Pebbles: 429 / 503 = 85.3% There are a lot of lessons here... So, I'm curious how well Pachi will do against Pebbles. ;-) I'm hoping that I'm nearing another major improvement in strength soon, so the current version may not stay on CGOS much longer. (Curiously, the two identical Pachi instances were even after many games very far apart in ELO points (about 100 ELO), somehow one of the instances was winning against the other in about 80% of games; it corrected itself after few more days without me doing anything, though. Stochastic environments are funny.) -- Petr Pasky Baudis A lot of people have my books on their bookshelves. That's the problem, they need to read them. -- Don Knuth ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: kgsGtp (was Re: [computer-go] Congratulations to AyaMC!)
2009/10/6 Jason House jason.james.ho...@gmail.com That already exists: kgs-game_over is sent after every game (if you support it). That it's up to your bot to decide if it should terminate, run a full garbage collection, pause pondering, etc... I think most people use a sentinel file. Are you sure that isn't cgos that does that?In other words, does KGS do that too? - Don Sent from my iPhone On Oct 6, 2009, at 5:28 PM, Peter Drake dr...@lclark.edu wrote: Incidentally, if a new version of kgsGtp appears, the one feature I desperately want is a way to tell kgsGtp to disconnect after the current game. As it is, I have to either wait for the end of the game or kill my program in the middle of someone's game. Peter Drake http://www.lclark.edu/%7Edrake/http://www.lclark.edu/~drake/http://www.lclark.edu/%7Edrake/ On Oct 6, 2009, at 2:19 PM, Jason House wrote: Yes, there is a way. Error responses start with ? and success responses start with =. The bigger issue is how to detect crashes in kgsGtp. Maybe it's as simple as having kgsGtp kill a bot with outstanding commands before joining a new game. Sent from my iPhone On Oct 6, 2009, at 3:22 PM, terry mcintyre terrymcint...@yahoo.com terrymcint...@yahoo.com wrote: Is there a way to implement I don't understand that command? a NAK, perhaps? Terry McIntyre terrymcint...@yahoo.comterrymcint...@yahoo.com And one sad servitude alike denotes The slave that labours and the slave that votes -- Peter Pindar -- *From:* Nick Wedd n...@maproom.co.ukn...@maproom.co.uk *To:* computer-go computer-go@computer-go.org computer-go@computer-go.org *Sent:* Tue, October 6, 2009 9:13:17 AM *Subject:* Re: [computer-go] Congratulations to AyaMC! In message wladvtgcx1ykf...@maproom.demon.co.ukwladvtgcx1ykf...@maproom.demon.co.uk wladvtgcx1ykf...@maproom.demon.co.uk, Nick Wedd n...@maproom.co.ukn...@maproom.co.uk n...@maproom.co.uk writes Congratulations to AyaMC, winner of Sunday's KGS Computer Go tournament! My report is at http://www.weddslist.com/kgs/past/52/index.htmlhttp://www.weddslist.com/kgs/past/52/index.html http://www.weddslist.com/kgs/past/52/index.html Two people had bots crash after receiving the message FINEST: Still an outstanding command. I do not know what this means, and am reporting it to wms. I have heard back from wms: The still an outstanding command message means that a command has been sent to the engine, but the engine hasn't yet answered it. That's probably a bug in the engine, because GTP requires all commands to be answered with an acknowledgement or an error. So it seems that CzechBot (=MoGo) and Fuego need to implement something, I don't know what. It's strange that this has never come up before. Nick -- Nick Weddn...@maproom.co.uk n...@maproom.co.uk n...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org computer-go@computer-go.org computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/http://www.computer-go.org/mailman/listinfo/computer-go/ http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.orgcomputer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.orgcomputer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] test: ignore
2009/9/12 jorge jorge...@terra.es sorry, but as i don´t receive anything, i don´t know is the list is not active or if i´m doing something wrong ... It's fairly active, but you might not get a message every single day. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] any mac programmers out there?
I tried both llvm-gcc and CLANG. I did not have any trouble getting them to work for my 64 bit chess program. I didn't try too hard, but neither is producing executables as fast as gcc. llvm-gcc is the slowest about 20% slower than gcc and clang is only a little slower than gcc. Since I developed with gcc it is very likely that the program and the way I write code is tuned to work well with gcc. Perhaps I will try this with the GO program, which is not heavily optimized. I grabbed and compiled the latest llvm and clang - so I cannot be accused of using outdated versions. And I didn't use the debug versions either. But I will keep my eye on llvm and clang. - Don 2009/9/6 Mark Boon tesujisoftw...@gmail.com On Sep 5, 2009, at 4:41 AM, terry mcintyre wrote: Found an interesting article on Snow Leopard at Ars Technica ... 20-some pages. http://arstechnica.com/apple/reviews/2009/08/mac-os-x-10-6.ars Of interest to Computer Go programmers: the addition of blocks to C, which allow closures and other fun stuff, much like Lisp. LLVM, which allows JIT compilation to multiple architectures, including GPUs; Grand Central Dispatch, which provides very light-weight concurrency; and CLANG, a new compiler which is said to be quite an improvement over GCC. Open CL, which leverages LLVM to program GPUs. Seems interesting indeed. Does anyone know how Objective-C 2.0 compares in speed to C? I like the promise of abstracting the CPU to the point where you can execute either on the CPU or the GPU, depending on which is available and which is suitable. I also like the blocks, it seems a little more elegant and more flexible than anonymous functions in Java. Combined with light-weight concurrency makes for an interesting combination. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bitmap Go revisited and mockup implementation
A couple of notes. Some of us on this computer-go forum are also Chess programmers and many of write 64 bit chess programs. I am one of them but I know there are others. My 64 bit chess program runs almost 2X faster if I compile it to run on a 64 bit OS - in other words I'm using real 64 bit values to represent the bit boards.So this really is a big deal - you can expect a pretty good gain. I also toyed with a bit board style go program and started working on one long ago. You still need several 64 bit words to represent the state of each color.I started to write some routines that did shift, popcount, etc as fast as possible. Basically you had to compile the program for each board size, and it figured out how many bits were needed and simulated (using struct) an integer data type that was large enough. About half way through I decided not to proceed - at the time I had some idea that I was more interested in and I never picked it back up - assuming that it would be too slow (but I didn't prove it.) I think you could look at glaurung (the chess program) to find great routines for the common bit operations. I think the author of Glaurung does it about as fast as it can be done and even has assembly code for finding the right-most bit, or something like that. But you could probably learn something from looking at that program. I'm not sure how useful this might be for go, but there are some pretty clever tricks with minimal perfect hashing - that you might find some use for. Perhaps there is a way to make this work for eye-detection or someting. There is some great explanations here: http://chessprogramming.wikispaces.com/I think you want to look under move generation perhaps. Perhaps this cannot be used for GO, but it's fun to read anyway :-) The only issue of course is that you need more than 64 bits for go - but the general principles might be made to work. - Don 2009/8/25 René van de Veerdonk rene.vandeveerd...@gmail.com Antoine, I apologize for misrepresenting your feelings. What I wanted to convey is that your e-mail expressed that with the same amount of computation, other implementation strategies provide more information, so the information gained for the effort put in is disappointing. In other words, bitmap-go had better be much faster to make up for the lack of information gained ... and it wasn't. That's pretty much what you are saying as well, I believe. As are the others in this thread. I think we can all agree on this. Going into this project, I was well aware that I was going to end up with light playouts only, and that heavy playouts is the way to go except perhaps for some special purposes such as ladder readouts. I was also well aware of the scaling argument. But, I hadn't thought that this would be the first thing thrown at my first post, as there are many programmers that seem to be stuck at 9x9. Nonetheless, bitmap-go as a topic keeps resurfacing on this mailing list every once in a while and nobody ever put solid data and a reference implementation behind it. That is what I wanted to accomplish with my mockup. Confession #2: I have been working on my own MCTS implementation using the standard implementation methods that almost everybody else is using. But there is a never-ending laundry-list of things that I would like to include before I would reach reasonable strength (where reasonable is a moving target). In the mean time, there are many others that have demonstrated much more capable programmers than I ever will be. So, by providing this bitmap-go mockup at least I had the feeling that I was contributing something newsworthy to the conversation. This may have never happened if I would wait until my MCTS program is ready. I imagine that there are others on this list in a similar situation. Besides, this was an interesting side-project and perhaps someone else can benefit from it (go for it Brian!). And, yes, it was fun. Okay, enough mesmerizing, on to the main topic. David, Lukasz, I did modify my mockup to do 19x19 bitmap-go (attached). It is a hardcoded solution using arrays of three 128-bit variables. I did not even attempt to optimize this version, so this is not the best possible solution. Nonetheless, here is a comparison: Example output (9x9): = [game] = 30236.1, [moves] = 111.071 [game] = 30249.7, [moves] = 111.068 [game] = 30145.7, [moves] = 111.089 [game] = 30237.7, [moves] = 111.122 [game] = 30210.1, [moves] = 111.101 [game] = 78.0488 kpps, [moves] = 111.023 [game] = 78.0488 kpps, [moves] = 111.045 [game] = 78.0488 kpps, [moves] = 111.046 [game] = 79.0123 kpps, [moves] = 111.131 [game] = 78.0488 kpps, [moves] = 111.082 [legal] 110/51, [pick] 110/74, [play] 106/168, [score] 44, [win] 0.4187 [legal] 111/51, [pick] 111/74, [play] 106/168, [score] 40, [win] 0.4201 [legal] 111/52, [pick] 111/75, [play] 106/168, [score] 42, [win] 0.4276
Re: [computer-go] Dynamic komi at high handicaps
I'm glad to see some are actually experimenting with this. My suggestion is to modify a program such as fuego to follow one of the algorithms as suggested - then test it with a large sample of games. If it doesn't work we can experiment until it does or until we are satisfied that it won't. And the tests should be visible and well documented. Instead of talking about it constantly we could be having fun experimenting with it. So it appears there has been some experimentation so far. We just need some better reporting on what was tried and how it did. - Don On Thu, Aug 20, 2009 at 7:00 AM, Yamato yamato...@yahoo.co.jp wrote: steve uurtamo wrote: zen wins many more of its even games with no handicap than it does with even, say, an even 2 stone handicap as either black or white. i haven't compiled numbers for it (i'm not zen's maintainer), but i watched it happen over the course of about 50 games one day. it was pretty consistently worse with any kind of handicap on the board, the more handicap the worse. fix the handicap problem and it would likely rise a stone in strength. I have done some experiments in dynamic komi on Zen, and it didn't work. My experiments might not be enough, but I feel this kind of idea is not a solution for the handicap problem. Did anyone succeed with it? -- Yamato ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
One must decide if the goal is to improve the program or to improve it's playing behavior when it's in a dead won or dead lost positions. It's my belief that you can probably cannot improve the playing strength soley with komi manipulation, but at a slight decrease in playing strength you can probably improve the behavior, as measured by a willingness to fight for space that is technically not relevant to the goal of winning the game.And only then if this is done carefully. However I believe there are better ways, such a pre-ordering the moves. Even if this can prove to be a gain, you are really working very hard to find something that only kicks in when the game is already decided - how to play when the game is already won or already lost.But only the case when the game is lost is this very interesting from the standpoint of making the program stronger. And even this case is not THAT interesting, because if you are losing, on average you are losing to stronger players. So you are working hard on an algorithm to beat stronger players when you are in a dead lost game? How much sense does that make? So the only realistic pay-off here is how to salvage lost games against players that are relatively close in strength since you can expect not to be in this situation very often agaist really weak players.So you are hoping to bamboozle players who are not not weaker than you - in situations where you have been bamboozled (since you are losing, you are the one being outplayed.) That is why I believe that at best you are looking at only a very minor improvement.If I were working on this problem I would be focused only on the playing style, not the playing strength. If you want more than the most minor playing strength improvement out of this algorithm, you have to start using it BEFORE the loss is clear, but then you are no longer playing for the win when you lower your goals, you are playing for the loss. - Don 2009/8/19 Stefan Kaitschick stefan.kaitsch...@hamburg.de One last rumination on dynamic komi: The main objection against introducing dynamic komi is that it ignores the true goal of winning by half a point. The power of the win/loss step function as scoring function underscores the validity of this critique. And yet, the current behaviour of mc bots, when either leading or trailing by a large margin, resembles random play. The simple reason for this is that either every move is a win or every move is a loss. So from the perspective of securing a win, every move is as good as any other move. Humans know how to handle these situations. They try to catch up from behind, or try to play safely while defending enough of a winning margin. For a bot, there are some numerical clues when it is missbehaving. When the calculated win rate is either very high or low and many move candidates have almost identical win rates, the bot is in coin toss country. A simple rule would be this: define a minimum value that has to separate the win rate of the 2 best move candidates. Do a normal search without komi. If the minimum difference is not reached, do a new a new search with some komi, but only allow the moves within the minimum value range from the best candidate. Repeat this with progressively higher komi until the two best candidates are sufficiently separated.(Or until the win rate is in a defined middle region) There can be some traps here, a group of moves can all accomplish the same critical goal. But I'm sure this can be handled. The main idea is to look for a less ambitious gloal when the true goal cannot be reached. (Or a more ambitious goal when it is allready satisfied). By only allowing moves that are in a statistical tie in the 0 komi search, it can be assured that short term gain doesn't compromise the long term goal. Stefan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
On Wed, Aug 19, 2009 at 9:39 AM, Magnus Persson magnus.pers...@phmp.sewrote: Don, what you write is certainly true for even games, but I think the problem is a real one in high handicap games with the computer as white. I use a hack to make Valkyria continue playing the opening in handicap games as white. It is forbidden to resign in the opening and early middle game because it would if it could. In handicap games the situation is different. You have roughly even chances whether taking the handicap or giving it. I think this illustrates that fundamentally this is an opponent modeling issue.And I really like the idea that someone had of throwing in occasional pass moves for the player who is presumed weaker. There is an analogy in computer chess - it's called the null move heuristic. If it is white to move, you can measure the potential of blacks positions by playing a pass move for white (called the null move) and the a reduced depth search.Whatever score is returned can be considered a lower bound - since you as white skipped one of your moves. With Go it is a little different. If you are trying to beat a much stronger player but you have been given a nice advantage due to handicap, then the playouts will see you easily winning the game and you will play these random looking moves. However, if the computer throws in some pass moves for itself in the playouts, it will play more focused - it will be challenged to find strategies that work in the presense of it's own sloppy play. In other words the computer will stop this anything works attitude and it will focus on robust strategies that give it some room for error. It should be able to find these more robust strategies because it knows it is comfortably ahead. I don't know if this will actually work, it's only at the idea stage as far as I know - but it's something that seems more consistent with the actual problem.Komi manipulation changes the goal which is very dangerous but this ideas does not change the goal, just how it is achieved. To rephrase your argument for even games, the problem situation should never occur because the losing player *should out of courtesy* resign long before the evalutaion become so skewed. That's not correct, because with handicap games the premise is different. My reasoning is based on the well known fact that you will not often get outplayed by signficantly weaker opponents and you will not often outplay signficantly stronger opponents. But this does not apply to handicap games because nobody was outplayed - you started from a game that is a dead win for one side. In a handicap game, it's not only likely, it is CERTAIN that you will find youself in a dead won game against a much stronger opponent.In even games this is going to be a rare occurance. But this does not apply to h9 games on 19x19 for example. And if I am not mistaken strong heavy playouts evaluates such positions very pessimistically, and thus we have a problem to solve, which grows with increasing playing strength. Still stronger programs will discriminate between bad and good moves even with extreme scores, so I think the dimensions of this problem is exaggerated. Yes, it's a problem. And likewise with komi manipulation, the stronger the program is the more likely a small komi change will wildly change the score, from dead won to dead lost or visa versa. Imagine a program so strong that it always plays random moves when losing, and when winning it randomly plays any move that does not lose. It should be obvious that in a winning position, it is going to play a winning move with certainty, but if you adjust komi to make it play better it will play a random move - which could be a losing move. This thought experiment consistitues a kind of proof that the idea at it's most fundamental level is wrong. This can be salvaged by doing multiple searches with different komi's and only playing moves they have in common. I think this all gets complicated (and interesting) becasue we tend to think in two different ways about playing games, one way is all about correctness, finding the best move in the game theoretic sense and the other is how to improve your practical winning chances in the face of fallible opposition (such as blowing smoke in his face.) So it's rather hard to make any kind of proof that something like this is better or not better - it all has to be emprical. - Don -Magnus Quoting Don Dailey dailey@gmail.com: One must decide if the goal is to improve the program or to improve it's playing behavior when it's in a dead won or dead lost positions. It's my belief that you can probably cannot improve the playing strength soley with komi manipulation, but at a slight decrease in playing strength you can probably improve the behavior, as measured by a willingness to fight for space that is technically not relevant to the goal
Re: [computer-go] Dynamic komi at high handicaps
2009/8/19 terry mcintyre terrymcint...@yahoo.com Consider the game when computer is black, with 7 stones against a very strong human opponent. Computer thinks every move is a winning move; it plays randomly; a half-point win is as good as a 70-point win. Pro gains ground as computer makes slack moves, taking slightly less than its full due. At some point, the computer, being the weaker player, makes one slack move too many and loses the game. Rinse and repeat. All you are doing here is repeating the idealized scenario that illustrates the rationale for this idea. That is a fine way to describe how this has potential to be a solution to the problem, but it doesn't explain why it has not been made to work and it does not address the fact that your scenario is highly idealized - not all positions work that way with everything so cut and dried. I can do exactly the same thing and I have been, constructing scenarios that will fail with any heuristic you propose. But that does not prove or disprove anything. So I propose that we need to start thinking about why this has been so resistant to success and consider the possibility that it doesn't work, or that we are not properly addressing the reason why it doesn't work.And to do this YOU have to be the one that constructs counter-examples. At some point, it dawns on the programmer: must attack to win handicap games. Must be a little bit greedy, to slow down the process of attrition. The attack part I agree with, the greed I do not. Dynamic komi models something real: the significant advantage of the computer in a handicap game. It tries to preserve as much of that advantage as possible. I think the problem and what I consider your misconception is revealed here. You use the word advantage incorrectly. Grabbing up points on the board is a different concept than having or not having an advantage Your solution is to suddenly switch to an inferior definition of advantage, one that is clearly broken, otherwise we would be using point count instead of win count in our programs. So I don't see this at all as trying to preserve the advantage, I see it as giving it away. I really believe the secret has to be in the playouts - we use those to estimate our chances. If you change komi the playouts try to estmate the chances that you will win at that NEW KOMI, not at some other komi. I don't know if it will work for computer vs human games. I do know that a similar idea helped me defeat a human player and reduce my handicap by 3 stones. Not having the patience for thousands of 30-minute games to achieve statistically valid results, I settled for trouncing my opponent three games in a row by a large margin, then doing it again with a smaller handicap for three more games. I can't win by 70 stones in a 7 stone game, but 20 or 30 was enough to prove my point. If I made random plays under the assumption that I still had a half-point win, my opponent's predictive powers would be superior to mine - that's why he gives me a handicap and not vice versa. That trick helped you due to human psychology. Humans have a tendancy to rise to the occaions and computers do not know how to try harder like we do. In computer chess one of the strengths of the old programs was that when they were losing they did not become disheartened like human players often do. Once I win a pawn or two or a piece you can sometimes feel your oppoent resign even if he doesn't say the words right away. You also assume the computer program is being sloppy which could not be farther from the truth. If the comptuer plays a random looking move it's only because the move has no affect on the winning chances that are within the computers ability estimate.And the move is only random because you define it to be so. If you try the same thing, you are just being cocky and you are letting your guard down. Us humans must always be vigilant and keep our interest in the game as high as possible and the best way to do this is to continue to fight - what is called the follow through in baseball. In tennis doubles, after breaking the opponent serve we used to say, now that we have them down, let's kick them. You almost have to play like you are losing in order to win if you are human. But computers always play at full throttle. I can't really be sure that my prediction of a 22.5 point win is exact to the last decimal point - but if it should be within 5 or 10 or even 20, I'm perfectly happy. It's nice that statistics of a series of one-bit values are so useful, but when a significant fraction of those one-bit values are 100% wrong, that introduces a bit of noise to one's estimates. One hopes that they balance evenly, but perhaps they do not. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* Don Dailey
Re: [computer-go] (no subject)
PS: Once again I would like to mention my report on Laziness of Monte Carlo, at http://www.althofer.de/mc-laziness.pdf In the meantime, a student has found the same phenomenon in UCT search (instead of basic MC). Also in discrete online optimization (so outside of combinatorial games) it has been observed by another Ph.D. student of mine: porcedures on Monte Carlo basis are stronger when they have the impression that the situation is tense. Laziness is something we all agree on. This is not in dispute. But how do you create the required tension in a way that produces a program that plays the game better? I don't mean selected positions, but the entire game. - Don -- Neu: GMX Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate für nur 19,99 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Laziness
On Wed, Aug 19, 2009 at 2:11 PM, Brian Sheppard sheppar...@aol.com wrote: My conclusion is the same as Gian-Carlo Pascutto's: I am convinced that the phenomenon of laziness is real, and that it hurts practical strength. Unfortunately this is not that point that is in question - I think we all agree on this. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
2009/8/15 Jason House jason.james.ho...@gmail.com On Aug 14, 2009, at 11:02 PM, David Fotland fotl...@smart-games.com wrote: Moves often merge two groups. I count liberties incrementally as I make moves, so no need to search to count. How do you detect shared libreties to avoid double counting. Simple addition does not work for real liberties (and I think you've said previously that you track real liberties. I don't know how David does it or if there are special tricks, but you get real updates without that much extra work - you just have to look at a few points around the newly placed stone. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
My code ignored this problem, I didn't know you were talking about merges.In my code I simply recomputed the liberty count when there was a merge. I'm not convinced all of this is worthwhile, especially when you keep adding more data structure. Also, it seems like modern processors favor keeping things simple and focusing more on cache behavior and branching stuff. All the heavy logic needed to update things incrementally may have worked better 15 years ago. So I guess you just have to try to see what works for you. Code it several different ways to see what works the best. You can use the code of one implementation to debug then next - always checking to see that you get the same answer. - Don 2009/8/15 Jason House jason.james.ho...@gmail.com On Aug 15, 2009, at 8:22 AM, Don Dailey dailey@gmail.com wrote: 2009/8/15 Jason House jason.james.ho...@gmail.com jason.james.ho...@gmail.com On Aug 14, 2009, at 11:02 PM, David Fotland fotl...@smart-games.com fotl...@smart-games.com wrote: Moves often merge two groups. I count liberties incrementally as I make moves, so no need to search to count. How do you detect shared libreties to avoid double counting. Simple addition does not work for real liberties (and I think you've said previously that you track real liberties. I don't know how David does it or if there are special tricks, but you get real updates without that much extra work - you just have to look at a few points around the newly placed stone. It's not that simple. Shared liberties can occur far away with longer changes. I've come up with a scheme that looks a few points around, but only works for chains up to about seven stones. Consider two parallel, linear chains of 5 stones each, separated by a space. A stone placed at one end to connect them is likely miss the more distant shared liberties. X + X It's also possible to construct more complicated cases (with non-linear chains) where there are no locally shared liberties, but some exist further away. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Erlang and computer go
Have you looked at scala yet?I don't understand Erlang performance but scala gives you something higher level than Java or C and same performance as Java, which for most long running applications is pretty close to C performance.I'm currently taking a look at it - I'm always on the lookout for a good high level language with good performance. The thing about C for me is that it always works and it always works well.I don't have a big gripe with java performance for most tasks, but it seems that when you write games like chess and go you invariably end up needing serious control over memory and bits and such. The nice high level abstractions of pretty languages just seem to get in your way it seems. And Java is a real memory hog - a characteristic I'm sure any java based language (such as scala) is going to share. If you want to prototype then you are looking for something that probably still fast and efficient but you are willing to give up some performance for ease of programming - I'll bet you would like Scala if you took the time to learn it. - Don On Fri, Aug 14, 2009 at 4:16 PM, Carter Cheng carter_ch...@yahoo.comwrote: I have been considering experimenting with Erlang as a means of prototyping certain aspects of a computer go program and I was curious if anyone has tried this already. How does a system like Erlang compare performance wise to writing something in say C/C++ (fastest) or Java? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Erlang and computer go
I don't think JVM performance will be an issue for this.I assumed that you were willing to sacrifice a small amount of speed for a high level prototyping language and I think you will only get about 20-30% slowdown over C - I'm judging this by the performance of the reference bots I did in both java and C. You are probably not going to get any closer than this with any other high level language. If you like lispy languages there is something called bitc which is supposed to be pretty close to C in speed and there is also D, which has the potential to be faster than C - although it isn't right now.D would probably be a little closer to C speed than Java or Scala. My issue with Java and JVM is the memory hog nature and pathetic startup times - which make it FEEL slow and unresponsive, but in actuality it is pretty fast.I have found that java doesn't play well with memory - I would not use Java (or Scala) if you plan to do the big memory thing with MCTS, which likes efficient memory management and lots of space for nodes. But I cannot say for sure that this won't work. I don't understand Java enough and maybe there are data structures that you can preallocate in unboxed fashion that will be efficient.But my sense of things is that a node is going to be pretty fat. Honestly, I think your decision to stay with C is likely to be best. I don't even consider anything else when I look at a project that I think is going to need serious performance and memory requirements. - Don On Fri, Aug 14, 2009 at 5:07 PM, Carter Cheng carter_ch...@yahoo.comwrote: Thanks both I guess I will stick with C/C++ for now. I have looked at Scala before though not in this particular context. It looks like a pretty compelling language with some pretty nice features (true lambda functions, argument pattern matching among others). JVM performance does concern me however. I do have a followup question but I will make a separate topic of it. --- On Fri, 8/14/09, Vlad Dumitrescu vladd...@gmail.com wrote: From: Vlad Dumitrescu vladd...@gmail.com Subject: Re: [computer-go] Erlang and computer go To: computer-go computer-go@computer-go.org Date: Friday, August 14, 2009, 1:56 PM On Fri, Aug 14, 2009 at 22:16, Carter Chengcarter_ch...@yahoo.com wrote: I have been considering experimenting with Erlang as a means of prototyping certain aspects of a computer go program and I was curious if anyone has tried this already. How does a system like Erlang compare performance wise to writing something in say C/C++ (fastest) or Java? Hi, I have started for some year ago to try to withe an Erlang library to play go, but got distracted by other stuff. Erlang has a lot of nice features, but in this particular instance speed isn't one of them. The main issue is that there are no mutable data structures, so for all processing there will be a lot of copying. This is somewhat simplified, of course, but the conclusion still holds. I don't have any hard numbers, it would depend very much upon the choice of data structure. Erlang would be good at coordinating work done by simple and fast slaves, written in C for example. It would be very appropriate for a distributed engine. The problem here is that the problem of synchronizing a distributed UCT tree hasn't been solvet yet, to my knowledge. regards, Vlad ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
On Fri, Aug 14, 2009 at 5:13 PM, Carter Cheng carter_ch...@yahoo.comwrote: I have been having difficulties selecting a good representation for liberty sets for strings of stones. I am curious how other people might be doing this. I suspect that for heavier playouts one would like to know not only the count of the liberties but also where precisely they might be relatively quickly(to determine if the group is in atari among other things). Simple is best, until you know EXACTLY what you will want to do and how often you will need to do it. Something pretty simple that I have used in the past is to track each chain and incrementally maintain the liberty count. When you plop a stone down, you have to look at only 4 points to see which group if any it belongs to, or if it connects 2 or more groups.And you can update the liberty counts of all affected groups very quickly. Where there is a capture, you must do considerably more work - but captures represent only a small fraction of the moves. Small captures are more common than large captures, but they require little work. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Erlang and computer go
2009/8/14 terry mcintyre terrymcint...@yahoo.com Peter Drake, I know Orego was written in Java. How do you handle memory allocation? Is there an equivalent of the C method of pre-allocating a large chunk and managing the nodes internally, instead of billions of alloc/free cycles? I think the issue is that you want something that is flat - like a an array of structs in C that have no pointers in them (except perhaps to other nodes like them.) In Java, everything more than simple uboxed types are going to be objects that are much bigger than the sum of the useable pieces in them because java has all this infrastrure necssary for keeping track of them and where they are in memory and so on.At least I think it works that way. - Don Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* Don Dailey dailey@gmail.com *To:* computer-go computer-go@computer-go.org *Sent:* Friday, August 14, 2009 2:25:06 PM *Subject:* Re: [computer-go] Erlang and computer go I don't think JVM performance will be an issue for this.I assumed that you were willing to sacrifice a small amount of speed for a high level prototyping language and I think you will only get about 20-30% slowdown over C - I'm judging this by the performance of the reference bots I did in both java and C. You are probably not going to get any closer than this with any other high level language. If you like lispy languages there is something called bitc which is supposed to be pretty close to C in speed and there is also D, which has the potential to be faster than C - although it isn't right now.D would probably be a little closer to C speed than Java or Scala. My issue with Java and JVM is the memory hog nature and pathetic startup times - which make it FEEL slow and unresponsive, but in actuality it is pretty fast.I have found that java doesn't play well with memory - I would not use Java (or Scala) if you plan to do the big memory thing with MCTS, which likes efficient memory management and lots of space for nodes. But I cannot say for sure that this won't work. I don't understand Java enough and maybe there are data structures that you can preallocate in unboxed fashion that will be efficient.But my sense of things is that a node is going to be pretty fat. Honestly, I think your decision to stay with C is likely to be best. I don't even consider anything else when I look at a project that I think is going to need serious performance and memory requirements. - Don On Fri, Aug 14, 2009 at 5:07 PM, Carter Cheng carter_ch...@yahoo.comwrote: Thanks both I guess I will stick with C/C++ for now. I have looked at Scala before though not in this particular context. It looks like a pretty compelling language with some pretty nice features (true lambda functions, argument pattern matching among others). JVM performance does concern me however. I do have a followup question but I will make a separate topic of it. --- On Fri, 8/14/09, Vlad Dumitrescu vladd...@gmail.com wrote: From: Vlad Dumitrescu vladd...@gmail.com Subject: Re: [computer-go] Erlang and computer go To: computer-go computer-go@computer-go.org Date: Friday, August 14, 2009, 1:56 PM On Fri, Aug 14, 2009 at 22:16, Carter Chengcarter_ch...@yahoo.com wrote: I have been considering experimenting with Erlang as a means of prototyping certain aspects of a computer go program and I was curious if anyone has tried this already. How does a system like Erlang compare performance wise to writing something in say C/C++ (fastest) or Java? Hi, I have started for some year ago to try to withe an Erlang library to play go, but got distracted by other stuff. Erlang has a lot of nice features, but in this particular instance speed isn't one of them. The main issue is that there are no mutable data structures, so for all processing there will be a lot of copying. This is somewhat simplified, of course, but the conclusion still holds. I don't have any hard numbers, it would depend very much upon the choice of data structure. Erlang would be good at coordinating work done by simple and fast slaves, written in C for example. It would be very appropriate for a distributed engine. The problem here is that the problem of synchronizing a distributed UCT tree hasn't been solvet yet, to my knowledge. regards, Vlad ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer
Re: [computer-go] representing liberties
to determine where the last two liberties for a group of stones for example is the obvious method of just doing it to have some method of liberty counting + a exhaustive search to determine the last two liberties for example? --- On Fri, 8/14/09, Don Dailey dailey@gmail.com wrote: From: Don Dailey dailey@gmail.com Subject: Re: [computer-go] representing liberties To: computer-go computer-go@computer-go.org Date: Friday, August 14, 2009, 2:33 PM On Fri, Aug 14, 2009 at 5:13 PM, Carter Cheng carter_ch...@yahoo.com wrote: I have been having difficulties selecting a good representation for liberty sets for strings of stones. I am curious how other people might be doing this. I suspect that for heavier playouts one would like to know not only the count of the liberties but also where precisely they might be relatively quickly(to determine if the group is in atari among other things). Simple is best, until you know EXACTLY what you will want to do and how often you will need to do it. Something pretty simple that I have used in the past is to track each chain and incrementally maintain the liberty count. When you plop a stone down, you have to look at only 4 points to see which group if any it belongs to, or if it connects 2 or more groups.And you can update the liberty counts of all affected groups very quickly. Where there is a capture, you must do considerably more work - but captures represent only a small fraction of the moves. Small captures are more common than large captures, but they require little work. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -Inline Attachment Follows- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] representing liberties
2009/8/14 David Fotland fotl...@smart-games.com
Many Faces old code does something like this. The board is an array of
group numbers. I used many single dimension arrays rather than an array of
structs, because it’s faster.
I would have guessed that having separate arrays would impact cache in a
negative way, because it's nice to do one read and have everything together
in the same cache line. But there are probably many factors that could
make this not such a big deal.
For instance it's probably the case that there are many times you only care
about 1 element in those structures, which actually would favor putting
them in separate arrays.
- Don
The new UCT code does something a little simpler and faster since there is
no need to take back moves.
David
*From:* computer-go-boun...@computer-go.org [mailto:
computer-go-boun...@computer-go.org] *On Behalf Of *Don Dailey
*Sent:* Friday, August 14, 2009 6:17 PM
*To:* computer-go
*Subject:* Re: [computer-go] representing liberties
I'm not sure I understand your question. But I'll try to explain it a
little better.
Basically, you keep a C structure or the equivalent which tracks each
individual chain. On your board array you put the index of that structure
(or a pointer to it.)
The structure will look something like this:
typedef struct
{
int color;
int stone_count;
int head_stone;
int liberty_count;
} chain_t;
And perhaps other crap you may want to keep.
So lets say you have an array of these, one for each chain on the board
with room to grow.
When you place a stone on the board, you look at the 4 neighbors to see if
this is going to be a new chain of 1, or connect to an existing chain.If
it's an existing chain, you will need to create a brand new entry, set the
stone_count to 1, the liberty count to 1, 2, 3 or 4 (by looking at the 4
surrounding points) and set the head_stone to the location of the new
stone.the head_stone can be ANY stone in the group - it's just a way to
quickly reference one of the stones in the group.
Your board of course will have the index of the chain_t.I start at 1
and make zero mean empty but you could use -1 to represent empty squares if
you want to. So if the value of the board array is 5, it means it is the
5th chain in the chain_t array and you can immediately see how many stones
are there, how many liberties etc.
The logic for updating the liberty count is pretty basic. When you place a
stone next to an existing group, you know that group loses 1 liberty, so
you subtract 1 from ANY group of either color that touches it (there can
only be 4 at most.) But then you must check to see if the stone you just
placed created liberties for the group it belongs to.So you count the
empty points around the new stone that do not already belong to that same
group. (There is also the case where 2 chains must be merged, but we
will ignore that for now.)
When a group is captured, you must do a bit more housekeeping. You need
to delete it's entry somewhow in the chain array and you will have to
recalculate the liberties for any enemy chain that is currently touching any
of the captured stones.This is not as hard as it seems once you work it
out.
One way to delete the entry is to just set the stone_count to zero for
instance. You may want to compress the chain list from time to time but
if you make the list big enough, you will be able to complete one or more
playouts without needing to do this. You could also keep a free list so
that you immediately re-use entries - that's probably what I would recommend
because it's real simple and the free list will never grow very large.
How do you unmake moves? I suggest that you don't. Instead, making a
move should either be by state copy, or if you know you will never need to
unmake a move (such as when doing fast playouts) you don't have to worry
about it.But of course you will still want to keep some original copy to
track the state of the actual game.
So your should wrap your whole game state up into a neat little package and
operate only on those. You will be thankful if you ever decide to go with
parallel processing for instance.
So to make a move you might have something like this in C, this is
non-object oriented version:
int make( const position *original_state, position *new_state,
move_type mv )
{
*new_state = *original_state;
status = low_level_make( new_state, mv );
return status;
}
The position object is a C structure that has the entire board, chain
lists and move history. The move history can be implemented as a pointer
to previous move states.
So in any kind of recursive search situation, you are simply passing
position states down the tree, never having to unmake a move.In the
playouts you don't even have to copy state
Re: [computer-go] representing liberties
On Fri, Aug 14, 2009 at 9:51 PM, David Fotland fotl...@smart-games.comwrote: Old Many Faces keeps linked lists of liberties for each group. They are sorted, singly linked lists, so merges are fast. Yes, I can see that merges would be really fast with linked lists. Are they common enough to make this really worth it though? I've never tried doing it this way. The new UCT code does not track liberties, just keeps a count, so to find a liberty takes a search over the points adjacent to the group. The stones in each group are in a linked list so this is not too slow. Even though you have a linked list don't you still have to test all the points around each stone in order to count liberties? Or do you have some kind of trick for doing this fast? - Don David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Carter Cheng Sent: Friday, August 14, 2009 2:16 PM To: computer-go@computer-go.org Subject: [computer-go] representing liberties I have been having difficulties selecting a good representation for liberty sets for strings of stones. I am curious how other people might be doing this. I suspect that for heavier playouts one would like to know not only the count of the liberties but also where precisely they might be relatively quickly(to determine if the group is in atari among other things). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
This idea makes much more sense to me than adjusting komi does.At least it's an attempt at opponent modeling, which is the actual problem that should be addressed. Whether it will actually work is something that could be tested. Another similar idea is not to pass but to play some percentage of random moves - which probably would work in programs with strong playout strategies. Of course this would be meaningless for bots that have weak (and already random) playout strategies. - Don On Thu, Aug 13, 2009 at 6:17 AM, Tapani Raiko pra...@cis.hut.fi wrote: I don't think the komi should be adjusted. Instead: Wouldn't random passing by black during the playouts model black making mistakes much more accurately? The number of random passes should be adjusted such that the playouts are close to 50/50. Adjusting the komi would make black play greedily, while random passing during playouts would make black play safe (rich men don't pick fights). Tapani Raiko Christoph Birk wrote: I think you got it the wrong way round. Without dynamic komi (in high ha ndicap games) even trillions of simulations with _not_ find a move that creates a winning line, because the is none, if the opponet has the same strength as you. WHITE has to assume that BLACK will make mistakes, otherwise there would be no handicap. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
On Thu, Aug 13, 2009 at 1:39 AM, Christoph Birk b...@ociw.edu wrote: On Aug 12, 2009, at 3:43 PM, Don Dailey wrote: I believe the only thing wrong with the current MCTS strategy is that you cannot get a statistical meaningful number of samples when almost all games are won or lost.You can get more meanful NUMBER of samples by adjusting komi, but unfortunately you are sampling the wrong thing - an approximation of the actual goal. Since the approximation may be wrong or right, your algorithm is not scalable. You could run on a billion processors sampling billions of nodes per seconds and with no flaw to the search or the playouts still play a move that gives you no chances of winning. I think you got it the wrong way round. Without dynamic komi (in high ha ndicap games) even trillions of simulations with _not_ find a move that creates a winning line, because the is none, if the opponet has the same strength as you. WHITE has to assume that BLACK will make mistakes, otherwise there would be no handicap. I'm not trying to define the problem - that has already been done and I agree with you - if the situation is hopeless the computer will play randomly regardless of the number of playouts. I'm explaining why this solution is imperfect and not scalable. I did not say it would make it play worse than nothing at all. - Don Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
There is one crude way to measure goal compatibility. See if you can make the same move work with different komi.If I'm on the east coast of the US traveling to the west coast, I will probably start off on the same road regardless of whether I'm going to Seattle or San Diego.If the same road does not work, then I'm facing a critical decision point. So it's probably safe to search for a move that works reasonable well with different komi. If you cannot do this, you probably have goals that are not compatible.But if you find a move that works well when the score is 50-50 (by manipulating the komi) then you should see if it's compatible with a tougher goal.This will at least be some evidence that you are looking at a common sense move and not a move that commits you to the wrong plan. But if you have a move that returns a really high score with one komi, but raising it up just a bit makes it drop to zero, you are in trouble with that move. Try to find a move that may not be quite as good in the first case, but is much better in the second case. Unfortunately, I don't think there is a simple way to implement this. Has anyone tried scoring where the total area was folded in to the main score, perhaps as much less signifant bits of the score?This makes winning big a secondary goal. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
2009/8/13 Stefan Kaitschick stefan.kaitsch...@hamburg.de Modeling the opponents mistakes is indeed an alternative to introducing komi. But it would have to be a lot more exact than simply rolling the dice or skipping a move here and there. Successful opponent modeling would implement the overplay school of thought - playing tactically refutable combinations that are beyond the opponents skill to punish them. I cannot believe you are being so technically precise about doing this correctly while advocating something on the other hand which is so obviously incorrect. You probably have something here though.I think the play-out policy is a more fruitful area to explore than dynamically changing komi. I would start simple, just trying the simplest approach first then gradually refining it. Random occasional pass moves is certainly easy to implement as a first step. - Don Introducing komi at the 50% win rate level would implement the honte school of thought - play as if against yourself. At a win rate of less than 50% it implements the almost honte school of thought. :-) I'm not trying to moralize. In love and go anything is fair. I'm just saying that while both approaches are legitimate, adjusting the komi is much easier to do. Different subject, suggestion for a komi adjustment scheme: 1. Make a regular evaluation(no extra komi) 2. If the win rate of the best move is within certain bounds you're done (Say between 30 and 70 percent.Just a guess ofcourse.Also, this might shift as the game progresses) 3. If not, make a komi adjustment dependant on how far out of bounds the win rate is. (No numerical suggestion here. Please experiment.) 4. Make a new search with this komi. 5. If the new result is in bounds calculate winrate_nokomi * factor + winrate_komi for each candidate and choose the highest one. (factor around 10 maybe) 6. If not, go back to 3 The idea is to choose a move that doesnt contradict the long term goal(no komi search) while trying for a short term goal(komi search) if no long term goal is available.( Or if every move satisfies the long term goal in case of taking handicap) Stefan - Original Message - *From:* Don Dailey dailey@gmail.com *To:* tapani.ra...@tkk.fi ; computer-go computer-go@computer-go.org *Sent:* Thursday, August 13, 2009 4:02 PM *Subject:* Re: [computer-go] Dynamic komi at high handicaps This idea makes much more sense to me than adjusting komi does.At least it's an attempt at opponent modeling, which is the actual problem that should be addressed. Whether it will actually work is something that could be tested. Another similar idea is not to pass but to play some percentage of random moves - which probably would work in programs with strong playout strategies. Of course this would be meaningless for bots that have weak (and already random) playout strategies. - Don On Thu, Aug 13, 2009 at 6:17 AM, Tapani Raiko pra...@cis.hut.fi wrote: I don't think the komi should be adjusted. Instead: Wouldn't random passing by black during the playouts model black making mistakes much more accurately? The number of random passes should be adjusted such that the playouts are close to 50/50. Adjusting the komi would make black play greedily, while random passing during playouts would make black play safe (rich men don't pick fights). Tapani Raiko Christoph Birk wrote: I think you got it the wrong way round. Without dynamic komi (in high ha ndicap games) even trillions of simulations with _not_ find a move that creates a winning line, because the is none, if the opponet has the same strength as you. WHITE has to assume that BLACK will make mistakes, otherwise there would be no handicap. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Tapani Raiko, tapani.ra...@tkk.fi, +358 50 5225750 http://www.iki.fi/raiko/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
2009/8/13 terry mcintyre terrymcint...@yahoo.com The dynamic komi is perhaps a misnomer; it's by accident that changing komi reflects something which we do want to measure, namely the predicted score. An algorithm which does not make use of the predicted score would not make use of all available information. You imply that it's some kind of travesty not to make use of available information, but the information is only available because you did extra work to generate it. And even if the information was free, it matters that you use it correctly. Just implying that it's wrong not to do this because you are throwing away available information is not going to cut it. On a 19x19 board, it is common for some areas to become settled; whether unconditionally alive, or ( more likely ) alive under the assumption of alternating play. Many moves trade the prospect of territory here versus there. Bad moves give up too much for too little. Good moves exploit bad or slack moves, and provide an equitable balance against good play. I think you have describe very well why dynamic komi is so hard. You take ALL these factors and ignore them all except for a single number. You don't know anything about the composition of that number.If your concern is about throwing away infromation, then dynamic komi should be a big problem for you. - Don Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* Don Dailey dailey@gmail.com *To:* computer-go computer-go@computer-go.org *Sent:* Thursday, August 13, 2009 9:27:11 AM *Subject:* Re: [computer-go] Dynamic komi at high handicaps 2009/8/13 Stefan Kaitschick stefan.kaitsch...@hamburg.de Modeling the opponents mistakes is indeed an alternative to introducing komi. But it would have to be a lot more exact than simply rolling the dice or skipping a move here and there. Successful opponent modeling would implement the overplay school of thought - playing tactically refutable combinations that are beyond the opponents skill to punish them. I cannot believe you are being so technically precise about doing this correctly while advocating something on the other hand which is so obviously incorrect. You probably have something here though.I think the play-out policy is a more fruitful area to explore than dynamically changing komi. I would start simple, just trying the simplest approach first then gradually refining it. Random occasional pass moves is certainly easy to implement as a first step. - Don Introducing komi at the 50% win rate level would implement the honte school of thought - play as if against yourself. At a win rate of less than 50% it implements the almost honte school of thought. :-) I'm not trying to moralize. In love and go anything is fair. I'm just saying that while both approaches are legitimate, adjusting the komi is much easier to do. Different subject, suggestion for a komi adjustment scheme: 1. Make a regular evaluation(no extra komi) 2. If the win rate of the best move is within certain bounds you're done (Say between 30 and 70 percent.Just a guess ofcourse.Also, this might shift as the game progresses) 3. If not, make a komi adjustment dependant on how far out of bounds the win rate is. (No numerical suggestion here. Please experiment.) 4. Make a new search with this komi. 5. If the new result is in bounds calculate winrate_nokomi * factor + winrate_komi for each candidate and choose the highest one. (factor around 10 maybe) 6. If not, go back to 3 The idea is to choose a move that doesnt contradict the long term goal(no komi search) while trying for a short term goal(komi search) if no long term goal is available.( Or if every move satisfies the long term goal in case of taking handicap) Stefan - Original Message - *From:* Don Dailey dailey@gmail.com *To:* tapani.ra...@tkk.fi ; computer-go computer-go@computer-go.org *Sent:* Thursday, August 13, 2009 4:02 PM *Subject:* Re: [computer-go] Dynamic komi at high handicaps This idea makes much more sense to me than adjusting komi does.At least it's an attempt at opponent modeling, which is the actual problem that should be addressed. Whether it will actually work is something that could be tested. Another similar idea is not to pass but to play some percentage of random moves - which probably would work in programs with strong playout strategies. Of course this would be meaningless for bots that have weak (and already random) playout strategies. - Don On Thu, Aug 13, 2009 at 6:17 AM, Tapani Raiko pra...@cis.hut.fi wrote: I don't think the komi should be adjusted. Instead: Wouldn't random passing by black during the playouts model black making mistakes much more accurately? The number of random passes should be adjusted
Re: [computer-go] new kid on the block
Yes, known problem :-( I'm still trying to find a method to see if a point is in an eye. Should not be too difficult in theory but in practice i have not found a method yet. Are you talking about 1 point eyes? For this I think most programs use the same definition, which is quite good and safe. As far as I know there is no perfect rule but this is close to perfect. The definition of an eye we use is this: An empty point whose direct neighbors are all of the same color AND whose diagonal neighbors contain no more than 1 stone of the opposite color. This definition must be modified slightly if the point in question is on the edge of the board - in which case there must be NO diagonal enemy stones. To know if a point is inside a bigger eye - that's much more speculative I think. - Don -- Multi tail barnamaj mowahib li mora9abat attasjilat wa nataij awamir al 7asoub. damj, talwin, mora9abat attarchi7 wa ila akhirih. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
2009/8/12 Ingo Althöfer 3-hirn-ver...@gmx.de In the last few weeks I have experimented a lot with dynamic komi in games with high handicap. Especially, I used the really nice commercial program Many Faces of Go (version 12.013) with its Monte Carlo level (about 2 kyu on 19x19 board) and its traditional 18-kyu level as the opponent. At handicap 21 I played (manulally!) 8 games with these opponents: 4 games with static komi (0.5) - here MFoG (2-kyu) won 1 of the 4 games. 4 games with dynamic komi - here MFoG (2-kyu) won 3 of the 4 games. I used dynamic komi in the following Rule 42 way. Starting point for this internal artificial komi was a very high value (to compensate for the handicap stones), typically 300.5 or 320.5 . Then, always when the evaluation had climbed up to 42 % or higher, dynamic komi was reduced by 50 or 30 or 20 (or 10 near the end), until finally the true value of 0.5 was reached. After this little sample I also tried a few games with dynamic komi at handicap 25. After some unsuccessful games (the Monte Carlo side died of starvation at komi=40.5 or 30.5) today one win came out: In best Monte Carlo fashion, the MC-level won by half a point. I have included sgf of this game. I am aware that small samples are not enough to prove something. Therefore, I hope that programmers may realize automatic versions of something like Rule 42 to find out how their programs behave with dynamic komi. The small samples is probably the least of the problems with this. Do you actually believe that you can play games against it and not be subjective in your observations or how you play against it? - Don Ingo. -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
Ok, I misunderstood his testing procedure. What he is doing is far more scientific than what I thought he was doing. There has got to be something better than this. What we need is a way to make the playouts more meaningful but not by artificially reducing our actual objective which is to win. For the high handicap games, shouldn't the goal be to maximize the score? Instead of adjusting komi why not just change the goal to win as much of the board as possible?This would be far more honest and reliable I would think and the program would not be forced to constantly waste effort on constantly changing goals. - Don On Wed, Aug 12, 2009 at 3:33 PM, Brian Sheppard sheppar...@aol.com wrote: The small samples is probably the least of the problems with this. Do you actually believe that you can play games against it and not be subjective in your observations or how you play against it? These are computer-vs-computer games. Ingo is manually transferring moves between two computer opponents. The result does support Ingo's belief that dynamic Komi will help programs play high handicap games. Due to small sample size it isn't very strong evidence. But maybe it is enough to induce a programmer who actually plays in such games to create a more exhaustive test. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
The problem with MCTS programs is that they like to consolidate. You set the komi and thereby give them a goal and they very quickly make moves which commit to that specific goal. Commiting to less than you need to actually win will often involve sacrificing chances to win.Sometime it won't, but you cannot have a scalable algorithm which is this arbitrary. However, if the handicap is too high, the program thinks every line is a loss and it plays randomly. That's why we even consider doing this. Dynamically changing komi could be of some benefit in that situation if there is no alternative reasonable strategy, but it does not address the real problem - which is what I call the committal consolidation problem. You are giving the program an arbitrary short term goal which may, or may not be compatible with the long term goal of winning the game. Whether it's compatible or not is based on your own credulity - not anything predictible or that you can scale. And as the base program gets stronger this aspect of the program becomes more and more of a wart. If this can be made to work in the short term, it should be considered a temporary hack which should be fixed as soon as possible. We have to think about this anyway sooner or later because if programs continue to develop and the predictive ability of the playouts and tree search gets several hundred ELO better, these programs may start to see more and more positions as either dead won or dead lost. I'm sure we will want some kind of robust mechanism for dealing with this which is better at estimating chances that the opponent will go wrong as opposed to doing something that is a random benefit or hindrance. - Don 2009/8/12 terry mcintyre terrymcint...@yahoo.com Ingo suggested something interesting - instead of changing the komi according to the move number, or some other fixed schedule, it varies according to the estimated winrate. It also, implicitly, depends on one's guess of the ability of the opponent. An interesting test would be to take an opponent known to be weaker, offer it a handicap, and tweak the dynamic komi per Ingo's suggestion. At what handicap does the ratio balance at 50:50? Can the number of handicap stones be increased with such an adaptive algorithm? Even better, play against a stronger opponent; can one increase the win rate versus strong opponents? The usual range of computer opponents is fairly narrow. None approach high-dan levels on 19x19 boards - yet. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* Brian Sheppard sheppar...@aol.com *To:* computer-go@computer-go.org *Sent:* Wednesday, August 12, 2009 12:33:13 PM *Subject:* [computer-go] Dynamic komi at high handicaps The small samples is probably the least of the problems with this. Do you actually believe that you can play games against it and not be subjective in your observations or how you play against it? These are computer-vs-computer games. Ingo is manually transferring moves between two computer opponents. The result does support Ingo's belief that dynamic Komi will help programs play high handicap games. Due to small sample size it isn't very strong evidence. But maybe it is enough to induce a programmer who actually plays in such games to create a more exhaustive test. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
Terry, I understand the reasoning behind this, your thought experiment did not add anything to my understanding. And I agree that if the program is strong enough and the handicap is high enough this is probably better than doing nothing at all. However, I think there must be something that is more along the lines of treating the disease, not the symptoms.You might be able to put a band aid on the problem but you have not addressed the real issue in a systematic way. Besides, I have not yet seen anyone demonstrate that this works - it's always talked about but never implemented.It is made to sound so simple that you have to wonder where the implementation is and why the strong programs do not have it. - Don 2009/8/12 terry mcintyre terrymcint...@yahoo.com Consider this thought experiment. You sit down at a board and your opponent has a 9-stone handicap. By any objective measure of the game, you should resign immediately. All your win-rate calculations report this hopeless state of affairs. Winrate gives you no objective basis to prefer one move or another. But, you think, what if I can make a small group? What if I try for a lesser goal, such as don't lose by more than 90 points? Your opponent has a 9 stone handicap because he makes more mistakes than you do. As the game progresses, those mistakes add up. You set your goal higher - losing by only 50 points; losing by only 10 points. The changing goal permits you to discriminate in a field which would otherwise look like a dark, desolate, win-less landscape. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* Don Dailey dailey@gmail.com *To:* computer-go computer-go@computer-go.org *Sent:* Wednesday, August 12, 2009 1:05:36 PM *Subject:* Re: [computer-go] Dynamic komi at high handicaps Ok, I misunderstood his testing procedure. What he is doing is far more scientific than what I thought he was doing. There has got to be something better than this. What we need is a way to make the playouts more meaningful but not by artificially reducing our actual objective which is to win. For the high handicap games, shouldn't the goal be to maximize the score? Instead of adjusting komi why not just change the goal to win as much of the board as possible?This would be far more honest and reliable I would think and the program would not be forced to constantly waste effort on constantly changing goals. - Don On Wed, Aug 12, 2009 at 3:33 PM, Brian Sheppard sheppar...@aol.comwrote: The small samples is probably the least of the problems with this. Do you actually believe that you can play games against it and not be subjective in your observations or how you play against it? These are computer-vs-computer games. Ingo is manually transferring moves between two computer opponents. The result does support Ingo's belief that dynamic Komi will help programs play high handicap games. Due to small sample size it isn't very strong evidence. But maybe it is enough to induce a programmer who actually plays in such games to create a more exhaustive test. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
On Wed, Aug 12, 2009 at 5:36 PM, Mark Boon tesujisoftw...@gmail.com wrote: I started to write something on this subject a while ago but it got caught up in other things I had to do. When humans play a (high) handicap game, they don't estimate a high winning percentage for the weaker player. They'll consider it to be more or less 50-50. So to adjust the komi at the beginning of the game such that the winning percentage becomes 50% seems a very reasonable idea to me. This is what humans do too, they'll assume the stronger player will be able to catch up a certain number of points to overcome the handicap. I disagree about this being what humans do. They do not set a fake komi and then try to win only by that much. I think their model is somewhat incremental, trying to win a bit at a time but I'm quite convinced that they won't just let the opponent consolidate like MCTS does. With dynamic komi the program will STILL just try to consolidate and not care about what his opponent does. But strong players will know that letting your opponent consolidate is not going to work.So they will keep things complicated and challenge their weaker opponents everywhere that is important. - Don What seems difficult to me however is to devise a reasonable way to decrease this komi as the game progresses. In an actual game the stronger player catches up in leaps and bounds, not smoothly. In MC things are not always intuitive though. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
2009/8/12 terry mcintyre terrymcint...@yahoo.com Most experiments are done on even games; this dynamic algorithm applies particularly to handicap games.In that context, it is not an ungainly kludge, but actually reflects the assessment of evenly matched pro players - they look at the board, and see a victory of n times 10 handicap stones ( or something roughly comparable ) for black. This matters because today's programs are not even close to playing at the pro level; to win respect, they'll have to master handicap games - and to do that, they'll need to do two things. First, they'll need to model the expectation that black with a handicap _should_ win big. Second, they'll need to behave gracefully as that initial advantage is whittled down. I disagree. I think strong players have a sense of what kind of mistakes to expect, and try to provoke those mistakes. Dynamic komi does not model that. It also does the opposite of making the program play provocatively, which I believe is necessary to beat a weaker player with a large handicap against you.Instead of making it fight, it encourages the program to be content with less. How does this model strong handicap players? - Don Existing programs don't do either of those two things well. They're tuned toward even-game strategy. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
On Wed, Aug 12, 2009 at 5:58 PM, Mark Boon tesujisoftw...@gmail.com wrote: 2009/8/12 Don Dailey dailey@gmail.com: I disagree about this being what humans do. They do not set a fake komi and then try to win only by that much. I didn't say that humans do that. I said they consider their chance 50-50. For an MC program to consider its chances to be 50-50 you'd have to up the komi. There's a difference. If the handicap is fair, their chance is about 50/50. However, rigging komi to give the same chance is NOT what humans do. The only thing you said that I consider correct is that humans estimate their chances to be about 50/50. One thing humans do is to set short term goals and I think dynamic komi is an attempt to do that - but it's a misguided attempt because you are setting the WRONG short term goal. The human will have a much more specific goal that is going to be compatible with his hope of winning the game.For instance I am sure he will not sit merrily by and watch his opponent consolidate a won game just so that he can have a respectable but losing score.Dynamic komi of course does not address that at all. I think their model is somewhat incremental, trying to win a bit at a time but I'm quite convinced that they won't just let the opponent consolidate like MCTS does. With dynamic komi the program will STILL just try to consolidate and not care about what his opponent does. But strong players will know that letting your opponent consolidate is not going to work. So they will keep things complicated and challenge their weaker opponents everywhere that is important. It's difficult to make hard claims about this. I don't agree at all that the stronger player constantly needs to keep things complicated. Personally I tend to play solidly when giving a handicap. Because most damage is self-inflicted. You can either make a guess what the weaker player doesn't know, or you can give him the initiative and he'll show you. I prefer the latter approach. When done properly, I don't see how an MCTS program would consolidate all the time. Doing so would keep the position stable while the komi declines. As soon as he gets behind the komi degradation curve play will automatically get more dynamic in an attempt to catch up. The problem is: we're speculating. The proof is in the pudding. Agreed. - Don Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
On Wed, Aug 12, 2009 at 6:03 PM, Matthew Woodcraft matt...@woodcraft.me.ukwrote: Don Dailey wrote: The problem with MCTS programs is that they like to consolidate. You set the komi and thereby give them a goal and they very quickly make moves which commit to that specific goal. How did you form this opinion? Can you show an example game record (on 19x19) showing this behaviour? Your kidding, right?Does anyone honestly dispute this? I'm certainly not going to entertain this with examples - if you don't understand this I'm sure we would waste a dozen emails arguing about it regardless of what I could show you. - Don -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi at high handicaps
2009/8/12 Stefan Kaitschick stefan.kaitsch...@hamburg.de What a bot does with its playouts in a handicap situation is to essentially try to beat itself, despite the handicap. And in this situation the bot reacts in a very human way, it becomes despondend. Adjusting the komi dynamically shifts the goal from winning to catching up quickly enough. I think that is the problem though. You have only 1 thing you can control, how to set the komi before doing the search.But how the program deals with your artificial (and crude) setting is unpredictable. What you really need is some kind of way to tell it to try to win some territory, but not spoil your chances of winning a bit more later. It's easier to win N points if you know in advance that you will not be asked later to win N more points.And I'm afraid that is what will happen all too often - the program will maximize it's chances of winning N, but this does not always translate directly into winning N plus MORE. I feel that that is the natural handicap strategy, not a band-aid. It's a scalability issue, which is why I call it a band-aid. It's not natural because it's an artificial goal, not a natural one and certainly not the ACTUAL goal, which is to win the game. Do you want to win N points, or do you want to win the game?And we all KNOW that it will try to maximize it's chances of winning N points, regardless of the consequences beyond that. You would never ask a runner to stop 50 feet short of the finish line, then ask him to go 10 feet more, and so on. The runner plans his strategy based on the actual distance run and anything else would change his pacing strategy in a bad way. If the program makes decisions about the best way to win N points, there is no guarantee that this is ALSO the best way to win N+1 points. This is the implicit assumption in this strategy, that the best way to win with ANY komi is the same and that the same moves are just as good no matter what. In fact the more you must win by, the more chances you must take. I believe the only thing wrong with the current MCTS strategy is that you cannot get a statistical meaningful number of samples when almost all games are won or lost.You can get more meanful NUMBER of samples by adjusting komi, but unfortunately you are sampling the wrong thing - an approximation of the actual goal. Since the approximation may be wrong or right, your algorithm is not scalable. You could run on a billion processors sampling billions of nodes per seconds and with no flaw to the search or the playouts still play a move that gives you no chances of winning. - Don Ofcourse, the dynamic komi must be adjusted down to zero in good time. I think there are 2 main reasons that this hasnt been fully explored sofar. 1. Trying to maximize the score turned out to be a huge mistake, compared to trying to maximize the winrate. This makes dynamic komi a kind of blind spot. 2. Handicap go wasnt given special attention sofar. Stefan - Original Message - *From:* Don Dailey dailey@gmail.com *To:* computer-go computer-go@computer-go.org *Sent:* Wednesday, August 12, 2009 11:24 PM *Subject:* Re: [computer-go] Dynamic komi at high handicaps Terry, I understand the reasoning behind this, your thought experiment did not add anything to my understanding. And I agree that if the program is strong enough and the handicap is high enough this is probably better than doing nothing at all. However, I think there must be something that is more along the lines of treating the disease, not the symptoms.You might be able to put a band aid on the problem but you have not addressed the real issue in a systematic way. Besides, I have not yet seen anyone demonstrate that this works - it's always talked about but never implemented.It is made to sound so simple that you have to wonder where the implementation is and why the strong programs do not have it. - Don 2009/8/12 terry mcintyre terrymcint...@yahoo.com Consider this thought experiment. You sit down at a board and your opponent has a 9-stone handicap. By any objective measure of the game, you should resign immediately. All your win-rate calculations report this hopeless state of affairs. Winrate gives you no objective basis to prefer one move or another. But, you think, what if I can make a small group? What if I try for a lesser goal, such as don't lose by more than 90 points? Your opponent has a 9 stone handicap because he makes more mistakes than you do. As the game progresses, those mistakes add up. You set your goal higher - losing by only 50 points; losing by only 10 points. The changing goal permits you to discriminate in a field which would otherwise look like a dark, desolate, win-less landscape. Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop
Re: Superko vs transposition table (was Re: [computer-go] Double/Triple Ko situation)
On Fri, Aug 7, 2009 at 5:51 AM, Folkert van Heusden folk...@vanheusden.comwrote: What is superko? My program keeps a list of all board-positions and then if it whants to do a move it checks if the new board-position is in the list. If so, it throws that move away. Are there other checks I need to do as well? Superko involves repeating a previous board position. Various forms of this are forbidden by various rulesets, see http://www.britgo.org/rules/compare.html#threeKK What you are doing ensures that your program will never violate any form of the rule. Ah ok! Odd is though that CGOS complains about Illegal KO attempted. Many time CGOS has been accused of calling a move illegal that wasn't - due to the KO rule. But so far it has never once been wrong when closely inspected. So I challenge you to show me a position where CGOS got this rule wrong! I'll give you a small monetary prize if you can :-)Just give the CGOS game number. Please note that the KO rule CGOS uses does NOT consider side to move. For example if the same exact board configuration repeats that has occurred previously, it is a positional superko violation regardless of which color is to move. Note that this is different than repetition in chess, where the same side must be on the move before consider the position as repeated. Also please note that when you play go there are other ways to define what a KO violation is. Players must agree to use the same rules when you sit down to play any game.CGOS uses the positional superko KO rule but it's also possible to play a game of go with the situational superko rule defined - which DOES take into consider the side to move. You can find disscussions on situational vs positional superko in the archives and on the web in other places - essentially there are some who feel the situational rule is more correct and more fundamental. I agree and I consider positional superko a slight complication (although by definition it is slighly simpler.) However, even though I feel that way, I chose positional superko for CGOS because I think it is more standard and accepted. - Don Folkert van Heusden -- Multitail es una herramienta flexible que permite visualizar los log file y seguir la ejecución de comandos. Permite filtrar, añadir colores, combinar archivos, la visualización de diferencias (diff- view), etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] matching 2 engines with sanity checks
It's pretty easy to add this test to the client - there is an object oriented package in the cgos code called gogame which follows a game and reports any illegal moves.Just cut and paste it to client and when a new game is started create a new game object, and use the object to verify the moves as they are made. It will report errors and is exactly what cgos does. - Don On Tue, Aug 4, 2009 at 4:17 PM, Folkert van Heusden folk...@vanheusden.comwrote: Yes, that's it. Checks if an engine does an illegal ko, puts a piece where already is a piece, etc. On Tue, Aug 04, 2009 at 04:15:18PM -0400, Joshua Shriver wrote: What do you mean by sanity checks? Such as legal moves? I wrote a chess engine vs engine app, could gut and reuse it for go and possible add legal move checking to it. -Josh On Mon, Aug 3, 2009 at 4:39 AM, Folkert van Heusden folk...@vanheusden.comwrote: Hi, CGOS does sanity checks on the moves played by the engines that are matched. Problem is that it might take a few hours before bugs get triggered (due to scheduling of matches). GoGui can let an engine play against itself and then does also does sanity-checks but it is possible that certain bugs in an engine won't get triggered. So I was wondering: are there any other tools available for matching engines WITH validity-checks? Folkert van Heusden -- MultiTail è uno flexible tool per seguire di logfiles e effettuazione di commissioni. Feltrare, provedere da colore, merge, 'diff-view', etc. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Folkert van Heusden -- MultiTail cok yonlu kullanimli bir program, loglari okumak, verilen kommandolari yerine getirebilen. Filter, renk verme, merge, 'diff- view', vs. http://www.vanheusden.com/multitail/ -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Finding specific CGOS game
Here are last few games of Pebbles where pebbles lost on time as black - which is what would happen in a crash. Pebbles is losing a lot of games on time. 794069|gnugo-3.7.12-l10F|1759|Pebbles|2155|2009-06-23 12:51|23130|306264|W+Time|y 796644|fuego-0.4-slow|2050|Pebbles|2144|2009-06-28 07:21|213889|314234|W+Time|y 797185|Nomitan_010|2099|Pebbles|2145|2009-06-29 05:25|166424|457572|W+Time|y 798339|fuego-0.4-slow|2062|PebblesToo|2120|2009-07-01 10:00|285864|300965|W+Time|y 800546|Aya681_1sim|2260|PebblesToo|2144|2009-07-05 07:03|42305|307156|W+Time|y 803518|Aya681_1sim|2245|Pebbles|2209|2009-07-09 22:44|8332|302132|W+Time|y 804223|Nomitan_tanabata|2102|Pebbles|2221|2009-07-11 06:16|286093|365965|W+Time|y 805600|PebblesToo|2210|Pebbles|2234|2009-07-13 06:08|156681|313945|W+Time|y 809161|fuego-0.4-slow|2015|PebblesToo|2257|2009-07-17 09:13|269777|300240|W+Time|y 811229|lingo-B5.10|2116?|Pebbles|2259|2009-07-19 02:55|174175|303600|W+Time|y 811242|fuego-0.4-slow|2002|PebblesToo|2227|2009-07-19 03:04|0|312380|W+Time|y 813140|gnugo-3.7.12-mc|1940|PebblesToo|2204|2009-07-20 14:26|0|314432|W+Time|y 813727|UmeBot-1b|1433|Pebbles|2226|2009-07-21 00:42|116508|305905|W+Time|y 816181|Fuego4C4PlaPo20Mno|2395|PebblesToo|2205|2009-07-22 21:10|0|314367|W+Time|y 819178|Aya681_1sim|2194|Pebbles|2223|2009-07-25 01:51|17213|300872|W+Time|y 820646|GnuGo-mc-10K-lev11|2013|PebblesToo|2195|2009-07-26 01:57|56697|306864|W+Time|y 821628|GG-500|1738|Pebbles|2210|2009-07-26 17:41|6380|310153|W+Time|y 823871|TakeRaveGom_ct1_15|2074?|PebblesToo|2186|2009-07-28 04:44|260261|308616|W+Time|y 824478|gnugo-3.7.12-mc|1899|Pebbles|2211|2009-07-28 15:35|164822|303483|W+Time|y 824905|Fuego4C4PlaPo20Mno|2375|PebblesToo|2190|2009-07-28 22:40|148900|306979|W+Time|y 824920|TakeRaveGom_ct1_15|2081|Pebbles|2200|2009-07-28 22:50|0|301031|W+Time|y 825424|GnuGo-mc-10K-lev11|2020|PebblesToo|2189|2009-07-29 07:04|276431|301032|W+Time|y 825563|Pebbles|2194|PebblesToo|2183|2009-07-29 09:27|232670|302187|W+Time|y 830994|GnuGo-mc-10K-lev11|1977|PebblesToo|2191|2009-08-02 07:05|255392|303189|W+Time|y On Sun, Aug 2, 2009 at 10:52 AM, Brian Sheppard sheppar...@aol.com wrote: Is there any way to find a specific game played on CGOS yesterday? Pebbles crashed overnight, and I would like to know what game it was playing. I know it was started around 2:54 am (Eastern US time), PebblesToo as black against GnuGo-mc-10K-lev11. Thanks, Brian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Finding specific CGOS game
I only showed black games because you said pebbles was black. - Don On Sun, Aug 2, 2009 at 1:27 PM, Christoph Birk b...@ociw.edu wrote: On Aug 2, 2009, at 8:05 AM, Don Dailey wrote: Here are last few games of Pebbles where pebbles lost on time as black - which is what would happen in a crash. Pebbles is losing a lot of games on time. And all of them as black. 794069|gnugo-3.7.12-l10F|1759|Pebbles|2155|2009-06-23 12:51|23130|306264|W+Time|y 796644|fuego-0.4-slow|2050|Pebbles|2144|2009-06-28 07:21|213889|314234|W+Time|y 797185|Nomitan_010|2099|Pebbles|2145|2009-06-29 05:25|166424|457572|W+Time|y 798339|fuego-0.4-slow|2062|PebblesToo|2120|2009-07-01 10:00|285864|300965|W+Time|y 800546|Aya681_1sim|2260|PebblesToo|2144|2009-07-05 07:03|42305|307156|W+Time|y 803518|Aya681_1sim|2245|Pebbles|2209|2009-07-09 22:44|8332|302132|W+Time|y 804223|Nomitan_tanabata|2102|Pebbles|2221|2009-07-11 06:16|286093|365965|W+Time|y 805600|PebblesToo|2210|Pebbles|2234|2009-07-13 06:08|156681|313945|W+Time|y 809161|fuego-0.4-slow|2015|PebblesToo|2257|2009-07-17 09:13|269777|300240|W+Time|y 811229|lingo-B5.10|2116?|Pebbles|2259|2009-07-19 02:55|174175|303600|W+Time|y 811242|fuego-0.4-slow|2002|PebblesToo|2227|2009-07-19 03:04|0|312380|W+Time|y 813140|gnugo-3.7.12-mc|1940|PebblesToo|2204|2009-07-20 14:26|0|314432|W+Time|y 813727|UmeBot-1b|1433|Pebbles|2226|2009-07-21 00:42|116508|305905|W+Time|y 816181|Fuego4C4PlaPo20Mno|2395|PebblesToo|2205|2009-07-22 21:10|0|314367|W+Time|y 819178|Aya681_1sim|2194|Pebbles|2223|2009-07-25 01:51|17213|300872|W+Time|y 820646|GnuGo-mc-10K-lev11|2013|PebblesToo|2195|2009-07-26 01:57|56697|306864|W+Time|y 821628|GG-500|1738|Pebbles|2210|2009-07-26 17:41|6380|310153|W+Time|y 823871|TakeRaveGom_ct1_15|2074?|PebblesToo|2186|2009-07-28 04:44|260261|308616|W+Time|y 824478|gnugo-3.7.12-mc|1899|Pebbles|2211|2009-07-28 15:35|164822|303483|W+Time|y 824905|Fuego4C4PlaPo20Mno|2375|PebblesToo|2190|2009-07-28 22:40|148900|306979|W+Time|y 824920|TakeRaveGom_ct1_15|2081|Pebbles|2200|2009-07-28 22:50|0|301031|W+Time|y 825424|GnuGo-mc-10K-lev11|2020|PebblesToo|2189|2009-07-29 07:04|276431|301032|W+Time|y 825563|Pebbles|2194|PebblesToo|2183|2009-07-29 09:27|232670|302187|W+Time|y 830994|GnuGo-mc-10K-lev11|1977|PebblesToo|2191|2009-08-02 07:05|255392|303189|W+Time|y Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] new kid on the block
I think the problem is yours, there is no known problem anything like this in Ggogui and I have been using it for a long time. Is your notation correct? In Go there is no 'i' file, we go from h to j skipping i.You may already know that of course if you are a go player but it still leads to bugs if you don't code it correctly. I would say for sure that if gogui says you are playing to an occupied point that you are. Could it be that captures are somehow being handled incorrectly? - Don On Thu, Jul 30, 2009 at 9:45 AM, Folkert van Heusden folk...@vanheusden.com wrote: Welcome. :) thanks! Consider implementing GTP so that your program can be used with nice GUIs such as GoGui. Got problems using GoGui: after a few moves (mostly after around 30 moves) GoGui says Stop played on a non-empty point. But I verified both in the logging of my program (which is called 'Stop') and in the logging of GoGui itself (Tools - Save Log) that no moves are repeated. Using GoGui 1.1.10. Can it be a known problem? Folkert van Heusden -- -- Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Mirror Go against Zen
How is the center point handled?I assume it plays to the center point as black and with either color it just ignores the center point in the symetry calculations, right? So if it's playing white, symmetry is broken as soon as white plays to the center because it cannot play a move that creates a symmetrical position (ignoring the center point.) Is all of that correct? - Don 2009/7/23 Gunnar Farnebäck gun...@lysator.liu.se Ingo Althöfer wrote: Alain Baeckeroot wrote: gnugo --mirror will try to play mirror go :) How does it do this? In the simplest possible way. If there is a legal move obtaining mirror symmetry it will play it, otherwise revert to normal move generation. It does not worry about komi, nor about tactical disasters. As you may guess this was primarily implemented in order to test the anti-mirror-go strategies in GNU Go. /Gunnar ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Mirror Go against Zen
2009/7/22 Andrés Domínguez andres...@gmail.com 2009/7/20 Stefan Kaitschick stefan.kaitsch...@hamburg.de: Ofcourse they can know. They just have to check for it. Those programs that do well against mirror go probably all do check for it. I think a strong MCTS could find the lines that make mirror Go useless. Maybe MF plays lines that brake mirror or related capture races because this lines have more probability of winning. I don't know if there is any evidence that MFGO plays this any better than ZEN, unless it's stronger than ZEN in general. If MFGO is stronger than Zen, then it should be no surprise. Otherwise ... In order for this to be scientific, you need a reasonable number of game examples.I can imagine that a program could look very foolish in one game, then brilliant in another and this might be totally dependent on whether it blundered into the right kind of position where the normal algorithm would punish the mirror play. So what is the basis for saying that MFGO easily handles this and Zen is totally clueless about mirror go? It could be true, but is there anything more than anecdotal evidence? - Don Andrés ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Mirror Go against Zen
It could be a matter of style as you say, not a matter of strength.My main questions is whether it's been established as true that Zen really plays poorly and Many Faces is brilliant against mirror go.Or does it just seem that way based on casual observation? The only reason I make an issue out of this is that it has happened to me many times, where I think I see a trend or a pattern based on a few games but it turns out to be just my imagination or low sample size. Humans have wonderful pattern recognition, but it's well know that we easily find patterns where they don't exist too. In high school I played a game of chess with this guy and happened to win and everyone assumed that I was better as a result of that game.But I remembered the game as a difficult one that could have gone either way. That one observation caused people to draw firm conclusions. In fact this happens all the time - Kasparov - Deep Blue proved that computers were now better than the best players (based on 4 games and a HUGE statistical margin of error.) Anyway, I don't dispute this (I have no idea if it's true or false), but it's an interesting enough problem or situation that I think we should know if we are on solid ground before speculating about why one program handles this and another doesn't. Can we assume that both programs are approximately equal or is MFGO clearly stronger (or visa versa?) - Don On Wed, Jul 22, 2009 at 6:49 PM, Darren Cook dar...@dcook.org wrote: But go programs do not KNOW they are playing mirror go and would have no motivation to specifically set this up. So how is it that some equally strong programs have no problem while others do? I wondered if some programs prefer contact moves more? In which case the chances of them attaching to the central stone are higher. Ingo's example game against Many Faces shows how playing mirror go religiously to the end becomes suicidal. Are the people playing mirror go against Zen on KGS breaking off the mirroring before falling into these traps? (It can be late, e.g. black 161, filling the liberty of a group that doesn't have two eyes yet, was the obvious point to stop, but even playing black 163 at N11 would have been in time.) Darren -- Darren Cook, Software Researcher/Developer http://dcook.org/gobet/ (Shodan Go Bet - who will win?) http://dcook.org/mlsn/ (Multilingual open source semantic network) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mirror Go against Zen
I thought you played mirror go as white? I'm not a go player, but it seems like it would be hard to win if you had the white pieces with 0.5 komi and black mirrored everything you did.You essentially start from a losing position anyway, right? Does the human play to the center on the first move and thereafter mirror everything? - Don On Mon, Jul 20, 2009 at 8:40 AM, Ingo Althöfer 3-hirn-ver...@gmx.dewrote: On KGS, some humans players (yakuman, finnes) now have started to play mirror go against Zen19 (Humans as Black; komi=+0.5). So far Zen19 seems to react helpless. In contrast, commercial versions of ManyFaces and Leela seem to have (almost) no problems with mirror go. Ingo. -- Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla Firefox 3 - sicherer, schneller und einfacher! http://portal.gmx.net/de/go/chbrowser ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Mirror Go against Zen
Again, I don't understand go so well, but how do you win against mirror go? It seems you must either take advantage somehow of the non-symmetry of the center point OR take advantage of the fact that a capture could break the symmetry. Is that right? If it's by capture it seems that since you will get the make the capture first, you could win by making sure this capture spoiled your opponent mirror capture. Is that the basic strategy or is there more? - Don On Mon, Jul 20, 2009 at 9:14 AM, Ingo Althöfer 3-hirn-ver...@gmx.dewrote: Don Dailey wrote: I thought you played mirror go as white? Or with Black, starting in center. It is possible when komi is only 0.5 and chinese scoring. I'm not a go player, but it seems like it would be hard to win if you had the white pieces with 0.5 komi and black mirrored everything you did.You essentially start from a losing position anyway, right? Right. But Many Faces and Leela manage to win with White in this situation (in several board sizes). Does the human play to the center on the first move and thereafter mirror everything? Right. Very boring. Ingo -- Neu: GMX Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate für nur 19,99 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Mirror Go against Zen
Ok, so I am right about this, you take advantage of the asymmetry of captures. But go programs do not KNOW they are playing mirror go and would have no motivation to specifically set this up. So how is it that some equally strong programs have no problem while others do? - Don On Mon, Jul 20, 2009 at 9:48 AM, Seo Sanghyeon sanx...@gmail.com wrote: 2009/7/20 Don Dailey dailey@gmail.com: Again, I don't understand go so well, but how do you win against mirror go? You setup two ladders that collide. -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] gtp which version to implement?
On Wed, Jul 15, 2009 at 9:41 AM, Carter Cheng carter_ch...@yahoo.comwrote: Where can I find information on these bridging protocols or are libraries provided for this (to the 9x9 19x19 servers)? The CGOS protocol is pretty easy to decode from the cgos client script which is written in TCL. Even if you don't know tcl you can learn the protocol easily from the script. However, there is no need to know the CGOS protocol if your engine speaks GTP. GTP is designed to be a universal protocol for GO engines - if your engine knows GTP it should be able to use all kinds of tool including GOGUI, a nice user interface for GO programs. The cgos client program speaks to the server in it's language and to your program using GTP. See how simple life can be? The CGOS protocol is about to change just slightly as I will be soon upgrading the server, but an updated client will be provided so that will require no change on your part. (And the old CGOS prototol will still work but with some restrictions.) - Don --- On Wed, 7/15/09, Hellwig Geisse hellwig.gei...@mni.fh-giessen.de wrote: From: Hellwig Geisse hellwig.gei...@mni.fh-giessen.de Subject: Re: [computer-go] gtp which version to implement? To: computer-go computer-go@computer-go.org Date: Wednesday, July 15, 2009, 2:44 AM On Wed, 2009-07-15 at 11:24 +0200, Urban Hafner wrote: Carter Cheng wrote: Thanks everyone for the help thus far. I have been looking at the GTP protocol page and I am curious which version of the protocol I should try to implement if I want to communicate with the servers. Should I be looking at the GTP 2.0 draft version? You should implement (part of) the draft. It's widely used nowadays. I'm not sure if there's any server out there that uses the old version. Just to be clear on this point: GTP is not a server protocol, but a protocol between a controller and an engine. If you want the engine to connect to a server, there is still a bridge needed, which communicates with the engine through GTP and with the server through whatever protocol the server is speaking. Hellwig ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
I think you could do this with a binary tree - at each node keep a total of the weight values of the subtree below the node. If the pattern was hashed, then each bit could define a branch of the tree, 0 = left branch 1 = right branch. Then you have a very simple divide and conquer algorithm. The tree would not be perfectly balanced, but even with a lousy (fast) hash function it would be more than adequate. You could have a massive populations of things to select from probabilistically and this would still be very fast. - Don On Wed, Jul 15, 2009 at 7:06 PM, Mark Boon tesujisoftw...@gmail.com wrote: When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
In the loop i is always zero. I think your code is wrong.
You probably meant to loop over all the weights (or I should say on average
half the weights), and this code is slow if there are a lot of weights.
2009/7/16 Peter Drake dr...@lclark.edu
I must be missing something. Isn't the obvious trick:
int r = random(sum of weights);
int i = 0;
while (r weights[i]) {
r -= weights[i];
}
return i;
This way, you only have to generate one random number.
Peter Drake
http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/
On Jul 15, 2009, at 8:55 PM, Zach Wegner wrote:
On Wed, Jul 15, 2009 at 10:37 PM, David Fotlandfotl...@smart-games.com
wrote:
So many complex ideas :) Why not just multiply the weight of each pattern
by a random number and pick the biggest result?
David
That involves generating N random numbers and then doing N-1
comparisons. The n-ary tree has only 1 random number and log N
comparisons, but has to be
incrementally updated (log N adds).
Also, I don't think the distribution is the same. Imagine two moves a
and b, with weights 2 and 1. The probabilities should be a=2/3 b=1/3,
but if you select two random numbers in a finite range, there's only a
1/4 chance that the second number is more than twice the first, which
is needed for b to be selected. I could be wrong here though.
Zach
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Random weighted patterns
On Wed, Jul 15, 2009 at 11:37 PM, David Fotland fotl...@smart-games.comwrote: So many complex ideas :) Why not just multiply the weight of each pattern by a random number and pick the biggest result? This is fine if you are looking for the slowest algorithm you can find. But it does have the merit of being straightforward, which is what he was asking for. The binary approach is O(log n) time on average, very efficient. Your approach is O(n). It's like the difference between doing a binary search to find something or scanning the whole list sequentially. If you are looking at less than 5 or 10 patterns there may not be much difference, but I assumed he was choosing among many patterns. - Don David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Mark Boon Sent: Wednesday, July 15, 2009 4:07 PM To: computer-go Subject: [computer-go] Random weighted patterns When using patterns during the playout I had improvised some code to select patterns randomly, but favour those with higher weights more or less proportionally to the weight.. I was wondering though if there's an established algorithm for something like this. To be a little more precise, if I have a set of values and two of those are represented by A and B. If A is twice as high as B it should have twice the chance to be selected. If there's a third value C that is 1.5 times A then it should be 1.5 times as likely to be selected as A and 3 times as likely as B. Etc. There are many strategies I can think of that make a randomly weighted selection from a set. But none of them are really straightforward. So I'd be interested to hear how others handled something like this. And if there's maybe a standard known algorithm, this kind of thing must appear in a lot of fields. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Tue, Jul 14, 2009 at 4:07 AM, Ingo Althöfer 3-hirn-ver...@gmx.dewrote: Darren Cook wrote: Ingo's suggestion (of two buttons to increment/decrement komi by one point) was to make it easy for strong humans to test out the idea for us. Don Dailey wrote: There is no question that if you provide a button to push, all kinds of positions will appear where this idea works. Providing a button is not nearly the same as providing an actual working algorithm that you can prove is superior. Right. Especially it may turn out that dynamic komi works well as a tool in computer-aided analysis. To give an example, the very new version 12.013 of Many Faces of Go has a feature: the program does not only compute its best move but also shows percentages for alternative popular moves (name coined by David Fotland). Here is a screenshot http://www.althofer.de/image-fotland.jpg or in context http://www.althofer.de/k-best-visualisations.html Of course, this feature not at all improves the playing strength of autonomous Many Faces. But it is a very hepful tool for computer- aided analysis of positions. The experience from almost two decades of chess programs on the pc: when you give users such tools to play with you will earlier or later get very helpful feedback. But this to me is just a random feature - it seems like many other more useful features would be much higher priority than a pseudo komi feature. - Don Ingo. -- Neu: GMX Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate für nur 19,99 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] memory management for search trees(basic question)
There has been quite a few descriptions on this forum about how people do this. I am guessing, but I think most of the authors allocate a pool of memory and manage this themselves.Are you writing in C? In C you can declare a fixed size record (called a struct) and just make an array of them.This is what my program does. When I need new nodes I just use the next ones available and a counter keeps track of where I am. It's a little more complicated if you also need to remove nodes. I don't do this. When a new search begins I can just start over again. I think there are a lot of variations of what people do.Perhaps a better way is to use a hash table instead of a tree. It's still a tree of course but structured different. With a hash table a zobrist key is used to index into a hash table. So you can build your tree this way, again using a fixed pool of nodes or whatever hash table method you need to.One advantage of a hash table is that with transpositions you can resuse information that has already been computed - but one disadvantage is that you have to deal with Graph History Interaction (GHI.) I think most program ignore GHI for the most part (in a similar way that computer chess programmers ignore the problem) but I'm not real sure on this one. You can also use malloc and free to allocate space for nodes - but it is well known that this can be challenging for writing bug free programs. I have found that you can almost always avoid it and I personally only use it for top level data structures - for instance I might allocate my initial fixed pool of nodes this way (and so it can be user configurable) but I won't allocate and free individual nodes. Also, if you use malloc and free you will surely see a slowdown. Another option is to use the Hans Boehm garbage collector, a library you simple link to in your C programs.It will do the automated garbage collection for you - but I think you will see a slowdown and I think there is a memory overhead penality for using this as it probably needs working space. - Don On Tue, Jul 14, 2009 at 11:06 AM, Carter Cheng carter_ch...@yahoo.comwrote: This is something I have been curious about since I am somewhat new to writing code in languages which require explicit memory management (as opposed to have some sort of garbage collector do it for you). The question is how do most programs manage memory w.r.t. the search nodes? Is the memory preallocated in advance or is there some strategy to grow the space required as the nodes accumulate during a search? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] memory management for search trees(basic question)
I think most programs completely ignore this issue except for simple ko. I think for all practical purposes you can consider 2 positions identical if they have the same set of legal moves possible, considering only simple ko. Of course this is not entirely correct, but I don't think it will weaken the program in any way that you could easily detect.At any rate, the cure might weaken the program more than the disease. You probably don't want to ignore this in the tree itself though. If a move is illegal due to any kind of ko, don't expand it. So your tree will be proper and correct, but some particular node may have data generated from positions that are technically different due to GHI issues. If anyone handles this any differently, it would be good to say something here ... - Don On Tue, Jul 14, 2009 at 12:10 PM, Carter Cheng carter_ch...@yahoo.comwrote: Thanks for the replies. I will most likely be writing in C++ given the additional abstraction mechanisms and my current lack of understanding of preprocessor #define type tricks. I remember reading about Zobrist's hash functions in some old messages on the list and some papers on the GHI issue but at this point I am still just implementing the basic light playout simulation code so I haven't quite gotten here yet. I wonder concerning GHI for doing searches in go that you could in principle encode extra information into the position key which could be use to discriminate board positions which appear to be the same but differ in crucial ways. Thanks everyone for the help. --- On Tue, 7/14/09, Don Dailey dailey@gmail.com wrote: From: Don Dailey dailey@gmail.com Subject: Re: [computer-go] memory management for search trees(basic question) To: computer-go computer-go@computer-go.org Date: Tuesday, July 14, 2009, 8:32 AM There has been quite a few descriptions on this forum about how people do this. I am guessing, but I think most of the authors allocate a pool of memory and manage this themselves.Are you writing in C? In C you can declare a fixed size record (called a struct) and just make an array of them.This is what my program does. When I need new nodes I just use the next ones available and a counter keeps track of where I am. It's a little more complicated if you also need to remove nodes. I don't do this. When a new search begins I can just start over again. I think there are a lot of variations of what people do.Perhaps a better way is to use a hash table instead of a tree. It's still a tree of course but structured different. With a hash table a zobrist key is used to index into a hash table. So you can build your tree this way, again using a fixed pool of nodes or whatever hash table method you need to.One advantage of a hash table is that with transpositions you can resuse information that has already been computed - but one disadvantage is that you have to deal with Graph History Interaction (GHI.) I think most program ignore GHI for the most part (in a similar way that computer chess programmers ignore the problem) but I'm not real sure on this one. You can also use malloc and free to allocate space for nodes - but it is well known that this can be challenging for writing bug free programs. I have found that you can almost always avoid it and I personally only use it for top level data structures - for instance I might allocate my initial fixed pool of nodes this way (and so it can be user configurable) but I won't allocate and free individual nodes. Also, if you use malloc and free you will surely see a slowdown. Another option is to use the Hans Boehm garbage collector, a library you simple link to in your C programs.It will do the automated garbage collection for you - but I think you will see a slowdown and I think there is a memory overhead penality for using this as it probably needs working space. - Don On Tue, Jul 14, 2009 at 11:06 AM, Carter Cheng carter_ch...@yahoo.com wrote: This is something I have been curious about since I am somewhat new to writing code in languages which require explicit memory management (as opposed to have some sort of garbage collector do it for you). The question is how do most programs manage memory w.r.t. the search nodes? Is the memory preallocated in advance or is there some strategy to grow the space required as the nodes accumulate during a search? Thanks in advance, Carter. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -Inline Attachment Follows- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sun, Jul 12, 2009 at 8:07 AM, Benjamin Teuber benjamin.teu...@web.dewrote: Hi, I would like to know what exact experiments with virtual komi have been made and why thay failed. To me, this idea seems very natural, as it encodes the confidence of the stronger player that the weaker one will eventually make more mistakes on his own. You don't need to catch up a fourty-point handicap at once and try to kill all - instead you just overplay a little in order to catch up slowly but steadily. You just hit the nail on the head. Dynamic komi does not encourage a program to overplay the position. Since you are starting from a losing position you HAVE to overplay a bit. You have to attack when it is futile. Dynamic komi just makes the program happy with less.That is NOT a good algorithm for winning against fallible opponents when you are behind.It' s NOT a natural algorithm and I don't believe it's what humans do either. Dynamic komi doesn't tell the program that you should fight for something that you probably cannot win - which is what you have to do in handicap play. It just tells the program that it's ok not to fight and play as if everything is fine. What I'm suggesting is not to ignore the problem but to find some other technique that actually addresses the true problem. If you're behind by 5 points after move 100 against a player who is five stones weaker than you, you can almost consider it a sure win. If you're behind by the same amount, but when the last endgame moves are being played, it's a safe loss. This all is encoded very naturally by a decreasing virtual komi. So why exactly shouldn't it work? Cheers, Benjamin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sun, Jul 12, 2009 at 8:59 AM, Benjamin Teuber benjamin.teu...@web.dewrote: You just hit the nail on the head. Dynamic komi does not encourage a program to overplay the position. Since you are starting from a losing position you HAVE to overplay a bit. You have to attack when it is futile. That depends on the komi - if you're behind by fourty points and set the virtual komi to 30, you play as if you'd be 10 behind, which would be agressive, but not kamikaze. This is exactly what people do, so I don't see your point. It's not up to me to prove anything. It's up to you. Several of us have tried variations of this idea of dynamic komi adjustment, which seems like a very good premise. This SHOULD help the play.But the fact of the matter is that none of us (so far) has made it work. If the observations do not fit the premise, at some point we should actually scrutinize the premise - even if the premise seems logical to us. I think the ones who still cling to this idea have not actually tried implementing it.Have you tried?If you have, why are still talking about it and not showing us something? - Don Benjamin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
2009/7/12 David Fotland fotl...@smart-games.com e) use a knowledge system that knows what good moves look to prune or bias the moves when way ahead or way behind. This is what many Faces does. This is what I believe to be the most reasonable approach. - Don David *From:* computer-go-boun...@computer-go.org [mailto: computer-go-boun...@computer-go.org] *On Behalf Of * dhillism...@netscape.net *Sent:* Sunday, July 12, 2009 9:54 AM *To:* computer-go@computer-go.org *Subject:* Re: [computer-go] Re: Dynamic komi in commercial programs There are 3 commonly cited problems and 4 commonly proposed remedies. Problems: 1) Human games remain interesting, even after the winner is clear, because the players just naturally switch to playing for maximum territory. Wouldn't MCTS bots be more fun to play against if they did that too? 2) Sometimes a bot has a win by a small margin, but thinks it's a win by a big margin (because it is misreading a seki or whatever). Consequently, the bot neglects to defend the space that matters and loses after all. 3) For a big enough handicap, the bot plays random, ugly looking moves in the beginning. Can't that be improved? Remedies: a) Play for maximum territory sometimes. b) Fake the Komi sometimes. c) Unbalance the playout strength sometimes. d) Worry about more important things. The vagueness in the sometimes part doesn't help in deciding which remedy is best for which problem. Looking at the handicap problem alone, how can I pick the best remedy and justify my decision? Maybe I could take my engine at a reasonable time setting and experiment with all the remedies to try to find the highest handicap I can give Wally and still win 50% of the games. - Dave Hillis -- *A Good Credit Score is 700 or Above. See yours in just 2 easy steps!http://pr.atwola.com/promoclk/100126575x1222377098x1201454399/aol?redir=http://www.freecreditreport.com/pm/default.aspx?sc=668072%26hmpgID=62%26bcd=JulystepsfooterNO62 * ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sun, Jul 12, 2009 at 1:22 PM, Christian Nentwich christian.nentw...@gmail.com wrote: Don, others, are there publications about this? If people have tried it out, are there any threads on this list that somebody remembers where results are posted? I have not been able to find any. It would be interesting to see. I think I just mentioned that there is probably not much on this except in the archive.And even then it's probably not very well documented. I did try this myself but I don't have any data to show what I did.What I remember is that it's incredibly tricky - how do you actually know when and how much to adjust? If the score starts getting really low or really high, do you restart the search with a new komi?If you restart then you have wasted effort. I tried 2 different thing. One of them involved using the total points won in some kind of hybrid approach and the other involved changing the komi during the game. Using JUST the total points won is a drastic weakening of the program and it's surprising how much. I tried factoring in a percentage of total points won and other things.After some time I gave up - it seemed like I was taking something that worked well and trying to make it better by factoring in something that sucked. It was like trying to make it play better by putting something in on purpose that I knew makes it play worse. The dynamic komi adjustment, from my recollection was more promising, but still played worse. The only way to make this work is if you know in advance what kind of position you really have.If you KNOW that you can pick off a small group without risk, then it probably would work just fine.But just increasing komi for no reason except that you are winning is not good enough. For instance if you KNOW there is a seki issue, then you should probably do it.But just doing it because there MIGHT be a seki issue every 50 games that actually matters is not good enough. You could call this a chicken and egg problem.You can of course easily construct positions that will illustrate how wonderful the idea is, and it will probably work great in those positions.Seki positions are always given as to why this will help - but not every game has a game critical seki. But I'm pretty convinced you cannot generalize the idea. You would have to do some kind of pre-analsysis to figure out what needs to be done, and by then you may already know what to do anyway and you have a more convential program. - Don Christian 2009/7/12 Don Dailey dailey@gmail.com: On Sun, Jul 12, 2009 at 8:59 AM, Benjamin Teuber benjamin.teu...@web.de wrote: You just hit the nail on the head. Dynamic komi does not encourage a program to overplay the position. Since you are starting from a losing position you HAVE to overplay a bit. You have to attack when it is futile. That depends on the komi - if you're behind by fourty points and set the virtual komi to 30, you play as if you'd be 10 behind, which would be agressive, but not kamikaze. This is exactly what people do, so I don't see your point. It's not up to me to prove anything. It's up to you. Several of us have tried variations of this idea of dynamic komi adjustment, which seems like a very good premise. This SHOULD help the play.But the fact of the matter is that none of us (so far) has made it work. If the observations do not fit the premise, at some point we should actually scrutinize the premise - even if the premise seems logical to us. I think the ones who still cling to this idea have not actually tried implementing it.Have you tried?If you have, why are still talking about it and not showing us something? - Don Benjamin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sun, Jul 12, 2009 at 3:08 PM, Benjamin Teuber benjamin.teu...@web.dewrote: It's not up to me to prove anything. It's up to you. You entered a discussion in which you gave arguments (that I believe are nonsense) ... but at least fits the observation that this method does not work. ... against this method, which I just meant to counter. Why don't you counter it with an argument that fits the actual observation? But I don't want to prove anything (well I might want, but I know I cannot). I'm really just curious about this good-sounding idea and hoped somebody might be able to give details of its failure. There are some things in the archive on this - the idea is literally years old. But I doubt you will any papers on this since it's a failure. Paper authors tend to spend more time writing papers on things that work - unless they have some really surprising or interesting result to report. - Don Cheers, Benjamin ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sun, Jul 12, 2009 at 7:12 PM, Matthew Woodcraft matt...@woodcraft.me.ukwrote: Don Dailey wrote: I did try this myself but I don't have any data to show what I did. What I remember is that it's incredibly tricky - how do you actually know when and how much to adjust? If the score starts getting really low or really high, do you restart the search with a new komi?If you restart then you have wasted effort. [...] The dynamic komi adjustment, from my recollection was more promising, but still played worse. So what board sizes were you working with? I only worked with boardsize 9. - Don -M- ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sun, Jul 12, 2009 at 8:10 PM, Darren Cook dar...@dcook.org wrote: I would like to know what exact experiments with virtual komi have been made and why thay failed. ... I'm only aware of Don's experiment [1], which he admits he doesn't have any details for and only remembers: I did a bunch of experiments and ALWAYS got a reduced wins when I faked the komi. On the other side we have some experiments by Kato-san [2] (where he reports a 100 ELO improvement over GnuGo, but only from a few tens of game) and a subjective experiment by Okasaki-san where he reported Mogo played clearly stronger on KGS [3]. My own experiments are even more subjective and small-scale, and in the context of 9x9 endgames, not 19x19 handicap openings. However they were enough to make me think the technique is viable, but that if you don't adjust the komi down so the winning rate is near 50% it is wasted effort (*), and so you need to replay the same move over and over with different komi until you zero in on that point. *: I.e. the program still plays weak moves if you've only adjusted komi to go from 80% to 65%, or from 25% to 35%. kill all - instead you just overplay a little in order to catch up slowly but steadily. You just hit the nail on the head. Dynamic komi does not encourage a program to overplay the position. Since you are starting from a losing position you HAVE to overplay a bit. You have to attack when it is futile. If the handicap is correct then you don't really need to overplay. As the stronger player you might guide the game towards more complex positions to encourage more mistakes, but mainly you are just sitting around waiting for those inevitable mistakes. But, the real point of adjusting komi is it is an easy to understand way to overcome MCTS's problem when seeing all moves as winning/losing, and choosing effectively randomly instead of falling back on an opponent model as a human would do. Ingo's suggestion (of two buttons to increment/decrement komi by one point) was to make it easy for strong humans to test out the idea for us. There is no question that if you provide a button to push, all kinds of positions will appear where this idea works. Providing a button is not nearly the same as providing an actual working algorithm that you can prove is superior. So if you can do this in a verifiable way I'll be interested. - Don Darren [1]: http://computer-go.org/pipermail/computer-go/2008-August/015870.html [2]: http://computer-go.org/pipermail/computer-go/2008-February/014283.html [3]: http://computer-go.org/pipermail/computer-go/2008-August/015877.html ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Dynamic komi in commercial programs
I think we should open up to other ideas, not just dynamic komi modification. In fact that has not proved to be a very fruitful technique and I don't understand the fascination with it. First we identify what it is we are trying to accomplish. You mentioned improving the strength of MCTS go programs in handicap games, but many people point to the ugly style of play. Here is something to think about in more theoretical terms. Define what good play is. To me there is no satisfying definition - the CORRECT definition is not the one that we intuitively expect. For instance, if you are in a dead lost position, every move you play is a losing move. How can you say any particular move is better?To me a good move is any move that preserve the best game theoretic result possible at this point in the game. That means in a lost position ALL moves are good moves because they all preserve the loss.It's an odd way to look at it, but it makes more sense in won positions, as only a few or even 1 move preserves a win. The intuitive definition that we really mean when we talk about good play is to play in such a way as to increase our chances of winning against fallible opponents.In fact, what is good is technically (and practically) defined by WHO your opponent is. It appears that dynamic komi modification does not even help you win against fallible opponents, so we should probably look to opponent modeling (since that is really what we are asking for - especially with handicap games.) Another definition for good play is one that could be added to our MCTS programs. Play the move which preserves the best possible total point score. That means even in a dead lost position we will fight for every point on the board. Why doesn't this code up well with go programs? From a purely theoretical view, it is a perfect goal in the sense that if it is followed perfectly, it will perform the same as simply playing for the win against perfect opponents. Part of the answer may be that it requires more skill. There are fewer moves (in general) that will accomplish this goal than there is in winning the game. It would not suprise me, although I haven't specifically tested this, if this led to stronger play than dynamic komi modification. Then there is the possibility of a hybrid between the two. A fourth possibility is to gently impose some higher order knowledge on the search - try to make the tree branch out with moves that WE consider stronger (by the practical defintion, not the correct definition.) Probably with only a little help, moves which are other equal but we like better can be coerced into being the ones expanded on first and thus end up being the ones chosen by the MC program.We could do this by letting some conventional program choose the best move(s) and give them a few bogus wins to make the tree begin with the moves we would prefer. There a probably tons of possibilities. What does Many Faces do? Does it play more naturual? I ask because I know that Dave is more concerned about the marketability of the program and is interested and concerned about such things. - Don On Sat, Jul 11, 2009 at 10:26 AM, Ingo Althöfer 3-hirn-ver...@gmx.dewrote: One of the difficult questions is if (or better how) dynamic komi can be used to improve the strength of MCTS go programs in handicap games (both cases being interesting: computer on strong side - and - computer on weak side). Especially, there are several normal go players (non-programmers) who are interested in this topic and who feel that the current non-activity on this question is unsatisfactorily. Stefan Kaitschick (German 5-dan amateur, EGF-rating 2439) is in some sense the most prominent amongst them. I think that it would be a real chance for the programmers to use the interest and creativity of such people. This might happen for instance in the following way: include a simple komi-modification button in your program (or a pair of buttons, one for +, one for -) which can be used by simple mouse clicks. Of course, all the time the true value of komi should also be shown. You programmers would probably be surprised to see what creative users would find out when playing around with such a feature. Ingo. -- Neu: GMX Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate für nur 19,99 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Dynamic komi in commercial programs
On Sat, Jul 11, 2009 at 4:54 PM, Dave Dyer dd...@real-me.net wrote: If you are in a lost position, good play is play that maximizes the probability of a turnaround, which is quite different depending on how far behind you are, and for what reason. What maximizes the probability of a turnaround depends on your opponent more than anything else. I'm sure the best move by this definition will change according to who you are playing. If the status of all the major groups is solid, then concentrating on tactics which can gain a few points reliably might be the right thing. I think the best PRACTICAL definition (which can be formalized) is to play the move (or one of the moves) that maximizes the total points on the board.I think this is the natural human style, more or less. My real point is that whether a move is good or bad cannot be precisely defined if you are looking for a practical definition. If you use my theoretical definion, it can be precisely defined, but it may not be the best practical definition for winning real games against fallible opponents. - Don On the other hand, if the status of some groups is less than immutable, then focusing on changing their status favorably might be correct. It's hard to see how shifting Komi will influence the style of play in this direction. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Scoring - step function or sigmoid function?
On Mon, Jun 8, 2009 at 7:35 AM, Stefan Kaitschick stefan.kaitsch...@hamburg.de wrote: Thinking about why... In a given board position moves can be grouped into sets: the set of correct moves, the set of 1pt mistakes, 2pt mistakes, etc. Let's assume each side has roughly the same number of moves each in each of these groupings. If black is winning by 0.5pt with perfect play, then mistakes by each side balance out and we get a winning percentage of just over 50%. If he is winning by 1.5pt then he has breathing space and can make an extra mistake. Or in other words, at a certain move he can play any of the moves in the correct moves set, or any of the moves in the 1pt mistakes set, and still win. So he wins more of the playouts. Say 55%. If he is winning by 2.5pts then he can make one 2pt mistakes or two 1pt mistakes (more than the opponent) and still win, so he wins more playouts, 60% perhaps. And so on. My conclusion was that the winning percentage is more than just an estimate of how likely the player is to win. It is in fact a crude estimator of the final score. Going back to your original comment, when choosing between move A that leads to a 0.5pt win, and move B that leads to a 100pt win, you should be seeing move B has a higher winning percentage. Darren Point well taken.Winning positions tend to cluster and critical swing moves are rare, statistically speaking. If the position is more or less evenly balanced, the step function might allready be very close to optimal because of this. But I would like to bring up a well known mc quirk: In handicap positions, or after one side scored a big success in an even game, bots play badly with both sides, until the position becomes closer again. The problem here is that every move is a win (or every move is a loss). On 9*9, its possible to beat a bot, giving it 2 stones, even when it's a close contest on even with komi. All it needs is a single bot missread at the moment the position becomes close(which it will, because the bot will be lazy until that point). I would say it's foolish to purposely give the bot 2 stones in order to hope for a misread unless you are expert on that particular behaviour and can predict just where and why it will go wrong. So it would be desirable for the bot to make keeping the score advantage large an auxiliary goal. This has been tried ofcourse, but without much success sofar. And it seems that the main reason is that tinkering with the scoring function to achive this, tends to worsen play in competitive situations. This is easy to understand - it's because maximizing your winning chances is a better strategy than maximizing how many points you take. One is the actual goal of the game (to win) and the other is a different goal which is not as highly corelated as we like to think it is. I have an alternative suggestion: In handicap games, introduce a virtual komi, that gets reduced to 0 as the game progresses. This would work for the bot on both sides: If the bot has b it will make less lazy plays, if it has w, it will be less maniacal. For example, in a 4 stone 19*19 game, if the real starting advantage is about 45 points, the bot could introduce an internal komi of about 30-35. The bot should be optimistic with b and pessimistic with w, but not to the point that every move evaluates to the same value, and move selection becomes a toss-up. Another way to look at this, is that humans that give a handicap know that they can't usually catch up in one piece. And humans that take a handicap know that they can't give up their advantage too quickly. Virtual komi encodes this simple knowledge. During the course of the game this internal komi would ofcourse have to be reduced to 0. The proper criteria can only be found by experimentation, but the important factors will be how far the game has progressed, and what the win rate is for the best move. If the bot becomes pessimistic with b it should lower the internal komi more quickly. In principle this is no different from the usual schemes applied when there is no handicap. In practice, there is one thing different that could make it at least worth a look.When you play WITH a handicap it's because your opponent is weaker than you are.When the opponent has the handicap it's because YOU are the weaker player.So you can use the fact that you are playing in a handicap game to tell you something about your opponent. Now if you are playing against a weaker opponent, your winning chances actually do increase, so by manipulation of the komi you can represent that fact.It's certainly wrong to do this with an equal opponent but perhaps not so bad with a weaker opponent. My guess is that this still won't work, but at least there is something different about these kind of games that could make this worth another look. The reason komi schemes like this probably dont' work well in general is because they
Re: [computer-go] Really basic question
On Tue, Jul 7, 2009 at 3:49 AM, Magnus Persson magnus.pers...@phmp.sewrote: Quoting Oliver Lewis ojfle...@gmail.com: Others on this list have reported in the past that the randomness is actually very important. Playouts that are very heavy, no matter how clever they are, actually reduce the performance because they narrow the number of games too much. I would like to disagree with this statement. I think it is difficult to make a good heavy playouts, but it is not impossible. Failing to make a playout stronger through heaviness does not prove anything. It just mean one has failed. If I could make a heavy playout of 1 Dan strength and then run in MC tree search. I am sure it would be stronger than the playout itself. I agree with everything you said. In the Mogo papers it is claimed that having stronger playouts does not NECESSARILY lead to stronger play in general. I don't believe everything I read, but I think there may be something to this.Also, having a random element to this does not imply weakening the play, perhaps it's more like varying the playing style. If the Mogo team is correct the formula seems to be that there is something in the playouts that can compliment the search in some way not fully understood. As you gradually go from random to deterministic you cease to have Monte Carlo and you have something that is more like a best first search.It may be that in a few years our programs will gradually transition away from MC and more toward TS using best first methods. Maybe that is really what we have discovered and the MC part is distracting us? The problem I think is to find a good tradeoff between heavyness and speed. In my test with Valkyria vs Fuego, Valkyria is superior when the number of playouts are the same. But Fuego can play 5 times more playouts per second on the hardware that results in Fuego being slightly stronger than Valkyria at the moment. The search is good at some things and poor at other things. These 2 aspects need to work together in a complimentary way and in my opinion will mean more domain specific knowledge. Your observation concerning Fuego and Valkyria indicate that there is a lot of overlap - you can make up search with knowledge and knowledge with search. I believe the huge lack of progress over the years (until recently) has been the blind failure to recgonize that you cannot cover everything with knowledge but we must not move too far in the other direction either. Domain specific GO knowledge is too brittle to do it all, but should be provided as hints to a search. That is exactly how us humans do it. We try to back up our positional judgement and knowledge with concrete analysis.When the knowledge, understanding and intuition is strong, less analysis is needed and visa versa. I have had many discussions with Larry Kaufman, who works with the Rybka chess team - currently the strongest chess program in the world. I think some of the things we have talked about applies very much to GO. It is very interesting to me that even though he is heavily involved in the knowledge engineering aspect of the program, he seems to feel that Rybka is confined by the knowledge part.He tells me (and this applies to ALL programs, not just Rybka), that there are certain positions, ideas or themes where Rybka is a victim of it's evaluation function. Adding an additional order of magnitude more time to the search is not going to change the basic misconception if the evaluation just doesn't understand the position. So you can have 2 equally strong chess programs that are playing stronger than any human player, choosing a different move in the same position and one can be correct and the other wrong - and the one that is wrong may not find the correct move even thinking 10X longer. That is a pretty depressing thought for GO programming because if it's a problem in Chess, then it can only be worse for GO. So I suspect that from your description of the differences between Valkyra and Fuego there will be huge differences in which positions Valkyra plays better vs Fuego. One thing I have found in chess is that each piece of knowledge has side-effects. Every new rule of thumb that you impose, makes your program a bit more dogmatic.I believe the trick is figuring out how not to make it too dogmatic, while still giving it a sensible set of heuristics to guide it along. It just cannot be that having strong playout leads to worse play in general. It is just a matter of not slowing down the code too much and add just those heavy elements that do increase playing strength. Yes, I guess I just repeated you but in a different way. - Don -Magnus -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Experimentation (was: Really basic question)
On Tue, Jul 7, 2009 at 6:31 AM, Christian Nentwich christ...@modeltwozero.com wrote: The problem I think is to find a good tradeoff between heavyness and speed. In my test with Valkyria vs Fuego, Valkyria is superior when the number of playouts are the same. But Fuego can play 5 times more playouts per second on the hardware that results in Fuego being slightly stronger than Valkyria at the moment. Indeed - this makes me wonder why I keep seeing papers where different versions of algorithms are compared with the same number of playouts, rather than under the same time limit. Because this is the right testing methodology to use. The first thing you want to know is if the core idea is good. This is because you will never know if you implemented it in the fastest possible way. But once you know that the idea gives you better results with the same number of playouts you have identified something about it that is superior - then you can go from there. There are two aspects that you are concerned about with tests like this. The first and most important thing is the theoretical soundness of the idea or approach being used.The second is the engineering issues, which are really quite open ended and tough to nail down accurately. Not only that, but you can kill 2 birds with one stone - if the theory is not sound, then there is no need to pursue the engineering aspect. There is probably no great crime in doing it your way if your only goal is to produce a strong program, but if your test fails you don't really know if it failed because the idea is stupid or if your implementation is unduly slow. If you are writing a paper you certainly do not want to claim results based solely on just your particular implementation of an idea that might be bad anyway. There is nothing wrong with presenting an engineering paper about an interesting way to implement something, but even then it would be a pretty silly paper if you did not present at least some analysis on why someone would WANT to implement this thing i.e. it is a commonly used thing (a new sorting algorithm) or has some practical application that you can identify. What is the motivation in this? I cannot conceive of any good reason for running an experiment this way, so I would be interested in opinions. It seems to me that making algorithms heavier and then demonstrating that they are stronger with the same number of playouts misses the point - why would one not run an experiment under the same time conditions instead? As I said, when you are writing a paper you have to prove that something is theoretically sound, at least empirically. If you are writing an engineering paper you might present an interesting implementation of some idea, but it should be an idea that has first been shown to be interesting in some way. For instance a new faster sorting algorithm is interesting. But you certainly don't want to present evidence that YOUR IMPLEMENTATION of YOUR IDEA is no good when you have not even attempted to establish whether the idea itself is viable. - Don Christian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
