Spielbaumsuche

Spielbaumsuche ist ein naiver Ansatz. Hier werden zu einem Problem alle möglichen Handlungsverläufe berechnet, um dann eine Handlung auszusuchen, die zu einem, im Sinne eines Ziels, gewinnbringenden Handlungsverlauf führt. Die hierbei entstehenden Datenmengen werden zur Ordnung und dem damit möglichen Durchsuchen in Spielbäumen gespeichert. Diese Bäume sind eine in der Informatik weit verbreitete Struktur. Sie bestehen aus Knoten und Zweigen, wobei jeweils zwei Knoten durch einen Zweig verbunden sind. Bei Spielbäumen stellen die Knoten sogenannte Spielsituationen im Handlungsverlauf (Spiel) und Zweige die Handlungen (Spielzüge) der sogenannten Spielpartner dar. Diese Bäume werden nun nach einem Pfad durchsucht, der zu einem gewünschten Ziel führt.

Da diese Spielbäume für Spiele, wie z.zum Beispiel Schach, schon sehr großwerden, will man sich gar nicht versuchen zu überlegen, wie großein solcher Baum zum Beispiel bei einer Konversation sein könnte. Daher können immer nur Teile eines solchen Baumes durchsucht werden. Dafür werden Algorithmen wie Minimax und seine Verbesserungen verwendet. Um nur einen Teil des Baumes betrachten zu können, wird eine Bewertungsfunktion verwendet. Diese errechnet aus einer Spielsituation, ob diese für einen Spieler vorteilhaft ist oder nicht. Der Minimax-Algorithmus erstellt nun ausgehend von der aktuellen Spielsituation einen Spielbaum bis zu einer bestimmten Suchtiefe oder auch Horizont. Die jeweils tiefsten Knoten werden mit der Bewertungsfunktion bewertet. Dann werden diese Bewertungen zu ihrem jeweils höheren Knoten (Vaterknoten) weitergereicht. Allerdings gibt es verschiedene Ebenen. Es gibt Knoten an denen Spieler A und Knoten an denen Spieler B an der Reihe ist. Da die beide gewinnen wollen, versuchen sie jeweils die Bewertung, welche die Gewinnchance eines der Spieler beschreibt, entweder zu maximieren oder zu minimieren. Somit gibt es Ebenen an denen dem Vaterknoten die höchste Bewertung seiner Kinderknoten hochgereicht wird und Ebenen in denen die niedrigste Bewertung hochgereicht wird. Ausgehend von der Ausgangssituation kann nun der Spielzug, der zum Knoten mit der für diesen Spieler besten Bewertung führt, gewählt werden [WP92].

Das Problem bei dieser Methode ist allerdings, dass man eine sehr gute Bewertungsfunktion finden muss und sie davon ausgeht, dass der Gegner immer perfekt spielt und die gleiche Bewertung verwendet. Somit können Schwächen des Gegners nicht ausgenutzt werden und es werden keine Risiken eingegangen um einen höheren oder schnelleren Gewinn zu erzielen.