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 server.dataset.RLBootstrapDataset import RLBootstrapDataset from snakes.TemplateSnake import TemplateSnake from server.GameBoard import GameBoard class ApexBattleSnake(TemplateSnake): """ ApexBattleSnake v1.0.0 Built on UltimateBattleSnake v4.5.0. All prior improvements (v3/v4/v4.5) are retained. New improvements: A1: Iterative deepening minimax — tries depth 1,2,...,N within time budget; keeps deepest fully-completed result instead of a fixed depth=2 call. A2: Hazard-aware starvation check — Dijkstra with per-tile hazard cost replaces BFS food distance when hazards are present and health < 55. Correctly models health depletion through hazard corridors when choosing whether to seek food. A3: Phase-adaptive scoring weights — board occupancy drives a game_phase scalar [0,1]. Territory weight scales up late-game; food bias scales down. Stored as self._game_phase. A4: Rich GameplayDatabase thinking data — add_to_history records game_phase, food_count, enemy lengths/healths, minimax_depth_reached, score_gap, safe_moves_count per turn. A5: Dynamic duel aggression — auto-adjusts head_pressure/distance_safety multipliers based on (my_len - enemy_len) delta on top of the configured duel style preset. A6: Constrictor endgame encirclement — when enemy is sealed in a region <= our body length, apply a strong encirclement bonus to close out the win efficiently. A7: Bounded BFS transposition cache — caps per-turn cache at 4096 entries to prevent memory growth in long games with many unique blocked-set combinations. """ VERSION = "1.0.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 = "ApexBattleSnake" 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 self._game_phase: float = 0.0 # A3: 0.0=early, 1.0=late; set each turn # A7: per-turn transposition cache with bounded size self._bfs_cache: dict[tuple, int] = {} self._bfs_cache_turn: int = -1 self._bfs_cache_max: int = 4096 # Config self._planning_depth = max(1, min(6, env_int("BATTLE_FUTURE_PLANNING_DEPTH", 3))) 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", 60)) # RL bootstrap dataset recorder self.rl_bootstrap = RLBootstrapDataset() def __getstate__(self): state = super().__getstate__() state['_game_phase'] = 0.0 # A3: per-turn scalar, recomputed in choose_move 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() 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 # A7: 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} 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"]) total_body_cells = len(my_body) + sum(len(s["body"]) for s in other_snakes) total_occupancy = total_body_cells / board_area # A3: game phase scalar for adaptive weight scaling self._game_phase = min(1.0, total_occupancy / 0.5) 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 } 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] self._enemy_dmaps = [ self._distance_map(eh, self._base_blocked, width, height) for eh in self._enemy_heads ] 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"]}, "game_phase": round(self._game_phase, 3), "is_snail": is_snail, "is_constrictor": is_constrictor, }) self.rl_bootstrap.record_sample(game_data, fallback, safe_moves, "no_safe_moves") return fallback mm_depth_reached = 0 # A4: will be populated by duel mode 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, mm_depth_reached = 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) # A4: rich thinking data for GameplayDatabase sorted_scores = sorted(scores.values(), reverse=True) if scores else [] best_score = sorted_scores[0] if sorted_scores else 0.0 score_gap = (sorted_scores[0] - sorted_scores[1]) if len(sorted_scores) >= 2 else 0.0 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), # A4 extended fields "game_phase": round(self._game_phase, 3), "food_count": len(foods), "enemy_lengths": [e.get("length", len(e.get("body", []))) for e in other_snakes], "enemy_healths": [e.get("health", 0) for e in other_snakes], "hazard_damage": hazard_damage, "is_snail": is_snail, "is_constrictor": is_constrictor, "safe_moves_count": len(safe_moves), "best_score": round(best_score, 3), "score_gap": round(score_gap, 3), "minimax_depth_reached": mm_depth_reached, "board_size": f"{width}x{height}", }) 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] = {} # A3: phase-adaptive territory weight for multi-snake territory_w = 0.35 + self._game_phase * 0.10 # [0.35, 0.45] 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) * territory_w 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, {} 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] 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], int]: 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 encase_target = max(8, enemy_len * 2) dw = dict(self._duel_weights(self._get_duel_style())) # A5: auto-adjust duel weights based on length delta length_delta = my_len - enemy_len if length_delta >= 3: dw["head_pressure"] = min(2.0, dw["head_pressure"] * 1.4) dw["distance_safety"] = max(0.4, dw["distance_safety"] * 0.65) elif length_delta <= -3: dw["head_pressure"] = max(0.3, dw["head_pressure"] * 0.55) dw["distance_safety"] = min(2.5, dw["distance_safety"] * 1.6) # A3: phase-aware territory and food weights for duel territory_w = 0.45 + self._game_phase * 0.15 # [0.45, 0.60] # Food priority scales down late game when space control matters more food_phase_adj = 0.15 - self._game_phase * 0.35 # +0.15 early, -0.20 late scores: dict[str, float] = {} safety: dict[str, dict] = {} mm_depth_reached = 0 # A4: track deepest minimax completed 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 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 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"] # Food bias: base duel weight + A3 phase adjustment nearest_food = info.get("nearest_food") total_food_adj = (dw["food_bias"] - 1.0) + food_phase_adj if nearest_food is not None and total_food_adj != 0.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 * total_food_adj sc += self._territory_fast(point, blocked, width, height, deadline) * territory_w scores[move] = round(sc, 5) safety[move] = info if not scores: return self._deterministic_fallback(safe_moves, width, height), {}, 0 best_move = self._select_best(scores, safety, safe_moves, list(scores)) # A1: iterative deepening minimax (was fixed depth=2) 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 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, depth_done = self._minimax_sim_id( 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, max_depth=self._planning_depth, alpha=-1e9, beta=1e9, deadline=deadline, previous_hazard_set=previous_hazard_set, ) mm_scores[m] = scores[m] + mm_val * 0.10 mm_depth_reached = max(mm_depth_reached, depth_done) 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()}, "mm_depth": mm_depth_reached, }) # F2: survival tree post-processing for duel 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, mm_depth_reached # ── 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"]) 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 # A6: endgame encirclement — enemy sealed in region <= our body length if 0 < enemy_best_space <= len(my_body): encircle_bonus = (len(my_body) - enemy_best_space) * 140.0 sc += encircle_bonus sc += info["reachable_space"] * 3.0 if enemy_total_opts == 0: sc += 500.0 # enemy has no moves — complete the trap scores[move] = round(sc, 5) safety[move] = info if not scores: return self._deterministic_fallback(safe_moves, width, height), {} 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 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) if is_constrictor: required_space = len(future_body) + max(3, len(future_body) // 6) else: required_space = len(future_body) 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) 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, ) art_penalty = self._articulation_penalty(point, blocked, width, height, required_space) 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 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_len_here = enemy_attack_map.get(point) losing_h2h = enemy_len_here is not None and enemy_len_here >= my_len 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) 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) ) 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) 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) hazard_stack = hazard_count.get(point, 1) if point in hazard_set else 1 health_after = 100 if ate_food else my_health - 1 if point in hazard_set and not ate_food and point in previous_hazard_set: health_after -= hazard_damage * hazard_stack 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 preserve_space = total_occupancy >= 0.34 and my_health > 35 if nearest_food is not None: contest_multiplier = 0.55 if food_contested else 1.0 # A2: hazard-aware starvation check — use Dijkstra cost when hazards present if hazard_damage > 0 and my_health < 55 and hazard_set: food_cost = self._food_health_cost( point, food_set, blocked, hazard_set, hazard_count, hazard_damage, width, height, ) if food_cost is not None and food_cost >= health_after: score -= 900.0 + (55 - my_health) * 22.0 elif food_cost is None and my_health < 30: score -= 1100.0 elif my_health < 40 and nearest_food >= health_after: score -= 800.0 + (40 - my_health) * 20.0 score += ((30.0 + 80.0 * hunger) / (nearest_food + 1)) * contest_multiplier 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: 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 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 ) if adjacent_hazard_stack > 0: score -= adjacent_hazard_stack * 6.0 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 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, "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 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 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: 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: 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) 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)) # ── A1: Iterative deepening minimax ────────────────────────────────────────── def _minimax_sim_id( 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, max_depth: int, alpha: float, beta: float, deadline: float | None, previous_hazard_set: set | None = None, ) -> tuple[float, int]: """A1: Iterative deepening minimax. Returns (score, depth_completed). Tries depth 1, 2, ..., max_depth. Only updates result after a depth fully completes without hitting the deadline. Returns the deepest completed result. """ result = self._minimax_eval(my_body, enemy_body, width, height) depth_reached = 0 for depth in range(1, max_depth + 1): if self._time_exceeded(deadline): break if self._remaining_ms(deadline) < 5: break candidate = self._minimax_sim( my_body, enemy_body, food_set, hazard_set, my_health, enemy_health, hazard_damage, hazard_count, width, height, depth, alpha, beta, deadline, previous_hazard_set, ) # Only accept result if we completed this depth before the deadline if not self._time_exceeded(deadline): result = candidate depth_reached = depth else: break # partial result — discard, stop searching deeper return result, depth_reached # ── Simultaneous minimax ────────────────────────────────────────────────────── 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: 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] 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 my_moves = self._sort_minimax_moves(my_moves, food_set, width, height) en_moves = self._sort_minimax_moves(en_moves, food_set, width, height) best = -1e9 for my_pt in my_moves: if self._time_exceeded(deadline): break worst = 1e9 for en_pt in en_moves: if my_pt == en_pt: 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 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, ) worst = min(worst, val) if worst <= alpha: break best = max(best, worst) alpha = max(alpha, best) if alpha >= beta: break return best def _sort_minimax_moves(self, moves: list, food_set: set, width: int, height: int) -> list: 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 ─────────────────────────────────────────────────── 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, ) return raw * 0.15 _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 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 viable = [(sc, fb) for sc, fb in scored if sc > self._TREE_DEATH_THRESHOLD] if not viable: 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) if is_constrictor: required = len(my_body) + max(3, len(my_body) // 6) else: required = len(my_body) 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 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) 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 ────────────────────────────────────────────── def _articulation_penalty( self, point: tuple, blocked: set, width: int, height: int, required_space: int, ) -> float: 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 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 min_size = min(partition_sizes) if min_size < required_space: return 1500.0 elif min_size < required_space * 2: return 400.0 else: return 85.0 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 # ── A2: Hazard-aware food cost (Dijkstra) ───────────────────────────────────── def _food_health_cost( self, start: tuple[int, int], food_set: set[tuple[int, int]], blocked: set[tuple[int, int]], hazard_set: set[tuple[int, int]], hazard_count: dict[tuple[int, int], int], hazard_damage: int, width: int, height: int, ) -> int | None: """A2: Dijkstra from start to nearest reachable food accounting for hazard health cost. Cost per step = 1 (non-hazard) or 1 + hazard_damage * stack (in hazard). Returns total health cost to reach the nearest food, or None if unreachable. The caller compares this against current health_after to determine starvation risk. """ if not food_set: return None heap: list[tuple[int, tuple[int, int]]] = [(0, start)] best: dict[tuple[int, int], int] = {start: 0} while heap: cost, pt = heapq.heappop(heap) if cost > best.get(pt, 10**9): continue if pt in food_set: return cost for n in self._neighbors(pt): if not self._in_bounds(n, width, height): continue # Food tiles are always steppable even if in blocked (matches _nearest_food_info) if n in blocked and n not in food_set: 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 None # ── Hazard multi-step check ─────────────────────────────────────────────────── 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: if hazard_damage <= 0: return False 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 # ── 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 ───────────────────────────────────────────────────── 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: 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) 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 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 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") 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: 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 if all_occupied is not None and pt in all_occupied: continue if health < 40: return True 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 + A7: per-turn transposition cache with bounded size 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) # A7: only write to cache when below the size cap if len(self._bfs_cache) < self._bfs_cache_max: 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_info( self, start: tuple, food_set: set, blocked: set, width: int, height: int, ) -> tuple[int | None, tuple | 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"