Compressed Game Solving

Das Kapitel vertieft sich in die historische Evolution der Spiellösungstechniken und geht auf frühe theoretische Grundlagen und bahnbrechende Arbeiten zurück, die den Grundstein für moderne Algorithmen legten. Es beleuchtet die Herausforderungen, die von den riesigen staatlichen Räumen komplexer Spiele und den innovativen Strategien ausgehen, die entwickelt wurden, um diese Hindernisse zu überwinden. Der Kernbeitrag des Kapitels ist die Einführung komprimierter Spiellösungen mittels deterministischer endlicher Automaten (DFAs), die eine sublineare Raumnutzung und effiziente Zuggenerierung ermöglichen. Dieser Ansatz wird durch die erfolgreiche Lösung verschiedener Spielgrößen demonstriert, einschließlich neuer Brettkonfigurationen für das Spiel Breakthrough. Das Kapitel diskutiert auch die möglichen Anwendungen dieser Methode auf andere Spiele und die Integration von Fachwissen, um die Effizienz weiter zu steigern. Anhand detaillierter empirischer Ergebnisse und Vergleiche mit bestehenden Methoden bietet das Kapitel einen umfassenden Überblick über die Fortschritte und zukünftigen Richtungen bei den Lösungsalgorithmen.