1565 lines
66 KiB
Python
1565 lines
66 KiB
Python
from collections.abc import Iterator
|
|
from collections import deque
|
|
from typing import Any, cast
|
|
from time import perf_counter
|
|
import heapq, os
|
|
|
|
from quart_common.web.env import env_int
|
|
|
|
from snakes.TemplateSnake import TemplateSnake
|
|
from server.GameBoard import GameBoard
|
|
from server.dataset.RLBootstrapDataset import RLBootstrapDataset
|
|
|
|
class UltimateBattleSnake(TemplateSnake):
|
|
"""
|
|
UltimateBattleSnake v4.5.0
|
|
|
|
All improvements over BestBattleSnake:
|
|
v3: #1+#9 Simultaneous minimax (both snakes move at once) with hazard/health tracking
|
|
v3: #2 Enemy distance maps recomputed per-candidate when time allows (>150ms left)
|
|
v3: #3 Restored enemy_confinement_metrics + full encirclement multipliers in duel
|
|
v3: #4 Restored enemy_constrictor_projection for constrictor games
|
|
v3: #5 Survival tree lookahead for multi-snake tiebreaking
|
|
v3: #6 _safe_next_options uses pre-built attack map (no redundant rebuild)
|
|
v3: #7 Occupancy ratio uses total board bodies, not just ours
|
|
v3: #8 Articulation penalty scales with partition size; BFS limit = board area
|
|
v3: #10 Duel style (safe/balanced/aggressive) restored from env var
|
|
v3: #11 Hazard multi-step health depletion check (will this corridor kill us?)
|
|
v3: #13 Tail-escape used as score-window tiebreaker, not primary filter
|
|
v3: #14 future_body + blocked returned in info dict (no recompute in callers)
|
|
v3: #15 BFS limit = width*height (not hardcoded 120)
|
|
v4: F1 Sort minimax move lists by food/center for better alpha-beta pruning
|
|
v4: F2 Survival tree added to constrictor mode and duel post-minimax
|
|
v4: F3 Starvation lookahead: heavy penalty when health < 40 and food unreachable in time
|
|
v4: F4/10 Food competition: penalise contested nearest food using precomputed enemy dmaps
|
|
v4: F5 Length-growth threshold bonus in duel when eating crosses enemy-length barrier
|
|
v4: F6 Optimistic flood fill: enemy tails excluded from blocked for reachable_space
|
|
v4: F8 H2H distance-2 penalty using precomputed enemy dmaps
|
|
v4: F9 Corner/edge geometric penalty scaled by total_occupancy
|
|
v4: F11 Constrictor dead-end buffer: required_space += max(3, len // 6)
|
|
v4: F12 Removed double _territory_fast call from _score_move (was also called by callers)
|
|
v4.1 B1 _simulation_blocked now correctly keeps enemy tail blocked when enemy_can_grow=True
|
|
v4.1 B2 _build_enemy_attack_map: can_en_tail=False when enemy is about to eat (won't vacate)
|
|
v4.1 B3 _compute_base_blocked: same enemy_can_grow fix for Voronoi dmap accuracy
|
|
v4.2 B4 _build_enemy_attack_map: enemy_can_grow now actually passed from choose_move and tree
|
|
v4.2 B5 _choose_duel_move: removed double food bias (score_move already adds it; duel now only adjusts delta)
|
|
v4.2 B6 _minimax_sim: occupancy now respects _is_tail_stacked (stacked tail not vacated)
|
|
v4.3 C1 hazard_count dict tracks Snail Mode stack depth; damage scaled by stack throughout
|
|
v4.3 C2 minimax: hazard damage skipped when food eaten on same tile (rules fidelity)
|
|
v4.3 C3 _hazard_will_kill: baseline -1/turn now included in health depletion math
|
|
v4.3 C4 _legal_moves: enemy tail vacate allowed when enemy won't grow (fixes false negatives)
|
|
v4.3 C5 mode detection uses both ruleset name and game map (snail mode hardening)
|
|
v4.4 D1 _minimax_sim: hazard spawn-immunity via previous_hazard_set (no damage on newly-spawned hazard)
|
|
v4.4 D2 _hazard_will_kill: Dijkstra with per-tile stack cost (was constant entry_stack for whole corridor)
|
|
v4.4 D3 all random.choice fallbacks replaced with deterministic degrade (last_move > center > lexical)
|
|
v4.5 E1 _enemy_can_grow_this_turn: health-urgency heuristic + occupied-set check (food blocked = no eat)
|
|
v4.5 E2 _flood_fill_count: per-turn frozenset-keyed transposition cache; resets each turn
|
|
v4.5 E3 Snail-specific trail scoring: adjacent hazard density + stack-risk penalty via self._is_snail
|
|
"""
|
|
|
|
VERSION = "4.5.0"
|
|
Point = tuple[int, int]
|
|
Coord = dict[str, int]
|
|
SnakeState = dict[str, Any]
|
|
MoveMap = dict[str, Coord]
|
|
|
|
DIRECTIONS = {
|
|
"up": (0, 1),
|
|
"down": (0, -1),
|
|
"left": (-1, 0),
|
|
"right": (1, 0),
|
|
}
|
|
|
|
OPPOSITE = {
|
|
"up": "down",
|
|
"down": "up",
|
|
"left": "right",
|
|
"right": "left",
|
|
}
|
|
|
|
def __init__(self):
|
|
super().__init__()
|
|
self.name = "UltimateBattleSnake"
|
|
self.version = self.VERSION
|
|
self.recent_heads: deque[tuple[int, int]] = deque(maxlen=14)
|
|
self.last_move: str | None = None
|
|
self.last_game_id: str | None = None
|
|
self.previous_hazards: set[tuple[int, int]] = set()
|
|
# Per-turn precomputed state
|
|
self._enemy_dmaps: list[dict] = []
|
|
self._enemy_heads: list[tuple[int, int]] = []
|
|
self._base_blocked: set[tuple[int, int]] = set()
|
|
self._is_snail: bool = False
|
|
# E2: per-turn transposition cache for flood-fill (reset each turn)
|
|
self._bfs_cache: dict[tuple, int] = {}
|
|
self._bfs_cache_turn: int = -1
|
|
# Config
|
|
self._planning_depth = max(1, min(4, env_int("BATTLE_FUTURE_PLANNING_DEPTH", 2)))
|
|
self._planning_branch = max(1, min(3, env_int("BATTLE_FUTURE_PLANNING_BRANCH", 2)))
|
|
self._planning_min_ms = max(25, env_int("BATTLE_FUTURE_PLANNING_MIN_MS", 70))
|
|
# RL bootstrap dataset recorder
|
|
self.rl_bootstrap = RLBootstrapDataset()
|
|
|
|
def __getstate__(self):
|
|
state = super().__getstate__()
|
|
# strip per-turn precomputed state — all re-assigned at the top of choose_move
|
|
state['_enemy_dmaps'] = []
|
|
state['_enemy_heads'] = []
|
|
state['_base_blocked'] = set()
|
|
state['_is_snail'] = False
|
|
state['_bfs_cache'] = {}
|
|
state['_bfs_cache_turn'] = -1
|
|
return state
|
|
|
|
# ── Env helpers ──────────────────────────────────────────────────────────────
|
|
|
|
def _get_timeout_buffer_ms(self) -> int:
|
|
try:
|
|
return max(30, int(os.getenv("SNAKE_TIMEOUT_BUFFER_MS", "130")))
|
|
except ValueError:
|
|
return 130
|
|
|
|
def _get_duel_style(self) -> str:
|
|
raw = os.getenv("BATTLE_SNAKE_DUEL_STYLE", os.getenv("DUEL_STYLE", "balanced"))
|
|
style = raw.strip().lower()
|
|
return style if style in {"safe", "balanced", "aggressive"} else "balanced"
|
|
|
|
def _duel_weights(self, style: str) -> dict[str, float]:
|
|
if style == "safe":
|
|
return {"head_pressure": 0.65, "distance_safety": 1.30, "food_bias": 1.00}
|
|
if style == "aggressive":
|
|
return {"head_pressure": 1.35, "distance_safety": 0.75, "food_bias": 0.85}
|
|
return {"head_pressure": 1.00, "distance_safety": 1.00, "food_bias": 1.00}
|
|
|
|
def _time_exceeded(self, deadline: float | None) -> bool:
|
|
return deadline is not None and perf_counter() >= deadline
|
|
|
|
def _remaining_ms(self, deadline: float | None) -> float:
|
|
if deadline is None:
|
|
return 10_000.0
|
|
return max(0.0, (deadline - perf_counter()) * 1000.0)
|
|
|
|
# ── Entry point ───────────────────────────────────────────────────────────────
|
|
|
|
def choose_move(self, game_data: GameBoard) -> str:
|
|
self.game_board = game_data
|
|
self.calculations = []
|
|
|
|
timeout_ms = (game_data.get_timeout() if hasattr(game_data, "get_timeout") else 500)
|
|
deadline = perf_counter() + (max(50, timeout_ms - self._get_timeout_buffer_ms()) / 1000.0)
|
|
|
|
game_id = getattr(game_data, "id", None)
|
|
turn = game_data.get_turn()
|
|
if game_id != self.last_game_id or turn <= 1:
|
|
self.recent_heads.clear()
|
|
self.last_move = None
|
|
self.previous_hazards = set()
|
|
self.last_game_id = game_id
|
|
self.rl_bootstrap.refresh_state()
|
|
|
|
my_snake = cast(dict[str, Any], game_data.get_my_snake())
|
|
my_head = my_snake["head"]
|
|
my_body = my_snake["body"]
|
|
my_len = my_snake.get("length", len(my_body))
|
|
my_health = my_snake.get("health", 100)
|
|
|
|
width = game_data.get_width()
|
|
height = game_data.get_height()
|
|
board_area = max(1, width * height)
|
|
|
|
foods = game_data.get_food()
|
|
hazards = game_data.get_hazard()
|
|
other_snakes = game_data.get_other_snakes()
|
|
# C5: use both ruleset name AND game map for robust mode detection
|
|
game_type = game_data.get_type()
|
|
game_map = game_data.get_map() if hasattr(game_data, "get_map") else None
|
|
is_constrictor = game_type == "constrictor"
|
|
is_snail = game_map in {"snail_mode", "snail"} or game_type == "snail_mode"
|
|
self._is_snail = is_snail # E3: store for use in _score_move
|
|
|
|
# E2: reset per-turn BFS transposition cache
|
|
if turn != self._bfs_cache_turn:
|
|
self._bfs_cache = {}
|
|
self._bfs_cache_turn = turn
|
|
|
|
food_set: set[tuple[int, int]] = {(f["x"], f["y"]) for f in foods}
|
|
# C1: track hazard stack depth (Snail Mode can stack multiple hazards on one tile)
|
|
hazard_set: set[tuple[int, int]] = set()
|
|
hazard_count: dict[tuple[int, int], int] = {}
|
|
for h in hazards:
|
|
pt = (h["x"], h["y"])
|
|
hazard_set.add(pt)
|
|
hazard_count[pt] = hazard_count.get(pt, 0) + 1
|
|
previous_hazard_set = set(self.previous_hazards)
|
|
hazard_damage = self._hazard_damage_per_turn(game_data)
|
|
current_head_pt = (my_head["x"], my_head["y"])
|
|
|
|
# Fix #7: total board occupancy (all snake bodies combined)
|
|
total_body_cells = len(my_body) + sum(len(s["body"]) for s in other_snakes)
|
|
total_occupancy = total_body_cells / board_area
|
|
|
|
# E1: build occupied set once so _enemy_can_grow_this_turn can skip food tiles under bodies
|
|
all_occupied: set[tuple[int, int]] = {(s["x"], s["y"]) for s in my_body}
|
|
for _s in other_snakes:
|
|
for _seg in _s["body"]:
|
|
all_occupied.add((_seg["x"], _seg["y"]))
|
|
enemy_can_grow = {
|
|
s["id"]: self._enemy_can_grow_this_turn(s, food_set, all_occupied)
|
|
for s in other_snakes if "id" in s
|
|
}
|
|
|
|
# ── Per-turn precomputation ───────────────────────────────────────────────
|
|
# Base blocked: current bodies with tails vacatable — for enemy dmap approximation
|
|
# Pass enemy_can_grow so tails of growing enemies stay blocked in the dmap
|
|
self._base_blocked = self._compute_base_blocked(
|
|
my_body, other_snakes, is_constrictor, enemy_can_grow, food_set
|
|
)
|
|
self._enemy_heads = [(s["head"]["x"], s["head"]["y"]) for s in other_snakes]
|
|
# Enemy distance maps precomputed ONCE; reused by all candidate evaluations
|
|
self._enemy_dmaps = [
|
|
self._distance_map(eh, self._base_blocked, width, height)
|
|
for eh in self._enemy_heads
|
|
]
|
|
# Enemy attack map: computed once, passed to all scoring (fixes #6)
|
|
enemy_attack_map = self._build_enemy_attack_map(
|
|
my_snake=my_snake, other_snakes=other_snakes, food_set=food_set,
|
|
is_constrictor=is_constrictor, width=width, height=height,
|
|
enemy_can_grow=enemy_can_grow,
|
|
)
|
|
|
|
safe_moves = self._legal_moves(
|
|
my_head=my_head, my_body=my_body, other_snakes=other_snakes,
|
|
food_set=food_set, is_constrictor=is_constrictor, width=width, height=height,
|
|
enemy_can_grow=enemy_can_grow,
|
|
)
|
|
|
|
if not safe_moves:
|
|
fallback = self._fallback_move(my_head, width, height)
|
|
self.recent_heads.append(current_head_pt)
|
|
self.last_move = fallback
|
|
self.previous_hazards = set(hazard_set)
|
|
self.add_to_history({
|
|
"turn": turn, "move": fallback, "reason": "no_safe_moves",
|
|
"health": my_health, "length": my_len,
|
|
"head": {"x": my_head["x"], "y": my_head["y"]},
|
|
})
|
|
self.rl_bootstrap.record_sample(game_data, fallback, safe_moves, "no_safe_moves")
|
|
return fallback
|
|
|
|
# ── Mode dispatch ─────────────────────────────────────────────────────────
|
|
if is_constrictor:
|
|
best_move, scores = self._choose_constrictor_move(
|
|
safe_moves=safe_moves, my_body=my_body, my_len=my_len, my_health=my_health,
|
|
other_snakes=other_snakes, food_set=food_set, hazard_set=hazard_set,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
previous_hazard_set=previous_hazard_set,
|
|
enemy_attack_map=enemy_attack_map, enemy_can_grow=enemy_can_grow,
|
|
total_occupancy=total_occupancy, width=width, height=height, deadline=deadline,
|
|
)
|
|
mode_label = "constrictor"
|
|
elif len(other_snakes) == 1:
|
|
best_move, scores = self._choose_duel_move(
|
|
safe_moves=safe_moves, my_body=my_body, my_len=my_len, my_health=my_health,
|
|
other_snakes=other_snakes, food_set=food_set, hazard_set=hazard_set,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
previous_hazard_set=previous_hazard_set,
|
|
enemy_attack_map=enemy_attack_map, enemy_can_grow=enemy_can_grow,
|
|
total_occupancy=total_occupancy, width=width, height=height, deadline=deadline,
|
|
)
|
|
mode_label = "duel"
|
|
else:
|
|
best_move, scores = self._choose_multi_move(
|
|
safe_moves=safe_moves, my_body=my_body, my_len=my_len, my_health=my_health,
|
|
other_snakes=other_snakes, food_set=food_set, hazard_set=hazard_set,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
previous_hazard_set=previous_hazard_set,
|
|
enemy_attack_map=enemy_attack_map, enemy_can_grow=enemy_can_grow,
|
|
total_occupancy=total_occupancy, width=width, height=height, deadline=deadline,
|
|
)
|
|
mode_label = "multi"
|
|
|
|
self.recent_heads.append(current_head_pt)
|
|
self.last_move = best_move
|
|
self.previous_hazards = set(hazard_set)
|
|
self.add_to_history({
|
|
"turn": turn, "move": best_move, "mode": mode_label,
|
|
"health": my_health, "length": my_len,
|
|
"head": {"x": my_head["x"], "y": my_head["y"]},
|
|
"snakes": len(other_snakes) + 1,
|
|
"occupancy": round(total_occupancy, 3),
|
|
"scores": scores,
|
|
"ms_remaining": round(self._remaining_ms(deadline), 1),
|
|
})
|
|
self.rl_bootstrap.record_sample(game_data, best_move, safe_moves, mode_label, scores)
|
|
return best_move
|
|
|
|
# ── Mode: multi-snake ─────────────────────────────────────────────────────────
|
|
|
|
def _choose_multi_move(
|
|
self, safe_moves: MoveMap, my_body: list, my_len: int, my_health: int,
|
|
other_snakes: list, food_set: set, hazard_set: set, hazard_damage: int,
|
|
hazard_count: dict, previous_hazard_set: set, enemy_attack_map: dict,
|
|
enemy_can_grow: dict, total_occupancy: float, width: int, height: int,
|
|
deadline: float | None,
|
|
) -> tuple[str, dict[str, float]]:
|
|
scores: dict[str, float] = {}
|
|
safety: dict[str, dict] = {}
|
|
|
|
for move, pos in safe_moves.items():
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
sc, info = self._score_move(
|
|
move=move, pos=pos, my_body=my_body, my_len=my_len, my_health=my_health,
|
|
other_snakes=other_snakes, food_set=food_set, hazard_set=hazard_set,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
previous_hazard_set=previous_hazard_set,
|
|
is_constrictor=False, enemy_attack_map=enemy_attack_map,
|
|
enemy_can_grow=enemy_can_grow, total_occupancy=total_occupancy,
|
|
width=width, height=height, deadline=deadline,
|
|
)
|
|
blocked = info["blocked"]
|
|
point = (pos["x"], pos["y"])
|
|
sc += self._territory_fast(point, blocked, width, height, deadline) * 0.40
|
|
scores[move] = round(sc, 5)
|
|
safety[move] = info
|
|
|
|
if not scores:
|
|
quick = self._deterministic_fallback(safe_moves, width, height)
|
|
self.add_to_history({
|
|
"turn": self.game_board.get_turn(), "mode": "multi",
|
|
"move": quick, "reason": "timeout_budget",
|
|
})
|
|
return quick, {}
|
|
|
|
# Survival tree: safety filter + tiebreaker
|
|
# Run on ALL survivable candidates (not just tied ones) so we can veto death paths
|
|
survivable_candidates = [m for m in scores if safety.get(m, {}).get("is_survivable", False)]
|
|
if not survivable_candidates:
|
|
survivable_candidates = list(scores.keys())
|
|
|
|
tree_bonuses: dict[str, float] = {}
|
|
if self._remaining_ms(deadline) > self._planning_min_ms:
|
|
ranked = sorted(survivable_candidates, key=lambda m: scores[m], reverse=True)[:4]
|
|
for m in ranked:
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
tree_bonuses[m] = self._future_rollout_bonus(
|
|
move=m, safe_moves=safe_moves, my_body=my_body,
|
|
other_snakes=other_snakes, food_set=food_set,
|
|
is_constrictor=False, width=width, height=height,
|
|
enemy_can_grow=enemy_can_grow, deadline=deadline,
|
|
)
|
|
scores[m] += tree_bonuses[m]
|
|
|
|
# Hard veto: exclude moves where tree signals certain death (bonus < -200)
|
|
# Scale is 0.15, so bonus < -200 means tree raw < -1333 (clearly dying)
|
|
DEATH_VETO = -200.0
|
|
safe_after_tree = [m for m in survivable_candidates if tree_bonuses.get(m, 0.0) >= DEATH_VETO]
|
|
vetoed = [m for m in survivable_candidates if m not in safe_after_tree]
|
|
considered = safe_after_tree if safe_after_tree else survivable_candidates
|
|
|
|
if tree_bonuses or vetoed:
|
|
self.add_to_history({
|
|
"turn": self.game_board.get_turn(), "mode": "multi",
|
|
"tree_bonuses": {k: round(v, 3) for k, v in tree_bonuses.items()},
|
|
"vetoed_by_tree": vetoed,
|
|
"considered": considered,
|
|
})
|
|
|
|
return self._select_best(scores, safety, safe_moves, considered), scores
|
|
|
|
# ── Mode: 1v1 duel ────────────────────────────────────────────────────────────
|
|
|
|
def _choose_duel_move(
|
|
self, safe_moves: MoveMap, my_body: list, my_len: int, my_health: int,
|
|
other_snakes: list, food_set: set, hazard_set: set, hazard_damage: int,
|
|
hazard_count: dict, previous_hazard_set: set, enemy_attack_map: dict,
|
|
enemy_can_grow: dict, total_occupancy: float, width: int, height: int,
|
|
deadline: float | None,
|
|
) -> tuple[str, dict[str, float]]:
|
|
enemy = other_snakes[0]
|
|
enemy_len = enemy.get("length", len(enemy["body"]))
|
|
enemy_head = (enemy["head"]["x"], enemy["head"]["y"])
|
|
enemy_health = enemy.get("health", 100)
|
|
can_head_hunt = my_len > enemy_len
|
|
dw = self._duel_weights(self._get_duel_style())
|
|
encase_target = max(8, enemy_len * 2)
|
|
|
|
scores: dict[str, float] = {}
|
|
safety: dict[str, dict] = {}
|
|
|
|
for move, pos in safe_moves.items():
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
sc, info = self._score_move(
|
|
move=move, pos=pos, my_body=my_body, my_len=my_len, my_health=my_health,
|
|
other_snakes=other_snakes, food_set=food_set, hazard_set=hazard_set,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
previous_hazard_set=previous_hazard_set,
|
|
is_constrictor=False, enemy_attack_map=enemy_attack_map,
|
|
enemy_can_grow=enemy_can_grow, total_occupancy=total_occupancy,
|
|
width=width, height=height, deadline=deadline,
|
|
)
|
|
blocked = info["blocked"]
|
|
point = (pos["x"], pos["y"])
|
|
dist = self._manhattan(point, enemy_head)
|
|
ate_food_here = point in food_set
|
|
|
|
# F5: length-growth threshold bonus — reward eating that crosses enemy-length barrier
|
|
if ate_food_here and not info.get("dead_end", False):
|
|
new_len = my_len + 1
|
|
if new_len > enemy_len:
|
|
sc += 160.0
|
|
elif new_len == enemy_len:
|
|
sc += 80.0
|
|
|
|
# Fix #3: enemy confinement metrics per candidate
|
|
enemy_space, enemy_options = self._enemy_confinement_metrics(enemy_head, blocked, width, height)
|
|
is_safe_move = not info.get("dead_end", False) and not info.get("losing_h2h", False)
|
|
|
|
if is_safe_move and enemy_space <= encase_target:
|
|
sc += (encase_target - enemy_space) * 42.0
|
|
sc += max(0, 3 - enemy_options) * 95.0
|
|
if info["reachable_space"] > enemy_space:
|
|
sc += 120.0
|
|
if dist <= 2 and can_head_hunt:
|
|
sc += 40.0
|
|
|
|
if can_head_hunt:
|
|
if dist == 1:
|
|
sc += 220.0 * dw["head_pressure"]
|
|
elif dist == 2:
|
|
sc += 80.0 * dw["head_pressure"]
|
|
else:
|
|
if dist <= 2:
|
|
sc -= 120.0 * dw["distance_safety"]
|
|
if dist == 1:
|
|
sc -= 180.0 * dw["distance_safety"]
|
|
|
|
# Apply duel-style food multiplier on top of the base food bias already added by _score_move.
|
|
# _score_move contributes (30+80*hunger)/(nearest_food+1); here we scale that contribution
|
|
# by (dw["food_bias"] - 1) so the net effect is the full duel-weighted amount.
|
|
nearest_food = info.get("nearest_food")
|
|
if nearest_food is not None and dw["food_bias"] != 1.0:
|
|
hunger = max(0.0, (65.0 - my_health) / 65.0)
|
|
base_food_contribution = (30.0 + 80.0 * hunger) / (nearest_food + 1)
|
|
sc += base_food_contribution * (dw["food_bias"] - 1.0)
|
|
|
|
sc += self._territory_fast(point, blocked, width, height, deadline) * 0.55
|
|
scores[move] = round(sc, 5)
|
|
safety[move] = info
|
|
|
|
if not scores:
|
|
return self._deterministic_fallback(safe_moves, width, height), {}
|
|
|
|
best_move = self._select_best(scores, safety, safe_moves, list(scores))
|
|
|
|
# Fix #1+#9: simultaneous minimax refinement with hazard/health
|
|
if self._remaining_ms(deadline) > 100:
|
|
best_sc = max(scores.values())
|
|
top = [m for m, s in scores.items() if best_sc - s <= 8.0]
|
|
if len(top) > 1:
|
|
mm_scores: dict[str, float] = {}
|
|
for m in top[:3]:
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
pos = safe_moves[m]
|
|
ate = (pos["x"], pos["y"]) in food_set
|
|
fb = self._future_body(my_body, pos, ate, False)
|
|
nmy_h = 100 if ate else my_health - 1
|
|
# C2: food eaten on hazard tile — no hazard penalty this turn (rules fidelity)
|
|
if (pos["x"], pos["y"]) in hazard_set and not ate:
|
|
nmy_h -= hazard_damage * hazard_count.get((pos["x"], pos["y"]), 1)
|
|
mm_val = self._minimax_sim(
|
|
my_body=fb, enemy_body=enemy["body"],
|
|
food_set=food_set, hazard_set=hazard_set,
|
|
my_health=nmy_h, enemy_health=enemy_health,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
width=width, height=height, depth=2,
|
|
alpha=-1e9, beta=1e9, deadline=deadline,
|
|
previous_hazard_set=previous_hazard_set, # D1: spawn-immunity for first minimax level
|
|
)
|
|
mm_scores[m] = scores[m] + mm_val * 0.10
|
|
if mm_scores:
|
|
prev_best = best_move
|
|
best_move = max(mm_scores, key=mm_scores.__getitem__)
|
|
scores = mm_scores
|
|
if best_move != prev_best:
|
|
self.add_to_history({
|
|
"turn": self.game_board.get_turn(), "mode": "duel",
|
|
"minimax_changed_move": True,
|
|
"from": prev_best, "to": best_move,
|
|
"mm_scores": {k: round(v, 3) for k, v in mm_scores.items()},
|
|
})
|
|
|
|
# F2: survival tree post-processing for duel to veto death paths after minimax
|
|
if self._remaining_ms(deadline) > self._planning_min_ms:
|
|
survivable_duel = [m for m in scores if safety.get(m, {}).get("is_survivable", False)]
|
|
if not survivable_duel:
|
|
survivable_duel = list(scores.keys())
|
|
duel_tree: dict[str, float] = {}
|
|
for m in sorted(survivable_duel, key=lambda m: scores[m], reverse=True)[:3]:
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
duel_tree[m] = self._future_rollout_bonus(
|
|
move=m, safe_moves=safe_moves, my_body=my_body,
|
|
other_snakes=other_snakes, food_set=food_set,
|
|
is_constrictor=False, width=width, height=height,
|
|
enemy_can_grow=enemy_can_grow, deadline=deadline,
|
|
)
|
|
scores[m] += duel_tree[m]
|
|
DEATH_VETO = -200.0
|
|
safe_duel_tree = [m for m in survivable_duel if duel_tree.get(m, 0.0) >= DEATH_VETO]
|
|
vetoed_duel = [m for m in survivable_duel if m not in safe_duel_tree]
|
|
if safe_duel_tree:
|
|
prev_best = best_move
|
|
best_move = max(safe_duel_tree, key=lambda m: scores[m])
|
|
if duel_tree or vetoed_duel:
|
|
self.add_to_history({
|
|
"turn": self.game_board.get_turn(), "mode": "duel",
|
|
"tree_bonuses": {k: round(v, 3) for k, v in duel_tree.items()},
|
|
"vetoed_by_tree": vetoed_duel,
|
|
"tree_changed_move": best_move != prev_best,
|
|
})
|
|
|
|
return best_move, scores
|
|
|
|
# ── Mode: constrictor ─────────────────────────────────────────────────────────
|
|
|
|
def _choose_constrictor_move(
|
|
self, safe_moves: MoveMap, my_body: list, my_len: int, my_health: int,
|
|
other_snakes: list, food_set: set, hazard_set: set, hazard_damage: int,
|
|
hazard_count: dict, previous_hazard_set: set, enemy_attack_map: dict,
|
|
enemy_can_grow: dict, total_occupancy: float, width: int, height: int,
|
|
deadline: float | None,
|
|
) -> tuple[str, dict[str, float]]:
|
|
scores: dict[str, float] = {}
|
|
safety: dict[str, dict] = {}
|
|
|
|
for move, pos in safe_moves.items():
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
sc, info = self._score_move(
|
|
move=move, pos=pos, my_body=my_body, my_len=my_len, my_health=my_health,
|
|
other_snakes=other_snakes, food_set=food_set, hazard_set=hazard_set,
|
|
hazard_damage=hazard_damage, hazard_count=hazard_count,
|
|
previous_hazard_set=previous_hazard_set,
|
|
is_constrictor=True, enemy_attack_map=enemy_attack_map,
|
|
enemy_can_grow=enemy_can_grow, total_occupancy=total_occupancy,
|
|
width=width, height=height, deadline=deadline,
|
|
)
|
|
blocked = info["blocked"]
|
|
point = (pos["x"], pos["y"])
|
|
|
|
# Fix #4: enemy constrictor projection
|
|
enemy_best_space, enemy_total_opts = self._enemy_constrictor_projection(
|
|
other_snakes=other_snakes, blocked=blocked, width=width, height=height,
|
|
)
|
|
sc += (info["reachable_space"] - enemy_best_space) * 3.2
|
|
sc += max(0, 8 - enemy_total_opts) * 18.0
|
|
if enemy_total_opts <= 2:
|
|
sc += 110.0
|
|
if enemy_best_space > int(info["reachable_space"] * 1.2):
|
|
sc -= 320.0
|
|
|
|
sc += info["reachable_space"] * 0.8
|
|
sc += self._territory_fast(point, blocked, width, height, deadline) * 0.65
|
|
scores[move] = round(sc, 5)
|
|
safety[move] = info
|
|
|
|
if not scores:
|
|
return self._deterministic_fallback(safe_moves, width, height), {}
|
|
|
|
# F2: survival tree for constrictor mode
|
|
survivable_const = [m for m in scores if safety.get(m, {}).get("is_survivable", False)]
|
|
if not survivable_const:
|
|
survivable_const = list(scores.keys())
|
|
|
|
tree_bonuses_c: dict[str, float] = {}
|
|
if self._remaining_ms(deadline) > self._planning_min_ms:
|
|
ranked_c = sorted(survivable_const, key=lambda m: scores[m], reverse=True)[:4]
|
|
for m in ranked_c:
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
tree_bonuses_c[m] = self._future_rollout_bonus(
|
|
move=m, safe_moves=safe_moves, my_body=my_body,
|
|
other_snakes=other_snakes, food_set=food_set,
|
|
is_constrictor=True, width=width, height=height,
|
|
enemy_can_grow=enemy_can_grow, deadline=deadline,
|
|
)
|
|
scores[m] += tree_bonuses_c[m]
|
|
|
|
DEATH_VETO = -200.0
|
|
safe_after_tree_c = [m for m in survivable_const if tree_bonuses_c.get(m, 0.0) >= DEATH_VETO]
|
|
vetoed_c = [m for m in survivable_const if m not in safe_after_tree_c]
|
|
considered_c = safe_after_tree_c if safe_after_tree_c else survivable_const
|
|
|
|
if tree_bonuses_c or vetoed_c:
|
|
self.add_to_history({
|
|
"turn": self.game_board.get_turn(), "mode": "constrictor",
|
|
"tree_bonuses": {k: round(v, 3) for k, v in tree_bonuses_c.items()},
|
|
"vetoed_by_tree": vetoed_c,
|
|
"considered": considered_c,
|
|
})
|
|
|
|
return self._select_best(scores, safety, safe_moves, considered_c), scores
|
|
|
|
# ── Unified move scorer ───────────────────────────────────────────────────────
|
|
|
|
def _score_move(
|
|
self, move: str, pos: Coord, my_body: list, my_len: int, my_health: int,
|
|
other_snakes: list, food_set: set, hazard_set: set, hazard_damage: int,
|
|
hazard_count: dict, previous_hazard_set: set, is_constrictor: bool,
|
|
enemy_attack_map: dict, enemy_can_grow: dict, total_occupancy: float,
|
|
width: int, height: int, deadline: float | None,
|
|
) -> tuple[float, dict]:
|
|
point = (pos["x"], pos["y"])
|
|
ate_food = point in food_set
|
|
|
|
# Fix #14: compute once, return in info for callers to reuse
|
|
future_body = self._future_body(my_body, pos, ate_food, is_constrictor)
|
|
blocked = self._simulation_blocked(future_body, other_snakes, food_set, is_constrictor, enemy_can_grow)
|
|
blocked.discard(point)
|
|
|
|
# F11: constrictor dead-end buffer — require extra margin proportional to body length
|
|
if is_constrictor:
|
|
required_space = len(future_body) + max(3, len(future_body) // 6)
|
|
else:
|
|
required_space = len(future_body)
|
|
|
|
# F6: optimistic flood fill — assume all enemy tails vacate (best-case reachable)
|
|
opt_blocked = set(blocked)
|
|
if not is_constrictor:
|
|
for snake in other_snakes:
|
|
opt_blocked.discard((snake["body"][-1]["x"], snake["body"][-1]["y"]))
|
|
reachable_space = self._flood_fill_count(point, opt_blocked, width, height)
|
|
liberties = self._open_neighbor_count(point, blocked, width, height)
|
|
next_opts = self._next_turn_options(future_body[0], blocked, width, height)
|
|
|
|
# Fix #6: _safe_next_options uses the pre-built attack map — no rebuild
|
|
en_safe_opts = self._safe_next_options(
|
|
future_body=future_body, my_len=my_len, blocked=blocked,
|
|
enemy_attack_map=enemy_attack_map, food_set=food_set,
|
|
is_constrictor=is_constrictor, width=width, height=height,
|
|
)
|
|
|
|
# Fix #8: articulation penalty scales with partition size; BFS limit = board area
|
|
art_penalty = self._articulation_penalty(point, blocked, width, height, required_space)
|
|
|
|
# Tail escape
|
|
future_tail = future_body[-1]
|
|
tail_pt = (future_tail["x"], future_tail["y"])
|
|
tail_dist = self._path_distance(point, tail_pt, blocked - {tail_pt}, width, height)
|
|
has_tail_escape = tail_dist is not None
|
|
|
|
# F4/10: nearest food + contest check using precomputed enemy dmaps (O(1) per enemy)
|
|
nearest_food, nearest_food_pt = self._nearest_food_info(point, food_set, blocked, width, height)
|
|
food_contested = False
|
|
if nearest_food_pt is not None and nearest_food is not None:
|
|
for em in self._enemy_dmaps:
|
|
en_dist = em.get(nearest_food_pt)
|
|
if en_dist is not None and en_dist <= nearest_food:
|
|
food_contested = True
|
|
break
|
|
|
|
# Enemy threat
|
|
enemy_len_here = enemy_attack_map.get(point)
|
|
losing_h2h = enemy_len_here is not None and enemy_len_here >= my_len
|
|
|
|
# F8: H2H distance-2 penalty using precomputed enemy dmaps
|
|
h2h_dist2_penalty = 0.0
|
|
for i, em in enumerate(self._enemy_dmaps):
|
|
d = em.get(point)
|
|
if d is not None and d == 2 and i < len(other_snakes):
|
|
en_len = other_snakes[i].get("length", len(other_snakes[i]["body"]))
|
|
if en_len >= my_len:
|
|
h2h_dist2_penalty = max(h2h_dist2_penalty, 90.0)
|
|
else:
|
|
h2h_dist2_penalty = max(h2h_dist2_penalty, -40.0) # hunting opportunity
|
|
|
|
# Dead-end detection (constrictor: no tail escape modifier)
|
|
if is_constrictor:
|
|
dead_end = reachable_space < required_space or liberties == 0 or next_opts == 0
|
|
else:
|
|
dead_end = (
|
|
(reachable_space < required_space and not has_tail_escape)
|
|
or (liberties == 0 and not has_tail_escape)
|
|
or (next_opts == 0 and not has_tail_escape)
|
|
)
|
|
|
|
# Center gravity
|
|
cx, cy = (width - 1) / 2.0, (height - 1) / 2.0
|
|
center_score = 1.0 - (abs(point[0] - cx) + abs(point[1] - cy)) / max(1.0, cx + cy)
|
|
|
|
# F9: corner/edge geometric penalty scaled by board occupancy
|
|
min_wall_dist = min(point[0], width - 1 - point[0], point[1], height - 1 - point[1])
|
|
if total_occupancy > 0.25:
|
|
if min_wall_dist == 0:
|
|
edge_penalty = 35.0 * total_occupancy
|
|
elif min_wall_dist == 1:
|
|
edge_penalty = 15.0 * total_occupancy
|
|
else:
|
|
edge_penalty = 0.0
|
|
else:
|
|
edge_penalty = 0.0
|
|
|
|
hunger = max(0.0, (60.0 - my_health) / 60.0)
|
|
|
|
# C1: use per-tile stack depth for accurate health simulation
|
|
hazard_stack = hazard_count.get(point, 1) if point in hazard_set else 1
|
|
# Simulated health after move
|
|
health_after = 100 if ate_food else my_health - 1
|
|
# C2: food eaten on hazard tile — no hazard penalty (rules fidelity)
|
|
if point in hazard_set and not ate_food and point in previous_hazard_set:
|
|
health_after -= hazard_damage * hazard_stack
|
|
|
|
# Fix #11: hazard corridor death check
|
|
hazard_will_kill = (
|
|
not ate_food and point in hazard_set and point in previous_hazard_set
|
|
and self._hazard_will_kill(point, hazard_set, hazard_count, blocked, width, height, my_health, hazard_damage)
|
|
)
|
|
|
|
# ── Score assembly ────────────────────────────────────────────────────────
|
|
score = 0.0
|
|
|
|
score += reachable_space * 3.0
|
|
score += liberties * 20.0
|
|
score += next_opts * 10.0
|
|
score += en_safe_opts * 24.0
|
|
score += center_score * 14.0
|
|
|
|
if en_safe_opts == 0:
|
|
score -= 1700.0
|
|
elif en_safe_opts == 1:
|
|
score -= 420.0
|
|
|
|
score -= art_penalty
|
|
score -= edge_penalty
|
|
score -= h2h_dist2_penalty
|
|
|
|
if dead_end:
|
|
score -= 1500.0
|
|
if reachable_space < required_space:
|
|
score -= 1200.0
|
|
if liberties == 0:
|
|
score -= 900.0
|
|
if next_opts == 0:
|
|
score -= 600.0
|
|
|
|
if losing_h2h:
|
|
score -= 1400.0
|
|
elif enemy_len_here is not None:
|
|
score += 80.0
|
|
|
|
# Fix #7: preserve space based on total occupancy, not just our length
|
|
preserve_space = total_occupancy >= 0.34 and my_health > 35
|
|
if nearest_food is not None:
|
|
# F4: contested food is worth less (enemy can grab it at same/sooner distance)
|
|
contest_multiplier = 0.55 if food_contested else 1.0
|
|
score += ((30.0 + 80.0 * hunger) / (nearest_food + 1)) * contest_multiplier
|
|
# F3: starvation lookahead — heavy penalty if we can't reach food before health runs out
|
|
if my_health < 40 and nearest_food >= health_after:
|
|
score -= 800.0 + (40 - my_health) * 20.0
|
|
elif my_health < 30:
|
|
score -= 160.0
|
|
|
|
if ate_food:
|
|
if dead_end:
|
|
score -= 1800.0
|
|
else:
|
|
score += 280.0 + 230.0 * hunger
|
|
if preserve_space and ate_food and my_health > 45:
|
|
score -= 300.0
|
|
|
|
if tail_dist is not None:
|
|
score += 14.0 / (tail_dist + 1)
|
|
else:
|
|
score -= 45.0
|
|
|
|
if point in hazard_set:
|
|
# C1: scale penalty by stack depth (Snail Mode stacked tiles are more dangerous)
|
|
scale = max(0.5, hazard_damage * hazard_stack / 14.0)
|
|
if not ate_food:
|
|
score -= (80.0 if my_health > 35 else 270.0) * scale
|
|
if hazard_will_kill:
|
|
score -= 10000.0
|
|
|
|
# E3: Snail Mode trail scoring
|
|
# Penalise moves that place us in hazard-dense neighbourhoods (future stack risk),
|
|
# reward moves toward hazard-free space (safer continuation).
|
|
if self._is_snail and hazard_set:
|
|
adjacent_hazard_stack = sum(
|
|
hazard_count.get(n, 1)
|
|
for n in self._neighbors(point)
|
|
if n in hazard_set
|
|
)
|
|
# Each unit of adjacent total stack costs health faster next turn
|
|
if adjacent_hazard_stack > 0:
|
|
score -= adjacent_hazard_stack * 6.0
|
|
# Bonus for having hazard-free neighbours (escape routes)
|
|
hazard_free_neighbors = sum(
|
|
1 for n in self._neighbors(point)
|
|
if self._in_bounds(n, width, height) and n not in hazard_set and n not in blocked
|
|
)
|
|
score += hazard_free_neighbors * 8.0
|
|
|
|
# F12: territory call REMOVED from here — callers (_choose_*_move) apply it after _score_move
|
|
|
|
score -= self._revisit_penalty(point)
|
|
|
|
if self.last_move == move:
|
|
score += 6.0
|
|
elif self.last_move and self.OPPOSITE.get(self.last_move) == move and len(other_snakes) > 0:
|
|
score -= 20.0
|
|
|
|
if health_after <= 0:
|
|
score -= 10000.0
|
|
|
|
info = {
|
|
"is_survivable": (
|
|
not dead_end and not losing_h2h
|
|
and en_safe_opts > 0 and health_after > 0
|
|
and not hazard_will_kill
|
|
),
|
|
"reachable_space": reachable_space,
|
|
"tail_escape": has_tail_escape,
|
|
"nearest_food": nearest_food,
|
|
"dead_end": dead_end,
|
|
"losing_h2h": losing_h2h,
|
|
# Fix #14: return computed sets for callers to reuse
|
|
"future_body": future_body,
|
|
"blocked": blocked,
|
|
}
|
|
return round(score, 5), info
|
|
|
|
# ── Territory: precomputed enemy dmaps with per-candidate refresh ──────────────
|
|
|
|
def _territory_fast(
|
|
self, my_pos: tuple, blocked: set, width: int, height: int,
|
|
deadline: float | None = None,
|
|
) -> int:
|
|
if not self._enemy_heads:
|
|
return 0
|
|
# Fix #2: recompute enemy dmaps with candidate-specific blocked when time allows
|
|
if deadline is not None and self._remaining_ms(deadline) > 150:
|
|
enemy_dmaps = [self._distance_map(eh, blocked, width, height) for eh in self._enemy_heads]
|
|
else:
|
|
enemy_dmaps = self._enemy_dmaps # fast approximation
|
|
|
|
my_dmap = self._distance_map(my_pos, blocked, width, height)
|
|
score = 0
|
|
for x in range(width):
|
|
for y in range(height):
|
|
pt = (x, y)
|
|
if pt in blocked:
|
|
continue
|
|
my_d = my_dmap.get(pt)
|
|
if my_d is None:
|
|
continue
|
|
enemy_best: int | None = None
|
|
for em in enemy_dmaps:
|
|
ed = em.get(pt)
|
|
if ed is not None and (enemy_best is None or ed < enemy_best):
|
|
enemy_best = ed
|
|
if enemy_best is None or my_d < enemy_best:
|
|
score += 1
|
|
elif enemy_best < my_d:
|
|
score -= 1
|
|
return score
|
|
|
|
# ── Move selector ─────────────────────────────────────────────────────────────
|
|
|
|
def _deterministic_fallback(self, safe_moves: MoveMap, width: int = 11, height: int = 11) -> str:
|
|
"""D3: Deterministic degrade ladder — last_move > center proximity > lexical order."""
|
|
if self.last_move and self.last_move in safe_moves:
|
|
return self.last_move
|
|
cx, cy = (width - 1) / 2.0, (height - 1) / 2.0
|
|
return min(
|
|
safe_moves,
|
|
key=lambda m: (abs(safe_moves[m]["x"] - cx) + abs(safe_moves[m]["y"] - cy), m),
|
|
)
|
|
|
|
def _select_best(
|
|
self, scores: dict[str, float], safety: dict[str, dict],
|
|
safe_moves: MoveMap, considered: list[str],
|
|
) -> str:
|
|
# Filter to survivable within considered
|
|
survivable = [m for m in considered if safety.get(m, {}).get("is_survivable", False)]
|
|
pool = survivable if survivable else (considered if considered else list(scores))
|
|
if not pool:
|
|
return self._deterministic_fallback(safe_moves)
|
|
|
|
best_sc = max(scores.get(m, -1e9) for m in pool)
|
|
|
|
# Fix #13: tail-escape as score-window tiebreaker (not primary filter)
|
|
tail_pool = [
|
|
m for m in pool
|
|
if safety.get(m, {}).get("tail_escape", False)
|
|
and best_sc - scores.get(m, -1e9) <= 5.0
|
|
]
|
|
final_pool = tail_pool if tail_pool else pool
|
|
return max(final_pool, key=lambda m: scores.get(m, -1e9))
|
|
|
|
# ── Simultaneous minimax (fixes #1 + #9) ─────────────────────────────────────
|
|
|
|
def _minimax_sim(
|
|
self, my_body: list, enemy_body: list, food_set: set, hazard_set: set,
|
|
my_health: int, enemy_health: int, hazard_damage: int, hazard_count: dict,
|
|
width: int, height: int, depth: int,
|
|
alpha: float, beta: float, deadline: float | None,
|
|
previous_hazard_set: set | None = None,
|
|
) -> float:
|
|
# D1: spawn-immunity — effective prev set; None means treat all current hazards as old
|
|
eff_prev = previous_hazard_set if previous_hazard_set is not None else hazard_set
|
|
if depth <= 0 or self._time_exceeded(deadline):
|
|
return self._minimax_eval(my_body, enemy_body, width, height)
|
|
|
|
my_h = my_body[0]
|
|
en_h = enemy_body[0]
|
|
|
|
# Occupied: bodies excluding tails that will vacate this turn.
|
|
# A tail only vacates if the snake is NOT stacked (i.e. didn't eat food last turn).
|
|
my_occ = {(s["x"], s["y"]) for s in my_body}
|
|
if not self._is_tail_stacked(my_body):
|
|
my_occ.discard((my_body[-1]["x"], my_body[-1]["y"]))
|
|
en_occ = {(s["x"], s["y"]) for s in enemy_body}
|
|
if not self._is_tail_stacked(enemy_body):
|
|
en_occ.discard((enemy_body[-1]["x"], enemy_body[-1]["y"]))
|
|
all_occ = my_occ | en_occ
|
|
|
|
my_moves = []
|
|
for dx, dy in self.DIRECTIONS.values():
|
|
pt = (my_h["x"] + dx, my_h["y"] + dy)
|
|
if self._in_bounds(pt, width, height) and pt not in all_occ:
|
|
my_moves.append(pt)
|
|
|
|
en_moves = []
|
|
for dx, dy in self.DIRECTIONS.values():
|
|
pt = (en_h["x"] + dx, en_h["y"] + dy)
|
|
if self._in_bounds(pt, width, height) and pt not in all_occ:
|
|
en_moves.append(pt)
|
|
|
|
if not my_moves:
|
|
return -3000.0
|
|
if not en_moves:
|
|
return 3000.0
|
|
|
|
# F1: sort moves by food/center heuristic for better alpha-beta pruning
|
|
my_moves = self._sort_minimax_moves(my_moves, food_set, width, height)
|
|
en_moves = self._sort_minimax_moves(en_moves, food_set, width, height)
|
|
|
|
# Paranoid simultaneous minimax: maximise over my moves, minimise over enemy moves
|
|
best = -1e9
|
|
for my_pt in my_moves:
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
worst = 1e9
|
|
for en_pt in en_moves:
|
|
# Resolve simultaneous move
|
|
if my_pt == en_pt:
|
|
# Head-to-head collision
|
|
ml, el = len(my_body), len(enemy_body)
|
|
val = 2000.0 if ml > el else (-2000.0 if ml < el else -500.0)
|
|
else:
|
|
my_ate = my_pt in food_set
|
|
en_ate = en_pt in food_set
|
|
new_my = self._future_body(my_body, {"x": my_pt[0], "y": my_pt[1]}, my_ate, False)
|
|
new_en = self._future_body(enemy_body, {"x": en_pt[0], "y": en_pt[1]}, en_ate, False)
|
|
|
|
nmy_h = 100 if my_ate else my_health - 1
|
|
nen_h = 100 if en_ate else enemy_health - 1
|
|
# C2: food consumed on hazard tile = no hazard penalty (rules fidelity)
|
|
# C1: scale damage by stack depth for Snail Mode accuracy
|
|
# D1: spawn-immunity — only charge damage if hazard existed before this move
|
|
if my_pt in hazard_set and not my_ate and my_pt in eff_prev:
|
|
nmy_h -= hazard_damage * hazard_count.get(my_pt, 1)
|
|
if en_pt in hazard_set and not en_ate and en_pt in eff_prev:
|
|
nen_h -= hazard_damage * hazard_count.get(en_pt, 1)
|
|
|
|
if nmy_h <= 0 and nen_h <= 0:
|
|
val = -500.0
|
|
elif nmy_h <= 0:
|
|
val = -3000.0
|
|
elif nen_h <= 0:
|
|
val = 3000.0
|
|
else:
|
|
val = self._minimax_sim(
|
|
new_my, new_en, food_set, hazard_set,
|
|
nmy_h, nen_h, hazard_damage, hazard_count, width, height,
|
|
depth - 1, alpha, beta, deadline,
|
|
previous_hazard_set=hazard_set, # D1: after this turn, current hazards are old
|
|
)
|
|
|
|
worst = min(worst, val)
|
|
if worst <= alpha:
|
|
break # alpha prune inner loop
|
|
|
|
best = max(best, worst)
|
|
alpha = max(alpha, best)
|
|
if alpha >= beta:
|
|
break # beta prune outer loop
|
|
|
|
return best
|
|
|
|
def _sort_minimax_moves(self, moves: list, food_set: set, width: int, height: int) -> list:
|
|
"""F1: Sort candidate positions — food first, then by distance to center (better pruning)."""
|
|
cx, cy = width / 2.0, height / 2.0
|
|
return sorted(moves, key=lambda pt: (0 if pt in food_set else 1, abs(pt[0] - cx) + abs(pt[1] - cy)))
|
|
|
|
def _minimax_eval(self, my_body: list, enemy_body: list, width: int, height: int) -> float:
|
|
my_head = (my_body[0]["x"], my_body[0]["y"])
|
|
en_head = (enemy_body[0]["x"], enemy_body[0]["y"])
|
|
shared = (
|
|
{(s["x"], s["y"]) for s in my_body[1:]} |
|
|
{(s["x"], s["y"]) for s in enemy_body[1:]}
|
|
)
|
|
my_space = self._flood_fill_count(my_head, shared - {my_head}, width, height)
|
|
en_space = self._flood_fill_count(en_head, shared - {en_head}, width, height)
|
|
return float(my_space - en_space)
|
|
|
|
# ── Survival tree lookahead (fix #5) ─────────────────────────────────────────
|
|
|
|
def _future_rollout_bonus(
|
|
self, move: str, safe_moves: MoveMap, my_body: list, other_snakes: list,
|
|
food_set: set, is_constrictor: bool, width: int, height: int,
|
|
enemy_can_grow: dict, deadline: float | None,
|
|
) -> float:
|
|
pos = safe_moves.get(move)
|
|
if pos is None:
|
|
return -250.0
|
|
point = (pos["x"], pos["y"])
|
|
ate = point in food_set
|
|
future_body = self._future_body(my_body, pos, ate, is_constrictor)
|
|
raw = self._future_survival_tree(
|
|
my_body=future_body, other_snakes=other_snakes, food_set=food_set,
|
|
is_constrictor=is_constrictor, width=width, height=height,
|
|
enemy_can_grow=enemy_can_grow,
|
|
depth=self._planning_depth, branch=self._planning_branch, deadline=deadline,
|
|
)
|
|
# Scale 0.15: certain-death raw (-5000) → -750 bonus, healthy path (+1000) → +150 bonus
|
|
# Strong enough to veto bad moves but not override large legitimate score gaps
|
|
return raw * 0.15
|
|
|
|
# Scores below this in _future_position_score are considered certain death
|
|
_TREE_DEATH_THRESHOLD = -3000.0
|
|
|
|
def _future_survival_tree(
|
|
self, my_body: list, other_snakes: list, food_set: set, is_constrictor: bool,
|
|
width: int, height: int, enemy_can_grow: dict,
|
|
depth: int, branch: int, deadline: float | None,
|
|
) -> float:
|
|
if depth <= 0 or self._time_exceeded(deadline):
|
|
return 0.0
|
|
my_head = my_body[0]
|
|
moves = self._legal_moves(my_head, my_body, other_snakes, food_set, is_constrictor, width, height, enemy_can_grow)
|
|
if not moves:
|
|
return -5000.0 # no legal moves = dead
|
|
|
|
scored: list[tuple[float, list]] = []
|
|
for pos in moves.values():
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
pt = (pos["x"], pos["y"])
|
|
ate = pt in food_set
|
|
fb = self._future_body(my_body, pos, ate, is_constrictor)
|
|
sc = self._future_position_score(fb, other_snakes, food_set, is_constrictor, width, height, enemy_can_grow, deadline)
|
|
scored.append((sc, fb))
|
|
|
|
if not scored:
|
|
return -5000.0
|
|
|
|
# Separate viable options from certain-death options
|
|
viable = [(sc, fb) for sc, fb in scored if sc > self._TREE_DEATH_THRESHOLD]
|
|
if not viable:
|
|
# All paths are deadly — return best of a bad situation (least negative)
|
|
return max(sc for sc, _ in scored)
|
|
|
|
viable.sort(key=lambda x: x[0], reverse=True)
|
|
|
|
if depth == 1:
|
|
return viable[0][0]
|
|
|
|
best = viable[0][0]
|
|
for sc, fb in viable[:branch]:
|
|
if self._time_exceeded(deadline):
|
|
break
|
|
cont = self._future_survival_tree(
|
|
fb, other_snakes, food_set, is_constrictor,
|
|
width, height, enemy_can_grow, depth - 1, branch, deadline,
|
|
)
|
|
total = sc + cont * 0.72
|
|
if total > best:
|
|
best = total
|
|
return best
|
|
|
|
def _future_position_score(
|
|
self, my_body: list, other_snakes: list, food_set: set, is_constrictor: bool,
|
|
width: int, height: int, enemy_can_grow: dict, deadline: float | None,
|
|
) -> float:
|
|
if self._time_exceeded(deadline):
|
|
return 0.0
|
|
head = (my_body[0]["x"], my_body[0]["y"])
|
|
blocked = self._simulation_blocked(my_body, other_snakes, food_set, is_constrictor, enemy_can_grow)
|
|
blocked.discard(head)
|
|
|
|
reachable = self._flood_fill_count(head, blocked, width, height)
|
|
# F11: constrictor dead-end buffer in survival tree too
|
|
if is_constrictor:
|
|
required = len(my_body) + max(3, len(my_body) // 6)
|
|
else:
|
|
required = len(my_body)
|
|
|
|
# Hard death conditions: return -5000 immediately so the tree treats this
|
|
# as certain death and doesn't recurse further into this branch
|
|
if reachable < required:
|
|
return -5000.0
|
|
|
|
liberties = self._open_neighbor_count(head, blocked, width, height)
|
|
if liberties == 0:
|
|
return -5000.0
|
|
|
|
next_opts = self._next_turn_options(my_body[0], blocked, width, height)
|
|
if next_opts == 0:
|
|
return -5000.0
|
|
|
|
# Build attack map for safe option count
|
|
future_snake = {"head": my_body[0], "body": my_body, "length": len(my_body), "id": "__future__"}
|
|
atk = self._build_enemy_attack_map(future_snake, other_snakes, food_set, is_constrictor, width, height, enemy_can_grow)
|
|
en_safe = self._safe_next_options(my_body, len(my_body), blocked, atk, food_set, is_constrictor, width, height)
|
|
|
|
# Zero safe options = will be forced into a losing head-to-head next turn
|
|
if en_safe == 0:
|
|
return -4000.0
|
|
|
|
sc = reachable * 1.9 + liberties * 14.0 + next_opts * 11.0 + en_safe * 26.0
|
|
if en_safe == 1:
|
|
sc -= 420.0
|
|
return sc
|
|
|
|
# ── Articulation point detection (fix #8) ────────────────────────────────────
|
|
|
|
def _articulation_penalty(
|
|
self, point: tuple, blocked: set, width: int, height: int, required_space: int,
|
|
) -> float:
|
|
"""Scaled penalty: mild if survivable partitions, severe if smallest < required_space."""
|
|
neighbors = [
|
|
n for n in self._neighbors(point)
|
|
if self._in_bounds(n, width, height) and n not in blocked
|
|
]
|
|
if len(neighbors) <= 1:
|
|
return 0.0
|
|
|
|
# Fix #15: use full board area as BFS limit
|
|
board_limit = width * height
|
|
test_blocked = blocked | {point}
|
|
seen_all: set[tuple] = set()
|
|
partition_sizes: list[int] = []
|
|
|
|
for n in neighbors:
|
|
if n in seen_all:
|
|
continue
|
|
part = self._bounded_bfs(n, test_blocked, width, height, limit=board_limit)
|
|
seen_all |= part
|
|
partition_sizes.append(len(part))
|
|
|
|
if len(partition_sizes) <= 1:
|
|
return 0.0 # all neighbors connect to same region — not a cut vertex
|
|
|
|
min_size = min(partition_sizes)
|
|
if min_size < required_space:
|
|
return 1500.0 # entering traps us in a too-small partition
|
|
elif min_size < required_space * 2:
|
|
return 400.0 # risky but survivable
|
|
else:
|
|
return 85.0 # soft warning
|
|
|
|
def _bounded_bfs(self, start: tuple, blocked: set, width: int, height: int, limit: int) -> set:
|
|
queue = deque([start])
|
|
seen = {start}
|
|
while queue and len(seen) < limit:
|
|
pt = queue.popleft()
|
|
for n in self._neighbors(pt):
|
|
if n in seen or not self._in_bounds(n, width, height) or n in blocked:
|
|
continue
|
|
seen.add(n)
|
|
queue.append(n)
|
|
return seen
|
|
|
|
# ── Hazard multi-step check (fix #11) ────────────────────────────────────────
|
|
|
|
def _hazard_will_kill(
|
|
self, point: tuple, hazard_set: set, hazard_count: dict, blocked: set,
|
|
width: int, height: int, health: int, hazard_damage: int,
|
|
) -> bool:
|
|
"""Return True if entering this hazard cell leads to death before reaching a safe cell.
|
|
C3: each turn in hazard costs 1 (baseline) + hazard_damage * stack; exit costs 1.
|
|
D2: Dijkstra with per-tile stack cost replaces fixed entry_stack for entire corridor.
|
|
"""
|
|
if hazard_damage <= 0:
|
|
return False
|
|
# D2: Dijkstra — accumulate damage per tile to find minimum-cost path to any non-hazard cell
|
|
# Entry cost includes this turn's hazard damage for landing on point
|
|
entry_cost = 1 + hazard_damage * hazard_count.get(point, 1)
|
|
heap: list[tuple[int, tuple]] = [(entry_cost, point)]
|
|
best: dict[tuple, int] = {point: entry_cost}
|
|
while heap:
|
|
cost, pt = heapq.heappop(heap)
|
|
if cost > best.get(pt, 10**9):
|
|
continue
|
|
if pt not in hazard_set:
|
|
return health - cost <= 0
|
|
for n in self._neighbors(pt):
|
|
if not self._in_bounds(n, width, height) or n in blocked:
|
|
continue
|
|
step = (1 + hazard_damage * hazard_count.get(n, 1)) if n in hazard_set else 1
|
|
nc = cost + step
|
|
if nc < best.get(n, 10**9):
|
|
best[n] = nc
|
|
heapq.heappush(heap, (nc, n))
|
|
return True # no exit reachable = fatal
|
|
|
|
# ── Duel + constrictor helpers ────────────────────────────────────────────────
|
|
|
|
def _enemy_confinement_metrics(
|
|
self, enemy_head: tuple, blocked: set, width: int, height: int,
|
|
) -> tuple[int, int]:
|
|
eb = set(blocked)
|
|
eb.discard(enemy_head)
|
|
space = self._flood_fill_count(enemy_head, eb, width, height)
|
|
options = self._open_neighbor_count(enemy_head, eb, width, height)
|
|
return space, options
|
|
|
|
def _enemy_constrictor_projection(
|
|
self, other_snakes: list, blocked: set, width: int, height: int,
|
|
) -> tuple[int, int]:
|
|
best_space = 0
|
|
total_opts = 0
|
|
for enemy in other_snakes:
|
|
eh = (enemy["head"]["x"], enemy["head"]["y"])
|
|
snake_best = 0
|
|
for n in self._neighbors(eh):
|
|
if not self._in_bounds(n, width, height) or n in blocked:
|
|
continue
|
|
total_opts += 1
|
|
sp = self._flood_fill_count(n, blocked | {n}, width, height)
|
|
snake_best = max(snake_best, sp)
|
|
best_space = max(best_space, snake_best)
|
|
return best_space, total_opts
|
|
|
|
# ── Anti-trapping helpers (fix #6 — use pre-built attack map) ────────────────
|
|
|
|
def _next_turn_options(self, head: Coord, blocked: set, width: int, height: int) -> int:
|
|
return sum(
|
|
1 for dx, dy in self.DIRECTIONS.values()
|
|
if self._in_bounds((head["x"] + dx, head["y"] + dy), width, height)
|
|
and (head["x"] + dx, head["y"] + dy) not in blocked
|
|
)
|
|
|
|
def _safe_next_options(
|
|
self, future_body: list, my_len: int, blocked: set,
|
|
enemy_attack_map: dict, food_set: set, is_constrictor: bool,
|
|
width: int, height: int,
|
|
) -> int:
|
|
"""Count next-turn moves not contested. Uses pre-built attack map — no rebuild."""
|
|
own_tail = (future_body[-1]["x"], future_body[-1]["y"])
|
|
own_tail_stacked = self._is_tail_stacked(future_body)
|
|
head = future_body[0]
|
|
count = 0
|
|
for dx, dy in self.DIRECTIONS.values():
|
|
pt = (head["x"] + dx, head["y"] + dy)
|
|
if not self._in_bounds(pt, width, height):
|
|
continue
|
|
ate = pt in food_set
|
|
can_step = self._can_step_on_own_tail(pt, own_tail, own_tail_stacked, ate, is_constrictor)
|
|
if pt in blocked and not can_step:
|
|
continue
|
|
en_len = enemy_attack_map.get(pt)
|
|
if en_len is not None and en_len >= my_len:
|
|
continue
|
|
count += 1
|
|
return count
|
|
|
|
# ── Board state helpers ───────────────────────────────────────────────────────
|
|
|
|
def _compute_base_blocked(
|
|
self, my_body: list, other_snakes: list, is_constrictor: bool,
|
|
enemy_can_grow: dict | None = None, food_set: set | None = None,
|
|
) -> set:
|
|
blocked = {(s["x"], s["y"]) for s in my_body}
|
|
if not is_constrictor and not self._is_tail_stacked(my_body):
|
|
blocked.discard((my_body[-1]["x"], my_body[-1]["y"]))
|
|
for snake in other_snakes:
|
|
for seg in snake["body"]:
|
|
blocked.add((seg["x"], seg["y"]))
|
|
if is_constrictor:
|
|
continue
|
|
if self._is_tail_stacked(snake["body"]):
|
|
continue
|
|
snake_id = snake.get("id")
|
|
can_grow: bool | None = None
|
|
if enemy_can_grow is not None and snake_id is not None:
|
|
can_grow = enemy_can_grow.get(snake_id)
|
|
if can_grow is None and food_set is not None:
|
|
can_grow = self._enemy_can_grow_this_turn(snake, food_set)
|
|
if can_grow:
|
|
continue
|
|
blocked.discard((snake["body"][-1]["x"], snake["body"][-1]["y"]))
|
|
return blocked
|
|
|
|
def _legal_moves(
|
|
self, my_head: Coord, my_body: list, other_snakes: list,
|
|
food_set: set, is_constrictor: bool, width: int, height: int,
|
|
enemy_can_grow: dict | None = None,
|
|
) -> MoveMap:
|
|
occupied = {(s["x"], s["y"]) for s in my_body}
|
|
for snake in other_snakes:
|
|
for seg in snake["body"]:
|
|
occupied.add((seg["x"], seg["y"]))
|
|
own_tail = (my_body[-1]["x"], my_body[-1]["y"])
|
|
own_tail_stacked = self._is_tail_stacked(my_body)
|
|
# C4: collect enemy tails that will vacate this turn (enemy won't grow, not stacked)
|
|
enemy_vacating_tails: set[tuple[int, int]] = set()
|
|
if not is_constrictor:
|
|
for snake in other_snakes:
|
|
if self._is_tail_stacked(snake["body"]):
|
|
continue
|
|
snake_id = snake.get("id")
|
|
can_grow: bool | None = None
|
|
if enemy_can_grow is not None and snake_id is not None:
|
|
can_grow = enemy_can_grow.get(snake_id)
|
|
if can_grow is None:
|
|
can_grow = self._enemy_can_grow_this_turn(snake, food_set)
|
|
if not can_grow:
|
|
enemy_vacating_tails.add((snake["body"][-1]["x"], snake["body"][-1]["y"]))
|
|
safe: MoveMap = {}
|
|
for move, (dx, dy) in self.DIRECTIONS.items():
|
|
pt = (my_head["x"] + dx, my_head["y"] + dy)
|
|
if not self._in_bounds(pt, width, height):
|
|
continue
|
|
ate = pt in food_set
|
|
can_step = self._can_step_on_own_tail(pt, own_tail, own_tail_stacked, ate, is_constrictor)
|
|
if not can_step and pt in enemy_vacating_tails:
|
|
can_step = True
|
|
if pt in occupied and not can_step:
|
|
continue
|
|
safe[move] = {"x": pt[0], "y": pt[1]}
|
|
return safe
|
|
|
|
def _simulation_blocked(
|
|
self, future_body: list, other_snakes: list, food_set: set,
|
|
is_constrictor: bool, enemy_can_grow: dict | None = None,
|
|
) -> set:
|
|
blocked = {(s["x"], s["y"]) for s in future_body}
|
|
if not is_constrictor and not self._is_tail_stacked(future_body):
|
|
tail = future_body[-1]
|
|
blocked.discard((tail["x"], tail["y"]))
|
|
for snake in other_snakes:
|
|
for seg in snake["body"]:
|
|
blocked.add((seg["x"], seg["y"]))
|
|
if is_constrictor:
|
|
continue
|
|
if self._is_tail_stacked(snake["body"]):
|
|
continue
|
|
# Check cache first, fall back to live check — if enemy will grow, tail won't vacate
|
|
snake_id = snake.get("id")
|
|
can_grow: bool | None = None
|
|
if enemy_can_grow is not None and snake_id is not None:
|
|
can_grow = enemy_can_grow.get(snake_id)
|
|
if can_grow is None:
|
|
can_grow = self._enemy_can_grow_this_turn(snake, food_set)
|
|
if can_grow:
|
|
continue # tail stays — enemy ate food this turn
|
|
blocked.discard((snake["body"][-1]["x"], snake["body"][-1]["y"]))
|
|
return blocked
|
|
|
|
def _build_enemy_attack_map(
|
|
self, my_snake: dict, other_snakes: list, food_set: set,
|
|
is_constrictor: bool, width: int, height: int,
|
|
enemy_can_grow: dict | None = None,
|
|
) -> dict:
|
|
occupied: set = {(s["x"], s["y"]) for s in my_snake["body"]}
|
|
for snake in other_snakes:
|
|
for seg in snake["body"]:
|
|
occupied.add((seg["x"], seg["y"]))
|
|
my_body_pts = {(s["x"], s["y"]) for s in my_snake["body"]}
|
|
my_tail = (my_snake["body"][-1]["x"], my_snake["body"][-1]["y"])
|
|
my_tail_stacked = self._is_tail_stacked(my_snake["body"])
|
|
attack_map: dict = {}
|
|
for enemy in other_snakes:
|
|
enemy_len = enemy.get("length", len(enemy["body"]))
|
|
enemy_tail = (enemy["body"][-1]["x"], enemy["body"][-1]["y"])
|
|
enemy_tail_stacked = self._is_tail_stacked(enemy["body"])
|
|
enemy_id = enemy.get("id")
|
|
# If the enemy can grow (adjacent to food), their tail won't vacate
|
|
en_can_grow: bool | None = None
|
|
if enemy_can_grow is not None and enemy_id is not None:
|
|
en_can_grow = enemy_can_grow.get(enemy_id)
|
|
if en_can_grow is None:
|
|
en_can_grow = self._enemy_can_grow_this_turn(enemy, food_set)
|
|
eh = enemy["head"]
|
|
for dx, dy in self.DIRECTIONS.values():
|
|
pt = (eh["x"] + dx, eh["y"] + dy)
|
|
if not self._in_bounds(pt, width, height):
|
|
continue
|
|
can_en_tail = (
|
|
not is_constrictor and pt == enemy_tail
|
|
and not enemy_tail_stacked and not en_can_grow
|
|
)
|
|
can_my_tail = not is_constrictor and pt == my_tail and not my_tail_stacked
|
|
if pt in occupied and not can_en_tail and not can_my_tail:
|
|
continue
|
|
if pt in my_body_pts and (is_constrictor or my_tail_stacked or pt != my_tail):
|
|
continue
|
|
prev = attack_map.get(pt)
|
|
if prev is None or enemy_len > prev:
|
|
attack_map[pt] = enemy_len
|
|
return attack_map
|
|
|
|
def _future_body(self, current_body: list, next_head: Coord, ate_food: bool, is_constrictor: bool) -> list:
|
|
nb = [next_head] + list(current_body)
|
|
if not is_constrictor and not ate_food:
|
|
nb.pop()
|
|
return nb
|
|
|
|
def _can_step_on_own_tail(
|
|
self, point: tuple, own_tail: tuple, stacked: bool, ate_food: bool, is_constrictor: bool,
|
|
) -> bool:
|
|
return not is_constrictor and not ate_food and not stacked and point == own_tail
|
|
|
|
def _is_tail_stacked(self, body: list) -> bool:
|
|
return len(body) >= 2 and body[-1]["x"] == body[-2]["x"] and body[-1]["y"] == body[-2]["y"]
|
|
|
|
def _enemy_can_grow_this_turn(self, snake:dict, food_set:set, all_occupied:set|None=None) -> bool:
|
|
"""E1: Estimate if enemy will eat food this turn (tail won't vacate).
|
|
- Hungry enemies (health < 40) always assumed to eat accessible adjacent food.
|
|
- Healthy enemies assumed to eat unless the food tile is blocked by a body segment.
|
|
- all_occupied: full set of body tiles; food under a body can't be eaten this turn.
|
|
"""
|
|
head = snake["head"]
|
|
health = snake.get("health", 100)
|
|
for dx, dy in self.DIRECTIONS.values():
|
|
pt = (head["x"] + dx, head["y"] + dy)
|
|
if pt not in food_set:
|
|
continue
|
|
# Food blocked by a body segment: snake can't step there, so tail will still vacate
|
|
if all_occupied is not None and pt in all_occupied:
|
|
continue
|
|
# Hungry snakes (health < 40) will eat regardless of other factors
|
|
if health < 40:
|
|
return True
|
|
# Healthy snake with accessible adjacent food: conservative assumption → will eat
|
|
return True
|
|
return False
|
|
|
|
def _hazard_damage_per_turn(self, game_data: GameBoard) -> int:
|
|
ruleset = game_data.get_ruleset() if hasattr(game_data, "get_ruleset") else {}
|
|
settings = (ruleset or {}).get("settings", {})
|
|
return int(settings.get("hazardDamagePerTurn", 15))
|
|
|
|
# ── Pathfinding primitives ────────────────────────────────────────────────────
|
|
|
|
def _flood_fill_count(self, start: tuple, blocked: set, width: int, height: int) -> int:
|
|
# E2: transposition cache — frozenset key deduplicates identical blocked sets across branches
|
|
cache_key = (start, frozenset(blocked))
|
|
cached = self._bfs_cache.get(cache_key)
|
|
if cached is not None:
|
|
return cached
|
|
queue = deque([start])
|
|
seen = {start}
|
|
while queue:
|
|
pt = queue.popleft()
|
|
for n in self._neighbors(pt):
|
|
if n not in seen and self._in_bounds(n, width, height) and n not in blocked:
|
|
seen.add(n)
|
|
queue.append(n)
|
|
result = len(seen)
|
|
self._bfs_cache[cache_key] = result
|
|
return result
|
|
|
|
def _open_neighbor_count(self, start: tuple, blocked: set, width: int, height: int) -> int:
|
|
return sum(
|
|
1 for n in self._neighbors(start)
|
|
if self._in_bounds(n, width, height) and n not in blocked
|
|
)
|
|
|
|
def _nearest_food_distance(
|
|
self, start: tuple, food_set: set, blocked: set, width: int, height: int,
|
|
) -> int | None:
|
|
dist, _ = self._nearest_food_info(start, food_set, blocked, width, height)
|
|
return dist
|
|
|
|
def _nearest_food_info(
|
|
self, start: tuple, food_set: set, blocked: set, width: int, height: int,
|
|
) -> tuple[int | None, tuple | None]:
|
|
"""Return (distance, food_coord) for nearest reachable food, or (None, None)."""
|
|
if not food_set:
|
|
return None, None
|
|
queue: deque[tuple[tuple, int]] = deque([(start, 0)])
|
|
seen = {start}
|
|
while queue:
|
|
pt, dist = queue.popleft()
|
|
if pt in food_set:
|
|
return dist, pt
|
|
for n in self._neighbors(pt):
|
|
if n in seen or not self._in_bounds(n, width, height):
|
|
continue
|
|
if n in blocked and n not in food_set:
|
|
continue
|
|
seen.add(n)
|
|
queue.append((n, dist + 1))
|
|
return None, None
|
|
|
|
def _path_distance(
|
|
self, start: tuple, goal: tuple, blocked: set, width: int, height: int,
|
|
) -> int | None:
|
|
queue: deque[tuple[tuple, int]] = deque([(start, 0)])
|
|
seen = {start}
|
|
while queue:
|
|
pt, dist = queue.popleft()
|
|
if pt == goal:
|
|
return dist
|
|
for n in self._neighbors(pt):
|
|
if n in seen or not self._in_bounds(n, width, height):
|
|
continue
|
|
if n in blocked and n != goal:
|
|
continue
|
|
seen.add(n)
|
|
queue.append((n, dist + 1))
|
|
return None
|
|
|
|
def _distance_map(self, start: tuple, blocked: set, width: int, height: int) -> dict:
|
|
queue: deque[tuple[tuple, int]] = deque([(start, 0)])
|
|
distances: dict = {start: 0}
|
|
while queue:
|
|
pt, dist = queue.popleft()
|
|
for n in self._neighbors(pt):
|
|
if n not in distances and self._in_bounds(n, width, height) and n not in blocked:
|
|
distances[n] = dist + 1
|
|
queue.append((n, dist + 1))
|
|
return distances
|
|
|
|
# ── Utilities ─────────────────────────────────────────────────────────────────
|
|
|
|
def _revisit_penalty(self, point: tuple) -> float:
|
|
penalty = 0.0
|
|
for i, old in enumerate(reversed(self.recent_heads), start=1):
|
|
if old == point:
|
|
penalty += max(0.0, 18.0 - i * 2.0)
|
|
return penalty
|
|
|
|
def _neighbors(self, point: tuple) -> Iterator[tuple]:
|
|
for dx, dy in self.DIRECTIONS.values():
|
|
yield (point[0] + dx, point[1] + dy)
|
|
|
|
def _manhattan(self, a: tuple, b: tuple) -> int:
|
|
return abs(a[0] - b[0]) + abs(a[1] - b[1])
|
|
|
|
def _in_bounds(self, point: tuple, width: int, height: int) -> bool:
|
|
return 0 <= point[0] < width and 0 <= point[1] < height
|
|
|
|
def _fallback_move(self, head: Coord, width: int, height: int) -> str:
|
|
for move, (dx, dy) in self.DIRECTIONS.items():
|
|
if self._in_bounds((head["x"] + dx, head["y"] + dy), width, height):
|
|
return move
|
|
return "up"
|