Transposition tables

Author

100

October 31, 2010 05:27 AM

Hi I am trying to code transposition table for my game.
The problem is that at higher depths, the program plays many of its own moves(same color),without giving a chance to opponent what problem might be there? At lower depths(4 plys) it plays properly. Trouble starts from depth 8 onwards.

My table size is 18 bits i.e 2^18=262144
hI=zob_key%(tablesize-1)

Here is the code where the transposition tables are coded:

  makeMove(posn, r, c, white);//make a move            if (hKey[hI] == zob_key) {                                 hit++;//Count number of hits in table.                   System.out.println("HIT "+hit+" " + " " + zob_key);                if (hDepth[hI] >= ply) {                    System.out.println("hply " + " " + hDepth[hI]+" ply "+ply);                    if (hType[hI] == 0) {                        System.out.println("hVal " + " " + hVal[hI]);                        return hVal[hI];                    }//hashfEXACT                    if ((hType[hI] == 1) && (hVal[hI] <= alpha)) {                        System.out.println("htype_alpha " + " " + hType[hI]);                        return alpha;                    }//hashfALPHA                    if ((hType[hI] == 2) && (hVal[hI] >= beta)) {                        System.out.println("htype_beta " + " " + hType[hI]);                        return beta;                    }//hashfBETA                 }            }            eval = -alphaBeta(posn, !white, ply + 1, -beta, -alpha);            undoMove(posn, r, c, white);//   undo move            if (eval >= beta) {                if (ply == 1) {                    bestMove = new Move(r, c);                }                //Record at Beta cutoff.                hKey[hI] = zob_key;                hType[hI] = 2;                hDepth[hI] = ply;                hVal[hI] = beta;                return beta;            }            if (eval > alpha) {                if (ply == 1) {                    bestMove = new Move(r, c);                }                alpha = eval;                hashType = 0;            }        }        hKey[hI] = zob_key;        hType[hI] = 0;        hDepth[hI] = ply;        hVal[hI] = alpha;        return alpha;

alvaro

21,607

October 31, 2010 08:17 AM

You inserted the code to look at the hash tables in the wrong place. You can't have a return statement in between the call to makeMove and undoMove. Instead, you should check at the beginning of the search if you already know the answer.

Also, you can't just return alpha or beta when the information in the transposition tables is only a bound: You can update alpha or beta with the new information, but you still need to search.

Yet another problem is that you are storing the hType as 0 whenever a beta cutoff doesn't happen, but this is not always correct. If alpha was never improved, you only know that the minimax value of this node is <= alpha.

Instead of multiple arrays, an array of structs is much more cache friendly. Finally, you should probably write functions to store and retrieve search information on the transposition tables. It will make your code much easier to read.

mandar9589

Author

100

October 31, 2010 01:55 PM

@alvaro
Thanks for replying.
The hashtables works now.
By adding hashtables, I am able to search 2plies deeper approx as compared to without hashtables.
Later today I will edit add to this post, a graph of depth-log(time),with and without TT.
till then any more improvements that you can suggest to speed up the search,are welcomed.

mandar9589

Author

100

October 31, 2010 01:55 PM

@alvaro
Thanks for replying.
The hashtables works now.
By adding hashtables, I am able to search 2plies deeper approx as compared to without hashtables.
Later today I will edit add to this post, a graph of depth-log(time),with and without TT.
till then any more improvements that you can suggest to speed up the search,are welcomed.

BitSet

121

November 05, 2010 07:35 AM

I'm not sure if 18 bit hash size is enough. Hash should be at least 64 bit long, otherwise collisions may become very common. Also remember to have Zobrist value for side on move and to XOR it with hash value every time move is made.

mandar9589

Author

100

November 07, 2010 03:36 PM

Quote: Original post by BitSet
I'm not sure if 18 bit hash size is enough. Hash should be at least 64 bit long, otherwise collisions may become very common. Also remember to have Zobrist value for side on move and to XOR it with hash value every time move is made.

Well correct me if I am wrong.
I have hashtable of size of 32kB(which I think is fair enough for a game like connect 4.)

