Author: John Hendrikx
Date: 14:43:50 01/02/00
I'm writing a chess-engine in Java and I'm making pretty good progress, even
though I don't fully understand some of the more advanced concepts yet. I've
implemented a Transposition Table (TT) and am using it to reduce the number of
positions searched (although not by much). This seems to work fine, and the
results I get when search 7 plies deep seem good:
160 ms d2-d3 [24] moves = 20 (0 = transposed)
440 ms d2-d3 d7-d6 [0] moves = 69 (0)
1040 ms d2-d3 d7-d6 b1-c3 [22] moves = 523 (0)
2360 ms d2-d3 d7-d6 b1-c3 b8-c6 [0] moves = 1556 (93)
4940 ms e2-e3 d7-d6 d1-f3 b8-d7 f3-f7 [76] moves = 31363 (1178)
14770 ms d2-d3 e7-e6 c1-f4 f8-c5 b1-c3 c5-f2 [-57] moves = 156461 (11163)
63770 ms e2-e3 e7-e6 g1-f3 g8-f6 f1-c4 b8-c6 c4-e6 [82] moves = 831941 (28116)
[No opening book, started as white from initial position on Celeron 333].
I was still looking for ways to improve the cutoff rate (tree gets 7 times
bigger every ply on average, and that's in the opening...). I tried something
called enhanced transposition cutoff; the idea is that after moves have been
generated one immediately checks all the moves to see if one is in the TT and
causes a cutoff. If that's case, no searching is done and the value in the TT
is returned. This however fails -- the results I got above become this:
220 ms d2-d3 [24] moves = 20 (0 = transposed)
440 ms d2-d3 d7-d6 [0] moves = 69 (0)
1100 ms d2-d3 d7-d6 b1-c3 [22] moves = 523 (0)
2640 ms d2-d3 d7-d6 b1-c3 b8-c6 [0] moves = 1555 (93)
4840 ms d2-d3 b8-c6 b1-c3 d7-d6 g1-f3 [22] moves = 24820 (286)
11150 ms e2-e3 e7-e6 d2-d3 g8-e7 g1-f3 b8-c6 [3] moves = 82580 (3250)
75580 ms e2-e3 g8-f6 f1-c4 d7-d5 c4-d3 h7-h6 g1-f3 [16] moves = 933153 (7686)
Slower, and different scores... null-moves were disabled in both cases.
The results I get here lead me to believe I've implemented the Transposition
Table incorrectly or something. I really don't see the harm in testing all
moves in the TT for a cutoff at once, instead of doing them one by one during
the search.
Here's my code (alphabeta + TranspositionTable class):
public final int alphabeta(Board board, Move bestLine, int depth) {
maxPlies=depth+2; // determines max. extensions (kludge for now).
return alphabeta(board, bestLine, board.getHash(), depth, 0,
-Integer.MAX_VALUE, Integer.MAX_VALUE);
}
/* Below is my implementation of negamax in Java.
board : A chessboard object, which can be evaluated.
bestLine : A chain of moves indicating the current best line (PV).
hash : Hash value of current position.
depth : Amount of plies left to search.
ply : The current ply (starting from 0).
alpha : Score we can achieve at minimum (??)
beta : Score to beat (??) */
public final int alphabeta(Board board, Move bestLine, int hash,
int depth, int ply, int alpha, int beta) {
short hashMove=-1;
board.pv=null;
if(depth==0 || ply>maxPlies) {
return board.score(); // Evaluate the board.
}
if(tt!=null) { // If there is a transposition table, use it.
int e;
if((e=tt.retrieve(hash, (byte)depth, board.whitesTurn))>=0) {
// A succesful retrieval. Depth is already checked.
// I'm not quite sure if I'm using this value correctly, but
// it seems to work. I think more cut-offs are possible though.
// I'm not making any use of the beta value stored in the TT...
if(tt.alpha[e] >= beta) {
transposed++;
return tt.alpha[e];
}
hashMove=tt.move[e];
}
}
if(nullMoves && depth > 3 && ply!=0) {
// A null-move implementation... it seems to work.
// Null moves are only done when we're atleast 2 levels away from the
// leaf-nodes and not at all on the first ply (I don't take it would
// make sense).
nullMoves=false;
board.whitesTurn=!board.whitesTurn;
int result=-alphabeta(board, bestLine!=null ? bestLine.next : null,
hash, depth-3, ply+1, -beta, -alpha);
board.whitesTurn=!board.whitesTurn;
nullMoves=true;
if(result >= beta) { // Any more I could do with the result?
return result;
}
}
// Below we get a list of moves we can try from this position. The moves
// are ordered; PV, Hash, Captures, Killers, Piece moves, Pawn moves.
List l=board.getMoves(bestLine, km[depth], hashMove, bestLine!=null ?
(short)((bestLine.source<<8) + bestLine.destination) : -1);
if(tt!=null) {
// This is an attempt to do something called 'enhanced transpositon
// cutoff'.
Iterator i=l.iterator();
while(i.hasNext()) { // Loop through all moves.
Move move=(Move)i.next();
int e;
int newHash=(hash ^ piecePositionHash[((board.whitesTurn ? 0 : 1)<<10)
+ ((Math.abs(board.pieceAt(move.source))-1)<<6)
+ move.source]) ^ piecePositionHash[((board.whitesTurn ? 0 : 1)<<10)
+ ((Math.abs(board.pieceAt(move.source))-1)<<6) + move.destination];
if((e=tt.retrieve(newHash, (byte)(depth-1), !board.whitesTurn))>=0) {
if(tt.alpha[e] >= -alpha) {
if(tt.alpha[e] >= beta) {
return tt.alpha[e];
}
}
}
}
}
Iterator i=l.iterator();
Move bestMove=null;
int best=-20000;
boolean hasMoves=false;
boolean inCheck=board.inCheck(board.whitesTurn);
// The main part of the alpha/beta search:
while(i.hasNext()) { // Loop through all moves.
Move move=(Move)i.next();
int newHash = (hash ^ piecePositionHash[((board.whitesTurn ? 0 : 1)<<10)
+ ((Math.abs(board.pieceAt(move.source))-1)<<6) + move.source])
^ piecePositionHash[((board.whitesTurn ? 0 : 1)<<10)
+ ((Math.abs(board.pieceAt(move.source))-1)<<6) + move.destination];
if(board.applyMove(move)) { // Makes sure no illegal moves are played.
hasMoves=true;
int result=-alphabeta(board, bestLine!=null ? bestLine.next : null,
newHash, inCheck ? depth : depth-1, ply+1, -beta, -alpha);
board.undoMove();
movesAnalyzed++;
if(result > best) {
best=result;
if(result > alpha) {
alpha=result;
}
bestMove=move;
bestMove.next=board.pv;
}
if(alpha >= beta) {
km[depth].add(move);
//alpha=beta; Not sure if this is needed... it could make a
// difference when storing the best move for this
// position in the TT.
break;
}
}
}
if(!hasMoves) {
if(inCheck) {
best=-10000+ply; // checkmate in x plies...
}
else {
best=0; // stalemate
}
}
if(tt!=null && bestMove!=null) {
// Both alpha and beta are stored here. Currently only alpha is used.
tt.store(hash, alpha, beta, (short)((bestMove.source<<8) +
bestMove.destination), depth, board.whitesTurn);
}
board.pv=bestMove;
return best;
}
class TranspositionTable {
private int mask;
private int size;
int[] hash;
short[] alpha;
short[] beta;
short[] move;
byte[] depth;
public TranspositionTable(int sizeAsPower2) {
size=1<<sizeAsPower2;
hash=new int[size];
alpha=new short[size];
beta=new short[size];
move=new short[size];
depth=new byte[size];
mask=(size>>1)-1;
}
public final void clear() {
for(int i=0; i<size; i++) {
depth[i]=-1;
}
}
public final int retrieve(int h, byte d, boolean isWhite) {
final int e=((h & mask)<<1) + (isWhite ? 0 : 1);
if(depth[e] >= d && hash[e] == h) {
return e;
}
return -1;
}
public final void store(int h, int a, int b, short m, int d,
boolean isWhite) {
final int e=((h & mask)<<1) + (isWhite ? 0 : 1);
hash[e]=h;
alpha[e]=(short)a;
beta[e]=(short)b;
move[e]=m;
depth[e]=(byte)d;
}
}
Your comments are appreciated :-)
John.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.