2011 bytes · sha256 422ed522d4e81e9a811… · public

"""Minimax bot: iterative-deepening alpha-beta search on top of the arena
helpers. Keeps a transposition table between moves (the bot process lives
for the whole game), and watches its clock."""
import time

from arena import MATE_SCORE

table = {}  # board key -> (depth, score); survives between moves


class OutOfTime(Exception):
    pass


def search(board, depth, alpha, beta, deadline):
    if time.monotonic() > deadline:
        raise OutOfTime()
    if board.is_game_over_fast():
        return board.evaluate()
    if depth == 0:
        return board.evaluate()
    key = (board.fen(), depth)
    if key in table:
        return table[key]
    best = -MATE_SCORE * 2
    for move in board.ordered_moves():
        board.push(move)
        score = -search(board, depth - 1, -beta, -alpha, deadline)
        board.pop()
        if score > best:
            best = score
        if best > alpha:
            alpha = best
        if alpha >= beta:
            break
    table[key] = best
    return best


def get_move(board, time_left_ms):
    # Use about 1/40 of the remaining clock (plus some of the increment).
    budget = time_left_ms / 40000 + board.increment_ms / 2000
    deadline = time.monotonic() + max(0.05, budget)
    moves = board.ordered_moves()
    best_move = moves[0]
    if len(table) > 200000:
        table.clear()
    for depth in range(1, 6):
        try:
            best_score, current = -MATE_SCORE * 2, None
            for move in moves:
                board.push(move)
                score = -search(board, depth - 1, -MATE_SCORE * 2, -best_score, deadline)
                board.pop()
                if score > best_score:
                    best_score, current = score, move
            best_move = current
            # Search the best move first next iteration.
            moves.remove(best_move)
            moves.insert(0, best_move)
        except OutOfTime:
            break
    return best_move