| 1 | """Deterministic standard-Gomoku computer: exact-five windows, broken threats, |
| 2 | forced replies and a bounded tactical search. No network or learned weights. |
| 3 | BOARD replaces the position; both protocol colours are relative to this brain. |
| 4 | """ |
| 5 | import sys |
| 6 | import time |
| 7 | |
| 8 | N, board, me = 15, {}, 1 |
| 9 | D = ((1, 0), (0, 1), (1, 1), (1, -1)) |
| 10 | WIN = 10_000_000 |
| 11 | turn_ms = 1000 |
| 12 | |
| 13 | |
| 14 | def candidates(): |
| 15 | if not board: |
| 16 | return [(N // 2, N // 2)] |
| 17 | near = {(x + a, y + b) for x, y in board |
| 18 | for a in range(-2, 3) for b in range(-2, 3)} |
| 19 | return sorted(p for p in near if 0 <= p[0] < N and 0 <= p[1] < N and p not in board) |
| 20 | |
| 21 | |
| 22 | def pattern(p, colour): |
| 23 | """Score exact-five windows through a hypothetical stone, including gaps. |
| 24 | |
| 25 | A window with our stone just beyond it cannot be an exact five. Distinct |
| 26 | winning points matter: two windows sharing one gap are only one threat. |
| 27 | """ |
| 28 | x, y = p |
| 29 | wins, threes, twos = set(), set(), set() |
| 30 | for dx, dy in D: |
| 31 | cells = [(x + i * dx, y + i * dy) for i in range(-5, 6)] |
| 32 | row = [colour if i == 5 else board.get(q, 0) if 0 <= q[0] < N and 0 <= q[1] < N else -1 |
| 33 | for i, q in enumerate(cells)] |
| 34 | for start in range(1, 6): |
| 35 | if row[start - 1] == colour or row[start + 5] == colour: |
| 36 | continue |
| 37 | line = row[start:start + 5] |
| 38 | if any(v not in (0, colour) for v in line): |
| 39 | continue |
| 40 | empty = tuple(cells[j] for j in range(start, start + 5) if row[j] == 0) |
| 41 | if not empty: |
| 42 | return WIN |
| 43 | if len(empty) == 1: |
| 44 | wins.add(empty[0]) |
| 45 | elif len(empty) == 2: |
| 46 | threes.add(empty) |
| 47 | elif len(empty) == 3: |
| 48 | twos.add(empty) |
| 49 | return ((900_000 if len(wins) >= 2 else 0) + 90_000 * len(wins) |
| 50 | + 2_400 * len(threes) + 90 * len(twos)) |
| 51 | |
| 52 | |
| 53 | def centre(p): |
| 54 | return -abs(p[0] - N // 2) - abs(p[1] - N // 2) |
| 55 | |
| 56 | |
| 57 | def ranked(colour): |
| 58 | rows = [(p, pattern(p, colour), pattern(p, 3 - colour)) for p in candidates()] |
| 59 | return sorted(rows, key=lambda r: (r[1] * 1.05 + r[2], centre(r[0]), -r[0][1], -r[0][0]), reverse=True) |
| 60 | |
| 61 | |
| 62 | class Budget(Exception): |
| 63 | pass |
| 64 | |
| 65 | |
| 66 | def move(): |
| 67 | if not board: |
| 68 | return N // 2, N // 2 |
| 69 | deadline = time.monotonic() + min(0.65, max(0.015, turn_ms / 1000 * 0.65)) |
| 70 | root = ranked(me) |
| 71 | for p, attack, _ in root: |
| 72 | if attack == WIN: |
| 73 | return p |
| 74 | blocks = [p for p, _, defence in root if defence == WIN] |
| 75 | if blocks: |
| 76 | return blocks[0] |
| 77 | for p, attack, _ in root: |
| 78 | if attack >= 900_000: |
| 79 | return p |
| 80 | |
| 81 | def search(colour, depth, alpha, beta, extensions=3): |
| 82 | if time.monotonic() >= deadline: |
| 83 | raise Budget |
| 84 | rows = ranked(colour) |
| 85 | if not rows: |
| 86 | return 0 |
| 87 | if any(a == WIN for _, a, _ in rows): |
| 88 | return WIN + depth |
| 89 | forced = [r for r in rows if r[2] == WIN] |
| 90 | if len(forced) > 1: |
| 91 | return -WIN - depth |
| 92 | if not depth and (not forced or not extensions): |
| 93 | own = sorted((r[1] for r in rows), reverse=True) |
| 94 | other = sorted((r[2] for r in rows), reverse=True) |
| 95 | return own[0] * 1.1 + sum(own[1:3]) * 0.15 - other[0] - sum(other[1:3]) * 0.15 |
| 96 | best = -2 * WIN |
| 97 | for p, _, _ in forced or rows[:4]: |
| 98 | board[p] = colour |
| 99 | try: |
| 100 | value = -search(3 - colour, max(0, depth - 1), -beta, -alpha, extensions - int(depth == 0)) |
| 101 | finally: |
| 102 | del board[p] |
| 103 | best = max(best, value) |
| 104 | alpha = max(alpha, value) |
| 105 | if alpha >= beta: |
| 106 | break |
| 107 | return best |
| 108 | |
| 109 | best, best_value = root[0][0], -3 * WIN |
| 110 | |
| 111 | for p, attack, defence in root[:8]: |
| 112 | board[p] = me |
| 113 | try: |
| 114 | value = -search(3 - me, 2, -2 * WIN, -best_value) |
| 115 | value += (attack * 1.05 + defence) * 0.01 |
| 116 | except Budget: |
| 117 | break |
| 118 | finally: |
| 119 | del board[p] |
| 120 | if value > best_value: |
| 121 | best, best_value = p, value |
| 122 | return best |
| 123 | |
| 124 | |
| 125 | def play(): |
| 126 | x, y = move() |
| 127 | board[(x, y)] = me |
| 128 | print(f'{x},{y}', flush=True) |
| 129 | |
| 130 | |
| 131 | def main(): |
| 132 | global N, turn_ms |
| 133 | for raw in sys.stdin: |
| 134 | cmd, _, arg = raw.strip().partition(' ') |
| 135 | cmd = cmd.upper() |
| 136 | if cmd == 'START': |
| 137 | N = int(arg) |
| 138 | board.clear() |
| 139 | print('OK', flush=True) |
| 140 | elif cmd == 'RESTART': |
| 141 | board.clear() |
| 142 | print('OK', flush=True) |
| 143 | elif cmd == 'BEGIN': |
| 144 | play() |
| 145 | elif cmd == 'TURN': |
| 146 | x, y = map(int, arg.split(',')) |
| 147 | board[(x, y)] = 2 |
| 148 | play() |
| 149 | elif cmd == 'BOARD': |
| 150 | board.clear() |
| 151 | for line in sys.stdin: |
| 152 | if line.strip().upper() == 'DONE': |
| 153 | break |
| 154 | x, y, colour = map(int, line.split(',')) |
| 155 | board[(x, y)] = colour |
| 156 | play() |
| 157 | elif cmd == 'INFO': |
| 158 | key, _, value = arg.partition(' ') |
| 159 | if key == 'timeout_turn': |
| 160 | turn_ms = int(value) |
| 161 | elif cmd == 'ABOUT': |
| 162 | print('name="threats", version="2", author="shoal-games"', flush=True) |
| 163 | elif cmd == 'END': |
| 164 | break |
| 165 | else: |
| 166 | print('UNKNOWN', flush=True) |
| 167 | |
| 168 | |
| 169 | if __name__ == '__main__': |
| 170 | main() |
