Scrivere un programma di scacchi – 1



computer chessI giochi da tavolo, come la Dama o gli Scacchi, sono sempre stati un terreno ideale per le ricerche nel campo dell’Intelligenza Computazionale.

Le regole sono fisse, lo scopo del problema è univocamente determinato e l’interazione tra i giocatori è ben definita. Storicamente i giochi sono sempre stati un modo popolarissimo per dimostrare nuove idee o scoperte nell’ambito dell’intelligenza artificiale.

Per la verità, uno dei primi obiettivi delle ricerche di I.A. fu proprio quello di creare un programma in grado ti battere il contemporaneo campione del mondo di scacchi in un match uomo-macchina.

Le ricerche in questo campo cominciarono nel 1950 quando Cloude Shannon, uno dei più grandi luminari nella storia della ricerca informatica, pubblicò un suo scritto sulla struttura di una macchina calcolatrice in grado di giocare a scacchi.

Nei cinquant’anni che seguirono la pubblicazione di questo documento, sono stati fatti enormi progressi e gli scacchi non sono più l’unico gioco oggetto di ricerca.

Negli anni ottanta David Levy creò le Computer Olympiad (Olimpiadi del Computer): un evento multi gioco che si svolge ogni anno in un luogo diverso e durante il quale decine di programmi competono l’uno contro l’altro.

La maggior parte dei giochi sono giochi da tavola, ma anche altri giochi come il Poker o il Bridge stanno prendendo piede. Queste Olimpiadi furono originariamente ospitate a Londra o a Maastricht, più tardi comuncque altre città in giro per il mondo hanno ospitato questo evento.  Non ricordo esattamente il motivo che mi spinse anni fa a scrivere il mio primo programma di scacchi (d’ora in poi motore di scacchi o chess engine), ma mentre cercavo informazioni su Internet venni a conoscenza di una vasta comunità internazionale di programmatori e ricercatori che si interessava dell’argomento. Scoprii quindi l’esistenza di una interfaccia grafica (Winboard) e di un protocollo standard che permetteva ai vari programmi di giocare tra loro su vari server sparsi nel mondo, in tornei online appositamente organizzati e in competizioni nazionali e internazionali.

Nel 2001, scrissi dunque il mio primo programma e partecipai al mio primo torneo classificandomi sesto su dodici. Da allora non ho più smesso.

Questo è il primo di una serie di articoli che spero vi aiutino a scrivere un vostro programma e infoltire la discretamente numerosa schiera di programmatori italiani. In questo articolo introduttivo parlerò dunque del linguaggio di programmazione da usare e fornirò uno schema introduttivo di un motore scacchistico.

Spesso in molti forum dedicati si può leggera la fatidica domanda : “Qual’è il miglior linguaggio da usare per scrivere un chess engine?”.

La risposta è semplice: il linguaggio che conosci meglio!

Ci sono motori scritti in C, C++, Pascal, Java, Delphi, Visual Basic, Assembly… Il mio programma, Mizar, è scritto in C. Per quanto riguarda i sistemi di sviluppo in Rete si trovano molti compilatori freeware o IDE da scaricare. Limitandomi al C/C++ e alla piattaforma Windows suggerisco:

  • Code::Block è un buon IDE multipiattaforma ed è compatibile con molti compilatori freeware ;
  • Open Watcom è la versione open source del buon vecchio compilatore Watcom e si integra con Code::Block;
  • Digital Mars è un compilatore freeware e si integra anch’esso con Code::Block;
  • MinGW è il “GCC per Windows”;
  • Dev-C++ è un ambiente integrato (IDE e compilatore) gratuito, ma il suo sviluppo è fermo dal 2004;
  • Visual C++ Express 2008 attualmente, penso, il miglior ambiente di sviluppo possibile ( non dimenticate di scaricare anche la MSDN Library).

Un’altra cosa che consiglio è un programma come CVS per implementare un sistema di controllo di versione: utilissimo per tenere traccia delle frequenti modifiche del codice e avere la possibilità in ogni istante di annullarle.

Un chess engine è semplicemente un programma console che legge dell’input testuale (un comando, una mossa…) dallo stream standard di input e scrive del testo (un comando, una risposta…) nello stream standard di output.

Tutto qui.

