static_evaluator = cluster is create, create_random, create_mutant,
create_move_mutant, mate, evaluate, unparse, parse, copy, equal,
get_anticipation
% Overview: static_evaluator is an immutable data type which is used
% by computer_player to determine an anti-chess strategy. The essential
% feature of the static_evaluator is that, given a chess_board, it can
% return a real number describing how "good" that board is for a player
% whose pieces are a given color. This number is only a heuristic result,
% but it can be used to build a more sophisticated algorithm.
%
% In keeping with the idea of the static_evaluator being the "brains"
% of a computer_player, the static_evaluator also contains information
% on the timing of moves (i.e., the procedures get_anticipation and
% create_move_mutant).
% This data structure also contains operations to aid in a
% genetic-algorithm optimization of an anti-chess strategy, allowing
% static evaluators to be randomly generated, mutated, and "mated".
% written by stevenj and twm
rep = sequence[int]
kingWeight = 1
pawnWeight = 2
knightWeight = 3
rookWeight = 4
bishopWeight = 5
queenWeight = 6
% leave this as the last weight to isolate it from mutation of
% the other weights.
movesPerGame = 7
weights = 7
rw = 7.0
% Abstraction function: A typical static evaluator is a set of
% weights for various quantities about the chess_board. For example,
% there is a weight for the number of pawns on the board. To evaluate
% a chess board, the weights of the weighted pieces are multiplied by
% the quantity of that type of piece and summed. The weighted sum
% of a players own pieces is subtracted from its score and the weighted
% sum of its opponents pieces are added to its score.
% The abstraction function
% is:
% A(r) = { elements of sequence r are the weights whose
% associated quantities are described by the
% equate for that index of r; e.g. r[kingWeight]
% is the weight for the number of kings on the board}
% Rep. Invariant:
% * size(r) = number of weights (7)
% * each element of r is in the interval [0,100000] except for the
% move weight which is in the range [1000,75000]
% * each element in r, with the possible exception of the move
% weight, is within one order of magnitude of all the other weights
% * the sum of the elements of r is 100,000 (weights are normalized)
create = proc() returns(cvt)
% effects: returns a new static evaluator.
return(down(parse(08189,
12057,
09667,
16472,
32606,
17009,
03600)))
end create
parse = proc(k, p, n, r, b, q, m: int) returns(cvt)
% requires: k,p,n,r,b,q all be within one order of magnitude of
% each other. All weights are >= 0. m is in the range
% [1000, 75000]
% effects: returns a static evaluator with the same relative weights
% as k,p,n,r,b, and q and the same absolute weight as m. k=king,
% p=pawn, n=knight, r=rook, b=bishop, q=queen and m = moves
% per game.
sum: int:= k+p+n+r+b+q
k2:int:=real$r2i(real$i2r(k)*real$i2r(100000-m)/real$i2r(sum))
p2:int:=real$r2i(real$i2r(p)*real$i2r(100000-m)/real$i2r(sum))
n2:int:=real$r2i(real$i2r(n)*real$i2r(100000-m)/real$i2r(sum))
r2:int:=real$r2i(real$i2r(r)*real$i2r(100000-m)/real$i2r(sum))
b2:int:=real$r2i(real$i2r(b)*real$i2r(100000-m)/real$i2r(sum))
q2:int:=real$r2i(real$i2r(q)*real$i2r(100000-m)/real$i2r(sum))
sum2: int:= k2+p2+n2+r2+b2+q2
k2:=k2+100000-sum2-m
return(rep$[k2,p2,n2,r2,b2,q2,m])
end parse
create_random = proc() returns(cvt)
% effects: returns a new, (pseudo)random static evaluator
random$seed(time$get_millis(run_time())*1000 +
time$get_micros(run_time()))
wts: array[int] := array[int]$create(1)
sum: int := 0
for i:int in int$from_to(1,weights) do
array[int]$addh(wts, (random$next(9000)+1000))
sum := sum + array[int]$top(wts)
end
wts[weights]:=int$max(1000, (wts[weights]*3)/4)
sum2: int := 0
for i:int in int$from_to(1, weights-1) do
wts[i] := wts[i] * (100000-wts[weights]) / sum
sum2:= sum2 + wts[i]
end
wts[1]:=wts[1] + (100000 - sum2 - wts[weights])
return(rep$a2s(wts))
end create_random
create_mutant = proc(e: cvt) returns(cvt)
% effects: returns a new static_evaluator which has the same
% relative weights as e, except for one randomly
% picked weight, which has been reassigned randomly.
% The weight representing the number of expected moves may
% be mutated, but if it's not mutated it remains the same (not just
% relatively) and all others are normalized so that all weights
% sum to 100,000.
random$seed(time$get_millis(run_time())*1000 +
time$get_micros(run_time()))
e2: array[int]:= rep$s2a(e)
i: int:= random$next(weights) + 1
top: int:= array[int]$high(e2)
if i = weights then
e2[i]:=random$next(74000) + 1000
else
mx: int:=0
mn: int:=100000
for w: int in int$from_to(1, top-1) do
mx:= int$max(mx, e2[w])
mn:= int$min(mn, e2[w])
end
lb: int:=mx / 10
hb: int:=mn * 10
e2[i] := random$next(hb-lb) + lb
end % if i = weights...
sum: int := 0
for x: int in int$from_to(1, top - 1)
do sum:=sum+e2[x] end
sum2: int:=0
for i2: int in int$from_to(1, top - 1) do
e2[i2]:=real$r2i(real$i2r(e2[i2])*
real$i2r(100000 - e2[top])
/real$i2r(sum))
sum2:=sum2 + e2[i2]
end
e2[1]:=e2[1] + (100000 - sum2 - e2[weights])
return(rep$a2s(e2))
end create_mutant
create_move_mutant = proc(e: cvt) returns(cvt)
% effects: returns a new static_evaluator which has the same
% relative piece weights as e.
% The weight representing the number of
% expected moves is reassigned randomly,
% and all other weights are normalized so that all weights
% sum to 100,000.
random$seed(time$get_millis(run_time())*1000 +
time$get_micros(run_time()))
e2: array[int]:= rep$s2a(e)
m: int:= e2[weights]
hb: int:= int$min(75000, m*2)
lb: int:= int$max(1000, m/2)
e2[weights] :=random$next(hb-lb) + lb
sum: int := 0
top: int:= array[int]$high(e2)
for x: int in int$from_to(1, top - 1)
do sum:=sum+e2[x] end
sum2: int:=0
for i2: int in int$from_to(1, top - 1) do
e2[i2]:=real$r2i(real$i2r(e2[i2])*
real$i2r(100000 - e2[top])
/real$i2r(sum))
sum2:=sum2 + e2[i2]
end
e2[1]:=e2[1] + (100000 - sum2 - e2[weights])
return(rep$a2s(e2))
end create_move_mutant
mate = proc(e1,e2: cvt) returns(cvt)
% effects: returns a new static evaluator which blends the
% behaviors of e1 and e2.
correction: int:=100000
for i: int in rep$indexes(e1) do
correction:=correction-(e1[i]+e2[i])/2
end
return(rep$[(e1[1]+e2[1])/2 + correction,
(e1[2]+e2[2])/2,
(e1[3]+e2[3])/2,
(e1[4]+e2[4])/2,
(e1[5]+e2[5])/2,
(e1[6]+e2[6])/2,
(e1[7]+e2[7])/2])
end mate
evaluate = proc(e: cvt, board: chess_board, color: pieceColor)
returns(int)
% effects: Returns a real number which indicates how "good"
% the current board is for the player whose pieces
% are the color "color." Higher numbers are better.
% This is only a heuristic result and carries no
% guarantees.
% N.B. this is likely to be at the center of a very tight loop,
% so try to make it as efficient as possible.
% Evaluation function returns:
% e[kingWeight] * (# of opponent's kings left) +
% e[pawnWeight] * (# of opponent's pawns left) + ...
% - e[kingWeight] * (# of player's kings left) -
% - e[pawnWeight] * (# of player's pawns left) - ...
goodness: int := 0
for pc:pieceColor,pk:pieceKind,r,c:int in chess_board$pieces(board) do
goal: int
if pc = color then
tagcase pk
tag king:
goodness := goodness - e[kingWeight]
tag pawn:
goodness := goodness - e[pawnWeight]
tag knight:
goodness := goodness - e[knightWeight]
tag rook:
goodness := goodness - e[rookWeight]
tag bishop:
goodness := goodness - e[bishopWeight]
tag queen:
goodness := goodness - e[queenWeight]
end
else
tagcase pk
tag king:
goodness := goodness + e[kingWeight]
tag pawn:
goodness := goodness + e[pawnWeight]
tag knight:
goodness := goodness + e[knightWeight]
tag rook:
goodness := goodness + e[rookWeight]
tag bishop:
goodness := goodness + e[bishopWeight]
tag queen:
goodness := goodness + e[queenWeight]
end % tagcase
end % if pc = color
end % for loop
return(goodness)
end evaluate
unparse = proc(specimen: cvt)
% effects: unparses a static_evalutator and sends the results to
% primary_output. Written for debugging and
% evolutionary purposes only.
display(string$concat("\nKing: ", int$unparse(specimen[kingWeight])))
display(string$concat("Pawn: ", int$unparse(specimen[pawnWeight])))
display(string$concat("Knight: ",
int$unparse(specimen[knightWeight])))
display(string$concat("Rook: ", int$unparse(specimen[rookWeight])))
display(string$concat("Bishop: ",
int$unparse(specimen[bishopWeight])))
display(string$concat("Queen: ", int$unparse(specimen[queenWeight])))
display("----------------")
display(string$concat("Moves: ",
int$unparse(specimen[movesPerGame])))
end unparse
display = proc(message: string)
% effects: sends message to primary_output() as a line.
stream$putl(stream$primary_output(), message)
end display
copy = proc(original: cvt) returns(cvt)
% effects: Returns a copy of original.
return(original)
end copy
equal = proc(ori, se: cvt) returns(bool)
% effects: returns whether ori and se are equal.
for index: int in rep$indexes(ori) do
if ori[index] ~= se[index] then
return(false) end
end
return(true)
end equal
get_anticipation = proc(e1: cvt) returns (real)
% effects: Returns the number of moves that e1
% expects to make during a game. This is obiviously
% not a guarantee (since it is real) and is only
% as good as the static_evalutor.
return(real$i2r(e1[movesPerGame]) * 0.00250)
end get_anticipation
end static_evaluator