Denis, 2009/12/4 Denis fidaali <[email protected]>
> o much complexity could be removed by not maintaining atari status for > strings (especially for capturing moves) > but atari information is essential for my move generation algorithm > (to disallow suicides, etc) > question: does the "do not play in your own eye" selection rule > require atari information? (my guess is yes) > follow-up question: do you maintain atari status incrementally or > determine it on demand? > > - It first depends on what you call an eye. At least some bots use > pseudo-eyes. Which does not need any information about liberties and status. > Basically : if it is empty and surrounded by friendly stones, it is a > candidate. Then check if it looks like a false eye. If not, this is a pseudo > eye. > This a very good approximation of an eye. And prevent the problem of not > connecting, when a participating string is in atari. I think most fast light > implementation use this definition. > Let me clarify the question and my approach. My move generation scheme first selects all "strictly legal" move candidates, then filters out "unwanted" moves. "Strictly legal" refers to all the empty points that provide at least one liberty to a friendly group if a friendly stone would be placed on that point. The liberty can be provided (i) by an empty neighboring point, (ii) by a capture of a neighboring enemy string (i.e., a neighboring enemy string that currently is in atari), or (iii) by connecting to a neighboring friendly string that is not currently in atari (otherwise I just played on its last liberty). Both the second and third criterion require knowledge of the atari status of strings. "Unwanted" moves (in my case) are eyes or half-eyes, i.e., moves that are "currently" suicide for the enemy. These are empty points that are characterized by (i) not having empty neighbors, (ii) not have enemy neighbors, and (iii) not have neighboring friendly strings in atari. The last criterion again requires atari knowledge. (There are known drawbacks for this "eye" definition, but that is another discussion alltogether.) The second part of the move generation can be replaced by the "do not play in your own eye" rule. This typical implements an (overly) conservative definition of an eye. It requires four direct neighbors to be of one color and at most one (none for edges/corners) of the corners missing, as you describe. This definition does not rely on atari knowledge, I understand that. However, the question remains for the first part of the move selection, which determines which move candidates are considered "strictly legal". One way around it is to consider "all" empty points as "strictly legal" and deal with the fallout elsewhere. To reduce single-stone suicide moves, you can filter enemy eyes in the second step. This does not handle hlaf-eyes, those need to be dealt with later. What also still remains are move candidates that result in multi-stone suicide. I convinced myself that an early version of libEgo quietly ignored the violation of multi-stone suicide or replaced it by "try-to-play" and "undo-if-wrong" approach (and eliminate that point from consideration down the road, or at least until a capture happens). I have also seen Don Daley, among others, advocate this approach on the mailing-list. It is my belief that if you wish to filter out multi-stone suicide move candidates upfront, you actually do need to maintain the atari status for all strings. So, to rephrase my my question, how do others deal with move candidates that are single-stone suicides on half-eye points, or multi-stone suicides? - I checked (very quickly) your code. What would help non cpp speakers like > myself, would be an overview of your algorithm. I think there is a probably > a lot of ways to implements bitmap playout (i tryed at least two very > different ones). So a quick description of the key principle (like your > definition of an eye in the "do not play in your own eye" rule would be > neat. > I agree with you that the documentation can be improved upon and will try to work on it. The file "doc/readme.txt" has some information already. You put this commentary right above the scoring method > /** > * assumptions > * all occupied points are considered alive > * black territory cannot have white neighbors > * no seki > */ > I don't think you should need the "no seki" hypothesis for scoring. I think > most use the following scoring policy : > If an empty intersection is surrouded by friendly stones (no adjacent > ennemy or empty intersection), then this is a point for the surrounding > collor. > Any point occupied is a point for the corresponding color. > If you score a final position, and there is a seki, this policy should > give you correct chineese-scoring. > I am using the definition as you describe to account for territory. And, my move generator guarantees there to be no seki's in the playouts. But you are correct that this assumption is an unnecessary restriction for scoring. The advantage it provides is that one needs to only count a single color, and can assume that the remainder of the board belongs to the other color. Therefore, it is almost twice as fast. On the other hand, counting is taking hardly any time (~30 cc out of ~25,000 cc), so doubling it is almost for free. I should follow your suggestion. That still leaves open the more difficult task of classifying eyes larger than 1 point (also guaranteed to be non-existent with my move generator). René PS. I have received confirmation that everything works correctly with g++ under Linux_64 on a different Intel processor. That's better than the previous version. Please let me know what does (not) work for you !
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
