The leading agent on Hex, written by a language model.
import random
import heapq
import time
SIZE = 11
CENTER_DIST = [[0]*SIZE for _ in range(SIZE)]
for r in range(SIZE):
for c in range(SIZE):
CENTER_DIST[r][c] = max(abs(r - 5), abs(c - 5), abs(r + c - 10))
VALID_NEIGHBORS = [[[] for _ in range(SIZE)] for _ in range(SIZE)]
for r in range(SIZE):
for c in range(SIZE):
for dr, dc in [(-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < SIZE and 0 <= nc < SIZE:
VALID_NEIGHBORS[r][c].append((nr, nc))
def get_cost_matrix(board, color, size=SIZE):
cost_matrix = [[0.0]*size for _ in range(size)]
for r in range(size):
for c in range(size):
cell = board[r][c]
if cell == color:
cost_matrix[r][c] = 0.0
elif cell == -color:
cost_matrix[r][c] = float('inf')
else:
friendly = 0
enemy = 0
for nr, nc in VALID_NEIGHBORS[r][c]:
n_cell = board[nr][nc]
if n_cell == color:
friendly += 1
elif n_cell == -color:
enemy += 1
cost_matrix[r][c] = 1.0 - 0.2 * friendly + 0.2 * enemy + 0.0005 * CENTER_DIST[r][c]
return cost_matrix
def single_shortest_path(color, cost_matrix, size=SIZE):
dist = [[float('inf')]*size for _ in range(size)]
heap = []
if color == 1:
for c in range(size):
if cost_matrix[0][c] != float('inf'):
dist[0][c] = cost_matrix[0][c]
heapq.heappush(heap, (dist[0][c], 0, c))
while heap:
cost, r, c = heapq.heappop(heap)
if cost > dist[r][c]: continue
if r == size - 1: return cost
for nr, nc in VALID_NEIGHBORS[r][c]:
step = cost_matrix[nr][nc]
if step != float('inf'):
new_cost = cost + step
if new_cost < dist[nr][nc]:
dist[nr][nc] = new_cost
heapq.heappush(heap, (new_cost, nr, nc))
else:
for r in range(size):
if cost_matrix[r][0] != float('inf'):
dist[r][0] = cost_matrix[r][0]
heapq.heappush(heap, (dist[r][0], r, 0))
while heap:
cost, r, c = heapq.heappop(heap)
if cost > dist[r][c]: continue
if c == size - 1: return cost
for nr, nc in VALID_NEIGHBORS[r][c]:
step = cost_matrix[nr][nc]
if step != float('inf'):
new_cost = cost + step
if new_cost < dist[nr][nc]:
dist[nr][nc] = new_cost
heapq.heappush(heap, (new_cost, nr, nc))
return float('inf')
def count_threat_positions(board, color, size=SIZE):
"""Count positions that create multiple winning threats"""
threat_count = 0
my_cm = get_cost_matrix(board, color)
my_path = single_shortest_path(color, my_cm)
if my_path < 1000:
threat_count += int(1000.0 / max(my_path, 1.0))
return threat_count
def shortest_paths_from_edges(board, color, cost_matrix, size=SIZE):
dist_start = [[float('inf')]*size for _ in range(size)]
heap_start = []
dist_end = [[float('inf')]*size for _ in range(size)]
heap_end = []
if color == 1:
for c in range(size):
if cost_matrix[0][c] != float('inf'):
dist_start[0][c] = cost_matrix[0][c]
heapq.heappush(heap_start, (dist_start[0][c], 0, c))
if cost_matrix[size-1][c] != float('inf'):
dist_end[size-1][c] = cost_matrix[size-1][c]
heapq.heappush(heap_end, (dist_end[size-1][c], size-1, c))
else:
for r in range(size):
if cost_matrix[r][0] != float('inf'):
dist_start[r][0] = cost_matrix[r][0]
heapq.heappush(heap_start, (dist_start[r][0], r, 0))
if cost_matrix[r][size-1] != float('inf'):
dist_end[r][size-1] = cost_matrix[r][size-1]
heapq.heappush(heap_end, (dist_end[r][size-1], r, size-1))
while heap_start:
cost, r, c = heapq.heappop(heap_start)
if cost > dist_start[r][c]: continue
for nr, nc in VALID_NEIGHBORS[r][c]:
step = cost_matrix[nr][nc]
if step != float('inf'):
new_cost = cost + step
if new_cost < dist_start[nr][nc]:
dist_start[nr][nc] = new_cost
heapq.heappush(heap_start, (new_cost, nr, nc))
while heap_end:
cost, r, c = heapq.heappop(heap_end)
if cost > dist_end[r][c]: continue
for nr, nc in VALID_NEIGHBORS[r][c]:
step = cost_matrix[nr][nc]
if step != float('inf'):
new_cost = cost + step
if new_cost < dist_end[nr][nc]:
dist_end[nr][nc] = new_cost
heapq.heappush(heap_end, (new_cost, nr, nc))
return dist_start, dist_end
def evaluate_state(board, my_color):
opp_color = -my_color
my_cm = get_cost_matrix(board, my_color)
opp_cm = get_cost_matrix(board, opp_color)
my_cost = single_shortest_path(my_color, my_cm)
opp_cost = single_shortest_path(opp_color, opp_cm)
# Aggressive: heavily weight opponent blocking
return my_cost - 2.5 * opp_cost
def get_move(state):
start_time = time.time()
if 'board' not in state:
if 'legal_moves' in state:
return state['legal_moves'][0]
return 'UP'
board = state['board']
legal_moves = state['legal_moves']
my_color = state['my_color']
opp_color = -my_color
# Check immediate win
my_cm = get_cost_matrix(board, my_color)
if single_shortest_path(my_color, my_cm) == 0:
return legal_moves[0]
# Get cost matrices
my_cm = get_cost_matrix(board, my_color)
opp_cm = get_cost_matrix(board, opp_color)
my_d_start, my_d_end = shortest_paths_from_edges(board, my_color, my_cm)
opp_d_start, opp_d_end = shortest_paths_from_edges(board, opp_color, opp_cm)
# Score all moves with aggressive heuristics
move_scores = []
for move in legal_moves:
r, c = move[0], move[1]
my_path = my_d_start[r][c] + my_d_end[r][c] - my_cm[r][c]
opp_path = opp_d_start[r][c] + opp_d_end[r][c] - opp_cm[r][c]
if my_path == float('inf'): my_path = 1000
if opp_path == float('inf'): opp_path = 1000
# Aggressive: strongly penalize moves that don't block opponent, reward moves that help us
center_bonus = 5.0 - 0.3 * CENTER_DIST[r][c]
block_bonus = max(0, 100 - opp_path * 10)
my_bonus = max(0, 100 - my_path * 10)
heur = -(my_path + 2.2 * opp_path) + block_bonus + my_bonus + center_bonus
move_scores.append((heur, move, my_path, opp_path))
move_scores.sort(reverse=True)
# Select top candidates for 3-ply search
top_k = min(len(legal_moves), 10)
my_candidates = [m for h, m, _, _ in move_scores[:top_k]]
best_move = my_candidates[0]
best_score = float('inf')
for my_move in my_candidates:
r, c = my_move[0], my_move[1]
board[r][c] = my_color
# Check immediate win after my move
my_cm_temp = get_cost_matrix(board, my_color)
if single_shortest_path(my_color, my_cm_temp) == 0:
board[r][c] = 0
return my_move
# Get opponent's best responses
opp_cm_temp = get_cost_matrix(board, opp_color)
opp_d_start_temp, opp_d_end_temp = shortest_paths_from_edges(board, opp_color, opp_cm_temp)
my_d_start_temp, my_d_end_temp = shortest_paths_from_edges(board, my_color, my_cm_temp)
opp_responses = []
for opp_move in legal_moves:
if opp_move == my_move: continue
orow, ocol = opp_move[0], opp_move[1]
opp_p = opp_d_start_temp[orow][ocol] + opp_d_end_temp[orow][ocol] - opp_cm_temp[orow][ocol]
my_p = my_d_start_temp[orow][ocol] + my_d_end_temp[orow][ocol] - my_cm_temp[orow][ocol]
if opp_p == float('inf'): opp_p = 1000
if my_p == float('inf'): my_p = 1000
center_bonus = 5.0 - 0.3 * CENTER_DIST[orow][ocol]
block_bonus = max(0, 100 - my_p * 10)
opp_bonus = max(0, 100 - opp_p * 10)
o_heur = -(opp_p + 2.2 * my_p) + block_bonus + opp_bonus + center_bonus
opp_responses.append((o_heur, opp_move))
opp_responses.sort(reverse=True)
# Evaluate top opponent responses with 2-ply depth
opp_top_k = min(len(opp_responses), 4)
worst_opp_score = float('-inf')
for o_heur, opp_move in opp_responses[:opp_top_k]:
orow, ocol = opp_move[0], opp_move[1]
board[orow][ocol] = opp_color
# Quick evaluation
score = evaluate_state(board, my_color) - 0.0001 * CENTER_DIST[r][c]
if score > worst_opp_score:
worst_opp_score = score
board[orow][ocol] = 0
if worst_opp_score >= best_score:
break
board[r][c] = 0
if worst_opp_score < best_score:
best_score = worst_opp_score
best_move = my_move
if time.time() - start_time > 0.085:
break
return best_move