Tuesday, November 29, 2011

Checkers AI, part 1

Logic languages such as Mercury love search problems. Game artifical intelligence is a great application of searches. AIs for many zero-sum two-player board games, such as checkers and chess, can be implemented as a minimax search; a search which assumes that each player makes a move which maximally benefits himself. In today’s post, I’d like to walk through modeling checkers in Mercury.

Architecture

The overall architecture of our checkers game will consist of the following modules:
color
The two colors (players) in the game and their relation (opponents).
piece
The four kinds of pieces in the game and functions over them (namely, kinging).
position
A representation of the position of a piece, and predicates defining useful relationships between positions (namely, moving and jumping).
board
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).
moves
Predicates to update a board via the patterns described in position.
game
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).
util
Some utility functions for dealing with integers and lists; used primarily by minimax.
minimax
The minimax algorithm and related typeclasses.
heuristic
A declaration of the game as a minimax problem, with associated heuristics.
game_io
Predicates for printing various game structures in a human-readable format, and obtaining user input.
checkers
The main module, allowing configuration of the game and defining the overall UI.
This architecture ensures that modules are loosely coupled and small in size (< 120 loc each, average ~ 60 loc), making modifications and debugging easy. A similar overall architecture should prove useful for other game AI implementations. Let’s go into each module in detail. In today’s post, we’ll focus on color, piece, position, and board.

color module

There are two colors in checkers, corresponding to the two players:
:- type color ---> red; white.
They are related as opponents:
:- pred opponent(color, color).
:- mode opponent(in, out) is det.
:- mode opponent(out, in) is det.

opponent(red, white).
opponent(white, red).
We can also define an opponent function for convenience:
:- func opponent(color) = color.
opponent(Color) = Opponent :- opponent(Color, Opponent).
That’s it! Short and to-the-point modules are good. We’ll see that most modules in this game are similarly sized.

piece module

Pieces come in two colors, defined in color, and can be either men or kings:
:- import_module color.
:- type kind ---> man; king.
:- type piece ---> piece(color::color, kind::kind).
It is also useful to talk about “kinging” a piece; changing a man into a king:
:- func king(piece) = piece is semidet.
king(piece(Color, man)) = piece(Color, king).
This module is also short and sweet.

position module

A position is simply an X, Y tuple:
:- type position ---> position(int, int).
It is useful to talk about pieces changing position by moving and jumping. Let’s declare two predicates, move and 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.
:- pred move(piece, position, position).
:- pred jump(piece, position, position, position).
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:
:- 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.
Because Mercury provides bidirectional arithmetic (i.e. + and - can deduce the values of one operand if the result is known), we can define these predicates with only one clause each:
:- 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).
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.

board module

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 bag module) of how many of each type of piece is on the board:
:- import_module color, piece, position.
:- import_module bag, int, map.

:- type board --->
    board(
        width::int,
        height::int,
        positions::map(position, piece),
        counts::bag(piece)
    ).
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 width and height, we need only declare them in our interface, even if we choose to hide the type of board:
:- func width(board) = int.
:- func height(board) = int.
Another trivial but important state accessor is count_pieces, which counts the number of a given kind of piece on the board:
:- func count_pieces(board, piece) = int.
count_pieces(Board, Piece) = count_value(Board^counts, Piece).
This function is implemented using the bag we added to the board type so that it may be quickly executed by our heuristic function (defined later).

Initializing the board

Next 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).
The int.fold_up predicate used here is Mercury’s idea of a for loop. init_row uses solutions.aggregate and legal_position (defined later) to iterate over the valid positions in a row:
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).
Note that we call legal_position with a partially instantiated position, position(_, Y), which is also bound to Pos. This means that we need a mode of legal_position which can fill in valid X coordinates of a given row.

Legal positions on the board

Here is a suitable declaration of legal_position:
:- 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.
All those modes! Beside the modes where the position argument is in and 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:
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)).
Unfortunately the predicate nondet_int_in_range in Mercury’s int module does not provide a semidet mode and is thus unsuitable for bidirectional programming. Instead, we declare a similar predicate, int_in_range, in our util module:
:- 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.
To define this predicate, we can make use of Mercury’s support for defining different clauses for different modes:
:- 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.
Because we know that these two clauses are logically equivalent, we promise such to Mercury using promise_equivalent_clauses.

Locating pieces

To query which pieces are at which positions, we declare piece_at. piece_at has 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:
:- pred piece_at(board, position, piece).
:- mode piece_at(in, in, out) is semidet.
:- mode piece_at(in, out, out) is nondet.
Our implementation of piece_at should be a thin layer over the positions map, but Mercury’s map module does not provide one predicate which serves both purposes. Again, we can remedy this by using different clauses for each mode:
:- 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).
We can also define no_piece_at, which has an identical signature, as:
no_piece_at(Board, Position) :-
    legal_position(Board, Position),
    not piece_at(Board, Position, _).
