Havannah - How to get a Computer to Detect a Ring

Greetings.  I'm writing a little utility to help me with my Havannah games, since Triumph is down.  (It won't be as slick... but it might be better than nothing.)

I've already gotten the program to detect when a player makes a bridge and a fork... but believe it or not, I can't seem to figure out a good way (or any way) for the program to detect when a player has completed a ring.

It's trickier than it initially appears.  We, as humans, can glance at a position for a second and determine, of course, if the last move made a ring.  But how to translate that to computer code?

For a few moments I thought I had it.  Simply start with the last move and follow all possible cells that also contain that same color token, and if that path happens to end BACK at the initial token you started with, you have a ring.  For example:

-a-b-c-------

h-----d------

-g-f-e-------

Here "h" wraps back to "a" and we have a ring.

But no, I quickly realized that's not always the case:

-a-b-c-d-e

k-j-i-h-f-

--------g

Here "k" wraps back and connects to "a" but there's no ring here.

Any ideas, in general terms (pseudocode) that could help me figure out a way to get a computer to understand rings in Havannah?

You only need a second condition to what you've already proposed above, so that you find if there is an "eye".

It's sufficient if one of the stones in the ring has an empty neighbour to it's right (if the ring turns right, else neighbour to left). You just have to define "left" and "right", but should be fairly easy when you already found the "direction" of the ring ;)

Thank you Arek, for responding.

Yea, I thought about checking for the existence of an "eye."  Obviously, all rings must have at least one eye.  (Recall this cell that's considered the eye can be empty or it can be occupied with a stone of either color.)

But it's not quite as easy (to me) as you make it sound.  A ring, in theory, can be one very long and winding continuous path, that zigs and zags left and right and up and down and all over the place, stretching out over the entire board.  Such a ring might have many eyes and to determine if a nearby cell is indeed an eye ("inside" the ring) as opposed to that cell just being a cell "outside" the ring, is easier said than done.

What you may try to is to identify these eyes as follows: for each position on the board which is not occupied by player A, expand from that position recursively into any neighboring position that is also not occupied by player A. If you hit a wall, stop. If you are unable to reach a wall, there must be a circle by player A and B has lost.

As an optimization, you only need to expand from the neighboring positions of the last piece that was played.

Combining mootwo's suggestion with the idea that we need to consider filled in hexes:

1.  Loop over each of the (up to 6) positions adjacent to the most recent play.

2.  If it is not filled in by player "A", expand from that position until you reach the edge (not win) or are forced to stop (win).

3.  If it is filled in by player "A", check whether it is not near the edge and all 6 positions surrounding it belong to player "A" (win) or not (not win).

This might be a silly suggestion, but if you’re already checking all paths, isn’t it simply a matter of filtering out paths where you have sharp cornerings? Basically just make sure that the next hex is not also adjacent to the previous one.

@Ed

 A ring, in theory, can be one very long and winding continuous path, that zigs and zags left and right and up and down

I understood that you already have the algorithm to identify a loop without an eye. When you have a loop then for absolutely sure it has ALL the "inside" on one side and ALL the "outside" on another.

If this is trouble to identify which side is "in" and which is "out", then simply check both. If on both sides exists at least 1 cell that is empty or opponent then you have a ring.

\* A crazy corner case would be a ring that is adjacent to board edges all around, then count the edge as empty too :D

A ring that surrounds your own piece is also a ring—it doesn’t have to be surround an opponent’s piece or an empty hex.

For loop identification (I have coded similar thing years ago for finding when a Hex game is over) I think you should start from a given stone and recursively find all adjacent stones of the same color while prohibiting to go back to original. When a stone is dead end then return false, when is the original stone then return true, otherwise return recursively the "search" function.

It branches a lot, but in practice for a Havannah/Hex game is no problem.

@ypaul oh! Then sorry, I did not know that, Im not a Havannah player.

Then it's more difficult:

A pattern starting in stone X is a ring when there exists a collection of adjacent stones C (X is in C) that lead back to X without going backwards AND collections NR and NL (neighbours left and right, that are not in C) are both not empty.

This is definitely doable, but I suppose there must be a better solution that maybe is somehow area-based...

For better understanding what I'm saying:

Adjacent stones are located anti-clockwise at angles: 60, 120, 180, 240, 300, 360/0 (north). Suppose you go north. Then cells 60 and 120 are in NL, and cells 240, 300 are in NR. 180 is the original stone aka backwards.

In very broad terms, I would do something like this:

Find all groups of connected stones for a player.

For each group:

    1) Walk a clockwise path through the exterior stones. Careful with this, there are tricky edge cases. Here are two example paths. In the one on the left, the path will go out and back over the same stones as it goes along the finger and then comes back:

    It's important that the path walk the full exterior of the group.

    2) For each point in the grid, do the following:

        2a) If it's one of the stones on the path, do nothing

        2b) If it's not one of the stones on the path, using the winding number to see if the path surrounds it ( see here ). If the path surrounds it, then there's a ring and the game is won!

