LaMoSca v0.07

L'algoritmo NegaMax

Obiettivo

In questa versione del programma viene usato l'algoritmo di ricerca NegaMax.

Il codice

Dal punto di vista funzionale, il NegaMax è identico al MiniMax, perché si basa sempre sulla ricerca delle posizioni ottimali per i due lati della partita. Dal punto della scrittura del codice, però il NegaMax evita di scrivere due funzioni quasi identiche, come succede nel MiniMax, per alternare operazioni di massimizzazione e minimizzazione dei valori della valutazione.

Adottando valori positivi per le posizioni del programma e negativi per quelle dell'avversario, le due operazioni si possono tradurre in una ricerca di massimo. In questo modo è possibile semplificare il codice, dato che l'analisi di un successivo livello avviene chiamando una nuova istanza della stessa funzione, solo che il risultato tornato da questa verrà utilizzato con il segno invertito nell'istanza chiamante. In pratica, è come se risalendo l'albero, si cambi il verso dell'asse dei valori ad ogni livello.

Un esempio di pseudocodice per la funzione NegaMax è il seguente:

NegaMax(Livello) {
  if (Livello == FOGLIA) return Valutazione();
  GeneraMosse();
  Massimo = - INFINITO;
  for (tutte le mosse) {
    FaiUnaMossa();
    Valore = - NegaMax (Livello + 1);
    TornaIndietro();
    if (Valore > Massimo) Massimo = Valore;
  }
  return Massimo;
}

L'alternanza dei segni richiede che la funzione di valutazione calcoli il risultato come differenza tra il valore dei pezzi di chi muove e quello della controparte, invece che come differenza tra il valore dei pezzi del programma meno quelli dell'avversario.

L'esecuzione del programma

La valutazione del programma per l'apertura con due livelli di analisi prevede, innanzitutto la valutazione delle risposte alla prima mossa "a2a3". La funzione tornerà i valori:

Mosse livello 2: b8a6=4 b8c6=9 g8f6=9 g8h6=4 a7a6=0 a7a5=1 b7b6=1 b7b5=3 c7c6=2 c7c5=5 d7d6=7 d7d5=11 e7e6=7 e7e5=11 f7f6=2 f7f5=5 g7g6=1 g7g5=3 h7h6=0 h7h5=1
Risultato livello 2: Trovata=1, Valore=11

Continuando per tutte le altre mosse, la funzione di livello 1 avrà i seguenti valori:

Mosse livello 1: a2a3=-11 a2a4=-10 b2b3=-10 b2b4=-8 c2c3=-9 c2c4=-6 d2d3=-4 d2d4=0 e2e3=-4 e2e4=0 f2f3=-9 f2f4=-6 g2g3=-10 g2g4=-8 h2h3=-11 h2h4=-10 b1a3=-7 b1c3=-2 g1f3=-2 g1h3=-7

Per cui, la scelta sarà come nel caso precedente:

Risultato livello 1: Trovata=1, Valore=0, Mossa=d2d4

E' bene sottolineare ancora una volta come i risultati del NegaMax e del MiniMax debbano essere identici, dato che cambia solamente la rappresentazione delle informazioni scambiate tra i differenti livelli di ricerca.

Download

LaMoSca07.zip (8.42 k)

Da completare

• generazione di arrocco, promozioni, catture en-passant;
• controllo di situazioni di patta;

Da fare

• eliminazione effetto orizzonte;
• efficienza.

Link

• Negamax