shared/bot/MinimaxAlphaBetaBot.ts

import { BOARD_SIZE, deserializeCoord, serializeCoord } from '../board.ts'
import { checkWin } from '../checkWin.ts'
import type { Cell, GameRules } from '../types.ts'
import { findThreatSpaceMove } from './ThreatSpaceSearch.ts'
import { ZobristHasher } from './Zobrist.ts'

export interface BotMove {
  x: number
  y: number
}

export interface BotContext {
  board: Record<string, Cell>
  currentPlayer: number
  playerSymbols: [string, string]
  rules: GameRules
  boardSize?: number
}

export interface MinimaxAlphaBetaOptions {
  maxDepth?: number
  timeBudgetMs?: number
  candidateRadius?: number
  maxCandidates?: number
  threatCandidateLimit?: number
  enableTranspositionTable?: boolean
  enableKillerMoves?: boolean
  enableIterativeDeepening?: boolean
  enableThreatSpaceSearch?: boolean
  panicPly?: number
}

interface ThreatSummary {
  openFours: number
  closedFours: number
  brokenFours: number
  openThrees: number
  closedThrees: number
  extensions: number
}

const DIRECTIONS: readonly [number, number][] = [[1, 0], [0, 1], [1, 1], [1, -1]]
const WIN_SCORE = 1_000_000_000
const FOUR_FOUR_SCORE = 80_000_000
const FOUR_THREE_SCORE = 50_000_000
const THREE_THREE_SCORE = 12_000_000

interface TranspositionEntry {
  depth: number
  value: number
  bound: 'exact' | 'lower' | 'upper'
  bestMove: BotMove | null
}

export class MinimaxAlphaBetaBot {
  private readonly maxDepth: number
  private readonly timeBudgetMs: number
  private readonly candidateRadius: number
  private readonly maxCandidates: number
  private readonly threatCandidateLimit: number
  private readonly enableTranspositionTable: boolean
  private readonly enableKillerMoves: boolean
  private readonly enableIterativeDeepening: boolean
  private readonly enableThreatSpaceSearch: boolean
  private readonly panicPly: number
  private deadline = 0
  private hardDeadline = 0
  private panicked = false
  private hasher = new ZobristHasher(BOARD_SIZE)
  private transpositionTable = new Map<bigint, TranspositionEntry>()
  private killerMoves: BotMove[][] = []

  constructor(options: MinimaxAlphaBetaOptions = {}) {
    this.maxDepth = options.maxDepth ?? 3
    this.timeBudgetMs = options.timeBudgetMs ?? 750
    this.candidateRadius = options.candidateRadius ?? 2
    this.maxCandidates = options.maxCandidates ?? 24
    this.threatCandidateLimit = options.threatCandidateLimit ?? 12
    this.enableTranspositionTable = options.enableTranspositionTable ?? true
    this.enableKillerMoves = options.enableKillerMoves ?? true
    this.enableIterativeDeepening = options.enableIterativeDeepening ?? true
    this.enableThreatSpaceSearch = options.enableThreatSpaceSearch ?? true
    this.panicPly = options.panicPly ?? 1
  }

