Lazy sorting algorithm - Sorting on steroids

[JohnWoe]

I published a paper here: https://github.com/SamuraiDangyo/lazy-sorting-algorithm

For those not using this algorithm. It gives a massive speedup. It gives a general case for this algorithm.

I used to simply generate all moves -> Sort them all -> Search. This was simple but slow. Then I all of the sudden figured out the best way to sort moves and such. I came out of chess programming retirement and published: Lazy sorting !

[hgm]

Isn't this exactly what eveyone has been doing for an eternity already? Just extract the single move with the highest key from those that have not been searched yet?

For sorting non-captures by history I prefer another method: just distribute all moves over a large number of logarithmically spaced narrow bins, creating a linked list for each bin. And then run through the bins. This is O(n) sorting, and hardly takes any effort over determining the sort-key values.

[JohnWoe]

Isn't this exactly what eveyone has been doing for an eternity already? Just extract the single move with the highest key from those that have not been searched yet?

Could be. Not obvious to me. This paper is for those not using this algorithm yet. You still need to selection sort the remaining list. You can't just pick some move. Like I said in the paper in chunks. Selection sort the list if small. Then just lazy sort.
Edit: Not sorting you have N if-operations all the time. With selection sort N - 1 if-operations + only 1 swap. The list is getting smaller as N -> 0

[lithander]

I do it like this:

Code: Select all

        private void PickBestMove(int first, int last)
        {
            //we want to swap the first move with the best move
            int best = first;
            int bestScore = Moves[first].MvvLvaScore();
            for (int i = first + 1; i <= last; i++)
            {
                int score = Moves[i].MvvLvaScore();
                if (score >= bestScore)
                {
                    best = i;
                    bestScore = score;
                }
            }
            //swap best with first
            if (best != first)
            {
                Move temp = Moves[best];
                Moves[best] = Moves[first];
                Moves[first] = temp;
            }
        }

MvvLVaScore is cheap to get. You swap the best move with the one in the first slot. Then you can just iterate over all moves with a basic for loop. Because you usually don't have to play all moves until you get a cutoff it's cheaper even though the worst case is O(n^2)

Code: Select all

for (int i = firstMove; i <= lastMove; i++)
{
	PickBestMove(i, lastMove);
	Play(Moves[i]);
	...
}

[AndrewGrant]

This is already the standard. Score moves, grab the best one. Keep grabbing until cutoff.

[Ras]

Then I all of the sudden figured out the best way to sort moves and such. I came out of chess programming retirement and published: Lazy sorting !

I pick the highest move with selection sort, and if that doesn't give a beta cut-off, I sort the rest of the move list with Shellsort.

[mvanthoor]

I used to simply generate all moves -> Sort them all -> Search. This was simple but slow. Then I all of the sudden figured out the best way to sort moves and such. I came out of chess programming retirement and published: Lazy sorting !

Not to be pedantic, but in this case I have to agree with HGM. Most engines nowadays don't just generate all moves, completely sort the list and then start searching. The reason is that you are doing all of that work, just to end up with the very first move in the list creating a beta-cut 85-90% of the time. You wasted all the work of generating and sorting those moves.

Therefore most engines do a pick_move() at the very least: generate all the moves. Then do order_move(&move_list). This function runs through all the moves, and puts the best move with the highest score first. So if you generate 31 pseudo-legal moves and you just start the search, the best move will be put at index 0. If this doesn't create a beta-cutoff, the next pass will be at index 1, so the best move of the remaining list will be put at index 1. And so on.

So you save all the effort of sorting the entire list, especially if the very first move causes a beta-cutoff.

Rustic has had this since Alpha 1.

A further optimization is implementing staged move generation: first try playing the TT-move if you have one; if it causes a beta-cutoff, you save ALL of the move generation and sorting. If it doesn't, you generate all the captures, and then do a pick_move() on those. (Make sure you skip the TT-move if it is in there.) If that doesn't give you a beta-cutoff either, you then generate the quiet moves and do a pick_move() on those.

