Solving Linear NoGo with Combinatorial Game Theory

Dieses Kapitel vertieft die strategische Tiefe von Linear NoGo, einer Variante des Spielklassikers Go, in dem Capturing und Selbstmordzüge verboten sind und das Spiel endet, wenn ein Spieler keinen Zug ausführen kann. Die Analyse nutzt die kombinatorische Spieltheorie (CGT), um das Brett als Summe unabhängiger Teilspiele darzustellen, was eine raffinierte Vereinfachung, Zerlegung und Reduktionstechniken des Brettes ermöglicht. Das Kapitel stellt CGTSolver vor, einen Negamax-basierten Solver, der mit CGT-Konzepten erweitert wurde und bisherige hochmoderne Solver sowohl bei der Knotenanzahl als auch bei der Wanduhrzeit übertrifft. Eine vorab berechnete Datenbank reduzierter NoGo-Positionen bis zu 15 Leerpunkten wird aufgebaut, die eine effiziente Spiellösung ermöglicht und Einblicke in die Struktur reduzierter linearer NoGo-Positionen bietet. Das Kapitel behandelt auch die Implementierungsdetails von CGTSolver, einschließlich statischer Evaluierung, Zugbestellheuristik und einer globalen Umsetzungstabelle, die gemeinsam zu seiner überlegenen Leistung beitragen. Experimentelle Ergebnisse zeigen, dass CGTSolver in der Lage ist, Bretter bis zu 28 Punkte zu lösen, was frühere Ergebnisse bestätigt und erweitert. Das Kapitel schließt mit einem Vergleich zu CGSuite und skizziert zukünftige Arbeiten, was die Anwendbarkeit dieser Techniken auf andere kombinatorische Spiele nahelegt.