LaMoSca v0.02

Generazione di Mosse Pseudo-legali

Obiettivo

Questa versione del programma genera la lista delle mosse possibili per la corrente posizione dei pezzi sulla scacchiera. Pur rispettando le caratteristiche di movimento dei pezzi degli scacchi, non viene fatto nessun controllo sulla loro completa correttezza (es.: persistenza di situazioni di scacco), per cui queste mosse vengono definite pseudo-legali.

L'uso che viene fatto di questa lista, per il momento è limitato alla verifica dell'ammissibilità delle mosse immesse in input dall'operatore, tramite un loro confronto con quelle generate dal software.

Le alternative

Nella generazione da parte del programma delle proprie mosse è possibile seguire strategie differenti secondo che si vogliano generare tutte le mosse possibili, per poi eliminare quelle non regolari e meno valide, oppure ci si voglia concentrare su di un numero ristretto di buone candidate.

Attualmente la scelta più seguita dai programmi di scacchi è la prima, con la generazione da computer di tutte le mosse possibili per i pezzi, indipendentemente dal fatto che risultino legali o meno (es.: lascino il re sotto scacco): queste mosse sono definite "pseudolegali". L'eliminazione di quelle non valide da parte del software avviene poi durante la ricerca della mossa ottima per il computer.
Un caso ancora valido, invece, di utilizzo della prima tecnica è quello della generazione da computer delle sole catture per la ricerca di situazioni di gioco stabile ("quiescenza"), situazioni, cioè nelle quali non si hanno scambi di pezzi tra le due parti. Questa ricerca viene eseguita per evitare valutazioni errate delle posizioni dovute a vantaggi solo temporanei di pezzi durante scambi prolungati ("effetto orizzonte").

Altro aspetto è quello della generazione algoritmica delle mosse, seguendo le regole di ciascun pezzo, oppure la precompilazione di librerie o tabelle di mosse e la loro selezione da parte del software in base alla posizione corrente sulla scacchiera, con grossi vantaggi in termini di tempi di elaborazione. La seconda modalità è applicabile innanzi tutto alle aperture, tramite l'utilizzo di librerie per la fase iniziale della partita di scacchi, per poi passare alla generazione algoritmica nel mediogioco. Altro campo è quello dei finali, con tabelle che permettono di identificare finali di gioco teoricamente risolti.

Anche nella generazione algoritmica delle mosse, è possibile "precompilare" tabelle con le mosse realizzabili dai pezzi per poi trasformare la generazione delle mosse stesse nell'accesso a queste tabelle da parte del computer usando come chiave di accesso la posizione corrente.

Il codice

I vettori di movimento

Nel programma la scacchiera è memorizzata come un vettore continuo di case con indici che vanno da "0" per l'A8 a 63 per H1. Per generare efficientemente le mosse tramite computer, è possibile memorizzare dei vettori per ogni pezzo con gli offset di tutte le possibili case destinazione a partire della casa corrente. Ad esempio, per un cavallo il vettore di movimento dovrebbe essere

-17, -15, -10, -6, 6, 10, 15, 17

Ipotizzando di avere il pezzo nella casa 36, le possibili case destinazione, da salvare in un apposito stack, sarebbero

19, 21, 26, 30, 42, 46, 51, 53

Per i pezzi che possono avanzare per più di una casa (es.: alfiere) il vettore di movimento sarà applicato fino a trovare una casa non libera e saranno salvate nello stack tante mosse quante sono le case visitate.

 0,  1,  2,  3,  4,  5,  6,  7,
 8,  9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23,
24, 25, 26, 27, 28, 29, 30, 31,
32, 33, 34, 35, 36, 37, 38, 39,
40, 41, 42, 43, 44, 45, 46, 47,
48, 49, 50, 51, 52, 53, 54, 55,
56, 57, 58, 59, 60, 61, 62, 63

Check tramite case di bordo

Un problema che si ha negli scacchi per la generazione delle mosse da parte del software è la verifica che la casa di destinazione sia all'interno della scacchiera. Ad esempio, tutte le mosse di un re in H1 dirette verso il basso e verso destra non debbono essere considerate.

-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1,  0,  1,  2,  3,  4,  5,  6,  7, -1,
-1,  8,  9, 10, 11, 12, 13, 14, 15, -1,
-1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
-1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
-1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
-1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
-1, 48, 49, 50, 51, 52, 53, 54, 55, -1,
-1, 56, 57, 58, 59, 60, 61, 62, 63, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1.

21, 22, 23, 24, 25, 26, 27, 28,
31, 32, 33, 34, 35, 36, 37, 38,
41, 42, 43, 44, 45, 46, 47, 48,
51, 52, 53, 54, 55, 56, 57, 58,
61, 62, 63, 64, 65, 66, 67, 68,
71, 72, 73, 74, 75, 76, 77, 78,
81, 82, 83, 84, 85, 86, 87, 88,
91, 92, 93, 94, 95, 96, 97, 98

Una tecnica utilizzabile è quella delle "case di bordo". Viene creata una matrice che all'esterno delle 8x8 case della scacchiera ha di valori convenzionali (es.: -1).

Il numero delle colonne aggiuntive è dettato dal movimento del cavallo che da una casa può saltare di due valori all'esterno di essa. Sono quindi necessarie due righe al di sopra e al di sotto della scacchiera convenzionale, mentre a destra e a sinistra basta una sola colonna, dato che ciascuna di queste può essere considerata come continuazione dell'altra. La matrice, quindi, ha dimensioni 10x12,  come quella mostrata a lato.

Per accedere da software a questa matrice se ne utilizza una seconda, di dimensioni 8x8, che riporta la corrispondenza tra gli indici della matrice 8x8 e quelli della 10x12.

La verifica durante il gioco che la casa destinazione sia all'interno della scacchiera si ottiene verificando che, accedendo alla matrice 10x12 non si ottenga un valore pari a "-1".

Il file di log

Per tenere traccia del funzionamento del programma di scacchi durante il gioco, in questa versione è stata inserita la possibilità di generare un file di log, attivabile passando il parametro "log" all'avvio del programma.

Ad esempio,analizzando il contenuto del file "LaMoScaLogFile.txt" si vede che le mosse generate a fronte degli input "e2e4", "d7d5" e "e4e5" saranno:

Mosse: a2a3 a2a4 b2b3 b2b4 c2c3 c2c4 d2d3 d2d4 e2e3 e2e4 f2f3 f2f4 g2g3 g2g4 h2h3 h2h4 b1a3 b1c3 g1f3 g1h3
Mosse: b8a6 b8c6 g8f6 g8h6 a7a6 a7a5 b7b6 b7b5 c7c6 c7c5 d7d6 d7d5 e7e6 e7e5 f7f6 f7f5 g7g6 g7g5 h7h6 h7h5
Mosse: e4d5 e4e5 a2a3 a2a4 b2b3 b2b4 c2c3 c2c4 d2d3 d2d4 f2f3 f2f4 g2g3 g2g4 h2h3 h2h4 b1a3 b1c3 d1e2 d1f3 d1g4 d1h5 e1e2 f1e2 f1d3 f1c4 f1b5 f1a6 g1f3 g1h3 g1e2

Download

LaMoSca02.zip (4.43 k)

Da Fare

• generare mosse legali;
• generare mosse speciali come arrocco, promozioni, catture en-passant;
• far eseguire mosse da parte del programma;
• gestire l'interfaccia grafica;
• verificare le situazioni di patta nel gioco per ripetizione e limite delle 50 mosse.

Riferimenti

• Paolo Ciancarini:
  "I Giocatori Artificiali";
  Mursia

Link

• Chess Programming