Note that no_piece_at(…) is not simply not piece_at(…)! By additionally requiring that Position be a legal position, we restrict the domain of no_piece_at and 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 board

There are three predicates in board to modify the board: move_piece, remove_piece, and king_piece. move_piece and remove_piece have modes which allow for both modifying a given location(s), and for generating all possible such modifications of the board. king_piece has 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_piece as an example:
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).
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),
    update(Pos, King, !Board^positions),
    det_remove(Piece, !Board^counts),
    insert(King, !Board^counts).
(Of course, the update functions allowed to be used with such a syntax must be restricted to those which commute with each other.)

Review

That’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 color, piece, position, and board, the modules defining the “parts” of the game. Next week we’ll see the implementations of the “rules” and “brains” of the game.

Wednesday, November 9, 2011

Making the grade

I know it’s been a while since my last post, but I have something fantastic in the works, I promise. Today though I’d like to talk about the compiler grades.

Common grades

Compiler grades correspond roughly to combinations of different backends (e.g. C or Java) and code models (e.g. parallel or debugging). Those of you new to the language may be confounded by the immense number of these grades, and when initially compiling Mercury it can be difficult to decide which grades to enable. Here’s a list of the ones I use most. In parentheses next to the grade names are the options needed to select the grade, assuming that asm_fast.gc is the default (it usually is).
asm_fast.gc (default)
This is my default go-to grade. It compiles to low-level C code using the Boehm garbage collector and supports concurrency (though not parallelism). It is therefore very fast, can interface seamlessly with C libraries, and can run code that uses threads.
asm_fast.par.gc.stseg (--parallel --stack-segments)
This grade adds parallelism and stack segmentation to the asm_fast.gc grade. Parallelism allows programs to make use of multiple cores (though note that this isn’t necessary if all you need is concurrent execution). Stack segmentation allows pieces of the stack to be allocated on the heap. Beside allowing programs to grow beyond a fixed stack size, this option (only available for the asm_fast grades) greatly reduces the amount of memory allocated by thread spawns, which can otherwise measure in the gigabytes. Both these features come at a small runtime cost.
hlc.gc (-H)
This is the “high-level C” grade. It compiles to C code which is much closer to what a programmer might write than that generated by the asm_fast grade. Curiously this grade is sometimes faster than the low-level grade (likely due to an increased number of optimization opportunities available to GCC), so if you need speed, it is worth testing your application in this grade as well. Unlike asm_fast however, this grade does not support concurrency.
hlc.par.gc (-H --parallel)
This grade adds to hlc.gc support for concurrency and parallelism via native system threads. If your application requires a 1:1 mapping of Mercury threads to system threads, then this grade is a must.
java (--java)
As the name implies, this grade compiles to Java code. It is the only option if you need to interface with Java libraries. Due to the JVM’s speed the code it generates is often as fast as its C counterparts. This grade supports concurrency and parallelism via Java’s built-in threading mechanisms (--parallel is not needed). (Note that unlike in the C grades, a program compiled under the java grade will not wait for all spawned threads to terminate before exiting.) Unfortunately some standard library procedures are not yet implemented.
asm_fast.gc.prof (-p); hlc.gc.prof (-H -p)
These grades allow you to profile your code using mprof, of course at the expense of execution speed. They are handy to have around.
asm_fast.gc.debug (--debug)
This grade allows you to debug your code using mdb. Note that if you’re not debugging the standard library, then instead of compiling this grade, you can instead pass the --trace deep option to the compiler to enable debugging of just your modules.

Compiling extra grades

We all know that the Mercury build process takes forever. This is because it must compile the standard library in each of the required grades. Fortunately there’s a shortcut around this.

The first time you install the system, instead of make install, run make install LIBGRADES=asm_fast.gc. This will install the compiler, but only the default library grade. You can pass LIBGRADES= if you wish instead to install no library grades.

Later, when you wish to install additional grades, run make install_grades LIBGRADES='asm_fast.par.gc hlc.gc' (for example). This will compile only the given library grades. To complete the installation, you should edit /path/to/mercury/lib/mercury/conf/Mercury.config to add the appropriate --libgrade flags to the end of DEFAULT_MCFLAGS (near the end of the file), and /path/to/mercury/lib/mercury/mmake/Mmake.vars to add the grade names to the definition of LIBGRADES. (These steps are only necessary if you plan to build and install libraries.)

Don’t forget also that you can speed up compilation by passing PARALLEL=-j5 (where 5 is one plus the number of parallel cores in your system) to make (or simply -j5 to mmake).

Working with multiple grades

Finally, when testing with multiple grades, you may with to use the --use-grade-subdirs option in conjunction with mmc --make. This will cause mmc --make to use a different subdirectory for each grade in which you build your project, avoiding errors caused by linking incompatible grades, and allowing you not to have to rebuild the entire project each time you switch grades.