[computer-go] string criticality?
Rémi Coulom offers a formula for the criticality of point x. (Criticality: a Monte-Carlo Heuristic for Go Programs) Criticality being a measure of how important holding x is for winning. c(x) = v(x)/N - (w(x)/N * W/N + b(x)/N * B/N) N: number of playouts W/B: playouts won by white/black w(x)/b(x): playouts where x is owned by white/black v(x): playouts where x is owned by playout winner I'm prepared to believe that this formula is a meaningful measure of covariance. The way I understand it, moves with a high criticality value are given a better chance of being tried. Seems logical to me. I just wonder if something similiar couldn't also be used to identify the importance of strings allready played. There would be 2 levels of criticality: 1. How important is the string for winning the game? 2. How important are points in the vicinity for attacking/defending this string? (possibly with ordering information) I'm not sure if the above formula should be used or if it should be something asymmetric. Unlike point criticality there is a preestablished owner for a string. There will be a tendency that losing a string will be more harmful for the defender than not capturing will be for the attacker. Stefan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] string criticality?
Stefan Kaitschick wrote: There would be 2 levels of criticality: 1. How important is the string for winning the game? 2. How important are points in the vicinity for attacking/defending this string? (possibly with ordering information) Few months ago I tested it without success. String criticality seems a nice idea, but how should it be implemented? Just giving high priority to the liberties does not work, because that cannot be distinguished from the simple dame-filling. Can you suggest a concrete formula? -- Yamato ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] string criticality?
Few months ago I tested it without success. String criticality seems a nice idea, but how should it be implemented? Just giving high priority to the liberties does not work, because that cannot be distinguished from the simple dame-filling. Can you suggest a concrete formula? -- Yamato a shot in the dark: 1. How important is the string for winning the game? Using Rémi Couloms' formula c(s) = v(s)/N - (w(s)/N * W/N + b(s)/N * B/N) N: number of playouts W/B: playouts won by white/black w(s)/b(s): playouts where s is owned by white/black v(s): playouts where s is owned by playout winner 2. How important are points for winning the string? In a semiai situation there are no critical points(ignoring eye making/destroying) Each side has its own valuable points, playing the opponents move is usually catastrophic. This should actually make it easier to find these points. They should be as good for one side as they are bad for the other. (Or worse, consider making your own large eye smaller) something like this(a little Bayes): P(C|X) = P(X|C) * P(C) / P(X) P(C|X): chance that the string will be captured if x is played by any side P(C): string_captured_count / N P(X): x_not_empty_count / N P(X|C): x_not_empty_when_string_captured / string_captured_count value 0: perfect defense value 1: perfect offense The moves of one side can be dependant on each other because they might have to be played in a certain order. This interdependence could be quite expensive/difficult to find. But ignoring it will indeed reduce string criticality to normal dame filling. So my suggestion is this: completely order the moves for both sides. This way interdependencies don't have to be explicitly analysed. A move that needs to be played earlier should get a higher rating naturally. The trick would be to allways impose this order, even if it doesn't actually exist. If the criticality of a string is high, it would try to suppress these moves in any other order. My hope is that this would alleviate an unfair permutation advantage by the losing side. Stefan ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] string criticality?
Maybe it would be good enough to only update the string criticality first. More expensive calculations for the found critical strings could kick in later. You asked for a formula, and I tried to comply, but its really only conceptual. Also there will still be points that are good for both, taking a liberty or extending by 2 liberties for example. The central idea would be to discourage permutations of dame-filling moves. The ordering criterea might not have to be so precise. Stefan - Original Message - From: Yamato yamato...@yahoo.co.jp To: computer-go computer-go@computer-go.org Sent: Monday, September 14, 2009 5:08 PM Subject: Re: [computer-go] string criticality? Stefan Kaitschick wrote: something like this(a little Bayes): P(C|X) = P(X|C) * P(C) / P(X) P(C|X): chance that the string will be captured if x is played by any side P(C): string_captured_count / N P(X): x_not_empty_count / N P(X|C): x_not_empty_when_string_captured / string_captured_count value 0: perfect defense value 1: perfect offense Well, it should work theoretically but seems very expensive for the processor. When we have this information, do we have to update every node value for every string every time? -- 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] string criticality?
Maybe from a different angle, but maybe you remember me writing about 'stone-age'. Basically what it did was assuming strings created during the playout are less critical than existing strings. I used this to limit my tactical search by a great deal by not doing any search on 'new' strings. This didn't affect strength in any way I could measure, but it reduced the overhead of tactics ( I don't remember exactly, but I think it cut in half). I think the single most useful information about strings or groups would be whether it has two eyes. Unfortunately I haven't been able to think of a cost-effective way to compute that yet :) Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] string criticality?
Stefan Kaitschick wrote: There would be 2 levels of criticality: 1. How important is the string for winning the game? 2. How important are points in the vicinity for attacking/defending this string? (possibly with ordering information) I like this idea. I'd also forgotten about the point criticality formula, but that also sounds like a very good way to extract useful information out of the playouts. Yamato wrote: Few months ago I tested it without success. String criticality seems a nice idea, but how should it be implemented? Just giving high priority to the liberties does not work, because that cannot be distinguished from the simple dame-filling. Hhmmm, I see. How about this: (First, string criticality needs to be converted into group criticality. Adjacent critical strings that are near each other should be treated as one unit, with their criticality number merged. Note: this is not the traditional group definition. If only the tail of a big group is critical, then only that tail string is the group in the below algorithm.) In 9x9 games there are three main types of game: i) strong groups quibbling over the territory boundaries; ii) one weak group trying to live, and the game depends upon it; iii) big semeai (usually involving all stones on the board). I think the string criticality idea allows us to distinguish between these three types. And then perhaps use a different pattern database or move selection strategy. Beyond that it may not be very useful though, as some radius of critical groups will tend to cover most of the board. I think the idea could really shine in 19x19 by discovering if there is key fight, whether life and death or semeai, and allowing the playout to focus on that fight. Use as follows: 1. If one group is much more critical than any other: Give high weight to defending moves for it (*); Give medium weight to attacks (*) against neighbouring enemy chains. (i.e. hunting for forcing moves that also strengthen the weak group) Give very low weight to all other moves. 2. Elseif 2 to 4 groups are critical and adjacent: Give high weight to all attack/defense moves (*) of those groups; Give very low weight to all other moves. 3. Else fall back on usual move selection. *: Simplistic move generation is: all 1st and 2nd order liberties. Alternatively have pattern libraries for things like: moves to make weak groups live, sente forcing moves against chains, etc. In other words, use string criticality non-linearly: if it discovers very critical groups then change the whole game plan, otherwise don't have it contribute at all. Quite a rapid decay of their importance is called for: my guess would be a linear decay of the weight, down to zero contribution 10 moves into the playout. 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/
