Math
Albero di gioco e alfa-beta
Un albero di gioco in cui ogni blocco è alto quanto il suo valore: un nodo MAX alto quanto il figlio più alto, un nodo MIN basso quanto il figlio più basso. Il minimax legge ogni foglia; l'alfa-beta salta ciò che non può cambiare la risposta, e quanto salta dipende dall'ordine delle mosse.
Cosa succede
Ogni blocco è alto quanto il suo valore, così la regola si vede prima di essere nominata: un nodo MAX è alto quanto il figlio più alto, un nodo MIN basso quanto il figlio più basso, e la radice è il valore del gioco. Il minimax legge tutte le b^d foglie. L'alfa-beta le legge in ordine e smette di guardare un nodo nell'istante in cui un fratello già visto rende il resto irrilevante - i rami in cui non entra mai restano scuri. La risposta non cambia mai per questo, cambia solo il conto, e il conto dipende dall'ORDINE delle mosse, non dall'albero: con la mossa migliore per prima in ogni nodo serve esattamente il minimo di Knuth e Moore, circa la radice quadrata di b^d; con la peggiore per prima vede ogni foglia - ma solo fino alla profondità 3, perché dalla 4 l'alfa alzato alla radice scende e pota anche quello. Cosa guardare: i rami potati, il sentiero dorato della variante principale e le tre barre sul fondo - minimax, questa ricerca, il minimo.
Equazioni del modulo
Equazioni nodo MAX: v = max sui figli; nodo MIN: v = min sui figli; il minimax legge tutte le b^d foglie alfa-beta: si tagliano i figli restanti di un nodo appena alfa >= beta - la risposta è la stessa, il conteggio no ordinamento perfetto: N_min = 2·b^(d/2) − 1 per d pari, b^((d+1)/2) + b^((d−1)/2) − 1 per d dispari (Knuth - Moore, 1975) ordinamento peggiore in ogni nodo: N = b^d per d <= 3; da d = 4 l'alfa della radice raggiunge il terzo livello e taglia comunque ordinamento s in [−1, 1]: i figli di un nodo sono ordinati per valore esatto quando la sua moneta di hash è sotto |s| - prima i migliori per s > 0, prima i peggiori per s < 0
