On Thu, May 10, 2012 at 1:32 PM, folkert <[email protected]> wrote: > What I mean is: say you've got a piece of board with a circle of stones > on it. Now what I've read is that one should not place stones in such a > circle. So the question is: how do you guys detect this? > Also see my question on > http://stackoverflow.com/questions/10531279/check-if-a-point-is-in-a-polygon-which-is-partially-open > which is about this problem I'm trying to describe.
Let me start with a joke. An engineer and a mathematician take part in a contest where they are asked to surround as much land as possible with a certain amount of wood. The engineer comes out with a svelte fence design and manages to surround 2 hectares. Very impressive. The mathematician then builds a tiny fence around himself and defines his side of the fence as "out". Back to go, the diagram on the stackoverflow post suggests that you are trying to identify the surrounded areas of the board. Keep in mind that what is "inside" and what is "outside" is somewhat arbitrary, as illustrated by the joke. For instance, imagine a chain connecting the North and the South of the board. Which side is in and which one is out? You can slowly move a configuration where in and out are clear into the one I just described, so the definition will break down at some point. Perhaps it's better to simply think about "connected components", even though typical positions contain one large one that most people would consider "outside". So you are trying to compute the connected components of the graph formed by the non-black (say) points on the board. Several algorithms to solve this problem are discussed here: http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29#Algorithms But if you are simply trying to stop your random playouts from plugging their own eyes, listen to Rémi. Álvaro. _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
