The two array whitexpieces and blackpieces store the pieces in the game. A piece is an object of type $PIECE which is explained below. Since both arrays are private, it is a secret of the board implementation in which way pieces are stored.
The board stores information about which color is to play (white_to_play) and about the last move (last_move). Moreover, the board knows whether the white or black king has been moved. This information is necessary, because castle moves are only allowed if the king has not been moved before.
class BOARD is
private attr whitepieces : ARRAY{$PIECE};
private attr blackpieces : ARRAY{$PIECE};
attr white_to_play : BOOL;
attr last_move : MOVE;
attr white_K_moved : BOOL;
attr black_K_moved : BOOL;
create:SAME is
ret::=new;
ret.set_up;
return ret;
end;
The private routine set_up initializes the board. 16 white and 16 black pieces are placed onto the board, the first player is set to be white, both kings have not moved.
private set_up is
position ::= #POS;
white_to_play := true;
-- set up white pieces
whitepieces := #(16);
position.pos := "a2";
loop i::=0.upto!(7);
whitepieces[i] := #PAWN(position,PIECE::white);
position.pos := position.east;
end;
position.pos := "a1"; whitepieces[8] := #ROOK(position,PIECE::white);
position.pos := "b1"; whitepieces[9] := #KNIGHT(position,PIECE::white);
position.pos := "c1"; whitepieces[10] := #BISHOP(position,PIECE::white);
position.pos := "d1"; whitepieces[11] := #QUEEN(position,PIECE::white);
position.pos := "e1"; whitepieces[12] := #KING(position,PIECE::white);
position.pos := "f1"; whitepieces[13] := #BISHOP(position,PIECE::white);
position.pos := "g1"; whitepieces[14] := #KNIGHT(position,PIECE::white);
position.pos := "h1"; whitepieces[15] := #ROOK(position,PIECE::white);
-- set up black pieces
blackpieces := #(16);
position.pos := "a7";
loop i::=0.upto!(7);
blackpieces[i] := #PAWN(position,PIECE::black);
position.pos := position.east;
end;
position.pos := "a8"; blackpieces[8] := #ROOK(position,PIECE::black);
position.pos := "b8"; blackpieces[9] := #KNIGHT(position,PIECE::black);
position.pos := "c8"; blackpieces[10] := #BISHOP(position,PIECE::black);
position.pos := "d8"; blackpieces[11] := #QUEEN(position,PIECE::black);
position.pos := "e8"; blackpieces[12] := #KING(position,PIECE::black);
position.pos := "f8"; blackpieces[13] := #BISHOP(position,PIECE::black);
position.pos := "g8"; blackpieces[14] := #KNIGHT(position,PIECE::black);
position.pos := "h8"; blackpieces[15] := #ROOK(position,PIECE::black);
white_K_moved := false;
black_K_moved := false;
last_move := void;
MAIN::display.redraw(self.str);
end;
Several iters are needed to return all pieces on the board that fulfill a certain condition.
The first iter whitepiece! returns all white pieces, which are still alive. For this purpose, it makes use of the iter elt! in line 52. The iter is provided by the ARRAY library class (see file Library/array.sa). If elt! yields an element, this element is yield to the caller if it fulfills the conditions. However, if elt! quits, this loop is terminated as well, no element is returned to the caller.
private whitepiece!:$PIECE is
loop p ::= whitepieces.elt!;
if ~void(p) and p.alive then yield p; end;
end;
end;
private blackpiece!:$PIECE is
loop
p ::= blackpieces.elt!;
if ~void(p) and p.alive then yield p; end;
end;
end;
The nesting depth of iters can be increased even further, as shown in my_piece below: Within whitepiece! the iter elt! is used. An element found by elt! is returned via whitepiece! and then returned to the caller of my_piece!. Similarly, a quit of elt!, induces a quit of whitepiece!, which in turn results in a quit of my_piece!. The latter terminates the loop, that must surround every call of my_piece! in the caller.
my_piece!:$PIECE is
if white_to_play then
loop
yield whitepiece!;
end;
else
loop
yield blackpiece!;
end;
end;
end;
private opp_piece!:$PIECE is
if white_to_play then
loop
yield blackpiece!;
end;
else
loop
yield whitepiece!;
end;
end;
end;
piece!:$PIECE is
loop
yield whitepiece!;
end;
loop
yield blackpiece!;
end;
end;
One of the secrets of the BOARD implementation is the way pieces are stored. For internal purposes it is necessary, to find out at which position of the arrays a particular piece is stored.
In the private routine index we use a post condition. To assure that the piece p is (dead or alive) on board we test whether the return value result is set appropriately, i.e., whether result is between 0 and 15 upon return. Note, that there may not be a semicolon behind a post condition. The conditions get checked before the routine returns. To access the value that will be returned, Sather provides the predefined results expression. The type of results is determined by the result type of the routine. If checking is desired, it has to be activated with the compiler flag -post <classes>.
The loop (line 97-104) is an excellent example of a loop that is controlled by multiple iters. The first two iters are defined in the ARRAY library class. The iter ind! (line 98) returns the existing indexes of array. As explained above, elt! (line 99) returns the corresponding array elements. For each iteration of the loop the following condition holds: whitepieces[i] = q. Both iters can be expected to yield the same number of times. If the end of the array is encountered, the call to ind! will terminate the loop; elt! will not be called.
However, if the desired piece is found, it is not necessary, to continue the search. To terminate the loop immediately, the predefined iter break! is called in line 102, which will always execute a quit statement.
The same search is implemented differently in the else branch (line 106). Here we use the library routine index_of provided in the ARRAY class. (See file Library/array.sa for details.)
private index(p:$PIECE):INT
post result.is_bet(0,15)
is
ret : INT := -1;
if p.iswhite then
loop
i::= whitepieces.ind!;
q::= whitepieces.elt!;
if p.position = q.position then
ret := i;
break!;
end;
end; -- of loop
else
ret := blackpieces.index_of(p);
end;
return ret;
end; -- private index
To check whether there is a piece on a given position of the board the following routines are provided:
has_piece(pos:POS):BOOL is
ret : BOOL := false;
loop p::=piece!;
if p.position = pos then ret := true; end;
end;
return ret;
end;
has_white_piece(pos:POS):BOOL is
ret : BOOL := false;
loop p::=whitepiece!;
if p.position = pos then ret := true; end;
end;
return ret;
end;
has_black_piece(pos:POS):BOOL is
ret : BOOL := false;
loop p::=blackpiece!;
if p.position = pos then ret := true; end;
end;
return ret;
end;
has_my_piece(pos:POS):BOOL is
if white_to_play then
return has_white_piece(pos);
else
return has_black_piece(pos);
end;
end;
The following two routines return a pointer to a piece at a given position of the board. The routine comes in two versions. The latter can process POS arguments by reducing them to STR parameters which are then processed by the first version.
piece(str:STR):$PIECE is
ret : $PIECE;
position ::= #POS;
position.pos := str;
loop p::=piece!;
if p.position = position then ret := p; end;
end;
return ret;
end;
piece(p:POS):$PIECE is
return piece(p.str);
end;
For interface purposes, a board can represent the status of all pieces in an ASCII representation. The character array is used to transmit the board situation to the ASCII_DISPLAY and via the X_DISPLAY to the external class XCW.
str:ARRAY{CHAR} is
ret::=#ARRAY{CHAR}(65);
loop
ret[0.upto!(63)] := ' ';
end;
ret[64] := '\0';
loop p::=self.whitepiece!;
if ~void(p) and p.alive then
ret[p.position.pos] := p.fig;
end;
end;
loop p::=self.blackpiece!;
if ~void(p) and p.alive then
ret[p.position.pos] := p.fig.lower;
end;
end;
return ret;
end;
After these helper routines and iters have been implemented, the central routines are presented. The routine pos_in_check tests whether a given position could be reached in the next move by the opponent.
In this routine there is again a good example of nested iter calls: The first loop (line 172-179) considers all pieces of the opponent player. The inner loop (line 173-178) then for each of these pieces considers target positions of potential moves. (Is is explained later on, what a move is if the flag for_check_test is set. Just ignore the flag for the time being.)
The call piece.move!() in line 174is a dispatched iter. See
page 
for an alternative implementation that
works with earlier releases of the Sather 1.0 compiler.
pos_in_check(p:POS):BOOL is
ret : BOOL;
pos : POS;
ret := false;
loop piece::=opp_piece!;
loop
pos :=piece.move!(self, PIECE::for_check_test);
if p=pos then
ret := true;
break!;
end;
end;
if ret then break!; end;
end;
return ret;
end; -- of pos_in_check
The routine my_king_isin_check returns true if the king of the current color (white_to_play) is in check. After an otherwise valid move of a piece, the own king is not allowed to be exposed and to be in check.
my_king_isin_check:BOOL is
piece : $PIECE;
loop
piece := my_piece!;
until!(piece.isking);
end;
return pos_in_check(piece.position);
end; -- of my_king_isin_check
Boolean expressions are evaluated with a short-circuit semantics. For an and this means that the second operand is only evaluated if the first operand was true. For an or the second operand is evaluated only if the first one was false. In routine check_n_apply_move we make use of this to ensure that a move is applied to a board only if it is valid.
Routine move_valid_so_far checks whether a given move is valid with respect to the current state of the board. The only circumstance which is not checked is whether the move would expose the own king to be in check.
check_n_apply_move(move:MOVE):BOOL is
return (move_valid_so_far(move) and apply_move_with_own_check_test(move));
end; -- of check_n_apply_move
private move_valid_so_far(move:MOVE):BOOL
pre ~move.isquit
is
ret : BOOL := false;
-- A valid move must start at a position where one of my pieces is....
if has_my_piece(move.from) then
p::=piece(move.from);
-- ... and it must be a valid move with respect to the mobility of the
-- piece at the current state of the board.
if p.valid_move(move.to,self) then
ret := true;
-- Since the move seems to be valid, the moving piece is stored
-- in the move object. That eases future access to the moving piece
-- and allows for un-doing of moves.
move.piece := p;
end;
end;
return ret;
end; -- of move_valif
The move is applied to the board in routine apply_move_with_own_check_test. The routine returns false, and leaves the state of the board unchanged, if an otherwise valid move would expose the own king to be in check.
First of all in lines 221-241 it is checked whether the move would kill an opponent piece. The normal circumstances for this are that the moving piece moves to a position that is occupied by an opponent piece. Chess has one special rule due to which a piece can be killed without moving to its former position. It is called an ``en passant" move. This special case can only occur if two pawns are involved. My pawn can kill an opponent pawn that sits immediately east or west of my pawn, if the other pawn has done an initial double move in the immediately preceding move. (That's why the last move is considered to be part of the state of a board.). If these conditions hold, my pawn can move diagonal so that his new position is ``behind" the opponent pawn.
Special action is required in case of castle moves. A castle move works as follows. If the king and a rook both are in their initial positions, if there is no piece in between them, if the king has not been moved in the game, and if the two positions next to the king in the direction toward the rook are not in check, then the king moves two positions towards the rook and then the rook jumps over the king and is put immediately next to the king. A castle move is a k-castle, if the king moves to the rook whose initial position is closer. Otherwise it is called q-castle, because due to the initial queen position, the distance to the rook is larger. Chess only allows castle moves, if the king has not been moved earlier in the game. The board keeps track of king moves in the two flags white_K_moved and black_K_moved. To enable un-doing of moves, a move knows whether it causes a change of a K_moved flag. See lines 254-268 for the K_moved flags and lines 269-286 for the implementation of castle moves.
Another special rule in chess allows to exchange a pawn against a queen or a knight when it reaches the base line of the opponent. Theoretically, a player could have 9 queens. This rule is implemented in lines 254-268.
apply_move_with_own_check_test(move:MOVE):BOOL
pre ~move.isquit and move_valid_so_far(move) and ~void(move.piece)
is
ret : BOOL := true; -- Will be false if the move is invalid due to
-- exposure of own "king in chess"
p:$PIECE:=move.piece; -- to be moved
r:$PIECE; -- may be killed
-- Case 1: Kill with normal move
r := piece(move.to); -- If it exists, it can only be opponent piece.
-- Otherwise the move would not be valid.
-- Case 2: En Passant.
if void(r) and ~void(last_move) and p.ispawn
and ~void(last_move.piece) and last_move.piece.ispawn
and ( last_move.to = p.position.east
or last_move.to = p.position.west)
then
if ( p.iswhite and white_to_play
and p.position.row = '5' and last_move.from.row = '7')
or ( ~p.iswhite and ~white_to_play
and p.position.row = '4' and last_move.from.row = '2')
then
r := last_move.piece;
end;
end;
if ~void(r) then
move.kills := r;
r.alive := false;
end;
p.update_position(move.to);
-- Deal with king moves.
if p.isking then
if white_to_play and ~white_K_moved then
white_K_moved := true;
move.king_chg := true;
end;
if ~white_to_play and ~black_K_moved then
black_K_moved := true;
move.king_chg := true;
end;
end;
-- Deal with pawn exchange.
if (p.ispawn and p.iswhite and white_to_play and p.position.row='8')
or (p.ispawn and ~p.iswhite and ~white_to_play and p.position.row='1')
then
case MAIN::player.ask_pawn_xchg
when 'Q' then
whitepieces[index(p)] := #QUEEN(p.position,PIECE::white);
when 'K' then
whitepieces[index(p)] := #KNIGHT(p.position,PIECE::white);
else
-- Do it fails safe.
raise "BOARD:apply_move:pawn_exchange invalid case entry\n"
end;
move.pawn_chg := true;
end;
-- Deal with castles.
if move.isq_castle then
if white_to_play then
rook ::= piece("a1");
rook.update_position("d1");
else
rook ::= piece("a8");
rook.update_position("d8");
end;
elsif move.isk_castle then
if white_to_play then
rook ::= piece("h1");
rook.update_position("f1");
else
rook ::= piece("h8");
rook.update_position("f8");
end;
end;
move.prev_move := last_move;
last_move := move;
-- Check whether my king is in check after application of the move
if my_king_isin_check then
-- Although otherwise correct this is an invalid move.
-- The original state of the board is reconstructed by calling
-- unapply_move.
ret := false;
unapply_move;
end;
white_to_play := ~white_to_play;
return ret;
end; -- of apply_move
The routine unapply_move uses the information that is stored in last_move to replay the move, i.e., restore the board to the state it had before the application of that move. It depends on the fact that last_move is a valid move except that the king might be in check afterwards.
unapply_move is
-- Restore killed opponent piece
if ~void(last_move.kills) then
last_move.kills.alive := true;
end;
-- Restore pawn exchange
if last_move.pawn_chg then
newpiece ::= piece(last_move.piece.position);
whitepieces[index(newpiece)] := last_move.piece;
end;
-- Restore move
last_move.piece.update_position(last_move.from);
if last_move.king_chg then
if white_to_play then
white_K_moved := false;
else
black_K_moved := false;
end;
end;
-- Restore castle
if last_move.isq_castle then
if white_to_play then
rook ::= piece("d1");
rook.update_position("a1");
else
rook ::= piece("d8");
rook.update_position("a8");
end;
elsif last_move.isk_castle then
if white_to_play then
rook ::= piece("f1");
rook.update_position("h1");
else
rook ::= piece("f8");
rook.update_position("h8");
end;
end;
last_move := last_move.prev_move;
white_to_play := ~white_to_play;
end; -- of unapply_move
For the automatic player, there must be a way to assign a worth to a board. This is done as follows. Compute the sum of the worths of all white pieces on the board. Similar, compute the worth of all black pieces. The value of the board is the ratio of the two values.
The routine board_value returns a floating point value, FLT, which is specified in the FLT library. (See file Library/flt.sa for details.)
More complex evaluation functions are known and can be used to replace the simple function board_value. For example, the degree of freedom the pieces have in their movement is an interesting aspect that might be considered in the evaluation function.
board_value:FLT is
white_value : INT := 0;
black_value : INT := 0;
loop p::= whitepiece!;
white_value := white_value + p.worth;
end;
loop p::= blackpiece!;
black_value := black_value + p.worth;
end;
return white_value.flt/black_value.flt;
end; -- of board_value
end; -- of class BOARD