Vertakkingsfactor

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een rood-zwart boom met vertakkingsfactor 2.

In de informatica en speltheorie is de vertakkingsfactor van een boomstructuur het aantal kinderen van een knoop. Als dit aantal niet voor alle kinderen hetzelfde is dan kan een gemiddelde vertakkingsfactor berekend worden.

In bijvoorbeeld schaken [1] heeft een knoop in de spelboom halverwege het spel gemiddeld een vertakkingsfactor van 35[2]. Elke knoop in de spelboom representeert een geldige toestand van het schaakbord en vanuit elke knoop kan de speler gemiddeld 35 geldige zetten doen.

Het uitputtend doorzoeken van de spelboom met brute force is vaak niet mogelijk naarmate de (gemiddelde) vertakkingsfactor groter wordt. Het aantal knopen groeit namelijk exponentieel (een combinatorische explosie) met elke laag van de boom. Als de vertakkingsfactor 10 is, dan heeft de wortel 10 kinderen, die elk ook weer 10 kinderen hebben (in totaal 102 = 100 knopen) met ook weer 10 kinderen (103 = 1000 knopen), enzovoort. Meer algemeen bestaat een boom met diepte d en vertakkingsfactor b uit bd knopen.

De gevolgen van deze combinatorische explosie kunnen beperkt worden door de boom op een zekere diepte af te kappen en niet dieper in de boom te zoeken. Een andere manier is het wegsnijden van delen van de boom waarvan bekend is dat die niet langer relevant zijn, bijvoorbeeld met alpha-beta pruning ('pruning' is 'snoei').

Bronnen, noten en/of referenties
  1. H.J. van den Herik - Computerschaak, schaakwereld en kunstmatige intelligentie, Academic Service, ISBN 90 62 33 093 2
  2. (en) Chess Programming Part IV: Basic Search, GameDev.net