Download breakthrough_mcvs.py from test1978/breakthrough-model: direct link, hf CLI and curl.
- Browser
- Download file 44.1 kB
-
https://huggingface.co/test1978/breakthrough-model/resolve/main/breakthrough_mcvs.py
- Command line
-
hf download hf://test1978/breakthrough-model/breakthrough_mcvs.py
-
curl -L -o breakthrough_mcvs.py https://huggingface.co/test1978/breakthrough-model/resolve/main/breakthrough_mcvs.py
44.1 kB
import numpy as np
import torch
import torch.nn as nn
import torch.optim as optim
import torch.nn.functional as F
from torch.utils.data import DataLoader, TensorDataset
from typing import List, Dict, Tuple
import random
import time
import os
import bisect
# ============================================================================
# HILBERT CURVE UTILITIES1
# ============================================================================
def xy2d(n: int, x: int, y: int) -> int:
"""Convert (x,y) to Hilbert curve distance."""
d = 0
s = n // 2
while s > 0:
rx = 1 if (x & s) > 0 else 0
ry = 1 if (y & s) > 0 else 0
d += s * s * ((3 * rx) ^ ry)
if ry == 0:
if rx == 1:
x = n - 1 - x
y = n - 1 - y
x, y = y, x
s //= 2
return d
def matrix_to_hilbert_index(W: np.ndarray) -> int:
if W.size == 0:
return 0
W_flat = W.flatten()
max_idx = np.argmax(W_flat)
x = max_idx % 64
y = max_idx // 64
return xy2d(64, x, y)
def move_to_index(fr: int, fc: int, tr: int, tc: int) -> int:
"""Convert move tuple (fr,fc,tr,tc) to policy index in [0,4095]."""
from_sq = fr * 8 + fc
to_sq = tr * 8 + tc
return from_sq * 64 + to_sq
# ============================================================================
# ABC MODEL DYNAMIC
# ============================================================================
class ABCModelDynamic:
"""ABC Model with displacement-based B matrices."""
def __init__(self, n: int = 2, t: float = 1.0, T: float = 1.41):
self.n = n
self.t = t
self.T = T
self.c0 = np.array([0.0, 0.0, 1.0])
self.B_blocks = []
self.piece_positions = []
self.a_product = np.eye(3)
self.delta = {}
self.kappa = {}
self.stage = 0
self.MB_current = self.c0.copy()
self.MB_previous = self.c0.copy()
self.history = []
def create_B_displacement(self, dx: float, dy: float) -> np.ndarray:
return np.array([
[1.0, 0.0, dx],
[0.0, 1.0, dy],
[0.0, 0.0, 1.0]
])
def add_piece(self, position: tuple, delta_values: tuple, kappa_vector: np.ndarray = None):
x, y = position
current_MB = self.MB_current.copy()
dx = x - current_MB[0]
dy = y - current_MB[1]
B_i = self.create_B_displacement(dx, dy)
idx = len(self.B_blocks)
self.B_blocks.append(B_i)
self.piece_positions.append((x, y))
self.a_product = self.a_product @ B_i
self.MB_previous = self.MB_current.copy()
self.MB_current = self.a_product @ self.c0
self.delta[idx] = delta_values
if kappa_vector is None:
kappa_vector = np.array(delta_values)
self.kappa[idx] = kappa_vector
self.stage += 1
self.history.append({
'stage': self.stage,
'SB_position': (x, y),
'displacement': (dx, dy),
'B_i': B_i.copy(),
'a_t': self.a_product.copy(),
'MB_prev': self.MB_previous.copy(),
'MB_curr': self.MB_current.copy(),
'delta': delta_values,
'kappa': kappa_vector.copy()
})
# ============================================================================
# WEIGHTED MATRIX ABC
# ============================================================================
class WeightedMatrixABC:
"""Compute weighted adjacency matrix from ABCModelDynamic."""
def __init__(self, abc_model: ABCModelDynamic, sigma: float = 1.0):
self.abc = abc_model
self.n = abc_model.n
self.t = abc_model.t
self.T = abc_model.T
self.sigma = sigma
self.positions = None
self.D = None
self.A = None
self.S = None
self.F = None
self.W = None
def compute_piece_positions(self) -> np.ndarray:
positions = []
for pos in self.abc.piece_positions:
x, y = pos
positions.append(np.array([x, y, 1.0]))
self.positions = np.array(positions)
return self.positions
def compute_distance_matrix(self) -> np.ndarray:
if self.positions is None:
self.compute_piece_positions()
num = len(self.positions)
D = np.zeros((num, num))
for i in range(num):
for j in range(num):
pos_i = self.positions[i][:2]
pos_j = self.positions[j][:2]
D[i, j] = np.linalg.norm(pos_i - pos_j)
self.D = D
return D
def compute_adjacency_matrix(self) -> np.ndarray:
if self.D is None:
self.compute_distance_matrix()
num = len(self.positions)
A = np.zeros((num, num))
isolated = set()
for i in range(num):
has_neighbor = False
for j in range(num):
if i != j and self.t <= self.D[i, j] <= self.T:
has_neighbor = True
break
if not has_neighbor:
isolated.add(i)
for i in range(num):
for j in range(num):
if i != j and self.t <= self.D[i, j] <= self.T:
A[i, j] = 1.0
elif i == j and i in isolated:
A[i, j] = 1.0
self.A = A
return A
def compute_spatial_matrix(self) -> np.ndarray:
if self.D is None:
self.compute_distance_matrix()
num = len(self.positions)
S = np.zeros((num, num))
for i in range(num):
for j in range(num):
S[i, j] = np.exp(-self.D[i, j] ** 2 / (2 * self.sigma ** 2))
self.S = S
return S
def compute_feature_matrix(self) -> np.ndarray:
num = len(self.positions)
F = np.zeros((num, num))
kappas = []
for i in range(num):
if i in self.abc.kappa:
kappas.append(self.abc.kappa[i])
elif i in self.abc.delta:
kappas.append(np.array(self.abc.delta[i]))
else:
kappas.append(np.array([1.0, 1.0, 1.0]))
for i in range(num):
for j in range(num):
kappa_i = kappas[i]
kappa_j = kappas[j]
dot_product = np.dot(kappa_i, kappa_j)
norm_i = np.linalg.norm(kappa_i)
norm_j = np.linalg.norm(kappa_j)
if norm_i > 0 and norm_j > 0:
F[i, j] = dot_product / (norm_i * norm_j)
else:
F[i, j] = 0.0
self.F = F
return F
def compute_weighted_matrix(self) -> np.ndarray:
if self.A is None:
self.compute_adjacency_matrix()
if self.S is None:
self.compute_spatial_matrix()
if self.F is None:
self.compute_feature_matrix()
W = self.A * self.S * self.F
self.W = W
return W
# ============================================================================
# BREAKTHROUGH GAME LOGIC
# ============================================================================
class Breakthrough:
ROWS, COLS = 8, 8
EMPTY, PLAYER1, PLAYER2 = 0, 1, 2
def __init__(self):
self.board = np.zeros((self.ROWS, self.COLS), dtype=np.int32)
self.board[0:2, :] = self.PLAYER1
self.board[6:8, :] = self.PLAYER2
self.move_count = 0
self._move_stack: List[Tuple] = [] # (fr, fc, tr, tc, captured)
self._cached_matrix = None
def copy(self):
new_game = Breakthrough.__new__(Breakthrough)
new_game.board = self.board.copy()
new_game.move_count = self.move_count
new_game._move_stack = list(self._move_stack)
new_game._cached_matrix = (
self._cached_matrix.copy() if self._cached_matrix is not None else None
)
return new_game
def get_legal_moves(self) -> List[Tuple[int, int, int, int]]:
moves = []
player = self.PLAYER1 if self.move_count % 2 == 0 else self.PLAYER2
direction = 1 if player == self.PLAYER1 else -1
opponent = 3 - player
for r in range(self.ROWS):
for c in range(self.COLS):
if self.board[r, c] == player:
nr = r + direction
if 0 <= nr < self.ROWS:
if self.board[nr, c] == self.EMPTY:
moves.append((r, c, nr, c))
for dc in [-1, 1]:
nc = c + dc
if 0 <= nc < self.COLS and self.board[nr, nc] == opponent:
moves.append((r, c, nr, nc))
return moves
def apply_move(self, move: Tuple[int, int, int, int]) -> None:
fr, fc, tr, tc = move
captured = int(self.board[tr, tc])
self._move_stack.append((fr, fc, tr, tc, captured))
self.board[tr, tc] = self.board[fr, fc]
self.board[fr, fc] = self.EMPTY
self.move_count += 1
self._cached_matrix = None
def undo_move(self) -> None:
if not self._move_stack:
return
fr, fc, tr, tc, captured = self._move_stack.pop()
self.board[fr, fc] = self.board[tr, tc]
self.board[tr, tc] = captured
self.move_count -= 1
self._cached_matrix = None
def check_winner(self) -> int:
"""Return PLAYER1 (1) if row 7 reached, PLAYER2 (2) if row 0 reached, else EMPTY (0)."""
if np.any(self.board[7, :] == self.PLAYER1):
return self.PLAYER1
if np.any(self.board[0, :] == self.PLAYER2):
return self.PLAYER2
return self.EMPTY
def is_terminal(self) -> bool:
return self.check_winner() != self.EMPTY or len(self.get_legal_moves()) == 0
def get_weighted_adjacency_matrix(self) -> np.ndarray:
if self._cached_matrix is not None:
return self._cached_matrix
occupied = []
for r in range(8):
for c in range(8):
piece = self.board[r, c]
if piece != self.EMPTY:
x = c - 3.5
y = 3.5 - r
delta_2 = 1.0 if piece == self.PLAYER1 else 1.1
kappa = np.array([1.0, delta_2, 1.0])
hilbert_d = xy2d(8, c, r)
occupied.append((hilbert_d, (x, y), kappa))
occupied.sort(key=lambda t: t[0])
abc = ABCModelDynamic(n=2, t=1.0, T=1.41)
for _, pos, kappa_vec in occupied:
abc.add_piece(pos, delta_values=(1.0, float(kappa_vec[1]), 1.0), kappa_vector=kappa_vec)
builder = WeightedMatrixABC(abc, sigma=1.0)
W_small = builder.compute_weighted_matrix()
n = len(occupied)
W = np.zeros((64, 64), dtype=np.float32)
if n > 0:
W[:n, :n] = W_small
self._cached_matrix = W
return W
# ============================================================================
# NEURAL NETWORKS
# ============================================================================
class PolicyNetworkCNN(nn.Module):
def __init__(self):
super().__init__()
self.conv = nn.Sequential(
nn.Conv2d(1, 64, kernel_size=5, padding=2, stride=2),
nn.ReLU(),
nn.Conv2d(64, 128, kernel_size=5, padding=2, stride=2),
nn.ReLU(),
nn.Conv2d(128, 128, kernel_size=3, padding=1, stride=2),
nn.ReLU(),
)
self.fc = nn.Linear(128 * 8 * 8, 4096)
def forward(self, x):
x = self.conv(x)
x = x.view(x.size(0), -1)
return self.fc(x)
class ValueNetworkCNN(nn.Module):
def __init__(self):
super().__init__()
self.conv = nn.Sequential(
nn.Conv2d(1, 64, kernel_size=5, padding=2, stride=2),
nn.ReLU(),
nn.Conv2d(64, 128, kernel_size=5, padding=2, stride=2),
nn.ReLU(),
nn.Conv2d(128, 128, kernel_size=3, padding=1, stride=2),
nn.ReLU(),
)
self.fc = nn.Sequential(
nn.Linear(128 * 8 * 8, 512),
nn.ReLU(),
nn.Linear(512, 1),
nn.Tanh()
)
def forward(self, x):
x = self.conv(x)
x = x.view(x.size(0), -1)
return self.fc(x)
# ============================================================================
# ZONE DATABASE
# ============================================================================
class HilbertOrderedZoneDatabase:
def __init__(self, filepath: str = "breakthrough_zone_db.npz", max_size: int = 10000):
self.filepath = filepath
self.max_size = max_size
self.winning_matrices = []
self.winning_indices = []
self.losing_matrices = []
self.losing_indices = []
self.draw_matrices = []
self.draw_indices = []
self.load()
def add_winning_matrix(self, W: np.ndarray):
if W.shape != (64, 64):
return
hilbert_idx = matrix_to_hilbert_index(W)
pos = bisect.bisect_left(self.winning_indices, hilbert_idx)
self.winning_indices.insert(pos, hilbert_idx)
self.winning_matrices.insert(pos, W.copy())
def add_losing_matrix(self, W: np.ndarray):
if W.shape != (64, 64):
return
hilbert_idx = matrix_to_hilbert_index(W)
pos = bisect.bisect_left(self.losing_indices, hilbert_idx)
self.losing_indices.insert(pos, hilbert_idx)
self.losing_matrices.insert(pos, W.copy())
def add_draw_matrix(self, W: np.ndarray):
if W.shape != (64, 64):
return
hilbert_idx = matrix_to_hilbert_index(W)
pos = bisect.bisect_left(self.draw_indices, hilbert_idx)
self.draw_indices.insert(pos, hilbert_idx)
self.draw_matrices.insert(pos, W.copy())
def add_game_record(self, trajectory: List[Breakthrough], result: int, sample_rate: float = 0.3):
sampled_states = []
for i, state in enumerate(trajectory):
if i == 0 or i == len(trajectory) - 1:
sampled_states.append(state)
elif random.random() < sample_rate:
sampled_states.append(state)
for state in sampled_states:
W = state.get_weighted_adjacency_matrix()
if result == 1:
self.add_winning_matrix(W)
elif result == -1:
self.add_losing_matrix(W)
else:
self.add_draw_matrix(W)
def save(self):
threshold = int(self.max_size * 0.8)
if (len(self.winning_matrices) > threshold or
len(self.losing_matrices) > threshold or
len(self.draw_matrices) > threshold):
print("Pruning database before save...")
self.prune_database(target_size=int(self.max_size * 0.7))
try:
np.savez_compressed(
self.filepath,
winning=np.array(self.winning_matrices, dtype=object),
winning_indices=np.array(self.winning_indices),
losing=np.array(self.losing_matrices, dtype=object),
losing_indices=np.array(self.losing_indices),
draw=np.array(self.draw_matrices, dtype=object),
draw_indices=np.array(self.draw_indices),
)
print(f"Zone DB saved: W={len(self.winning_matrices)}, L={len(self.losing_matrices)}, D={len(self.draw_matrices)}")
except MemoryError:
print("MemoryError during save! Pruning more aggressively...")
self.prune_database(target_size=1000)
np.savez_compressed(
self.filepath,
winning=np.array(self.winning_matrices, dtype=object),
winning_indices=np.array(self.winning_indices),
losing=np.array(self.losing_matrices, dtype=object),
losing_indices=np.array(self.losing_indices),
draw=np.array(self.draw_matrices, dtype=object),
draw_indices=np.array(self.draw_indices),
)
def load(self):
if os.path.exists(self.filepath):
try:
data = np.load(self.filepath, allow_pickle=True)
if 'winning' in data and 'winning_indices' in data:
self.winning_matrices = list(data['winning'])
self.winning_indices = list(data['winning_indices'])
self.losing_matrices = list(data['losing'])
self.losing_indices = list(data['losing_indices'])
self.draw_matrices = list(data['draw'])
self.draw_indices = list(data['draw_indices'])
elif 'winning_matrices' in data and 'winning_indices' in data:
self.winning_matrices = list(data['winning_matrices'])
self.winning_indices = list(data['winning_indices'])
self.losing_matrices = list(data['losing_matrices'])
self.losing_indices = list(data['losing_indices'])
self.draw_matrices = list(data['draw_matrices'])
self.draw_indices = list(data['draw_indices'])
else:
try:
self.winning_matrices = list(data.get('winning', data.get('winning_matrices', [])))
self.winning_indices = list(data.get('winning_indices', []))
self.losing_matrices = list(data.get('losing', data.get('losing_matrices', [])))
self.losing_indices = list(data.get('losing_indices', []))
self.draw_matrices = list(data.get('draw', data.get('draw_matrices', [])))
self.draw_indices = list(data.get('draw_indices', []))
except Exception:
self.winning_matrices = []
self.winning_indices = []
self.losing_matrices = []
self.losing_indices = []
self.draw_matrices = []
self.draw_indices = []
print(f"Loaded zone DB: W={len(self.winning_matrices)}, L={len(self.losing_matrices)}, D={len(self.draw_matrices)}")
except Exception as e:
print(f"Failed to load zone database: {e}")
def prune_database(self, target_size: int = 5000):
def prune_zone(matrices, indices, target):
if len(matrices) <= target:
return matrices, indices
step = max(1, len(matrices) // target)
keep_idx = list(range(0, len(matrices), step))[:target]
return [matrices[i] for i in keep_idx], [indices[i] for i in keep_idx]
old_sizes = (len(self.winning_matrices), len(self.losing_matrices), len(self.draw_matrices))
self.winning_matrices, self.winning_indices = prune_zone(
self.winning_matrices, self.winning_indices, target_size)
self.losing_matrices, self.losing_indices = prune_zone(
self.losing_matrices, self.losing_indices, target_size)
self.draw_matrices, self.draw_indices = prune_zone(
self.draw_matrices, self.draw_indices, target_size)
new_sizes = (len(self.winning_matrices), len(self.losing_matrices), len(self.draw_matrices))
print(f"Pruned: W {old_sizes[0]}->{new_sizes[0]}, L {old_sizes[1]}->{new_sizes[1]}, D {old_sizes[2]}->{new_sizes[2]}")
def compute_zone_score(self, W: np.ndarray, k: int = 5, beta: float = 0.5) -> float:
if W.shape != (64, 64):
return 0.0
def knn_similarity(matrices, k_val):
if len(matrices) == 0:
return 0.0
k_actual = min(k_val, len(matrices))
distances = [np.sum(np.abs(W - mat)) / (64.0 * 64.0) for mat in matrices[:k_actual]]
return np.mean([1.0 - d for d in distances])
zone_win = knn_similarity(self.winning_matrices, k)
zone_loss = knn_similarity(self.losing_matrices, k)
zone_draw = knn_similarity(self.draw_matrices, k)
Z = zone_win - zone_loss + beta * zone_draw
return float(np.clip(Z, -1.0, 1.0))
# ============================================================================
# TRAINING FUNCTION
# ============================================================================
def train_networks(policy_net, value_net, W_states, policies, values,
epochs=5, batch_size=32, device='cpu', lr=0.001):
policy_net.train()
value_net.train()
opt_p = optim.Adam(policy_net.parameters(), lr=lr)
opt_v = optim.Adam(value_net.parameters(), lr=lr)
W_tensor = torch.tensor(np.array(W_states)[:, np.newaxis, :, :], dtype=torch.float32)
pi_tensor = torch.tensor(np.array(policies), dtype=torch.float32)
v_tensor = torch.tensor(np.array(values), dtype=torch.float32).unsqueeze(1)
dataset = TensorDataset(W_tensor, pi_tensor, v_tensor)
loader = DataLoader(dataset, batch_size=batch_size, shuffle=True)
for epoch in range(epochs):
total_loss = 0.0
for batch_W, batch_pi, batch_v in loader:
batch_W = batch_W.to(device)
batch_pi = batch_pi.to(device)
batch_v = batch_v.to(device)
logits = policy_net(batch_W)
policy_loss = F.kl_div(F.log_softmax(logits, dim=1), batch_pi, reduction='batchmean')
pred_v = value_net(batch_W)
value_loss = F.mse_loss(pred_v, batch_v)
loss = policy_loss + value_loss
total_loss += loss.item()
opt_p.zero_grad()
opt_v.zero_grad()
loss.backward()
torch.nn.utils.clip_grad_norm_(policy_net.parameters(), max_norm=1.0)
torch.nn.utils.clip_grad_norm_(value_net.parameters(), max_norm=1.0)
opt_p.step()
opt_v.step()
print(f"Epoch {epoch+1}/{epochs} - Loss: {total_loss/len(loader):.4f}")
# ============================================================================
# MCVS SEARCHER
# ============================================================================
class MCVSSearcher:
def __init__(self, policy_net, value_net, zone_db, device='cpu',
cpuct=1.41, lambda_zone=0.0, k_zone=5, use_nets=True,
dirichlet_alpha: float = 0.3, dirichlet_noise_fraction: float = 0.25):
self.policy_net = policy_net.to(device) if policy_net and use_nets else None
self.value_net = value_net.to(device) if value_net and use_nets else None
self.zone_db = zone_db
self.device = device
self.cpuct = cpuct
self.lambda_zone = lambda_zone
self.k_zone = k_zone
self.use_nets = use_nets
self.dirichlet_alpha = float(dirichlet_alpha)
self.dirichlet_noise_fraction = float(dirichlet_noise_fraction)
def _rollout(self, game: Breakthrough) -> float:
"""Random rollout using apply/undo for efficiency; leaves game at leaf state."""
depth = 0
max_depth = 60
moves_played = []
while not game.is_terminal() and depth < max_depth:
moves = game.get_legal_moves()
if not moves:
break
m = random.choice(moves)
game.apply_move(m)
moves_played.append(m)
depth += 1
winner = game.check_winner()
for _ in range(len(moves_played)):
game.undo_move()
if winner == Breakthrough.PLAYER1:
return 1.0
elif winner == Breakthrough.PLAYER2:
return -1.0
return 0.0
class Node:
def __init__(self, prior: float = 0.0, zone: float = 0.0):
self.prior = prior
self.zone = zone
self.visit_count = 0
self.value_sum = 0.0
self.children: Dict[Tuple[int, int, int, int], 'MCVSSearcher.Node'] = {}
def search_with_time_budget(self, game: Breakthrough, time_budget: float
) -> Tuple[Dict[Tuple[int, int, int, int], int], int]:
root = self.Node()
start_time = time.time()
simulations = 0
if not game.get_legal_moves():
return {}, 0
while time.time() - start_time < time_budget:
current_game = game # shared reference — apply/undo restores state
node = root
path = []
moves_made = []
# ---- Selection ----
while node.children:
path.append(node)
total_n = sum(c.visit_count for c in node.children.values()) + 1
best_score = -float('inf')
best_move = None
best_child = None
for move, child in node.children.items():
q = child.value_sum / child.visit_count if child.visit_count > 0 else 0.0
p_lambda = max(child.prior + self.lambda_zone * child.zone, 0.001)
u = self.cpuct * p_lambda * np.sqrt(total_n) / (1 + child.visit_count)
score = q + u
if score > best_score:
best_score = score
best_move = move
best_child = child
current_game.apply_move(best_move)
moves_made.append(best_move)
node = best_child
path.append(node)
# ---- Expansion & Evaluation ----
if current_game.is_terminal():
w = current_game.check_winner()
value = 1.0 if w == Breakthrough.PLAYER1 else (-1.0 if w == Breakthrough.PLAYER2 else 0.0)
legal_moves = []
else:
legal_moves = current_game.get_legal_moves()
if self.use_nets and self.policy_net is not None and self.value_net is not None:
W = current_game.get_weighted_adjacency_matrix()
W_tensor = torch.from_numpy(W)[None, None, :, :].float().to(self.device)
with torch.no_grad():
logits = self.policy_net(W_tensor)[0]
value = self.value_net(W_tensor)[0, 0].item()
probs = F.softmax(logits, dim=0).cpu().numpy()
prior_dict = {}
prior_sum = 0.0
for m in legal_moves:
idx = move_to_index(*m)
p = float(probs[idx]) if idx < probs.size else 0.0
prior_dict[m] = p
prior_sum += p
if prior_sum > 0.0:
for m in prior_dict:
prior_dict[m] /= prior_sum
else:
p = 1.0 / len(legal_moves)
prior_dict = {m: p for m in legal_moves}
else:
value = self._rollout(current_game)
prior_dict = {m: 1.0 / len(legal_moves) for m in legal_moves} if legal_moves else {}
# Dirichlet noise at root when using nets
noise = None
if len(path) == 1 and self.use_nets and legal_moves:
noise = np.random.dirichlet([self.dirichlet_alpha] * len(legal_moves))
for i, m in enumerate(legal_moves):
prior_dict[m] = ((1 - self.dirichlet_noise_fraction) * prior_dict[m]
+ self.dirichlet_noise_fraction * noise[i])
prior_sum = sum(prior_dict.values())
if prior_sum > 0:
for m in prior_dict:
prior_dict[m] /= prior_sum
zone_db_empty = (
self.zone_db is None or
(len(getattr(self.zone_db, 'winning_matrices', [])) == 0 and
len(getattr(self.zone_db, 'losing_matrices', [])) == 0 and
len(getattr(self.zone_db, 'draw_matrices', [])) == 0)
)
need_zone = (self.lambda_zone != 0.0) and (not zone_db_empty)
for i, m in enumerate(legal_moves):
if need_zone:
current_game.apply_move(m)
child_W = current_game.get_weighted_adjacency_matrix()
child_Z = self.zone_db.compute_zone_score(child_W, k=self.k_zone)
current_game.undo_move()
else:
child_Z = 0.0
if len(path) == 1 and self.use_nets and legal_moves and noise is not None:
z_noise = (noise[i] * 2.0) - 1.0
child_Z = ((1 - self.dirichlet_noise_fraction) * child_Z
+ self.dirichlet_noise_fraction * z_noise)
node.children[m] = self.Node(prior=prior_dict.get(m, 0.0), zone=child_Z)
# ---- Backpropagation ----
v = value
for n in reversed(path):
n.visit_count += 1
n.value_sum += v
v = -v
# Restore game to root state
for _ in range(len(moves_made)):
current_game.undo_move()
simulations += 1
visits = {move: child.visit_count for move, child in root.children.items()}
if not visits:
legal = game.get_legal_moves()
visits = {random.choice(legal): 1} if legal else {}
return visits, simulations
# ============================================================================
# UCT SEARCHER (baseline)
# ============================================================================
class UCTSearcher:
def __init__(self, cpuct: float = np.sqrt(2.0)):
self.cpuct = cpuct
class Node:
def __init__(self):
self.visit_count = 0
self.value_sum = 0.0
self.children: Dict[Tuple[int, int, int, int], 'UCTSearcher.Node'] = {}
def _rollout(self, game: Breakthrough) -> float:
depth = 0
max_depth = 60
moves_played = []
while not game.is_terminal() and depth < max_depth:
moves = game.get_legal_moves()
if not moves:
break
m = random.choice(moves)
game.apply_move(m)
moves_played.append(m)
depth += 1
if depth >= max_depth:
for _ in range(len(moves_played)):
game.undo_move()
return 0.0
winner = game.check_winner()
for _ in range(len(moves_played)):
game.undo_move()
if winner == Breakthrough.PLAYER1:
return 1.0
elif winner == Breakthrough.PLAYER2:
return -1.0
return 0.0
def search_with_time_budget(self, game: Breakthrough, time_budget: float
) -> Tuple[Dict[Tuple[int, int, int, int], int], int]:
root = self.Node()
start_time = time.time()
simulations = 0
while time.time() - start_time < time_budget:
current_game = game
node = root
path = [node]
moves_made = []
while True:
legal_moves = current_game.get_legal_moves()
if current_game.is_terminal():
w = current_game.check_winner()
value = 1.0 if w == Breakthrough.PLAYER1 else (-1.0 if w == Breakthrough.PLAYER2 else 0.0)
break
if not legal_moves:
value = 0.0
break
unvisited = [m for m in legal_moves if m not in node.children]
if unvisited:
move = random.choice(unvisited)
child = self.Node()
node.children[move] = child
current_game.apply_move(move)
moves_made.append(move)
path.append(child)
value = self._rollout(current_game)
break
best_score = -float('inf')
best_move = None
best_child = None
total_visits = node.visit_count
for move in legal_moves:
child = node.children[move]
Q = child.value_sum / (child.visit_count + 1e-8)
U = self.cpuct * np.sqrt(np.log(total_visits + 1) / (child.visit_count + 1e-8))
score = Q + U
if score > best_score:
best_score = score
best_move = move
best_child = child
current_game.apply_move(best_move)
moves_made.append(best_move)
node = best_child
path.append(node)
for n in reversed(path):
n.visit_count += 1
n.value_sum += value
value = -value
for _ in range(len(moves_made)):
current_game.undo_move()
simulations += 1
visits = {move: child.visit_count for move, child in root.children.items()}
if not visits:
legal = game.get_legal_moves()
return {random.choice(legal): 1} if legal else {}, simulations
return visits, simulations
# ============================================================================
# SELF-PLAY DATA GENERATION
# ============================================================================
def generate_self_play_data(policy_net, value_net, zone_db, max_time_seconds=60.0,
lambda_zone=0.5, device='cpu'):
"""Generate self-play games using MCVS with zone guidance."""
searcher = MCVSSearcher(policy_net, value_net, zone_db, device=device,
cpuct=1.41, lambda_zone=lambda_zone, k_zone=5)
W_states = []
policies = []
values = []
trajectories = []
start_time = time.time()
game_idx = 0
while time.time() - start_time < max_time_seconds:
game_start_time = time.time()
game = Breakthrough()
trajectory = [game.copy()]
W_state_list = []
policy_list = []
while not game.is_terminal():
time_per_move = 0.3
W_t = game.get_weighted_adjacency_matrix()
visits, _ = searcher.search_with_time_budget(game, time_per_move)
if not visits:
break
moves = list(visits.keys())
visit_counts = np.array([visits[m] for m in moves], dtype=float)
total_visits = visit_counts.sum()
if total_visits <= 0:
break
probs = visit_counts / total_visits
temperature = 1.0 if game.move_count < 8 else 0.25
if temperature != 1.0:
probs = probs ** (1.0 / temperature)
prob_sum = probs.sum()
if prob_sum <= 0:
probs = np.ones(len(moves)) / len(moves)
else:
probs = probs / prob_sum
policy_target = np.zeros(4096)
for move, count in visits.items():
idx = move_to_index(*move)
if 0 <= idx < 4096:
policy_target[idx] = count / total_visits
W_state_list.append(W_t)
policy_list.append(policy_target)
if len(moves) > 1:
chosen_idx = np.random.choice(len(moves), p=probs)
chosen_move = moves[chosen_idx]
else:
chosen_move = moves[0]
game.apply_move(chosen_move)
trajectory.append(game.copy())
winner = game.check_winner()
result = (1 if winner == Breakthrough.PLAYER1
else -1 if winner == Breakthrough.PLAYER2
else 0)
for i in range(len(W_state_list)):
player_to_move = 1 if i % 2 == 0 else -1
value = result if result == 0 else (result if result == player_to_move else -result)
W_states.append(W_state_list[i])
policies.append(policy_list[i])
values.append(value)
zone_db.add_game_record(trajectory, result)
trajectories.append(trajectory)
game_idx += 1
game_duration = time.time() - game_start_time
total_elapsed = time.time() - start_time
print(f"Game {game_idx}: Winner={winner}, Moves={game.move_count}, "
f"Duration={game_duration:.1f}s, Total={total_elapsed:.1f}s")
elapsed = time.time() - start_time
print(f"\nSelf-play finished: {game_idx} games in {elapsed:.1f}s, "
f"{len(W_states)} training examples collected")
return W_states, policies, values, trajectories
# ============================================================================
# DIAGNOSTIC TEST FOR MOVE DIVERSITY
# ============================================================================
def test_move_diversity(policy_net, value_net, zone_db, num_trials=30,
time_budget=2.0, device='cpu'):
searcher = MCVSSearcher(policy_net, value_net, zone_db, device=device)
game = Breakthrough()
move_counts = {}
for _ in range(num_trials):
visits, _ = searcher.search_with_time_budget(game, time_budget)
if visits:
best_move = max(visits, key=visits.get)
move_counts[best_move] = move_counts.get(best_move, 0) + 1
print("\nMove diversity test (starting position):")
total = sum(move_counts.values())
for m, cnt in sorted(move_counts.items(), key=lambda x: -x[1]):
print(f"{m}: {cnt:2d}x ({cnt/total:.1%})")
print(f"Unique moves chosen: {len(move_counts)} out of {len(game.get_legal_moves())} legal\n")
# ============================================================================
# GUIDED MCVS vs UCT-MCTS TOURNAMENT
# ============================================================================
def play_match_mcvs_vs_uct(policy_net, value_net, zone_db, num_games: int = 200,
time_per_move: float = 0.3, device: str = 'cpu'):
"""
Tournament between guided MCVS and UCT.
Odd games: MCVS as PLAYER1; even games: UCT as PLAYER1.
"""
mcvs_searcher = MCVSSearcher(policy_net, value_net, zone_db,
device=device, cpuct=1.41,
lambda_zone=1.0, k_zone=5)
uct_searcher = UCTSearcher(cpuct=np.sqrt(2.0))
mcvs_wins = 0
uct_wins = 0
draws = 0
for g in range(1, num_games + 1):
game = Breakthrough()
mcvs_as_player1 = (g % 2 == 1)
while not game.is_terminal():
moves = game.get_legal_moves()
if not moves:
break
is_player1_turn = (game.move_count % 2 == 0)
use_mcvs = mcvs_as_player1 if is_player1_turn else not mcvs_as_player1
if use_mcvs:
visits, _ = mcvs_searcher.search_with_time_budget(game, time_per_move)
else:
visits, _ = uct_searcher.search_with_time_budget(game, time_per_move)
if not visits:
break
moves_list = list(visits.keys())
counts = np.array([visits[m] for m in moves_list], dtype=float)
chosen_move = moves_list[int(np.argmax(counts))]
game.apply_move(chosen_move)
winner = game.check_winner()
if winner == Breakthrough.PLAYER1:
if mcvs_as_player1:
mcvs_wins += 1
else:
uct_wins += 1
elif winner == Breakthrough.PLAYER2:
if mcvs_as_player1:
uct_wins += 1
else:
mcvs_wins += 1
else:
draws += 1
print(f"Game {g}/{num_games} finished. Winner={winner} (MCVS as P1: {mcvs_as_player1})")
print("\n=== MCVS vs UCT Tournament Results ===")
print(f"Total games : {num_games}")
print(f"MCVS wins : {mcvs_wins}")
print(f"UCT wins : {uct_wins}")
print(f"Draws : {draws}")
if num_games > 0:
print(f"Win rates : MCVS={mcvs_wins/num_games*100:.1f}%, "
f"UCT={uct_wins/num_games*100:.1f}%, Draw={draws/num_games*100:.1f}%\n")
def main():
print("=" * 80)
print("BREAKTHROUGH MCVS - INCREMENTAL TRAINING")
print("=" * 80)
device = "cuda" if torch.cuda.is_available() else "cpu"
print(f"Device: {device}")
policy_net = PolicyNetworkCNN().to(device)
value_net = ValueNetworkCNN().to(device)
zone_db = HilbertOrderedZoneDatabase("breakthrough_zone_db.npz", max_size=10000)
checkpoint_path = "breakthrough_checkpoint.pt"
iteration = 0
if os.path.exists(checkpoint_path):
print(f"Loading checkpoint from {checkpoint_path}...")
checkpoint = torch.load(checkpoint_path, map_location=device)
policy_net.load_state_dict(checkpoint['policy'])
value_net.load_state_dict(checkpoint['value'])
iteration = checkpoint.get('iteration', 0)
print(f"Resumed from iteration {iteration}")
all_W_states: List = []
all_policies: List = []
all_values: List = []
while True:
print("=" * 80)
print(f"ITERATION {iteration}")
print("=" * 80)
print("Generating self-play data (30 minutes)...")
lambda_zone = 0.0 if iteration == 0 else 1.0
W_states, policies, values, trajectories = generate_self_play_data(
policy_net, value_net, zone_db,
max_time_seconds=1800.0,
lambda_zone=lambda_zone,
device=device
)
print(f"Collected {len(W_states)} training examples from {len(trajectories)} games")
all_W_states.extend(W_states)
all_policies.extend(policies)
all_values.extend(values)
max_training_examples = 50000
if len(all_W_states) > max_training_examples:
print(f"Trimming training data to most recent {max_training_examples} examples...")
all_W_states = all_W_states[-max_training_examples:]
all_policies = all_policies[-max_training_examples:]
all_values = all_values[-max_training_examples:]
print(f"Total accumulated training examples: {len(all_W_states)}")
print("Training networks...")
train_networks(
policy_net, value_net,
all_W_states, all_policies, all_values,
epochs=10,
device=device,
lr=0.001
)
print("Saving checkpoint...")
torch.save({
'policy': policy_net.state_dict(),
'value': value_net.state_dict(),
'iteration': iteration,
'num_training_examples': len(all_W_states)
}, checkpoint_path)
print(f"Checkpoint saved: {checkpoint_path}")
zone_db.save()
print(f"Zone DB saved: W={len(zone_db.winning_matrices)}, "
f"L={len(zone_db.losing_matrices)}, D={len(zone_db.draw_matrices)}")
iteration += 1
print("\n" + "=" * 80)
print(f"Iteration {iteration} complete!")
print(f"Files updated: {checkpoint_path}, {zone_db.filepath}")
print("=" * 80 + "\n")
if iteration % 5 == 0:
print("\nRunning tournament evaluation...")
play_match_mcvs_vs_uct(
policy_net, value_net, zone_db,
num_games=20,
time_per_move=0.5,
device=device
)
# ============================================================================
# MAIN
# ============================================================================
if __name__ == "__main__":
pass
import numpy as np
import torch
import torch.nn as nn
import torch.optim as optim
import torch.nn.functional as F
from torch.utils.data import DataLoader, TensorDataset
from typing import List, Dict, Tuple
import random
import time
import os
import bisect
# ============================================================================
# HILBERT CURVE UTILITIES1
# ============================================================================
def xy2d(n: int, x: int, y: int) -> int:
"""Convert (x,y) to Hilbert curve distance."""
d = 0
s = n // 2
while s > 0:
rx = 1 if (x & s) > 0 else 0
ry = 1 if (y & s) > 0 else 0
d += s * s * ((3 * rx) ^ ry)
if ry == 0:
if rx == 1:
x = n - 1 - x
y = n - 1 - y
x, y = y, x
s //= 2
return d
def matrix_to_hilbert_index(W: np.ndarray) -> int:
if W.size == 0:
return 0
W_flat = W.flatten()
max_idx = np.argmax(W_flat)
x = max_idx % 64
y = max_idx // 64
return xy2d(64, x, y)
def move_to_index(fr: int, fc: int, tr: int, tc: int) -> int:
"""Convert move tuple (fr,fc,tr,tc) to policy index in [0,4095]."""
from_sq = fr * 8 + fc
to_sq = tr * 8 + tc
return from_sq * 64 + to_sq
# ============================================================================
# ABC MODEL DYNAMIC
# ============================================================================
class ABCModelDynamic:
"""ABC Model with displacement-based B matrices."""
def __init__(self, n: int = 2, t: float = 1.0, T: float = 1.41):
self.n = n
self.t = t
self.T = T
self.c0 = np.array([0.0, 0.0, 1.0])
self.B_blocks = []
self.piece_positions = []
self.a_product = np.eye(3)
self.delta = {}
self.kappa = {}
self.stage = 0
self.MB_current = self.c0.copy()
self.MB_previous = self.c0.copy()
self.history = []
def create_B_displacement(self, dx: float, dy: float) -> np.ndarray:
return np.array([
[1.0, 0.0, dx],
[0.0, 1.0, dy],
[0.0, 0.0, 1.0]
])
def add_piece(self, position: tuple, delta_values: tuple, kappa_vector: np.ndarray = None):
x, y = position
current_MB = self.MB_current.copy()
dx = x - current_MB[0]
dy = y - current_MB[1]
B_i = self.create_B_displacement(dx, dy)
idx = len(self.B_blocks)
self.B_blocks.append(B_i)
self.piece_positions.append((x, y))
self.a_product = self.a_product @ B_i
self.MB_previous = self.MB_current.copy()
self.MB_current = self.a_product @ self.c0
self.delta[idx] = delta_values
if kappa_vector is None:
kappa_vector = np.array(delta_values)
self.kappa[idx] = kappa_vector
self.stage += 1
self.history.append({
'stage': self.stage,
'SB_position': (x, y),
'displacement': (dx, dy),
'B_i': B_i.copy(),