Facteur de Ramification & Nombre de Nœuds
Un arbre de jeu modélise chaque séquence possible de coups à partir d'une position de départ. Chaque nœud représente un état du plateau. Chaque arête représente un coup légal. La structure de l'arbre détermine si la recherche reste réalisable.
Paramètres Clés
Facteur de ramification b : nombre de coups légaux disponibles à une position typique.
Profondeur d : nombre de demi-coups (plies) à anticiper.
Nombre de nœuds à profondeur d : b^d
Nombre total de nœuds sur toutes les profondeurs : 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Pour b et d grands, le total ≈ b^d (dominé par le niveau des feuilles).
Tic-Tac-Toe 4×4×4
L'arbre de jeu complet : b ≈ 64 (carrés légaux), d = 64 (coups totaux). Nombre total de nœuds ≈ 64^64 ≈ 10^115. L'univers observable contient environ 10^80 atomes. La recherche par force brute est physiquement impossible.
Calcul de la Taille de l'Arbre
Les échecs fournissent des nombres plus réalistes. Facteur de ramification moyen b ≈ 35. Une recherche de 6 demi-coups (3 coups chaque côté) nécessite environ 35^6 nœuds.
Élagage Alpha-Bêta : Réduction de l'Exposant
L'élagage alpha-bêta élimine les sous-arbres qui ne peuvent pas affecter le résultat minimax. L'idée clé : si vous savez déjà qu'une branche donne la valeur V, vous pouvez élaguer toute branche sœur dont la valeur tombe probablement en dessous de V (pour le joueur maximisant) ou au-dessus de V (pour le joueur minimisant).
Géométrie du Meilleur Cas
Avec un classement optimal des coups (les meilleurs coups cherchés en premier), l'élagage alpha-bêta réduit le facteur de ramification effectif de b à √b. La profondeur de recherche double effectivement pour le même budget de nœuds :
Recherche complète : b^d nœuds
Meilleur cas alpha-bêta : b^(d/2) nœuds
Exemple : b=35, d=6. Complet : 35^6 ≈ 1,84 × 10^9. Alpha-bêta : 35^3 = 42 875. Facteur de réduction : ~43 000.
En pratique, le classement des coups est imparfait. Réduction typique : b^(d×0,75) — facteur de ramification équivalent ≈ b^0,75.
Dualité Centre-Coin
Hamming note une dualité géométrique dans le cube 4×4×4 : il existe une inversion envoyant les 8 positions de coin aux 8 positions centrales (le cube intérieur 2×2×2) & vice versa, tout en préservant toutes les 76 lignes gagnantes.
Comptage des Lignes Passant par une Position
Dans un cube 4×4×4, les positions diffèrent par le nombre de lignes gagnantes qui les traversent :
Positions de coin : 7 lignes chacune (4 diagonales de face, 2 lignes d'arête, 1 diagonale spatiale)
Positions de centre d'arête : 4 lignes chacune
Positions de centre de face : 6 lignes chacune
Positions de centre du corps (cube intérieur 2×2×2) : 7 lignes chacune
La dualité mappe les coins (7 lignes) aux centres du corps (7 lignes). Les deux ensembles forment des « points chauds ».
Pourquoi les Points Chauds Importent Géométriquement
Un joueur contrôlant plus de positions avec un nombre de lignes élevé contrôle plus de lignes gagnantes potentielles. C'est un argument géométrique direct : la maximisation de la couverture des lignes guide la sélection des coups sans aucune recherche.
Fonctions d'Évaluation
Chaque programme de jeu a besoin d'une fonction d'évaluation : une fonction mappant les états du plateau à des valeurs numériques (positif = bon pour le joueur qui maximise, négatif = bon pour le joueur qui minimise). La fonction d'évaluation fournit la condition limite aux feuilles de l'arbre de recherche.
Fonctions d'Évaluation Linéaires
Une fonction d'évaluation linéaire assigne un poids w_i à chaque caractéristique f_i de la position :
E(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Pour le tic-tac-toe 4×4×4 : les caractéristiques pourraient inclure les lignes ouvertes contrôlées, les positions dans les carrés avec nombre de lignes élevé, les fourches menacées. Pour les échecs : le décompte de matériel, le contrôle du centre, la sécurité du roi, la structure des pions.
C'est une fonction linéaire dans l'espace des caractéristiques — un hyperplan dans ℝ^n. Deux positions avec les mêmes valeurs de caractéristiques obtiennent la même évaluation quelles que soient toutes les autres différences. La géométrie de la fonction d'évaluation détermine ce que le programme « voit ».
Samuel's checker program improved by adjusting the weight vector w — gradient descent in the space of linear evaluation functions.
Géométrie & la Limite de la Formalisation
L'arbre de jeu a une structure géométrique claire : croissance exponentielle à profondeur d, réductible à b^(d/2) par l'élagage alpha-bêta, davantage réductible en restreignant aux positions de haute valeur (les points chauds réduisent l'b effectif). La fonction d'évaluation définit un hyperplan dans l'espace des caractéristiques.
Tout cela est clair, précis, formellement complet. Il décrit le centre du problème du jeu — la région où la structure mathématique fournit une orientation claire.
La limite — où basculer de l'application de règles à l'exploration, quand troquer l'avantage positionnel pour une opportunité tactique, comment reconnaître les motifs émergents au-delà de la fonction d'évaluation — résiste à cette formalisation. Le savoir tacite de Hamming vit à cette limite.
La géométrie vous permet de calculer combien de recherche vous pouvez vous permettre. Elle ne vous dit pas ce qu'il faut chercher.