CheckEvasions - reasons to use

[selectany]

I can't understand what is the reasons for use of GenerateCheckEvesionsMoves as part of move generation.
Can I just use GenerateAllMoves and filter moves to only legal ones, by testing for check after probing (MakeMove/UnmakeMove) each generated move?
Only one reason (for me) might be if GenerateCheckEvesionsMove routine is faster than GenerateAllMoves one.

[Teemu Pudas]

It's faster but checks are so rare that you're probably better off writing GenerateCaptures and GenerateNonCaptures first.

[mcostalba]

It's faster but checks are so rare that you're probably better off writing GenerateCaptures and GenerateNonCaptures first.

No they are not rare. In qsearch you always try checks at least at depth 0, this means you are going to generate evasion.

....and yes, the reason to use a dedicated generating function is the speed.

[sje]

Checks are quite common outside of the opening. A well written check evasion move generation routine adds significant speed to a program. Also, a routine that generates only checking moves can be quite useful as long as it's fast and doesn't rely on actually executing each move to determine checking status. Another possibility is a routine that generates only checkmating moves; this can be difficult to write.

For captures vs non-captures, my code distinguishes between "gainers" (regular captures, en passant, and promotions) and "holders" (non-captures and non promotions including castlings).

In all cases, my code generates only legal moves. Getting correct results for castling and en passant is not so hard and getting these right can be worth the implementation effort.

Once the basic move generation routines have been tested, two more sets can be coded: routines that can quickly return a count of moves form a position, and routines that can quickly determine checkmate and stalemate status.

[Daniel Shawul]

May be for speed but I doubt you gain much from it. For qsearch, generating evasions could be a waste specially if you don't generate checks. My new engine with an inaccuate movegen in qsearch i.e gen_caps even when being in check consistently beats the one with accurate evasion generator like 70-30% no matter what I tried. It is a very simple engine with piece square eval only which could be the problem.

[Evert]

May be for speed but I doubt you gain much from it.

My move generator takes from and to bitmasks, so it can only generate moves from or to a part of the board. For instance, if I only want to generate captures, I set the to-mask to the position of all enemy pieces. When in check, I set the to-mask to the set of squares that could be reached by a superpiece at the location of the king: this generates only candidate check evasions, interuptions and captures. This is still very crude, of course, because I still generate many moves that have no chance to resolve the check simply because they aren't on the correct ray. Nevertheless, when I tested this it was clearly much better than just looking at all possible moves.
Not generating moves you know you will prune anyway can never be bad, especially if you can do so quickly.

That said, it probably depends very much on the design of the engine in question what the best approach is.

[Teemu Pudas]

It's faster but checks are so rare that you're probably better off writing GenerateCaptures and GenerateNonCaptures first.

No they are not rare. In qsearch you always try checks at least at depth 0, this means you are going to generate evasion.

Compared to generating _all_ moves in _every_ node, including qsearch, they are rare.

[Daniel Shawul]

I found a measurable speed up in incremental generators for making the hash table move without generating any other move. For killers and captures I didnt find any measurable difference. As you pointed out , this is probably due to my use of piece lists in which case generating captures takes almost as much time as noncaps & allmoves. Bitboards are best for games like checkers. In orthodox chess they require some rotation or majic tables and become clumsy.

Also when you do incremental, you need a sanity check for that move which is not that trivial. In some games it is just impossible to do that. There are so many tests you need to do, it is much easier generating all moves at once. Even for the hash table move this privilage could get screwed up when you go multi processor due to hash collisions.


If we only talk about orthodox chess evasions, I remeber I did gain some speed up for my old engine with piece list. I had to do some game specific in_check and pinned routines to achive that. Taking into consideration the effort that you have to put in, it might not be worth much.

[hgm]

In Spartacus I use 0x88-style capture tests to generate the captures. The advantage is that I can generate captures victim by victim, in MVV order, so that when I have a quick cutoff, I don't even have to generate all captures. I did not pick that system primarily for efficiency, but because the idea that in a future version I would have incrementally-updated attack maps around, where generating captures to a given square would just be a matter of consulting the table.

But to my surprise it is quite competitive in itself. For normal Chess, for instance, generating moves with a Knight from the square it is on requires you to look into 8 directions, probing the board to see if you capture something. Doing the captures 'retrograde', you have to run through 16 possible victims, testing each of them for a 0x88 match with that same Knight. That seems more work, but in a very large fraction of the cases captures on Pawns are futile, so they would never been done even in all-nodes, and that reduces you to 8 victims already. Then the number of tests is equal, but the 0x88 test is slightly more expensive than testing the board. (It requires memory accesses to get the position and capture mask of the potential attacker, and needs to consult the 0x88 table as well, while probing the board for an opponent piece was just a single memory access.) But you make up for that in two ways: often you have a cutoff after considering the first target (if it was a fat one), and you save a lot on sorting the captures. To get MVV/LVA you would only have to sort when there are multiple targets of the same value (and you actually get to them), and the total number of captures on them is usually very small. Sorting is usually a quadratic process, so only having to sort LVA order on captures to equal victims can really save a lot.

And of course as the board occupancy thins, you start to gain big: the Knight would always continue to have 8 moves, there would just be an ever dwindling chance to actually find something on the 8 board squares you have to probe. But the piece list gets shorter and shorter, so the number of 0x88 tests you have to do even in an all-node decreases quadratically. (It is the product of victims x (non-Pawn attackers + 2), as you test the Pawns of course not from the list but by probing the board.)

[Mincho Georgiev]

One of the main reasons to generate only evasions is to use their count. Whether you are going to use them for extensions, reduction or something else is a matter of choice. And whether or not they are useful is another subject.