When the move list is very small, like captures normally
are, it is faster to pick the best move with a linear
scan, one per cycle.
This has the added advantage that the picked capture move is
very possibly a cut-off move, so that other searches are
avoided. For non-captures it is still faster to sort in
advance.
Because scan-and-pick alghortim is not stable, node count
has changed.
After 885 games at 1+0
Mod vs Orig +196 =510 -179 50.96% 451.0/885
Signed-off-by: Marco Costalba <mcostalba@gmail.com>
+// Picks up the best move in range [curMove, lastMove), one per cycle.
+// It is faster then sorting all the moves in advance when moves are few,
+// as normally are the possible captures. Note that is not a stable alghoritm.
+template<typename T>
+inline T pick_best(T* curMove, T* lastMove)
+{
+ T bestMove, tmp;
+
+ bestMove = *curMove;
+ while (++curMove != lastMove)
+ {
+ if (*curMove < bestMove)
+ {
+ tmp = *curMove;
+ *curMove = bestMove;
+ bestMove = tmp;
+ }
+ }
+ return bestMove;
+}
+
////
//// Inline functions
////
////
//// Inline functions
////
case PH_GOOD_CAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
case PH_GOOD_CAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
- sort_moves(moves, lastMove);
// to get SEE move ordering.
curMove = badCaptures;
lastMove = lastBadCapture;
// to get SEE move ordering.
curMove = badCaptures;
lastMove = lastBadCapture;
- sort_moves(badCaptures, lastMove);
return;
case PH_EVASIONS:
assert(pos.is_check());
lastMove = generate_evasions(pos, moves, pinned);
score_evasions();
return;
case PH_EVASIONS:
assert(pos.is_check());
lastMove = generate_evasions(pos, moves, pinned);
score_evasions();
- sort_moves(moves, lastMove);
return;
case PH_QCAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
return;
case PH_QCAPTURES:
lastMove = generate_captures(pos, moves);
score_captures();
- sort_moves(moves, lastMove);
{
while (curMove != lastMove)
{
{
while (curMove != lastMove)
{
- move = (curMove++)->move;
-
switch (phase) {
case PH_TT_MOVES:
switch (phase) {
case PH_TT_MOVES:
+ move = (curMove++)->move;
if ( move != MOVE_NONE
&& move_is_legal(pos, move, pinned))
return move;
break;
case PH_GOOD_CAPTURES:
if ( move != MOVE_NONE
&& move_is_legal(pos, move, pinned))
return move;
break;
case PH_GOOD_CAPTURES:
+ move = pick_best(curMove++, lastMove).move;
if ( move != ttMoves[0].move
&& move != ttMoves[1].move
&& pos.pl_move_is_legal(move, pinned))
if ( move != ttMoves[0].move
&& move != ttMoves[1].move
&& pos.pl_move_is_legal(move, pinned))
+ move = (curMove++)->move;
if ( move != MOVE_NONE
&& move != ttMoves[0].move
&& move != ttMoves[1].move
if ( move != MOVE_NONE
&& move != ttMoves[0].move
&& move != ttMoves[1].move
break;
case PH_NONCAPTURES:
break;
case PH_NONCAPTURES:
+ move = (curMove++)->move;
if ( move != ttMoves[0].move
&& move != ttMoves[1].move
&& move != killers[0].move
if ( move != ttMoves[0].move
&& move != ttMoves[1].move
&& move != killers[0].move
case PH_EVASIONS:
case PH_BAD_CAPTURES:
case PH_EVASIONS:
case PH_BAD_CAPTURES:
+ move = pick_best(curMove++, lastMove).move;
return move;
case PH_QCAPTURES:
return move;
case PH_QCAPTURES:
+ move = pick_best(curMove++, lastMove).move;
+ if ( move != ttMoves[0].move
+ && pos.pl_move_is_legal(move, pinned))
+ return move;
+ break;
+
- // Maybe postpone the legality check until after futility pruning?
+ move = (curMove++)->move;
if ( move != ttMoves[0].move
&& pos.pl_move_is_legal(move, pinned))
return move;
if ( move != ttMoves[0].move
&& pos.pl_move_is_legal(move, pinned))
return move;