  selectMove(context: BotContext): BotMove {
    const board = new Map(Object.entries(context.board))
    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    const player = context.currentPlayer
    const opponent = otherPlayer(player)
    this.deadline = Date.now() + this.timeBudgetMs
    this.hardDeadline = Date.now() + Math.max(this.timeBudgetMs * 1.5, this.timeBudgetMs + 200)
    this.panicked = false
    this.hasher = new ZobristHasher(boardSize)
    this.transpositionTable.clear()
    this.killerMoves = []
    const candidates = this.generateCandidates(board, boardSize)

    if (candidates.length === 0) {
      const center = Math.floor(boardSize / 2)
      return { x: center, y: center }
    }

    const ownWin = this.findWinningMove(board, candidates, player, context.playerSymbols, context.rules)
    if (ownWin) return ownWin

    const blockWin = this.findWinningMove(board, candidates, opponent, context.playerSymbols, context.rules)
    if (blockWin) return blockWin

    if (this.enableThreatSpaceSearch) {
      const threatSpaceMove = findThreatSpaceMove(context, {
        mode: 'vct',
        maxDepth: 5,
        candidateRadius: this.candidateRadius,
        maxCandidates: Math.min(16, this.maxCandidates),
        timeBudgetMs: Math.min(300, Math.max(180, Math.floor(this.timeBudgetMs / 2))),
      })
      if (threatSpaceMove) return threatSpaceMove.move
    }

    const forcingDefense = this.findForcingDefense(board, candidates, player, opponent, context)
    if (forcingDefense) return forcingDefense

    const urgentDefense = this.findUrgentDefense(board, candidates, player, opponent, context)
    if (urgentDefense) return urgentDefense

    let ordered = this.orderMoves(board, candidates, player, context, 0)
    let best = ordered[0]
    let bestScore = -Infinity
    let searchedAny = false
    const maxDepth = this.enableIterativeDeepening ? this.maxDepth : this.maxDepth
    const startDepth = this.enableIterativeDeepening ? 1 : this.maxDepth

    for (let depth = startDepth; depth <= maxDepth; depth++) {
      let completedDepth = true
      let depthBest = best
      let depthBestScore = -Infinity
      ordered = this.orderMoves(board, ordered, player, context, 0, best)

      for (const move of ordered) {
        if (this.outOfTime()) break
        const next = this.withMove(board, move, player, context.playerSymbols)
        const score = this.minimax(next, depth - 1, -Infinity, Infinity, false, opponent, player, context, 1)
        if (this.outOfTime()) break
        searchedAny = true
        if (score > depthBestScore || (score === depthBestScore && compareMove(move, depthBest) < 0)) {
          depthBest = move
          depthBestScore = score
        }
      }

      if (!completedDepth) break
      best = depthBest
      bestScore = depthBestScore
      if (Math.abs(bestScore) >= WIN_SCORE / 2) break
      if (!this.enableIterativeDeepening) break
      }

    if (!searchedAny || this.panicked) {
      const panicMove = this.panicMove(board, player, opponent, context, boardSize)
      if (panicMove) return panicMove
    }

    return best
  }

  private panicMove(
    board: Map<string, Cell>,
    player: number,
    opponent: number,
    context: BotContext,
    boardSize: number,
  ): BotMove | null {
    const candidates = this.generateCandidates(board, boardSize)
    if (candidates.length === 0) return null

    const ownWin = this.findWinningMove(board, candidates, player, context.playerSymbols, context.rules)
    if (ownWin) return ownWin

    const blockWin = this.findWinningMove(board, candidates, opponent, context.playerSymbols, context.rules)
    if (blockWin) return blockWin

    const ordered = this.orderMoves(board, candidates, player, context, 0).slice(0, this.maxCandidates)
    let best = ordered[0]
    let bestScore = -Infinity

    for (const move of ordered) {
      if (this.hardOutOfTime()) break
      const next = this.withMove(board, move, player, context.playerSymbols)
      const score = this.panicMinimax(next, this.panicPly - 1, -Infinity, Infinity, false, opponent, player, context, 1)
      if (score > bestScore || (score === bestScore && compareMove(move, best) < 0)) {
        best = move
        bestScore = score
      }
    }

    return best
  }

  private panicMinimax(
    board: Map<string, Cell>,
    depth: number,
    alpha: number,
    beta: number,
    maximizing: boolean,
    turn: number,
    rootPlayer: number,
    context: BotContext,
    ply: number,
  ): number {
    if (depth <= 0 || this.hardOutOfTime()) {
      return this.evaluate(board, rootPlayer, context)
    }

    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    const candidates = this.orderMoves(board, this.generateCandidates(board, boardSize), turn, {
      ...context,
      board: Object.fromEntries(board),
      currentPlayer: turn,
    }, ply).slice(0, this.maxCandidates)

    if (candidates.length === 0) return this.evaluate(board, rootPlayer, context)

    if (maximizing) {
      let value = -Infinity
      for (const move of candidates) {
        const next = this.withMove(board, move, turn, context.playerSymbols)
        if (checkWin(next, move.x, move.y, String(turn), context.rules.noOverlines).won) {
          return WIN_SCORE - (this.panicPly - depth)
        }
        value = Math.max(value, this.panicMinimax(next, depth - 1, alpha, beta, false, otherPlayer(turn), rootPlayer, context, ply + 1))
        alpha = Math.max(alpha, value)
        if (alpha >= beta || this.hardOutOfTime()) break
      }
      return value
    }

    let value = Infinity
    for (const move of candidates) {
      const next = this.withMove(board, move, turn, context.playerSymbols)
      if (checkWin(next, move.x, move.y, String(turn), context.rules.noOverlines).won) {
        return -WIN_SCORE + (this.panicPly - depth)
      }
      value = Math.min(value, this.panicMinimax(next, depth - 1, alpha, beta, true, otherPlayer(turn), rootPlayer, context, ply + 1))
      beta = Math.min(beta, value)
      if (alpha >= beta || this.hardOutOfTime()) break
    }

    return value
  }

