Modeling of Chess in Prolog

I started modeling Chess in Prolog this weekend. This work was not finished and I might be moving to something else before I do that, so I'll explain things so far.

Whole interest into chess isn't about chess at all. The intent is to explore interactive logic programming.

Describing every game of chess

For the purpose it's not sufficient to only describe the valid moves in the game. We need to logically describe how the game proceeds. To do this I have to introduce a concept of channel that lets the system to send and receive values.

I represent it with the A{...}B -construct.

The resulting program for the chess look like this:

; Players are taking turns.
chess(Game1, Board1) :-
  Game1{send Action, receive Response}Game2,
  move(Board1, white, Action),
  move(Action, black, Response),
  chess(Game2, Response).

; The white loses to the black player.
chess(Game1, Board) :-
  checkmate(Board, white),
  Game1{},
  fail.

; The white wins against the black.
chess(Game1, Board) :-
  move(Board, white, Victory),
  checkmate(Victory, black),
  Game1{send Victory}.

The checkmate and the movement require their implementations.

The checkmate is conceptually easy:

checkmate(Board, Player) :-
  \+(move(Board, Player, _)).

This means that the game is lost when the player can no longer do a proper move.

In the movement we have to describe how you can't do a move if it allows the enemy to capture your king on his turn.

In a naive way you could probably express this like..

move(A, Player, B) :-
  possible_move(A, Player, B),
  opponent(Player, Other),
  \+(
    possible_move(B, Other, C),
    \+(member(piece(Player, king, _, _), C))).

This literally means that if there's an opponent move that results in the king being captured, then this possible movement doesn't count as a valid move.

To do this better we may have to keep a list of the movements. This is necessary anyway because we cannot model the En-passant without a list of moves.

The En-passant is a move which allows you to capture a pawn that did the initial two steps instead of one.

.r.h.b.q.k.b.h.r. imaginary situation
.p.p.p.p.p._.p.p.
._._._._._._._._.
._._._._._._._._.
._._._._._.p._._.
._._._._._._._._.
.p.p.p.p.p.p.p.p.
.r.h.b.q.k.b.h.r.

.r.h.b.q.k.b.h.r. the black player moves his pawn two steps.
.p.p.p.p.p._.p.p.
._._._._._._._._.
._._._._._._._._.
._._._._.p.p._._.
._._._._.|._._._.
.p.p.p.p.|.p.p.p.
.r.h.b.q.k.b.h.r.

.r.h.b.q.k.b.h.r. This is the en-passant, you can capture
.p.p.p.p.p._.p.p. the pawn as if it had done just one step.
._._._._._._._._.
._._._._._._._._.
._._._._._./._._.
._._._._.p._._._.
.p.p.p.p._.p.p.p.
.r.h.b.q.k.b.h.r.

I remember having hit by this at least once. Somebody must have thought that the game was way too simple.

Initial board configuration

The initial board is easily described like this:

initial(piece(white, rook,   1, 1)).
initial(piece(white, knight, 2, 1)).
initial(piece(white, bishop, 3, 1)).
initial(piece(white, queen,  4, 1)).
initial(piece(white, king,   5, 1)).
initial(piece(white, bishop, 6, 1)).
initial(piece(white, knight, 7, 1)).
initial(piece(white, rook,   8, 1)).
initial(piece(white, pawn,   X, 2)) :-
    between(1, 8, X).

initial(piece(black, rook,   1, 8)).
initial(piece(black, knight, 2, 8)).
initial(piece(black, bishop, 3, 8)).
initial(piece(black, queen,  4, 8)).
initial(piece(black, king,   5, 8)).
initial(piece(black, bishop, 6, 8)).
initial(piece(black, knight, 7, 8)).
initial(piece(black, rook,   8, 8)).
initial(piece(black, pawn,   X, 7)) :-
    between(1, 8, X).

To generate it user can use Prolog's 'findall':

initial_board(Board) :-
    findall(Piece, initial(Piece), Board).

The board ends up being a list of all the pieces.

Opponents

This describes that the white is the opponent of the black, and the black is the opponent of the white.

opponent(white, black).
opponent(black, white).

Vacancy

To describe where a piece can be moved, it suffices to tell where the edges of the board are, and check that there's not an another piece on the way.

vacant(X, Y, Board) :-
  between(1, 8, X),
  between(1, 8, Y),
  \+(member(piece(_, _, X, Y), Board)).

Capture

When describing the capture of individual pieces, it has to be told that you can only capture opponent's pieces and the piece ends up being replaced by an another.

