Sorting captures

[Pablo Vazquez]

Hi, I'm currently implementing basic move sorting in my engine (only mvv/lva for captures) and I got some unexpected results so I want to know if someone had a similar experience.

In normal search, the difference between generating all moves (captures and non captures mixed) and generating first captures and then quiet moves (without sorting captures), resulted in a 66% reduction of the nodes (for me).

In quiescence search, the difference between sorting and not sorting captures resulted in a 20% reduction.

Now, with these two optimizations, the next step I did was sort captures also in normal search. But surprisingly, this resulted in less than 1% reduction.

Anybody else has experienced something like this?

[bob]

Hi, I'm currently implementing basic move sorting in my engine (only mvv/lva for captures) and I got some unexpected results so I want to know if someone had a similar experience.

In normal search, the difference between generating all moves (captures and non captures mixed) and generating first captures and then quiet moves (without sorting captures), resulted in a 66% reduction of the nodes (for me).

In quiescence search, the difference between sorting and not sorting captures resulted in a 20% reduction.

Now, with these two optimizations, the next step I did was sort captures also in normal search. But surprisingly, this resulted in less than 1% reduction.

Anybody else has experienced something like this?

either something is broken or you are not using the same definition of "nodes" as ther rest of us. Not generating non-captures until after you try captuers will not change the size of the tree being searched whatsoever. It just saves the time used to generate the non-captures that are often never even searched.

So first, look at how you define "node". Most of us consider node == one call to MakeMove().

[xsadar]

Hi, I'm currently implementing basic move sorting in my engine (only mvv/lva for captures) and I got some unexpected results so I want to know if someone had a similar experience.

In normal search, the difference between generating all moves (captures and non captures mixed) and generating first captures and then quiet moves (without sorting captures), resulted in a 66% reduction of the nodes (for me).

In quiescence search, the difference between sorting and not sorting captures resulted in a 20% reduction.

Now, with these two optimizations, the next step I did was sort captures also in normal search. But surprisingly, this resulted in less than 1% reduction.

Anybody else has experienced something like this?

either something is broken or you are not using the same definition of "nodes" as ther rest of us. Not generating non-captures until after you try captuers will not change the size of the tree being searched whatsoever. It just saves the time used to generate the non-captures that are often never even searched.

So first, look at how you define "node". Most of us consider node == one call to MakeMove().

He said he originally had captures and non-captures mixed together. Un-mixing them would of course give a very sizable reduction in nodes.

[Pablo Vazquez]

I increment the node count in each call to search and qsearch. Yes, I know that generating captures, trying them, and then generating quiet moves and trying them would give the same tree as generating first captures and then quiet moves all together and then trying all the moves. But what I meant is that first I had only one function called generate_moves() in which I just collected the moves resulting from attacks & ~my_pieces. Then I made separate functions for captures and non captures.

The only reason I have found so far is that actually I implicitly sort the moves because I first generate pawn captures, then knight... So it's kind of a LVA/random sorting.

Maybe someone has another explanation?

[bob]

Hi, I'm currently implementing basic move sorting in my engine (only mvv/lva for captures) and I got some unexpected results so I want to know if someone had a similar experience.

In normal search, the difference between generating all moves (captures and non captures mixed) and generating first captures and then quiet moves (without sorting captures), resulted in a 66% reduction of the nodes (for me).

In quiescence search, the difference between sorting and not sorting captures resulted in a 20% reduction.

Now, with these two optimizations, the next step I did was sort captures also in normal search. But surprisingly, this resulted in less than 1% reduction.

Anybody else has experienced something like this?

either something is broken or you are not using the same definition of "nodes" as ther rest of us. Not generating non-captures until after you try captuers will not change the size of the tree being searched whatsoever. It just saves the time used to generate the non-captures that are often never even searched.

So first, look at how you define "node". Most of us consider node == one call to MakeMove().

He said he originally had captures and non-captures mixed together. Un-mixing them would of course give a very sizable reduction in nodes.

I assumed that he still used the same ordering however, in that good captures (whether based on MVV/LVA or SEE) are tried first...

[bob]

I increment the node count in each call to search and qsearch. Yes, I know that generating captures, trying them, and then generating quiet moves and trying them would give the same tree as generating first captures and then quiet moves all together and then trying all the moves. But what I meant is that first I had only one function called generate_moves() in which I just collected the moves resulting from attacks & ~my_pieces. Then I made separate functions for captures and non captures.

The only reason I have found so far is that actually I implicitly sort the moves because I first generate pawn captures, then knight... So it's kind of a LVA/random sorting.

Maybe someone has another explanation?

OK, if you were searching in what is essentially random order, then moving good captures first will absolutely shrink the tree. And by far more than just 66%. Compare minimax to depth D to alpha/beta to depth D. And random move ordering is essentially minimax, while good ordering gets closer and closer to alpha/beta optimality.

[Pablo Vazquez]

I did an experiment: I took fruit 2.1 source and I removed line 311 in sort.cpp (list_sort(sort->list);) for captures. This increased the nodes by 20%, but then I noticed that fruit generates pawn captures in the last place so I moved the code to generate them first and now the increase was only 1%, like in my case.

So my question is: why does fruit and crafty generate pawn captures last?
And also, has anybody tried this also in his program?

Thanks for your answers.

[bob]

I did an experiment: I took fruit 2.1 source and I removed line 311 in sort.cpp (list_sort(sort->list);) for captures. This increased the nodes by 20%, but then I noticed that fruit generates pawn captures in the last place so I moved the code to generate them first and now the increase was only 1%, like in my case.

So my question is: why does fruit and crafty generate pawn captures last?
And also, has anybody tried this also in his program?

Thanks for your answers.

Because it doesn't matter when they are generated, it matters when they are searched. After generating all the captures, I then sort 'em using SEE values, so that I try the most profitable capture first, regardless of the order the captures were generated.

[Pablo Vazquez]

If you sort them, then the order in which are generated obviously doesn't matter but it you don't sort them and rely on the order of generation (generating from less valuable attacker to most valuable) there is almost no difference with mvv/lva. SEE is more accurate so I will end up implementing it and therefor sorting captures, anyway.

All that I tested here was in the normal search. In quiescence search, sorting captures helps, and a lot.

[plattyaj]

So my question is: why does fruit and crafty generate pawn captures last?
And also, has anybody tried this also in his program?

Thanks for your answers.

Without looking at their source I can guess the answer is because they generate all pawn moves last. And the reason for that is that they are seldom the best move. When they are the best move hopefully the move ordering based on captures, hash, history, etc. has already put them there.

I put that change in Schola a few weeks ago and it made a reasonable difference in first move cutoff.

Andy.