Fattore di Ramificazione & Conteggio dei Nodi
Un albero di gioco modella ogni possibile sequenza di mosse da una posizione iniziale. Ogni nodo rappresenta uno stato della plancia. Ogni arco rappresenta una mossa legale. La struttura dell'albero determina se la ricerca rimane fattibile.
Parametri Chiave
Fattore di ramificazione b: numero di mosse legali disponibili in una posizione tipica.
Profondità d: numero di plies (semmosse) da cercare in avanti.
Conteggio dei nodi alla profondità d: b^d
Nodi totali su tutte le profondità: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
Per b e d grandi, il totale ≈ b^d (dominato dal livello foglia).
Tris 4×4×4
L'albero di gioco completo: b ≈ 64 (caselle legali), d = 64 (mosse totali). Conteggio dei nodi completo ≈ 64^64 ≈ 10^115. L'universo osservabile contiene approssimativamente 10^80 atomi. La ricerca per bruta forza è fisicamente impossibile.
Calcolo della Dimensione dell'Albero
Gli scacchi forniscono numeri più realistici. Fattore di ramificazione medio b ≈ 35. Una ricerca di 6-ply (3 mosse per parte) richiede approssimativamente 35^6 nodi.
Potatura Alfa-Beta: Riduzione dell'Esponente
La potatura alfa-beta elimina i sottoalberi che non possono influenzare il risultato minimax. L'intuizione chiave: se sai già che un ramo dà valore V, puoi potare qualsiasi ramo fratello il cui valore provabilmente scende al di sotto di V (per il giocatore massimizzante) o al di sopra di V (per il giocatore minimizzante).
Geometria del Caso Migliore
Con ordinamento ottimale delle mosse (le migliori mosse cercate prima), alfa-beta riduce il fattore di ramificazione effettivo da b a √b. La profondità di ricerca raddoppia effettivamente per lo stesso budget di nodi:
Ricerca completa: b^d nodi
Caso migliore alfa-beta: b^(d/2) nodi
Esempio: b=35, d=6. Completa: 35^6 ≈ 1.84 × 10^9. Alfa-beta: 35^3 = 42.875. Fattore di riduzione: ~43.000.
In pratica, l'ordinamento delle mosse non è perfetto. Riduzione tipica: b^(d×0,75) — fattore di ramificazione equivalente ≈ b^0,75.
Dualità Centro-Angolo
Hamming nota una dualità geometrica nel cubo 4×4×4: esiste un'inversione che invia le 8 posizioni d'angolo alle 8 posizioni centrali (il cubo interno 2×2×2) & viceversa, preservando tutte le 76 linee vincenti.
Conteggio delle Linee Attraverso una Posizione
In un cubo 4×4×4, le posizioni differiscono nel numero di linee vincenti che le attraversano:
Posizioni d'angolo: 7 linee ciascuna (4 diagonali di faccia, 2 linee di bordo, 1 diagonale dello spazio)
Posizioni centro-bordo: 4 linee ciascuna
Posizioni centro-faccia: 6 linee ciascuna
Posizioni centro-corpo (cubo interno 2×2×2): 7 linee ciascuna
La dualità mappa gli angoli (7 linee) ai centri-corpo (7 linee). Entrambi gli insiemi formano 'punti caldi'.
Perché i Punti Caldi Contano Geometricamente
Un giocatore che controlla più posizioni con alto conteggio di linee controlla più linee vincenti potenziali. Questo è un argomento geometrico diretto: la massimizzazione della copertura di linea guida la selezione delle mosse senza alcuna ricerca.
Funzioni di Valutazione
Ogni programma che gioca ha bisogno di una funzione di valutazione: una funzione che mappa stati della plancia a valori numerici (positivo = buono per il giocatore massimizzante, negativo = buono per il giocatore minimizzante). La funzione di valutazione fornisce la condizione al contorno alle foglie dell'albero di ricerca.
Funzioni di Valutazione Lineare
Una funzione di valutazione lineare assegna un peso w_i a ogni caratteristica f_i della posizione:
E(posizione) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
Per il tris 4×4×4: le caratteristiche potrebbero includere linee aperte controllate, posizioni in caselle con conteggio di linee elevate, fork minacciati. Per gli scacchi: conteggio del materiale, controllo del centro, sicurezza del re, struttura dei pedoni.
Questa è una funzione lineare nello spazio delle caratteristiche — un iperpiano in ℝ^n. Due posizioni con gli stessi valori di caratteristica ricevono la stessa valutazione indipendentemente da tutte le altre differenze. La geometria della funzione di valutazione determina quello che il programma 'vede'.
Il programma di dama di Samuel è migliorato regolando il vettore di peso w — discesa del gradiente nello spazio delle funzioni di valutazione lineare.
Geometria & il Confine della Formalizzazione
L'albero di gioco ha una struttura geometrica pulita: crescita esponenziale a profondità d, riducibile a b^(d/2) per alfa-beta, ulteriormente riducibile limitandosi a posizioni ad alto valore (i punti caldi riducono b effettivo). La funzione di valutazione definisce un iperpiano nello spazio delle caratteristiche.
Tutto questo è pulito, preciso, formalmente completo. Descrive il centro del problema del gioco — la regione in cui la struttura matematica fornisce una guida chiara.
Il confine — dove passare dall'applicazione di regole all'esplorazione, quando scambiare il vantaggio posizionale per l'opportunità tattica, come riconoscere i modelli emergenti oltre la funzione di valutazione — resiste a questa formalizzazione. La conoscenza tacita di Hamming vive a quel confine.
La geometria ti consente di calcolare quanta ricerca puoi permetterti. Non ti dice cosa cercare.