Hex boardgame with fast random rollouts (OpenAI gym framework) I implemented the boardgame Hex using the OpenAI gym framework with the aim of building a bot/AI player that can learn through self-play and expert iteration (details Note: not my paper; I am merely reproducing it).
The initial agent uses Monte-Carlo tree search (MCTS), and I will compare myself against it to evaluate the strength of different bots. MCTS involves simulating the game with random moves (called a rollout) and this is done A LOT (&gt;1,000 games played per move in the actual game), so this rollout speed matters to me. Indeed, when I profile my code, the bottleneck is said rollout, and, more specifically, the test if the game has ended.
Currently, I check if the game is finished using the following mechanism (I'm sure there is a name for it, but I don't know it):

Pad the board with 1 extra row/column and place stones on the west/east side (player white/blue) or north/south side (player black/red) (cached at the start of the game)
Find all the connected regions for the current player (cached from previous turn)
Place stone on board
check neighborhood of stone and (a) start new region if unconnected, (b) add to the region with lowest region index
if multiple regions are in the neighborhood, merge them with the region that has the lowest index

I assign index 1 to the stones in the north/west (black/white) padding, and can then efficiently test if the game is over by checking the south-east corner. If it has region index 1, it is connected to the opposite side and the game has finished.
The full code of the game is available on GitHub together with a MWE that performs a random rollout. It's not a big repo (maybe 500 lines). The critical function is this one
    def flood_fill(self, position):
        regions = self.regions[self.active_player]

        current_position = (position[0] + 1, position[1] + 1)
        low_x = current_position[1] - 1
        high_x = current_position[1] + 2
        low_y = current_position[0] - 1
        high_y = current_position[0] + 2
        neighbourhood = regions[low_y:high_y, low_x:high_x].copy()
        neighbourhood[0, 0] = 0
        neighbourhood[2, 2] = 0
        adjacent_regions = sorted(set(neighbourhood.flatten().tolist()))
        adjacent_regions.pop(0)

        if len(adjacent_regions) == 0:
            regions[tuple(current_position)] = self.region_counter[self.active_player]
            self.region_counter[self.active_player] += 1
        else:
            new_region_label = adjacent_regions.pop(0)
            regions[tuple(current_position)] = new_region_label
            for label in adjacent_regions:
                regions[regions == label] = new_region_label

with the most expensive line being adjacent_regions = sorted(set(neighbourhood.flatten().tolist())). I'm wondering if this can be implemented in a nicer way, either by using a different algorithm or vectorizing the code more, more intelligent caching, ...
Of course, I'm also happy with any other comment on the code.
Disclaimer: I found a basic hex implementation in an old commit in the OpenAI gym repo, which I used as a base to work off. Most of the code has changed, but some of it (e.g., the render function) I did not write myself.
When reading this function alone, without any surrounding code, I wonder where the initial + 1 for the position comes from. That looks like an off-by-one bug to me. I don't know whether it is indeed a bug, it's just suspicious.
The calls to tuple() look redundant since the current_position already is a tuple. Doesn't your IDE warn about such things?
The word position is a bad name since it is ambiguous. It could either mean an (x, y) tuple or the complete (board, player_to_move) tuple, like in the sentence &quot;in this position, Red should resign&quot;. A better name would be last_move or prev_move.
Is there a good reason why you use a tuple at all? Having two variables x and y would make the code pretty clear. These variable names are short enough that you don't need the low_x and related variables anymore.
Do you need the call to tolist() at all?
Instead of generating a 2-dimensional matrix, it could be more efficient if you just took the 6 neighbor regions explicitly and individually. That way you also get rid of the pop(0). I don't know whether that is faster in Python though.