  private minimax(
    board: Map<string, Cell>,
    depth: number,
    alpha: number,
    beta: number,
    maximizing: boolean,
    turn: number,
    rootPlayer: number,
    context: BotContext,
    ply: number,
  ): number {
    if (depth <= 0 || this.outOfTime()) {
      return this.evaluate(board, rootPlayer, context)
    }

    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    const hash = this.hasher.hash(board, turn)
    const originalAlpha = alpha
    const originalBeta = beta
    const ttEntry = this.enableTranspositionTable ? this.transpositionTable.get(hash) : undefined
    if (ttEntry && ttEntry.depth >= depth) {
      if (ttEntry.bound === 'exact') return ttEntry.value
      if (ttEntry.bound === 'lower') alpha = Math.max(alpha, ttEntry.value)
      if (ttEntry.bound === 'upper') beta = Math.min(beta, ttEntry.value)
      if (alpha >= beta) return ttEntry.value
    }

    const candidates = this.orderMoves(board, this.generateCandidates(board, boardSize), turn, {
      ...context,
      board: Object.fromEntries(board),
      currentPlayer: turn,
    }, ply, ttEntry?.bestMove ?? undefined)

    if (candidates.length === 0) return this.evaluate(board, rootPlayer, context)

    let bestMove: BotMove | null = null
    let result: number
    if (maximizing) {
      let value = -Infinity
      for (const move of candidates) {
        const next = this.withMove(board, move, turn, context.playerSymbols)
        if (checkWin(next, move.x, move.y, String(turn), context.rules.noOverlines).won) {
          return WIN_SCORE - (this.maxDepth - depth)
        }
        const child = this.minimax(next, depth - 1, alpha, beta, false, otherPlayer(turn), rootPlayer, context, ply + 1)
        if (child > value) {
          value = child
          bestMove = move
        }
        alpha = Math.max(alpha, value)
        if (alpha >= beta) {
          this.recordKillerMove(ply, move)
          break
        }
      }
      result = value
    } else {
      let value = Infinity
      for (const move of candidates) {
        const next = this.withMove(board, move, turn, context.playerSymbols)
        if (checkWin(next, move.x, move.y, String(turn), context.rules.noOverlines).won) {
          return -WIN_SCORE + (this.maxDepth - depth)
        }
        const child = this.minimax(next, depth - 1, alpha, beta, true, otherPlayer(turn), rootPlayer, context, ply + 1)
        if (child < value) {
          value = child
          bestMove = move
        }
        beta = Math.min(beta, value)
        if (alpha >= beta) {
          this.recordKillerMove(ply, move)
          break
        }
      }
      result = value
    }

    if (this.enableTranspositionTable) {
      const bound = result <= originalAlpha ? 'upper' : result >= originalBeta ? 'lower' : 'exact'
      this.transpositionTable.set(hash, { depth, value: result, bound, bestMove })
    }
    return result
  }

  private findWinningMove(
    board: Map<string, Cell>,
    candidates: BotMove[],
    player: number,
    symbols: [string, string],
    rules: GameRules,
  ): BotMove | null {
    for (const move of candidates) {
      const next = this.withMove(board, move, player, symbols)
      if (checkWin(next, move.x, move.y, String(player), rules.noOverlines).won) {
        return move
      }
    }
    return null
  }

  private evaluate(board: Map<string, Cell>, rootPlayer: number, context: BotContext): number {
    const own = this.scorePlayer(board, rootPlayer, context)
    const opponent = this.scorePlayer(board, otherPlayer(rootPlayer), context)
    return own - opponent * 1.08
  }

