Hex棋游戏中最快的胜负判定方法探究

我正在实现Hex棋游戏，胜负规则如下：玩家1连接棋盘左右两侧即获胜，玩家2连接棋盘上下两侧即获胜。游戏中采用六边形邻接模式，每个单元格的相邻位置为(i-1,j), (i,j-1), (i+1,j), (i,j+1), (i-1,j+1), (i+1,j-1)。

我已经用Python实现了基于BFS的胜负判定算法，但想知道是否有更优的方案。比如DFS或者其他算法会不会比BFS更快？另外我也曾尝试用Union Find（并查集）来实现，但因为要开发AI判断下一步是否能获胜，需要创建大量不相交集合，导致这个方案难以落地。我考虑给Union Find添加移除元素的方法，这样只需要维护一个不相交集合，但不确定该如何实现，也不清楚这种改进后的Union Find是否比BFS更快。

以下是我当前的BFS实现代码：

from collections import deque

def check_win(matrix, player):
    queue = deque()
    visited = set()
    if player == 1:
        for r in range(len(matrix[0])):
            if matrix[r][0] == player:
                queue.append((r,0))
                visited.add((r,0))
        while queue:
            r, c = queue.popleft()
            if c == len(matrix) - 1:
                return player
            for x, y in ((r-1,c), (r,c-1), (r+1,c), (r,c+1), (r-1,c+1), (r+1,c-1)):
                if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == player and (x,y) not in visited:
                    queue.append((x,y))
                    visited.add((x,y))
        return 0
    else:
        for c in range(len(matrix[0])):
            if matrix[0][c] == player:
                queue.append((0,c))
                visited.add((0,c))
        while queue:
            r, c = queue.popleft()
            if r == len(matrix) - 1:
                return player
            for x, y in ((r-1,c), (r,c-1), (r+1,c), (r,c+1), (r-1,c+1), (r+1,c-1)):
                if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == player and (x,y) not in visited:
                    queue.append((x,y))
                    visited.add((x,y))
        return 0

以下是一个玩家获胜的棋盘状态示例：

board = [[0, 0, 2, 1, 0],
         [0, 0, 1, 0, 2],
         [2, 0, 1, 0, 0],
         [0, 1, 0, 0, 0],
         [1, 2, 0, 0, 1]]

内容的提问来源于stack exchange，提问作者Jonathan Helgesen