Getting a baseline on move ordering

[zd3nik]

Hello all. I'm new to this forum, but I've been writing chess engines (poorly) for years as a hobby.

I've been trying to figure out why recent changes in my current chess program ended up drastically reducing effectiveness of LMR and other search techniques in my PVS framework. I've read through this discussion http://www.open-chess.org/viewtopic.php?f=5&t=2173, and it pretty much confirms what I was thinking: LMR (and others) are dramatically effected by move ordering. But with LMR the effect is kind of backward from what I would want. The more I improve my move ordering, the less effective LMR becomes because it's applied to fewer branches. I was getting better results with worse move ordering because LMR was being applied to a much larger number of branches within the tree. And the improved move ordering isn't producing as much benefit overall as LMR + worse move ordering was. In fact it's much worse. Now my program's only hitting about 12 ply on average in a 5 minute game. Before the move ordering improvements it was hitting more like 15-16 ply resulting in much better round-robin results against other engines - in case you're wondering, it still gets creamed by the big boys in either case

Anyway, as a bit of a spin-off from this particular problem, I'm wondering if there are any stats out there to use as a benchmark for the effectiveness of an engine's move ordering. Of course the real test is how well your engine plays but a baseline could still be handy, especially if you're just getting started.

I've added some counters to my current program to show how many searches are done at moves 0-99 in each ply and of those how many produced a beta cutoff. Slot 0 is for cutoffs produced before any move is searched, such as TT and Null Move cutoffs. This should probably also show how many alpha increases occurred at each move number, but before I make any more changes I want to see if I get any feedback using what I already have.

I don't include captures, promotions, passed pawn pushes, or moves in positions where the side to move is in check. Basically I'm only counting LMR candidate moves. CUT nodes and ALL nodes are counted separately. I've chosen what I think is a good mix of test positions for this small trial: startpos, middle game positions, and early endgame positions. All except startpos being volatile enough to have a mix of good/bad lines, and no drawish positions.

Results with all search enhancements disabled. Just brute force PVS + Quiescence + Move Ordering (killer bonus, history bonus, PST, etc):

Code: Select all

depth: 10, max quiescence depth: 34, total nodes: 3620860503

CUT nodes:
0/461211053(0.00) 445593682/461009801(96.66) 3878/29890(12.97) 2003/29207(6.86) 1068/32332(3.30) 728/35347(2.06) 707/36792(1.92)
566/37326(1.52) 535/38199(1.40) 408/38334(1.06) 352/37434(0.94) 310/37209(0.83) 229/37399(0.61) 289/38645(0.75) 230/38314(0.60)
218/39442(0.55) 253/40722(0.62) 242/42633(0.57) 197/44899(0.44) 182/45990(0.40) 147/43317(0.34) 167/42410(0.39) 115/40335(0.29)
91/36865(0.25) 95/35316(0.27) 80/32306(0.25) 96/28975(0.33) 67/25071(0.27) 61/22356(0.27) 39/20725(0.19) 28/18990(0.15)
15/16711(0.09) 12/14173(0.08) 8/11880(0.07) 7/10117(0.07) 4/8374(0.05) 4/6681(0.06) 1/5231(0.02) 4/3644(0.11) 3/2447(0.12)
0/1613(0.00) 1/980(0.10) 0/483(0.00) 0/215(0.00) 0/93(0.00) 0/47(0.00) 0/16(0.00) 0/16(0.00) 0/4(0.00) 0/2(0.00)

ALL nodes:
0/51688421(0.00) 2234436/51946721(4.30) 485/738510(0.07) 255/795428(0.03) 237/864372(0.03) 204/911869(0.02) 137/943767(0.01)
111/1050256(0.01) 107/1072304(0.01) 82/1048043(0.01) 104/1004394(0.01) 129/986795(0.01) 141/991634(0.01) 130/1001543(0.01)
170/1026547(0.02) 129/1026708(0.01) 141/991838(0.01) 140/923451(0.02) 127/829661(0.02) 96/762579(0.01) 87/697047(0.01)
76/636570(0.01) 63/600109(0.01) 46/552703(0.01) 28/497563(0.01) 25/423608(0.01) 32/353371(0.01) 26/291769(0.01)
14/225920(0.01) 4/175184(0.00) 5/132516(0.00) 2/93830(0.00) 3/68270(0.00) 0/45175(0.00) 1/29247(0.00) 2/19015(0.01)
0/11394(0.00) 0/7311(0.00) 0/4110(0.00) 0/2521(0.00) 0/1354(0.00) 0/739(0.00) 2/374(0.53) 0/156(0.00) 0/63(0.00)
0/18(0.00) 0/8(0.00) 0/3(0.00) 0/3(0.00) 0/2(0.00)

Are these numbers even remotely in line with other engines? Anyone out there willing to perform a similar test in their engines so we can build a dataset to get a feel for what's sane and what isn't?

[zd3nik]

It appears my post was not very well constructed. Perhaps I should narrow the field a bit and actually ask a specific question...

Forget about the move ordering baseline. Too many variables involved and too much work required to get data.

So all that remains is this question: Has anyone else experienced counterproductive results from improved move ordering?

Before my recent move ordering improvements LMR was much more effective because a greater number of late moves were being search. Now an inconsequential number of late moves are being searched and as a result late move reductions (of any value) have no meaningful effect. The total number of nodes searched is only reduced by about 2%.

The weird thing is: the benefit of fewer late move searches (more early move cutoffs) is proving to be less effective than worse move ordering which allows LMR to take effect on a greater number of branches within the search tree. The tactical weaknesses of more depth reductions are counterbalanced (sometimes) by greater overall search depths obtained within the same amount of time. As I said in the original post, before my move ordering improvements my program was achieving about 15-16 plies on average in 5 minute games. With the move ordering improvements it's only obtaining 11-12 plies. Node rate has stayed the same.

[hyatt]

I didn't quite follow your question. Move ordering should not cause LMR to reduce fewer moves. It should only change which moves get reduced and by how much. Normal practice is first few moves are reduced very little, if any. Later moves (hence the LM in LMR) get reduced more. How is move ordering preventing you from reducing moves that appear later in the list???

[zd3nik]

I didn't quite follow your question. Move ordering should not cause LMR to reduce fewer moves. It should only change which moves get reduced and by how much. Normal practice is first few moves are reduced very little, if any. Later moves (hence the LM in LMR) get reduced more. How is move ordering preventing you from reducing moves that appear later in the list???

Yeah, I have a tendency to over-explain things, which obfuscates rather than clarifies my questions. Sorry about that...

Anyway, better move ordering isn't preventing moves later in the list from being "reduced", it's preventing most late moves from being searched at all because I'm getting so many beta cutoffs in early moves. One would think this would still be a net gain, but that's not what I'm seeing.

[zd3nik]

Turns out I had moved a couple calls around resulting in LMR "candidates" being reduced to almost nothing. It was basically thinking (incorrectly) that almost every move was a capture.

Sorry if I wasted anyone's time.