  private findWinningMoves(
    board: Map<string, Cell>,
    candidates: BotMove[],
    player: number,
    symbols: [string, string],
    rules: GameRules,
  ): BotMove[] {
    const wins: BotMove[] = []
    for (const move of candidates) {
      const next = this.withMove(board, move, player, symbols)
      if (checkWin(next, move.x, move.y, String(player), rules.noOverlines).won) {
        wins.push(move)
      }
    }
    return wins
  }

  private findForcingDefense(
    board: Map<string, Cell>,
    candidates: BotMove[],
    player: number,
    opponent: number,
    context: BotContext,
  ): BotMove | null {
    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    const currentThreat = this.maxForcingStarterThreat(board, opponent, context, boardSize)
    const currentDanger = currentThreat.danger
    if (currentDanger < FOUR_THREE_SCORE) return null

    let best: BotMove | null = null
    let bestDanger = Infinity
    let bestOwnScore = -Infinity
    let bestBlocksStarter = false

    for (const move of this.cheapOrderMoves(board, candidates, player, context, 0).slice(0, this.maxCandidates)) {
      const next = this.withMove(board, move, player, context.playerSymbols)
      const danger = this.maxForcingStarterDanger(next, opponent, context, boardSize)
      const ownScore = this.scorePlayer(next, player, context)
      const blocksStarter = currentThreat.moves.some(threat => sameMove(threat, move))

      if (
        danger < bestDanger ||
        (danger === bestDanger && blocksStarter && !bestBlocksStarter) ||
        (danger === bestDanger && ownScore > bestOwnScore) ||
        (danger === bestDanger && blocksStarter === bestBlocksStarter && ownScore === bestOwnScore && best && compareMove(move, best) < 0)
      ) {
        best = move
        bestDanger = danger
        bestOwnScore = ownScore
        bestBlocksStarter = blocksStarter
      }
    }

    return best && bestDanger < currentDanger ? best : null
  }

  private maxForcingStarterDanger(
    board: Map<string, Cell>,
    player: number,
    context: BotContext,
    boardSize: number,
  ): number {
    let danger = 0
    const moves = this.cheapOrderMoves(board, this.generateCandidates(board, boardSize), player, context, 0)
      .slice(0, this.maxCandidates)

    for (const move of moves) {
      danger = Math.max(danger, this.forcingStarterDanger(board, move, player, context, boardSize))
      if (danger >= WIN_SCORE / 2) return danger
    }

    return danger
  }

  private maxForcingStarterThreat(
    board: Map<string, Cell>,
    player: number,
    context: BotContext,
    boardSize: number,
  ): { danger: number; moves: BotMove[] } {
    let danger = 0
    let moves: BotMove[] = []
    const candidates = this.cheapOrderMoves(board, this.generateCandidates(board, boardSize), player, context, 0)
      .slice(0, this.maxCandidates)

    for (const move of candidates) {
      const moveDanger = this.forcingStarterDanger(board, move, player, context, boardSize)
      if (moveDanger > danger) {
        danger = moveDanger
        moves = [move]
      } else if (moveDanger === danger && danger > 0) {
        moves.push(move)
      }
    }

    return { danger, moves }
  }

  private forcingStarterDanger(
    board: Map<string, Cell>,
    move: BotMove,
    player: number,
    context: BotContext,
    boardSize: number,
  ): number {
    const next = this.withMove(board, move, player, context.playerSymbols)
    if (checkWin(next, move.x, move.y, String(player), context.rules.noOverlines).won) {
      return WIN_SCORE
    }

    const opponent = otherPlayer(player)
    const replyCandidates = this.generateCandidates(next, boardSize)
    const immediateWins = this.findWinningMoves(next, replyCandidates, player, context.playerSymbols, context.rules)
    if (immediateWins.length === 0) return this.threatDangerScore(this.analyzeThreats(next, player, context))

    let danger = 8_000_000 + immediateWins.length * 1_000_000 + this.threatDangerScore(this.analyzeThreats(next, player, context))

    for (const block of immediateWins.slice(0, 3)) {
      const afterBlock = this.withMove(next, block, opponent, context.playerSymbols)
      const continuations = this.cheapOrderMoves(afterBlock, this.generateCandidates(afterBlock, boardSize), player, context, 0)
        .slice(0, this.maxCandidates)
      let followUpDanger = 0
      for (const continuation of continuations) {
        const afterContinuation = this.withMove(afterBlock, continuation, player, context.playerSymbols)
        const continuationWon = checkWin(
          afterContinuation,
          continuation.x,
          continuation.y,
          String(player),
          context.rules.noOverlines,
        ).won
        followUpDanger = Math.max(
          followUpDanger,
          continuationWon ? WIN_SCORE : this.threatDangerScore(this.analyzeThreats(afterContinuation, player, context)),
        )
      }
      danger = Math.max(danger, 12_000_000 + followUpDanger)
    }

    return danger
  }

