Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e...

14
Chess Game Chess Game Visualizer Visualizer Un interprete per Un interprete per Short Algebraic Short Algebraic Notation Notation Progetto per l’esame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08 by Niko Mennucci

Transcript of Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e...

Page 1: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Chess Game VisualizerChess Game Visualizer

Un interprete per Un interprete per

Short Algebraic NotationShort Algebraic Notation

Progetto per l’esame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08

by Niko Mennucci

Page 2: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Motivazioni, Obiettivi e Strumenti

• Motivazioni: Per migliorare il proprio stile di gioco negli scacchi è fondamentale studiare le partite dei grandi campioni. Esiste una notazione internazionale standard per registrare partite di scacchi in forma testuale che però risulta piuttosto noiosa da leggere.

• Obiettivo: Creare un’applicazione che visualizzi in formato grafico la sequenza di mosse di una partita di scacchi registrata secondo lo standard noto in letteratura come “Short Algebraic Notation”.

• Strumenti usati: Java 1.6 ed Eclipse come IDE, JavaCC 4.1d1 + JTB 1.3.2 (plug-in per Eclipse 3.3).

Page 3: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Short Algebraic Notation (1/4)

• Ogni casa è identificata da un’unica coppia Lettera-Numero cui corrisponde la coppia File-Rank (Colonna-Traversa) .

• I pezzi vengono indicati con una lettera maiuscola: K,Q,R,B,N (King, Queen, Rook, Bishop, Knight).

• I pedoni non sono indicati con lettere ma, come vedremo, dalla loro assenza.

Page 4: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Short Algebraic Notation (2/4)

• Le mosse sono indicate con la lettera del pezzo che muove seguita dalla casa destinazione. Es: Nf5 significa cavallo muove in f5, e5 pedone muove in e5.

• Se due (o più) pezzi identici possono muovere nella stessa casa, l’iniziale del pezzo è seguita dalla traversa o colonna di partenza per cui si differenziano o entrambi, se da soli non sufficienti (puo’ accadere con 3 o più pezzi). Es: N4f5 cavallo dalla traversa 4 muove in f5, Ndf5 cavallo dalla colonna d muove in f5.

• Se un pezzo effettua una cattura viene messa una x tra casa di partenza e casa destinazione. Es: Nxf5 cavallo muove e cattura in f5, N4xf5 cavallo dalla traversa d muove cattura in f5.

Page 5: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Short Algebraic Notation (3/4)

• Quando un pedone muove in ultima traversa (promozione) il pezzo scelto è indicato dopo la mossa, eventualmente preceduto da = (Es: e8=Q oppure e8Q promozione a regina).

• Arrocco corto e arroco lungo sono indicati rispettivamente con O-O e O-O-O.

• Ogni mossa che porta a mettere sotto scacco è seguita da un +.

• Ogni mossa che porta ad uno scaccomatto è seguita da un # (o anche ++).

• Es: Ngf3+ cavallo da colonna g muove in f3, scacco.

Page 6: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Short Algebraic Notation (4/4)

• Ad ogni mossa può seguire un commento espresso con dei simboli (!! mossa eccellente, ! interessante etc…).

• Alla fine della lista mosse si può indicare il risultato (1-0 vince il bianco, 0-1 vince il nero, ½-½ patta).

• La lista mosse prevede il formato Numero progressivo.-semimossa bianco-semimossa nero, con uno (ed uno solo) spazio come separatore fra mosse e semimosse.

• Es: 1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 … Lo spazio tra . e semimossa bianco è opzionale.

Page 7: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

La grammatica

• Scope ::= ListOfMove [EndGame] <EOF>• StartMove ::= <NUM> [“ “]• ListOfMove ::= (StartMove HalfMove “ “ HalfMove)*

[StartMove HalfMove“ “]• HalfMove ::= (NormalHalfMove | PawnHalfMove | Castlings)

[<CHECK> | <CHECKMATE>] [<COMMENT>]• NormalHalfMove ::= NormalPiece [<FILE> | <RANK> | <FILE><RANK> ]

[<CAPTURE>] <FILE><RANK>• PawnHalfMove ::= < FILE> (<RANK> |

<CAPTURE><FILE><RANK> [<ENPASSANT>] ) [Promotion]

• Castlings ::= “O-O” | “O-O-O”• Promotion ::=[“=“] NormalPiece • NormalPiece ::= <KING> | <QUEEN> | <ROOK> | <BISHOP> | <KNIGHT>• EndGame ::= <WHITE_WINS> | <BLACK_WINS> | <DRAW>

Casa partenza (opzionale)

Casa Destinazione (obbligatorio)

Differenzia mosse di pedoni da mosse di altri pezzi

Spinta di pedone

Cattura con pedone

Page 8: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

La grammatica

• La grammatica non è nella forma regolare ma non presenta self-embedding e quindi il linguaggio generato sarà sicuramente di tipo 3.

