File size: 6,044 Bytes
de8be59 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 |
"""
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)
} |