  private findUrgentDefense(
    board: Map<string, Cell>,
    candidates: BotMove[],
    player: number,
    opponent: number,
    context: BotContext,
  ): BotMove | null {
    const currentDanger = this.threatDangerScore(this.analyzeThreats(board, opponent, context))
    if (currentDanger < 120_000) return null

    let best: BotMove | null = null
    let bestDanger = Infinity
    let bestOwnScore = -Infinity

    for (const move of this.orderMoves(board, candidates, player, context, 0)) {
      const next = this.withMove(board, move, player, context.playerSymbols)
      const danger = this.threatDangerScore(this.analyzeThreats(next, opponent, context))
      const ownScore = this.scorePlayer(next, player, context)

      if (
        danger < bestDanger ||
        (danger === bestDanger && ownScore > bestOwnScore) ||
        (danger === bestDanger && ownScore === bestOwnScore && best && compareMove(move, best) < 0)
      ) {
        best = move
        bestDanger = danger
        bestOwnScore = ownScore
      }
    }

    return best && bestDanger < currentDanger ? best : null
  }

  private threatDangerScore(threats: ThreatSummary): number {
    let score = 0
    score += threats.openFours * 5_000_000
    score += threats.brokenFours * 4_500_000
    score += threats.closedFours * 900_000
    score += threats.openThrees * 180_000
    score += threats.closedThrees * 20_000
    if (threats.openFours >= 2) score += FOUR_FOUR_SCORE
    if (threats.openFours >= 1 && threats.openThrees >= 1) score += FOUR_THREE_SCORE
    if (threats.openThrees >= 2) score += THREE_THREE_SCORE
    return score
  }

  private scorePlayer(board: Map<string, Cell>, player: number, context: BotContext): number {
    const threats = this.analyzeThreats(board, player, context)
    let score = 0
    score += threats.openFours * 4_000_000
    score += threats.brokenFours * 3_200_000
    score += threats.closedFours * 900_000
    score += threats.openThrees * 180_000
    score += threats.closedThrees * 18_000
    score += threats.extensions * 1_200

    if (threats.openFours >= 2) score += FOUR_FOUR_SCORE
    if (threats.openFours >= 1 && threats.openThrees >= 1) score += FOUR_THREE_SCORE
    if (threats.openThrees >= 2) score += THREE_THREE_SCORE

    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    const center = (boardSize - 1) / 2
    for (const [key, cell] of board) {
      if (cell.playerId !== String(player)) continue
      const { x, y } = deserializeCoord(key)
      score += Math.max(0, boardSize - Math.abs(x - center) - Math.abs(y - center))
    }

    return score
  }