To detect black ring:

(1) Let A be the set of all non-black cells, plus black cells with 6 black neighbors.

(2) Find the connected components of A.

(3) If there is a connected component which is NOT adjacent to the edge of the board, then there is a black ring.

Note that the second part of (1) above is necessary to detect black rings which are entirely filled-in with black cells.

Oh, that's a much better algorithm

Ignatius' algorithm seems the best, however it depends on the implementation of "Find the connected components of A", which itself is not yet trivial :)

Am I missing something? Because I thought that my proposal was a lot simpler, and I can't think of any edge cases where it might fail. Just get the list of all loops and check that every other hex is not adjacent to each other in that loop.

In fact, I should add that this is true for every connection: forks, bridges or rings. In any of those connections, sharp corners will contain a redundant cell, so you shouldn't need to check for them at all. Just exclude all connections that contain alternately adjacent hexes and you might decrease the number of connections to check in each board state, although it does add an extra condition.

I had the same problem in the past. Luckily I had contact with Ingo Althofer, and he gave a very simple guideline:

1) Like Arek already stated, you can define the different directions/angles in +/- 60, 120, etc. (translate this to your own implementation).

2) From the stone in the last move, go ONLY in directions 120, -120 or 180 (which means straightforward). And NEVER 60 or -60.  As you can see, the smallest ring is a continuous going of direction 120.

3) As soon as you get back in this way to the starting stone (or some other stone in the chain you built this way?), you know you have a ring!

4) A different situation is when you are starting to analyse some given position. Then you probably will have to do more tests, as you do not know the last move. But that is another story ;).

Indeed, checking only >=120deg connections solves it. Haha, so easy :)

Step 2 may be unclear. The first thing to do is choose one of the stones directly adjacent to the last move (if there is any). The direction in which that stone lies is your direction zero (straightforward). Direction +/- 120 is relative to that zero-direction. When unsuccesful try starting with another adjacent stone (if any) that is NOT part of the chain(s) you already searched.

The fastest algorithm I've seen is the one used by Timo Ewalds (from which I got my version), which uses the fact that a (minimal) path of stones forming a ring never forms an acute inner angle (as stated above).

It can be defined recursively as the following function FIND_RING, where S0 is the last stone played, S is a stone, v an adjacency vector (for any stone S, S + v is one of its neighbours) and D is a set of pairs (stone, vector).

FIND_RING() = FIND_RING(null, null, {});

FIND_RING(S, v, D) = {

if (S = null or v = null or D is empty) {

add pair (S0, null) to D

for each adjacency vector w such that stone T = S0 + w is of the same colour as S0, if FIND_RING(T, w, D) return true

return false

} else {

if (S0 = S) return true

if (D contains (S, v)) return false

else add (S, v) to D

for each adjacency vectors w such that the angle between v and w is between -60° and 60° and such that T = s + w is of the same colour as S, if FIND_RING(T, w, D) return true

return false

}

}.

The condition the angle between v and w is between-60° and 60° can be replaced (to be more general) by v· w > 0 (i.e. the dot product of v and w is strictly positive).

Wow, I see there are a lot of responses since I last checked.  Thanks to everyone who replied.

I figured out a solution last night, while I was lying in bed.  During my lunch hour at work today I started the code and then I finished it up soon after I got home this evening.  It seems to work fine.

My solution is not nearly as elegant as that of Paul's and eobilor's, and if I had saw their ideas earlier I probably would have attempted that algorithm.

The algorithm I came up with is different than anything mentioned so far.  (I just wasn't comfortable with looking for a structure that looped back to the point of origin and then also looked for "eyes."  I didn't think it was necessary and determing what cell or cells may have been eyes, which could be empty or of either color, was confusing to me.)

It dawned on me that with every valid ring, no matter how small of a ring or how large of a ring or what type of a ring it is (circular, oval, winding all over the place, etc.) each cell that's a part of the ring is connected (via the same color token) to exactly two OTHER cells, of which THOSE cells are NOT neighbors themselves.

