#!/bin/python import sys import re import time import random from enum import Enum from typing import Dict, List, Tuple, Optional, Set, Iterator from collections import defaultdict class Color(Enum): WHITE = 0 BLACK = 1 class PieceType(Enum): PAWN = 1 KNIGHT = 2 BISHOP = 3 ROOK = 4 QUEEN = 5 KING = 6 class Square: def __init__(self, index: int): self.index = index @property def file(self) -> int: return self.index & 7 @property def rank(self) -> int: return self.index >> 3 @classmethod def from_coords(cls, file: int, rank: int) -> 'Square': return cls(rank * 8 + file) def __eq__(self, other): return isinstance(other, Square) and self.index == other.index def __hash__(self): return self.index def __str__(self): return f"{chr(self.file + ord('a'))}{self.rank + 1}" def __repr__(self): return str(self) class Move: def __init__(self, from_sq: Square, to_sq: Square, promotion: Optional[PieceType] = None): self.from_sq = from_sq self.to_sq = to_sq self.promotion = promotion def __eq__(self, other): if not isinstance(other, Move): return False return (self.from_sq == other.from_sq and self.to_sq == other.to_sq and self.promotion == other.promotion) def __hash__(self): return hash((self.from_sq.index, self.to_sq.index, self.promotion)) def __str__(self): result = f"{self.from_sq}{self.to_sq}" if self.promotion: piece_char = {PieceType.QUEEN: 'q', PieceType.ROOK: 'r', PieceType.BISHOP: 'b', PieceType.KNIGHT: 'n'} result += piece_char[self.promotion] return result def __repr__(self): return str(self) class Board: def __init__(self): self.pieces = {} self.side_to_move = Color.WHITE self.castling_rights = {"K": True, "Q": True, "k": True, "q": True} self.en_passant_square = None self.halfmove_clock = 0 self.fullmove_number = 1 self.position_history = [] self.move_history = [] self.move_list = [] self.piece_move_count = {} self._initialize_starting_position() def _initialize_starting_position(self): piece_placement = [ ("a1", (PieceType.ROOK, Color.WHITE)), ("b1", (PieceType.KNIGHT, Color.WHITE)), ("c1", (PieceType.BISHOP, Color.WHITE)), ("d1", (PieceType.QUEEN, Color.WHITE)), ("e1", (PieceType.KING, Color.WHITE)), ("f1", (PieceType.BISHOP, Color.WHITE)), ("g1", (PieceType.KNIGHT, Color.WHITE)), ("h1", (PieceType.ROOK, Color.WHITE)), ("a2", (PieceType.PAWN, Color.WHITE)), ("b2", (PieceType.PAWN, Color.WHITE)), ("c2", (PieceType.PAWN, Color.WHITE)), ("d2", (PieceType.PAWN, Color.WHITE)), ("e2", (PieceType.PAWN, Color.WHITE)), ("f2", (PieceType.PAWN, Color.WHITE)), ("g2", (PieceType.PAWN, Color.WHITE)), ("h2", (PieceType.PAWN, Color.WHITE)), ("a7", (PieceType.PAWN, Color.BLACK)), ("b7", (PieceType.PAWN, Color.BLACK)), ("c7", (PieceType.PAWN, Color.BLACK)), ("d7", (PieceType.PAWN, Color.BLACK)), ("e7", (PieceType.PAWN, Color.BLACK)), ("f7", (PieceType.PAWN, Color.BLACK)), ("g7", (PieceType.PAWN, Color.BLACK)), ("h7", (PieceType.PAWN, Color.BLACK)), ("a8", (PieceType.ROOK, Color.BLACK)), ("b8", (PieceType.KNIGHT, Color.BLACK)), ("c8", (PieceType.BISHOP, Color.BLACK)), ("d8", (PieceType.QUEEN, Color.BLACK)), ("e8", (PieceType.KING, Color.BLACK)), ("f8", (PieceType.BISHOP, Color.BLACK)), ("g8", (PieceType.KNIGHT, Color.BLACK)), ("h8", (PieceType.ROOK, Color.BLACK)) ] for square_str, (piece_type, color) in piece_placement: file = ord(square_str[0]) - ord('a') rank = int(square_str[1]) - 1 square = Square.from_coords(file, rank) self.pieces[square] = (piece_type, color) def get_piece_at(self, square: Square) -> Optional[Tuple[PieceType, Color]]: return self.pieces.get(square) def make_move(self, move: Move) -> bool: piece_info = self.pieces.get(move.from_sq) if not piece_info: return False piece_type, piece_color = piece_info if piece_color != self.side_to_move: return False captured_piece = self.pieces.get(move.to_sq) new_pieces = dict(self.pieces) del new_pieces[move.from_sq] promotion_type = move.promotion if move.promotion else piece_type new_pieces[move.to_sq] = (promotion_type, piece_color) if piece_type == PieceType.KING and abs(move.from_sq.file - move.to_sq.file) == 2: rook_from_file = 7 if move.to_sq.file == 6 else 0 rook_to_file = 5 if move.to_sq.file == 6 else 3 rook_from = Square.from_coords(rook_from_file, move.from_sq.rank) rook_to = Square.from_coords(rook_to_file, move.from_sq.rank) rook_piece = new_pieces[rook_from] del new_pieces[rook_from] new_pieces[rook_to] = rook_piece if piece_type == PieceType.PAWN and move.to_sq == self.en_passant_square: captured_sq = Square.from_coords(move.to_sq.file, move.from_sq.rank) if captured_sq in new_pieces: del new_pieces[captured_sq] new_en_passant = None if piece_type == PieceType.PAWN and abs(move.from_sq.rank - move.to_sq.rank) == 2: direction = 1 if piece_color == Color.WHITE else -1 new_en_passant = Square.from_coords(move.from_sq.file, move.from_sq.rank + direction) new_castling = dict(self.castling_rights) if piece_type == PieceType.KING: if piece_color == Color.WHITE: new_castling["K"] = False new_castling["Q"] = False else: new_castling["k"] = False new_castling["q"] = False elif piece_type == PieceType.ROOK: if move.from_sq.file == 0: if piece_color == Color.WHITE: new_castling["Q"] = False else: new_castling["q"] = False elif move.from_sq.file == 7: if piece_color == Color.WHITE: new_castling["K"] = False else: new_castling["k"] = False new_halfmove = self.halfmove_clock + 1 if piece_type == PieceType.PAWN or captured_piece: new_halfmove = 0 new_fullmove = self.fullmove_number if self.side_to_move == Color.BLACK: new_fullmove += 1 new_board = Board() new_board.pieces = new_pieces new_board.side_to_move = Color.BLACK if self.side_to_move == Color.WHITE else Color.WHITE new_board.castling_rights = new_castling new_board.en_passant_square = new_en_passant new_board.halfmove_clock = new_halfmove new_board.fullmove_number = new_fullmove new_board.position_history = self.position_history + [self.get_position_hash()] self.__dict__.update(new_board.__dict__) self.move_history.append(move) self.move_list.append(self.move_to_algebraic(move)) return True def get_position_hash(self) -> str: pieces_str = [] for rank in range(7, -1, -1): empty = 0 for file in range(8): sq = Square.from_coords(file, rank) piece = self.pieces.get(sq) if piece: if empty > 0: pieces_str.append(str(empty)) empty = 0 piece_type, color = piece char = piece_type.name[0].lower() if piece_type != PieceType.KNIGHT else 'n' if color == Color.WHITE: char = char.upper() pieces_str.append(char) else: empty += 1 if empty > 0: pieces_str.append(str(empty)) if rank > 0: pieces_str.append('/') fen_pieces = ''.join(pieces_str) fen_side = 'w' if self.side_to_move == Color.WHITE else 'b' fen_castling = ''.join([k for k, v in self.castling_rights.items() if v]) or '-' fen_ep = str(self.en_passant_square) if self.en_passant_square else '-' fen_halfmove = str(self.halfmove_clock) fen_fullmove = str(self.fullmove_number) return f"{fen_pieces} {fen_side} {fen_castling} {fen_ep} {fen_halfmove} {fen_fullmove}" def is_in_check(self, color: Color) -> bool: king_square = None for sq, (piece_type, piece_color) in self.pieces.items(): if piece_type == PieceType.KING and piece_color == color: king_square = sq break if not king_square: return False opponent_color = Color.BLACK if color == Color.WHITE else Color.WHITE knight_moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)] for dx, dy in knight_moves: f = king_square.file + dx r = king_square.rank + dy if 0 <= f < 8 and 0 <= r < 8: sq = Square.from_coords(f, r) piece = self.pieces.get(sq) if piece and piece[1] == opponent_color and piece[0] == PieceType.KNIGHT: return True directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)] for dx, dy in directions: f, r = king_square.file + dx, king_square.rank + dy while 0 <= f < 8 and 0 <= r < 8: sq = Square.from_coords(f, r) piece = self.pieces.get(sq) if piece: if piece[1] == opponent_color: piece_type = piece[0] if dx == 0 or dy == 0: if piece_type in [PieceType.ROOK, PieceType.QUEEN]: return True else: if piece_type in [PieceType.BISHOP, PieceType.QUEEN]: return True if abs(f - king_square.file) == 1 and piece_type == PieceType.PAWN: pawn_dir = 1 if opponent_color == Color.BLACK else -1 if r - king_square.rank == pawn_dir: return True break f += dx r += dy return False def generate_pseudo_legal_moves(self) -> List[Move]: moves = [] for from_sq, (piece_type, piece_color) in self.pieces.items(): if piece_color != self.side_to_move: continue if piece_type == PieceType.PAWN: direction = 1 if piece_color == Color.WHITE else -1 start_rank = 1 if piece_color == Color.WHITE else 6 forward = Square.from_coords(from_sq.file, from_sq.rank + direction) if not self.pieces.get(forward): moves.append(Move(from_sq, forward)) if from_sq.rank == start_rank: double = Square.from_coords(from_sq.file, from_sq.rank + 2 * direction) if not self.pieces.get(double): moves.append(Move(from_sq, double)) for dx in [-1, 1]: f = from_sq.file + dx r = from_sq.rank + direction if 0 <= f < 8 and 0 <= r < 8: to_sq = Square.from_coords(f, r) target = self.pieces.get(to_sq) if target and target[1] != piece_color: moves.append(Move(from_sq, to_sq)) elif self.en_passant_square and to_sq.index == self.en_passant_square.index: moves.append(Move(from_sq, to_sq)) elif piece_type == PieceType.KNIGHT: jumps = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)] for dx, dy in jumps: f = from_sq.file + dx r = from_sq.rank + dy if 0 <= f < 8 and 0 <= r < 8: to_sq = Square.from_coords(f, r) target = self.pieces.get(to_sq) if not target or target[1] != piece_color: moves.append(Move(from_sq, to_sq)) elif piece_type == PieceType.BISHOP: directions = [(1, 1), (1, -1), (-1, 1), (-1, -1)] for dx, dy in directions: f, r = from_sq.file + dx, from_sq.rank + dy while 0 <= f < 8 and 0 <= r < 8: to_sq = Square.from_coords(f, r) target = self.pieces.get(to_sq) if not target: moves.append(Move(from_sq, to_sq)) elif target[1] != piece_color: moves.append(Move(from_sq, to_sq)) break else: break f += dx r += dy elif piece_type == PieceType.ROOK: directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] for dx, dy in directions: f, r = from_sq.file + dx, from_sq.rank + dy while 0 <= f < 8 and 0 <= r < 8: to_sq = Square.from_coords(f, r) target = self.pieces.get(to_sq) if not target: moves.append(Move(from_sq, to_sq)) elif target[1] != piece_color: moves.append(Move(from_sq, to_sq)) break else: break f += dx r += dy elif piece_type == PieceType.QUEEN: directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)] for dx, dy in directions: f, r = from_sq.file + dx, from_sq.rank + dy while 0 <= f < 8 and 0 <= r < 8: to_sq = Square.from_coords(f, r) target = self.pieces.get(to_sq) if not target: moves.append(Move(from_sq, to_sq)) elif target[1] != piece_color: moves.append(Move(from_sq, to_sq)) break else: break f += dx r += dy elif piece_type == PieceType.KING: for dx in [-1, 0, 1]: for dy in [-1, 0, 1]: if dx == 0 and dy == 0: continue f = from_sq.file + dx r = from_sq.rank + dy if 0 <= f < 8 and 0 <= r < 8: to_sq = Square.from_coords(f, r) target = self.pieces.get(to_sq) if not target or target[1] != piece_color: moves.append(Move(from_sq, to_sq)) if piece_color == Color.WHITE: if self.castling_rights.get("K"): if (not self.pieces.get(Square.from_coords(5, 0)) and not self.pieces.get(Square.from_coords(6, 0)) and not self.is_in_check(Color.WHITE)): safe = True for f in [5, 6]: sq = Square.from_coords(f, 0) if self.is_square_attacked(sq, Color.BLACK): safe = False break if safe: moves.append(Move(Square.from_coords(4, 0), Square.from_coords(6, 0))) if self.castling_rights.get("Q"): if (not self.pieces.get(Square.from_coords(1, 0)) and not self.pieces.get(Square.from_coords(2, 0)) and not self.pieces.get(Square.from_coords(3, 0)) and not self.is_in_check(Color.WHITE)): safe = True for f in [2, 3]: sq = Square.from_coords(f, 0) if self.is_square_attacked(sq, Color.BLACK): safe = False break if safe: moves.append(Move(Square.from_coords(4, 0), Square.from_coords(2, 0))) else: if self.castling_rights.get("k"): if (not self.pieces.get(Square.from_coords(5, 7)) and not self.pieces.get(Square.from_coords(6, 7)) and not self.is_in_check(Color.BLACK)): safe = True for f in [5, 6]: sq = Square.from_coords(f, 7) if self.is_square_attacked(sq, Color.WHITE): safe = False break if safe: moves.append(Move(Square.from_coords(4, 7), Square.from_coords(6, 7))) if self.castling_rights.get("q"): if (not self.pieces.get(Square.from_coords(1, 7)) and not self.pieces.get(Square.from_coords(2, 7)) and not self.pieces.get(Square.from_coords(3, 7)) and not self.is_in_check(Color.BLACK)): safe = True for f in [2, 3]: sq = Square.from_coords(f, 7) if self.is_square_attacked(sq, Color.WHITE): safe = False break if safe: moves.append(Move(Square.from_coords(4, 7), Square.from_coords(2, 7))) promotion_moves = [] for move in moves: from_sq = move.from_sq piece_info = self.pieces.get(from_sq) if piece_info and piece_info[0] == PieceType.PAWN: if (piece_info[1] == Color.WHITE and move.to_sq.rank == 7) or \ (piece_info[1] == Color.BLACK and move.to_sq.rank == 0): for promo in [PieceType.QUEEN, PieceType.ROOK, PieceType.BISHOP, PieceType.KNIGHT]: promotion_moves.append(Move(from_sq, move.to_sq, promo)) moves = [m for m in moves if not (self.pieces.get(m.from_sq) and self.pieces.get(m.from_sq)[0] == PieceType.PAWN and ((self.pieces.get(m.from_sq)[1] == Color.WHITE and m.to_sq.rank == 7) or (self.pieces.get(m.from_sq)[1] == Color.BLACK and m.to_sq.rank == 0)))] moves.extend(promotion_moves) return moves def generate_legal_moves(self) -> List[Move]: pseudo = self.generate_pseudo_legal_moves() legal = [] for move in pseudo: test_board = Board() test_board.__dict__.update(self.__dict__) test_board.position_history = list(self.position_history) if test_board.make_move(move): if not test_board.is_in_check(self.side_to_move): legal.append(move) return legal def move_to_algebraic(self, move): piece_info = self.pieces.get(move.from_sq) if not piece_info: return "???" piece_type, color = piece_info target = self.pieces.get(move.to_sq) capture = target is not None if piece_type == PieceType.PAWN: base = str(move.to_sq) if capture: base = f"{chr(move.from_sq.file + ord('a'))}x{base}" elif piece_type == PieceType.KING and abs(move.from_sq.file - move.to_sq.file) == 2: if move.to_sq.file == 6: base = "O-O" elif move.to_sq.file == 2: base = "O-O-O" else: base = f"K{str(move.to_sq)}" else: piece_letter = {PieceType.KNIGHT: 'N', PieceType.BISHOP: 'B', PieceType.ROOK: 'R', PieceType.QUEEN: 'Q', PieceType.KING: 'K'}[piece_type] base = f"{piece_letter}{str(move.to_sq)}" if capture: base = f"{piece_letter}x{str(move.to_sq)}" if move.promotion: promo = {'q':'Q', 'r':'R', 'b':'B', 'n':'N'}[move.promotion.name[0].lower()] base += f"={promo}" return base def is_square_attacked(self, square: Square, by_color: Color) -> bool: knight_moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)] for dx, dy in knight_moves: f = square.file + dx r = square.rank + dy if 0 <= f < 8 and 0 <= r < 8: sq = Square.from_coords(f, r) piece = self.pieces.get(sq) if piece and piece[1] == by_color and piece[0] == PieceType.KNIGHT: return True pawn_dir = 1 if by_color == Color.BLACK else -1 for dx in [-1, 1]: f = square.file + dx r = square.rank + pawn_dir if 0 <= f < 8 and 0 <= r < 8: sq = Square.from_coords(f, r) piece = self.pieces.get(sq) if piece and piece[1] == by_color and piece[0] == PieceType.PAWN: return True # King attacks king_deltas = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] for dx, dy in king_deltas: f = square.file + dx r = square.rank + dy if 0 <= f < 8 and 0 <= r < 8: sq = Square.from_coords(f, r) piece = self.pieces.get(sq) if piece and piece[1] == by_color and piece[0] == PieceType.KING: return True directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)] for dx, dy in directions: f, r = square.file + dx, square.rank + dy while 0 <= f < 8 and 0 <= r < 8: sq = Square.from_coords(f, r) piece = self.pieces.get(sq) if piece: if piece[1] == by_color: piece_type = piece[0] if dx == 0 or dy == 0: if piece_type in [PieceType.ROOK, PieceType.QUEEN]: return True else: if piece_type in [PieceType.BISHOP, PieceType.QUEEN]: return True break f += dx r += dy return False def is_checkmate(self) -> bool: if not self.is_in_check(self.side_to_move): return False return len(self.generate_legal_moves()) == 0 def is_stalemate(self) -> bool: if self.is_in_check(self.side_to_move): return False return len(self.generate_legal_moves()) == 0 def is_insufficient_material(self) -> bool: pieces = list(self.pieces.values()) if len(pieces) <= 2: return True if len(pieces) == 3: bishops = [p for p in pieces if p[0] == PieceType.BISHOP] knights = [p for p in pieces if p[0] == PieceType.KNIGHT] if len(bishops) == 1 or len(knights) == 1: return True if len(pieces) == 4: bishops = [p for p in pieces if p[0] == PieceType.BISHOP] if len(bishops) == 2: bishop_squares = [] for sq, piece in self.pieces.items(): if piece[0] == PieceType.BISHOP: bishop_squares.append(sq) if len(bishop_squares) == 2: color1 = (bishop_squares[0].file + bishop_squares[0].rank) % 2 color2 = (bishop_squares[1].file + bishop_squares[1].rank) % 2 if color1 == color2: return True return False def is_fifty_moves(self) -> bool: return self.halfmove_clock >= 100 def is_threefold_repetition(self) -> bool: current_hash = self.get_position_hash() position_fen = current_hash.split()[0] count = 0 for pos in self.position_history: if pos.split()[0] == position_fen: count += 1 return count >= 2 class Evaluation: piece_square_tables = { PieceType.QUEEN: [ [-2, -1, -1, -0.5, -0.5, -1, -1, -2], [-1, 0, 0, 0, 0, 0, 0, -1], [-1, 0, 0.5, 0.5, 0.5, 0.5, 0, -1], [-0.5, 0, 0.5, 0.5, 0.5, 0.5, 0, -0.5], [0, 0, 0.5, 0.5, 0.5, 0.5, 0, -0.5], [-1, 0.5, 0.5, 0.5, 0.5, 0.5, 0, -1], [-1, 0, 0.5, 0, 0, 0, 0, -1], [-2, -1, -1, -0.5, -0.5, -1, -1, -2] ] } @staticmethod def evaluate(board: Board) -> float: score = 0.0 piece_values = { PieceType.PAWN: 1.00, PieceType.KNIGHT: 3.20, PieceType.BISHOP: 3.35, PieceType.ROOK: 5.10, PieceType.QUEEN: 9.60, PieceType.KING: 0.0 } center_squares = [Square.from_coords(3, 3), Square.from_coords(4, 3), Square.from_coords(3, 4), Square.from_coords(4, 4)] extended_center = [Square.from_coords(2, 2), Square.from_coords(3, 2), Square.from_coords(4, 2), Square.from_coords(5, 2), Square.from_coords(2, 3), Square.from_coords(5, 3), Square.from_coords(2, 4), Square.from_coords(5, 4), Square.from_coords(2, 5), Square.from_coords(3, 5), Square.from_coords(4, 5), Square.from_coords(5, 5)] white_pawns = [] black_pawns = [] for square, (piece_type, color) in board.pieces.items(): value = piece_values[piece_type] sign = 1.0 if color == Color.WHITE else -1.0 score += value * sign if piece_type in Evaluation.piece_square_tables: table = Evaluation.piece_square_tables[piece_type] if color == Color.WHITE: pst = table[square.rank][square.file] else: pst = table[7 - square.rank][square.file] score += pst * sign if piece_type == PieceType.PAWN: if color == Color.WHITE: white_pawns.append(square) else: black_pawns.append(square) if square in center_squares: score += 0.50 * sign elif square in extended_center: score += 0.25 * sign if (color == Color.WHITE and square.rank == 6) or (color == Color.BLACK and square.rank == 1): score += 0.80 * sign files = [sq.file for sq in (white_pawns if color == Color.WHITE else black_pawns)] if files.count(square.file) > 1: score -= 0.30 * sign elif piece_type == PieceType.KNIGHT: if square in center_squares: score += 0.30 * sign elif square in extended_center: score += 0.15 * sign elif piece_type == PieceType.BISHOP: if square in extended_center: score += 0.15 * sign elif piece_type == PieceType.ROOK: if (color == Color.WHITE and square.rank == 6) or (color == Color.BLACK and square.rank == 1): score += 0.50 * sign elif piece_type == PieceType.KING: # King movement penalties if not board.is_in_check(color): # Penalize king moves without being in check score -= 0.3 * sign # Penalize early king moves if board.fullmove_number <= 10: starting_king = Square.from_coords(4, 0 if color == Color.WHITE else 7) if square != starting_king: score -= 0.5 * sign # Original king evaluation if board.fullmove_number < 20: if (color == Color.WHITE and square.file in [2, 6]) or (color == Color.BLACK and square.file in [2, 6]): score += 0.60 * sign elif square.file == 4: score -= 0.80 * sign if board.fullmove_number < 15: if (color == Color.WHITE and square.rank != 0) or (color == Color.BLACK and square.rank != 7): score -= 1.0 * sign starting_king = Square.from_coords(4, 0 if color == Color.WHITE else 7) if square != starting_king: score -= 0.5 * sign if square.rank in [0, 7]: shield_score = 0 for f in range(max(0, square.file - 1), min(8, square.file + 2)): shield_sq = Square.from_coords(f, square.rank + (1 if color == Color.WHITE else -1)) if board.pieces.get(shield_sq) and board.pieces[shield_sq][0] == PieceType.PAWN and board.pieces[shield_sq][1] == color: shield_score += 0.20 score += shield_score * sign developed_white = 0 developed_black = 0 for sq, (pt, col) in board.pieces.items(): if pt in [PieceType.KNIGHT, PieceType.BISHOP, PieceType.ROOK, PieceType.QUEEN]: if col == Color.WHITE: if sq.rank > 1: developed_white += 1 else: if sq.rank < 6: developed_black += 1 score += developed_white * 0.05 score -= developed_black * 0.05 # Development bonuses for square, (piece_type, color) in board.pieces.items(): sign = 1.0 if color == Color.WHITE else -1.0 # Bishop from f1 development bonus if piece_type == PieceType.BISHOP and square == Square.from_coords(5, 0) and color == Color.WHITE: score += 0.2 * sign # Knight from b1 development bonus if piece_type == PieceType.KNIGHT and square == Square.from_coords(1, 0) and color == Color.WHITE: score += 0.2 * sign # Bishop from c8 development bonus (black) if piece_type == PieceType.BISHOP and square == Square.from_coords(2, 7) and color == Color.BLACK: score -= 0.2 * sign # Knight from g8 development bonus (black) if piece_type == PieceType.KNIGHT and square == Square.from_coords(6, 7) and color == Color.BLACK: score -= 0.2 * sign # Castling bonus if not board.castling_rights.get('K', False) and not board.castling_rights.get('Q', False): score += 0.3 # White has castled if not board.castling_rights.get('k', False) and not board.castling_rights.get('q', False): score -= 0.3 # Black has castled if board.fullmove_number < 20: if not board.castling_rights.get('K', False): score -= 0.3 if not board.castling_rights.get('Q', False): score -= 0.3 if not board.castling_rights.get('k', False): score += 0.3 if not board.castling_rights.get('q', False): score += 0.3 bishops = [p for p in board.pieces.values() if p[0] == PieceType.BISHOP] white_bishops = [p for p in bishops if p[1] == Color.WHITE] black_bishops = [p for p in bishops if p[1] == Color.BLACK] if len(white_bishops) == 2: score += 0.40 if len(black_bishops) == 2: score -= 0.40 for file in range(8): white_pawns_in_file = sum(1 for sq in white_pawns if sq.file == file) black_pawns_in_file = sum(1 for sq in black_pawns if sq.file == file) if white_pawns_in_file == 0: for rank in range(8): sq = Square.from_coords(file, rank) piece = board.pieces.get(sq) if piece and piece[1] == Color.WHITE and piece[0] in [PieceType.ROOK, PieceType.QUEEN]: score += 0.10 if black_pawns_in_file == 0: for rank in range(8): sq = Square.from_coords(file, rank) piece = board.pieces.get(sq) if piece and piece[1] == Color.BLACK and piece[0] in [PieceType.ROOK, PieceType.QUEEN]: score -= 0.10 white_isolated = 0 black_isolated = 0 for pawn_sq in white_pawns: adjacent_files = [pawn_sq.file - 1, pawn_sq.file + 1] has_friend = False for adj_file in adjacent_files: if 0 <= adj_file < 8: if any(p.file == adj_file for p in white_pawns): has_friend = True break if not has_friend: white_isolated += 1 for pawn_sq in black_pawns: adjacent_files = [pawn_sq.file - 1, pawn_sq.file + 1] has_friend = False for adj_file in adjacent_files: if 0 <= adj_file < 8: if any(p.file == adj_file for p in black_pawns): has_friend = True break if not has_friend: black_isolated += 1 score -= white_isolated * 0.35 score += black_isolated * 0.35 if board.is_checkmate(): if board.side_to_move == Color.WHITE: return -10000.0 else: return 10000.0 if board.is_stalemate() or board.is_insufficient_material() or board.is_fifty_moves() or board.is_threefold_repetition(): return 0.0 if board.side_to_move == Color.BLACK: score = -score opponent_color = Color.BLACK if board.side_to_move == Color.WHITE else Color.WHITE if board.is_in_check(opponent_color): score -= 0.05 return score class Search: def __init__(self): self.nodes_searched = 0 self.transposition_table = {} self.killer_moves = [[None, None] for _ in range(100)] self.history_table = [[[0 for _ in range(64)] for _ in range(64)] for _ in range(2)] def iterative_deepening(self, board: Board, max_depth: int, time_limit: float) -> Tuple[Optional[Move], float]: start_time = time.time() best_move = None best_score = -float('inf') for depth in range(1, max_depth + 1): if time.time() - start_time > time_limit: break score, move = self.alpha_beta(board, depth, -float('inf'), float('inf'), start_time, time_limit) if move is not None and time.time() - start_time <= time_limit: best_move = move best_score = score else: break return best_move, best_score def alpha_beta(self, board: Board, depth: int, alpha: float, beta: float, start_time: float, time_limit: float) -> Tuple[float, Optional[Move]]: if time.time() - start_time > time_limit: return 0, None self.nodes_searched += 1 if depth == 0: return self.quiescence_search(board, alpha, beta, start_time, time_limit), None # Simple transposition table lookup position_hash = board.get_position_hash() if position_hash in self.transposition_table: entry = self.transposition_table[position_hash] if entry['depth'] >= depth: if entry['flag'] == 'exact': return entry['score'], entry['move'] elif entry['flag'] == 'lowerbound': alpha = max(alpha, entry['score']) elif entry['flag'] == 'upperbound': beta = min(beta, entry['score']) if alpha >= beta: return entry['score'], entry['move'] moves = board.generate_legal_moves() if not moves: if board.is_in_check(board.side_to_move): return -10000 + depth, None else: return 0, None moves = self.order_moves(board, moves, depth) best_move = None best_score = -float('inf') flag = 'exact' for move in moves: new_board = Board() new_board.__dict__.update(board.__dict__) new_board.position_history = list(board.position_history) if not new_board.make_move(move): continue score, _ = self.alpha_beta(new_board, depth - 1, -beta, -alpha, start_time, time_limit) score = -score if score >= beta: # Beta cutoff - store as lower bound self.transposition_table[position_hash] = { 'score': beta, 'depth': depth, 'flag': 'lowerbound', 'move': move } if move.promotion is None: self.killer_moves[depth][1] = self.killer_moves[depth][0] self.killer_moves[depth][0] = move return beta, None if score > alpha: alpha = score best_move = move best_score = score flag = 'exact' else: flag = 'upperbound' # Store in transposition table self.transposition_table[position_hash] = { 'score': best_score, 'depth': depth, 'flag': flag, 'move': best_move } return alpha, best_move def quiescence_search(self, board: Board, alpha: float, beta: float, start_time: float, time_limit: float) -> float: if time.time() - start_time > time_limit: return 0 self.nodes_searched += 1 stand_pat = Evaluation.evaluate(board) if stand_pat >= beta: return beta if alpha < stand_pat: alpha = stand_pat moves = board.generate_legal_moves() captures = [] for move in moves: from_piece = board.pieces.get(move.from_sq) to_piece = board.pieces.get(move.to_sq) if to_piece or (from_piece and from_piece[0] == PieceType.PAWN and board.en_passant_square and move.to_sq.index == board.en_passant_square.index): captures.append(move) captures = sorted(captures, key=lambda m: self.capture_score(board, m), reverse=True) for move in captures: new_board = Board() new_board.__dict__.update(board.__dict__) new_board.position_history = list(board.position_history) if not new_board.make_move(move): continue score = -self.quiescence_search(new_board, -beta, -alpha, start_time, time_limit) if score >= beta: return beta if score > alpha: alpha = score return alpha def capture_score(self, board: Board, move: Move) -> int: from_piece = board.pieces.get(move.from_sq) to_piece = board.pieces.get(move.to_sq) if not from_piece: return 0 victim_value = 0 if to_piece: values = {PieceType.PAWN: 1, PieceType.KNIGHT: 3, PieceType.BISHOP: 3, PieceType.ROOK: 5, PieceType.QUEEN: 9} victim_value = values.get(to_piece[0], 0) elif board.en_passant_square and move.to_sq.index == board.en_passant_square.index: victim_value = 1 attacker_value = {PieceType.PAWN: 1, PieceType.KNIGHT: 3, PieceType.BISHOP: 3, PieceType.ROOK: 5, PieceType.QUEEN: 9}.get(from_piece[0], 0) return victim_value * 10 - attacker_value def order_moves(self, board: Board, moves: List[Move], depth: int) -> List[Move]: move_scores = [] for move in moves: score = 0 from_piece = board.pieces.get(move.from_sq) to_piece = board.pieces.get(move.to_sq) # Prioritize captures if to_piece: values = {PieceType.PAWN: 1, PieceType.KNIGHT: 3, PieceType.BISHOP: 3, PieceType.ROOK: 5, PieceType.QUEEN: 9} victim_value = values.get(to_piece[0], 0) attacker_value = values.get(from_piece[0], 0) if from_piece else 0 score += 10000 + victim_value * 10 - attacker_value elif board.en_passant_square and move.to_sq.index == board.en_passant_square.index: score += 10000 + 1 * 10 - 1 # Prioritize promotions if move.promotion: score += 9000 # Prioritize killer moves if depth < len(self.killer_moves): if self.killer_moves[depth][0] is not None and self.killer_moves[depth][0] == move: score += 900 elif self.killer_moves[depth][1] is not None and self.killer_moves[depth][1] == move: score += 800 # History heuristic if from_piece and move.from_sq.index < 64 and move.to_sq.index < 64: color_idx = 0 if from_piece[1] == Color.WHITE else 1 history_score = self.history_table[color_idx][move.from_sq.index][move.to_sq.index] score += history_score move_scores.append((score, move)) # Sort with efficient algorithm for small lists if len(move_scores) <= 10: # Use simple sort for small lists move_scores.sort(key=lambda x: x[0], reverse=True) else: # Use Timsort for larger lists move_scores.sort(key=lambda x: x[0], reverse=True) return [move for _, move in move_scores] class OpeningBook: def __init__(self): self.book = { "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1": [ ("e2e4", 100), ("d2d4", 90), ("c2c4", 70), ("g1f3", 80) ], "rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq - 0 1": [ ("e7e5", 100), ("c7c5", 80), ("e7e6", 70), ("d7d5", 60) ], "rnbqkbnr/pppp1ppp/8/4p3/4P3/8/PPPP1PPP/RNBQKBNR w KQkq - 0 2": [ ("g1f3", 100), ("f1c4", 70), ("f1b5", 80), ("d2d4", 90) ], "rnbqkbnr/pppp1ppp/8/4p3/4P3/5N2/PPPP1PPP/RNBQKB1R b KQkq - 1 2": [ ("b8c6", 100), ("g8f6", 90), ("d7d6", 80) ] } def get_move(self, fen: str) -> Optional[str]: if fen in self.book: moves = self.book[fen] total = sum(weight for _, weight in moves) r = random.randint(1, total) cumulative = 0 for move_str, weight in moves: cumulative += weight if r <= cumulative: return move_str return None class StackfishEngine: def __init__(self): self.board = Board() self.search = Search() self.book = OpeningBook() def uci_move(self, move_str: str) -> bool: try: move_str = move_str.strip() # Support abbreviated notation (e.g., "e4" for pawn moves) if len(move_str) == 2: # Parse target square to_file = ord(move_str[0]) - ord('a') to_rank = int(move_str[1]) - 1 if not (0 <= to_file < 8 and 0 <= to_rank < 8): return False to_sq = Square.from_coords(to_file, to_rank) # Find all legal moves to this square legal_moves = self.board.generate_legal_moves() matching_moves = [move for move in legal_moves if move.to_sq == to_sq] if len(matching_moves) == 1: # Only one piece can move there, use it return self.board.make_move(matching_moves[0]) elif len(matching_moves) > 1: # Multiple pieces can move there, need more disambiguation return False else: return False # Full notation (e.g., "e2e4") if len(move_str) < 4: return False from_file = ord(move_str[0]) - ord('a') from_rank = int(move_str[1]) - 1 to_file = ord(move_str[2]) - ord('a') to_rank = int(move_str[3]) - 1 if not (0 <= from_file < 8 and 0 <= from_rank < 8 and 0 <= to_file < 8 and 0 <= to_rank < 8): return False from_sq = Square.from_coords(from_file, from_rank) to_sq = Square.from_coords(to_file, to_rank) promotion = None if len(move_str) == 5: promo_char = move_str[4] promo_map = {'q': PieceType.QUEEN, 'r': PieceType.ROOK, 'b': PieceType.BISHOP, 'n': PieceType.KNIGHT} promotion = promo_map.get(promo_char.lower()) move = Move(from_sq, to_sq, promotion) legal_moves = self.board.generate_legal_moves() if move in legal_moves: return self.board.make_move(move) except: pass return False def print_board(self): print(" +---+---+---+---+---+---+---+---+") for rank in range(7, -1, -1): line = f"{rank + 1} |" for file in range(8): sq = Square.from_coords(file, rank) piece = self.board.pieces.get(sq) if piece: piece_type, color = piece symbols = { (PieceType.PAWN, Color.WHITE): '♙', (PieceType.PAWN, Color.BLACK): '♟', (PieceType.KNIGHT, Color.WHITE): '♘', (PieceType.KNIGHT, Color.BLACK): '♞', (PieceType.BISHOP, Color.WHITE): '♗', (PieceType.BISHOP, Color.BLACK): '♝', (PieceType.ROOK, Color.WHITE): '♖', (PieceType.ROOK, Color.BLACK): '♜', (PieceType.QUEEN, Color.WHITE): '♕', (PieceType.QUEEN, Color.BLACK): '♛', (PieceType.KING, Color.WHITE): '♔', (PieceType.KING, Color.BLACK): '♚' } line += f" {symbols[(piece_type, color)]} |" else: line += " · |" print(line) print(" +---+---+---+---+---+---+---+---+") print(" a b c d e f g h") def get_pgn(self): if not self.board.move_list: return "" result = [] for i in range(0, len(self.board.move_list), 2): move_num = (i // 2) + 1 white_move = self.board.move_list[i] black_move = self.board.move_list[i+1] if i+1 < len(self.board.move_list) else "" result.append(f"{move_num}. {white_move} {black_move}".strip()) return " ".join(result) def run_cli(self): print("Stackfish Chess Engine") print("Commands: board, move , go [d= | t=