Interprete del formato pgn

Da Tesine Linguaggi e Traduttori.

Jump to: navigation, search

Il formato PGN (dall'inglese Portable Game Notation) è un formato utilizzato per registrare le partite di scacchi; è stato inventato per essere utilizzato dai programmi per computer che giocassero a scacchi, ma allo stesso tempo per essere facilmente letto dall'uomo.

La sua struttura è stata definita tenendo conto di entrambe le necessità: infatti, da una parte, il formato deve consentire ad uno scanner e ad un parser di poterlo interpretare correttamente con il minimo numero di ambiguità e dall'altra, deve essere sufficientemente semplice e intuitivo per poter essere compreso da un essere umano.

Lo scopo del formato PGN è quello di facilitare la condivisione di dati relativi a partite di scacchi tra giocatori, analisti e ricercatori.

Contents

Definizione del formato

Il formato PGN è molto complesso, di seguito ne riportiamo alcune caratteristiche:

Campo Event

  • Il campo Event deve essere ragionevolmente descrittivo.
  • Le abbreviazioni devono essere evitate quando è possibile.
  • Se il torneo e' a squadre, specificare.
  • Se il nome dell'evento è sconosciuto, è necessario indicarlo con un punto interrogativo.

Esempi corretti:

[Event "FIDE World Championship"]
[Event "Moscow City Championship"]
[Event "ACM North American Computer Championship"]
[Event "Casual Game"]
[Event "?"]


Campo Site

  • Il campo Site deve includere i nomi della città e della regione insieme alla sigla standard della nazione
  • Se è disponibile, è consigliato utilizzare una sigla IOC(International Olympic Committee) di tre lettere.
  • Se il nome del luogo è sconosciuto, è necessario indicarlo con un punto interrogativo.
  • Può essere usata una virgola per separare la città dalla regione.
  • Non è necessaria la virgola per separare la città o la regione dalla sigla IOC.

Esempi corretti:

[Site "New York City, NY USA"]
[Site "St. Petersburg RUS"]
[Site "Riga LAT"]
[Site "?"]

Campo Date

  • Il campo Date indica la data di svolgimento della partita nel formato "aaaa.mm.gg".
  • I numeri dei mesi e dei giorni devono essere a due cifre con eventuali zeri non significativi.
  • In caso di anno, mese o giorno sconosciuto, inserire "??".

Esempi corretti:

[Date "2004.08.23"]
[Date "2004.??.??"]

Esempi NON corretti:

[Date "23.08.2004"]
[Date "2004.8.23"]
[Date "2004.11.5"]
[Date "2004"]


Campo Round

  • Il campo Round definisce il numero del turno di svolgimento della partita.
  • Se il torneo ha piu' di 9 turni, inserire il turno comunque senza zeri non significativi.
  • In caso di turno sconosciuto, inserire "?".

Esempi corretti:

[Round "8"]
[Round "11"]
[Round "8.1"] (per tornei a squadre nazionali)
[Round "?"]

Esempi NON corretti:

[Round "08"]


Campi White e Black

  • I campi White e Black contengono i nominativi dei giocatori nel formato "Cognome, Nome" lasciando una spazio bianco dopo la virgola. Usare lettere maiuscole solo per le iniziali.
  • Uno o più nomi secondari possono comparire (quando è presente una virgola, è necessario che sia seguita da uno spazio)
  • Se più persone stanno giocando da una parte, i nomi devo essere messi in ordine alfabetico.
  • Se un giocatore è un programma informatico, è necessaria la presenza del numero di versione.
  • In caso di nome sconosciuto, inserire "?".

Esempi corretti:

[White "Tal, Mikhail N."]
[White "van der Wiel, Johan"]
[White "Acme Pawngrabber v.3.2"]
[White "Fine, R."]
[Black "Lasker, Emmanuel"]
[Black "Smyslov, Vasily V."]
[Black "Smith, John Q.:Woodpusher 2000"]
[Black "Morphy"]


Campo Result

  • Il campo Result contiene il risultato della partita.
  • Sono ammessi solo 4 valori: "1-0", "0-1", "1/2-1/2", "*"
  • Non sono ammessi i valori "X" o "1/2"
  • Il risultato "*" e' ammesso solo in caso eccezionale, cioè quando la partita venga interrotta per motivi straordinari.

Esempi corretti:

[Result "0-1"]
[Result "1-0"]
[Result "1/2-1/2"]
[Result "*"]

Esempi NON corretti:

[Result "1/2"]


Mosse

Ogni mossa viene indicata tramite l'iniziale del pezzo e la casa di destinazione. Ad esempio Ae5 (oppure Be5, in inglese, o ancora ♗e5, secondo la notazione simbolica) significa "muove l'Alfiere in e5"; Cf3 (Nf3, ♘f3) significa "muove il Cavallo in f3". Nel caso dei Pedoni si indica solo la casa di destinazione: e5 significa "muove il Pedone in e5".

Se due pezzi dello stesso tipo possono muovere nella stessa casa, l'iniziale del pezzo è seguita da:

  • se i due pezzi sono sulla stessa riga: la colonna del pezzo che effettua la mossa;
  • se i due pezzi sono sulla stessa colonna: la riga del pezzo che effettua la mossa;

Quando un pezzo effettua una cattura, si inserisce una x tra l'iniziale del nome e la casa di destinazione. Ad esempio Axe5 significa "l'Alfiere cattura in e5"; Cexf3 significa "il Cavallo della colonna e cattura in f3" (in questo caso entrambi i cavalli potevano catturare in f3). Nel caso dei Pedoni si indica la colonna di partenza al posto dell'iniziale del nome del pezzo: dxe5 significa "il Pedone della colonna d cattura in e5". In caso di presa en passant si indica la casa di arrivo del Pedone che cattura, non quella del Pedone catturato; inoltre si può far seguire la dicitura e.p.: quindi cxb6 e.p. significa "il Pedone della colonna c cattura en passant in b6".

Quando un Pedone raggiunge la parte opposta della scacchiera e viene promosso, il pezzo scelto viene indicato dopo la mossa, ad esempio: a8Q (""muove il Pedone in a8 e promuove a Donna"), bxa8Q (""il Pedone mangia in a8 e promuove a Donna"). A volte viene usato il segno =: a8=Q.

L'arrocco corto (o arrocco di Re) viene indicato con O-O e l'arrocco lungo (o arrocco di Donna) con O-O-O. Attenzione: è usata la lettera "o" maiuscola, non il numero "0". La cosa non ha risvolti pratici nella trascrizione a mano, ma può confondere (e non poco) i programmi per computer! In alternativa, specialmente nei programmi, può essere indicato con la mossa del Re: Rg1.

Una mossa che mette in scacco il Re avversario può essere indicata con un +, mentre lo scacco matto viene indicato con # (anche se alcuni usano ++).

Se la partita e' stata vinta a forfait, non inserire alcuna mossa. Le partite vanno ordinate per turno e poi per ordine alfabetico del giocatore con i pezzi bianchi. La maggior parte dei software di gestione partite permette questo tipo di ordinamento.

Esempio di una partita:

[Event "F/S Return Match"]
[Site "Belgrade, Serbia JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3
O-O 9. h3 Nb8 10. d4 Nbd7 11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15.
Nb1 h6 16. Bh4 c5 17. dxe5 Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21.
Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7
27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33.
f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5
40. Rd6 Kc5 41. Ra6 Nf2 42. g4 Bd3 43. Re6 1/2-1/2


Indicatori qualità mossa

Dopo ogni mossa può essere inserito un indicatore della bontà della mossa. Gli indicatori possibili sono:

  •  ! buona mossa
  •  !! mossa eccellente
  •  ? errore
  •  ?? errore grave
  •  !? mossa interessante, forse non la migliore
  •  ?! mossa dubbia, ma non necessariamente sbagliata


Valutazione abilità di un giocatore

Il crescente numero di tornei scacchistici registratosi dagli anni '40 ad oggi ha richiesto l'introduzione di un metodo matematico per valutare l'abilità di un giocatore e poter stilare classifiche generali. Per il nostro progetto è stato scelto il metodo di valutazione basato sulla stima bayessiana.


Metodi a confronto

Elo

L'assunto centrale di Elo è che l'abilità scacchistica di un dato giocatore, nel corso di una data partita, sia dato da un'ipotetica variabile casuale normalmente distribuita, con un valore medio che rappresenta il reale valore del giocatore e che cambia lentamente. Dato questo modello matematico, lo scopo del sistema Elo è quello di stimare il valore medio del giocatore, considerando l'unico dato osservabile, ovvero il numero di partite vinte, perse e patte. Il punto di forza di questo metodo è certamente la facilità di calcolo facendo si che ogni giocatore possa calcolarsi da solo la variazione di punteggio dopo ogni partita. Purtroppo questo metodo non è ineccepibile: Roberto Ricca sfruttando incongruenze di tale metodo è riuscito a piazzarsi nella prima posizione della classifica italiana mettendo così in difficoltà la federazione scacchistica. Il sistema Elo è universalmente utilizzato come metodo di riferimento nei tornei professionistici.

Glicko

Per quanto riguarda i server internet che permettono di confrontarsi contro altri utenti il sistema utilizzato per il calcolo del rating è il sistema Glicko. Questo metodo è di complessità matematica molto superiore al metodo Elo. Maggiori informazioni sulla metodologia di calcolo possono essere reperite sul sito dell'inventore di tale metodo prof. Mark E. Glickman (http://math.bu.edu/people/mg/glicko/glicko.doc/glicko.html).

Stima bayesiana

Il metodo di valutazione Bayesiana è sicuramente il metodo più preciso (anche se ancora distante dalla perfezione assoluta) ma anche il più complicato dal punto di vista computazionale. La maggior precisione è dovuta al fatto che ad ogni giocatore sono associati due valori: la media, rappresentante l'abilità del giocatore, e la varianza che serve a calcolare l'abilità dopo ogni partita. L'aggiunta di un parametro rispetto al metodo Elo fa si che se un giocatore continua a giocare contro giocatori di rank più basso del suo il suo valore di varianza diminuirà considerevolmente e lo scarto della media dopo le partite successive tenderà a zero. Questo corregge il problema che ha condotto al "caso Ricca".

Fondamenti teorici della stima bayessiana

L'abilità di un giocatore A può essere rappresentata tramite una variabile casuale approssimata con una distribuzione normale di media a e varianza delta_a^2.

Immagine:formula1.gif

Se A gioca contro B verranno modificati i suoi valori di media e varianza a seconda dell'esito della partita. Dichiarando R il risultato della partita la nuova densità può essere calcolata utilizzando il teorema di Bayes e avrà il seguente valore:

Immagine:formula2.gif

Vittoria

Il nuovo valore della media sarà dato da

Immagine:formula3.gif

Dove il parametro Kv vale

Immagine:formula4.gif

Mentre la nuova varianza sarà:

Immagine:formula5.gif

Sconfitta

Il nuovo valore della media sarà dato da

Immagine:formula6.gif

Dove il parametro Ks vale

Immagine:formula7.gif

Mentre la nuova varianza sarà:

Immagine:formula8.gif

Pareggio

La media e varianza saranno:

Immagine:formula9.gif

Implementazione

Sono state create due classi java (Player e Opponent) al fine di implementare questa funzionalità. La struttura dati utilizzata è una lista di Player a ciascuno dei quali è associata una lista non vuota di Opponent. Per ogni partita trovata nel file .png viene cercato il giocatore nella lista e nel caso non sia presente viene aggiunto. Se sono presenti i valori di media e varianza saranno usati quelli se no i due parametri saranno settati ai valori standard (1000 e 100). Se il valore è presente ma il giocatore è già presente nella lista viene utilizzato il valore già presente nella struttura dati. Viene quindi aggiunto l'avversario nella lista degli Opponent e salvato il risultato della partita.

Alla fine della fase di parsing del file viene lanciata una funzione atta al calcolo dei nuovi valori di abilità dei giocatori. Questa scorre la lista dei giocatori e per ognuno di essi la lista degli avversari e applica per ogni partita le formule descritte nel paragrafo precedente. E' da notare che per ogni per ogni partita viene aggiornato solo il valore del giocatore A ma non quello del giocatore B: questo sarà fatto il Player corrente sarà il giocatore B. Questo accorgimento è stato necessario per rendere la funzione attinente al metodo nel caso in cui il giocatore giochi più di una partita tra due calcoli successivi delle abilità(cosa molto probabile visto che un giocatore durante un torneo gioca più di una partita al giorno e non è detto che non possa giocare più tornei nello stesso giorno).

Dopo il calcolo vengono stampati i nuovi valori di media e varianza per ogni giocatore.

Progetto

Archivio del progetto: http://www.skenz.it/traduttori/tesine/materiale/pgn/tesina.tar.gz

L'archivio contiene i seguenti file:

  • scanner.jflex
  • parser.cup
  • Main.java
  • Player.java
  • Opponent.java
  • cupper

L'ultimo file è uno script bash atto alla compilazione di tutte le parti del progetto utilizzando il solo comando:

./cupper scanner.jflex parser.cup Main.java <file_di_test>

Scanner

Per realizzare lo scanner, sono state implementati due wrapper in grado di restituire al parser, in caso di errore, informazioni relative alla riga e alla colonna in cui esso è avvenuto. Inoltre, dato che le informazioni relative al valore medio e alla varianza associate a un giocatore sono inserite nel file pgn all'interno di appositi commenti, è stato creato uno stato esclusivo TAG in cui si potessero riconoscere tali variabili. Per il resto, la struttura dello scanner è discretamente semplice, in quanto è in grado di riconoscere i vari campi di intestazione, le mosse normali come un movimento o una cattura o le mosse speciali come un arrocco o una promozione e gli eventuali indicatori della qualità della mossa.

Parser

La struttura del parser è decisamente più complessa di quella dello scanner, in parte causa della necessità di tradurre le ambiguità presenti nello standard in regole precise, in parte causa della molteplicità dello regole presenti nel gioco degli scacchi.

Grammatica

Sono stati definiti come simboli terminali tutti i simboli direttamente restituiti dallo scanner, mentre i simboli non terminali e i loro tipi sono stati dettati dalle specifiche del formato PGN.

Il file che viene dato in pasto al parser può contenere diverse partite, e ognuna di esse deve presentare i 7 campi di intestazione (evento, luogo, data, round, bianco, nero, risultato), la liste delle mosse ed il risultato della partita; i campi di intestazione devono essere tutti racchiusi da parentesi quadre: in particolare, i campi White e Black possono essere seguiti dai simboli terminali relativi al rank e alla varianza del giocatore.

Ogni turno è composto dalla mossa del bianco seguita dalla mossa del nero(l'unica eccezione si può avere nell'ultimo turno). Nella regola che definisce il turno sono stati inseriti alcuni marker, che passano alla semantica una variabile per specificare se la mossa sia del bianco o del nero.

La singola mossa, oltre alla possibile presenza dell'indicatore di qualità, può presentare simboli addizionali in caso di scacco o di scacco matto; generalmente può essere una mossa di movimento, una mossa di cattura, un arrocco o una promozione. Mentre per l'arrocco e per la promozione le regole sono abbastanza intuitive, quelle riguardanti il movimento e la cattura hanno richiesto una più attenta fase di analisi e di progetto, soprattutto per poter garantire una grammatica non ambigua e completamente priva di conflitti.

Semantica

Innanzitutto, è stata inserita all'interno della sezione "parser code" una porzione di codice in grado di gestire gli errori e di segnalare su standard output in quale riga e colonna sia accaduto; il resto del codice relativo alla semantica è stato invece inserito nella sezione "action code".

La struttura dati scelta per rappresentare la scacchiera è stata una matrice bidimensionale, riempita dall'indice che specifica il tipo del pezzo e il suo colore. Questa scelta è motivata dall'estrema complessità dei movimenti dei vari pezzi sulla scacchiera e dalla difficoltà a immaginare geometricamente la scacchiera scorrendo una lista o utilizzando una hashmap.

Per ogni mossa restituita dallo scanner, sono state realizzate funzioni che analizzassero la correttezza della mossa: per la promozione la funzione promotion(), per l'arrocco corto la funzione kingSideCastle() e per l'arrocco lungo la funzione queenSideCastle(). Per tutte le altre mosse è stata implementata la funzione isMoveLegal(), che a seconda del pieceId che riceve lancia una istanza diversa: se il pezzo è un pedone, lancia pawnMove(), se è un cavallo knightMove(), se è un alfiere bishopMove(), se è una torre rookMove(), se è una donna queenMove() e se è un re kingMove(). Ognuna di queste funzioni riceve lo stesso pieceId in modo da poter caratterizzare eventuali diversi comportamenti causati dal colore.

Main

Lo scopo del main è estremamente semplice, in quanto esso non deve fare altro che creare una istanza lo scanner, una istanza del parser e avviare il parser. Nel nostro caso è stato utilizzato un main.java fornito come soluzione di una esercitazione di laboratorio.

Componenti

I componenti necessari per il corretto funzionamento del programma sono :

Note

Personal tools