This is a follow-up to my last post. The code works without any errors and can calculate the next best move. I've been looking into how to incorporate transposition tables and move ordering into my negamax function to make it run faster and more accurately, but it seems somewhat difficult and advanced for a beginner like myself.
You can find my code here.
While researching on the chess programming wiki I found some sample code for transposition tables:
def negamax(node, depth, alpha, beta, color):
alphaOrig = alpha
## Transposition Table Lookup; node is the lookup key for ttEntry
ttEntry = transpositionTableLookup(node)
if ttEntry.is_valid is True and ttEntry.depth >= depth:
if ttEntry.flag == EXACT :
return ttEntry.value
if ttEntry.flag == LOWERBOUND:
alpha = max(alpha, ttEntry.value)
if ttEntry.flag == UPPERBOUND:
beta = min(beta, ttEntry.value)
if alpha >= beta:
return ttEntry.value
if depth == 0 or node is terminal_node:
return color* heuristic_value_of_node
childNodes = domove(node)
childNodes = orderMoves(childNodes)
bestValue = -99999
for child in childNodes:
bestValue = max(bestValue, -negamax(child, depth - 1, -beta, -alpha, -color))
alpha = max(alpha, bestValue)
if alpha >= beta:
break
##Transposition Table Store; node is the lookup key for ttEntry
ttEntry.value = bestValue
if bestValue <= alphaOrig:
ttEntry.flag = UPPERBOUND
if bestValue >= beta:
ttEntry.flag = LOWERBOUND
else:
ttEntry.flag = EXACT
ttEntry.depth = depth
transpositionTableStore(node, ttEntry)
return bestValue
I tried making a few modifications to integrate it into my code, but I didn't get any results out of it. I've also seen something about storing hash keys with a Zobrist key for the positions, but I didn't understand well how it worked so I dropped the idea. Currently somewhat stuck with these problems and don't know what the next step is.
To use transposition tables you "need" to use Zorbrist hashing. The hashing gives each position an (almost) unique code that you store in the transposition table along with its evaluation. Then, to explain it easily, if the current position you are searching is found in your transposition table you won't have to evaluate it again, you just use the stored value.
Zorbrist keys are a nightmare to get right and very hard to debug. If it helps you can check out my implementation in the Endamat Chess Engine, but since you might have a different approach it might be easier to just read on how Zorbrist keys works and try to get it right for your implementation.