  private analyzeThreats(board: Map<string, Cell>, player: number, context: BotContext): ThreatSummary {
    const summary: ThreatSummary = {
      openFours: 0,
      closedFours: 0,
      brokenFours: 0,
      openThrees: 0,
      closedThrees: 0,
      extensions: 0,
    }
    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    const playerId = String(player)
    const opponentId = String(otherPlayer(player))

    for (const [dx, dy] of DIRECTIONS) {
      for (let y = 0; y < boardSize; y++) {
        for (let x = 0; x < boardSize; x++) {
          const endX = x + dx * 4
          const endY = y + dy * 4
          if (!inBounds(endX, endY, boardSize)) continue

          const cells: string[] = []
          let playerCount = 0
          let emptyCount = 0
          let blocked = false

          for (let i = 0; i < 5; i++) {
            const cell = board.get(serializeCoord(x + dx * i, y + dy * i))
            if (!cell) {
              cells.push('_')
              emptyCount++
            } else if (cell.playerId === playerId) {
              cells.push('X')
              playerCount++
            } else if (cell.playerId === opponentId) {
              blocked = true
              cells.push('O')
            }
          }

          if (blocked || playerCount === 0) continue

          const before = board.get(serializeCoord(x - dx, y - dy))
          const after = board.get(serializeCoord(x + dx * 5, y + dy * 5))
          const openEnds = Number(isOpenEnd(before, x - dx, y - dy, boardSize)) + Number(isOpenEnd(after, x + dx * 5, y + dy * 5, boardSize))
          const pattern = cells.join('')

          if (playerCount === 5) {
            summary.openFours += 2
          } else if (playerCount === 4 && emptyCount === 1) {
            const broken = pattern === 'XX_XX' || pattern === 'X_XXX' || pattern === 'XXX_X'
            if (openEnds >= 1) summary.openFours++
            else summary.closedFours++
            if (broken) summary.brokenFours++
          } else if (playerCount === 3 && emptyCount === 2) {
            if (openEnds >= 2) summary.openThrees++
            else if (openEnds >= 1) summary.closedThrees++
          } else if (playerCount === 2 && emptyCount === 3) {
            summary.extensions++
          }
        }
      }
    }

    return summary
  }

  private generateCandidates(board: Map<string, Cell>, boardSize: number): BotMove[] {
    if (board.size === 0) {
      const center = Math.floor(boardSize / 2)
      return [{ x: center, y: center }]
    }

    const candidates = new Map<string, BotMove>()
    for (const key of board.keys()) {
      const { x, y } = deserializeCoord(key)
      for (let dy = -this.candidateRadius; dy <= this.candidateRadius; dy++) {
        for (let dx = -this.candidateRadius; dx <= this.candidateRadius; dx++) {
          const nx = x + dx
          const ny = y + dy
          const nKey = serializeCoord(nx, ny)
          if (!inBounds(nx, ny, boardSize) || board.has(nKey)) continue
          candidates.set(nKey, { x: nx, y: ny })
        }
      }
    }
    return [...candidates.values()]
  }

  private orderMoves(
    board: Map<string, Cell>,
    moves: BotMove[],
    player: number,
    context: BotContext,
    ply: number,
    ttMove?: BotMove,
  ): BotMove[] {
    const cheap = this.cheapOrderMoves(board, moves, player, context, ply, ttMove)
      .slice(0, Math.max(this.maxCandidates, this.threatCandidateLimit))
    const filtered = this.threatSpaceFilter(board, cheap, player, context)
    return filtered.sort((a, b) => {
      const scoreB = this.quickMoveScore(board, b, player, context)
      const scoreA = this.quickMoveScore(board, a, player, context)
      return scoreB - scoreA || compareMove(a, b)
    }).slice(0, this.maxCandidates)
  }

  private cheapOrderMoves(
    board: Map<string, Cell>,
    moves: BotMove[],
    player: number,
    context: BotContext,
    ply: number,
    ttMove?: BotMove,
  ): BotMove[] {
    const boardSize = context.boardSize ?? context.rules.boardSize ?? BOARD_SIZE
    return [...moves].sort((a, b) => {
      const scoreB = this.cheapMoveScore(board, b, player, boardSize, ply, ttMove)
      const scoreA = this.cheapMoveScore(board, a, player, boardSize, ply, ttMove)
      return scoreB - scoreA || compareMove(a, b)
    })
  }

  private cheapMoveScore(
    board: Map<string, Cell>,
    move: BotMove,
    player: number,
    boardSize: number,
    ply: number,
    ttMove?: BotMove,
  ): number {
    let score = 0
    if (ttMove && sameMove(move, ttMove)) score += 10_000_000
    if (this.isKillerMove(ply, move)) score += 5_000_000
    score += this.localLinePotential(board, move, player, boardSize) * 100_000
    score += this.localLinePotential(board, move, otherPlayer(player), boardSize) * 80_000
    const center = (boardSize - 1) / 2
    score += Math.max(0, boardSize - Math.abs(move.x - center) - Math.abs(move.y - center))
    return score
  }

