Inhalt
Aktueller Ordner:
chessteg_modular/enginesearch.py
"""
Chessteg Search Module - KORRIGIERTE VERSION MIT DEBUG
Vollständiger Alpha-Beta Suchalgorithmus mit Quiescence Search
"""
import math
import time
import copy
from typing import List, Dict, Any, Optional, Tuple
class SearchAlgorithm:
"""
Vollständiger Alpha-Beta Suchalgorithmus mit erweiterten Features
"""
# Konstanten für Alpha-Beta
MATE_SCORE = 20000000
MAX_DEPTH = 30
# Figuren-Typen und Werte
PAWN = 1
KNIGHT = 4
BISHOP = 3
ROOK = 5
QUEEN = 9
KING = 99
# Figurenwerte für Move Ordering
PIECE_VALUES = {
PAWN: 100,
KNIGHT: 320,
BISHOP: 330,
ROOK: 500,
QUEEN: 900,
KING: 20000
}
def __init__(self, engine):
self.engine = engine
self.ai_settings = {
'search_depth': 3,
'extended_evaluation': True,
'quiescence_search': False, # 🚨 KORREKTUR: Erstmal deaktivieren für Stabilität
'quiescence_depth': 2,
'timeout_ms': 5000 # 🚨 KORREKTUR: Mehr Zeit für Debugging
}
# Suchstatistiken
self.node_counter = 0
self.move_counter = 0
self.calculation_start_time = 0
self.transposition_table = {}
# Move Ordering Cache
self.move_ordering_cache = {}
def computer_move(self) -> Optional[Dict[str, Any]]:
"""
Berechnet den besten Zug für den Computer mit vollständiger Alpha-Beta-Suche
"""
print("=== KI MOVE CALCULATION STARTED ===")
start_time = time.time()
self.calculation_start_time = start_time
self.node_counter = 0
self.move_counter = 0
self.transposition_table = {}
current_color = 1 if self.engine.white_turn else -1
# 1. Alle legalen Züge generieren
all_moves = self.engine.generate_all_moves(current_color)
if not all_moves:
print("❌ Keine legalen Züge gefunden - Matt oder Patt?")
print(f"Checkmate: {self.engine.checkmate}, Stalemate: {self.engine.stalemate}")
print(f"King in check: {self.engine.is_king_in_check(current_color)}")
return None
print(f"🔍 {len(all_moves)} legale Züge verfügbar für {'Weiß' if current_color == 1 else 'Schwarz'}")
# 2. Züge sortieren (Move Ordering)
sorted_moves = self._order_moves(all_moves)
best_move = None
best_score = -self.MATE_SCORE - 1
# 3. Iterative Deepening
depth = self.ai_settings['search_depth']
# 4. Alpha-Beta-Suche starten
alpha = -self.MATE_SCORE - 1
beta = self.MATE_SCORE + 1
print(f"🎯 Starte Alpha-Beta-Suche mit Tiefe {depth}, {len(sorted_moves)} Zügen")
for i, move in enumerate(sorted_moves):
self.move_counter += 1
# Zug ausführen (transaktional)
if not self.engine.make_move(move):
print(f"❌ Zug {i+1}/{len(sorted_moves)}: {self._move_to_notation(move)} konnte nicht ausgeführt werden")
continue
# Rufe Alpha-Beta für die nächste Tiefe auf
score = -self._alpha_beta(depth - 1, -beta, -alpha)
# Zug rückgängig machen
self.engine.undo_move()
print(f"🔍 Zug {i+1}/{len(sorted_moves)}: {self._move_to_notation(move)} -> Score: {score}")
# Timeout-Check
if self._check_timeout():
print(f"⏰ Timeout erreicht nach {self.move_counter} Zügen")
break
# Alpha-Beta Update
if score > best_score:
best_score = score
best_move = move
print(f"🏆 NEUER BESTER ZUG: {self._move_to_notation(move)} mit Score {score}")
if score > alpha:
alpha = score
# Beta-Cutoff
if alpha >= beta:
print(f"✂️ Beta-Cutoff bei Zug {i+1}")
break
end_time = time.time()
duration = end_time - start_time
print(f"=== KI MOVE CALCULATION FINISHED ===")
print(f"Best Score: {best_score}")
print(f"Best Move: {self._move_to_notation(best_move) if best_move else 'None'}")
print(f"Search Depth: {depth}")
print(f"Nodes Visited: {self.node_counter}")
print(f"Moves Evaluated: {self.move_counter}")
print(f"Calculation Time: {duration:.2f}s")
print(f"NPS: {self.node_counter / duration if duration > 0 else 0:.0f}")
if best_move:
print(f"✅ KI hat Zug gefunden: {self._move_to_notation(best_move)}")
else:
print("❌ KI konnte keinen Zug finden")
return best_move
def _alpha_beta(self, depth: int, alpha: int, beta: int) -> int:
"""
Der rekursive Alpha-Beta-Suchalgorithmus.
"""
self.node_counter += 1
# Timeout-Check
if self._check_timeout():
return 0
# 1. Prüfe auf Spielende (Matt/Patt)
if self.engine.is_game_over():
score = self._mate_or_stalemate_score(depth)
# 🚨 DEBUG: Zeige Matt/Patt-Erkennung
if abs(score) > 1000000:
print(f" 🏁 Terminalstellung: Score {score} (Tiefe {depth})")
return score
# 2. Basisfall: Tiefe erreicht
if depth <= 0:
score = self.engine.evaluator.evaluate_position()
# 🚨 DEBUG: Zeige erste Bewertungen
if self.node_counter < 10:
print(f" 📊 Blattevaluation: {score} (Tiefe {depth})")
return score
# 3. Zuggenerierung
current_color = 1 if self.engine.white_turn else -1
all_moves = self.engine.generate_all_moves(current_color)
if not all_moves:
score = self._mate_or_stalemate_score(depth)
print(f" ❌ Keine Züge in Tiefe {depth}: Score {score}")
return score
# 4. Move Ordering
sorted_moves = self._order_moves(all_moves)
# 5. Haupt-Alpha-Beta-Loop
best_score = -self.MATE_SCORE - 1
for move in sorted_moves:
# 🚨 DEBUG: Zeige ersten paar Züge
if self.node_counter < 5 and depth == self.ai_settings['search_depth'] - 1:
print(f" 🔍 Prüfe Zug: {self._move_to_notation(move)} in Tiefe {depth}")
if not self.engine.make_move(move):
continue
# Rekursiver Aufruf
score = -self._alpha_beta(depth - 1, -beta, -alpha)
self.engine.undo_move()
# Alpha-Beta Update
if score > best_score:
best_score = score
if score > alpha:
alpha = score
if alpha >= beta:
break
return best_score
def _mate_or_stalemate_score(self, depth: int) -> int:
"""Berechnet den Score bei Matt oder Patt - KORRIGIERTE VERSION"""
current_color = 1 if self.engine.white_turn else -1
# Prüfe auf Schach
if self.engine.is_king_in_check(current_color):
# Matt - sehr schlecht für den aktuellen Spieler
mate_score = -self.MATE_SCORE + (self.MAX_DEPTH - depth)
print(f" ♟️ MATT erkannt! Score: {mate_score} (Tiefe {depth})")
return mate_score
else:
# Patt - Unentschieden
print(f" 🤝 PATT erkannt! Score: 0 (Tiefe {depth})")
return 0
def _check_timeout(self) -> bool:
"""Prüft, ob das Timeout erreicht ist."""
if self.ai_settings['timeout_ms'] <= 0:
return False
elapsed_time_ms = (time.time() - self.calculation_start_time) * 1000
return elapsed_time_ms >= self.ai_settings['timeout_ms']
def _order_moves(self, moves: List[Dict[str, Any]], quiescence: bool = False) -> List[Dict[str, Any]]:
"""
Sortiert Züge für bessere Alpha-Beta-Performance.
"""
scored_moves = []
for move in moves:
score = 0
# Schlagzüge priorisieren
if move.get('is_capture') or move.get('special_type') == 'en_passant':
# MVV-LVA Scoring
if move.get('special_type') == 'en_passant':
victim_value = self.PIECE_VALUES[1] # Bauer
else:
victim = self.engine.get_piece_at(move['to_pos'])
victim_value = self.PIECE_VALUES.get(victim['type'], 0) if victim else 0
attacker_value = self.PIECE_VALUES.get(move['piece']['type'], 0)
score += 10 * victim_value - attacker_value
score += 10000 # Hoher Bonus für Schläge
# Umwandlungen priorisieren
elif move.get('promotion_piece'):
promotion_value = self.PIECE_VALUES.get(move['promotion_piece'], 0)
score += 900 + promotion_value
scored_moves.append((score, move))
# Absteigend sortieren nach Score
scored_moves.sort(key=lambda x: x[0], reverse=True)
return [move for score, move in scored_moves]
def _get_move_key(self, move: Dict[str, Any]) -> Tuple[int, int, int]:
"""Erzeugt einen eindeutigen Schlüssel für einen Zug."""
promo = move.get('promotion_type', 0)
return (move['from_pos'], move['to_pos'], promo)
def _move_to_notation(self, move: Dict[str, Any]) -> str:
"""Konvertiert Zug zu algebraischer Notation"""
from_pos = self._position_to_notation(move['from_pos'])
to_pos = self._position_to_notation(move['to_pos'])
return f"{from_pos}{to_pos}"
def _position_to_notation(self, position: int) -> str:
"""Konvertiert interne Position zu algebraischer Notation"""
files = ['', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '']
row = position // 10
file = position % 10
return f"{files[file]}{row - 1}"
# Test des Search-Algorithmus
if __name__ == "__main__":
print("Testing SearchAlgorithm...")
# Benötigt alle Engine-Komponenten für einen vollständigen Test
try:
from core import ChesstegEngine
engine = ChesstegEngine()
searcher = SearchAlgorithm(engine)
# Test: Standardstellung, Tiefe 3
print(f"\n--- Test: Startstellung, Tiefe {searcher.ai_settings['search_depth']} ---")
best_move = searcher.computer_move()
if best_move:
print(f"Bester Zug gefunden: {searcher._move_to_notation(best_move)}")
# Führe den Zug aus
engine.make_move(best_move)
# Test: Nach einem Zug, Tiefe 3
print(f"\n--- Test: Nach erstem Zug, Tiefe {searcher.ai_settings['search_depth']} ---")
best_move_2 = searcher.computer_move()
if best_move_2:
print(f"Bester Zug für Schwarz gefunden: {searcher._move_to_notation(best_move_2)}")
else:
print("Kein Zug für Schwarz gefunden.")
else:
print("Kein Zug für Weiß gefunden.")
except ImportError as e:
print(f"ERROR: Full test requires all engine components (core, __init__, etc.). Failed to import: {e}")