engine/move_ordering.py

"""
Advanced Move Ordering Techniques
Critical for alpha-beta pruning efficiency

Research References:
- Stockfish move ordering (2023) - History heuristic + killer moves
- Fruit 2.1 - MVV-LVA and late move reductions
- Crafty - History tables and counter moves

Good move ordering can reduce search tree by 10-100x!
"""

import chess
from typing import List, Optional, Dict, Tuple
import numpy as np


class MoveOrderer:
    """
    Advanced move ordering system
    Combines multiple heuristics for optimal move ordering
    """
    
    # Piece values for MVV-LVA (victim values)
    PIECE_VALUES = {
        chess.PAWN: 100,
        chess.KNIGHT: 320,
        chess.BISHOP: 330,
        chess.ROOK: 500,
        chess.QUEEN: 900,
        chess.KING: 20000
    }
    
    def __init__(self):
        """Initialize move ordering data structures"""
        
        # Killer moves (quiet moves that caused beta cutoff)
        # killer_moves[depth] = [move1, move2]
        self.killer_moves: Dict[int, List[Optional[chess.Move]]] = {}
        self.max_killers = 2  # Store top 2 killer moves per depth
        
        # History heuristic (move success rates)
        # history[from_square][to_square] = score
        self.history = np.zeros((64, 64), dtype=np.int32)
        
        # Counter moves (refutation table)
        # counter_moves[prev_move] = best_response
        self.counter_moves: Dict[chess.Move, Optional[chess.Move]] = {}
        
        # Statistics
        self.history_hits = 0
        self.killer_hits = 0
    
    def order_moves(
        self,
        board: chess.Board,
        moves: List[chess.Move],
        depth: int,
        tt_move: Optional[chess.Move] = None,
        previous_move: Optional[chess.Move] = None
    ) -> List[chess.Move]:
        """
        Order moves for optimal alpha-beta pruning
        
        Priority order (research-based):
        1. TT move (from transposition table)
        2. Winning captures (MVV-LVA)
        3. Killer moves
        4. Counter moves
        5. History heuristic
        6. Losing captures
        7. Quiet moves
        
        Args:
            board: Current position
            moves: Legal moves to order
            depth: Current search depth
            tt_move: Best move from transposition table
            previous_move: Opponent's last move
        
        Returns:
            Ordered list of moves
        """
        scored_moves = []
        
        for move in moves:
            score = 0
            
            # ========== PRIORITY 1: TT Move ==========
            if tt_move and move == tt_move:
                score += 1000000
            
            # ========== PRIORITY 2: Captures (MVV-LVA) ==========
            elif board.is_capture(move):
                score += self._score_capture(board, move)
            
            # ========== PRIORITY 3-7: Quiet Moves ==========
            else:
                # Check if it's a killer move
                if self._is_killer_move(move, depth):
                    score += 9000
                    self.killer_hits += 1
                
                # Counter move bonus
                if previous_move and move == self.counter_moves.get(previous_move):
                    score += 8000
                
                # History heuristic
                history_score = self.history[move.from_square, move.to_square]
                score += min(history_score, 7000)
                
                # Promotions
                if move.promotion == chess.QUEEN:
                    score += 10000
                elif move.promotion in [chess.KNIGHT, chess.ROOK, chess.BISHOP]:
                    score += 5000
                
                # Checks
                board.push(move)
                if board.is_check():
                    score += 6000
                board.pop()
                
                # Castling
                if board.is_castling(move):
                    score += 3000
                
                # Positional bonuses
                score += self._score_positional(board, move)
            
            scored_moves.append((score, move))
        
        # Sort by score (descending)
        scored_moves.sort(key=lambda x: x[0], reverse=True)
        
        return [move for _, move in scored_moves]
    
    def _score_capture(self, board: chess.Board, move: chess.Move) -> int:
        """
        Score capture using MVV-LVA (Most Valuable Victim - Least Valuable Attacker)
        Enhanced with SEE (Static Exchange Evaluation)
        """
        captured_piece = board.piece_at(move.to_square)
        moving_piece = board.piece_at(move.from_square)
        
        if not captured_piece or not moving_piece:
            return 0
        
        victim_value = self.PIECE_VALUES.get(captured_piece.piece_type, 0)
        attacker_value = self.PIECE_VALUES.get(moving_piece.piece_type, 1)
        
        # MVV-LVA base score
        mvv_lva_score = (victim_value * 10 - attacker_value) * 100
        
        # Bonus for en passant
        if board.is_en_passant(move):
            mvv_lva_score += 10500
        
        # Penalty for hanging pieces (simplified SEE)
        # Check if capture square is defended
        if board.is_attacked_by(not board.turn, move.to_square):
            # Losing capture if victim < attacker
            if victim_value < attacker_value:
                mvv_lva_score -= 5000  # Deprioritize losing captures
        
        return mvv_lva_score
    
    def _score_positional(self, board: chess.Board, move: chess.Move) -> int:
        """
        Positional scoring for quiet moves
        Based on Stockfish evaluation terms
        """
        score = 0
        
        piece = board.piece_at(move.from_square)
        if not piece:
            return 0
        
        # Center control (e4, d4, e5, d5)
        center_squares = [chess.E4, chess.D4, chess.E5, chess.D5]
        if move.to_square in center_squares:
            score += 50
        
        # Extended center
        extended_center = [
            chess.C3, chess.D3, chess.E3, chess.F3,
            chess.C4, chess.F4,
            chess.C5, chess.F5,
            chess.C6, chess.D6, chess.E6, chess.F6
        ]
        if move.to_square in extended_center:
            score += 20
        
        # Piece development (from back rank)
        if piece.piece_type in [chess.KNIGHT, chess.BISHOP]:
            from_rank = move.from_square // 8
            if from_rank in [0, 7]:  # Back rank
                score += 30
        
        # Knight outposts (protected squares in enemy territory)
        if piece.piece_type == chess.KNIGHT:
            to_rank = move.to_square // 8
            if (board.turn == chess.WHITE and to_rank >= 4) or \
               (board.turn == chess.BLACK and to_rank <= 3):
                # Check if protected by pawn
                board.push(move)
                if board.is_attacked_by(board.turn, move.to_square):
                    score += 40
                board.pop()
        
        return score
    
    def _is_killer_move(self, move: chess.Move, depth: int) -> bool:
        """Check if move is a killer move at this depth"""
        killers = self.killer_moves.get(depth, [])
        return move in killers
    
    def update_killer_move(self, move: chess.Move, depth: int):
        """
        Update killer moves for this depth
        Killer moves are quiet moves that caused beta cutoff
        """
        if depth not in self.killer_moves:
            self.killer_moves[depth] = []
        
        killers = self.killer_moves[depth]
        
        # Add move if not already in list
        if move not in killers:
            killers.insert(0, move)
            # Keep only top N killers
            self.killer_moves[depth] = killers[:self.max_killers]
    
    def update_history(self, move: chess.Move, depth: int, success: bool):
        """
        Update history heuristic
        
        Args:
            move: Move that was tried
            depth: Search depth
            success: True if move caused beta cutoff
        """
        if success:
            # Increase score (depth squared bonus for deeper searches)
            bonus = depth * depth
            self.history[move.from_square, move.to_square] += bonus
            self.history_hits += 1
        else:
            # Slight penalty for moves that failed low
            self.history[move.from_square, move.to_square] -= 1
        
        # Cap values to prevent overflow
        self.history = np.clip(self.history, -10000, 10000)
    
    def update_counter_move(self, previous_move: chess.Move, refutation: chess.Move):
        """
        Update counter move table
        Counter move = best response to opponent's last move
        """
        self.counter_moves[previous_move] = refutation
    
    def clear_history(self):
        """Clear history table (called at new search)"""
        self.history.fill(0)
        self.killer_moves.clear()
        self.history_hits = 0
        self.killer_hits = 0
    
    def age_history(self, factor: float = 0.9):
        """
        Age history table (reduce all values)
        Prevents old data from dominating
        """
        self.history = (self.history * factor).astype(np.int32)
    
    def get_stats(self) -> Dict:
        """Get move ordering statistics"""
        return {
            'killer_hits': self.killer_hits,
            'history_hits': self.history_hits,
            'history_max': int(np.max(self.history)),
            'killer_depths': len(self.killer_moves),
            'counter_moves': len(self.counter_moves)
        }