I have filled this table with 64-bit long integers(random numbers).
Actually I am having trouble in writing the evaluation where it sees three in a row and some more sophistication,as of now it has only the winning conditions.

BitSet

121

November 08, 2010 11:00 AM

It's hard to understand what are you doing. TT element contains more than just Zobrist hash of game state. It must also contain type of stored value: exact, upper bound, lower bound. It usually also contains the best successor: struct TT_element { uint64 hash; int score; char type; MOVE best_successor; };

I'm not familiar with Connect 4 but before you start writing evaluation first take blank sheet of paper and make a list of what is good/bad about game state.

mandar9589

Author

100

November 08, 2010 02:52 PM

Connect-4 is a like tic-tac-toe, but has gravity rule.

http://en.wikipedia.org/wiki/Connect_Four#Mathematical_solution

I have the evaluation,or my ideas there, but there is something which I am missing when I try to focus on doing 3-in-row or may be odd move threat or something like that.

    public static int evaluate(char[][] posn, boolean turn) {        int eval = 0;        int score_x = 0;        int score_o = 0;        //Winning.        for (row = 0; row < 6; row++) {            for (column = 0; column < 4; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row][column + 1]                        && posn[row][column] == posn[row][column + 2]                        && posn[row][column] == posn[row][column + 3]) {                    eval = -1000;                    return eval;                }            }        }// check for a vertical win        for (row = 0; row < 3; row++) {            for (column = 0; column < 7; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row + 1][column]                        && posn[row][column] == posn[row + 2][column]                        && posn[row][column] == posn[row + 3][column]) {                    eval = -1000;                    return eval;                }            }        }// check for a diagonal win (positive slope)        for (row = 0; row < 3; row++) {            for (column = 0; column < 4; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row + 1][column + 1]                        && posn[row][column] == posn[row + 2][column + 2]                        && posn[row][column] == posn[row + 3][column + 3]) {                    eval = -1000;                    return eval;                }            }        }// check for a diagonal win (negative slope)        for (row = 3; row < 6; row++) {            for (column = 0; column < 4; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row - 1][column + 1]                        && posn[row][column] == posn[row - 2][column + 2]                        && posn[row][column] == posn[row - 3][column + 3]) {                    eval = -1000;                    return eval;                }            }        }        //..........................................................//        for (row = 0; row < rows; row++) {            for (column = 0; column < cols - 2; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row][column + 1]                        && posn[row][column] == posn[row][column + 2]) {                    if (posn[row][column] == X) {                        score_x = three;                    }                    if (posn[row][column] == O) {                        score_o = three;                    }                }            }        }// check for a diagonal win (positive slope)        for (row = 0; row < rows - 2; row++) {            for (column = 0; column < cols - 2; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row + 1][column + 1]                        && posn[row][column] == posn[row + 2][column + 2]) {                    if (posn[row][column] == X) {                        score_x = three;                    }                    if (posn[row][column] == O) {                        score_o = three;                    }                }            }        }// check for a diagonal win (negative slope)        for (row = 3; row < rows; row++) {            for (column = 0; column < cols - 3; column++) {                if (posn[row][column] != EMPTY                        && posn[row][column] == posn[row - 1][column + 1]                        && posn[row][column] == posn[row - 2][column + 2]) {                    if (posn[row][column] == X) {                        score_x = three;                    }                    if (posn[row][column] == O) {                        score_o = three;                    }                }            }        }        if (turn == true) {            return (score_x - score_o);        }        if (turn == false) {            return (score_o - score_x);        }        return 0;    }

Here the above is the source for evaluation,and x is the first player(turn==true,player=x,else player=o)
if (posn[row][column] == X) {
score_x= three;
}
if (posn[row][column] == O) {
score_o = three;
}
In this case the score_x and score_o simply gets itself overwritten if the next condition is satisfied,so the computer will never come to know if there is a better square which might get it to connect 4.
The point is if I replace the above code by,
if (posn[row][column] == X) {
score_x+= three;
}
if (posn[row][column] == O) {
score_o += three;
}

then all it does it just connect 3 in a row and block three in row, doesnt care abt four in a row. I have ideas for evaluation but then the problem is how to program it correctly.

Transposition tables

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Transposition tables

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines