Alpha Beta Searching and Transposition Tables

Question

I have alpha beta search working and want to implement transposition tables to make it faster. The problem I'm having is the relationship between the entries in the table and the current position being evaluated.

The literature I've read so far says you need to store the position type, the score, and some other information. Why do you have to store the type? Can't you just use the score as long as the entry in the table from a previous search went deeper?

This page shows some sample code to do it, but I can't figure out why the AB search returns beta when alpha>=beta. Shouldn't you be returning alpha?

Thanks,

ZW

Answer 1

You might store the position if your hash function can produce collisions. You would also need to store the position depth, as you note, to assure that the score is from a deeper search. and of course, you must store the score.

As for your second question... that is known as a Beta cutoff. The premise is your opponent has already found a better line for himself earlier in the search and initialized that score to Beta (negative alpha, passed as beta for you)... when testing your moves, if you can at any point beat Beta, he doesn't care by how much you can beat it by and he will just cull the rest of the search in that branch. The easiest way to do that is just return beta.