Brute-Force-Methode

Brute-Force-Methode

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 expotentiell 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 expotentielle Wachstum zu riesigen Verbesserungen führen kann. Eine sehr übliche Verbesserung ist das Alpha-Beta-Verfahren: 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 ist, ab einer gewissen Tiefe nur noch "forcierende" Züge zu betrachten. Im Schach wären dies etwa Schachgebote oder Schlagzüge.

In dem strategischen Spiel Go ist die Brute-Force-Methode unabhängig von der zukünftigen Entwicklung der Hardware zum Scheitern verurteilt.