How to efficiently update restricted pieces in the game of Hive?

Question

I am making an engine for the game of Hive (https://www.gen42.com/games/hive) in C++ and I need it to be highly efficient as I will have an AI searching through many thousands of positions. Note that it is not essential to be familiar with Hive to answer this, as this question is more related to graph theory. There is an example at the end.

Representation

In the game of Hive, pieces can be placed and moved around on an infinite hexagonal grid. There is a crucial rule, the One Hive Rule, that states: The pieces in play must be linked at all times (i.e., the Hive may never be broken)

In other words, the hive can be represented as a connected undirected planar graph, where:

• The vertices are the pieces

• The edges are the connections between adjacent pieces

The articulation points of this graph represent pieces restricted by the One Hive Rule. Also, no vertex can have more than six edges. (pieces on top of the hive are not included in the graph)

Problem

The problem I have is recalculating these articulation points efficiently after the graph is changed and I am wondering if there is some efficient data structure that could handle this.

Specifically, the data structure would need to accommodate the following updates:

• Add a vertex to the graph along with its connecting edges (i.e., placing a piece/moving a piece to its new location)

• Remove a vertex from the graph along with its connected edges (i.e., removing a piece when it is being moved to a new location)

When queried, the data structure would return which vertices are articulation points.

Also note that the graph begins empty, and the number of vertices can never decrease. (pieces cannot be removed from the hive)

Ideas

I am aware of algorithms like Tarjan’s which calculate the articulation points of a graph in a single DFS traversal. However, most of the time in Hive when a piece is moved, only a few pieces become restricted/unrestricted by this rule (usally no more than 2), and therefore only a few vertices in the graph should have to be updated. (rather than re-traversing the entire graph every time)

Can anyone provide me with an efficient data structure and/or algorithm for this?

Example

(You don’t need to know how the pieces move)

In the current position, the white ant (blue) is about to move to the location south-east of the black bee (yellow). In the graph, I have shown in dark blue the updates that would be required.

The vertices in the graph circled in red are articulation points (immobile pieces). Also note that after the ant has moved to its new location, the vertex corresponding to the black bee will also become an articulation point.

Example Image

Answer 1

A block-cut tree may be useful in solving the problem, but more to the point of this answer, it may help you understand that there is no easy solution to the problem.

Consider the graph shown below (source:wikipedia with modifications in color)):

The graph with 18 vertices (black) is shown on the left. The corresponding block-cut tree is shown to the right. Notice that the cut points (aka articulation points) are considered to be part of the blocks that they connect. So for example, cut point 1 (C1) in the tree, which is vertex 2 (V2) in the graph is a member of blocks B1, B2, and B3.

I propose to add vertex 19 (magenta), and then consider the consequences. I've circled the cut points in the graph. Those circled in red (V2, V8, and V10) remain as cut points when V19 is added. But V7 (aka C2) ceases to be a cut point when V19 is added. That's because C2 in the block-cut tree is part of a cycle that is created by adding V19. And unlike C1, C3, and C4, it doesn't connect to any blocks that aren't part of the cycle. It only connects B3 and B4, which are both part of the cycle.

So after adding V19, there are only 4 blocks and 3 cut points. B2, B5, and B7 continue to exist as separate blocks, connected by C1, C3, and C4 respectively. B1, C1, B3, C2, B4, C3, C4, and B6 are now all part of a single large block. The resulting block-cut tree is shown below (source:ibid with modifications in color):

Finally getting to the point, notice that V7 is about as far away from V19 as it can possibly be. So the effects of adding a vertex aren't localized to the neighbors of the added vertex. The effects can propagate throughout the graph.

And then it gets worse.

We've seen the effects of adding a vertex. Now consider the reverse. After adding V19, the player decides to move the piece that V19 represents, thereby removing V19 from the graph. Suddenly, block B19 explodes into four blocks (B1, B3, B4, and B6), and C2 appears as a cut point. Basically restructuring the entire block-cut tree. So by the time the code finds the newly formed cut point, and rearranges the block-cut tree, it may have been possible (or even faster) to run Tarjan's again.