Re: Re: [computer-go] 3-4-5 rule
I thinkHeikki makes a valid point here. I am not a particularly strong player (about 1-2 dan european), but I have learned that playing defensively is generally detrimental to the final result, whereas taking the initiative is more likely to lead to a win. If moves close to the existing position are given much greater weight than those further away, this may result in more defensive play than otherwise. During much of thegame, most moves between human players, even at professional level, are playednear to the previous move. Soconsideringall moves near to the last played moveis likely to increase the probablility of selecting the best move. Thiscould be the factor that is currently resulting in more wins where the 3-4-5 rule is applied. However, there are times when the best move ismost definitely not in the vicinity of the previous one, and a strong player will 'tenuki' -i.e. leave that part of the position to play something more important elsewhere - an urgent invasion on the other side of the board for example. If computer go programmes are to become truly strong they will need to have a way to emulate this kind of approach. In my (limited) opinion, the 3-4-5 rule may result in a short-term gain, butwill require refinement in due course to allow for what human playersmight call creativity. Paul Dec 30, 2008 11:56:58 PM, computer-go@computer-go.org wrote: On Wed, Dec 31, 2008 at 12:25:10AM +0100, Rémi Coulom wrote: If you'd like to try a simple pruning scheme that improves playing strength on 19x19, then I'd suggest progressive widening. It only works in the tree, not in the playouts. You don't need complex patterns for progressive widening to work. You can simply use distance to the previous move. Search moves at distance 1 from the previous move for N playouts. Then add moves at distance 2 for N*x playouts. Moves at distance 3 for N*x*x. So, you'd be playing like a beginner, with a local answer to every move theopponent makes. Never taking sente to play elsewhere. Sounds like a receipefor a disaster to me. But then again, I am only a kyu-level player, so I maybe wrong...-H-- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk___computer-go mailing listcomputer-go@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/
Re: Re: [computer-go] 3-4-5 rule
On Wed, 2008-12-31 at 12:25 +, p...@tabor.com wrote: I think Heikki makes a valid point here. I am not a particularly strong player (about 1-2 dan european), but I have learned that playing defensively is generally detrimental to the final result, whereas taking the initiative is more likely to lead to a win. This is how I feel about playing in general, but it's better stated by what a chess master once told me: Play your own game. From his own experience he told me that weaker players often get intimidated when they play a master and play worse than they normally would. Also they avoid tactics even when that is the strongest part of their game feeling that they will surely get crushed. So the advice is to just do what you do best, play your strengths. If moves close to the existing position are given much greater weight than those further away, this may result in more defensive play than otherwise. As I said before, for a weak bot this is not really a matter of playing inferior to what it is capable of. We are talking about a random strategy and playing moves that are much more likely to be good than random moves is probably not a defensive losing strategy in my opinion. I don't have a strong opinion on how good the actual strategy 3-4-5 strategy is however, I'm not much of a go player.How often is this rule violated in top level games?And when it is, can it be shown that no reasonable conforming rule exists? I don't know the answer to that. During much of the game, most moves between human players, even at professional level, are played near to the previous move. So considering all moves near to the last played move is likely to increase the probablility of selecting the best move. This could be the factor that is currently resulting in more wins where the 3-4-5 rule is applied. The issue is whether resulting in more wins is correlated to playing stronger in the general case against a variety of opponents.So if one bot is NOT using this strategy and the other IS using this strategy, then one of them is not biased in this regard, yet it is losing. The conclusion I would draw here is that with high probability the one using the strategy is actually playing a better overall game. This is the simplest and most Occam's razor conclusion. If the bot was far stronger and much more sophisticated, then this is a rule which might very well hold it back. However, there are times when the best move is most definitely not in the vicinity of the previous one, and a strong player will 'tenuki' - i.e. leave that part of the position to play something more important elsewhere - an urgent invasion on the other side of the board for example. If computer go programmes are to become truly strong they will need to have a way to emulate this kind of approach. I don't think that is in question. What is being called into question is whether there should be any kind of rules or evaluation that might occasionally be in error. The answer is crystal clear, all strong go programs have biased playouts and it works. In my (limited) opinion, the 3-4-5 rule may result in a short-term gain, but will require refinement in due course to allow for what human players might call creativity. I agree. To me this is like a chess evaluation function, nobody has every written a good one but they work really well anyway. You could do without one and watch your program get really weak. Random playouts by themselves probably never will advance beyond horrible play and thus approximate rules can be a big win. - Don Paul Dec 30, 2008 11:56:58 PM, computer-go@computer-go.org wrote: On Wed, Dec 31, 2008 at 12:25:10AM +0100, Rémi Coulom wrote: If you'd like to try a simple pruning scheme that improves playing strength on 19x19, then I'd suggest progressive widening. It only works in the tree, not in the playouts. You don't need complex patterns for progressive widening to work. You can simply use distance to the previous move. Search moves at distance 1 from the previous move for N playouts. Then add moves at distance 2 for N*x playouts. Moves at distance 3 for N*x*x. So, you'd be playing like a beginner, with a local answer to every move the opponent makes. Never taking sente to play elsewhere. Sounds like a receipe for a disaster to me. But then again, I am only a kyu-level player, so I may be wrong... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org
Re: Re: [computer-go] 3-4-5 rule
On Wed, Dec 31, 2008 at 12:25:01PM +, p...@tabor.com wrote: I think Heikki makes a valid point here. I am not a particularly strong player (about 1-2 dan european), but I have learned that playing defensively is generally detrimental to the final result, whereas taking the initiative is more likely to lead to a win. If moves close to the existing position are given much greater weight than those further away, this may result in more defensive play than otherwise. Actually, as I undersand it, the rule was not to play close to the opponent's last move, but to limit play to either - 3rd, 4th, or 5th row - near any stone already played. This makes much more go-sense to me, even though I am a weak player (something like 5 kyu in Denmark). This rule will allow most of the common side extensions, invasions, etc, as well as answering any move locally or not. It will disallow some few moyo-reducing moves, but not too many. I guess in most cases those moyos can also be reduced by playing close enough to other stones, and/or on the 4th or 5th line. Of course a clever player who knows about this can direct the game so that he ends with a moyo, where the optimal reduction move does not get considered. That sounds tricky, and the advantage from such is slight, he can be a tiny bit more confident of keeping his moyo... - Heikki -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re: [computer-go] 3-4-5 rule
On Wed, 2008-12-31 at 14:45 +0100, Heikki Levanto wrote: Of course a clever player who knows about this can direct the game so that he ends with a moyo, where the optimal reduction move does not get considered. That sounds tricky, and the advantage from such is slight, he can be a tiny bit more confident of keeping his moyo... A player sophisticated enough to even think about doing this is way beyond the level of a simple reference bot using this strategy in the playouts.In fact, even trying to win like this would probably weaken him a little. Why go to the trouble when it's so easy to win other ways? I would love it if my much stronger opponents were to try to get clever on me when they didn't have to. Like this same chess master told me, keep it simple, don't get too clever when you don't have to. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Wed, 2008-12-31 at 17:59 +0200, Berk Ozbozkurt wrote: Heikki Levanto wrote: On Tue, Dec 30, 2008 at 08:01:27PM +0200, Berk Ozbozkurt wrote: I think such a change may make engine objectively stronger while making it more vulnerable against humans. Even if the human opponent isn't aware of the move pruning logic initially, it wouldn't take a lot of games to figure out that the computer never makes a move away from the last move to the center or to the sides. So sorry, but I think you have misunderstoodthe rule being tested here. It has nothing to do with the last move played, it is all about *not* playing to a point that is more than 3 (or 2) poitns away from any stone on the board, *or* that is on the 3th 4th, or the 5th row from the edge. This still leaves open a possibility of setting up two ladders, so that a ladder break somewhere in the center would be the right move. But even then, the random nature of the MC playouts would make such a position look pretty bad, and direct the program away from it - which would most often be good playing style anyway. My real mistake was thinking this was a tree searching engine. My all points are moot as this was only ref-bot doing AMAF. Assume, for argument's sake, the rule is implemented in a searching go engine and moves not conforming to the rule are hard pruned during search. It doesn't matter whether 2 points from any stone or just last move is considered. In many openings neither side would have any stones near the center, so no moves to the center would be considered by the engine, for at least a few more branches down the tree. Note that, it is the human opponent, who makes losing ladders with the intention of putting a ladder breaker in the center. As the program is oblivious to the fact that only one ladder may be won by it, the program will evaluate its position *highly* and tend to continue ladders as long as human continues playing them. It is not necessary to construct an example - it's just understood that any imperfect rule can be taken advantage of. I think most game tree search expert understand that hard pruning is wrong in the sense that it produce non-scalable programs. It might make your program stronger in the short term as someone said, but you would now have some rule that a clever opponent can take advantage of such as the case you just constructed. No matter what hard pruning rule you come up with, someone can construct an example where it's wrong, unless of course the rule is 100 percent correct and fool-proof. You basically just set up a position where the opponent really must play the forbidden move knowing that he cannot see it. But that doesn't mean you should not use SOFT pruning or bias - even in the tree.In fact most progress in computer go and computer chess has been in shaping the tree using imperfect heuristics, sometimes domain specific.There is no convincing logic that I know of that says it's better NOT to do that. You can always construct an example of some position where it goes wrong, but go ahead and build a program with the principal of not using knowledge and I will show you an extremely weak program. The perfect example is humans. Full of contradiction, bias and imperfect knowledge. A clever enough player can take advantage of even the strongest human players with methods like you suggest. I think the key is that knowledge you add must be reasonable and practical. Generally, beginners are given good practical rules of thumb, that serve him well. But a good strong player following such rules religiously would be compromised. You see, the same rule can make one play much better, another much worse.The rule must be compatible with your competence. Image being able to construct hundreds of rules like the 3-4-5 rule that are applied in decision tree fashion. One can imagine the program playing better and better as you add more rules. At some point the program would reach a level of competence where you would have to reconsider some of the rules, because they are now hurting the program. The 3-4-5 rule might be good at first, but imagine (I know this is silly) that such a program reached several dan level. The 3-4-5 rule would have to be replaced, or refined with exceptions otherwise further progress is hindered. As a kid I did a paper program for chess that worked like this. You just followed the instructions and eventually a move was produced. The program was designed to delay development of the queen - because every beginner knows not to move your queen out early. So you could threaten the opponent in such a way that a queen move was required, and the program could not defend. But the program was so weak and primitive that it was still a good rule - i.e. better than no rule at all. - Don - Don ___ computer-go
Re: [computer-go] 3-4-5 rule
After 39 games it looks pretty close: Rank Name Elo+- games score oppo. draws 1 d3p 2009 55 5539 51% 20000% 2 base 2000 55 5539 49% 20090% confidence interval still too high to say for sure, but it is starting to appear that depth 2 works better. - Don On Tue, 2008-12-30 at 23:22 +0100, Heikki Levanto wrote: On Tue, Dec 30, 2008 at 02:01:29PM -0500, Don Dailey wrote: It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) So sorry, but as far as I can see, three games don't prove very much. Could you please run at least 10 games more, before jumping into conclusions. -H ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
that's with or manhattan distance 2 as well? how about 3 or 4? s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey dailey@gmail.com wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ 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] 3-4-5 rule
I used distance = 2 first because it tested better on 9x9. Of course 3 might test better on 19x19 and I will try that now.The error bar makes it clear that 2 is an improvement, so I will stop the test and try 3 next. - Don On Tue, 2008-12-30 at 12:52 -0500, steve uurtamo wrote: that's with or manhattan distance 2 as well? how about 3 or 4? s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey dailey@gmail.com wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ 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] 3-4-5 rule
Don Dailey wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% You are using the rule for move selection during the playouts and the search, right? I think such a change may make engine objectively stronger while making it more vulnerable against humans. Even if the human opponent isn't aware of the move pruning logic initially, it wouldn't take a lot of games to figure out that the computer never makes a move away from the last move to the center or to the sides. Once the player understands the reason (because the engine never _considers_ such moves) building traps should be very easy for a good go player. For example, start a losing ladder towards the center on one side, then start another losing ladder to the center from another side, such that a ladder breaker in the center can break both ladders. Now the engine would play thinking all of its stones in the ladder are safe, oblivious to the fact it will be able to rescue only one group of them, if a move to the center is made. Of course the same idea may be used by a programmer to specifically build an engine stronger against engines with 3-4-5 rule too. The engine should at least allow _opponent_ to break the rule in the search tree. That is quite a bit harder to exploit. Now the player must find moves with refutations outside of the allowed search window. But there is now the problem of increased evaluation difference between odd and even depths (as one player is objectively stronger.) Therefore I think you shouldn't let engine prune in the tree with *any* simple heuristic rule, no matter how often that rule is a useful guide. OTOH pruning in the playouts seems safe enough. Does that increase strength too? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, 2008-12-30 at 20:01 +0200, Berk Ozbozkurt wrote: Don Dailey wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% You are using the rule for move selection during the playouts and the search, right? The rule applies in the playouts, as well as final move choice. I think such a change may make engine objectively stronger while making it more vulnerable against humans. I don't think that is the case.The premise is that it's wrong to violate this rule (even though we admit it is not 100% correct) - and even so, 99.9% of the time it's probably not a serious error. When the opponent violates the rule, the computer then is free to respond of course. Even if the human opponent isn't aware of the move pruning logic initially, it wouldn't take a lot of games to figure out that the computer never makes a move away from the last move to the center or to the sides. No, the computer can always move to line 3,4 and 5, OR it can make a move within distance N of ANY STONE sitting on the board. This is not limited to just the last move. So what you say next is probably based on a misunderstanding of how I implemented the rule. Once the player understands the reason (because the engine never _considers_ such moves) building traps should be very easy for a good go player. For example, start a losing ladder towards the center on one side, then start another losing ladder to the center from another side, such that a ladder breaker in the center can break both ladders. Now the engine would play thinking all of its stones in the ladder are safe, oblivious to the fact it will be able to rescue only one group of them, if a move to the center is made. Of course the same idea may be used by a programmer to specifically build an engine stronger against engines with 3-4-5 rule too. The engine should at least allow _opponent_ to break the rule in the search tree. This is one of those things that look good on paper, but I have real doubt it would work in practice.I have never seen asymmetric rules or evaluation actually work out like you think it should. I never say never, you may be right, I'm just saying I don't have any faith in that idea. The problem with asymmetric rules like this, is that it's really based on the assumption that you (the program) doesn't know what it is doing, but your opponent does.If he plays one of those moves it must be good but if you play it it's probably bad.That's a self-defeating attitude to base a game playing program on and it's eventually self-limiting. It's funny, but I have done the same thing in my own games when playing a stronger player and have come to grief. I once thought I had a pretty strong attack (in chess), which my much stronger opponent, by his move choice, told me that he didn't believe there was anything there. My time was relatively short, so I relied on his analysis and believed him.It turns out that I was a fool in this case. He really needed to defend against my attack to win. He had a probably win if he had defended, and now he had a win because I failed to follow through with natural attacking moves. I should have just trusted my own analysis. Even if your opponent is stronger you should never assume his moves must be correct and yours must suck. That is quite a bit harder to exploit. Now the player must find moves with refutations outside of the allowed search window. But there is now the problem of increased evaluation difference between odd and even depths (as one player is objectively stronger.) Therefore I think you shouldn't let engine prune in the tree with *any* simple heuristic rule, no matter how often that rule is a useful guide. OTOH pruning in the playouts seems safe enough. Does that increase strength too? I don't think you realize that this is not a tree based program - it is basically the simple reference bot modified with the 3-4-5 rule. The refbot does N playouts, then uses AMAF to select a move without any kind of proper tree search. But I definitely agree with what you just said about pruning in the tree. I don't believe in hard pruning, it should always be progressive. Unless of course you have stone cold proof that a move is less than the best.For a practical program you may be able to do cold hard pruning right now, but this is inherently non-scalable. It means there will always be a class of moves your program can never play correctly even with an infinite or arbitrarily deep search. In the case of the reference bot, it's not
Re: [computer-go] 3-4-5 rule
On Tue, 2008-12-30 at 12:52 -0500, steve uurtamo wrote: that's with or manhattan distance 2 as well? how about 3 or 4? It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) - Don s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey dailey@gmail.com wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ 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] 3-4-5 rule
I hope you're joking... Sent from my iPhone On Dec 30, 2008, at 2:01 PM, Don Dailey dailey@gmail.com wrote: On Tue, 2008-12-30 at 12:52 -0500, steve uurtamo wrote: that's with or manhattan distance 2 as well? how about 3 or 4? It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) - Don s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey dailey@gmail.com wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ 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] 3-4-5 rule
On Tue, 2008-12-30 at 14:23 -0500, Jason House wrote: I hope you're joking... It lost twice as many as it won, you're not convinced? :-) Ok, I'll let it run a few hundred more games just in case it somehow manages to turn things around. - Don Sent from my iPhone On Dec 30, 2008, at 2:01 PM, Don Dailey dailey@gmail.com wrote: On Tue, 2008-12-30 at 12:52 -0500, steve uurtamo wrote: that's with or manhattan distance 2 as well? how about 3 or 4? It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) - Don s. On Mon, Dec 29, 2008 at 7:42 PM, Don Dailey dailey@gmail.com wrote: After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ 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] 3-4-5 rule
On Tue, 30 Dec 2008, Don Dailey wrote: On Tue, 2008-12-30 at 14:23 -0500, Jason House wrote: I hope you're joking... It lost twice as many as it won, you're not convinced? :-) Ok, I'll let it run a few hundred more games just in case it somehow manages to turn things around. I agree with Jason ... how can it (distance=3) be worse? Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, 2008-12-30 at 12:19 -0800, Christoph Birk wrote: On Tue, 30 Dec 2008, Don Dailey wrote: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) ok, you got me there (3 games played :-) So you thought Jason was responding to the idea that distance 3 might be worse? Distance 3 could easily play worse - we shall see. Just because a distance 3 move is sometimes good doesn't mean it will make the program play better not throwing those out. If it's RARELY best, then the reduced effort and increased focus on (usually) more relevant moves could be a win. In fact I expect distance 2 to be better for that reason. But we shall see - no need to debate it :-) - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, 30 Dec 2008, Don Dailey wrote: Distance 3 could easily play worse - we shall see. Just because a distance 3 move is sometimes good doesn't mean it will make the program play better not throwing those out. If it's RARELY best, then the reduced effort and increased focus on (usually) more relevant moves could be a win. In fact I expect distance 2 to be better for that reason. IMHO 'd3' could be worse than 'd2' but not worse than 'base'. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, 2008-12-30 at 13:13 -0800, Christoph Birk wrote: On Tue, 30 Dec 2008, Don Dailey wrote: Distance 3 could easily play worse - we shall see. Just because a distance 3 move is sometimes good doesn't mean it will make the program play better not throwing those out. If it's RARELY best, then the reduced effort and increased focus on (usually) more relevant moves could be a win. In fact I expect distance 2 to be better for that reason. IMHO 'd3' could be worse than 'd2' but not worse than 'base'. Agreed. d3 should definitely be safer and has less potential to hurt things. So although I believe d2 will come out better than d3, it's like a risky investment with a higher expected value, such an investment has more risk too. - Don Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, Dec 30, 2008 at 02:01:29PM -0500, Don Dailey wrote: It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) So sorry, but as far as I can see, three games don't prove very much. Could you please run at least 10 games more, before jumping into conclusions. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, Dec 30, 2008 at 08:01:27PM +0200, Berk Ozbozkurt wrote: I think such a change may make engine objectively stronger while making it more vulnerable against humans. Even if the human opponent isn't aware of the move pruning logic initially, it wouldn't take a lot of games to figure out that the computer never makes a move away from the last move to the center or to the sides. So sorry, but I think you have misunderstoodthe rule being tested here. It has nothing to do with the last move played, it is all about *not* playing to a point that is more than 3 (or 2) poitns away from any stone on the board, *or* that is on the 3th 4th, or the 5th row from the edge. This still leaves open a possibility of setting up two ladders, so that a ladder break somewhere in the center would be the right move. But even then, the random nature of the MC playouts would make such a position look pretty bad, and direct the program away from it - which would most often be good playing style anyway. - H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
-Original Message- From: Heikki Levanto hei...@lsd.dk To: dailey@gmail.com; computer-go computer-go@computer-go.org Sent: Tue, 30 Dec 2008 5:22 pm Subject: Re: [computer-go] 3-4-5 rule On Tue, Dec 30, 2008 at 02:01:29PM -0500, Don Dailey wrote: It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) So sorry, but as far as I can see, three games don't prove very much. Could you please run at least 10 games more, before jumping into conclusions. -H Yes, 10 more trials would conclusively prove that 2.5 is the correct value. (Our sense of humor is what makes engineers the life of every party.) Actually, the best?answer might turn out to be something like?2.5 or 3.5. I have a similar rule in my program, but I search for neighbors in a square region because I am interested in Knight's moves and Monkey Jumps. ? - Dave Hillis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
From: dhillism...@netscape.net dhillism...@netscape.net I have a similar rule in my program, but I search for neighbors in a square region because I am interested in Knight's moves and Monkey Jumps. Here's an interesting scenario: A row of stones high on the fifth line, open on one side. A long knight's move invasion to the edge might be very successful. It might never be considered by the 3-4-5-manhattan-3 rule because it is not on the 3,4,5 lines, and is not within a manhattan distance of 3 of any stone on the board. ( The long knight's move has a manhattan distance of four - but it is a quite solid connection in many cases. ) These scenarios, being uncommon, are unlikely to occur even in a long series of games, but a savvy opponent would delight in laying such traps. I suspect that such rules might be most useful with an arbitrary cutoff at move 50 or some such point. After that, they don't discriminate much, and may weed out good moves. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Tue, 2008-12-30 at 23:22 +0100, Heikki Levanto wrote: On Tue, Dec 30, 2008 at 02:01:29PM -0500, Don Dailey wrote: It looks like 3 is no good: Rank Name Elo+- games score oppo. draws 1 base 2000 296 199 3 67% 18880% 2 d3p 1888 199 296 3 33% 20000% I think I have proven decisively that 3 doesn't work, it lost 2 out of the 3 games I played :-) So sorry, but as far as I can see, three games don't prove very much. Could you please run at least 10 games more, before jumping into conclusions. You are right, the d3p version rallied to come from behind and staged an exciting and dramatic comeback: Rank Name Elo+- games score oppo. draws 1 d3p 2016 77 7521 52% 20000% 2 base 2000 75 7721 48% 20160% - Don -H ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
Don Dailey wrote: You are right, the d3p version rallied to come from behind and staged an exciting and dramatic comeback: Rank Name Elo+- games score oppo. draws 1 d3p 2016 77 7521 52% 20000% 2 base 2000 75 7721 48% 20160% - Don If you'd like to try a simple pruning scheme that improves playing strength on 19x19, then I'd suggest progressive widening. It only works in the tree, not in the playouts. You don't need complex patterns for progressive widening to work. You can simply use distance to the previous move. Search moves at distance 1 from the previous move for N playouts. Then add moves at distance 2 for N*x playouts. Moves at distance 3 for N*x*x. N and x are the two parameters that need tuning. I expect you can get tremendous strength improvement on 19x19 with this simple scheme. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Wed, Dec 31, 2008 at 12:25:10AM +0100, Rémi Coulom wrote: If you'd like to try a simple pruning scheme that improves playing strength on 19x19, then I'd suggest progressive widening. It only works in the tree, not in the playouts. You don't need complex patterns for progressive widening to work. You can simply use distance to the previous move. Search moves at distance 1 from the previous move for N playouts. Then add moves at distance 2 for N*x playouts. Moves at distance 3 for N*x*x. So, you'd be playing like a beginner, with a local answer to every move the opponent makes. Never taking sente to play elsewhere. Sounds like a receipe for a disaster to me. But then again, I am only a kyu-level player, so I may be wrong... -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
On Wed, 2008-12-31 at 00:25 +0100, Rémi Coulom wrote: Don Dailey wrote: You are right, the d3p version rallied to come from behind and staged an exciting and dramatic comeback: Rank Name Elo+- games score oppo. draws 1 d3p 2016 77 7521 52% 20000% 2 base 2000 75 7721 48% 20160% - Don If you'd like to try a simple pruning scheme that improves playing strength on 19x19, then I'd suggest progressive widening. It only works in the tree, not in the playouts. You don't need complex patterns for progressive widening to work. You can simply use distance to the previous move. Search moves at distance 1 from the previous move for N playouts. Then add moves at distance 2 for N*x playouts. Moves at distance 3 for N*x*x. N and x are the two parameters that need tuning. I expect you can get tremendous strength improvement on 19x19 with this simple scheme. I'm not sure I understand - when you say N playouts, do you mean N visits of that node? Because once you visit a node, you expand it, no longer doing playouts from that point. For instance if e5 is played (from the root position) are you saying we would only look at the moves touching e5 the first few times e5 was visited, then start looking at distance 2 for a while, and so on stopping after 3? The reference bot of course does not build a tree, what I'm actually looking for is a way to produce a medium strength but really simple bot that does not build a tree and just has a lot of playout magic. I wonder if this behavior can be emulated in the playouts somehow? It's not so simple because we are not expanding a tree, and when we look at some moves more often than others we get more statistical noise in the moves we don't look at, and this can make them look artificially good or bad. I can definitely see how such a scheme would work well in the tree. - Don Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 3-4-5 rule
Don Dailey wrote: I'm not sure I understand - when you say N playouts, do you mean N visits of that node? Because once you visit a node, you expand it, no longer doing playouts from that point. Yes, I mean N visits. In my view, every playout starts at the root. For instance if e5 is played (from the root position) are you saying we would only look at the moves touching e5 the first few times e5 was visited, then start looking at distance 2 for a while, and so on stopping after 3? Yes, except that you would not stop after 3. Continue at distance 4, then 5, etc. This guarantees that in the limit of infinite thinking time, this algorithm would be optimal. The reference bot of course does not build a tree, what I'm actually looking for is a way to produce a medium strength but really simple bot that does not build a tree and just has a lot of playout magic. I wonder if this behavior can be emulated in the playouts somehow? It's not so simple because we are not expanding a tree, and when we look at some moves more often than others we get more statistical noise in the moves we don't look at, and this can make them look artificially good or bad. I can definitely see how such a scheme would work well in the tree. - Don Oh, sorry, I thought your program was an UCT bot. If you build no tree, then progressive widening probably does not help much. I am not sure. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 3-4-5 rule
After 842 games with 19x19 go the version with the 3-4-5 line rule is scoring about 55% I thought it might do better, I think the rule is reasonably sound - but 55% is pretty respectable for such an easy change and it hardly slows down the search at all. Rank Name Elo+- games score oppo. draws 1 d2p 2037 12 12 842 55% 20000% 2 base 2000 12 12 842 45% 20370% ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
