imported>Megatherium am 27. Mai 2023 um 12:39 Uhr

2023-05-27T12:39:39Z

Neue Seite

'''A- und B-Strategie''' sind Begriffe aus der Programmierung von [[Strategiespiel]]en, insbesondere dem [[Computerschach]].

== Beschreibung ==

Ein Programm zum Spielen eines Strategiespiels betrachtet üblicherweise einen Suchbaum, der ein Teil des [[Extensivform eines Spiels|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 [[Heuristik|heuristisch]] bewertet, und die Züge, die dazu geführt haben, werden nach dem [[Minimax-Algorithmus|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 (Spiel)|Go]] die Brute-Force-Methoden an ihre Grenzen. Bei den früheren Go-Programmen wurde daher überwiegend mit der B-Strategie gearbeitet. Heutige [[Go (Spiel)#Computer-Go|Go-Programme]] nutzen hingegen wieder andere Ansätze, vor allem eine [[Randomisierter Algorithmus|randomisierte]] Baumsuche (Monte-Carlo Tree Search).

== Literatur ==
* {{Literatur
|Autor=Edmund Bruns
|Titel=Das Schachspiel als Phänomen der Kulturgeschichte des 19. und 20. Jahrhunderts
|Verlag=LIT Verlag
|Ort=Münster
|Datum=2003
|ISBN=3-8258-6546-0
|Seiten=307–308
|Online={{Google Buch |BuchID=iRk1WzH0WHEC |Seite=307}}}}

[[Kategorie:Computerschach]]
[[Kategorie:Go]]

A- und B-Strategie - Versionsgeschichte

imported>Megatherium am 27. Mai 2023 um 12:39 Uhr