In che maniera un computer gioca a scacchi? Beh, non è facile spiegarlo con parole semplici, ma per il momento, semplifivando di molto il tutto possiamo dire che un chess engine:

  1.  legge una stringa di testo che rappresenta una mossa espressa in coordinate algebriche ( per esempio ‘e2e4’)
  2. aggiorna la propria rappresentazione interna della scacchiera
  3. da questa posizione che chiamiamo nodo radice (root) genera tutte le possibili mosse di risposta
  4. ogni mossa generata viene eseguita sulla scacchiera virtuale interna e per ogni nuova configurazione vengono generate le rispettive contromosse
  5. ogni contromossa viene eseguita sulla scacchiera virtuale interna e per ogni configurazione vengono generate le rispettive contro-contromosse
  6. questo processo continua fino ad un certo numero di mosse nel futuro, si viene così a generare un vero e proprio albero delle mosse i cui nodi terminali vengono detti nodi foglia.
  7. con una funzione matematica che esprime la bontà di una posizione con un numero tutti i nodi foglia vengono valutati
  8. viene quindi eseguita la mossa che ha più possibilità di portare ad una posizione migliore per il computer stesso

Ricordatevi che questa è una versione molto semplificata del reale processo, ma in questa fase serve a poco capire i dettagli.

Piuttosto adesso si può facilmente comprendere che per scrivere un chess engine occorre:

  • un modo per rappresentare la scacchiera in memoria
  • un modo per aggiornare la scacchiera ed ottenere una nuova scacchiera eseguendo una mossa
  • un modo per generare le mosse a partire dalla configurazione corrente della scacchiera
  • un algoritmo per scegliere tra tutte le mosse possibili, quelle legalmente (dal punto di vista delle regole del gioco) fattibili
  • un modo per conservare l’albero delle mosse in memoria e visitarlo
  • una funzione di valutazione della scacchiera
  • una interfaccia grafica

Possiamo dimenticarci tranquillamente dell’interfaccia grafica; esistono due popolarissime interfaccie freeware usate dalla quasi totalità dei chess engine esistenti: Winboard Arena. Entrambi i programmi si interfacciano ai motori tramite delle Pipe anonime: in questo modo noi dovremo “limitarci” a scrivere un semplice programma console che legge e scrive sugli stream standard.

Per cominciare suggerisco di utilizzare un approccio iterativo che porti prima a realizzare un semplicissimo programma da potenziare via via (da qui la quasi necessita di un sistema quale il CVS); quando sarete più esperti potrete riscrivere il vostro programma partendo dalle fondamenta e pianificando dall’inizio l’implementazione di tutte le tecniche di cui parleremo. nello specifico suggerisco questo percorso:

  1. decidere come rappresentare la scacchiera in memoria;
  2. scrivere una funzione per tradurre le stringhe FEN nella nostra rappresentazione interna;
  3. scrivere un generatore di mosse;
  4. scrivere una funzione che ci dica se una determinata casella è attaccata da uno dei due giocatori;
  5. scrivere una funzione per aggiornare la configurazione interna della scacchiera con una mossa data ( e anche per riportarla nella condizione iniziale);
  6. Controllo 1: fermarsi e scrivere una funzione Perft per il debug di quanto scritto fin’ora;
  7. scrivere una semplice funzione di valutazione;
  8. scrivere una funzione di ricerca sull’albero delle mosse;
  9. scrivere una funzione che guidi questa ricerca;
  10. scrivere una semplice funzione per connettere il proprio motore a Winboard e/o ad Arena;
  11. Contollo 2: fermarsi e fare il debug!

Puoi trovare molte informazioni, suggerimenti e papers in questi siti (per il 99% in inglese):

Nel prossimo articolo: La rappresentazione della scacchiera

Annunci sponsorizzati:
Condividi su Facebook Condividi su Twitter!
  • george w.

    troppo difficile

  • E lo deduci dall’introduzione?! :D Ad ogni modo non è un molto più complesso di programmare qualunque altra cosa: certo devi sapere programmare. E conoscere un poco di html non è sapere programmare! ;)

  • C’e’ Qualche brava Persona nel Mondo dei Programmatori Professionisti
    che Potesse farmi Avere anche solo sotto forma di studio il Gioco della Dama
    e degli Scacchi Scritto in Visual Basic 6.0!.
    Vi Ringrazzierei Tantissimo ; perche’ pur essendo un AutoDidatta che studia da Tanti anni
    non sono mai riuscito a realizzare questo mio Sogno.
    Distinti Saluti e Grazie ancora di Tutto da :
    A. Maurizio – maury1704@alice.it – ” 393.38.32.667 “

  • luke

    Bravo Nicola ottimo articolo!

    Luke (uragano)

Pinterest