Answers.Body: <p>Your current implementation just stores on which positions quiesce search was ran. If it was run before, then it skips the position.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-08-11T10:39:29.297Z
Answers.LastActivityDate: 2022-08-11T10:45:27.483Z
Answers.LastEditDate: 2022-08-11T10:45:27.483Z
Answers.UserDisplayName: random_and_unknown
Body: <p>I have this implementation of alpha beta pruning I made a couple days ago. I've been trying to look into transposition tables.</p>
  <p>When I tried this implementation it was slower than the original code. I even tried Zobrist hashing.</p>
  <p>Why is my transposition table implementation slowing down Alpha Beta Pruning?</p>
  <p>Here is the code.</p>
  <pre><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 &gt;= 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 &gt;= 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 &gt;= beta):
                  return beta
              if (score &gt; 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 &gt; bestValue:
              bestValue = boardValue
              bestMove = move
          alpha = max(boardValue,alpha)
          bd.pop()
      return bestMove
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-08-12T04:11:57.483Z
Comments.Text: 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)
Comments.UserDisplayName: qwr
Tags: <python><transpositions><minimax>
Title: My Transposition Tables implementation slows down Alpha Beta Pruning
ThreadText: # My Transposition Tables implementation slows down Alpha Beta Pruning
  
  (Asked by: username_0 on 2022-08-11)
  
  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
  
  ```
  
  **Tags:** python, transpositions, minimax
  
  > **Comments:**
  > **username_1**: 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)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-08-11. Score: 6 | Accepted answer
  
  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.
  
  
  ---
  
  