  private threatSpaceFilter(board: Map<string, Cell>, moves: BotMove[], player: number, context: BotContext): BotMove[] {
    const opponent = otherPlayer(player)
    const winning: BotMove[] = []
    const blocking: BotMove[] = []
    const forcing: BotMove[] = []

    for (const move of moves) {
      const own = this.withMove(board, move, player, context.playerSymbols)
      if (checkWin(own, move.x, move.y, String(player), context.rules.noOverlines).won) {
        winning.push(move)
        continue
      }
      const opp = this.withMove(board, move, opponent, context.playerSymbols)
      if (checkWin(opp, move.x, move.y, String(opponent), context.rules.noOverlines).won) {
        blocking.push(move)
        continue
      }
      const ownThreat = this.threatDangerScore(this.analyzeThreats(own, player, context))
      if (ownThreat >= 180_000) forcing.push(move)
    }

    if (winning.length > 0) return winning.slice(0, this.threatCandidateLimit)
    if (blocking.length > 0) return blocking.slice(0, this.threatCandidateLimit)
    if (forcing.length > 0) return [...forcing, ...moves.filter(move => !forcing.some(candidate => sameMove(candidate, move)))]
      .slice(0, Math.max(this.threatCandidateLimit, this.maxCandidates))
    return moves
  }

  private quickMoveScore(board: Map<string, Cell>, move: BotMove, player: number, context: BotContext): number {
    const next = this.withMove(board, move, player, context.playerSymbols)
    const threats = this.analyzeThreats(next, player, context)
    return this.scorePlayer(next, player, context)
      + threats.openFours * 2_000_000
      + threats.brokenFours * 1_000_000
      + threats.openThrees * 100_000
  }

  private withMove(board: Map<string, Cell>, move: BotMove, player: number, symbols: [string, string]): Map<string, Cell> {
    const next = new Map(board)
    next.set(serializeCoord(move.x, move.y), {
      playerId: String(player),
      symbol: symbols[player],
      timestamp: 0,
    })
    return next
  }

  private outOfTime(): boolean {
    if (Date.now() >= this.deadline) {
      this.panicked = true
      return true
    }
    return false
  }

  private hardOutOfTime(): boolean {
    return Date.now() >= this.hardDeadline
  }

  private recordKillerMove(ply: number, move: BotMove): void {
    if (!this.enableKillerMoves) return
    const moves = this.killerMoves[ply] ?? []
    if (moves.some(candidate => sameMove(candidate, move))) return
    this.killerMoves[ply] = [move, ...moves].slice(0, 2)
  }

  private isKillerMove(ply: number, move: BotMove): boolean {
    return this.enableKillerMoves && (this.killerMoves[ply] ?? []).some(candidate => sameMove(candidate, move))
  }

  private localLinePotential(board: Map<string, Cell>, move: BotMove, player: number, boardSize: number): number {
    const playerId = String(player)
    let best = 0
    for (const [dx, dy] of DIRECTIONS) {
      let count = 1
      let openEnds = 0
      let cx = move.x + dx
      let cy = move.y + dy
      while (board.get(serializeCoord(cx, cy))?.playerId === playerId) {
        count++
        cx += dx
        cy += dy
      }
      if (inBounds(cx, cy, boardSize) && !board.has(serializeCoord(cx, cy))) openEnds++
      cx = move.x - dx
      cy = move.y - dy
      while (board.get(serializeCoord(cx, cy))?.playerId === playerId) {
        count++
        cx -= dx
        cy -= dy
      }
      if (inBounds(cx, cy, boardSize) && !board.has(serializeCoord(cx, cy))) openEnds++
      best = Math.max(best, count * 3 + openEnds)
    }
    return best
  }
}

function otherPlayer(player: number): number {
  return player === 0 ? 1 : 0
}

function inBounds(x: number, y: number, boardSize: number): boolean {
  return x >= 0 && x < boardSize && y >= 0 && y < boardSize
}

function isOpenEnd(cell: Cell | undefined, x: number, y: number, boardSize: number): boolean {
  return inBounds(x, y, boardSize) && cell === undefined
}

function compareMove(a: BotMove, b: BotMove): number {
  return a.y - b.y || a.x - b.x
}

function sameMove(a: BotMove, b: BotMove): boolean {
  return a.x === b.x && a.y === b.y
}