Brute Force

aus Schachcomputer.info Wiki, der freien Schachcomputer-Wissensdatenbank
Wechseln zu: Navigation, Suche

Die Brute Force -Methode bzw. Methode der rohen Gewalt ist der Fachbegriff für eine Lösungsmethode schwerer Probleme aus dem Bereich der Informatik und der Spieltheorie, die auf dem Ausprobieren aller (oder zumindest eines erheblichen Teils der in Frage kommenden) Varianten beruht.

In der Spieltheorie bezeichnet man mit der Brute Force-Methode eine Strategie, in der der Variantenbaum bis zu einer gewissen Tiefe vollständig analysiert wird. Eine Bewertungsfunktion für jede der dabei auftretenden Stellungen dient dabei zur Entscheidungsfindung für den besten Zug.

Der Aufwand für die Brute Force-Methode wächst exponentiell mit der verwendeten Maximaltiefe; damit setzt die Hardware dieser Methode eine natürliche Grenze.

Die Brute Force-Methode kann mit den verschiedensten Methoden verfeinert werden, was durch das genannte exponentielle Wachstum zu erheblichen Verbesserungen führen kann. Eine sehr übliche Verbesserung ist die Alpha-Beta-Suche: ist ein Zug in einer bestimmten Tiefe durch einen gewissen Gegenzug widerlegt, dann ist es nutzlos, nach noch besseren Widerlegungen zu suchen.

Eine andere übliche Methode (Selektiv) ist, ab einer gewissen Tiefe nur noch „forcierende“ Züge zu betrachten. Im Schach wären dies etwa Schachgebote oder Schlagzüge.

Grundsätzlich rechnet der Computer Brute Force. Die meisten Programme arbeiten mittlerweile nach einer gemischten Methode.

Ein Beispiel: Das Programm ist auf Selektivität 4 eingestellt. Die ersten 4 Halbzüge werden Brute Force berechnet. Alle weiteren Züge werden dann selektiv berechnet.