I'm adding TT to my negascout function and I'm using zobrist keys. I have a question with regard to storing the score in the table. When storing the best move as well, is this always the best move that is updated in the root function?

No. The best move stored in the transposition table is the move that happened to be best the last time we search the node. The point is that if we ever visit this node again, even if we cannot skip the search with the information stored in the TT (because we are now searching at higher depth or because the bound stored wasn't good enough), we can still try that move first. This is particularly important when the move caused a beta cut-off. Chances are pretty good that the same move will also cause a beta cut-off at higher depth and save us a ton of time.

When there's a beta cut-off I save the entry as follows:

setTT(key, depth, a, TTEntry.BOUND_UPPER, moves.get(i));

Before I exit the function returning 'a', I save the entry as follows:

setTT(key, depth, a, TTEntry.BOUND_LOWER, null);

But shouldn't I store an actual move instead of null?

When I attempt to find a move at the beginning of the function, I do the following:

        if (depth == maxDepth)
        {
        	val = board.getScore();
        	setTT(key, depth, val, TTEntry.BOUND_EXACT, null);
        	
        	return val;
        }

Also, should the TT applied to the recursive function or also to the root?

I think you have the bounds wrong. When you have a buta cut-off you want to store it as a lower bound. When you exit the function returning alpha, you have either an upper bound (if alpha was never improved) or an exact score (if alpha was improved).

http://web.archive.org/web/20080315233307/http://www.seanet.com/~brucemo/topics/hashing.htm

The transposition table is for the recursive function only (and perhaps for quiescence search, if your program has it). I don't see any point in doing anything with the transposition table at the root.

Ooopss I swapped them. I still don#t have quiescence search but I'm planning to add one soon... right after iterative deepening!!

Ooopss I swapped them. I still don#t have quiescence search but I'm planning to add one soon... right after iterative deepening!!

If you are programming chess, I would implement quiescence search immediately. The results of the search are almost meaningless without it.

No I'm working on the nine men morris game for now. I will use quiescence search to return just the moves that will form mills. I think that would be similar to to capture moves in chess.

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

No I'm working on the nine men morris game for now. I will use quiescence search to return just the moves that will form mills. I think that would be similar to to capture moves in chess.

Oh, in that case it might help, but I don't think it will be as critical as in chess.

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

That's a very tricky thing to test. I would implement iterative deepening right away. You should then observe the behavior where after searching up to depth D, repeating the search gets you to depth D almost instantly. If that doesn't happen, you are probably doing something wrong.

You should pick a few positions and measure the number of nodes and the time it takes for the search to reach a particular depth. Although the speed in nodes per second will probably go down after implementing the transposition table, the time to reach a depth should go down.

Finally, you should play a match between your program with and without transposition tables. How many games to play is a tricky question, but I wouldn't do less than a thousand. They can be quite fast (for chess I use about 0.2 seconds per move). The important thing here is accumulating statistics. I would also observe the two programs playing at slower pace (say 10 seconds per move), so you can see what they are doing and notice if there's something broken.

I do what I described in the previous paragraph for almost every change to my program. If you don't do something like that, I don't think you can make meaningful progress.

Thanks for the tips. I will definitely do like that. I already thought that I'd need to add iterative deepening to test transposition tables better. That will be my next task!!

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

One thing I've done is to perform each search with TT on and TT off and then check that the same result is being returned. The TT shouldn't affect the result (only in extremely rare instances) compared to a normal search - it should only affect the speed.