Indice

LaMoSca

Introduzione

Struttura di un programma per scacchi

ProgrammaLe funzioni che debbono essere svolte da un programma di scacchi possono essere ricondotte a tre grandi categorie:

  • l'individuazione delle mosse possibili per una determinata posizione;
  • la valutazione delle posizioni ottenute con ciascuna mossa;
  • la scelta della sequenza di mosse ottimale tra tutte quelle possibili.

Mentre la prima funzionalità è abbastanza semplice da realizzare, le altre due sono, per motivi differenti, decisamente più complesse da svolgere con un computer.

La difficoltà della corretta valutazione di una certa posizione di gioco sulla scacchiera è sperimentata da chiunque voglia iniziare a giocare a scacchi ad un livello appena più evoluto rispetto a chi gioca senza una strategia a lungo termine.

La scelta della sequenza ottimale è un compito solo apparentemente semplice. Teoricamente sarebbe sufficiente generare tramite software tutte le mosse possibili dall'apertura alla fine della partita. Contando il numero delle opzioni che è necessario studiare secondo questa impostazione, ci si rende conto della complessità dell'impresa. L'apertura, ad esempio, prevede 20 differenti scelte possibili. Considerando che per ciascuna di queste, l'avversario può generare altre venti risposte, solo al primo livello si ha un totale di 20^2 = 400 alternative.

Considerando una media di alternative per ogni livello di gioco pari a 35 per ciascun giocatore e che una partita di scacchi conta circa 40 livelli, si ha un numero complessivo di nodi da analizzare pari a 35^(2*40) = 3.35 e+123, che rende impraticabile la ricerca completa delle varianti.

L'insieme di tutte le varianti possibili dalla posizione iniziale della scacchiera, però, forma un albero di mosse nel quale la definizione della sequenza migliore rappresenta un percorso ottimo, problema ben noto in informatica.

La ricerca del percorso ottimo all'interno dell'albero generato dal software è l'elemento caratteristico degli attuali programmi di scacchi. Il miglioramento dell'efficienza del software in questa ricerca, con il conseguente aumento della profondità di analisi raggiungibile dal computer, rappresenta il modo per superare i limiti nella capacità di valutare la qualità del gioco da parte della macchina.

Per quanto riguarda le strutture dati utilizzate dal software, in linea di principio sono necessarie solo poche informazioni, quali:

  • la posizione dei pezzi sulla scacchiera;
  • il lato che deve muovere;
  • la lista delle mosse da valutare;
  • la possibilità di arrocco per ciascun lato;
  • una memoria delle scelte fatte dal computer, per valutare la correttezza di catture "en-passant", le patte per ripetizione e per per il superamento del limite delle 50 mosse dall'ultima cattura o avanzamento di pedone (oltre che, eventualmente, per permettere al programma di tornare indietro nel gioco).

Ciascun particolare algoritmo introdotto nel programma di scacchi, poi, richiederà sue specifiche strutture dati.

Riferimenti

Paolo Ciancarini:
"I Giocatori Artificiali";
Mursia, 1992 - 252 pag.
ISBN 88-425-1319-9

Link

Indice

Avanti