Move ordering searches more nodes

[niel5946]

Hi.

I have been fiddling around with move ordering the last couple of days in hopes of making LMR more effective, and yesterday I realized that all captures (both winning and loosing) were scored above killers and promotions.
Therefore, I have now changed my move ordering from: hash move, all captures, killers, countermoves, history, promotions and enpassant, to:

• Hash move
• Promotions
• Winning/equal captures (En passant counts as P x P)
• Killer moves
• Countermoves
• Quiets scored with history heuristic
• Losing captures

I sort captures with Mvv/Lva.
After this change I have measured that the percentage of beta-cutoffs on the first move searched has risen from ~84% to ~91%, which should be good. But when I test this change against my previous version it scores around 50 to 100 elo points below, and on top of that it searches around 6 million nodes at depth 10 from the starting position whereas the old version only searches 4.7 million.

Have anybody encountered this problem where better move ordering results in worse play and more nodes? (nps i the same)

[mvanthoor]

Hi.

I have been fiddling around with move ordering the last couple of days
...
Have anybody encountered this problem where better move ordering results in worse play and more nodes? (nps i the same)

Not yet...I'm now in the stages of testing the transposition table (which does order the hash move first, and this seems to work, as it is lowering the number of nodes searched). However, after releasing this, the next version of the engine will be completely about move ordering:

- Order last iteration's best move first when in the root
- Hash move (already in there)
- MVV-LVA (already in there)
- Killers
- Heuristics
- Maybe I'll do something with promotions/capturing promotions as well.

I'll definitely be keeping my eye on that node counter. It would be very strange if the number of searched nodes goes down but the engine searches longer and gets weaker, or if the number of searched nodes goes up. If the latter is the case, it would mean you're putting moves that are worse, to the front of the move list. In that case I'd expect a mistake in the scoring algorithm.

[niel5946]

Hi.

I have been fiddling around with move ordering the last couple of days
...
Have anybody encountered this problem where better move ordering results in worse play and more nodes? (nps i the same)

Not yet...I'm now in the stages of testing the transposition table (which does order the hash move first, and this seems to work, as it is lowering the number of nodes searched). However, after releasing this, the next version of the engine will be completely about move ordering:

- Order last iteration's best move first when in the root
- Hash move (already in there)
- MVV-LVA (already in there)
- Killers
- Heuristics
- Maybe I'll do something with promotions/capturing promotions as well.

I'll definitely be keeping my eye on that node counter. It would be very strange if the number of searched nodes goes down but the engine searches longer and gets weaker, or if the number of searched nodes goes up. If the latter is the case, it would mean you're putting moves that are worse, to the front of the move list. In that case I'd expect a mistake in the scoring algorithm.

That is probably right, but then again: The only thing I have done is added the first_killer score to the move scoring of winning/equal captures, which I would suspect only placed these above the killer moves. But I will have to check that again

[Ras]

Losing captures

How did you implement that? Just high takes low is a necessary condition for a losing capture, but not a sufficient one.

[niel5946]

Losing captures

How did you implement that? Just high takes low is a necessary condition for a losing capture, but not a sufficient one.

I indeed tried just calling H x L losing because I haven't implemented SEE and don't really understand it yet. My MvvLva initialization is now:

Code: Select all

// Initialize MvvLva[attacker][victim].
	int first_killer = 90000;
	int countermove_bonus = 70000;
	
	int victim_scores[6] = { 100, 200, 300, 400, 500, 600 };

	for (int victim = KING; victim >= PAWN; victim--) {
		for (int attacker = KING; attacker >= PAWN; attacker--) {
			
			if (victim >= attacker) { // Equal or winning capture
				MvvLva[attacker][victim] = first_killer + victim_scores[victim] + (6 - attacker);
			}
			else { // Loosing capture. Sort this just before the countermoves
				MvvLva[attacker][victim] = countermove_bonus + victim_scores[victim] + (6 - attacker);
			}
		}
	}

I have just now changed this to score all captures before countermoves, but this still looses ~60 elo.
I don't understand why it doesn't work when calling higher takes lower as loosing. I would suspect that by doing it this way, I would get a cutoff if there were captures of L x H (since these are usually better), but if there were none or they were insufficient, the killers would have a good chance of producing cutoffs. Since there are only two killers, the "loosing" captures would be searched pretty quickly and cutoff if they were actually good.

Is this correct or is my logic flawed?

[hgm]

You overlook that the victim could be unprotected. QxR gains you more than PxB, if the Rook is unprotected. This is what SEE will figure out for you. If the Rook is unprotected, the QxR will have SEE = 5. If it is protected, it will have SEE = -4. All captures with SEE < 0 are bad.

[Ras]

I indeed tried just calling H x L losing because I haven't implemented SEE

That's the issue. HxL is only losing if the opponent can recapture in a winning way. Let's say a queen takes a bishop, that's HxL, but if the bishop is hanging, then it's not a losing capture. Quite the other way around, it's winning material.

I would suspect that by doing it this way, I would get a cutoff if there were captures of L x H (since these are usually better)

You need to go in MVV-LVA order because e.g. QxQ is not necessarily an equal capture in the sense of SEE - it actually can win a queen if the captured queen is hanging. And also, if your queen is hanging, but you get rid of it by capturing your opponent's queen, your opponent cannot win your queen in the next move. That's why you search QxQ before PxR.

[niel5946]

You overlook that the victim could be unprotected. QxR gains you more than PxB, if the Rook is unprotected. This is what SEE will figure out for you. If the Rook is unprotected, the QxR will have SEE = 5. If it is protected, it will have SEE = -4. All captures with SEE < 0 are bad.

Alright, I get it now. What I don't understand however is, when do i call SEE? For every capture or for ones that seem bad?
I can't understand how SEE is more efficient even if it cuts loosing captures in quiescence and helps move ordering... Isn't it just a simple search function only for captures?

[hgm]

The best way is to use SEE only on captures that might be bad (HxL). You can then downgrade the primary sort key (the victim value) to the SEE value. SEE can still be positive even for H x protected L. E.g. when two Rooks attack a Bishop protected by a Knight you can get B+N for R, which makes a SEE of +1.

In principle SEE is a capture search restricted to a single destination square. But there are more efficient ways to calculate it. It is for instance best to capture with your least-valuable piece first. (In a full QS this could be bad because it is soft-pinned, or has to keep protecting some other piece you don't want to lose, but since it would require a capture on another square to punish using that piece in the current exchange, SEE cannot see it.) So at any stage you just have to choose between continuing (with your then lowest attacker) or stopping (standing pat). Because the only side affect a move to a given square can have on other moves to that same square is 'X-raying', you can selectively generate all captures (including X-ray captures) to that square in the current position, without actually making moves and generating new moves from scratch in the resulting position. So you would not really program it as a search. You would just make a list of all white and all black attackers on the square, sorted by increasing value, (but preserving the order of batteries, e.g. with a Rook X-raying a Queen you cannot use the Rook before the Queen), and then calculate how the score ends when the captures would be 'played out' in that order.

Even then, it is still expensive. (But not nearly as expensive as searching an entire node.) So it is a good thing you don't have to do it for all the captures, but only for HxL. But you can use cheaper approximations. E.g. only test whether there are zero protectors, or more, and postpone if there are more. Or also look what the lowest protector is, and if its value together with that of the victim is not more than that of the attacker, you can be sure SEE < 0. (And then you are not interested how much below 0 it is.)