Re: computer-go: speculative introspection

[Kurt Thorn Perkins <thorn@xxxxxxxxxxxx>]

Serge Boisse wrote:

> Alternativelly, if you maintain a "chain" structure in yr programm (everybody
> should implement this, i think), all you have to do is to compare wether A and B
> belong to the same chain or have a same neighbouring chain. This is even faster.
>
> Serge.

I had wondered along these lines. My thought was to instead create an object
to represent a placed stone, and this stone would have a "direct connect" list,
i.e. those stones directly/solidly connected to itself. As another stone is placed
next to it, the representative objects would both add the other's direct connect
list to its own, with operations to sort and uniq the list.

The upside is that you may now determine if "A" is connected directly to "B"
by a relatively simple (and rapid) binary search of this list. The downside is
the potential to end up with a list which may be excessively large, especially
if the plays being made are overly concentrated. <ponder> A shared list
perhaps; when a stone is placed in connection, add its own entries, then
point its own internal list to the "chain's" list, so there is only one list for any

solid group.

I also wondered about where one might put links between stones that are
not actually solid, but are generally considered to be connected due to
the nature of the group (i.e. a bamboo joint, or two stones in diagonal
contact with no other stones occupying the common orthogonal points).
Should these be represented in the method to determine connection? And
if so, should they carry a probability with them, so the program knows
it is not a "solid" connection, but instead one with a certain chance of
being solid (my thought is that, with either of the two groups I suggested
above, a sufficient threat elsewhere on the board might cause the
person/program to not play to connect after the opponent has played a
threatening move to seperate the two halves). In these cases, you would
need to provide for rebuilding the entire connection list upon a stone being
placed, rather than just adding that stone's connections in.

Err... sorry, rather long winded for a delurking post. My apologies if this
has been posed before. Now I'll scurry off for US thanksgiving vacation.

  T