from collections import deque import math import random import time def play(gameState, memo={}): start_time = time.process_time() turn = gameState.currentTurn maxT = gameState.maxTurn INF = 10 ** 9 WIN = 100000 PLYLIM = 44 # Quy ước lưới 20x9 có vùng đệm 1 ô xung quanh -> STRIDE = 22, SIZE = 242 W = 20 H = 9 STRIDE = 22 SIZE = 242 OFFS = (23, 22, 1, 21, -21, -1, -22, -23) DIRN = {21: 1, 22: 2, 23: 3, 1: 4, -21: 5, -22: 6, -23: 7, -1: 8} BT = ((False, False, True), (True, False, False), (False, True, False)) PRED = (1, 2, 0) PREY = (2, 0, 1) LO = (1, 11) # Mở rộng bảng trọng số chạy đua lên 24 bước cho chiều dài map 20x9 RT = ( 0, 920, 520, 290, 170, 100, 65, 45, 32, 24, 18, 14, 10, 8, 6, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0 ) UNSTOP_RT = ( 0, 1650, 1050, 680, 440, 290, 195, 135, 95, 68, 48, 34, 24, 17, 12, 8, 5, 3, 1, 0, 0, 0, 0, 0, 0 ) PASS_ON = True PASS_SLEEP = 3.4 PASS_ROOT = 10 PASS_IN = 8 ELIM1 = 65 ELIM2 = 0 PASSM = (-1, 0, -1, -1, 0) # Xác định hướng xuất phát (trái hay phải khi xoay 180 độ) ally_list = list(gameState.ally) left_side = (sum(p.x for p in ally_list) <= 10 * max(1, len(ally_list))) restarted = ('tabs' not in memo) and turn > 1 if restarted: memo['pc'] = 3 tabs = memo.get('tabs') if tabs is None or memo.get('left_side') != left_side: memo['left_side'] = left_side # Đặt cứng 2 khối tường đen (7x3 ô) và dải 5 cờ mục tiêu của map 20x9 if left_side: WALL_SET = frozenset( y * STRIDE + x for x in range(13, 20) for y in (1, 2, 3, 7, 8, 9) ) GOAL0 = frozenset(y * STRIDE + 20 for y in range(3, 8)) GOAL1 = frozenset(y * STRIDE + 12 for y in range(3, 8)) else: WALL_SET = frozenset( y * STRIDE + x for x in range(2, 9) for y in (1, 2, 3, 7, 8, 9) ) GOAL0 = frozenset(y * STRIDE + 1 for y in range(3, 8)) GOAL1 = frozenset(y * STRIDE + 9 for y in range(3, 8)) GOAL = (GOAL0, GOAL1) cells = [ y * STRIDE + x for y in range(1, H + 1) for x in range(1, W + 1) if (y * STRIDE + x) not in WALL_SET ] valid_set = set(cells) nb0_set = {g + off for g in GOAL0 for off in OFFS if (g + off) in valid_set and (g + off) not in GOAL0} nb1_set = {g + off for g in GOAL1 for off in OFFS if (g + off) in valid_set and (g + off) not in GOAL1} NB = (tuple(nb0_set), tuple(nb1_set)) DEF_SQ = (GOAL0 | nb0_set, GOAL1 | nb1_set) # BFS tính khoảng cách ngắn nhất vòng qua tường tới dải 5 cờ (D0, D1) MAX_D = 40 D0 = [MAX_D] * SIZE dq = deque(GOAL0) for g in GOAL0: D0[g] = 0 while dq: u = dq.popleft() du = D0[u] + 1 for off in OFFS: v = u + off if v in valid_set and du < D0[v]: D0[v] = du dq.append(v) D1 = [MAX_D] * SIZE dq = deque(GOAL1) for g in GOAL1: D1[g] = 0 while dq: u = dq.popleft() du = D1[u] + 1 for off in OFFS: v = u + off if v in valid_set and du < D1[v]: D1[v] = du dq.append(v) # BFS tính khoảng cách săn đuổi né tường giữa mọi cặp ô hợp lệ (DT, MDT) DT = [[MAX_D] * SIZE for _ in range(SIZE)] MDT = [[MAX_D * 2] * SIZE for _ in range(SIZE)] for src in cells: row = DT[src] mrow = MDT[src] row[src] = 0 mrow[src] = 0 dq = deque([src]) while dq: u = dq.popleft() du = row[u] + 1 for off in OFFS: v = u + off if v in valid_set and du < row[v]: row[v] = du mrow[v] = du * 2 dq.append(v) max_d0 = max((D0[a] for a in cells if D0[a] < MAX_D), default=1) max_d1 = max((D1[a] for a in cells if D1[a] < MAX_D), default=1) ADV0 = [0] * SIZE ADV1 = [0] * SIZE CENTER = [0] * SIZE for a in cells: x = a % STRIDE y = a // STRIDE ADV0[a] = max(0, max_d0 - D0[a]) ADV1[a] = max(0, max_d1 - D1[a]) cx = abs(x - 10.5) cy = abs(y - 5.0) CENTER[a] = max(0, int(4 - max(cx / 2.0, cy))) MTAB0 = [() for _ in range(SIZE)] MTAB1 = [() for _ in range(SIZE)] for a in cells: m0 = [] m1 = [] for off in OFFS: q = a + off if q in valid_set: h_ix = a * SIZE + q fw0_b = (D0[a] - D0[q]) * 2 fw1_b = (D1[a] - D1[q]) * 2 m0.append((q, fw0_b, h_ix, 1 if q in nb0_set else 0)) m1.append((q, fw1_b, h_ix, 1 if q in nb1_set else 0)) m0.sort(key=lambda item: item[1], reverse=True) m1.sort(key=lambda item: item[1], reverse=True) MTAB0[a] = tuple(m0) MTAB1[a] = tuple(m1) MTAB = (tuple(MTAB0), tuple(MTAB1)) rz = random.Random(20260402) Z = tuple(tuple(rz.getrandbits(52) for _ in range(SIZE)) for _ in range(20)) ZS = rz.getrandbits(52) PASSK = rz.getrandbits(52) tabs = (WALL_SET, GOAL, NB, DEF_SQ, DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, Z, ZS, PASSK) memo['tabs'] = tabs WALL_SET, GOAL, NB, DEF_SQ, DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, Z, ZS, PASSK = tabs used = memo.get('used', 0.0) left = max(1, (maxT - turn) // 2 + 1) if turn <= 1: budget = 0.82 else: budget = min(0.81, max(0.04, (155.0 - used) / min(left, 150))) deadline = start_time + budget # Dựng bàn cờ 20x9: ngoài biên và ô tường đen đều là -1 board = [-1] * SIZE for yy in range(1, H + 1): base_y = yy * STRIDE for xx in range(1, W + 1): pos = base_y + xx if pos not in WALL_SET: board[pos] = 0 tp = [0] * 20 ps = [-1] * 20 TI = {'R': 0, 'P': 1, 'S': 2} cnt = [0, 0] for p in ally_list: c = p.pid tp[c] = TI[p.Type] pos = p.y * STRIDE + p.x ps[c] = pos board[pos] = c cnt[0] += 1 for p in gameState.opponent: c = 10 + p.pid tp[c] = TI[p.Type] pos = p.y * STRIDE + p.x ps[c] = pos board[pos] = c cnt[1] += 1 tt = memo.get('tt') if tt is None or len(tt) > 120000 or turn <= 1: tt = {} memo['tt'] = tt HIST_SIZE = SIZE * SIZE HIST = memo.get('hist') if HIST is None or len(HIST) != HIST_SIZE or turn <= 1: HIST = [0] * HIST_SIZE memo['hist'] = HIST else: for i in range(HIST_SIZE): if HIST[i]: HIST[i] >>= 1 KILLER = [None] * 64 nodes = [0] abort = [False] total = cnt[0] + cnt[1] if memo.get('prev_total') != total: memo['prev_total'] = total memo['capt_turn'] = turn memo['cfg'] = {} stag = (turn - memo.get('capt_turn', turn)) // 2 ahead = cnt[0] > cnt[1] behind = cnt[0] < cnt[1] K = 5 + min(8, turn // 25) if not behind and stag > 16: K += min(7, (stag - 16) // 6) if behind: HW = 3 elif stag > 16: HW = 11 else: HW = 6 if ahead and stag > 26: DP = (0, 220, 120, 55) else: DP = (0, 330, 175, 80) roles = {} e_types_alive = [0, 0, 0] e_near_home = [] e_near_away = [0, 0, 0] for c in range(11, 20): q = ps[c] if q >= 0: u = tp[c] e_types_alive[u] += 1 if D1[q] <= 4: e_near_home.append((D1[q], q, u)) if D0[q] <= 2: e_near_away[u] += 1 e_near_home.sort() def_assigned = set() for d_h, q_h, u_h in e_near_home: need_t = PRED[u_h] best_c = 0 best_d = 99 for c in range(1, 10): p = ps[c] if p >= 0 and tp[c] == need_t and c not in def_assigned: d_c = D1[p] if d_c < best_d: best_d = d_c best_c = c if best_c: roles[best_c] = 'DEFENDER' def_assigned.add(best_c) if not def_assigned: best_c = 0 best_d = 99 for c in range(1, 10): p = ps[c] if p >= 0 and e_types_alive[PREY[tp[c]]] > 0: d_c = D1[p] if d_c < best_d: best_d = d_c best_c = c if best_c and best_d <= 3: roles[best_c] = 'DEFENDER' def_assigned.add(best_c) runner_cands = [] for c in range(1, 10): p = ps[c] if p >= 0 and c not in def_assigned: t = tp[c] imm = 1 if e_types_alive[PRED[t]] == 0 else 0 brk = 1 if e_near_away[PREY[t]] > 0 else 0 runner_cands.append((D0[p] - 2 * imm - brk, -ADV0[p], c)) runner_cands.sort() for idx_r in range(min(2, len(runner_cands))): roles[runner_cands[idx_r][2]] = 'RUNNER' for c in range(1, 10): if ps[c] >= 0 and c not in roles: roles[c] = 'HUNTER' memo['roles'] = roles def wins_now(s): lo = LO[s] hi = lo + 8 for g in GOAL[s]: v0 = board[g] if v0 == 0: for off in OFFS: v = board[g + off] if lo <= v <= hi: return True else: t = tp[v0] for off in OFFS: v = board[g + off] if lo <= v <= hi and BT[tp[v]][t]: return True return False def gen(s, mode): res = [] lo = LO[s] elo = LO[1 - s] ehi = elo + 8 mtab = MTAB[s] gset = GOAL[s] egset = GOAL[1 - s] for c in range(lo, lo + 9): p = ps[c] if p < 0: continue t = tp[c] bt = BT[t] for q, fw_b, h_ix, is_nb in mtab[p]: v = board[q] if v == 0: if mode == 0: h = HIST[h_ix] res.append((fw_b + (h if h < 72 else 72), c, p, q, 0)) elif mode == 2 and is_nb: for off in OFFS: gq = q + off if gq in gset: vg = board[gq] if vg == 0 or (elo <= vg <= ehi and bt[tp[vg]]): res.append((820 + fw_b, c, p, q, 0)) break elif elo <= v <= ehi: ut = tp[v] if bt[ut]: res.append((1050 + fw_b + (90 if q in egset or D1[q] <= 2 else 0), c, p, q, v)) return res def evaluate_raw(s): A_p = [] A_t = [] B_p = [] B_t = [] cA0 = cA1 = cA2 = 0 cB0 = cB1 = cB2 = 0 for c in range(1, 10): p = ps[c] if p >= 0: t = tp[c] A_p.append(p) A_t.append(t) if t == 0: cA0 += 1 elif t == 1: cA1 += 1 else: cA2 += 1 for c in range(11, 20): p = ps[c] if p >= 0: t = tp[c] B_p.append(p) B_t.append(t) if t == 0: cB0 += 1 elif t == 1: cB1 += 1 else: cB2 += 1 na = len(A_p) nb = len(B_p) if na == 0: return -WIN + 100 if s == 0 else WIN - 100 if nb == 0: return WIN - 100 if s == 0 else -WIN + 100 cA = (cA0, cA1, cA2) cB = (cB0, cB1, cB2) v = 1050 * (na - nb) + 3200 * (na - nb) // (na + nb) for t in (0, 1, 2): pred = PRED[t] prey = PREY[t] ca = cA[t] cb = cB[t] if ca: if cB[pred] == 0: v += ca * (500 if cB[t] == 0 else 360) elif cB[pred] == 1 and cA[prey] > 0: v += ca * ELIM1 elif ELIM2 and cB[pred] == 2 and cA[prey] >= 2: v += ca * ELIM2 v += ca * (80 * cB[prey] if cB[prey] else -50) if cb: if cA[pred] == 0: v -= cb * (500 if cA[t] == 0 else 360) elif cA[pred] == 1 and cB[prey] > 0: v -= cb * ELIM1 elif ELIM2 and cA[pred] == 2 and cB[prey] >= 2: v -= cb * ELIM2 v -= cb * (80 * cA[prey] if cA[prey] else -50) far_d = 40 ha = [far_d] * na pa = [far_d] * na ma = [far_d * 2] * na inta = [99] * na hb = [far_d] * nb pb = [far_d] * nb mb = [far_d * 2] * nb intb = [99] * nb for i in range(na): p = A_p[i] t = A_t[i] d0p = D0[p] row = DT[p] mrow = MDT[p] bt = BT[t] for j in range(nb): q = B_p[j] u = B_t[j] d0q = D0[q] d1q = D1[q] if u == t: if d0q <= d0p and d0q < inta[i]: inta[i] = d0q if D1[p] <= d1q and D1[p] < intb[j]: intb[j] = D1[p] continue d = row[q] md = mrow[q] if bt[u]: if d < pa[i]: pa[i] = d if md < ma[i]: ma[i] = md if d < hb[j]: hb[j] = d if D1[p] <= d1q + 1 and D1[p] < intb[j]: intb[j] = D1[p] else: if d < ha[i]: ha[i] = d if d < pb[j]: pb[j] = d if md < mb[j]: mb[j] = md if d0q <= d0p + 1 and d0q < inta[i]: inta[i] = d0q adv0 = 0 thr0 = 0 dg0 = 0 hunt0 = 0 hang0 = 0 away_guard_b = [0, 0, 0] for j in range(nb): if D0[B_p[j]] <= 2: away_guard_b[B_t[j]] = 1 max_unstop = len(UNSTOP_RT) - 1 max_rt = len(RT) - 1 for i in range(na): p = A_p[i] t = A_t[i] ap = ADV0[p] if cB[PRED[t]] == 0: ap += ap >> 1 if away_guard_b[PREY[t]]: ap += max(0, 14 - D0[p]) * 3 adv0 += ap mp = pa[i] if mp < far_d: hunt0 += HW * max(0, 16 - mp) + max(0, 32 - ma[i]) else: hunt0 += CENTER[p] mh = ha[i] if mh <= 3: pt = PREY[t] row = DT[p] prot = False for k in range(na): if A_t[k] == pt and row[A_p[k]] <= 1: prot = True break if not prot: if mh <= 1: dg0 += DP[1] + (160 if s == 1 else 0) hang0 += 1 else: dg0 += DP[mh] elif mh <= 2: hunt0 += 25 d = D0[p] if inta[i] == 99: if d <= max_unstop: tv = UNSTOP_RT[d] if tv > thr0: thr0 = tv elif d <= max_rt: tv = RT[d] if mh <= 2 or inta[i] <= d: tv //= 3 if tv > thr0: thr0 = tv if hang0 >= 2: dg0 += 380 * (hang0 - 1) adv1 = 0 thr1 = 0 dg1 = 0 hunt1 = 0 hang1 = 0 home_guard_a = [0, 0, 0] for i in range(na): if D1[A_p[i]] <= 2: home_guard_a[A_t[i]] = 1 for j in range(nb): q = B_p[j] u = B_t[j] aq = ADV1[q] if cA[PRED[u]] == 0: aq += aq >> 1 if home_guard_a[PREY[u]]: aq += max(0, 14 - D1[q]) * 3 adv1 += aq mp = pb[j] if mp < far_d: hunt1 += HW * max(0, 16 - mp) + max(0, 32 - mb[j]) else: hunt1 += CENTER[q] mh = hb[j] if mh <= 3: pt = PREY[u] row = DT[q] prot = False for k in range(nb): if B_t[k] == pt and row[B_p[k]] <= 1: prot = True break if not prot: if mh <= 1: dg1 += DP[1] + (160 if s == 0 else 0) hang1 += 1 else: dg1 += DP[mh] elif mh <= 2: hunt1 += 25 d = D1[q] if intb[j] == 99: if d <= max_unstop: tv = UNSTOP_RT[d] if tv > thr1: thr1 = tv elif d <= max_rt: tv = RT[d] if mh <= 2 or intb[j] <= d: tv //= 3 if tv > thr1: thr1 = tv if hang1 >= 2: dg1 += 380 * (hang1 - 1) v += K * (adv0 - adv1) + (thr0 - thr1) - (dg0 - dg1) + (hunt0 - hunt1) has_useful_def = False for i in range(na): if D1[A_p[i]] <= 2 and cB[PREY[A_t[i]]] > 0: has_useful_def = True break near_cnt = 0 for j in range(nb): d = D1[B_p[j]] if d <= 2: v -= 520 * (3 - d) near_cnt += 1 if intb[j] == 99: v -= 450 * (3 - d) elif d == 3: v -= 110 if intb[j] == 99: v -= 220 elif d == 4: v -= 35 if near_cnt >= 2: v -= 420 * (near_cnt - 1) if near_cnt >= 1 and not has_useful_def: v -= 420 * near_cnt if has_useful_def: v += 135 + 105 * near_cnt return v if s == 0 else -v evc = {} def evaluate(s, h): r = evc.get(h) if r is None: r = evaluate_raw(s) evc[h] = r return r def qsearch(s, alpha, beta, ply, qd, h): nodes[0] += 1 if (nodes[0] & 63) == 0 and (time.process_time() > deadline or time.process_time() - start_time > 0.85): abort[0] = True if abort[0]: return 0 if wins_now(s): return WIN - ply o = 1 - s in_chk = wins_now(o) if in_chk: if qd >= 4: return -WIN + ply + 1 all_m = gen(s, 0) def_sq = DEF_SQ[o] evasions = [m for m in all_m if m[3] in def_sq] if not evasions: return -WIN + ply + 1 evasions.sort(reverse=True) best = -WIN + ply + 1 for m in evasions: c = m[1] p = m[2] q = m[3] cap = m[4] board[p] = 0 board[q] = c ps[c] = q h2 = h ^ Z[c][p] ^ Z[c][q] ^ ZS if cap: ps[cap] = -1 cnt[o] -= 1 h2 ^= Z[cap][q] still_w = wins_now(o) if not still_w: if cap and cnt[o] == 0: val = WIN - ply else: val = -qsearch(o, -beta, -alpha, ply + 1, qd + 1, h2) else: val = -WIN + ply + 1 if cap: cnt[o] += 1 ps[cap] = q board[q] = cap board[p] = c ps[c] = p if abort[0]: return 0 if val > best: best = val if val > alpha: alpha = val if alpha >= beta: break return best stand = evaluate(s, h) if stand >= beta: return stand if stand > alpha: alpha = stand if qd >= 6: return stand moves = gen(s, 2 if qd == 0 else 1) if not moves: return stand moves.sort(reverse=True) for m in moves: c = m[1] p = m[2] q = m[3] cap = m[4] board[p] = 0 board[q] = c ps[c] = q h2 = h ^ Z[c][p] ^ Z[c][q] ^ ZS if cap: ps[cap] = -1 cnt[o] -= 1 h2 ^= Z[cap][q] if cap and cnt[o] == 0: val = WIN - ply else: val = -qsearch(o, -beta, -alpha, ply + 1, qd + 1, h2) if cap: cnt[o] += 1 ps[cap] = q board[q] = cap board[p] = c ps[c] = p if abort[0]: return 0 if val > stand: stand = val if val > alpha: alpha = val if alpha >= beta: break return stand def search(s, depth, alpha, beta, ply, h, pp=0): nodes[0] += 1 if (nodes[0] & 63) == 0 and (time.process_time() > deadline or time.process_time() - start_time > 0.85): abort[0] = True if abort[0]: return 0 if wins_now(s): return WIN - ply o = 1 - s in_chk = wins_now(o) if depth <= 0: if in_chk and ply < PLYLIM: depth = 1 else: return qsearch(s, alpha, beta, ply, 0, h) a0 = alpha ttm = None hk = (h ^ PASSK) if pp else h e = tt.get(hk) if e is not None: ed, ef, ev, em = e if ev > WIN - 1000: ev -= ply elif ev < -WIN + 1000: ev += ply ttm = em if ed >= depth: if ef == 0: return ev if ef == 1: if ev >= beta: return ev elif ev <= alpha: return ev moves = gen(s, 0) if not moves: return -WIN + ply + 1 if in_chk else evaluate(s, h) if in_chk: def_sq = DEF_SQ[o] moves = [m for m in moves if m[3] in def_sq] if not moves: return -WIN + ply + 1 moves.sort(reverse=True) km = KILLER[ply] if ply < 64 else None if km is not None or ttm is not None: for i in range(len(moves)): m = moves[i] if ttm is not None and m[1] == ttm[0] and m[2] == ttm[1] and m[3] == ttm[2]: if i: moves.insert(0, moves.pop(i)) break if km is not None: for i in range(1, len(moves)): m = moves[i] if m[1] == km[0] and m[2] == km[1] and m[3] == km[2]: moves.insert(1 if ttm is not None else 0, moves.pop(i)) break best = -WIN + ply + 1 if in_chk else -INF bm = None idx = 0 nb_set = DEF_SQ[s] for m in moves: c = m[1] p = m[2] q = m[3] cap = m[4] board[p] = 0 board[q] = c ps[c] = q h2 = h ^ Z[c][p] ^ Z[c][q] ^ ZS if cap: ps[cap] = -1 cnt[o] -= 1 h2 ^= Z[cap][q] if in_chk and wins_now(o): val = -WIN + ply + 1 elif cap and cnt[o] == 0: val = WIN - ply else: if idx == 0: val = -search(o, depth - 1, -beta, -alpha, ply + 1, h2) else: red = 1 if (idx >= 4 and depth >= 3 and not cap and not in_chk and q not in nb_set) else 0 if idx >= 12 and depth >= 5 and red: red = 2 val = -search(o, depth - 1 - red, -alpha - 1, -alpha, ply + 1, h2) if val > alpha and not abort[0]: val = -search(o, depth - 1, -beta, -alpha, ply + 1, h2) if cap: cnt[o] += 1 ps[cap] = q board[q] = cap board[p] = c ps[c] = p if abort[0]: return 0 if val > best: best = val bm = (c, p, q) if val > alpha: alpha = val if alpha >= beta: if not cap: HIST[p * SIZE + q] += depth * depth if ply < 64: KILLER[ply] = bm break idx += 1 if PASS_ON and not pp and not in_chk and alpha < beta and ply < 40: val = -search(o, depth - 1, -beta - PASS_IN, -alpha - PASS_IN, ply + 1, h ^ ZS, 1) - PASS_IN if abort[0]: return 0 if val > best: best = val bm = None if val > alpha: alpha = val sv = best if sv > WIN - 1000: sv += ply elif sv < -WIN + 1000: sv -= ply if best <= a0: fl = 2 elif best >= beta: fl = 1 else: fl = 0 tt[hk] = (depth, fl, sv, bm) return best def decide(): root = gen(0, 0) if not root: return (0, 0) gset0 = GOAL[0] for m in root: if m[3] in gset0 or (m[4] and cnt[1] == 1): return (m[1], DIRN[m[3] - m[2]]) if wins_now(1): safe = [] for m in root: c0 = m[1] p0 = m[2] q0 = m[3] cap0 = m[4] board[p0] = 0 board[q0] = c0 ps[c0] = q0 if cap0: ps[cap0] = -1 cnt[1] -= 1 if not wins_now(1): safe.append(m) if cap0: cnt[1] += 1 ps[cap0] = q0 board[q0] = cap0 board[p0] = c0 ps[c0] = p0 if safe: root = safe if len(root) == 1: return (root[0][1], DIRN[root[0][3] - root[0][2]]) h0 = 0 for c in range(1, 20): if ps[c] >= 0: h0 ^= Z[c][ps[c]] seen = memo.setdefault('seen', {}) cfg = memo.setdefault('cfg', {}) pen_unit = 130 + 2 * min(turn, 200) cfg_unit = (45 + 4 * stag) * (0.25 if behind else 1.0) order = [] for m in root: c = m[1] p = m[2] q = m[3] cap = m[4] t = tp[c] pred_t = PRED[t] prey_t = PREY[t] role = roles.get(c, 'HUNTER') tb = m[0] * 10 if cap: tb += 5000 min_pred_p = 99 min_pred_q = 99 min_prey_q = 99 row_p = DT[p] row_q = DT[q] for ec in range(11, 20): ep = ps[ec] if ep >= 0 and ec != cap: et = tp[ec] if et == pred_t: if row_p[ep] < min_pred_p: min_pred_p = row_p[ep] if row_q[ep] < min_pred_q: min_pred_q = row_q[ep] elif et == prey_t: if row_q[ep] < min_prey_q: min_prey_q = row_q[ep] if min_pred_p == 1 and min_pred_q > 1: tb += 350 if min_pred_q == 1: tb -= 600 if role == 'RUNNER': tb += (D0[p] - D0[q]) * 45 + (ADV0[q] - ADV0[p]) * 20 elif role == 'DEFENDER': tb += (D1[p] - D1[q]) * 35 else: tb += max(0, 18 - min_prey_q) * 25 order.append((tb, m)) order.sort(reverse=True) order = [x[1] for x in order] pens = {} for m in order: c = m[1] p = m[2] q = m[3] cap = m[4] board[p] = 0 board[q] = c ps[c] = q if cap: ps[cap] = -1 key = tuple(ps) ck = tuple(ps[1:10]) if cap: ps[cap] = q board[q] = cap board[p] = c ps[c] = p pens[(c, p, q)] = min(750, int(pen_unit * seen.get(key, 0) + cfg_unit * cfg.get(ck, 0))) can_pass = ( PASS_ON and turn > 1 and memo.get('pc', 0) < 2 and (155.0 - used) > 15 and not wins_now(1) and not wins_now(0) ) best_move = order[0] for depth in range(1, 42): best_adj = -INF cur_best = None done = 0 vals = [] for m in order: if time.process_time() - start_time > 0.85: abort[0] = True break c = m[1] p = m[2] q = m[3] cap = m[4] pen = pens[(c, p, q)] araw = best_adj + pen if best_adj > -INF else -INF board[p] = 0 board[q] = c ps[c] = q h2 = h0 ^ Z[c][p] ^ Z[c][q] ^ ZS if cap: ps[cap] = -1 cnt[1] -= 1 h2 ^= Z[cap][q] val = -search(1, depth - 1, -INF, -araw if araw > -INF else INF, 1, h2) if cap: cnt[1] += 1 ps[cap] = q board[q] = cap board[p] = c ps[c] = p if abort[0]: break done += 1 adj = val - pen if val < WIN - 1000 else val vals.append((adj, m)) if adj > best_adj: best_adj = adj cur_best = m if can_pass and cur_best is not None and not abort[0]: araw = best_adj + PASS_ROOT if best_adj > -INF else -INF val = -search(1, depth - 1, -INF, -araw if araw > -INF else INF, 1, h0 ^ ZS, 1) if not abort[0]: adj = val - PASS_ROOT if val < WIN - 1000 else val vals.append((adj, PASSM)) if adj > best_adj: best_adj = adj cur_best = PASSM if cur_best is not None and (not abort[0] or done >= 1): best_move = cur_best if not abort[0]: vals.sort(key=lambda z: z[0], reverse=True) order = [t_item[1] for t_item in vals if t_item[1] is not PASSM] elif cur_best is not PASSM: order.remove(cur_best) order.insert(0, cur_best) if abort[0]: break if best_adj > WIN - 1000 or best_adj < -WIN + 1000: break if time.process_time() > deadline or time.process_time() - start_time > 0.85: break if best_move is PASSM: memo['pc'] = memo.get('pc', 0) + 1 memo['used'] = used + (time.process_time() - start_time) time.sleep(PASS_SLEEP) return (0, 0) memo['pc'] = 0 c = best_move[1] p = best_move[2] q = best_move[3] cap = best_move[4] board[p] = 0 board[q] = c ps[c] = q if cap: ps[cap] = -1 key = tuple(ps) seen[key] = seen.get(key, 0) + 1 ck = tuple(ps[1:10]) cfg[ck] = cfg.get(ck, 0) + 1 return (c, DIRN[q - p]) try: res = decide() except Exception: res = (0, 0) bestk = -INF for p in gameState.ally: for d in range(1, 9): dx, dy = ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0))[d - 1] nx = p.x + dx ny = p.y + dy if nx < 1 or nx > W or ny < 1 or ny > H or (ny * STRIDE + nx) in WALL_SET: continue ok = True for a in gameState.ally: if a.x == nx and a.y == ny: ok = False for e in gameState.opponent: if e.x == nx and e.y == ny: if not ((p.Type == 'R' and e.Type == 'S') or (p.Type == 'S' and e.Type == 'P') or (p.Type == 'P' and e.Type == 'R')): ok = False if ok and ADV0[ny * STRIDE + nx] > bestk: bestk = ADV0[ny * STRIDE + nx] res = (p.pid, d) memo['used'] = used + (time.process_time() - start_time) return res