• Non c’è bisogno di riscrivere la grammatica nella forma regolare visto che gli strumenti automatici usati per il parser applicano comunque l’analisi ricorsiva discendente.

• La grammatica prevede anche ε-rules in quanto una partita (sopratutto nei tornei) può non essere giocata affatto (ad esempio per abbandono o per accordo) e può essere interrotta.

• Essendo il linguaggio di tipo 3 sicuramente sarà possibile rendere la grammatica LL(1).

• Scritta così però presenta alcuni conflitti: bisogna manipolare alcune produzioni…

Page 9: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

La grammatica LL(1)

• La produzioneListOfMove ::= (StartMove HalfMove “ “ HalfMove)*

[StartMove HalfMove “ ”]

• Presenta un conflitto risolvibile riscrivendola in questo modo (piuttosto illegibile):ListOfMove ::= StartMove HalfMove “ “

[ HalfMove “ “ [ListOfMove] ]

• Così facendo viene a mancare la possibilità di lista mosse vuota. Per motivi di leggibilità si è deciso di riscrivere la regola dello Scope per comprenderla:

Scope ::= [ListOfMove] [EndGame] <EOF>

Page 10: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

La grammatica LL(1)

La produzioneNormalHalfMove ::= NormalPiece [<FILE> | <RANK> | <FILE><RANK>]

[<CAPTURE>]<FILE><RANK>Non rende la grammatica LL(1). Infatti, riscrivendola, si notano i conflitti:NormalHalfMove::=NormalPiece (

<FILE> [<CAPTURE>] <FILE><RANK> |<CAPTURE><FILE><RANK> |<FILE><RANK> |<FILE><RANK> [<CAPTURE>] <FILE><RANK> |<RANK> [<CAPTURE>] <FILE><RANK> )

Fattorizzando 2 volte si risolve il problema:NormalHalfMove::=NormalPiece (

<FILE> ( [<CAPTURE>] <FILE><RANK> | <RANK> [ [<CAPTURE>]<FILE><RANK> ] ) |

<CAPTURE><FILE><RANK> |<RANK> [<CAPTURE>] <FILE><RANK> )

Page 11: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

ArchitetturaDefinisce l’oggetto Chessboard ( la scacchiera virtuale) e contiene la tassonomia dei pezzi.

Tassonomia delle mosse: ogni mossa mette a disposizione i metodi make() e undo() che lanciano eccezioni se non valide.

Definisce l’oggetto ChessGame che gestisce la scacchiera virtuale e la lista delle mosse.

Definisce il visitor ChessGameVisitor che esplora l’APT e restituisce un oggetto ChessGame.

Contiene inoltre il main dell’ applicazione.

Gestisce la Visualizzazione di un oggetto ChessGame.

Gestisce un piccolo editor di testo.

Contiene le classi dell’APT (generato automaticamente).

Contiene la grammatica EBNF.

Gestisce il lexer (generato automaticamente).

Contiene gli scheletri dei visitor (generato automaticamente).

Page 12: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Il Visitor

• Utilizza lo scheletro GJNoArguDepthFirst<R> creato da JTB che permette di restituire un oggetto (ChessGame nel nostro caso) ed effettuare una visita in profondità dell’APT.

• Durante la costruzione dell’oggetto ChessGame ‘gioca’ l’intera partita facendo controlli semantici. Controlla se le mosse siano valide e se le varie indicazioni di scacco, scaccomatto, cattura, fine partita etc.. siano congruenti.

• Nel caso ci siano errori semantici restituisce anche dei warnings con indicazione della posizione.

• Gli errori semantici non pregiudicano la costruzione dell’oggetto ChessGame che viene restituito comunque (costruito fin dove possibile).

Page 13: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Collaudo

• Si è effettuato un collaudo sulla tassonomia delle mosse per verificare l’esattezza dei controlli sulla validità delle mosse per ogni pezzo (in piccolo main di collaudo per ogni pezzo).

• Sul web vi è una grande quantità di partite registrate, famose e non.

• Ne sono state scaricate alcune per vedere la bontà dell’applicazione su registrazioni corrette.

• In un secondo momento sono state apportate leggere modifiche a queste ultime per verificare la correttezza dei controlli semantici da parte del visitor.

Page 14: Chess Game Visualizer Un interprete per Short Algebraic Notation Progetto per lesame di Linguaggi e modelli computazionali LS prof. Denti – A.A. 2007/08.

Sviluppi Futuri

• Sviluppo di un’applicazione in grado di leggere file in formato pgn (Portable Game Notation). Tale notazione prevede ulteriori informazioni sulla partita (nome dei giocatori, luogo della sfida, anno etc) e la possibilità di registrare partite già iniziate con la notazione FEN (Forsyth-Edwards Notation).

• Sviluppo di un’ applicazione che faccia giocare una partita fra due giocatori e preveda la registrazione della stessa in Short Algebraic Notation.

• Sviluppo di un’ intelligenza artificiale che permetta di giocare contro il computer.