Quiscence Search Performance

Question

This is a two-digit question. I put together a simple chess engine that does an alpha beta search, and then a Quiescence search at the end. Finding peace affects performance. The question is, is this effect acceptable? If not, what needs to be done to fix this problem?

The performance impact is shown in the figures below.

Please note that these statistics were taken into account in the middle of the game. FEN:

r3k2r / pb2qpbp / 1pn1pnp1 / 2PpP3 / 2B2B2 / 2N2N2 / PPPQ1PPP / R3K2R w KQkq - 0 1

Without rest:

• 6 layers in 82 069 ms (~ 82 sec)
• 5 layers in 5,298 ms (~ 5.3 sec)

In rest mode:

• 5 layers in 83 502 ms (~ 83 sec)

I did not make statistics for 6 layers using the search in the rest mode, but I would not want to calculate if necessary.

The main thing to note is that adding a rest search is equivalent to finding an additional layer. This is normal?

The following are the Alpha-Beta and Quiescence procedures in C #. They are based on the wiki chess program .

public static int AlphaBeta(Board board, int alpha, int beta, int depthLeft, int side) { if (depthLeft == 0) { return Quiescence(board, side, alpha, beta); } List<Move> moves = board.GenerateMoves(side); //nodesCount += moves.Count; BoardState state; int score; int oppositeSide = -1 * side; for (int i = 0; i < moves.Count; i++) { state = board.GetCurrentBoardState(); if (!board.MakeMove(moves[i])) { continue; } score = -AlphaBeta(board, -beta, -alpha, depthLeft - 1, oppositeSide); board.RestoreState(state); if (score >= beta) { return beta; } if (score > alpha) { alpha = score; } } return alpha; } 

Peace

  private static int Quiescence(Board board, int side, int alpha, int beta) { int standingPat = Evaluation.EvaluateFromPerspectiveOf(board, side); if (standingPat >= beta) { return beta; } if (alpha < standingPat) { alpha = standingPat; } int oppositeSide = -1 * side; List<Move> moves = board.GenerateMoves(side); int score; BoardState state; for (int i = 0; i < moves.Count; i++) { if (!board.IsCaptureMove(moves[i])) { continue; } //nodesCount++; state = board.GetCurrentBoardState(); if (!board.MakeMove(moves[i])) { continue; } score = -Quiescence(board, oppositeSide, -beta, -alpha); board.RestoreState(state); if (score >= beta) { return beta; } if (score > alpha) { alpha = score; } } return alpha; } 

Answer 1

Well, a search in search of a call sign should have a penalty for performance, as it searches deeper in some lines to stabilize the position estimate. But this should not be so much: the capture lines are quite rare and cannot be as numerous as the entire 6th layer.

You might want to display the number of positions evaluated, and then see how many positions are processed by Quiscence. This number should not be large. Make sure your Quiscence search also uses alpha beta cropping.

In addition, these search times (5 seconds for 5-layer depth and 82 seconds for 6-layer depth) seem very slow. Maybe something is wrong with the beta cut-off or with moving orders in the search (that is, you are looking for a complete tree), or your compiler does not perform any optimizations. Any modern chess engine reaches a depth of 5 in the blink of an eye.

Another hint: usually Quiscence search uses a separate movement generator that only generates paw captures, checks and advancements (such a generator is simpler and faster than usual).