Vertakkingsfactor

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 heeft een knoop in de spelboom halverwege het spel gemiddeld een vertakkingsfactor van 35. 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 10² = 100 knopen) met ook weer 10 kinderen (10³ = 1000 knopen), enzovoort. Meer algemeen bestaat een boom met diepte d en vertakkingsfactor b uit b^d 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