A few things to debate for my chess engine

[ZirconiumX]

The reason I haven't implemented move sorting is because I'm not sure how to do it. By this I mean do I have a huge table of moves that a function says this move is the best to search? (I took a look at Viper, and that's how it does move sorting) Do I have a function that wastes time sorting all the moves, then passes them to search? Do I search PV move first? Captures? Checks? What if I don't have a PV?

See what I mean?

Matthew:out

[hgm]

Well, if you have no move sorting you should not be surprised your search performs like cr*p and hardly reaches any depth at all. Move sorting is themost critical thing in an engine, absolutely esential to benefit significantly from alpha-beta pruning.

The bare minimum is to first search the capture of the most valuable victim, (you will get horrible search explosion in QS if you don't, making your depth drop below 1 ply later in the game if you don't), then other captures, then non-captures. If you have a hash or PV move it should be searched before all those. Even micro-Max does this. Then there are heuristics that speed up our search (time-vs-depth-wise) like killer and history, which tell you in what order to search the non-captures

The way it is usually implemented is have the move generator put the moves in a table (local to the node), 'score' them with a sort key, and then extract the move with the highest sort key when you need to search the next move. (Complete sorting in advance could be wasteful, because there is a 90% probability the first move will cause a beta cutoff. So it is better to use a poor sorting algorithm that is cheap when you abort it.) The simplest way to sort the captures is MVV/LVA order.

[ZirconiumX]

I have a sorting algorithm in place. It orders moves highest value to lowest value. (Ignoring the fact that the moves may or may not be captures).

Code: Select all

info string dbg: nodes: 17410 = ALL, 250822 = CUT, 7748 = PV, 3688828 = Quiescence
info string dbg: search: pruning: 1835 = Futility, 64 = Extended Futility, 7912 = Nullmove, 0 = Hash Table, 0 = Multi-Cut
info string dbg: search: reductions: 19 = Razoring, 79135 = Fail-High, 14500 = Late Move
info string dbg: search: extensions: 2318 = Check, 0 = One Reply, 4897 = Singular
info depth 6 score cp -10 nodes 6078949 time 60363 nps 29554 pv b8c6 b1c3 a7a6 d1f3 c6e5 f3e3 
bestmove b8c6

Not brilliant I know...

Matthew:out

[Evert]

The way it is usually implemented is have the move generator put the moves in a table (local to the node), 'score' them with a sort key, and then extract the move with the highest sort key when you need to search the next move. (Complete sorting in advance could be wasteful, because there is a 90% probability the first move will cause a beta cutoff. So it is better to use a poor sorting algorithm that is cheap when you abort it.)

Indeed.
I keep track of the expected best move, and I try it before sorting the rest of the movelist. To do the sort itself I use libc's qsort, which is probably not the best choice, but it works (and I've been too lazy to sit down and replace it by something else, I suspect a lazy insertion sort may be better).

[hgm]

I have a sorting algorithm in place. It orders moves highest value to lowest value. (Ignoring the fact that the moves may or may not be captures).

Good. Now sorting was not a goal in itself, but this will allow you to sort them in a benificial order. Of course you could also sort them in a way that maximally slows down the earch, by firstsearching the moves that are least likely to be good.

So it all depends on what exactly you call 'value' above. The fact that you ignore whether the moves are captures or not does not sound very promising in this respect...

[ZirconiumX]

Value is defined as:
Capture: Value is MVV/LVA value.
Non-Capture: History value. The problem with this is that the history table at the start of the search is empty...

Current Root Move order after 1. e4: Na6, Nc6, a5, b6, e5, a6, b5, c6, d6, d5, e6, f6, f5, g5, h6, h5, Nh6, c5, g6, Nf6.

So they are sorted, but not sorted, if you know what I mean.

Matthew:out

[AlvaroBegue]

In your description, it's still unclear what "MVV/LVA value" means.

You should make sure that values for non-captures are always higher than values for captures. If you have transposition tables, you should store the best move in them, and then you should make sure that the move from the transposition tables has the highest value.

Code: Select all

if (move[i] == hash_move) {
  value = 2000000000;
} else if (is_capture(move[i])) {
  value = 1000000000 + victim(move[i]) * 100 - attacker(move[i]); // assuming the codes for pieces are small numbers with P<N<B<R<Q<K
}
else {
  value = min(history_table[move[i].from][move[i].to], 900000000);
}

You can start with code that looks something like that, and then decide where you want killer moves, or you may want to use SEE (static exchange evaluation) to discriminate between captures...

The good news about working on move ordering is that, unless you use LMR, changing it mostly doesn't affect the result of the search, only how long it takes to complete it. So it's fairly easy to test on a set of positions, unlike pretty much any other type of improvement to the search.

[ZirconiumX]

From what I've read - this is not what should happen. Captures are forcing things, that should be investigated ASAP. MVV/LVA Value is value of captured piece minus value to capturing piece.

Anyway, trying your idea has an extermely detrimental effect on my search. (I get depth 5 with 602K nodes, whereas your idea gets depth 5 with 853K nodes).

BTW: I do use LMR.

Matthew:out

[sje]

The way it is usually implemented is have the move generator put the moves in a table (local to the node), 'score' them with a sort key, and then extract the move with the highest sort key when you need to search the next move. (Complete sorting in advance could be wasteful, because there is a 90% probability the first move will cause a beta cutoff. So it is better to use a poor sorting algorithm that is cheap when you abort it.)

Indeed.
I keep track of the expected best move, and I try it before sorting the rest of the movelist. To do the sort itself I use libc's qsort, which is probably not the best choice, but it works (and I've been too lazy to sit down and replace it by something else, I suspect a lazy insertion sort may be better).

It is worthwhile to write a specialized sort than to rely upon a general library sort for time-critical code. One reason here is that any general library sort will treat record length as a variable and so moving records will always take longer than with the fixed length case.

From BozoChess, I have presented a move sort routine that moves records exactly twice; once into a temporary array and once back into the result array. All other motion is of only score values and a one byte record index.

For other issues involving move sorting, the best answers can be had only via experimentation.

[AlvaroBegue]

It is worthwhile to write a specialized sort than to rely upon a general library sort for time-critical code. One reason here is that any general library sort will treat record length as a variable and so moving records will always take longer than with the fixed length case.

Actually, that is not true of C++'s std::sort. In that case, the compiler will generate code using the record length as a constant.

The other reason why you may not want to use a library sort is that you often only need to explore the first few moves, so if you simply select the highest value in O(n) and swap the corresponding move to the beginning of the move list, you don't need to pay O(n*log(n)) if an early cut is found. Perhaps one should sort differently depending on whether you expect the node to be a CUT node or not.