I have this implementation of alpha beta pruning I made a couple days ago. I've been trying to look into transposition tables.
When I tried this implementation it was slower than the original code. I even tried Zobrist hashing.
Why is my transposition table implementation slowing down Alpha Beta Pruning?
Here is the code.
pawntable = [
0, 0, 0, 0, 0, 0, 0, 0,
5, 10, 10, -20, -20, 10, 10, 5,
5, -5, -10, 0, 0, -10, -5, 5,
0, 0, 0, 20, 20, 0, 0, 0,
5, 5, 10, 25, 25, 10, 5, 5,
10, 10, 20, 30, 30, 20, 10, 10,
50, 50, 50, 50, 50, 50, 50, 50,
0, 0, 0, 0, 0, 0, 0, 0]
knightstable = [
-50, -40, -30, -30, -30, -30, -40, -50,
-40, -20, 0, 5, 5, 0, -20, -40,
-30, 5, 10, 15, 15, 10, 5, -30,
-30, 0, 15, 20, 20, 15, 0, -30,
-30, 5, 15, 20, 20, 15, 5, -30,
-30, 0, 10, 15, 15, 10, 0, -30,
-40, -20, 0, 0, 0, 0, -20, -40,
-50, -40, -30, -30, -30, -30, -40, -50]
bishopstable = [
-20, -10, -10, -10, -10, -10, -10, -20,
-10, 5, 0, 0, 0, 0, 5, -10,
-10, 10, 10, 10, 10, 10, 10, -10,
-10, 0, 10, 10, 10, 10, 0, -10,
-10, 5, 5, 10, 10, 5, 5, -10,
-10, 0, 5, 10, 10, 5, 0, -10,
-10, 0, 0, 0, 0, 0, 0, -10,
-20, -10, -10, -10, -10, -10, -10, -20]
rookstable = [
0, 0, 0, 5, 5, 0, 0, 0,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
5, 10, 10, 10, 10, 10, 10, 5,
0, 0, 0, 0, 0, 0, 0, 0]
queenstable = [
-20, -10, -10, -5, -5, -10, -10, -20,
-10, 0, 0, 0, 0, 0, 0, -10,
-10, 5, 5, 5, 5, 5, 0, -10,
0, 0, 5, 5, 5, 5, 0, -5,
-5, 0, 5, 5, 5, 5, 0, -5,
-10, 0, 5, 5, 5, 5, 0, -10,
-10, 0, 0, 0, 0, 0, 0, -10,
-20, -10, -10, -5, -5, -10, -10, -20]
kingstable = [
20, 30, 10, 0, 0, 10, 30, 20,
20, 20, 0, 0, 0, 0, 20, 20,
-10, -20, -20, -20, -20, -20, -20, -10,
-20, -30, -30, -40, -40, -30, -30, -20,
-30, -40, -40, -50, -50, -40, -40, -30,
-30, -40, -40, -50, -50, -40, -40, -30,
20,20,0,0,0,0,20,20,
20,30,10,0,0,10,30,20]
def evaluate_board(bd):
if bd.is_checkmate():
if bd.turn:
return -9999
else:
return 9999
if bd.is_stalemate():
return 0
if bd.is_insufficient_material():
return 0
wp = len(bd.pieces(chess.PAWN, chess.WHITE))
bp = len(bd.pieces(chess.PAWN, chess.BLACK))
wn = len(bd.pieces(chess.KNIGHT, chess.WHITE))
bn = len(bd.pieces(chess.KNIGHT, chess.BLACK))
wb = len(bd.pieces(chess.BISHOP, chess.WHITE))
bb = len(bd.pieces(chess.BISHOP, chess.BLACK))
wr = len(bd.pieces(chess.ROOK, chess.WHITE))
br = len(bd.pieces(chess.ROOK, chess.BLACK))
wq = len(bd.pieces(chess.QUEEN, chess.WHITE))
bq = len(bd.pieces(chess.QUEEN, chess.BLACK))
material = 100 * (wp - bp) + 320 * (wn - bn) + 330 * (wb - bb) + 500 * (wr - br) + 900 * (wq - bq)
pawnsq = sum([pawntable[i] for i in bd.pieces(chess.PAWN, chess.WHITE)])
pawnsq = pawnsq + sum([-pawntable[chess.square_mirror(i)]
for i in bd.pieces(chess.PAWN, chess.BLACK)])
knightsq = sum([knightstable[i] for i in bd.pieces(chess.KNIGHT, chess.WHITE)])
knightsq = knightsq + sum([-knightstable[chess.square_mirror(i)]
for i in bd.pieces(chess.KNIGHT, chess.BLACK)])
bishopsq = sum([bishopstable[i] for i in bd.pieces(chess.BISHOP, chess.WHITE)])
bishopsq = bishopsq + sum([-bishopstable[chess.square_mirror(i)]
for i in bd.pieces(chess.BISHOP, chess.BLACK)])
rooksq = sum([rookstable[i] for i in bd.pieces(chess.ROOK, chess.WHITE)])
rooksq = rooksq + sum([-rookstable[chess.square_mirror(i)]
for i in bd.pieces(chess.ROOK, chess.BLACK)])
queensq = sum([queenstable[i] for i in bd.pieces(chess.QUEEN, chess.WHITE)])
queensq = queensq + sum([-queenstable[chess.square_mirror(i)]
for i in bd.pieces(chess.QUEEN, chess.BLACK)])
kingsq = sum([kingstable[i] for i in bd.pieces(chess.KING, chess.WHITE)])
kingsq = kingsq + sum([-kingstable[chess.square_mirror(i)]
for i in bd.pieces(chess.KING, chess.BLACK)])
eval = material + pawnsq + knightsq + bishopsq + rooksq + queensq + kingsq
if bd.turn:
return eval
else:
return -eval
boards = {}
def alphabeta(alpha, beta, depthleft, bd):
global boards
bestscore = -9999
if depthleft == 0:
return quiesce(alpha, beta, bd)
for move in bd.legal_moves:
bd.push(move)
# implementation of transposition tables
if depthleft == 1:
try:
boards[chess.polyglot.zobrist_hash(bd)]
bd.pop()
continue
except:
boards[chess.polyglot.zobrist_hash(bd)] = 0
# done
score = -alphabeta(-beta, -alpha, depthleft - 1, bd)
bd.pop()
if (score >= beta):
return score
bestscore = max(bestscore,score)
alpha = max(alpha,score)
return bestscore
def quiesce(alpha, beta, bd):
stand_pat = evaluate_board(bd)
if stand_pat >= beta:
return beta
alpha = max(alpha,stand_pat)
for move in bd.legal_moves:
if bd.is_capture(move):
bd.push(move)
score = -quiesce(-beta, -alpha, bd)
bd.pop()
if (score >= beta):
return beta
if (score > alpha):
alpha = score
return alpha
def selectmove(depth, bd):
bestMove = chess.Move.null()
bestValue = -99999
alpha = -100000
beta = 100000
for move in bd.legal_moves:
bd.push(move)
boardValue = -alphabeta(-beta, -alpha, depth - 1, board)
if boardValue > bestValue:
bestValue = boardValue
bestMove = move
alpha = max(boardValue,alpha)
bd.pop()
return bestMove
