engine/move_ordering.py

"""
Move Ordering for Nexus-Core
Simplified but effective heuristics

Research:
- Schaeffer (1989) - History heuristic
- Akl & Newborn (1977) - Killer moves
"""

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


class MoveOrderer:
    """Move ordering with killer + history heuristics"""
    
    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 structures"""
        
        # Killer moves (2 per depth)
        self.killer_moves: Dict[int, List[Optional[chess.Move]]] = {}
        self.max_killers = 2
        
        # History table [from_square][to_square]
        self.history = np.zeros((64, 64), dtype=np.int32)
        
        # Counter moves
        self.counter_moves: Dict[chess.Move, Optional[chess.Move]] = {}
        
        # Stats
        self.killer_hits = 0
        self.history_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 pruning
        
        Priority:
        1. TT move
        2. Winning captures (MVV-LVA)
        3. Killer moves
        4. Counter moves
        5. History heuristic
        6. Quiet moves
        """
        
        scored_moves = []
        
        for move in moves:
            score = 0
            
            # TT move (highest priority)
            if tt_move and move == tt_move:
                score += 1000000
            
            # Captures
            elif board.is_capture(move):
                score += self._score_capture(board, move)
            
            # Quiet moves
            else:
                # Killer moves
                if self._is_killer_move(move, depth):
                    score += 9000
                    self.killer_hits += 1
                
                # Counter moves
                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
                
                # Checks
                board.push(move)
                if board.is_check():
                    score += 6000
                board.pop()
                
                # Castling
                if board.is_castling(move):
                    score += 3000
                
                # Center control
                center = [chess.D4, chess.D5, chess.E4, chess.E5]
                if move.to_square in center:
                    score += 50
            
            scored_moves.append((score, move))
        
        # Sort 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:
        """MVV-LVA capture scoring"""
        
        captured = board.piece_at(move.to_square)
        attacker = board.piece_at(move.from_square)
        
        if not captured or not attacker:
            return 0
        
        victim_value = self.PIECE_VALUES.get(captured.piece_type, 0)
        attacker_value = self.PIECE_VALUES.get(attacker.piece_type, 1)
        
        # MVV-LVA formula
        mvv_lva = (victim_value * 10 - attacker_value) * 100
        
        # En passant bonus
        if board.is_en_passant(move):
            mvv_lva += 10500
        
        # Penalty for hanging captures
        if board.is_attacked_by(not board.turn, move.to_square):
            if victim_value < attacker_value:
                mvv_lva -= 5000
        
        return mvv_lva
    
    def _is_killer_move(self, move: chess.Move, depth: int) -> bool:
        """Check if killer move"""
        killers = self.killer_moves.get(depth, [])
        return move in killers
    
    def update_killer_move(self, move: chess.Move, depth: int):
        """Update killer moves"""
        if depth not in self.killer_moves:
            self.killer_moves[depth] = []
        
        killers = self.killer_moves[depth]
        
        if move not in killers:
            killers.insert(0, move)
            self.killer_moves[depth] = killers[:self.max_killers]
    
    def update_history(self, move: chess.Move, depth: int, success: bool):
        """Update history heuristic"""
        if success:
            bonus = depth * depth
            self.history[move.from_square, move.to_square] += bonus
            self.history_hits += 1
        else:
            self.history[move.from_square, move.to_square] -= 1
        
        # Clip 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"""
        self.counter_moves[previous_move] = refutation
    
    def clear_history(self):
        """Clear history"""
        self.history.fill(0)
        self.killer_moves.clear()
        self.killer_hits = 0
        self.history_hits = 0
    
    def age_history(self, factor: float = 0.9):
        """Age history table"""
        self.history = (self.history * factor).astype(np.int32)
    
    def get_stats(self) -> Dict:
        """Get 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)
        }