1595 lines
62 KiB
Python
1595 lines
62 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 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"
|