Answers.Body: <p>sounds like you're missing a negative sign somewhere. I don't know where the exact problem is, but you should really consider using negamax instead. It's much cleaner and is a lot easier to handle once you get used to it. I don't know where the problem is, but I think in the long run you'll save a lot of work and debugging by using negamax instead.</p>
  <p>But, here is some sample code from my engine if it helps:
  (Note that depth is used to mean depth from root,)</p>
  <pre><code> if allowNull and depth != 0 and (maxSearchDepth - depth) &gt;= 2:  # dont search leaf/frontier nodes, NMP wastes energy here
          if not GetGamePhase(board) &lt; MAX_ENDGAME_PHASE:  # don't null move in potential zugzwang positions
              if not IsCheck(board):
                  board[64] = 1 - board[64]  # flip turn flag                  
                  epTemp = board[69]
                  board[69] = 8  # no ep
                  nullMoveScore = -Search(board, maxSearchDepth - R, -beta, -beta + 1, depth + 1, allowNull=False)      
                  board[64] = 1 - board[64]  # unflip turn flag
                  board[69] = epTemp # reset ep flag
                  if nullMoveScore &gt;= beta:
                      return beta
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-20T18:50:04.857Z
Answers.LastActivityDate: 2024-12-20T18:56:31.637Z
Answers.LastEditDate: 2024-12-20T18:56:31.637Z
Answers.UserDisplayName: user43110
Body: <p>I've recently implemented Null Move Pruning into my Chess AI (written in VB.net), but unfortunately it is not actually saving the search any time, in pretty much any position. I was just wondering if there are any apparent flaws in my approach, or implementation, of this NMP algorithm?</p>
  <p>I'm currently using <code>R = 3</code> (but have tried <code>R = 2</code>), and I use MiniMax, rather than NegaMax, in my search algorithm (I could technically migrate to NegaMax, but that would take a while, and I doubt it'd make my engine stronger?). Hopefully that doesn't make things too hard to follow, although I fear that the issue with this algorithm has to do with that structure (as it changes the meaning of Alpha &amp; Beta from ~{best move for me, best move for opponent} to ~{best move for white, best move for black}).</p>
  <p>A couple of test positions:</p>
  <ol>
  <li><p>r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - (~60% slower with NMP on, although this is mainly for the higher depths (ie: 8+). Lower depths seem to be unaffected).</p>
  </li>
  <li><p>r1b1kb1r/2pp1ppp/1np1q3/p3P3/2P5/1P6/PB1NQPPP/R3KB1R b KQkq - (roughly 40% slower with NMP, although funnily enough if I enable NMP for <em>only</em> the black pieces, I do see a significant performance increase! This is not the case for the first test position).
  I've also experimented with different Alpha-Beta windows, and only using NullMoves if <code>Alpha = Beta - 1</code>. Nothing seems to work.</p>
  </li>
  </ol>
  <p>My code is below (I've only included lines which are essential to this implementation).</p>
  <p>The ActNullMove sub: (reversible??)</p>
  <pre><code>Sub ActNullMove(Board, EnPassant, ZobristValue)
          'Removes EnPassant Privileges from the hash value.
          If EnPassant &lt;&gt; 0 Then ZobristValue = ZobristValue Xor ZobristHashTable(2, 0, (EnPassant And 56) &gt;&gt; 3, EnPassant And 7)
          'Changes the player to move on the Zobrist Key.
          ZobristValue = ZobristValue Xor HashConstants(0)
      End Sub
  </code></pre>
  <p>And the main search algorithm:</p>
  <pre><code>If depth &gt;= 4 AndAlso not PlayerInCheck AndAlso CanTakeNullMove AndAlso PieceInPos Then
      StandPat = Evaluate(Board, MaterialCount, WKPos, BKPos)
      If WhiteTurn Then
          If StandPat &gt;= Beta Then
              ActNullMove(Board, EnPassant, ZobristValue)
              DepthFromRoot += 1
              BestMove = MiniMax(Board, depth - SearchSettings.NullMoveRValue - 1, WhiteTurn=False, EnPassant=0, ZobristValue, Beta - 1, Beta, CanTakeNullMove=False)
              DepthFromRoot -= 1
              ActNullMove(Board, EnPassant, ZobristValue)
              If Beta &lt;= BestMove Then Return Beta
          End If
      Else
          If StandPat &lt;= Alpha Then
              ActNullMove(Board, EnPassant, ZobristValue)
              DepthFromRoot += 1
              BestMove = MiniMax(Board, depth - SearchSettings.NullMoveRValue - 1, WhiteTurn=True, EnPassant=0, ZobristValue, ZobristValue, Alpha, Alpha + 1, CanTakeNullMove=False)
              DepthFromRoot -= 1
              ActNullMove(Board, EnPassant, ZobristValue)
              If BestMove &lt;= Alpha Then Return Alpha
          End If
      End If
  End If
  </code></pre>
  
Tags: <programming><minimax>
Title: Null Move Pruning Makes my Engine Slower on almost all Positions
ThreadText: # Null Move Pruning Makes my Engine Slower on almost all Positions
  
  (Asked by: username_0 on 2024-12-20)
  
  I've recently implemented Null Move Pruning into my Chess AI (written in VB.net), but unfortunately it is not actually saving the search any time, in pretty much any position. I was just wondering if there are any apparent flaws in my approach, or implementation, of this NMP algorithm?
  
  I'm currently using `R = 3` (but have tried `R = 2`), and I use MiniMax, rather than NegaMax, in my search algorithm (I could technically migrate to NegaMax, but that would take a while, and I doubt it'd make my engine stronger?). Hopefully that doesn't make things too hard to follow, although I fear that the issue with this algorithm has to do with that structure (as it changes the meaning of Alpha & Beta from ~{best move for me, best move for opponent} to ~{best move for white, best move for black}).
  
  A couple of test positions:
  
  1. r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - (~60% slower with NMP on, although this is mainly for the higher depths (ie: 8+). Lower depths seem to be unaffected).
  2. r1b1kb1r/2pp1ppp/1np1q3/p3P3/2P5/1P6/PB1NQPPP/R3KB1R b KQkq - (roughly 40% slower with NMP, although funnily enough if I enable NMP for *only* the black pieces, I do see a significant performance increase! This is not the case for the first test position).
     I've also experimented with different Alpha-Beta windows, and only using NullMoves if `Alpha = Beta - 1`. Nothing seems to work.
  
  My code is below (I've only included lines which are essential to this implementation).
  
  The ActNullMove sub: (reversible??)
  
  ```
  Sub ActNullMove(Board, EnPassant, ZobristValue)
          'Removes EnPassant Privileges from the hash value.
          If EnPassant <> 0 Then ZobristValue = ZobristValue Xor ZobristHashTable(2, 0, (EnPassant And 56) >> 3, EnPassant And 7)
          'Changes the player to move on the Zobrist Key.
          ZobristValue = ZobristValue Xor HashConstants(0)
      End Sub
  
  ```
  
  And the main search algorithm:
  
  ```
  If depth >= 4 AndAlso not PlayerInCheck AndAlso CanTakeNullMove AndAlso PieceInPos Then
      StandPat = Evaluate(Board, MaterialCount, WKPos, BKPos)
      If WhiteTurn Then
          If StandPat >= Beta Then
              ActNullMove(Board, EnPassant, ZobristValue)
              DepthFromRoot += 1
              BestMove = MiniMax(Board, depth - SearchSettings.NullMoveRValue - 1, WhiteTurn=False, EnPassant=0, ZobristValue, Beta - 1, Beta, CanTakeNullMove=False)
              DepthFromRoot -= 1
              ActNullMove(Board, EnPassant, ZobristValue)
              If Beta <= BestMove Then Return Beta
          End If
      Else
          If StandPat <= Alpha Then
              ActNullMove(Board, EnPassant, ZobristValue)
              DepthFromRoot += 1
              BestMove = MiniMax(Board, depth - SearchSettings.NullMoveRValue - 1, WhiteTurn=True, EnPassant=0, ZobristValue, ZobristValue, Alpha, Alpha + 1, CanTakeNullMove=False)
              DepthFromRoot -= 1
              ActNullMove(Board, EnPassant, ZobristValue)
              If BestMove <= Alpha Then Return Alpha
          End If
      End If
  End If
  
  ```
  
  **Tags:** programming, minimax
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-12-20. Score: 0
  
  sounds like you're missing a negative sign somewhere. I don't know where the exact problem is, but you should really consider using negamax instead. It's much cleaner and is a lot easier to handle once you get used to it. I don't know where the problem is, but I think in the long run you'll save a lot of work and debugging by using negamax instead.
  
  But, here is some sample code from my engine if it helps:
  (Note that depth is used to mean depth from root,)
  
  ```
   if allowNull and depth != 0 and (maxSearchDepth - depth) >= 2:  # dont search leaf/frontier nodes, NMP wastes energy here
          if not GetGamePhase(board) < MAX_ENDGAME_PHASE:  # don't null move in potential zugzwang positions
              if not IsCheck(board):
                  board[64] = 1 - board[64]  # flip turn flag                  
                  epTemp = board[69]
                  board[69] = 8  # no ep
                  nullMoveScore = -Search(board, maxSearchDepth - R, -beta, -beta + 1, depth + 1, allowNull=False)      
                  board[64] = 1 - board[64]  # unflip turn flag
                  board[69] = epTemp # reset ep flag
                  if nullMoveScore >= beta:
                      return beta
  
  ```
  
  
  ---
  
  