Lazy sorting algorithm - Sorting on steroids

[tcusr]

to make the code even shorter use std::max_element

[dangi12012]

To be honest if the movegenerator itself has heuristics baked in (which i have seen used before) there is really no need to sort the resulting list. If direct recursion is used there is no list at all.

[Algorhythm]

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
```

Here's my sorting code if you want to give it a check:

Code: Select all

pub struct MoveSorter {
    moves: Vec<Move>,
    sorted_index: usize,
}

impl Iterator for MoveSorter {
    type Item = Move;
    fn next(&mut self) -> Option<Self::Item> {
        if self.sorted_index == self.moves.len() {
            return None;
        }
        for i in (self.sorted_index + 1)..self.moves.len() {
            if self.moves[i].sort_score > self.moves[self.sorted_index].sort_score {
                self.moves.swap(i, self.sorted_index);
            }
        }

        self.sorted_index += 1;
        Some(self.moves[self.sorted_index - 1])
    }
}

The select_nth_unstable_by function replaces the for loop with:

Code: Select all

self.moves[self.sorted_index..].select_nth_unstable_by(0, |a, b| b.sort_score.cmp(&a.sort_score));

[xr_a_y]

Maybe it would make sense to sort move by move at expected cutnode and sort all moves at allnode.
I did try that in Minic some weeks ago, without great success ...

[mvanthoor]

Here's my sorting code if you want to give it a check:
...

You already have your moves in a Vec<Move>, which already has an iterator implementation. Because you wrap this Vec<Move> into a MoveSorter with its own sorted_index, you'll have to implement an iterator specifically for this new struct. You could have just created a function and use the Vec's own iterator. Compare with my move_picker() function():

Code: Select all

    pub fn pick_move(ml: &mut MoveList, current_index: u8) {
        let mut best_index = current_index;

        for i in (current_index + 1)..ml.len() {
            if ml.get_move(i).get_sort_score() > ml.get_move(best_index).get_sort_score() {
                best_index = i;
            }
        }

        ml.swap(current_index as usize, best_index as usize);
    }

It takes a reference to the move list, and the index it is currently at. Then it runs from current_index+1 to the end of the list, and swaps the highest sorted move into current_index. That's basically it.

PS: My MoveList is an array of length 255, backed by an index counter. These are wrapped in a struct. I have tried implementing an iterator for this struct so I could iterate over the for list by just doing "for mv in move_list". It works, but because the Iterator requires the result to be wrapped in "Some" if it exists and the caller then needs to unwrap it with "if let Some()...", the iterator turns out to be about 10% slower than just looping with a standard for-loop.

I also tried to implement "Display" for my principal variation. Because this is a Vec<Move>, I had to wrap it in a struct so I could implement Display on that struct. This necessitated me to expose part of the functionality of the Vec (including the iterator), just as you would do with a compound object in an object-oriented language. Because updating the principal variation is in the hot path of the code (in the alpha-beta function), this compound struct turned out to be 10% slower than the normal Vec<Move>.

Because Vec<Move> is already wrapped in a struct called SearchInfo (which obviously holds all the information about the current search), I just implemented search_info.pv_to_string().

This is also the reason why I have a "Nothing" variant in most of my enums, so I can initialize with "let X = Stuff::Nothing", and later check with "if X != Stuff::Nothing". I know; the proper way would be to use Some, None, and and an "if let" and certainly not a dummy value such as Nothing, because that implementation looks an eerie lot like NULL. But... yeah... the proper way is just _slower_ because "if let" is slower than "if".

Doing things 100% the proper and pretty Rust way sometimes turns out to be slower than doing it the old-fashioned way. You may want to keep that in mind, because 10% here, 5% there, and another 7% somewhere else stacks up pretty quickly. I try to follow best practices as much as possible, but not if costs me 10% speed each time I do so. (And I'm certainly not going to re-implement features a wrapped type already has.)

[pedrojdm2021]

Guys, now that we're talking about sorting, i was trying an idea in my case to prevent so many calls of "GetMoveScroe" that according to visual studio, that function seems to be generating a hugue bottleneck in the performance of my engine due to so many calls to it.

My idea was to "Cache" the scores in another array of the same size as the move_list array, this is just After one call GenerateMoves:

Code: Select all

sbyte target_index = board.GenerateMoves(in move_list[ply], false);
ScoreMoves(target_index);
			
for (sbyte moveIndex = 0; moveIndex <= target_index; moveIndex++)
{
	OrderMoves(moveIndex, target_index);

The function itself:

Code: Select all

private static void ScoreMoves(sbyte _targetIndex)
{
	for (sbyte moveIndex = 0; moveIndex <= _targetIndex; moveIndex++)
	{
		move_scores[ply][moveIndex] = GuessMoveScore(move_list[ply][moveIndex]);
	}
}

The results in terms of speed are hugue, before cache the move scores i was getting about 800.000 NPS. Now I'm getting 1.400.000 NPS

But there's a problem:
I'm now getting different node count during the search, and my engine is weak now, now it lost against the same engine were it was winning always.

This is my OrderMoves function:

Code: Select all

private static void OrderMoves(sbyte _currentIndex, sbyte _targetIndex)
{
	sbyte best_index = _currentIndex;
	int best_score = 0;
	int score;

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

	if (best_index != _currentIndex)
	{
		// swap moves
		(move_list[ply][_currentIndex], move_list[ply][best_index]) =
			(move_list[ply][best_index], move_list[ply][_currentIndex]);

		// swap scores
		(move_scores[ply][_currentIndex], move_scores[ply][best_index]) =
			(move_scores[ply][best_index], move_scores[ply][_currentIndex]);
	}
}

Anyone here have been trying to do something similar? maybe i'm missing something?

my move list and move scores are indexed by ply and move_index, to prevent collisions with parent nodes in the search tree.

[Pio]

Guys, now that we're talking about sorting, i was trying an idea in my case to prevent so many calls of "GetMoveScroe" that according to visual studio, that function seems to be generating a hugue bottleneck in the performance of my engine due to so many calls to it.

My idea was to "Cache" the scores in another array of the same size as the move_list array, this is just After one call GenerateMoves:

Code: Select all

sbyte target_index = board.GenerateMoves(in move_list[ply], false);
ScoreMoves(target_index);
			
for (sbyte moveIndex = 0; moveIndex <= target_index; moveIndex++)
{
	OrderMoves(moveIndex, target_index);

The function itself:

Code: Select all

private static void ScoreMoves(sbyte _targetIndex)
{
	for (sbyte moveIndex = 0; moveIndex <= _targetIndex; moveIndex++)
	{
		move_scores[ply][moveIndex] = GuessMoveScore(move_list[ply][moveIndex]);
	}
}

The results in terms of speed are hugue, before cache the move scores i was getting about 800.000 NPS. Now I'm getting 1.400.000 NPS

But there's a problem:
I'm now getting different node count during the search, and my engine is weak now, now it lost against the same engine were it was winning always.

This is my OrderMoves function:

Code: Select all

private static void OrderMoves(sbyte _currentIndex, sbyte _targetIndex)
{
	sbyte best_index = _currentIndex;
	int best_score = 0;
	int score;

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

	if (best_index != _currentIndex)
	{
		// swap moves
		(move_list[ply][_currentIndex], move_list[ply][best_index]) =
			(move_list[ply][best_index], move_list[ply][_currentIndex]);

		// swap scores
		(move_scores[ply][_currentIndex], move_scores[ply][best_index]) =
			(move_scores[ply][best_index], move_scores[ply][_currentIndex]);
	}
}

Anyone here have been trying to do something similar? maybe i'm missing something?

my move list and move scores are indexed by ply and move_index, to prevent collisions with parent nodes in the search tree.

I see two things that look a little bit suspicious. First it looks like you are not swapping anything in the code below

Code: Select all

		// swap moves
		(move_list[ply][_currentIndex], move_list[ply][best_index]) =
			(move_list[ply][best_index], move_list[ply][_currentIndex]);

		// swap scores
		(move_scores[ply][_currentIndex], move_scores[ply][best_index]) =
			(move_scores[ply][best_index], move_scores[ply][_currentIndex]);

The other problem might be that you might use another branch’s list with the same ply number while sorting. Why not make the move list local. Then you don’t have to think about the ply.

Good luck!

[tcusr]

that's how you swap variables in python
a, b = b, a
maybe it's the same in whatever language he's using

[pedrojdm2021]

Guys, now that we're talking about sorting, i was trying an idea in my case to prevent so many calls of "GetMoveScroe" that according to visual studio, that function seems to be generating a hugue bottleneck in the performance of my engine due to so many calls to it.

My idea was to "Cache" the scores in another array of the same size as the move_list array, this is just After one call GenerateMoves:

Code: Select all

sbyte target_index = board.GenerateMoves(in move_list[ply], false);
ScoreMoves(target_index);
			
for (sbyte moveIndex = 0; moveIndex <= target_index; moveIndex++)
{
	OrderMoves(moveIndex, target_index);

The function itself:

Code: Select all

private static void ScoreMoves(sbyte _targetIndex)
{
	for (sbyte moveIndex = 0; moveIndex <= _targetIndex; moveIndex++)
	{
		move_scores[ply][moveIndex] = GuessMoveScore(move_list[ply][moveIndex]);
	}
}

The results in terms of speed are hugue, before cache the move scores i was getting about 800.000 NPS. Now I'm getting 1.400.000 NPS

But there's a problem:
I'm now getting different node count during the search, and my engine is weak now, now it lost against the same engine were it was winning always.

This is my OrderMoves function:

Code: Select all

private static void OrderMoves(sbyte _currentIndex, sbyte _targetIndex)
{
	sbyte best_index = _currentIndex;
	int best_score = 0;
	int score;

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

	if (best_index != _currentIndex)
	{
		// swap moves
		(move_list[ply][_currentIndex], move_list[ply][best_index]) =
			(move_list[ply][best_index], move_list[ply][_currentIndex]);

		// swap scores
		(move_scores[ply][_currentIndex], move_scores[ply][best_index]) =
			(move_scores[ply][best_index], move_scores[ply][_currentIndex]);
	}
}

Anyone here have been trying to do something similar? maybe i'm missing something?

my move list and move scores are indexed by ply and move_index, to prevent collisions with parent nodes in the search tree.

I see two things that look a little bit suspicious. First it looks like you are not swapping anything in the code below

Code: Select all

		// swap moves
		(move_list[ply][_currentIndex], move_list[ply][best_index]) =
			(move_list[ply][best_index], move_list[ply][_currentIndex]);

		// swap scores
		(move_scores[ply][_currentIndex], move_scores[ply][best_index]) =
			(move_scores[ply][best_index], move_scores[ply][_currentIndex]);

The other problem might be that you might use another branch’s list with the same ply number while sorting. Why not make the move list local. Then you don’t have to think about the ply.

Good luck!

Thank you for your reply! I did some debugging today and i was able to fix the bug

First of all, i changed the OrderMoves function from the old one to this one:

Code: Select all

private static void OrderMoves(sbyte _currentIndex, sbyte _targetIndex)
{
	for (sbyte moveIndex = _currentIndex; moveIndex <= _targetIndex; ++moveIndex)
	{
		if (move_scores[ply][moveIndex] > move_scores[ply][_currentIndex])
		{
			// swap scores
			(move_scores[ply][_currentIndex],move_scores[ply][moveIndex]) = (move_scores[ply][moveIndex],move_scores[ply][_currentIndex]);
			// swap moves
			(move_list[ply][_currentIndex],move_list[ply][moveIndex]) = (move_list[ply][moveIndex],move_list[ply][_currentIndex]);
		}
	}
}

Then i found that i was calling the ScoreMoves() function BEFORE i call the enable_pv_scoring() function that i'm using to search PV moves first.
And it should be called AFTER it. So i changed that.

and finally i found that i had a wrong condition in the futility pruning, i had it applying for depth <= 2, when it should be depth == 2.

I changed that stuff, and i tested it again, and it won!

[pgn]
[Event "Computer chess game"]
[Site "DESKTOP-LTHGU0S"]
[Date "2022.02.08"]
[Round "?"]
[White "ChessPedro"]
[Black "Vice1.1"]
[Result "1-0"]
[BlackElo "2000"]
[ECO "D02"]
[Opening "Queen's Pawn"]
[Time "19:35:04"]
[Variation "London"]
[WhiteElo "2000"]
[Termination "normal"]
[PlyCount "137"]
[WhiteType "program"]
[BlackType "program"]

1. Nf3 {(Ng1-f3 Nb8-c6 d2-d4 d7-d5 e2-e3 Bc8-f5 Bf1-b5 Ng8-f6) +0.15/8 0}
d5 {(d7d5 d2d4 c8f5 c1d2 g8f6 e2e3 b8c6 f1d3) -0.15/8 0} 2. d4 {(d2-d4
Bc8-f5 Bc1-f4 Nb8-c6 e2-e3 e7-e6 Bf1-d3 Bf8-b4+) +0.09/8 0} Nf6 {(g8f6 e2e3
c8g4 f1d3 b8c6 h2h3 g4e6 e1g1) -0.15/8 1} 3. Bf4 {(Bc1-f4 Bc8-f5 e2-e3
e7-e6 Nb1-c3 Bf8-d6 Bf1-d3 Bd6xf4) +0.16/8 0} e6 {(e7e6 e2e3 f8b4 c2c3 b4d6
f1d3 e8g8 e1g1) -0.05/8 1} 4. e3 {(e2-e3 Bf8-d6 Bf4xd6 c7xd6 Bf1-d3 Nb8-c6
Nb1-c3 e6-e5) +0.39/8 0} Bb4+ {(f8b4 c2c3 b4d6 f4d6 c7d6 f1b5 c8d7 b1a3)
-0.05/8 2} 5. c3 {(c2-c3 Bb4-d6 Bf4xd6 Qd8xd6 Bf1-d3 Nb8-c6 Nb1-d2 Bc8-d7
Ra1-c1) +0.61/8 0} Be7 {(b4e7 f3e5 e8g8 f1d3 e7d6 e1g1 b8d7 b1d2) -0.13/8
0} 6. Bd3 {(Bf1-d3 Nb8-c6 O-O O-O Nb1-d2 Bc8-d7 Ra1-c1 Ra8-c8) +0.64/8 0}
Nh5 {(f6h5 f4e5 b8c6 e1g1 f7f6 e5g3) -0.05/8 0} 7. Be5 {(Bf4-e5 Nb8-c6 O-O
O-O Nb1-d2 Nc6xe5 Nf3xe5 Nh5-f6) +0.56/8 0} Nc6 {(b8c6 f3d2 h5f6 e5f6 e7f6
d1c2 h7h6 e1g1) 0.00/8 1} 8. O-O {(O-O O-O Nb1-d2 Bc8-d7 Ra1-c1 Nc6xe5
Nf3xe5 Nh5-f6) +0.44/8 0} O-O {(e8g8 f3d2 g7g6 c3c4 f7f6 e5g3 c6b4 d2f3)
+0.10/8 0} 9. Nbd2 {(Nb1-d2 Bc8-d7 Qd1-b3 b7-b6 Ra1-d1 Nc6xe5 Nf3xe5
Ra8-c8) +0.53/8 0} f6 {(f7f6 e5g3 h5g3 f2g3 c8d7 d1b3 c6a5 b3c2) +0.15/8 0}
10. Bg3 {(Be5-g3 f6-f5 Qd1-c2 Nh5xg3 h2xg3 Bc8-d7 Ra1-d1 Ra8-c8) +0.67/8 0}
Nxg3 {(h5g3 f2g3 e6e5 d3b5 e5e4 f3h4 c8d7 h4f5) +0.30/8 0} 11. hxg3 {(h2xg3
e6-e5 d4xe5 Nc6xe5 Nf3xe5 f6xe5 Qd1-h5 e5-e4) +0.26/8 0} e5 {(e6e5 e3e4
c8e6 d1c2 e5d4 c3d4 d5e4 d3e4) +0.32/8 0} 12. e4 {(e3-e4 Bc8-e6 Rf1-e1
e5xd4 c3xd4 d5xe4 Re1xe4 Nc6-b4) +0.44/8 0} exd4 {(e5d4 e4d5 c6e5 d1b3 d8d6
c3d4 e5d3 b3d3) +0.18/8 0} 13. exd5 {(e4xd5 d4xc3 b2xc3 Rf8-f7 Bd3-c4
Nc6-e5 Rf1-e1 Bc8-g4) +0.59/8 0} dxc3 {(d4c3 d5c6 d8d3 d1b3 g8h8 a1e1 e7c5
c6b7) +0.15/8 0} 14. Qb3 {(Qd1-b3 Kg8-h8 b2xc3 Nc6-a5 Qb3-c2 Qd8xd5 Ra1-d1
Bc8-e6) +0.43/8 0} Kh8 {(g8h8 b2c3 c6a5 b3b5 c7c6 d5c6 a5c6 a1e1) +0.27/8
0} 15. bxc3 {(b2xc3 Nc6-a5 Qb3-c2 Qd8xd5 Bd3xh7 f6-f5 Bh7-g6 Kh8-g8)
+0.68/8 0} Na5 {(c6a5 b3b5 c7c6 d5c6 a5c6 f1e1 f8e8 a1d1) +0.27/8 0} 16.
Qc2 {(Qb3-c2 Qd8xd5 Bd3xh7 f6-f5 Bh7-g6 Bc8-e6 Ra1-e1 Ra8-d8) +0.71/8 0}
Qxd5 {(d8d5 d3h7 f6f5 a1e1 e7f6 h7g6 c8e6 f3d4) +0.50/8 0} 17. Bxh7
{(Bd3xh7 f6-f5 Ra1-e1 Na5-c6 Bh7-g6 Qd5-d6 Nf3-d4 Qd6xg6) +0.81/8 0} f5
{(f6f5 a1e1 a5c6 h7g6 c8d7) +0.52/8 1} 18. Bg6 {(Bh7-g6 Na5-c6 Ra1-e1
Qd5-d6 Nf3-d4 Qd6xg6 Nd4xc6 Be7-c5) +0.70/8 0} Qd6 {(d5d6 a1e1 a5c6 f3d4
c6d4 c3d4 e7g5 f2f4) +1.27/8 1} 19. Rae1 {(Ra1-e1 Na5-c6 Bg6-h5 g7-g6
Re1xe7 Nc6xe7 Nd2-c4 Qd6-f6) -0.25/8 0} Nc6 {(a5c6 f3d4 c6d4 c3d4 e7g5 f2f4
d6d4 f1f2) +1.17/8 0} 20. Nd4 {(Nf3-d4 Nc6xd4 c3xd4 Be7-g5 f2-f4 Bg5-f6
Nd2-b3 Bf6xd4+) -0.78/8 0} Bd8 {(e7d8 d4c6 d6c6 g6h5 d8f6 c3c4 c8e6 f2f4)
+0.45/8 0} 21. Nxc6 {(Nd4xc6 Qd6xc6 Bg6-h5 Bd8-f6 c3-c4 Bc8-e6 Bh5-f3
Qc6-b6) +0.71/8 0} Qxc6 {(d6c6 g6h5 c6h6 h5f3 d8g5 d2b3 f8d8 b3d4) +0.35/8
0} 22. Bh5 {(Bg6-h5 Bd8-f6 c3-c4 Rf8-d8 Bh5-f7 b7-b5 c4-c5 Rd8xd2) +0.59/8
0} Bf6 {(d8f6 e1e3 f8d8 h5f3 c6a6 f3e2 a6d6 f1d1) +0.35/8 0} 23. c4 {(c3-c4
Rf8-d8 Bh5-f3 Qc6-d6 Nd2-b3 c7-c6 Re1-d1 Qd6-e7) +0.57/8 0} Bd7 {(c8d7 h5f3
c6a6 e1b1 c7c6 c2b3 a8d8 b3b7) +0.40/8 0} 24. Bf3 {(Bh5-f3 Qc6-a6 Qc2-b1
c7-c6 c4-c5 Ra8-d8 Qb1-b3 Rf8-e8) +0.18/8 0} Qa6 {(c6a6 c2b3 c7c6 e1b1 a8b8
f1e1 f8d8 b1d1) +0.37/8 0} 25. Nb3 {(Nd2-b3 Bd7-e6 Re1-c1 Be6xc4 Qc2xc4
Qa6xa2 Qc4-b4 Ra8-c8) +0.67/8 0} Qb6 {(a6b6 c4c5 b6b5) +0.35/8 0} 26. c5
{(c4-c5 Qb6-a6 Bf3-e2 Qa6-a4 Be2-c4 b7-b6 Bc4-d5 b6xc5) +0.59/8 0} Qb5
{(b6b5 c5c6 d7c6 f3c6 b7c6 e1e6 a8d8 c2c6) +0.20/8 0} 27. Bd5 {(Bf3-d5
Ra8-d8 Qc2-d1 g7-g6 Qd1-d2 Kh8-g7 Qd2-f4 c7-c6) +0.47/8 0} Rad8 {(a8d8 d5e6
d7e6 e1e6 d8d3 f1e1) +0.30/8 1} 28. Bc4 {(Bd5-c4 Qb5-a4 Qc2-e2 g7-g6 Nb3-d2
Rf8-e8 Qe2-f3 Qa4-c2) +0.18/8 0} Qa4 {(b5a4 c4d3 g7g6) +0.45/8 0} 29. Bd3
{(Bc4-d3 Rf8-e8 Re1xe8+ Rd8xe8 Rf1-d1 Qa4-g4 Bd3-c4 Bd7-c6 Bc4-f7) -0.14/8
0} Qg4 {(a4g4 b3a5 g4b4 a5b3 b4c3 c2b1 g7g6 e1e3) +0.52/8 1} 30. Be2
{(Bd3-e2 Qg4-b4 Be2-d3 b7-b6 c5-c6 Bd7xc6 Qc2xc6 Rd8xd3) -0.19/8 0} Qb4
{(g4b4 e2d3 b4c3 c2b1 g7g6 e1e3 f8e8 f1e1) +0.52/8 0} 31. Rd1 {(Re1-d1
Qb4-c3 Qc2xc3 Bf6xc3 Be2-c4 f5-f4 g3xf4 Rf8xf4) -0.26/8 1} Rfe8 {(f8e8 e2d3
b4g4 b3a5 d7a4 a5b3 e8e5 f1e1) +0.55/8 3} 32. Bh5 {(Be2-h5 Re8-e7 Bh5-f3
c7-c6 Rd1-d6 Bf6-e5 Rd6-g6 Kh8-g8) -0.06/8 0} Re5 {(e8e5 f2f4 e5e7 g3g4
b4e4 c2d2 e4e2) +0.70/8 1} 33. Bf7 {(Bh5-f7 Qb4-e4 Qc2-c1 Bd7-c6 Rd1xd8+
Bf6xd8 f2-f3 Qe4-e3+ Qc1xe3 Re5xe3) -0.12/8 0} Bb5 {(d7b5 d1d8 f6d8 c2d1
d8g5 f2f4 b5e2) +0.65/8 2} 34. Rxd8+ {(Rd1xd8+ Bf6xd8 Qc2-d1 Bd8-g5 f2-f4
Re5xc5 f4xg5 Bb5xf1 Nb3xc5) +0.19/8 0} Bxd8 {(f6d8 c2d1 d8g5 f2f4 b5f1 f4e5
f1b5 d1h5) -0.70/8 0} 35. Qd1 {(Qc2-d1 Bd8-g5 f2-f4 Re5xc5 f4xg5 Bb5xf1
Nb3xc5) +0.19/7 0} Bg5 {(d8g5 f2f4 b5f1 f4e5 f1b5 d1h5 g5h6 h5f5) -0.55/8
0} 36. f4 {(f2-f4 Bb5xf1 f4xe5 Bf1-a6 Qd1-h5+ Bg5-h6 e5-e6 Qb4-e1+ Kg1-h2
Ba6-d3) +0.66/8 0} Qe4 {(b4e4 f4g5 e4e3 g1h2 e3g5 f1h1 g5e3 d1d8) -2.20/8
1} 37. fxg5 {(f4xg5 Qe4-e3+ Rf1-f2 Qe3xg5 Rf2-f4 Re5-e4 Nb3-d4 Re4xf4
g3xf4) +2.48/8 0} Qe3+ {(e4e3 g1h2 e3g5 f1h1 g5e3 d1d8 b5e8 f7e8) -2.20/8
0} 38. Rf2 {(Rf1-f2 Qe3-e1+ Qd1xe1 Re5xe1+ Kg1-h2 b7-b6 Rf2xf5 b6xc5 Rf5xc5
Re1-e7 g5-g6) +2.64/8 0} Qxg5 {(e3g5 f2f4 e5e4 f7d5 e4f4 g3f4 g5f4 d5b7)
-2.10/8 0} 39. Rf4 {(Rf2-f4 Re5-e4 Nb3-d4 Bb5-d7 Qd1-f3 a7-a5 Rf4-h4+
Re4xh4 g3xh4) +2.68/8 0} Re4 {(e5e4 f7d5 e4f4 g3f4 g5h4 b3d4 c7c6 d4f5)
-2.30/8 0} 40. Nd4 {(Nb3-d4 Bb5-d7 Qd1-f3 g7-g6 Bf7-d5 Re4-e5 Rf4-h4+
Kh8-g7 a2-a3) +2.72/8 0} Bd7 {(b5d7 f7d5 e4f4 g3f4 g5h4 d5b7 h4f4 b7d5)
-2.50/8 0} 41. Qf3 {(Qd1-f3 c7-c6 a2-a4 b7-b6 c5xb6 a7xb6 Rf4xe4 f5xe4)
+2.73/8 0} c6 {(c7c6 f4e4 f5e4 f3e4 g5g3 d4f3 d7g4 f3e5) -2.20/8 0} 42. a4
{(a2-a4 b7-b6 c5xb6 a7xb6 Rf4xe4 Qg5-c1+ Kg1-f2 f5xe4 Qf3xe4) +2.48/8 0} a6
{(a7a6 f4e4 f5e4) -2.15/8 0} 43. Kf2 {(Kg1-f2 a6-a5 Nd4-b3 Re4xf4 g3xf4
Qg5-h4+ Qf3-g3 Qh4-f6 Bf7-c4) +2.85/8 0} Rxf4 {(e4f4 f3f4 g5f4 g3f4 h8h7
a4a5 h7h6 f2f3) -2.40/8 0} 44. gxf4 {(g3xf4 Qg5-h4+ Qf3-g3 Qh4xg3+ Kf2xg3
Kh8-h7 a4-a5 g7-g6 Bf7-c4 Kh7-g7) +2.96/8 0} Qh6 {(g5h6 f3h5 h6h5 f7h5 h8h7
f2e3 h7h6 h5e2) -2.35/8 0} 45. Qg3 {(Qf3-g3 Kh8-h7 a4-a5 g7-g6 Nd4-e6
Bd7xe6 Bf7xe6 Qh6-h1) +3.09/8 0} Kh7 {(h8h7 d4f3 a6a5 f3g5 h7h8 f7c4 h6h1
g3h3) -2.65/8 0} 46. Nf3 {(Nd4-f3 a6-a5 Nf3-g5+ Kh7-h8 Kf2-g1 Qh6-f6 Qg3-d3
Qf6-a1+ Kg1-h2 Bd7-c8) +3.32/8 0} Bc8 {(d7c8 f3h4 c8e6 g3g6 h6g6 f7g6 h7h6
g6f5) -3.30/8 0} 47. Ng5+ {(Nf3-g5+ Kh7-h8 Kf2-g1 Qh6-f6 Qg3-h3+ Qf6-h6
Qh3-d3 Qh6-f6 a4-a5 g7-g6) +3.57/8 0} Kh8 {(h7h8 g3e3 c8e6 f7e6 h6h4 e3g3
h4h1 g5f7) -6.75/8 0} 48. Bc4 {(Bf7-c4 Qh6-h1 Ng5-f7+ Kh8-h7 Nf7-d6 Bc8-d7
Nd6xb7 Qh1-d1 a4-a5) +3.78/8 0} Qh5 {(h6h5 g5f7 h8h7 f7d6 c8d7 d6b7 h5d1
g3h3) -3.55/8 0} 49. Nf7+ {(Ng5-f7+ Kh8-h7 Nf7-d6 Bc8-d7 Bc4-e2 Qh5-h1
Nd6xb7 Bd7-e6 Be2xa6) +3.72/8 0} Kh7 {(h8h7 f7d6 c8d7 a4a5 h5h6 d6b7 d7e6
c4a6) -4.00/8 0} 50. Nd6 {(Nf7-d6 Bc8-d7 Bc4-e2 Qh5-h1 Nd6xb7 Bd7-e6 a4-a5
Be6-d5) +4.00/8 0} Bd7 {(c8d7 a4a5 h5h6 d6b7 h6h1 c4a6 h7g8 b7d6) -4.25/8
0} 51. Be2 {(Bc4-e2 Qh5-h1 Nd6xb7 Qh1-a1 Qg3-d3 Qa1xa4 Qd3xd7 Qa4xf4+)
+3.99/8 0} Qh6 {(h5h6 d6b7 h6f6 g3d3 f6e7 f2f1 d7c8 b7d6) -3.95/8 0} 52.
Nxb7 {(Nd6xb7 Qh6-f6 a4-a5 Qf6-d4+ Qg3-e3 Qd4-b2 Nb7-d6 Qb2-b4 Be2xa6)
+4.16/8 0} Qf6 {(h6f6 g3d3 d7e6 a4a5 e6d5 d3h3 h7g8 e2a6) -4.00/8 0} 53. a5
{(a4-a5 Qf6-d4+ Qg3-e3 Qd4-b4 Be2xa6 Bd7-c8 Qe3-e7 Qb4xf4+ Kf2-g1 Kh7-g6)
+3.79/8 0} Qb2 {(f6b2 g3h4 h7g6 b7d6 b2d4 f2f1 d4a1 h4e1) -4.05/8 0} 54.
Qh4+ {(Qg3-h4+ Kh7-g6 Qh4-h5+ Kg6-f6 Qh5-g5+ Kf6-e6 Qg5-g6+ Qb2-f6 Qg6xf6+
Ke6xf6 Be2xa6 Bd7-e6 Nb7-d6) +4.64/8 0} Kg6 {(h7g6 h4h5 g6f6 h5g5 f6e6 b7d8
e6d5 g5e7) -4.95/8 0} 55. Qh5+ {(Qh4-h5+ Kg6-f6 Qh5-g5+ Kf6-e6 Qg5-g6+
Qb2-f6 Qg6xf6+ Ke6xf6 Be2xa6 Bd7-e6 Nb7-d6 Be6-d5) +4.65/8 0} Kf6 {(g6f6
h5g5 f6f7 b7d6 f7e6 d6f5 d7e8 g5g7) -6.45/8 0} 56. Qg5+ {(Qh5-g5+ Kf6-e6
Qg5-g6+ Qb2-f6 Qg6xf6+ Ke6xf6 Be2xa6 Bd7-e6 Nb7-d6 Be6-d5 Ba6-c4) +4.85/8
0} Ke6 {(f6e6 b7d8 e6d5 g5e7 b2d4 f2g3 d7c8 e7d6) -6.60/8 0} 57. Qg6+
{(Qg5-g6+ Qb2-f6 Qg6xf6+ Ke6xf6 Nb7-d6 Bd7-e6 Be2xa6 Be6-d5 Ba6-c4 Bd5xc4)
+4.90/8 0} Qf6 {(b2f6 g6f6 e6f6 b7d6 d7e6 e2a6 g7g5 f4g5) -4.70/8 0} 58.
Qxf6+ {(Qg6xf6+ Ke6xf6 Nb7-d6 Bd7-e6 Be2xa6 g7-g5 f4xg5+ Kf6xg5 Kf2-g3
f5-f4+) +4.84/8 0} Kxf6 {(e6f6 b7d6 f6e6 e2c4 e6f6 c4a6 d7e6 a6d3) -4.80/8
0} 59. Nd6 {(Nb7-d6 Kf6-e6 Be2-c4+ Ke6-f6 Bc4xa6 Bd7-e6 Ba6-d3 g7-g5
f4xg5+) +5.14/8 0} g5 {(g7g5 f4g5 f6g5 e2a6 d7e6 a6d3 g5f6 a5a6) -4.80/8 0}
60. fxg5+ {(f4xg5+ Kf6xg5 Be2xa6 Kg5-f6 Ba6-c4 Kf6-e5 a5-a6 Ke5-d4 a6-a7)
+5.60/8 0} Kxg5 {(f6g5 e2a6 g5f4 a6d3 f4e5 a5a6 e5d4 d3f5) -4.95/8 0} 61.
Bxa6 {(Be2xa6 Kg5-f6 Ba6-e2 Kf6-e5 a5-a6 Ke5-d4 Nd6-b7 Bd7-e6) +5.68/8 0}
f4 {(f5f4 a6c4 f4f3 g2f3 g5f6 a5a6 f6e5 a6a7) -6.35/8 0} 62. Bc4 {(Ba6-c4
f4-f3 g2xf3 Kg5-f6 a5-a6 Bd7-e6 a6-a7 Be6xc4) +8.33/8 0} Bh3 {(d7h3 g2h3
g5h4 d6f5 h4h3 f2f3 h3h2 a5a6) -8.65/8 0} 63. gxh3 {(g2xh3 f4-f3 Kf2xf3
Kg5-h5 a5-a6 Kh5-h4 a6-a7 Kh4xh3) +10.75/8 0} f3 {(f4f3 f2f3 g5f6 d6f7 f6f5
f7d8 f5e5 d8c6) -10.20/8 0} 64. a6 {(a5-a6 Kg5-h4 a6-a7 Kh4xh3 Kf2xf3
Kh3-h2 a7-a8Q) +16.57/7 0} Kf6 {(g5f6 a6a7 f6g5 a7a8q g5h4 a8c6 h4h3 f2f3)
-19.05/8 0} 65. a7 {(a6-a7 Kf6-g6 Kf2xf3 Kg6-g5 a7-a8Q Kg5-h4 Qa8xc6)
+18.31/7 0} Ke5 {(f6e5 a7a8q e5d4 a8c6 d4c3 c6f3 c3c2 c5c6) -20.35/8 0} 66.
a8=Q {(a7-a8Q Ke5-f6 Qa8xc6 Kf6-e7 Qc6xf3 Ke7-d7 h3-h4) +19.67/7 0} Kd4
{(e5d4 a8a3 d4e5 a3a1 e5f4) -M3/8 1} 67. Qa3 {(Qa8-a3 Kd4-e5 Qa3xf3 Ke5-d4
Qf3-e3+) +M500/8 0} Ke5 {(d4e5 a3a1 e5f4 a1f6) -M2/8 1} 68. Qxf3 {(Qa3xf3)
+M500/8 0} Kd4 {(e5d4 f3e3) -M1/8 1} 69. Qe3# {(Qf3-e3+) +M500/8 0} 1-0
[/pgn]

A game of my Engine (white) VS VICE 1.1 (black)

[eligolf]

Back to the original post and "paper". In the results I see that the node count went up after using lazy sorting, how is this possible? I am asking because I saw similar results when I tried it myself. Since you score the moves the same and then instead of sorting all moves you sort them one by one, they should still be tried in the same order no matter what? Which in turn should give the same node count as scoring and then sorting all moves before trying them?