Pseudo-legal move and move ordering

[hgm]

It is unusual for engines to take into account whether moves deliver check, in move ordering. I am surprised that it helps.

Some engines search non-captures that deliver check in the first few levels of QS, though. These have to face a similar dilemma as you. The efficient solution there is to generate checks selectively, rather than just generate all moves, and test those on a per-move basis for delivering check.

E.g. Fruit has tables that for a given relative location of a piece and the enemy King tabulate a list of squares where a piece of that type could potentially deliver check, and only tries to generate those moves. With bitboard you can easily generate bitboards with the empty squares where various piece types could deliver check as prepatory work, and intersect those with the moves you generate for individual pieces to get the subset of moves that delivers check. The intersection of orthogonals and diagonals from the enemy King with stm pieces indicate which pieces could potentially deliver discovered checks.

[Jakob Progsch]

It is unusual for engines to take into account whether moves deliver check, in move ordering. I am surprised that it helps.

While not representative for most engines I found without check extensions ordering checking moves early provided a decent amount of speed up/node reduction. I did some measureing of statistics and while I can't remember the numbers it was something like checks having a lower chance of producing cuts than captures, but since checks only have very few responses there are less nodes below them in the tree. So they produce more cutoffs per nodes searched than other moves at the same depth.
Obviously once you have check extensions that goes out the window since those invert this behavior and make the trees below checks bigger.

[lithander]

- ordering moves that give check early is good for Zahak

It is unusual for engines to take into account whether moves deliver check, in move ordering. I am surprised that it helps.

I found without check extensions ordering checking moves early provided a decent amount of speed up/node reduction.

I don't really do check extensions at this point I think. Just in QSearch, when a side is in check it's allowed to expand all moves instead of only the capture moves to evade it.

So to favor moves that give check in the move ordering is a pretty interesting idea I will put on my list to try. (Check extensions is already on that list)
I assume you'll still play a capture that doesn't give check before a quiet move that gives check?

[Jakob Progsch]

I assume you'll still play a capture that doesn't give check before a quiet move that gives check?

I think I saw improvements all the way up to ordering them before winning captures but below promotions. But I then considered the behavior pathological for the extension reason. Also while measurable the effect wasn't huge. It was just interesting since it seemed to go against common wisdom. I felt a more general approach would be to have the engine measure statistics of tree sizes and cut probabilities and then trying to order by "bang for buck" (cuts per node) instead of move strength in no-PV moves. I have not actually acted on that idea yet though.

[hgm]

Obviously once you have check extensions that goes out the window since those invert this behavior and make the trees below checks bigger.

That was exactly my expectation. And a lot of checks are very poor moves, in particular when the checker simply gets captured. So it would probably be helpful to distingush checks with SEE < 0 from others.

[amanjpro]

I have check extension, and my move ordering is this:

- PV node
- Promotion
- MVV-LVA
- Captures with positive SEE
- EP capture
- MVV-LVA for captures that have SEE == 0 (I believe, I should move this to before EP)
- (quiet) Killer moves
- (quiet) History moves
- (quiet) Checks (that are not captures)
- (quiet) Castles
- (quiet) Other moves sorted in an increasing order of the value of the mover (pawn first, king last)
- Captures with negative SEE

There is a possible update though, I figured that I was calling `time.Now` a bit too much, and this is very slow in GoLang. So probably whatever I was doing, the impact of calling that function was just too high. Now I removed them all, and use more efficient ways to get time elapsed since start time, I'll retry pseudo-legal moves again and see if there is any change.

[hgm]

If I use history I apply it to all non-captures. How do you limit the number of history moves, just a fixed number, or by history score?

[amanjpro]

If I use history I apply it to all non-captures. How do you limit the number of history moves, just a fixed number, or by history score?

I give history bonus on beta-cutoff, and also decrease the bonus for moves that do not produce beta-cutoff in each ply. If history bonus is 0, that means the move has never produced a beta-cutoff, and that is where the fallback happens

Edit Thinking about it, the moves that have history bonus == 0 is rather small, so I doubt the ordering that happen after history have much impact. I'll revisit

[amanjpro]

So, quick update. For time elapsed (time management) I was using: `time.Now().Sub(timeStarted)` And this allocates a new `time` object on the heap only to throw it away right after the statement. And this was happening in every search iteration. I was creating an enourmous amount of objects on the heap. GoLang being a GC langauge, didn't like this and was keeping cleaning up the heap after me.

With pseudo legal moves, I was able to search more nodes fast, then GC wakes up and slows down the search, thus I was experiencing Elo loss. I fixed the `time` allocation, and now I gain some Elos (a match is going on, and here is the result so far):

Code: Select all

Score of zahak_next vs zahak_master: 185 - 147 - 303  [0.530] 635
...      zahak_next playing White: 110 - 55 - 153  [0.586] 318
...      zahak_next playing Black: 75 - 92 - 150  [0.473] 317
...      White vs Black: 202 - 130 - 303  [0.557] 635
Elo difference: 20.8 +/- 19.5, LOS: 98.1 %, DrawRatio: 47.7 %
Started game 642 of 3000 (zahak_master vs zahak_next)

the gain is within my expectations

[amanjpro]

I reduced the frequency of time check up and gained double the NPS. And now the pseudo legal movegen is much better. At least 50 elos stronger