A- und B-Strategie

A- und B-Strategie sind Begriffe aus der Programmierung von Strategiespielen, insbesondere dem Computerschach.

Beschreibung

Ein Programm zum Spielen eines Strategiespiels betrachtet üblicherweise einen Suchbaum, der ein Teil des Spielbaums ist.

A-Strategie bezeichnet nach Claude Shannon ein Verfahren, welches zur Bestimmung des besten Zuges alle möglichen Kombinationen von Zügen und Gegenzügen durchrechnet, bis zu einer bestimmten Tiefe (Zahl der aufeinanderfolgenden Züge), die durch Rechenleistung und verfügbare Zeit begrenzt wird. Die erreichten Stellungen werden heuristisch bewertet, und die Züge, die dazu geführt haben, werden nach dem Minimax-Prinzip bewertet. Die A-Strategie bezeichnet man auch als Brute-Force-Methode.

Im Gegensatz zur A-Strategie spielt ein Programm gemäß der B-Strategie, wenn es nur plausible – und nicht alle – Zugfolgen bei der Analyse einer Stellung durchsucht. Die Züge werden heuristisch bewertet, und nur solche mit hohem Wert werden in den Suchbaum aufgenommen. Die B-Strategie wird mitunter als Versuch verstanden, den menschlichen Denkprozess bei der Analyse von Varianten nachzubilden. Der Mensch berechnet auch nicht alle in einer Stellung legalen Züge, sondern erkennt bestimmte Merkmale der Stellung und wählt dann Züge zur genaueren Betrachtung aus, die im Hinblick auf die Stellungsmerkmale aussichtsreich sind.

Weil die Zahl der Varianten mit der Tiefe langsamer wächst als bei der A-Strategie, können die Varianten entsprechend bis zu einer größeren Tiefe berechnet werden. Dadurch kann das Programm taktische Kombinationen erkennen, die jenseits des Horizonts der A-Strategie liegen. Dafür übersieht es aber manchmal eine Wendung, indem es einen guten Zug niedrig bewertet und dadurch von vornherein aus dem Suchbaum ausschließt.

Der erste Versuch, ein Schachprogramm nach der B-Strategie zu schreiben, wurde 1955 bis 1958 von Allen Newell, John Shaw und Herbert A. Simon unternommen. Er schlug praktisch fehl, und man begann zu verstehen, dass die Realisierung eines solchen Programms weit schwieriger ist, als man zunächst angenommen hatte. Moderne Schachprogramme verwenden überwiegend modifizierte Formen der A-Strategie, die einzelne aussichtsreiche oder taktisch kritische Varianten tiefer als andere verfolgen.

Anders als im Computerschach stoßen beim Brettspiel Go die Brute-Force-Methoden an ihre Grenzen. Bei den früheren Go-Programmen wurde daher überwiegend mit der B-Strategie gearbeitet. Heutige Go-Programme nutzen hingegen wieder andere Ansätze, vor allem eine randomisierte Baumsuche (Monte-Carlo Tree Search).

Literatur

• Edmund Bruns: Das Schachspiel als Phänomen der Kulturgeschichte des 19. und 20. Jahrhunderts. LIT Verlag, Münster 2003, ISBN 3-8258-6546-0, S. 307–308 (eingeschränkte Vorschau in der Google-Buchsuche).