caps->noncaps vs. goodcaps->noncaps->badcaps

[jswaff]

Some time back I changed the move ordering in Prophet to just try all captures before noncaptures are even generated. However, I continue to read that many (most?) defer losing captures until after the noncaptures have been tried. So, I decided to give it another try.

Below are the node counts from running WAC and BT2630 to a fixed depth of 10 (well, 10 iterations). As you can see, there was a *significant* increase in the number of nodes processed when deferring bad captures. (The node counts below are divided by 1000 BTW.)

WAC:

Code: Select all

james@frodo ~/haskell $ runhugs nodecounts.hs < capsfirst-wac.out
300 lines processed.
total interior nodes&#58; 48188
total quiesence nodes&#58; 173934
total nodes&#58; 222122
done!

james@frodo ~/haskell $ runhugs nodecounts.hs < badcapslast-wac.out
300 lines processed.
total interior nodes&#58; 64056
total quiesence nodes&#58; 303719
total nodes&#58; 367775
done!

BT2630:

Code: Select all

james@frodo ~/haskell $ runhugs nodecounts.hs < capsfirst-bt2630.out
30 lines processed.
total interior nodes&#58; 10025
total quiesence nodes&#58; 38898
total nodes&#58; 48923
done!

james@frodo ~/haskell $ runhugs nodecounts.hs < badcapslast-bt2630.out
30 lines processed.
total interior nodes&#58; 15111
total quiesence nodes&#58; 77186
total nodes&#58; 92297
done!

My current move ordering scheme for interior nodes (non root) is simply:
pv move
hash move 1 (from depth preferred table)
hash move 2 (from always replace table)
captures, in order of MVV/LVA
killer 1
killer 2
noncaptures, in order of history score

I'm curious how many of you defer losing captures, and how many do not, and if anybody has had similar results to what I've come up with.

--
James

[frankp]

I do losing captures after non-caps and believe it a win, based on minimal testing. Logically I would anticipate leaving daft moves until last a win on average. Tactical positions might prove the exception - when it may be good to sac a piece or two.

Do you do late move reduction on losing captures, or all captures, or non captures and losing captures ......?

[bob]

Some time back I changed the move ordering in Prophet to just try all captures before noncaptures are even generated. However, I continue to read that many (most?) defer losing captures until after the noncaptures have been tried. So, I decided to give it another try.

Below are the node counts from running WAC and BT2630 to a fixed depth of 10 (well, 10 iterations). As you can see, there was a *significant* increase in the number of nodes processed when deferring bad captures. (The node counts below are divided by 1000 BTW.)

WAC:

Code: Select all

james@frodo ~/haskell $ runhugs nodecounts.hs < capsfirst-wac.out
300 lines processed.
total interior nodes&#58; 48188
total quiesence nodes&#58; 173934
total nodes&#58; 222122
done!

james@frodo ~/haskell $ runhugs nodecounts.hs < badcapslast-wac.out
300 lines processed.
total interior nodes&#58; 64056
total quiesence nodes&#58; 303719
total nodes&#58; 367775
done!

BT2630:

Code: Select all

james@frodo ~/haskell $ runhugs nodecounts.hs < capsfirst-bt2630.out
30 lines processed.
total interior nodes&#58; 10025
total quiesence nodes&#58; 38898
total nodes&#58; 48923
done!

james@frodo ~/haskell $ runhugs nodecounts.hs < badcapslast-bt2630.out
30 lines processed.
total interior nodes&#58; 15111
total quiesence nodes&#58; 77186
total nodes&#58; 92297
done!

My current move ordering scheme for interior nodes (non root) is simply:
pv move
hash move 1 (from depth preferred table)
hash move 2 (from always replace table)
captures, in order of MVV/LVA
killer 1
killer 2
noncaptures, in order of history score

I'm curious how many of you defer losing captures, and how many do not, and if anybody has had similar results to what I've come up with.

--
James

two notes:

(1) your result is exactly what I would expect for tactical tests. After all, tactics generally involve captures and looking at them first is better in those positions. WAC 141 is a classic example where a terrible capture is winning.

(2) the real test is over a couple of thousand games, where real game play becomes more important than just being faster to spot a tactic. Here I'd bet that trying some non-captures first is better.

I will note that in crafty, my move ordering goes like this:

1. hash move (if any)
2. >= 0 captures
3. killer moves
4. losing captures
5. rest of moves.

4 is there because I generate all captures first, but only try the good ones before I try killers. Once killers are done, I generate all the non-captures, but those losing (SEE) captures are still at the front of the list. I'd suspect trying them later is better in non-tactical positions and worse in tactical ones.

[Tord Romstad]

Some time back I changed the move ordering in Prophet to just try all captures before noncaptures are even generated. However, I continue to read that many (most?) defer losing captures until after the noncaptures have been tried. So, I decided to give it another try.

Below are the node counts from running WAC and BT2630 to a fixed depth of 10 (well, 10 iterations). As you can see, there was a *significant* increase in the number of nodes processed when deferring bad captures. (The node counts below are divided by 1000 BTW.)

As has been pointed out elsewhere in the thread, tactical test positions are not good for testing move ordering, because they are very different from the average position you see in actual games. In particular, losing captures are often the best moves in tactical tet positions, so the results you observe are not unexpected.