This is a three-staged move generation. You can extend that with first trying the killers, even before the captures, to try to save even the capture generation if the TT-move doesn't cause a beta-cutoff; but I don't know if having more than three stages is useful. Because the TT-move causes so many cut-offs, I can see a quickly diminishing return for every stage you add after that.

Rustic will have three-staged move generation at version 5.

[pedrojdm2021]

I never knew that it had a name

i do it in a very similar way:

Code: Select all

// populate move list with new moves
sbyte target_move_index = board.GenerateMoves(in move_list[ply]);
for (sbyte moveIndex = 0; moveIndex <= target_move_index; moveIndex++)
{
	OrderMoves(moveIndex, target_move_index);
	.......

And the orderMoves:

Code: Select all

private static void OrderMoves(sbyte _currentIndex, sbyte _moveIndex)
{
	int score = 0;
	int best_score = GuessMoveScore(move_list[ply][_currentIndex]);
	sbyte best_index = _currentIndex;

	for (sbyte moveIndex = _currentIndex; moveIndex <= _moveIndex; moveIndex++)
	{
		score = GuessMoveScore(move_list[ply][moveIndex]);
		if (score >= best_score)
		{
			best_score = score;
			best_index = moveIndex;
		}
	}

	// swap the values
	(move_list[ply][_currentIndex], move_list[ply][best_index]) =
		(move_list[ply][best_index], move_list[ply][_currentIndex]);
}

it works pretty good

[Algorhythm]

After reading this thread I had my doubts; quicksorting a list of some tens of moves is not going to be slow by any means, surely an O(N^2) selection sort, even if it has potential to finish early can't be a significant improvement on the naive case?

So I tested a version of my engine with and without this feature and after 800 games the naive case actually came out on top:

Code: Select all

Score of 18_lazy_sorting vs full_sorting: 336 - 354 - 110  [0.489] 800
...      18_lazy_sorting playing White: 187 - 171 - 42  [0.520] 400
...      18_lazy_sorting playing Black: 149 - 183 - 68  [0.458] 400
...      White vs Black: 370 - 320 - 110  [0.531] 800
Elo difference: -7.8 +/- 22.4, LOS: 24.7 %, DrawRatio: 13.8 %
SPRT: llr -0.985 (-33.4%), lbound -2.94, ubound 2.94

Test setup:

• cutechess-cli

• Titans.bin polyglot openings

• 64MB transposition table

• Play 2 games in each opening with flipped colors

• Time control: 10s+0.01

Possible contending factors:

• I am writing my engine in Rust, and [T]'s sort_unstable_by_key function uses a pattern-defeating quicksort as per the docs which may be fast enough to outstrip this technique on its own

• I implemented this technique using Rust's Iterator trait for nice idiomatic code, perhaps this was adding additional overhead

While writing this post I discovered that Rust's [T] now has the select_nth_unstable family of functions which perform this selection using the quickselect portion of the quicksort algorithm. I ran the test again but after 630 games it seems to perform even worse:

Code: Select all

Score of vec_select vs full_sorting: 284 - 326 - 24  [0.467] 634
...      vec_select playing White: 116 - 185 - 16  [0.391] 317
...      vec_select playing Black: 168 - 141 - 8  [0.543] 317
...      White vs Black: 257 - 353 - 24  [0.424] 634
Elo difference: -23.0 +/- 26.6, LOS: 4.5 %, DrawRatio: 3.8 %
SPRT: llr -1.53 (-51.9%), lbound -2.94, ubound 2.94

I'd be interested to hear how others' numbers compare, or anything you think I've missed!

[JohnWoe]

After reading this thread I had my doubts; quicksorting a list of some tens of moves is not going to be slow by any means, surely an O(N^2) selection sort, even if it has potential to finish early can't be a significant improvement on the naive case?

So I tested a version of my engine with and without this feature and after 800 games the naive case actually came out on top:

Code: Select all

Score of 18_lazy_sorting vs full_sorting: 336 - 354 - 110  [0.489] 800
...      18_lazy_sorting playing White: 187 - 171 - 42  [0.520] 400
...      18_lazy_sorting playing Black: 149 - 183 - 68  [0.458] 400
...      White vs Black: 370 - 320 - 110  [0.531] 800
Elo difference: -7.8 +/- 22.4, LOS: 24.7 %, DrawRatio: 13.8 %
SPRT: llr -0.985 (-33.4%), lbound -2.94, ubound 2.94

Test setup:

• cutechess-cli

• Titans.bin polyglot openings

• 64MB transposition table

• Play 2 games in each opening with flipped colors

• Time control: 10s+0.01

Possible contending factors:

• I am writing my engine in Rust, and [T]'s sort_unstable_by_key function uses a pattern-defeating quicksort as per the docs which may be fast enough to outstrip this technique on its own

• I implemented this technique using Rust's Iterator trait for nice idiomatic code, perhaps this was adding additional overhead

While writing this post I discovered that Rust's [T] now has the select_nth_unstable family of functions which perform this selection using the quickselect portion of the quicksort algorithm. I ran the test again but after 630 games it seems to perform even worse:

Code: Select all

Score of vec_select vs full_sorting: 284 - 326 - 24  [0.467] 634
...      vec_select playing White: 116 - 185 - 16  [0.391] 317
...      vec_select playing Black: 168 - 141 - 8  [0.543] 317
...      White vs Black: 257 - 353 - 24  [0.424] 634
Elo difference: -23.0 +/- 26.6, LOS: 4.5 %, DrawRatio: 3.8 %
SPRT: llr -1.53 (-51.9%), lbound -2.94, ubound 2.94

I'd be interested to hear how others' numbers compare, or anything you think I've missed!

Thanks for testing Lazy Sorting!
I'm puzzled of your results. It might be that Rust has very fast sort. Maybe your Lazy sorting algo wasn't correct. My pseudo-code was incorrect in the 1st version. I fixed it. Nothing wrong sorting all. Lazy sorting add just overhead when called many times

Remember Lazy sorting is just a speedup. It doesn't "smarten" the engine anyway.
Anyway I ran tests LazySort vs std::sort vs SortAll. In this order. LazySort was the fastest. Like I claimed in the paper.

NPS:
> bench inf 10000

Code: Select all

LazySort: 1155482
std::sort: 1016291
SelectionSort: 985227

With source code.

Code: Select all

# Benchmarks

## Lazy sorting

```
void SortOneMoveOnly(const int ply, const int nth, const int total_moves) {
  auto score = g_boards[ply][nth].score;
  for (auto i = nth + 1; i < total_moves; ++i)
    if (g_boards[ply][i].score > score) {
      score = g_boards[ply][i].score;
      std::swap(g_boards[ply][nth], g_boards[ply][i]);
    }
}
```

Results:
```
Nodes:    173353532
Time(ms): 150027
NPS:      1155482

```

## Selection sort

```
void SelectionSort(const int ply, const int total_moves) {
  for (auto i = 0; i < total_moves - 1; ++i) {
    auto score = g_boards[ply][i].score;
    for (auto j = i + 1; j < total_moves; ++j)
      if (g_boards[ply][i].score > score) {
        score = g_boards[ply][i].score;
        std::swap(g_boards[ply][i], g_boards[ply][i]);
      }
  }
}
```

Results:
```
Nodes:    147793041
Time(ms): 150009
NPS:      985227
```

## C++ Sort

```
void CppSort(const int ply, const int total_moves) {
  std::sort(g_boards[ply] + 0, g_boards[ply] + total_moves, // 9 -> 0
      [](const auto &a, const auto &b) {return a.score > b.score;});
}

```

Results:
```
Nodes:    152475232
Time(ms): 150031
NPS:      1016291
```