In a typical minimax alpha-beta, hash tables improve performance by avoiding to examine again nodes already evaluated. But the value of each node in the hash table does not have its actual value. If there has been alpha-beta prunning, its real value is the one stored or worse (better). In a new search (say, two moves later), even if you get into a node that's already on the table (from the previous tree search), you cannot use it because its value is not real. So, in fact, the hash table is worthless among searches, it's only valid during the same search. Am I wrong? Is there any way to take advantadge of the node having been analyzed in a previous tree search? Thanks

That the value for a node is not exact does not mean it is useless. You can use its value to get a tighter bound in the new search, perhaps even get a cut off. You just have to store a flag with this value that indicates wether it is exact or a lower or upper bound on the real value, so that you know how to use it later. You also store the best move found at every node, so that you can search this move first in the next search, thereby improveing move ordering dramatically, especially when used with iterative deepening.

Sorry if this is just a summary, I don't have time to be detailed and I'm sure someone else will fill you in. Besides, google's got all the answers.

Thanks Anonymous, it helps a lot.

Be VERY CAREFUL with re-using hash tables on later moves, at each value stored in the table you have to also associate with that value what depth its good for. Because if you have a hash entry for a certain game state, but its score was based on a search tree of 4 moves deep (below that state), & you want to use its that hash entry at a level that requires 5 levels deep, its score is not useful to you, you need to discard that hash-entry.

In summary, only use hash entries when their depth matches or is greater than your current search depth. Also... just in case you want a side tip:

depending the game you are coding up, its usually a good idea
to do a quiescence search as well. Because even though a
jump, or a score, or a kill looks real good at one level, the
very next move could result in a double jump or death for
yourself.

The re-use of hash entries between moves begins to shine within an iterative-deepening framework.

If the engine iterates up to 10 ply every time, then the last 2 ply of any given move will of course be entirely "new territory" but the first 8 ply will be able to take advantage of previous searches.

I think nobody has mentioned move ordering. Alpha-beta's performance depends dramatically on how well you order the moves: good moves should be searched first. One of the important uses of hash tables is actually storing which move was found to be best (or good enough to provoke a beta cut), so it can be tried first in the new search. This works even when the stored depth is lower than the current search depth; the move that was best in depth 4 is a good candidate to be the best move in depth 5.

I always analyze the whole game (a trick tacking card game, bridge-like) unless a cut-off occurs. Currently 10 tricks (40 ply) is within a reasonable time although I would need 12 (48 ply). From time to time, a game takes an enormous time to complete: nodes examined are usually in the range 50/100 million, but I've reached 2.000 million!!.

Move ordering is crucial, I obtained a ratio of aprox 30 times better with my current algorithm. Also, forward prunning revealed more than valuable.

On the transposition tables I store the best move to analyze it first as alvaro suggests.

The hits on the TT allow aprox. a 85% of "inmediate return" while another 15% of the hits are useless. The hits that allow for an alpha-beta adjustement are negligible (less than 0.5%).

Currently I'm conducting a series of tests to compare NegaScout with MTD(f). First results show that MTD(f) WITH A PERFECT GUESS (obtained from previous NegaScout) returns the result in about 55%/60% of the NegaScout time, while MTD(f) WITH A MEDIUM GUESS (deliberately not good enough, just to compare) needs 125% of the NegaScout time.

I still need to work on how to obtain the Principal Variation, specially with MTD(f).

Thanks again to everybody.