Transposition table for game tree (connect 4)
<p>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.</p>

<p>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.</p>

<p>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?</p>

<p>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.</p>

<p>Thanks in advance.</p>
