Sequentielle und verteilte Algorithmen zur selektiven Auswertung von Min/Max-Bäumen

点击翻译按钮获取中文摘要

In diesem Forschungsvorhaben sollen sequentielle und verteilte Verfahren zur Auswertung von Min/Max - Graphen entwickelt werden. In vielen Anwendungen ist es nicht möglich eine Entscheidung zu treffen, die auf der vollständigen Auswertung des vorliegenden Min/Max-Graphen beruht. Für viele dieser Min/Max - Graphen ist es möglich, mit tieferer und geschickterer Vorausschau die Qualität einer Entscheidung zu verbessern. Selektive Suchen können hier helfen, relevante Varianten mit tieferer Vorausschau und irrelevante Varianten mit geringerem Aufwand zu durchsuchen. Die Nullmoveheuristik ist die in Schachprogrammen am weitesten verbreitete, anwendungsunabhängige Beschneidungsheuristik für Spielbäume. Im folgenden Antragszeitraum soll untersucht werden, inwieweit sich das in diesem Schwerpunkt erarbeitete CCNS Verfahren mit der sogenannten Nullmoveheuristik kombinieren läßt. Außerdem soll der parallele CCNS-Algorithmus in einer Library eingebunden werden. Desweiteren wurde der FHR-Algorithmus, ein selektives Tiefensuchverfahren für die Spielbaumsuche, auf die Cray T3E portiert. Die erzielte Effizienz war ebensogut, wie die der von uns entwickelten Parallelisierung des nur wenig selektiven Alphabeta-Algorithmus. Die Methoden der Parallelisierung selektiver Tiefensuchverfahren sollen im nächsten Projektjahr auf das klassische Problem der Erfüllbarkeit von quantifizierten Boolschen Formeln übertragen werden. Mit Hilfe der für die sequentiellen Verfahren entworfenen Techniken soll ein Strategiefindungsproblem aus dem Bereich des Szenario Managements gelöst werden.