[Python] How to implement a recursive distance function for Hex game AI evaluation?

I'm working on a Hex game AI that uses the alpha-beta pruning algorithm, and as part of evaluating the board state, I need to calculate the distance between two cells (u and v) on the board. More detailed information about this distance calculation can be found in a paper (see pages 14–17).

To simplify, my main challenge is how to compute this distance metric for the evaluation function.

Conceptually, this boils down to calculating the distance between two cells (u and v) on a custom graph, I think its similar to BFS, DFS, or Dijkstra’s algorithm — but implemented recursively.

-the Graph to calutate the distance from u to v-

There are two key components for calculating the distance:

-example of N(u) that have been shaded-

1. 
   Neighborhood of a cell u (denoted N(u)): This is not the classical neighborhood you’d find on Wikipedia. Instead, it depends on the current board state and changes dynamically. The neighborhood consists of:
   
   • The immediate neighbors of u.
   • If u is connected to occupied cells on the board, include their neighbors as well.
   • If u is connected to virtual nodes on the board, include their neighbors too.
2. 
   The distance function itself, which I’m struggling to implement.
   

-the distance function-

The function c_k(u, v) returns the number of cells in the neighborhood of u whose distance to v is less than k:



here is my code from the distance function :


def distancemetric(u, v, player, board, visited=None, memo=None):


if visited is None:
visited = set()
if memo is None:
memo = {}

if u == v:
distance = 0
return distance

neighbors = neighborhood(u, player, board)

if v in neighbors:
distance = 1
return distance

else:
visited.add(u)
min_distance = float('inf')

for k in range (2, 1000):
for w in neighbors:
# print(w)
if w not in visited:
# print("not ", w)
d = distancemetric(w, v, player, board, visited, memo)
print(w, v, d)
if d is not None:
min_distance = min(min_distance, d + 1)

if min_distance != float('inf'):
if min_distance < k:
return min_distance
else:
return None # v not reachable from u


Any help interpreting this function’s definition or guidance on implementing this recursive distance function would be greatly appreciated. Thank you

I tried every technique I know, but they led to exceeding the recursion depth. I also tried an iterative approach and expected a corrected version of the function, but I’ve hit a dead end.And this is my new code with still wrong distance

Continue reading...