   Adding transposition tables to TicTacToe
import java.io.*;import java.util.Vector;public class Table implements Utils {    public Hashentry[] hashtable;public long[] repZobrist;public int HASHSIZE;// Ordinary transposition tablepublic Table(int HASHSIZE){this.HASHSIZE = HASHSIZE;hashtable = new Hashentry[HASHSIZE];}   public Hashentry getEntry(long zobrist){int hashkey = (int)(zobrist%HASHSIZE);if(hashtable[hashkey] != null && hashtable[hashkey].zobrist == zobrist) return hashtable[hashkey];return null;}    public  void record(long zobrist, int depth, int flag, int eval, int move){// Depth replacement schemeint hashkey = (int)(zobrist%HASHSIZE);}    public class Hashentry{public long zobrist;public int depth;public int flag;public int eval;public int move;public Hashentry(long zobrist, int depth, int flag, int eval,  int move){this.zobrist = zobrist;this.depth = depth;this.flag = flag;this.eval = eval;this.move = move;}}}This is a new class created which will handle the transposition tables which I want to use to speed up the search.My game of Tic Tac Toe is been programed using negamax along with alpha beta pruning,with history heuristics.I know that transposition tables are not required for small game like tic tac toe, but as I am just learning to implement such algorithms,I think its best to start with a simple program, even if there is no need for transposition tables, I could still learn the way in which  transposition tables can be implemented.kindly help as I am unable to proceed further with recordmove();   
  I don't "speak" Java very well. What is it you don't know how to do?It's probably best to practice on a slightly less toyish game, because you'll have a hard time observing any improvements in tic-tac-toe, so you won't know if you did it right. Perhaps connect-4?;  Thanks for replying.I thought implementing hash tables in tic tac toe will be better as I am trying it out or the first time. Anyways since an experienced programmer like you is telling me to try it out on connect4, I think its best to follow your advice.Quote:I don't "speak" Java very wellI guess the data structures won't be of any trouble. But I know C programmers like to use pointers,but in Java pointers are managed by the compiler and interpreters.public  void record(long zobrist, int depth, int flag, int eval, int move){// Depth replacement schemeint hashkey = (int)(zobrist%HASHSIZE);}This is where I was stuck.but then I could write other methods to save the data.here is what i did. public Hashentry getEntry(long zobrist) {   int hashkey = (int) (zobrist % HASHSIZE);   if (hashtable[hashkey] != null && hashtable[hashkey].zobrist == zobrist) {  return hashtable[hashkey];   }   return null;    }public void record(long zobrist, int depth, int flag, int eval, int move) {    int hashkey = (int) (zobrist % HASHSIZE); if (hashtable[hashkey] == null) {  hashtable[hashkey] = new Hashentry(zobrist, depth, flag, eval, move);  return;   }  // Depth replacement scheme   if (hashtable[hashkey].depth <= depth) {  hashtable[hashkey] = new Hashentry(zobrist, depth, flag, eval, move);  return;   }   if (hashtable[hashkey].zobrist == zobrist && hashtable[hashkey].move == 0) {  hashtable[hashkey].move = move;  return;   }Then I wrote for zobrist key but now I am unable to proceed further.public class Zobrist implements Utils {//side(empty,player1,player2 ),pieces,squares    public static long[][][] ttboard = new long[3][2][42];long zobristkey;    public long RandomGenerator() {   Random random; long r;   random = new Random();   r = random.nextLong();   for (int square = 0; square < 42; square++) {  ttboard[0][0][square] = Math.abs(r);  ttboard[1][0][square] = Math.abs(r);  ttboard[2][1][square] = Math.abs(r);   } //  zobristkey^=?? return zobristkey;    }};  An important thing about Zobrist keys that you seem to have missed is that you don't need to recompute them every time. You can instead keep it as part of the board description and update it when something changes on the board. Here's some pseudo-Java:class Board {  int content[42];  unsigned long zobrist_key;    Board() { // I don't know if this is how to write a constructor in Java...    for (int i=0; i<42; ++i) content = 0;    zobrist_key = 0;  }    void make_move(int location, int color) {    content[location] = color;    zobrist_key ^= zobrist_table[location];<br>  }<br>  <br>  <span class="cpp-keyword">void</span> undo_move(<span class="cpp-keyword">int</span> location) {<br>    <span class="cpp-keyword">int</span> color = content[location];<br>    content[location] = <span class="cpp-number">0</span>;<br>    zobrist_key ^= zobrist_table[location];<br>  }<br>};<br><br></pre></div><!–ENDSCRIPT–><br><br>When adding transposition tables to an alpha-beta search, the hard part is not writing the hash class itself (you basically have that right, although you will have to revisit your replacement scheme at some point). The hard part is integrating it into the search.<br><br>Anyway, if you could just formulate a question in English about the part you are having trouble with, you'll save me reading through a lot of code I don't quite understand.<br><br>;Ok I am editing this post because I thought that it was better to experiment with my code and then let you know.  make_move(coor, player);if (hKey[hI] == zobrist_key) { // using exact matches for now.  if (depth == hDepth[hI]) { if (hType[hI] == 0) {return hVal[hI]; } if ((hType[hI] == 2) && (hVal[hI] <= alpha)) {return alpha; } if ((hType[hI] == 1) && (hVal[hI] >= beta)) {return beta; }  }   }  undo_move(coor);When I put depth <= hDepth[hI] at that time program does not look for loss many a times(some times even when its loss in 1.)but then the speed is very fast,if I put it  depth == hDepth[hI]then the search is correct but it takes lot of time to play.What wrong am I doing?[Edited by - mandar9589 on June 5, 2010 8:41:57 PM]