Gelöste Spiele

Ein gelöstes Spiel ist ein Spiel, dessen Ausgang (Sieg, Niederlage oder Unentschieden) von jeder Stellung aus korrekt vorhergesagt werden kann, vorausgesetzt, alle Parteien spielen optimal. Dieses Konzept wird meist auf Strategiespiele angewendet, insbesondere auf solche mit perfekter Information und ohne Zufallselemente. Die Lösung solcher Spiele beruht meist auf Kombinatorik und Spieltheorie oder Brute-Force Lösungen durch Computer.

Ein zufallsfreies Zwei-Personen-Spiel mit perfekter Information kann in unterschiedlicher Weise gelöst werden:

• Sehr schwach gelöst (engl. ultra weakly solved) ist ein Spiel, wenn man für die Startposition des Spieles dasjenige Spielergebnis bestimmen kann, das jeder der beiden Spieler unabhängig von der Spielweise seines Gegners mindestens erzwingen kann. Ein diesbezüglicher Nachweis muss über die dafür notwendigen Spielweisen keine Aussage machen.
• Schwach gelöst ist ein Spiel, wenn darüber hinaus ein praktisch realisierbarer Algorithmus angegeben werden kann, mit dem die beidseitig optimalen Spielweisen ausgehend von der Startposition des Spiels bestimmt werden können.
• Stark gelöst ist ein Spiel, wenn ein allgemeiner, praktisch realisierbarer Algorithmus existiert, mit dem für jede Position ein optimaler Zug berechnet werden kann. Im Unterschied zu schwach gelösten Spielen muss dieser Algorithmus auch für solche Positionen funktionieren, die ausgehend von der Ausgangsposition nur bei fehlerhafter Spielweise vorkommen.

Wichtig ist die Anforderung eines praktisch (auf einem Computer) realisierbaren Algorithmus, da mit dem Minimax-Algorithmus stets ein allgemeines Verfahren existiert, mit dem theoretisch für jede Position eines endlichen Zwei-Personen-Spiels mit vollständiger Information ein optimaler Zug berechnet werden kann.

1. ↑ L.V. Allis: Searching for solutions in games and artificial intelligence. Maastricht University, 1994, doi:10.26481/dis.19940923la (maastrichtuniversity.nl [abgerufen am 8. August 2025]). 
2. ↑ H.Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck: Games solved: Now and in the future. In: Artificial Intelligence. Band 134, Nr. 1-2, Januar 2002, S. 277–311, doi:10.1016/S0004-3702(01)00152-7 (elsevier.com [abgerufen am 8. August 2025]).