Sure, some ring structures may contain "extra" cells of the same color that are touching a part of the ring, and these cells, for example, may have three or more neighbors, but these cells can be removed/ignored from the connecting structure and you still have a valid ring.

A connecting cell that's a part of the structure with exactly TWO neighbors that ARE neighbors themselves can also be removed/ignored from the structure.  This cell also doesn't contribute to the ring.

Obviously, if a cell, for example, only has ONE other neighbor, it cannot possibly be a part of a valid ring, and can be also be removed/ignored from the structure.  And a cell THAT cell was connected to, which a moment ago may have had two neighbors that were not neighbors themselves, may now have just one neighbor.  So THIS cell can now be removed/ignored, and so on and so on, recursively.

When you're all done removing and checking cells, if you have a structure left with six or more valid cells (again, a valid cell is one that has exactly two OTHER neighbors, of which THOSE cells are NOT neighbors themselves) it must now, by definition, be a valid ring.  You don't even have to check to see if it loops back and connects to the point of origin.  It must.

And as you're removing/ignoring cells from your structure, when you're down to five cells, you can stop right there because what's left could not possibly be a valid ring.

So far every position I've tested this algorithm with works.  Valid rings are identified as such, and structures that have lots of similarly colored cells all nearby but are not rings, are not identified as a ring.

I suspect one could come up with several other algorithms.  And if I was writing a bot I'd want the fastest one possible, to leave more time for the evaluation function.  Since that's not my goal, my solution works for me.

Again, thanks to all who replied.

FWIW, Lajkonik detects moves that close a ring in a different way. Every stone knows the chain it belongs to. A move closes a ring if either condition is true:

1.  Among the six surrounding cells, there are two cells containing stones from the same chain (of the same color as the played stone) separated by at least one empty cell or opponent's stone.
   
2.  It closes a 7-stone "blob": among the six surrounding cells, there are three consecutive stones from the same chain (of the same color as the played stone), and the three stones behind them have the same color as the played stone.
   

My implementation of this logic uses separate 2D arrays for each player's stones, with sentinels around the actual board, and a static look-up array indexed by the status of the surrounding cells. Here is the code: https://github.com/MarcinCiura/lajkonik/blob/master/havannah.cc#L368

My Hex/Havannah analysis tool ('AHex') detects a black ring as follows:

If any black stone has black neighbors in all six directions, a ring exists.   Otherwise:

Count all black stones on the board.  Count all non-black (empty or white) cells reachable by iterative expansion to adjacent non-black cells, starting from cells on the edge of the board.  If the sum of these counts is less than the total number of cells on the board, some non-black cells are unreachable from the board's edges and thus must be enclosed in a black ring.

The code is in the function note_winner_havannah in the Javascript at https://minortriad.com/ahex.html

I missed this thread back in August. If I'm not mistaken, all the algorithms so far are linear time or worse. Of course, you cannot beat linear time if the input is just a Havannah board. But for an AI, you likely have the ability to keep a data structure for the board, and you want to check for a winner after each piece is placed. In that case, linear time (in the size of the board) is potentially pretty bad, because you're doing it once per move. You'd ideally want to get this down to constant time per move.

This is possible to do using the "union\-find data structure". See this wikipedia article. Using this data structure, keep track of all the connected components of the black pieces on the board (two black pieces have an edge if they are adjacent, giving a graph). Then, whenever you place a new piece, check if it's adjacent to the same connected component in more than one way (i.e. check the 6 neighbors of the newly placed piece to check if there are (a) two black pieces that (b) are in the same connected component according to the data structure, but (c) are not immediately connected to each other by looking just at those 6 neighbors).

The amortized running time of this approach is O(alpha(n)) per move, where alpha(n) is the inverse Ackermann function and n is the number of moves so far. This is very, very close to being O(1) per move, so it is essentially optimal.

@shalev we miss you in the hex community ;)

@Arek, I'm back in the championship now! Table 2.2. I'm still warming up after not playing so long, trying to remember all the rules of the game

If this has already been covered, excuse me. I read the top several posts and then my eyes started to give out.

You don't need to know what stones are in a ring. You don't need to directly check for a ring at all. Start with an interior hex as a possible eye. Then add each adjacent cell that does not have the target color. (When you're all done, you'll repeat the procedure with the other color.) Continue expanding outward until you either hit the edge of the board (no eye; no ring) or you can add no more hexes (ring exists).