In my own move ordering tests, I use 500 randomly chosen positions from my own engine's games.

Some time ago, I compared three different move ordering schemes for Glaurung:

Scheme 1:

1. Hash move.
2. Winning and equal captures, ordered by MVV/LVA (somewhat surprisingly, MVV/LVA seems to work better than SEE).
3. Killer moves.
4. Non-captures, ordered by history scores.
5. Losing captures, ordered by SEE value.

Scheme 2:

1. Hash move.
2. Winning and equal captures, ordered by MVV/LVA.
3. Losing captures, ordered by SEE.
4. Killer moves.
5. Non-captures, ordered by history scores.

Scheme 3:

1. Hash move.
2. Winning and equal captures, ordered by MVV/LVA
3. Killer moves.
4. Non-losing non-captures, ordered by history scores.
5. Losing captures and non-captures, ordered by SEE.

Of these three schemes, scheme number 1 was slightly better than scheme number 2, while scheme number 3 performed clearly worse. I don't understand why - intuitively I would expect scheme number 3 to be the best.

Tord

[jswaff]

I do losing captures after non-caps and believe it a win, based on minimal testing. Logically I would anticipate leaving daft moves until last a win on average. Tactical positions might prove the exception - when it may be good to sac a piece or two.

Do you do late move reduction on losing captures, or all captures, or non captures and losing captures ......?

Hi Frank,
Thanks for your reply.

My LMR is probably overly restrictive, mainly because I haven't put the time into testing more "relaxed" conditions. As it is now, I don't do LMR on captures at all. The first four moves are never reduced, either. (There are other constraints as well.)

After reading your response earlier today I disabled LMR and repeated the test on the BT2630 suite. Still, quite a significant increase in the number of nodes processed by the version that deferred the losing captures until after the noncaptures.

I'm currently testing Bob's method of trying the losing captures immediately after the killers. And, I guess I should find a non-tactical suite of positions as well.

Code: Select all

james@frodo ~/haskell $ runhugs nodecounts.hs < nolmr_badcapslast-bt2630.out
30 lines processed.
total interior nodes&#58; 81353
total quiesence nodes&#58; 560769
total nodes&#58; 642122
done!

james@frodo ~/haskell $ runhugs nodecounts.hs < nolmr_capsfirst-bt2630.out
30 lines processed.
total interior nodes&#58; 26529
total quiesence nodes&#58; 117993
total nodes&#58; 144522
done!

--
James

[jswaff]

In my own move ordering tests, I use 500 randomly chosen positions from my own engine's games.

I understand what you're saying (and I've heard it before), but at the same time I want to make sure I'm not significantly impairing my programs already limited tactical abilities.

Would you mind sharing your test positions?

--
James

[BubbaTough]

I use Tord Scheme 1...which (last time I checked) works best for me in both tactics and practice. Of course, I do a lot of weird reductions / extensions / pruning so I doubt my experiences generalizes as well as more "normal" (better) engines like Hyatt and Tord built.

In terms of non-tactical test positions, I just grab terminal positions from any old engine opening book. This seems to give me a better sample of interesting positions than from my own engine games...not as many unbalanced positions where one side sacks a pawn for initiative for example. They rarely have a winning tactic in them, and provide a nice mixture of position types (endgames not well represented in short opening books, but you will find them in the 40ply ones.

One thing to note is that depending on how you are doing LMR reductions, move order effects move choice not just depth. For example, if you are reducing all non-captures not in the first 3 moves, doing bad captures first means you are usually reducing ALL non-captures non-cached moves...particularly if you do them before killer movers. Also a factor is whether you allow LMR to reduce killer moves.

-Sam

[CRoberson]

There are two ways to do MVV/LVA:

1) do all queen captures then rook captures ....
2) perform pxb before rxq

I've tried both and 1 seems best.

I think the reason for 1 working better than 2 is the same as putting
bad captures before noncaptures.

Every capture reduces the branch factor and capturing the queen
will reduce it more than capturing the rook.

[bob]

There are two ways to do MVV/LVA:

1) do all queen captures then rook captures ....
2) perform pxb before rxq

I've tried both and 1 seems best.

I think the reason for 1 working better than 2 is the same as putting
bad captures before noncaptures.

Every capture reduces the branch factor and capturing the queen
will reduce it more than capturing the rook.

there can't be two ways. MVV = most valuable victim. So you are constrained to capture the most valuable enemy piece, period, no matter what does the capturing. LVA = least valuable attacker/aggressor. So you find the most valuable piece being attacked, and capture it with the least valuable piece that is attacking it. There's no other way to do MVV/LVA, because it would not be MVV/LVA

[jswaff]

There are two ways to do MVV/LVA:

1) do all queen captures then rook captures ....
2) perform pxb before rxq

I've tried both and 1 seems best.

I think the reason for 1 working better than 2 is the same as putting
bad captures before noncaptures.

Every capture reduces the branch factor and capturing the queen
will reduce it more than capturing the rook.

I've never considered number one. Intuitively number two seems much better. For example, QxQ would not be as attractive as, say, PxR.

I don't get your comment on reducing branching factor. If you can get a cutoff, you want to get it as soon as possible, meaning you want to play the most promising move as early as possible.


--
James