Transposition tables for python chess engine

Question

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.

Burnsed

Answer 1

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.

Bristle

Thanks. I'll definitely take a look at your code. Gonna do some more research on this topic and see what I can find. – Burnsed