Move ordering searches more nodes

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
niel5946
Posts: 82
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Move ordering searches more nodes

Post by niel5946 » Sun Mar 07, 2021 10:44 am

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)
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

User avatar
mvanthoor
Posts: 986
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Move ordering searches more nodes

Post by mvanthoor » Sun Mar 07, 2021 11:00 am

niel5946 wrote:
Sun Mar 07, 2021 10:44 am
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.
Author of Rustic.
Releases | Code | Docs

niel5946
Posts: 82
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Move ordering searches more nodes

Post by niel5946 » Sun Mar 07, 2021 11:04 am

mvanthoor wrote:
Sun Mar 07, 2021 11:00 am
niel5946 wrote:
Sun Mar 07, 2021 10:44 am
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
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

Ras
Posts: 1875
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Move ordering searches more nodes

Post by Ras » Sun Mar 07, 2021 11:53 am

niel5946 wrote:
Sun Mar 07, 2021 10:44 am
Losing captures
How did you implement that? Just high takes low is a necessary condition for a losing capture, but not a sufficient one.
Rasmus Althoff
https://www.ct800.net

niel5946
Posts: 82
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Move ordering searches more nodes

Post by niel5946 » Sun Mar 07, 2021 12:09 pm

Ras wrote:
Sun Mar 07, 2021 11:53 am
niel5946 wrote:
Sun Mar 07, 2021 10:44 am
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?
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

User avatar
hgm
Posts: 26134
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering searches more nodes

Post by hgm » Sun Mar 07, 2021 12:29 pm

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
Posts: 1875
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: Move ordering searches more nodes

Post by Ras » Sun Mar 07, 2021 12:29 pm

niel5946 wrote:
Sun Mar 07, 2021 12:09 pm
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.
Rasmus Althoff
https://www.ct800.net

niel5946
Posts: 82
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: Move ordering searches more nodes

Post by niel5946 » Sun Mar 07, 2021 1:09 pm

hgm wrote:
Sun Mar 07, 2021 12:29 pm
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?
Author of Loki, a C++ work in progress.
Code | Releases | Progress Log |

User avatar
hgm
Posts: 26134
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering searches more nodes

Post by hgm » Sun Mar 07, 2021 1:37 pm

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.)

Post Reply