Havannah bots recognize rings

When bots started playing Havannah here, the topic of ring-threat recognition algorithms came up. I've been thinking about it off and on for the last however many years it's been. What algorithms are used by the various bots here?

The best I've thought of for ring recognition is

# Keep track of chains, defined as the contiguous sets of cells occupied by same-colored stones.
# Within a chain the "peripheral" cells are the ones that are on the border of the board or have a neighbor cell not occupied by a same-colored stone. A chain that includes a non-peripheral cell is already a ring.
# A newly placed stone can form a ring only if it has at least two of its 6 (or fewer) neighbors that belong to the same chain. It forms a ring iff either
## Among its neighbors, there are two distinct sets of contiguous stones that belong the same chain or
## The new stone converts at least one neighbor from peripheral to non-peripheral.

Your approach is close to what Lajkonik does. His chains are bit masks that reflect the cells occupied by the stones of this chain. Every occupied cell points to its chain. Empty cells contain null pointers.

Putting a stone on the board entails one of three cases:
# The stone is isolated from other stones of the same player - create a new chain for it.
# The stone is adjacent to one chain of the same player - merge it into the chain.
# The stone is adjacent to two or three chains of the same player - replace them with a new chain, being their union.
In cases 2 and 3, after the merging, six nearest neighbors of the affected cell are read *from the resulting chain*. As a six-bit number, they serve as an index to a predefined lookup table, whose entries look like

000000: no

000001: no

000010: no

000011: no

000101: yes

000110: no

000111: check the three cells behind the neighbors 4,5,6

etc.

The last case shown detects closing six-stone rings with a seventh stone inside, like below.

 . * *
. # * *
 . * *

As far as I know, Castro uses a different technique. See "page 38 of Timo's thesis":http://havannah.ewalds.ca/thesis.pdf#page=53.

In order to keep working sets small, I prefer to not save extra information about chains. Instead:

Definition: Let c be the color of a stone. (That is white or black). A field f is not c-isolated if there is a sequence (f.0=f, ..., f.k-1) such that
- f.i and f.i+1 are neighbours
- f.j is not occupied by a stone of color c (could be very well occupied by a stone of a color that is not c)
- f.k-1 is either a border or a corner field.

(Lemma: Border and corner fields are not c-isolated for arbitrary c.)

Lemma: Using a depth first search, we can check in space less than 6*diam(board) and in time less than 6*fieldcount(board) whether or not a field is c-isolated.

Claim: It will be faster to actually perform the dfs within the cache instead of saving, maintaining and accessing extra information about chains in memory.

Lemma: Putting a stone of color c to field f closes a ring if
- there is a neighbour of f that is occupied by a stone of color c and has six neighbours that are also occupied by a stone of color c (the ring with 7 stones and diameter 1), or
- there is a neighbour of f that is c-isolated.

The good news is, that the question whether or not a put closes a fork or bridge can be answered also by a very similar dfs. So after all, the decision if a put finished a game can be drawn with one dfs (for fork/bridge) and at most 6 more dfs for ring detection.

Using this approach, a program can tabularize size 3 (with 19 cells) in 44 seconds on one 2.66 GHz core of my laptop. This includes the evaluation of 90814537 normal forms of which 16578814 are unique, the calculation of the normal form after each put and the maintenance of the game cache.

Significant improvement in speed is still possible: Please note, that for a fixed board size, the dfs can be "unrolled" to a piece of code
- that accumulates the border/edge connectivity,
- that has no branches and therefore will be executed very effectively also on machines with instruction pipelines and
- that uses bit operations only and therefore is well suited to use SIMD extensions.
Moreover, the 6 ring dfs could be collapsed to a single one which works bottom up.

FatPhil is right, this is an exercise in programming, not in understanding Havannah. But good engineering may help to advance there.

Well, that's a different approach.

> no branches

No branches means no early return, but it's faster because of in-cache and/or parallel execution, eh?

yes, exactly. maybe one should query for early return from time to time but then always give hints about the expected outcome to the branch prediction unit such that the pipeline stays populated with useful instructions when there is no early return.

You should read Timo's entire thesis -- it's good work. IIRC, he has an O(1) incremental check for rings, and a fast detection algorithm (and good engineering throughout).

One of the large improvements in Castro came from turning off ring checks for deeper search. The rollouts get misled by ring wins, because rings are more probable from random play than other win conditions. And not checking for rings is *very* fast... ;-)

I read it, good piece of work indeed. The O(1) ring check calls 'find_ring' which basically follows a chain of stones of the same color. It is fast since Timo saves the group membership per cell (the parent). This is exactly the difference I mean: Store, maintain and access some extra information or keep the working set as small as possible and recalculate things.

[BTW, the dfs sketched above also is O(1) for a fixed board size.]