2

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
1
  • 3
    I argue there's little point in trying to optimize pure python code for speed, even with pypy. The python interpreter is so abstracted from the bare metal that certain operations run way slower than they should for no good reason (people have tried for competition programming)
    – qwr
    Commented Aug 12, 2022 at 4:11

1 Answer 1

6

Your current implementation just stores on which positions quiesce search was ran. If it was run before, then it skips the position.

But you don't want to skip searching all positions you searched previously. You need to store the result of each (quiesce) search into the transposition table, and then use those values as the position score, so running the search again isn't necesarry.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.