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):
- 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 + 1, position + 1) low_x = current_position - 1 high_x = current_position + 2 low_y = current_position - 1 high_y = current_position + 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.