Hex boardgame with fast random rollouts (OpenAI gym framework)

Question

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 (>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):

1. 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)
2. Find all the connected regions for the current player (cached from previous turn)
3. Place stone on board
4. check neighborhood of stone and (a) start new region if unconnected, (b) add to the region with lowest region index
5. 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.

Answer 1

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 "in this position, Red should resign". 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.

Answer 2

Without the profile numbers you have, I can't suggest changes that make assumptions about the input to the function. For instance, if you knew that most times the 'check if the game is over' fails, you could only run the check once the player has a piece in every row and a piece in every column. I will also be picking off small things, as I don't know what specific parts of the function are too slow. The changes below are a little agnostic to your code in a sense, and might not help all that much.

---

As a personal preference, I don't like code that makes liberal use of indexing. I find it is often harder to read than it needs to be.

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

There is a little bit of unnecessary adding and subtracting here. You can simplify it a little.

low_x = current_position[1] - 1
low_x = position[1] + 1 - 1  # Replace current_position[1] with its definition: position[1] + 1
low_x = position[1]

and the same holds for the other variables here

current_position = (position[0] + 1, position[1] + 1)
low_x = position[1]
high_x = position[1] + 3
low_y = position[0]
high_y = position[0] + 3

Since position is indexed into a few times, it makes sense to unpack it. I would also remove low_x and low_y since they already have (sensible) names; x and y.

x, y = position
current_position = x + 1, y + 1
low_x = x
high_x = x + 3
low_y = y
high_y = y + 3
neighbourhood = regions[low_y:high_y, low_x:high_x].copy()

Then there is no point in keeping the variables low_x, low_y, high_x, or high_y. They don't add any clarity and are not used anywhere else.

x, y = position
current_position = x + 1, y + 1
neighbourhood = regions[y:y+3, x:x+3].copy()

This code now has magic constants x+3 and y+3. I don't know where they come from, a comment explaining it would be nice.

---

adjacent_regions = sorted(...)
adjacent_regions.pop(0)

if len(adjacent_regions) == 0:
    ...
    ...
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

I've removed anything that doesn't pertain to adjacent_regions. From this I noticed two things.

The list structure is popped from the front once or twice. Usually lists have O(n) complexity when popped from the front, as it needs to make changes to everything in the list. Even though it might not be a long list, it is still a complexity smell that we should try to avoid.

A quick fix would be to sort the list in reverse, and pop from the end rather than the start. In this case, as I don't seen adjacent_region exposed outside of the function, we can avoid modifying the list instead. Not popping from the front, and accounting for the extra element, the code might look something like this:

adjacent_regions = sorted(...)
# adjacent_regions.pop(0)  # REMOVED

if len(adjacent_regions) == 1:  # Empty other than the '0' label
    ...
    ...
else:
    # Ignoring the first element, this becomes .pop(1)
    # Then changed .pop to a simple __getitem__
    new_region_label = adjacent_regions[1]
    regions[tuple(current_position)] = new_region_label
    for label in adjacent_regions:
        regions[regions == label] = new_region_label