I have been experimenting with pseudo-legal moves, and its impact on Zahak.
Currently Zahak generates fully legal moves. For every move at move generation
time:
- Movegen plays them
- checks if it is in-check or gives check
- Rejects moves that exposes king
- Tags check moves with (Check), which is then used in search to know if position is in check
- The check tag is also used for move-ordering (after killer and history moves, I prefer check moves).
- Note that, in this approach I play EVERY pseudo-legal move at least ONCE, and every legal move at most TWICE (at move gen time, and search time)
I changed this to:
- Movegen generates pseudo legal moves
- Sends them all to search (move-picker)
- Search plays them, and rejects illegal ones, accepts legal ones
- ONLY the moves that are actually searched are played (moves played at most ONCE)
- I do not and CANNOT use (check) for move-ordering. As I no longer have the info prior to search
The second approach, while makes for a much better NPS, but fails in the depth test. As my engine really enjoys the current move ordering. Anybody has experience with this? I probably need to find a more efficient way to find legal moves at movegen time, and tag moves with Check at the same time. But so far, all the approaches that I have seen are super complex for discovered checks
Pseudo-legal move and move ordering
Moderators: hgm, Rebel, chrisw
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Pseudo-legal move and move ordering
I order illegal moves. (That is Add them to a priority queue) .
But before I play them I test if they are legal.
But my engine is slow.
But before I play them I test if they are legal.
But my engine is slow.
Last edited by Henk on Wed May 12, 2021 3:10 pm, edited 1 time in total.
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Pseudo-legal move and move ordering
In both cases I was ordering moves legal and illegal. But in pseudo legal moves I cannot use Check tag anymore, as they will be available after a move is searched
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Pseudo-legal move and move ordering
Don't know what check tag means.
MoveGeneration may be different when in check.
MoveGeneration may be different when in check.
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Pseudo-legal move and move ordering
Oh, I meant I tag a move that gives check. So I can recognize them, instead of computing it always on the fly.
And I only know that, if I actually play the move (at least in my current implementation)
And I only know that, if I actually play the move (at least in my current implementation)
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: Pseudo-legal move and move ordering
Checking whether a move gives check is expensive. Might be that move is never played or do they always get highest priority.
But even then. Move might be illlegal.
But even then. Move might be illlegal.
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Pseudo-legal move and move ordering
And despite that, as I mentioned in the original post, checking it for EVERY move, legal or illegal makes for a niche better search depth. As I get compensated in the move ordering
-
- Posts: 27796
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Pseudo-legal move and move ordering
does your engine extend check evasions? My enines usually do, and this makes searching checks far more expensive than searching other moves. So it is more a case of 'when all else fails, try a check'.
If you want to know in advance which moves are checks, it might be better to selectively generate those than to generate all and test them all for delivering check. I don't know if your engine is mailbox or bitboard. Fruit is a mailbox engine that has a dedicated move generator for checks. It runs throuh the piece list, and has tables indexed by the relative King and piece position where it can look up on which squares the piece could potentially deliver check. (Being mailbox it then has to test for sliders whether the paths to that square are unobstructed.)
If you want to know in advance which moves are checks, it might be better to selectively generate those than to generate all and test them all for delivering check. I don't know if your engine is mailbox or bitboard. Fruit is a mailbox engine that has a dedicated move generator for checks. It runs throuh the piece list, and has tables indexed by the relative King and piece position where it can look up on which squares the piece could potentially deliver check. (Being mailbox it then has to test for sliders whether the paths to that square are unobstructed.)
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Pseudo-legal move and move ordering
I do have check extension yes. It adds ~30 elo I believe.hgm wrote: ↑Wed May 12, 2021 3:33 pm does your engine extend check evasions? My enines usually do, and this makes searching checks far more expensive than searching other moves. So it is more a case of 'when all else fails, try a check'.
If you want to know in advance which moves are checks, it might be better to selectively generate those than to generate all and test them all for delivering check. I don't know if your engine is mailbox or bitboard. Fruit is a mailbox engine that has a dedicated move generator for checks. It runs throuh the piece list, and has tables indexed by the relative King and piece position where it can look up on which squares the piece could potentially deliver check. (Being mailbox it then has to test for sliders whether the paths to that square are unobstructed.)
I use bitboard (mainly because I didn't know about mailbox when I first started working on Zahak )
Thanks to your reply, I think I found a way to detect illegal moves/tag moves that give check without playing them... will try it next
-
- Posts: 883
- Joined: Sat Mar 13, 2021 1:47 am
- Full name: Amanj Sherwany
Re: Pseudo-legal move and move ordering
Okey... I believe it is official for Zahak. He won't be getting pseudo legal movegen. I implemented one and it caused a loss of strength. Which I can only explain with three factors:
- My movescore and next move functions become slower as the move list grows (pseudo legal moves can be in hundreds)
- ordering moves that give check early is good for Zahak
- my make move method (actually partial make move method which is tailored for movegen only) is fast enough to balance out/beat the pseudo legal movegen version
- My movescore and next move functions become slower as the move list grows (pseudo legal moves can be in hundreds)
- ordering moves that give check early is good for Zahak
- my make move method (actually partial make move method which is tailored for movegen only) is fast enough to balance out/beat the pseudo legal movegen version