Chess
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.
State description
chess.kif
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
is 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.
alexChess.kif
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
GDL predicates.
Figuring out legal moves
In GDL, the bases in the current state are assumed to be globally available as true(Base). This means next(Base),
legal(Role, Move), goal(Role, Utility), and terminal don’t need to have the state passed as an argument.
Furthermore, 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.
chess.kif
|
|
|
|
(<= (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])`.