Similar to the situation between the abstract type $CHESS_DISPLAY and the classes ASCII_DISPLAY and X_DISPLAY, the players are organized with subtyping and include as well. The abstract type $PLAYER specifies the common interface.
type $PLAYER is getmove(b:BOARD):MOVE; ask_pawn_xchg:CHAR; end;
This is a class of type $PLAYER, which will not be used to instantiate. There will be no objects of type PLAYER. The main purpose of this class is to declare attributes and routines that are common to other classes of type $PLAYER, which include the implementation of this class.
The routine getmove does not provide a basic implementation. However, for consistency with the interface required by $PLAYER, a dummy implementation must be given. The routine ask_pawn_xchg provides a default implementation.
class PLAYER < $PLAYER is
attr iswhite:BOOL;
create(iswhite:BOOL):SAME is
ret : SAME := new;
ret.iswhite := iswhite;
return ret;
end;
getmove(b:BOARD):MOVE is
raise "PLAYER:invalid call to getmove\n";
end;
ask_pawn_xchg:CHAR is
return 'Q';
end;
end; -- of class PLAYER
This is a good place to look at the list of available class elements. We have already encountered routine definitions and include statements. Iter definitions are similar to routine definitions. All class elements can be declared private. Private elements can only be accessed from within the implementation of the class. Per default, class elements are public. It is worthwhile to take a closer look at the other class elements:
A human player will enter his move via the interface. This is coded in the routine getmove that replaces the inherited dummy implementation.
If a human player has the chance to exchange one of his pawns with a queen or a knight, the human player will enter his decision via the interface in routine ask_pawn_xchg.
class HUMAN < $PLAYER is
include PLAYER;
getmove(b:BOARD):MOVE is
return MAIN::display.getmove(iswhite);
end;
ask_pawn_xchg:CHAR is
MAIN::display.update(MAIN::board.str);
return MAIN::display.ask_pawn_xchg;
end;
end; -- of class HUMAN
The automatic player is represented by the class MINMAX. The class is called MINMAX, since the strategy for determining a move is based on a minmax search.
We define a couple of constants first. The boolean constants max and min are later on used to determine whether the minmax search is at a max- or at a min-level. The constant max_depth gives the maximal depth of the search tree. If max_depth is 3, then (1) all potential next moves, (2) all reactions of the opponent player and (3) all potential future reactions to these are considered.
The best moves of phase (1) are gathered in a dynamically sized list of type FLIST, as defined in the library file Library/flist.sa. FLIST will store all moves that will eventually result in the same board evaluation on level (3).
The random number generator declared in line 35 is used to select an arbitrary move from the list. MS_RANDOM_GEN is a class that is defined in the Sather Libraries. You find it in the file Library/rnd.sa The random number object is created and initialized in the create routine in line 40.
class MINMAX < $PLAYER is
include PLAYER;
const max : BOOL := true;
const min : BOOL := ~max;
const max_depth : INT := 3;
attr bestmoves : FLIST{MOVE};
shared rnd : MS_RANDOM_GEN;
create(iswhite:BOOL):SAME is
ret ::= new;
ret.iswhite := iswhite;
ret.bestmoves := #FLIST{MOVE};
rnd := #MS_RANDOM_GEN;
rnd.init(4711);
return ret;
end;
The getmove routine at first tells the viewing user that it is ``thinking" (line 46). Then it uses the routine minmax, which is described below, to find the best move. There might be more than one move that is considered to be ``best". The list bestmoves stores all of these. If there are no available moves, i.e., if the list of bestmoves is empty, then the player is mate - the game is over. This is checked in line 54.
Otherwise the random number generator returns a value in
. This is multiplied by the size of the list of available
best moves. Before multiplication, size, which is an integer
value, is cast to be of type FLTD. The product is rounded to
the floor and then cast into an integer value by the routine
int. The result is then used to index into the list of possible
best moves.
Before returning the move to the caller, it is displayed in line 61.
getmove(board:BOARD):MOVE is
ret : MOVE;
MAIN::display.thinking(board.white_to_play);
if board.white_to_play then
-- minmax returns a value, that is nor needed. However, Sather does
-- require to use the return value somehow.
dummy ::= minmax(board,max,max_depth);
else
dummy ::= minmax(board,min,max_depth);
end;
if bestmoves.size = 0 then
return #MOVE("quit",board.white_to_play);
else
ret := bestmoves[(bestmoves.size.fltd * rnd.get).floor.int];
bestmoves.clear;
text : STR;
text := ret.from.str + "-" + ret.to.str;
MAIN::display.showmove(text);
return ret;
end;
end; -- of getmove
The private routine minmax returns a floating point value, FLT. FLT is specified in the library class FLT. See file Library/flt.sa for details.
The body of minmax has a good example of nested iter calls: The first loop (lines 74-103) considers all pieces on the board of my color. The inner loop (lines 75-102) then for each of these pieces considers target positions of potential moves. (It is explained later on, what an ordinary move is. Just ignore this flag for the time being.)
The move created in line 77 is guaranteed to be correct, i.e., the piece is of the correct color and the target position is correct with respect to the basic movement rules of chess. The only condition that is not guaranteed to hold is whether the own king is exposed to be in check after the piece is moved. This is checked in apply_move_with_own_check_test. See line 79.
After a move has been applied successfully, we either consider the possible reactions recursively (line 83), or evaluate the value of the board in line 81.
The depth-first search requires backtracking. This is done in line 100 by calling board.unapply_move.
private minmax(board:BOARD,minmax:BOOL,depth:INT):FLT is
move : MOVE;
val,bv : FLT;
pos : POS;
if minmax = max then
val := -1000.0;
else
val := 1000.0;
end;
loop piece::=board.my_piece!;
loop
pos :=piece.move!(board,PIECE::ordinary);
move := #MOVE(piece,pos);
move.piece := piece;
if board.apply_move_with_own_check_test(move) then
if depth = 1 then
bv := board.board_value;
else
bv := minmax(board,~minmax,depth - 1);
end;
-- If this move really is better than previous ones,
-- the list of best moves found so far is erased.
if depth = max_depth and ( (minmax = max and bv > val)
or (minmax = min and bv < val))
then
bestmoves.clear;
end;
-- If this move is not worse than previous ones, the move
-- is added to the list of best moves found so far.
if depth = max_depth and ( (minmax = max and bv >= val)
or (minmax = min and bv <= val))
then
val := bv;
bestmoves := bestmoves.push(move);
end;
board.unapply_move;
end;
end;
end;
return val;
end; -- of minmax
end; -- of class MINMAX
The following remark will be completely understandable only after the type $PIECE and the concrete subtypes have been presented in section 9. For reasons of completeness note that line 76 is a dispatched iter call. Depending on the concrete type of the piece:$PIECE a different iter is called.
In Sather 1.0.2
dispatched iters are not implemented. The typecase statement can
be used to implement the intended behavior:
typecase piece
when PAWN then pos:=piece.move!(board,PIECE::ordinary);
when ROOK then pos:=piece.move!(board,PIECE::ordinary);
when KNIGHT then pos:=piece.move!(board,PIECE::ordinary);
when BISHOP then pos:=piece.move!(board,PIECE::ordinary);
when KING then pos:=piece.move!(board,PIECE::ordinary);
when QUEEN then pos:=piece.move!(board,PIECE::ordinary);
else
end;