2

I am making a Connect 4 app for Android and right now I am using a minimax algorithm coupled with alpha-beta prunning and heuristic evaluation function for leaf nodes. I also ordered the moves to further maximize the pruning process. Unfortunately with that strategy the algorithm takes too much time in depth 7, leading me to abandon it in favor of using a transposition table.

Now, I've read information about transposition tables and have got a general idea of how they work, but I am unsure how to proceed with the actual implementation in code. I am not a Java expert so I need any help you can give me.

In my game I am using a int[42] array for the board positions. I thought of using a hash map and storing some kind of data structure objects, where every one of these object will include the board position(array) and an int "score"variable (which would in fact be the score given to this position by the evaluation function). But, that means that every time I want to put a new board position in the table I need to perform some kind of check to see if this position does not exist already(??). And if not, only then insert into the table?

I will be glad for any technical help you guys can give me on this subject. I can put some code examples if needed, but this is a general question and I don't think they are really necessary at this point.

Thanks in advance.

1 Answer 1

2

You can use a technique from chess transposition tables: Zobrist hashing. Basically instead of storing the entire board, you compute a long that serves as a hash key for the position, and store that along with the relevant data. It has the additional benefit of being able to be incrementally updated. Instead of generating the key from scratch when making moves, you can update the key with a single bitwise XOR operation (very fast).

Basically, generate some random numbers for each square (slot?). You need one for each side. I assume that black = 0 and red = 1 for easy indexing. Initialization looks like

long[][] zobrist = new long[42][2];
for (int square = 0; square < zobrist.length; square++) 
   for (int side = 0; side < zobrist[i].length; side++)
      zobrist[square][side] = RandomLong();

You will need to find a PRNG that generates a random long for RandomLong(). Make sure it has good randomness when looking at the bits. I recommend against using LCGs.

To compute the hash key for a position from scratch, you just need to XOR together all the zobrist values.

long computeKey(int[] board) {
   long hashKey = 0;
   for (int square = 0; square < board.length; square++)
      if (hasPiece(board[square])) {
         int side = getColour(board[square]);
         hashKey ^= zobrist[square][side];
      }
}

To incrementally update, just XOR the effect of the move. This is when you want to make a move and just update the key.

long updateKey(long oldKey, int moveSquare, int moveSide) {
   return oldKey ^ zobrist[moveSquare][moveSide];
}

To unmake the move and get the old key, the above function works too! XOR behaves like negation in logic, so applying it twice gets you back your original key.

4
  • thank you very much! ..yes,I am now remembering that i heard about the Zobrist hashing concept,but never got into it. it will explore it further, but just so you know,my rather little knowledge and experience in programming will proabaly lead me to using a more simple and straight farward techniques..this is also the reason why my search and evaluation functions are not ideal and probably take much more time than they actually need. but thx again for the info, and i wanted to give you vote up but it won't let me :) May 28, 2013 at 5:55
  • I've added lots of code examples. It's not too hard. I think you're still able to accept the answer if you like it.
    – Zong
    May 28, 2013 at 6:07
  • thank you, i am scanning your code example right now and it is written well. this conecpt and operations is rather new to me and i need some time to read and understand what's going on. if i see that i understand this,i will go for it (at least try to implement it in my code). thanks again for the good answer though,very appreciated :) and ofcoruse i will except your answer, i just want to wait for some other replies as well. May 28, 2013 at 6:14
  • let's say i want to implement the hash table in a more straight farward way ,maybe using arrays and hashMap instead of creating random longs.. how should i do it? what is the simplest approach? May 28, 2013 at 6:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.