Chess

By Robert Laing

In its beginning, Computer Chess was called the Drosophila of Artificial Intelligence. — www.chessprogramming.org

checkmate(Player) :- 
  true(control(Player)), 
  true(check(Player, _Ptype, _X, _Y)), 
  stuck(Player).

A bug in checkmate above caused chess.pl not to see the winning move in this puzzle:

State = [ control(white), 
  cell(a,1,b),cell(a,2,b),cell(a,3,b),cell(a,4,b),cell(a,5,b),cell(a,6,b),cell(a,7,bk),cell(a,8,b),
  cell(b,1,b),cell(b,2,b),cell(b,3,b),cell(b,4,b),cell(b,5,wp),cell(b,6,bp),cell(b,7,b),cell(b,8,wr),
  cell(c,1,b),cell(c,2,b),cell(c,3,b),cell(c,4,b),cell(c,5,b),cell(c,6,b),cell(c,7,bn),cell(c,8,b),
  cell(d,1,b),cell(d,2,b),cell(d,3,b),cell(d,4,b),cell(d,5,b),cell(d,6,b),cell(d,7,wk),cell(d,8,b),
  cell(e,1,b),cell(e,2,b),cell(e,3,b),cell(e,4,b),cell(e,5,b),cell(e,6,b),cell(e,7,b),cell(e,8,b),
  cell(f,1,b),cell(f,2,b),cell(f,3,b),cell(f,4,b),cell(f,5,b),cell(f,6,b),cell(f,7,b),cell(f,8,b),
  cell(g,1,b),cell(g,2,b),cell(g,3,b),cell(g,4,b),cell(g,5,b),cell(g,6,b),cell(g,7,b),cell(g,8,b),
  cell(h,1,b),cell(h,2,b),cell(h,3,b),cell(h,4,b),cell(h,5,b),cell(h,6,b),cell(h,7,b),cell(h,8,b)
  ],

Legals = [
  [does(white,move(wk,d,7,c,6)),does(black,noop)],
  [does(white,move(wk,d,7,c,7)),does(black,noop)],
  [does(white,move(wk,d,7,c,8)),does(black,noop)],
  [does(white,move(wk,d,7,d,6)),does(black,noop)],
  [does(white,move(wk,d,7,d,8)),does(black,noop)],
  [does(white,move(wk,d,7,e,7)),does(black,noop)],
  [does(white,move(wr,b,8,a,8)),does(black,noop)],
  [does(white,move(wr,b,8,b,6)),does(black,noop)],
  [does(white,move(wr,b,8,b,7)),does(black,noop)],
  [does(white,move(wr,b,8,c,8)),does(black,noop)],
  [does(white,move(wr,b,8,d,8)),does(black,noop)],
  [does(white,move(wr,b,8,e,8)),does(black,noop)],
  [does(white,move(wr,b,8,f,8)),does(black,noop)],
  [does(white,move(wr,b,8,g,8)),does(black,noop)],
  [does(white,move(wr,b,8,h,8)),does(black,noop)]
].

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:

1. chess.kif
2. alexChess.kif

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

; Legal Move when you are:
; 1) NOT in check
; 2) NOT moving your King
; 3) NOT capturing
(<= (legal ?player (move ?piece ?u ?v ?x ?y))
    (true (control ?player))
    (not (in_check ?player))
    (piece_owner_type ?piece ?player ?ptype)
    (distinct ?ptype king)
    (true (cell ?u ?v ?piece))
    (legal2 ?player (move ?piece ?u ?v ?x ?y))
    (true (cell ?x ?y b))
    ;;  Make sure ?player isn't left in check
    (piece_owner_type ?king ?player king)
    (true (cell ?kx ?ky ?king))
    (not (threatened ?player ?kx ?ky ?u ?v))	; (u,v) is location moved from -- ignore it
    )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

; Legal Move when you are:
; 1) NOT in check
; 2) NOT moving your King
; 3) CAPTURING
(<= (legal ?player (move ?piece ?u ?v ?x ?y))
    (true (control ?player))
    (not (in_check ?player))
    (piece_owner_type ?piece ?player ?ptype)
    (distinct ?ptype king)
    (true (cell ?u ?v ?piece)) ; missing from original, not sure why
    (legal2 ?player (move ?piece ?u ?v ?x ?y))
    (occupied_by_opponent ?x ?y ?player)
    ;;  Make sure ?player isn't left in check
    (piece_owner_type ?king ?player king)
    (true (cell ?kx ?ky ?king))
    (not (threatened_with_capture ?player ?x ?y ?kx ?ky ?u ?v))	; (u,v) is location moved from -- ignore it
    )

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])`.