capture(piece(Color, Which, X, Y), Motion, End) :-
  opponent(Color, Other),
  select(piece(Other, _, X, Y),     Motion, Motion2),
  End = [piece(Color, Which, X, Y) | Motion2].

I originally used the same command to remove and introduce a piece. Use of a list would seem to be a bad move anyway. We would have to be able of describing our board as a set instead.

place(Piece, Motion, End) :-
  End = [Piece | Motion].

If the placement of a piece was described like the removal is described, it would mean that the interpreter can permute the board's representation to get the same moves structured in different ways.

Knight's movements

Knight's possible moves are easiest to describe.

possible_move(Board, Color, End) :-
  select(piece(Color, knight, X, Y), Board, Motion),
  (
    N_X is X + 1, N_Y is Y + 2;
    N_X is X - 1, N_Y is Y + 2;
    N_X is X + 1, N_Y is Y - 2;
    N_X is X - 1, N_Y is Y - 2;
    N_X is X + 2, N_Y is Y + 1;
    N_X is X - 2, N_Y is Y + 1;
    N_X is X + 2, N_Y is Y - 1;
    N_X is X - 2, N_Y is Y - 1
  ),
  (
    vacant(N_X, N_Y, Board),
    place(piece(Color, knight, N_X, N_Y), Motion, End)
    ;
    capture(piece(Color, knight, N_X, N_Y), Motion, End)
  ).

Prolog's extralogical features are starting to take a toll here. I'm planning to use the rules with TAU prolog so I am not willing to use a constraint solver on the numerical variables.

Unfortunately it also means that I cannot ask all the questions I could ask from a full chess-model. Tinkering with such model could be almost as fun as actually playing the game.

There are six different characters in total and some of their movements are similar. Also some special moves are present. I think those special moves would be the easiest to explain through prolog, whereas they would probably take most effort in the other languages.

Little bit of dirty Prolog for formatting boards.

To draw the boards in SWI-Prolog I also wrote a little bit of imperative code in Prolog. I know that someone else might want to draw chess boards into a console as well, so it's inevitable that someone wants this. Here it is for you, whoever you are.

draw_board(Board) :-
  nl, draw_row(1, 1, Board), nl.

draw_row(X, Y, Board) :-
  X =< 8,
  draw_piece(X, Y, Board),
  X1 is X+1,
  draw_row(X1, Y, Board).
draw_row(9, Y, Board) :-
  Y =< 7,
  nl,
  Y1 is Y+1,
  draw_row(1, Y1, Board).
draw_row(9, 8, _) :-
  nl.

draw_piece(X, Y, Board) :-
  X == 1,
  write('    .'),
  draw_piece_on_board(X, Y, Board),
  write('.').

draw_piece(X, Y, Board) :-
  X > 1,
  draw_piece_on_board(X, Y, Board),
  write('.').

draw_piece_on_board(X, Y, Board) :-
  ( member(piece(_, Which, X, Y), Board) ->
    letter(Which, Letter),
    write(Letter)
    ;
    write('_')
  ).

letter(bishop, 'b').
letter(king,   'k').
letter(knight, 'h').
letter(pawn,   'p').
letter(queen,  'q').
letter(rook,   'r').

Enjoy yourselves. It's not fast but it does the job, well you could say that about all of the Prolog code here. You can test it with the initial_board.

I think that the dirty code shows something about Prolog. When you step out and start writing code in the imperative style, it becomes convoluted and difficult to follow what is happening there.

If you're careful with the guards and nondeterminism you can do it. This is the problem though.

Prolog is supposed to be a language that doesn't keep you on your toes with its oddball antics, yet the imperative operation it requires for side-effects is exactly this kind of a feature.

Why interactive logic programming?

The chess(Game, Board) describes every game where the white player wins. Also the Game1{send Action, receive Response}Game2 is from the viewpoint of the white player.

Note that we describe every possible game here. The chess(Game, Board) is a type for describing every game of chess ever played and every move made in those games.

Theoretically this notation would be sufficient for implementing a communicating Prolog interpreter. It could use minimax and alpha beta pruning to decide the next move it does. It would know the correct and valid moves and probably beat some players in this game.

You may spot one disrepancy here. If the opponent does a wrong move, the machine loses. That's because we represent the loss with the fail and do not describe responsibilities any other way.

If you could easily describe a system that can play chess, would that be something to motivate to look into interactive logic?

Of course, first we would need ways to describe interactions through logic. Japaridze seems to have done a fitting logic for this purpose.

I'm sorry that the chess program isn't finished here. Maybe I'll get it finished later.

Similar posts