ArchitectureThe overall architecture of our checkers game will consist of the following modules:
- The two colors (players) in the game and their relation (opponents).
- The four kinds of pieces in the game and functions over them (namely, kinging).
- A representation of the position of a piece, and predicates defining useful relationships between positions (namely, moving and jumping).
- A representation of the checkers board, predicates about positions on it, predicates about pieces on it, and predicates to modify a board in useful ways (namely, moving, removing, and kinging pieces).
- Predicates to update a board via the patterns described in
- An encoding of the state of a game, a predicate to modify it (by making a move according to the rules of checkers), and predicates to query the state of a game (namely, whether the game has ended, and the result if so).
- Some utility functions for dealing with integers and lists; used primarily by
- The minimax algorithm and related typeclasses.
- A declaration of the game as a minimax problem, with associated heuristics.
- Predicates for printing various game structures in a human-readable format, and obtaining user input.
- The main module, allowing configuration of the game and defining the overall UI.
There are two colors in checkers, corresponding to the two players:
They are related as opponents:
:- type color ---> red; white.
We can also define an
:- pred opponent(color, color). :- mode opponent(in, out) is det. :- mode opponent(out, in) is det. opponent(red, white). opponent(white, red).
opponentfunction for convenience:
That’s it! Short and to-the-point modules are good. We’ll see that most modules in this game are similarly sized.
:- func opponent(color) = color. opponent(Color) = Opponent :- opponent(Color, Opponent).
Pieces come in two colors, defined in
color, and can be either men or kings:
It is also useful to talk about “kinging” a piece; changing a man into a king:
:- import_module color. :- type kind ---> man; king. :- type piece ---> piece(color::color, kind::kind).
This module is also short and sweet.
:- func king(piece) = piece is semidet. king(piece(Color, man)) = piece(Color, king).
A position is simply an X, Y tuple:
It is useful to talk about pieces changing position by moving and jumping. Let’s declare two predicates,
:- type position ---> position(int, int).
jump, which will define the relationship between the starting and ending locations of a piece which moves or jumps, and in the case of a jump, the position which was jumped over.
It will be most useful to know whether a particular change in position describes a move or jump, and given a starting position, what ending positions would result from a move or jump. We will declare two modes, corresponding to these use cases, for each predicate:
:- pred move(piece, position, position). :- pred jump(piece, position, position, position).
Because Mercury provides bidirectional arithmetic (i.e.
:- mode move(in, in, in) is semidet. :- mode move(in, in, out) is multi. :- mode jump(in, in, out, in) is semidet. :- mode jump(in, in, out, out) is multi.
-can deduce the values of one operand if the result is known), we can define these predicates with only one clause each:
Unfortunately any attempt to compact this code results in mode errors. This is because Mercury’s switch detection code is not very robust in the face of complicated switches, and because Mercury seems not to reorder conjunctions to obtain mode-correctness.
:- import_module color. :- import_module int. move(Piece, position(X, Y), position(X + XD, Y + YD)) :- (XD = 1; XD = -1), (Piece = piece(red, man), YD = 1; Piece = piece(white, man), YD = -1; Piece = piece(_, king), YD = 1; Piece = piece(_, king), YD = -1). jump(Piece, position(X, Y), position(X + XD, Y + YD), position(X + XD2, Y + YD2)) :- (XD = 1, XD2 = 2; XD = -1, XD2 = -2), (Piece = piece(red, man), YD = 1, YD2 = 2; Piece = piece(white, man), YD = -1, YD2 = -2; Piece = piece(_, king), YD = 1, YD2 = 2; Piece = piece(_, king), YD = -1, YD2 = -2).
First we define the type of a board, which should contain its width, height, a mapping from position to piece, and (for efficiency) a count (using the handy
bagmodule) of how many of each type of piece is on the board:
Of course we could fix the width and height to 8, but it is easy and interesting to allow for other size boards. Since Mercury automatically generates “getter” functions for
:- import_module color, piece, position. :- import_module bag, int, map. :- type board ---> board( width::int, height::int, positions::map(position, piece), counts::bag(piece) ).
height, we need only declare them in our interface, even if we choose to hide the type of
Another trivial but important state accessor is
:- func width(board) = int. :- func height(board) = int.
count_pieces, which counts the number of a given kind of piece on the board:
This function is implemented using the bag we added to the
:- func count_pieces(board, piece) = int. count_pieces(Board, Piece) = count_value(Board^counts, Piece).
boardtype so that it may be quickly executed by our heuristic function (defined later).
Initializing the boardNext we define how to initialize a board of a given size:
:- func init(int, int) = board. init(Width, Height) = !:Board :- !:Board = board(Width, Height, init, init), fold_up(init_row(piece(red, man)), 0, Height / 2 - 2, !Board), fold_up(init_row(piece(white, man)), (Height + 1) / 2 + 1, Height - 1, !Board).
int.fold_uppredicate used here is Mercury’s idea of a for loop.
legal_position(defined later) to iterate over the valid positions in a row:
Note that we call
init_row(Piece, Y, !Board) :- aggregate( (pred(Pos::out) is nondet :- legal_position(!.Board, position(_, Y) @ Pos)), (pred(Pos::in, !.Board0::in, !:Board0::out) is det :- !Board0^positions := det_insert(!.Board0^positions, Pos, Piece), !Board0^counts := insert(!.Board0^counts, Piece)), !Board).
legal_positionwith a partially instantiated position,
position(_, Y), which is also bound to
Pos. This means that we need a mode of
legal_positionwhich can fill in valid X coordinates of a given row.
Legal positions on the boardHere is a suitable declaration of
All those modes! Beside the modes where the
:- pred legal_position(board, position). :- mode legal_position(in, in) is semidet. :- mode legal_position(in, out) is nondet. :- mode legal_position(in, bound(position(ground, free)) >> ground) is nondet. :- mode legal_position(in, bound(position(free, ground)) >> ground) is nondet.
out(corresponding to checking a legal position and generating all legal positions), the other two modes work with partially instantiated positions, where we wish to know the legal positions in a given column or row (respectively). Thankfully, all four modes can be implemented with one body:
Unfortunately the predicate
legal_position(Board, position(X, Y)) :- int_in_range(0, Board^height - 1, Y), int_in_range(0, Board^width - 1, X), (even(X), even(Y); odd(X), odd(Y)).
intmodule does not provide a
semidetmode and is thus unsuitable for bidirectional programming. Instead, we declare a similar predicate,
int_in_range, in our
To define this predicate, we can make use of Mercury’s support for defining different clauses for different modes:
:- pred int_in_range(int, int, int). :- mode int_in_range(in, in, in) is semidet. :- mode int_in_range(in, in, out) is nondet.
Because we know that these two clauses are logically equivalent, we promise such to Mercury using
:- pragma promise_equivalent_clauses(int_in_range/3). int_in_range(Lo::in, Hi::in, X::out) :- nondet_int_in_range(Lo, Hi, X). int_in_range(Lo::in, Hi::in, X::in) :- Lo =< X, X =< Hi.
Locating piecesTo query which pieces are at which positions, we declare
piece_athas two modes, one for checking which piece (if any) is at a given position, and one for iterating over all pieces currently on the board:
Our implementation of
:- pred piece_at(board, position, piece). :- mode piece_at(in, in, out) is semidet. :- mode piece_at(in, out, out) is nondet.
piece_atshould be a thin layer over the
positionsmap, but Mercury’s
mapmodule does not provide one predicate which serves both purposes. Again, we can remedy this by using different clauses for each mode:
We can also define
:- pragma promise_equivalent_clauses(piece_at/3). piece_at(Board::in, Position::in, Piece::out) :- search(Board^positions, Position, Piece). piece_at(Board::in, Position::out, Piece::out) :- member(Board^positions, Position, Piece).
no_piece_at, which has an identical signature, as:
no_piece_at(Board, Position) :- legal_position(Board, Position), not piece_at(Board, Position, _).
no_piece_at(…)is not simply
not piece_at(…)! By additionally requiring that
Positionbe a legal position, we restrict the domain of
no_piece_atand thus allow it to output the finite number of positions where no piece exists (as opposed to the infinite number of positions which either have no piece or are not legal).
Modifying the boardThere are three predicates in
boardto modify the board:
remove_piecehave modes which allow for both modifying a given location(s), and for generating all possible such modifications of the board.
king_piecehas only one mode to modify a given location. All three have similar code utilizing state variable field update syntax. Here is the implementation of
king_pieceas an example:
It is my opinion that Mercury would benefit from an extension to state variable update syntax which allows state variable record syntax for data terms. Such a syntax would, in concert with the standard library argument order modifications introduced in Mercury 11.07, allow the above predicate to be written more concisely as:
king_piece(Pos, !Board) :- piece_at(!.Board, Pos, Piece), King = king(Piece), !Board^positions := update(!.Board^positions, Pos, King), !Board^counts := det_remove(!.Board^counts, Piece), !Board^counts := insert(!.Board^counts, King).
(Of course, the update functions allowed to be used with such a syntax must be restricted to those which commute with each other.)
king_piece(Pos, !Board) :- piece_at(!.Board, Pos, Piece), King = king(Piece), update(Pos, King, !Board^positions), det_remove(Piece, !Board^counts), insert(King, !Board^counts).
ReviewThat’s all for now, this post is long enough! Today we saw the overall structure of our checkers AI – ten small modules – and the implementations of
board, the modules defining the “parts” of the game. Next week we’ll see the implementations of the “rules” and “brains” of the game.