Author: Robert Hyatt
Date: 17:31:43 01/03/00
Go up one level in this thread
On January 02, 2000 at 17:43:50, John Hendrikx wrote:
>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:
>
This is not exactly what you should be doing. You should check every move
to see it it leads to a position in the hash table that will cause a cutoff,
but you can't assume that it will. You should make it, and then try your
usual stuff. The reason what you are doing is wrong is that you are overlooking
_draws_. IE repetitions. If you recursively call search() after trying the
move suggested by ETC, you will catch this right. Otherwise you have to catch
this in your ETC code where you are deciding to return the table value.
Don't forget draws by repetition, by the 50 move rule, and other such things
that are normally done at the front of the search code, but which you are
bypassing...
> 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.