Facteur de branchement

Le facteur de branchement est le nombre d’enfants à chaque nœud, le plus profond . Si cette valeur n'est pas uniforme, un facteur de branchement moyen peut être calculé.

Par exemple, aux échecs, si un "nœud" est considéré comme une position légale, le facteur de branchement moyen h serait d'environ 35  , et une analyse statistique de plus de 2,5 millions de parties a révélé une moyenne de 31. Cela signifie qu’en moyenne, un joueur a environ 31 à 35 mouvements légaux à son tour à chaque tour. En comparaison, le facteur de branchement moyen du jeu Go est de 250.

Des facteurs de branchement élevés rendent très gourmands en puissance de calcul les algorithmes qui suivent de  façon systématique, toutes les branches à chaque nœud, en raison de l’augmentation exponentielle nombre de noeuds, conduisant à une explosion combinatoire.

Par exemple, si le facteur de branchement est 10, il y aura 10 nœuds à un niveau inférieur à la position actuelle, 10 2 (ou 100) nœuds à deux niveaux, 10 3 (ou 1 000) nœuds à trois niveaux, etc. . Plus le facteur de ramification est élevé, plus cette "exploitation" est rapide. Le facteur de ramification peut être réduit par un algorithme d'élagage.

Le facteur de branchement moyen peut être rapidement calculé en divisant le nombre de nœuds non racines (taille de l'arbre, moins un; ou nombre d'arêtes) divisé par le nombre de nœuds non feuilles.