By Robert Laing
In its beginning, Computer Chess was called the Drosophila of Artificial Intelligence. — www.chessprogramming.org
Many basic concepts — such as columns are labled a to h, rows are labeled 1 at the bottom (white side) and 8 at the top (black side) — along with a convention for the input signals, called Portable Game Notation (PGN) are established for chess. Though in our case I’m translating these to GDL, there’s a fairly easy way to map between the two.
Another advantage of chess and PGN is many records of games are available from www.chessabc.com or csvn. Having these treasuries of chess games helps in a number of ways, including checking that the chess rules are correct by checking if our state machine accepts the input signals.
At least two versions of chess have been written in GDL:
Chess is quite a bit more complicated than tic-tac-toe, requiring quite a few additional base propositions.
As with any board game, we need a set of propositions describing the board and pieces,
cell(Column, Row, Piece),
and whose turn it is
control(Player). GDL rules often include
step(Count) as a base element of a state,
which among others things protects against cycles. For my implementation, I separate the count from the permantly
stored states to avoid duplications.
Start = [ cell(a,8,br),cell(b,8,bn),cell(c,8,bb),cell(d,8,bq),cell(e,8,bk),cell(f,8,bb),cell(g,8,bn),cell(h,8,br), cell(a,7,bp),cell(b,7,bp),cell(c,7,bp),cell(d,7,bp),cell(e,7,bp),cell(f,7,bp),cell(g,7,bp),cell(h,7,bp), cell(a,6,b),cell(b,6,b),cell(c,6,b),cell(d,6,b),cell(e,6,b),cell(f,6,b),cell(g,6,b),cell(h,6,b), cell(a,5,b),cell(b,5,b),cell(c,5,b),cell(d,5,b),cell(e,5,b),cell(f,5,b),cell(g,5,b),cell(h,5,b), cell(a,4,b),cell(b,4,b),cell(c,4,b),cell(d,4,b),cell(e,4,b),cell(f,4,b),cell(g,4,b),cell(h,4,b), cell(a,3,b),cell(b,3,b),cell(c,3,b),cell(d,3,b),cell(e,3,b),cell(f,3,b),cell(g,3,b),cell(h,3,b), cell(a,2,wp),cell(b,2,wp),cell(c,2,wp),cell(d,2,wp),cell(e,2,wp),cell(f,2,wp),cell(g,2,wp),cell(h,2,wp), cell(a,1,wr),cell(b,1,wn),cell(c,1,wb),cell(d,1,wq),cell(e,1,wk),cell(f,1,wb),cell(g,1,wn),cell(h,1,wr), control(white) ]
In addition to the above, the state needs to “remember* if the king or a castle have moved to know if castling is a legal move, adding the following potential base propositions. The format remembers the starting position, presumbably to differentiate the rooks.
piece_has_moved(wk,e,1),piece_has_moved(bk,e,8), piece_has_moved(wr,a,1),piece_has_moved(br,a,8), piece_has_moved(wr,h,1),piece_has_moved(br,h,8),
To handle en passant,
pawn_moved_two(Pawn, Column) is included in a state, but for only the next state.
Another state base is
check(Player, Piece, Column, Row). Among the things that makes chess more complex than tic-tac-toe
legal(Player, Move) needs to be aware of the set of
next(Base) propositions because it is illegal for a player
to make moves which expose his king to opposing pieces.
The alternative chess rules by Alex Landau reduce the number of bases by only listing pieces, instead of each square, using
piece(Piece, Column, Row) notation.
[ piece(bra,a,8),piece(bnb,b,8),piece(bbc,c,8),piece(bq,d,8),piece(bk,e,8),piece(bbf,f,8),piece(bng,g,8),piece(brh,h,8), piece(bpa,a,7),piece(bpb,b,7),piece(bpc,c,7),piece(bpd,d,7),piece(bpe,e,7),piece(bpf,f,7),piece(bpg,g,7),piece(bph,h,7), piece(wpa,a,2),piece(wpb,b,2),piece(wpc,c,2),piece(wpd,d,2),piece(wpe,e,2),piece(wpf,f,2),piece(wpg,g,2),piece(wph,h,2), piece(wra,a,1),piece(wnb,b,1),piece(wbc,c,1),piece(wq,d,1),piece(wk,e,1),piece(wbf,f,1),piece(wng,g,1),piece(wrh,h,1), control(white) ]
Bases to remember if castling or en passant moves are legal:
whiteHasMovedKing,blackHasMovedKing, whiteHasMovedA1Rook, blackHasMovedA8Rook, whiteHasMovedH1Rook, blackHasMovedH8Rook, canEnPassantInFile(Column)
I prefer the
cell(Row, Column, Piece) representation since each state assumes less background information stored in non-standard
Figuring out legal moves
In GDL, the bases in the current state are assumed to be globally available as
true(Base). This means
goal(Role, Utility), and
terminal don’t need to have the state passed as an argument.
next(Base) assumes the required
does(Role, Move) is globally available.
In Prolog jargon, global variables are in the clausal store, where the current truths can be wiped out using
retractall(true(_)) and then each base in
State = [Base1, Base2, ..., BaseN] could be put, in that order, with
forall(member(Base, State), assertz(true(Base))).
update_true(Game, State) :- retractall(Game:true(_)), forall(member(Base, State), assertz(Game:true(Base))).
I hit a couple of snags with the above. For starters, simply erasing all
true(Base) causes some which are supposed to be
passed unchanged to vanish — for instance the pale squares in checkers or draughts.
My preference has become to work with lists of bases rather than numerous
true(BaseN) in the clausal store. That way the
order the bases are tranformed from Base to Base' remains consistent, else the order of the
next(Base) clauses in the
rules needs very careful thought.
Rather than check for
true(Base), I prefer
memberchk(Base, State), where State needs to be provided as an argument.
Comparing the way non-capturing and capturing legal predicates have been written in chess.kif, it appears the “Don’t repeat yourself” (DRY) rule has been broken. The two are nearly identical except for line 12 which could be simplified to the square moved to must either be blank or occupied by an opposing piece.
Something that complicates chess is a player may not move a piece standing between his king and an enemy queen, rook, or bishop.
The provided code has two versions, threatened and threatened_with_capture, which needs to check the attacking piece hasn’t been removed.
(<= (in_check ?player) (true (check ?player ?ptype ?x ?y)))
This is how I’ve translated this into Prolog, with the addition of a State list of bases to avoid true globals.
legal(State, Player, move(Piece, U, V, X, Y)) :- memberchk(control(Player), State),
The rules need the concept of counting to iterate through columns and rows, and in KIF files this tends to be fairly labourious.
For instance, in chess.kif there are
(succ 1 2) all the way to
succ(200 201) which in SWI Prolog can simply be done with
succ(R1, R2), R1 >= 1, R2 =< 8, …
or alternatively by [nextto(R1, R2, [1,2,3,4,5,6,7,8])](https://www.swi-prolog.org/pldoc/doc_for?object=nextto/3), which also works for columnsnextto(C1, C2, [a,b,c,d,e,f,g,h])`.