Potatura alphabeta, alfa uguale o superiore a beta. Perché è uguale?

Question

Pur comprendendo il concetto di potatura alfa-beta e albero MiniMax, non capisco perché in molte (ad esempio wikipedia) risorse sull'alfa-beta di potatura ci sia una condizione come α> = β. Nello specifico, l'uguaglianza è confusa. Come ho capito, la beta alfa restituisce mossa che il minmax sarebbe tornato, ma per lo più lo fa più velocemente. Ma questo esempio lo contraddice:

 . 
    /| \ 
    1 3* 2 
/|/\ | \ \ 
    1 1 5 3 4 3 2 

Sopra è l'albero min-max originale. Come possiamo vedere che sarebbe scegliere quella mossa con punteggio di 3. Ora facciamo l'alfa-beta:

 . 
    /| \ 
    1 3* 3* 
/|/\ | \ 
    1 1 5 3 4 3 

Interrompe il più a destra mossa, perché 3> = 3. Ma poi l'algoritmo può scegliere tra 2 mosse perché hanno lo stesso punteggio, ma come abbiamo visto in min-max la scelta giusta è leggermente peggiore. Ciò non accadrebbe se l'algoritmo specificasse semplicemente α> β, quindi avrebbe bisogno di cercare anche 2.

Quindi è stato un errore di battitura nello pseudocodice di wikipedia (e in molte altre risorse)? O ho frainteso qualcosa di veramente grande qui.

Answer 1

L'algoritmo su Wikipedia non restituisce una mossa, restituisce il punteggio del nodo radice che è 3. È questo punteggio uguale al risultato minimax. Dovresti modificare leggermente l'algoritmo per ottenere il movimento da giocare invece del punteggio.

Un modo per farlo è eseguire la funzione alphabeta su ogni spostamento possibile dallo stato corrente e riprodurre il punteggio più alto. Seguendo i collegamenti su wikipedia viene fornito uno implementation che esegue questa operazione.

Penso che si possa anche tenere traccia della mossa migliore trovata all'interno della funzione alphabeta, ma se più nodi hanno lo stesso punteggio allo stesso livello, quindi restituire il primo trovato. Questo potrebbe essere migliore perché è necessario valutare meno nodi.

Answer 2

Di solito, viene utilizzato uguale, poiché consente un guadagno di prestazioni riconoscibile e poiché il valore restituito non cambia da rami uguali.

L'unico punto in cui potrebbe essere utile almeno nella prima profondità di ricerca, ma la perdita di prestazioni è la peggiore qui.

Il Minimax fa affidamento sull'avversario che gioca sempre le mosse migliori e non sulla speculazione in cui sbaglia. Se includi una valutazione speciale per scegliere il meglio di due rami uguali, dovresti spendere risorse per la speculazione (cosa che non fai in minimax a causa della sua definizione).

Quindi, tutto sommato, non ha senso usare gli uguali.