Selective techniques

[metax]

Hello,

since about 4 months, I am developing my engine ChessMind now. I implemented null move with R=3 (without verification), transposition tables and Futility pruning. The problem is the following:
I currently search at least 250 kilonodes per second, in a normal middlegame position 300 on average. That is not a very good value, but still OK in my opinion. My problem is the tree explosion. Other programs easily reach search depths of at least 14-15 in a few seconds, ChessMind reaches ply 7-8 in that time. This is because I need about 1.000.000 nodes to reach ply 8 or 9 in most middlegame positions, whereas other engines need 1.000.000 nodes to reach ply 14. My conclusion is that I have to improve my selective techniques, but how? I experimented a bit with some reductions if one side has lost too much material, but that either gave me not much performance or had very high tactical risks. For example, I found out that to reduce the tactical risk, I should not reduce captures, check or transposition table moves. I only allowed one reduction per branch and even if I reduced two plies if there was a very high material imbalance, that gave me not much and was tactically risky anyway.

What I do in the search is: At the root, I search the first move with an aspiration window of 200 centipawns around alpha. If it fails high or low, I open the window completely and search the first move again. After having searched the first move, I close the window. When a fail-high occurs, I search the move again with an open window. In the tree, I simply do "normal" alpha-beta, which means I take the given window.
I'm not sure if this is optimal because quite often, the engine isn't sure which one of two moves is better, and then fail-highs at the root occur which seems to take some performance.
As move ordering, I take the transposition table move (if available), then the two killer moves and MVV-LVA. I have no history heuristic or anything else than killer moves to order the non-captures because many people say that at today's search depths, history is only a random noise (would it be an idea to only count history moves until a given ply?).

I'm not sure about the different search algorithms, but I think PVS is to do at every node what I do only only at the root (correct me if I am wrong). I have heard that PVS is faster than alpha-beta if over about 90% of first moves in the tree fail high and slower at less than 90%. As my move ordering success is about 80-85% in middlegame, I haven't tried PVS yet.

Any ideas how I could reduce the number of nodes that have to be searched without dramatically increasing tactical risks?

[Edsel Apostol]

Your move ordering is not good.

Try this:

transposition table move
good captures including queen promotion (SEE >= 0) ordered by MVV\LVA
killer moves (you must not store captures here)
all moves that are not capture and promotion
bad captures including underpromotions (SEE < 0)

You can also prune captures in the quiescent search with SEE < 0.

Then you can try LMR but it needs a lot of tuning and restraints.

You're not using SEE (Static Exchange Evaluation)?

[metax]

Your move ordering is not good.

Try this:

transposition table move
good captures including queen promotion (SEE >= 0) ordered by MVV\LVA
killer moves (you must not store captures here)
all moves that are not capture and promotion
bad captures including underpromotions (SEE < 0)

You can also prune captures in the quiescent search with SEE < 0.

Then you can try LMR but it needs a lot of tuning and restraints.

You're not using SEE (Static Exchange Evaluation)?

No, I am not using SEE. I am not using bitboards either and I am not detecting the hanging pieces in a position, so SEE would rather decrease performance, wouldn't it?
The proposal not to store captures in the killer slots didn't work for me: The move ordering success (from the starting position) dropped from 86% to 83%, and to reach ply 10 I needed 3.1 million nodes instead of 2.4 million, so that was rather counterproductive...

edit: Which move ordering success rates do you actually reach in your engines?

[OliverUwira]

No, I am not using SEE. I am not using bitboards either and I am not detecting the hanging pieces in a position, so SEE would rather decrease performance, wouldn't it?
The proposal not to store captures in the killer slots didn't work for me: The move ordering success (from the starting position) dropped from 86% to 83%, and to reach ply 10 I needed 3.1 million nodes instead of 2.4 million, so that was rather counterproductive...

How do you define "move ordering success"? Is this percentage of nodes where you have searched the eventual best move first?

In order to make your quiescence search more efficient, you might want to implemement a SEE and check whether the relation of reached depth and searched nodes (which is independent of speed) improves. If it does, you at least have a clue as to the culprit.

[metax]

How do you define "move ordering success"? Is this percentage of nodes where you have searched the eventual best move first?

Yes, exactly.

In order to make your quiescence search more efficient, you might want to implemement a SEE and check whether the relation of reached depth and searched nodes (which is independent of speed) improves. If it does, you at least have a clue as to the culprit.

I'll try that ans report here.

[opraus]

The reason I think your killers do better WITH captures, is because you have killers BEFORE captures. And, even without SEE, that may be wrong. [though interesting]

Try:
hash/PV
ALL captures [by MVV-LVA]
killers [no caps in here]
rest [as they are]

-David

[mcostalba]

The reason I think your killers do better WITH captures, is because you have killers BEFORE captures. And, even without SEE, that may be wrong.

Yes I agree. The capture killers improvment that you see is just an artifact due to the fact that you don't try captures before killers.

I also suggest you to remove bad captures and try them after non-capture moves. If you don't have SEE you can try a poor man see where you consider bad capture a capture of a lesser piece that is defended.

It is not 100% correct but it is easier to implement and is better then nothing.

[Uri Blass]

How do you define "move ordering success"? Is this percentage of nodes where you have searched the eventual best move first?

Yes, exactly.

No

I guess that you mean to percentage of nodes when first move fail high.

first move fail high does not mean searching the best move first because it is possible that there is a better move that can also fail high but you do not search.

Uri

[mcostalba]

How do you define "move ordering success"? Is this percentage of nodes where you have searched the eventual best move first?

Yes, exactly.

No

I guess that you mean to percentage of nodes when first move fail high.

first move fail high does not mean searching the best move first because it is possible that there is a better move that can also fail high but you do not search.

Uri

Yes, I agree with Uri.

The IMHO correct way to measure move ordering is to calculate the average move count of the move that produces a cut-off, i.e. the move that fails high.

Sometime it will be the first, sometime move 5 or move 12. Every time a move produces a cut-off then update the average move count:

Code: Select all

cutOffNr++;
cutOffDistance += moveIndex;

At the end the metric to evaluate move ordering is:

Code: Select all

    avgDistance = cutOffDistance / cutOffNr

The smaller the better of course.

[OliverUwira]

How do you define "move ordering success"? Is this percentage of nodes where you have searched the eventual best move first?

Yes, exactly.

No

I guess that you mean to percentage of nodes when first move fail high.

first move fail high does not mean searching the best move first because it is possible that there is a better move that can also fail high but you do not search.

Uri

At PV nodes, where all moves have to be searched, we still want to search the best move first, don't we?

So to be more precise, the number of nodes where the first move we search either lets us cut off (failing high) or stays the best move in case we don't fail high at all.