Home

LaMoSca v0.06

Ricerca tramite MiniMax

Obiettivo

In questa versione del programma viene implementato l'algoritmo di ricerca MiniMax; algoritmi pi?efficienti sono introdotti in successive versioni.

La ricerca

La bontà di una mossa non può essere valutata giudicando solo la posizione immediatamente ottenuta, ma è necessario prevedere la posizione finale di una serie di mosse costituita dalle migliori risposte dell'avversario e possibili contromosse del programma.
L'insieme delle varianti costituisce un albero e la scelta della mossa migliore richiede l'identificazione del percorso ottimo.

L'algoritmo MiniMax

MiniMax

MiniMax è un algoritmo che serve per scegliere la mossa ottima tra tutte quelle generabili. Senza tenere conto delle risposte dell'avversario, la mossa da scegliere in una determinata posizione di gioco sarebbe quella che porta alla posizione con la valutazione massima (in funzione dei valore dei pezzi, posizione sulla scacchiera, ecc.).

Tenendo conto anche la risposta dell'avversario, questo tenterà a sua volta di massimizzare la sua posizione, minimizzando di conseguenza il valore della nostra. In altre parole, la migliore risposta dell'avversario sarà quella ci lascia nella posizione meno favorevole tra quelle possibili.

Questo discorso può essere esteso per un numero qualsiasi di livelli di analisi, valutando alternativamente le mosse del programma e tutte le possibili risposte dell'avversario. L'insieme di tutte le varianti genera un albero di mosse e di risposte. Le foglie dell'albero sono le posizioni finali delle varianti e saranno le sole ad essere valutate: tutte le posizioni intermedie sono ignorate.

Partendo dalle posizioni foglia e propagando verso la radice (costituita dalla posizione corrente) le loro valutazioni, si avrà che:

  • i livelli che corrispondono a risposte dell'avversario propagheranno verso la radice i valori massimi, dato che il programma sceglierà la posizione migliore raggiungibile da quel livello (livello Max);
  • i livelli che corrispondono a mosse del programma propagheranno i valori minimi, dato che l'avversario cercherà di costringerci nella posizione peggiore (livello Min).

Da quest'alternanza di scelte tra i valori massimo e minimo deriva il nome dell'algoritmo (MiniMax). Un esempio di pseudocodice per le funzioni di minimizzazione e massimizzazione è il seguente:

Mini(Livello) {
  if (Livello == FOGLIA) return Valutazione();
  GeneraMosse();
  Minimo = INFINITO;
  for (tutte le mosse) {
    FaiUnaMossa();
    Valore = Max(Livello+1);
    TornaIndietro();
    if (Valore < Minimo) Minimo = Valore;
  }
  return Minimo;
}

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

L'esecuzione del programma

In questa versione del programma, il numero di livelli massimo da analizzare è fissato dalla costante "MAXLIVELLI", mentre la profondità realmente utilizzata è variabile con il comando WinBoard "sd".

Considerando l'apertura con due livelli di analisi, innanzitutto verranno generate le mosse del programma e poi si avrà la valutazione delle risposte dell'avversario. Considerando la prima mossa "a2a3" del programma, la funzione da usare sarà quella di minimizzazione ed i valori pari a:

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

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

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

Per cui, la scelta sarà

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

Passando a 4 livelli, però, ci accorgiamo che d2d4 non viene scelta. Infatti, risulta

M1:d2d4=-6; m2:b8c6=-6; M3:b1c3=-101; m4:c6d4=-101

In pratica, con 4 livelli non è possibile proseguire la ricerca oltre la cattura del pedone da parte del cavallo in c6d4. Questo fa si che venga scelta la mossa più prudenziale

M1:b1c3=-2

La scelta non ottimale delle mosse dovuta ad una profondità di ricerca insufficiente (tipicamente legata a sequenze di catture) è chiamata "effetto orizzonte".

Download

LaMoSca06.zip (8.33 k)

Da completare

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

Da fare

  • eliminazione effetto orizzonte;
  • semplificazione del codice;
  • efficienza.

Link
Indietro Indice Avanti