Re: computer-go: speculative introspection

[Serge Boisse <boisse@xxxxxxxxxxxx>]

William Harold Newman wrote:

> 
> Actually, I'd be interested even to know how the brain quickly
> recognizes solid connections from A to B:
> 
>  . . . . C . 8
>  A X X X X X 7
>  . . X . X . 6
>  . . . . X . 5
>  . . . X X X 4
>  . . . X . . 3 
>  . . . X X . 2
>  . . . . B . 1
   a b c d e f
> 
First, the eye (the visual circuitry in the brain) sees that B is bottom left
from A. Th the good direction to go from A to B is downright.
Then i think it uses a "blurred" smaller version of the board, to find a path
that then it tries to follow in the real board.
For instance in the above figure the path is "go right, then down" (there is an
equal range of coord difference in x and y), so we arbitrary choose this order).

To find a right path, try a best first search : here you order the possible
directions : from A to B best are right and down, other directions are to
explore only in case of failure. From C to B, the best direction is down,
(because you have more way to do down than left) then left, then up and right
(equally bad).
Of course you have to mark intersections already explored, to avoid cycling.

>From a7(A) to e1(B) :
1 explore right first : b7 : OK, there is a white stone here.
2   then from c7 the best is down : explore c6 : OK
3     but c6 is wrong way (no neighbour at c5 and d6) : backtrack
4   from c7 explore d7: OK
5    from d7 best is down (no way) then right : explore e7 : OK
6     from e7 best is down  : explore e6 : OK
7      from e6 best is down  : explore e5 : OK
8       from e5 best is down  : explore e4 : OK
9        from e4 best is down  : explore e3 : no way
10       from e4 next choice is right  : explore f4 : OK
11        from f4 explore f3 : no way
12        from f4 explore e4 : no way (marked)
13        no way from f4 : bactrack
14       from e4 next choice is left : d4 : OK
15        from d4 best is down : d3 : OK
16         from d3 best is down : d2 : OK
17          from d2 best are right or down we choose right first : e2 : OK
18           from e2 best is down : e1 : OK
19             at e1 we are at pooint B : succeeded !

So we prove that A and B are solidly connected in less than a
total 19 steps. This should take less than your 500 miliseconds !

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.