Branching Factor

Der Branching Factor (Verzweigungsfaktor) ist ein Maß für die Komplexität eines Spiels oder eines Entscheidungsproblems. Er gibt an, wie viele mögliche nächste Züge oder Entscheidungen es aus einer durchschnittlichen Position gibt.

Im Schach liegt der Branching Factor bei etwa 35. Das heißt, ein Computer muss für jeden Blick in die Zukunft 35 Möglichkeiten prüfen, dann für jeden dieser Züge wieder 35 Antworten des Gegners, und so weiter. Dies führt zu einer 'kombinatorischen Explosion', die es unmöglich macht, alles durchzurechnen. Im asiatischen Brettspiel Go beträgt der Faktor sogar ca. 250, was der Grund war, warum klassische KI dort lange scheiterte. Moderne KI (wie AlphaGo) nutzt neuronale Netze, um diesen Suchraum zu beschneiden ('Pruning'), indem sie intuitiv nur die vielversprechendsten Zweige untersucht, ähnlich wie ein Mensch.