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 W = gameState.width H = gameState.height goal_mode = gameState.goalMode walls_xy = frozenset((w.x, w.y) for w in gameState.walls) goals0_xy = frozenset((g.x, g.y) for g in gameState.goals) or frozenset([(W, H)]) goals1_xy = frozenset((g.x, g.y) for g in gameState.enemyGoals) or frozenset([(1, 1)]) # Bảng khắc chế: 0=R (Búa), 1=P (Bao), 2=S (Kéo) BT = ((False, False, True), (True, False, False), (False, True, False)) PRED = (1, 2, 0) PREY = (2, 0, 1) ELIM1 = 65 ELIM2 = 0 # Nếu trận trước bị reset giữa chừng thì xóa cache cũ if turn <= 1 and 'tabs' in memo: memo.clear() map_sig = (W, H, walls_xy, goals0_xy, goals1_xy, goal_mode) tabs = memo.get('tabs') # Khởi tạo bảng tra cứu bản đồ (chạy 1 lần ở lượt đầu hoặc khi đổi map) if tabs is None or memo.get('map_sig') != map_sig: memo['map_sig'] = map_sig memo['tt'] = {} memo['hist'] = None memo['seen'] = {} memo['cfg'] = {} STRIDE = W + 2 SIZE = (W + 2) * (H + 2) OFFS = (STRIDE + 1, STRIDE, 1, STRIDE - 1, -(STRIDE - 1), -1, -STRIDE, -(STRIDE + 1)) DIRN = { STRIDE - 1: 1, STRIDE: 2, STRIDE + 1: 3, 1: 4, -(STRIDE - 1): 5, -STRIDE: 6, -(STRIDE + 1): 7, -1: 8, } wall_set = frozenset( y * STRIDE + x for (x, y) in walls_xy if 1 <= x <= W and 1 <= y <= H ) 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) GOAL0 = frozenset(y * STRIDE + x for (x, y) in goals0_xy if (y * STRIDE + x) in valid_set) GOAL1 = frozenset(y * STRIDE + x for (x, y) in goals1_xy if (y * STRIDE + x) in valid_set) GOAL = (GOAL0, GOAL1) 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) MAX_D = W + H + 12 # BFS tính khoảng cách ngắn nhất né tường tới tập ô đích của ta (D0) và địch (D1) D0 = [MAX_D] * SIZE bfs_q = list(GOAL0) for g in GOAL0: D0[g] = 0 head = 0 while head < len(bfs_q): u = bfs_q[head] head += 1 du = D0[u] + 1 for off in OFFS: v = u + off if v in valid_set and du < D0[v]: D0[v] = du bfs_q.append(v) D1 = [MAX_D] * SIZE bfs_q = list(GOAL1) for g in GOAL1: D1[g] = 0 head = 0 while head < len(bfs_q): u = bfs_q[head] head += 1 du = D1[u] + 1 for off in OFFS: v = u + off if v in valid_set and du < D1[v]: D1[v] = du bfs_q.append(v) # BFS tính khoảng cách thực tế giữa mọi cặp ô hợp lệ để săn đuổi vòng qua vật cản 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 bfs_q = [src] head = 0 while head < len(bfs_q): u = bfs_q[head] head += 1 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 bfs_q.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 mid_x = (W + 1) * 0.5 mid_y = (H + 1) * 0.5 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 - mid_x) / max(1.0, W / 9.0) cy = abs(y - mid_y) / max(1.0, H / 9.0) CENTER[a] = max(0, int(4 - max(cx, cy))) # Bảng nước đi hợp lệ sắp xếp sẵn theo độ giảm khoảng cách tới đích 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)) # Bảng điểm thưởng khoảng cách tới đích (tự co giãn theo kích thước map) RT = tuple([0] + [int(950 * (0.60 ** (d - 1))) for d in range(1, MAX_D + 1)]) UNSTOP_RT = tuple([0] + [int(1750 * (0.64 ** (d - 1))) for d in range(1, MAX_D + 1)]) rz = random.Random(20260402) Z = tuple(tuple(rz.getrandbits(52) for _ in range(SIZE)) for _ in range(48)) ZS = rz.getrandbits(52) tabs = ( STRIDE, SIZE, MAX_D, OFFS, DIRN, wall_set, GOAL, NB, DEF_SQ, DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, RT, UNSTOP_RT, Z, ZS ) memo['tabs'] = tabs ( STRIDE, SIZE, MAX_D, OFFS, DIRN, wall_set, GOAL, NB, DEF_SQ, DT, MDT, ADV0, ADV1, D0, D1, CENTER, MTAB, RT, UNSTOP_RT, Z, ZS ) = tabs # Quản lý ngân sách CPU: tổng 180s/ván, tối đa 1s/nước (chốt ở 0.82s để an toàn) used = memo.get('used', 0.0) left = max(1, (maxT - turn) // 2 + 1) if turn <= 1: budget = 0.82 else: budget = min(0.82, max(0.04, (160.0 - used) / min(left, 150))) deadline = start_time + budget # Dựng bàn cờ 1 chiều: ngoài biên và ô tường đen mang giá trị -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 # Đánh chỉ số động cho quân hai bên (hỗ trợ map có số quân khác 9) ally_list = list(gameState.ally) opp_list = list(gameState.opponent) na_init = len(ally_list) nb_init = len(opp_list) ALLY_LO = 1 ALLY_HI = na_init OPP_LO = na_init + 2 OPP_HI = OPP_LO + nb_init - 1 LO = (ALLY_LO, OPP_LO) HI = (ALLY_HI, OPP_HI) slot_cap = max(48, OPP_HI + 2) if len(Z) < slot_cap: rz = random.Random(20260402) Z = tuple(tuple(rz.getrandbits(52) for _ in range(SIZE)) for _ in range(slot_cap)) tp = [0] * slot_cap ps = [-1] * slot_cap pid_of = [0] * slot_cap TI = {'R': 0, 'P': 1, 'S': 2} cnt = [0, 0] for idx_a, p in enumerate(ally_list): c = ALLY_LO + idx_a pid_of[c] = p.pid tp[c] = TI[p.Type] pos = p.y * STRIDE + p.x ps[c] = pos board[pos] = c cnt[0] += 1 for idx_b, p in enumerate(opp_list): c = OPP_LO + idx_b pid_of[c] = 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: tt = {} memo['tt'] = tt hist_len = SIZE * SIZE HIST = memo.get('hist') if HIST is None or len(HIST) != hist_len: HIST = [0] * hist_len memo['hist'] = HIST else: for i in range(hist_len): 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) # Phân vai chiến thuật: DEFENDER (chặn đích nhà), RUNNER (đột phá), HUNTER (săn quân) roles = {} e_types_alive = [0, 0, 0] e_near_home = [] e_near_away = [0, 0, 0] for c in range(OPP_LO, OPP_HI + 1): 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 = 999 for c in range(ALLY_LO, ALLY_HI + 1): 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 = 999 for c in range(ALLY_LO, ALLY_HI + 1): 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(ALLY_LO, ALLY_HI + 1): 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() num_runners = max(2, len(GOAL[0])) if goal_mode == 1 else 2 for idx_r in range(min(num_runners, len(runner_cands))): roles[runner_cands[idx_r][2]] = 'RUNNER' for c in range(ALLY_LO, ALLY_HI + 1): if ps[c] >= 0 and c not in roles: roles[c] = 'HUNTER' # Kiểm tra phe s có thể chạm đích thắng ngay trong 1 nước đi không def wins_now(s): lo = LO[s] hi = HI[s] gset = GOAL[s] if goal_mode == 0: for g in gset: v0 = board[g] if lo <= v0 <= hi: return True 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 else: missing = [g for g in gset if not (lo <= board[g] <= hi)] if not missing: return True if len(missing) > 1: return False g = missing[0] v0 = board[g] for off in OFFS: src = g + off v = board[src] if lo <= v <= hi and src not in gset: if v0 == 0 or BT[tp[v]][tp[v0]]: return True return False # Sinh nước đi hợp lệ: mode=0 (tất cả), mode=1 (chỉ ăn quân), mode=2 (ăn quân + áp sát đích) def gen(s, mode): res = [] lo = LO[s] hi = HI[s] elo = LO[1 - s] ehi = HI[1 - s] mtab = MTAB[s] gset = GOAL[s] egset = GOAL[1 - s] for c in range(lo, hi + 1): p = ps[c] if p < 0: continue t = tp[c] bt = BT[t] on_goal = (goal_mode == 1 and p in gset) for q, fw_b, h_ix, is_nb in mtab[p]: v = board[q] if v == 0: if mode == 0: h = HIST[h_ix] pen_leave = -35 if (on_goal and q not in gset) else 0 res.append((fw_b + pen_leave + (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: if bt[tp[v]]: bonus = 90 if (q in egset or D1[q] <= 2) else 0 res.append((1050 + fw_b + bonus, c, p, q, v)) return res # Hàm lượng giá thế cờ tĩnh từ góc nhìn phe s def evaluate_raw(s): A_p = [] A_t = [] B_p = [] B_t = [] cA0 = cA1 = cA2 = 0 cB0 = cB1 = cB2 = 0 for c in range(ALLY_LO, ALLY_HI + 1): 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(OPP_LO, OPP_HI + 1): 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) # Hơn quân và lợi thế tuyệt đối khi địch mất sạch loại quân khắc chế 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) # Điểm chiếm đóng đồng thời khi bản đồ bật goalMode == 1 if goal_mode == 1: occ0 = 0 for g in GOAL[0]: if ALLY_LO <= board[g] <= ALLY_HI: occ0 += 1 occ1 = 0 for g in GOAL[1]: if OPP_LO <= board[g] <= OPP_HI: occ1 += 1 if occ0 == len(GOAL[0]): return WIN - 50 if s == 0 else -WIN + 50 if occ1 == len(GOAL[1]): return -WIN + 50 if s == 0 else WIN - 50 v += 900 * (occ0 - occ1) ha = [MAX_D] * na pa = [MAX_D] * na ma = [MAX_D * 2] * na inta = [999] * na hb = [MAX_D] * nb pb = [MAX_D] * nb mb = [MAX_D * 2] * nb intb = [999] * 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 hunt_range = max(10, (W + H) // 2 + 2) 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, hunt_range - D0[p]) * 3 adv0 += ap mp = pa[i] if mp < MAX_D: hunt0 += HW * max(0, hunt_range - mp) + max(0, hunt_range * 2 - 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] == 999: 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, hunt_range - D1[q]) * 3 adv1 += aq mp = pb[j] if mp < MAX_D: hunt1 += HW * max(0, hunt_range - mp) + max(0, hunt_range * 2 - 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] == 999: 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) # Phòng thủ vùng cờ nhà 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] == 999: v -= 450 * (3 - d) elif d == 3: v -= 110 if intb[j] == 999: 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 # Tìm kiếm tĩnh (Quiescence Search) giải quyết chuỗi ăn quân và đe dọa chạm đích 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.84): 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 # Alpha-Beta PVS kết hợp bảng băm TT, Killer Heuristic và Late Move Reduction def search(s, depth, alpha, beta, ply, h): nodes[0] += 1 if (nodes[0] & 63) == 0 and (time.process_time() > deadline or time.process_time() - start_time > 0.84): 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 e = tt.get(h) 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 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[h] = (depth, fl, sv, bm) return best # Chọn nước đi tối ưu bằng Iterative Deepening tại nút gốc def decide(): root = gen(0, 0) if not root: return (0, 0) # Kiểm tra nước thắng ngay lập tức gset0 = GOAL[0] for m in root: c0 = m[1] p0 = m[2] q0 = m[3] cap0 = m[4] if cap0 and cnt[1] == 1: return (pid_of[c0], DIRN[q0 - p0]) if q0 in gset0: if goal_mode == 0: return (pid_of[c0], DIRN[q0 - p0]) elif all((g == q0 or (ALLY_LO <= board[g] <= ALLY_HI and g != p0)) for g in gset0): return (pid_of[c0], DIRN[q0 - p0]) # Nếu địch đang dọa chạm đích ở lượt kế, lọc các nước phòng thủ bắt buộc 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 (pid_of[root[0][1]], DIRN[root[0][3] - root[0][2]]) h0 = 0 for c in range(1, OPP_HI + 1): 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) hunt_range = max(10, (W + H) // 2 + 2) 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 = 999 min_pred_q = 999 min_prey_q = 999 row_p = DT[p] row_q = DT[q] for ec in range(OPP_LO, OPP_HI + 1): 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, hunt_range - min_prey_q) * 25 order.append((tb, m)) order.sort(reverse=True) order = [x[1] for x in order] # Phạt nhẹ các thế cờ lặp lại để tránh đi quẩn quanh 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[ALLY_LO:ALLY_HI + 1]) 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))) 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.84: 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 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] else: 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.84: break 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[ALLY_LO:ALLY_HI + 1]) cfg[ck] = cfg.get(ck, 0) + 1 return (pid_of[c], DIRN[q - p]) try: res = decide() except Exception: # Nhánh dự phòng an toàn nếu gặp sự cố bất ngờ res = (0, 0) bestk = -INF dirs = ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0)) for p in ally_list: for d in range(1, 9): dx, dy = dirs[d - 1] nx = p.x + dx ny = p.y + dy if nx < 1 or nx > W or ny < 1 or ny > H or (nx, ny) in walls_xy: continue ok = True for a in ally_list: if a.x == nx and a.y == ny: ok = False for e in opp_list: 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