which first: legality or delivering check?

[hgm]

When I have a pseudo-legal move generator, (deferring legality-checking to when I actually consider searching the move, to maximally profit from the fact that that moment might never come because of a beta cutoff), which strategy is better?

Should I first test the legality (if the move puts myself in check) and then the checking status (if and how I put the opponent in check)? Then I don't waste time on the checking status in case the move was illegal.

Or should I reverse the order, and test if the move is checking first? The point is that this information might cause me to realize that I don't want to search this move at all, near the leaves, (futility pruning). I need the in-check information to decide if standing pat is allowed, and if it is, and causes a cutoff, the move would already have been proved poor enough not to affect the search, without the need to know if it is also illegal. (Except, of course, if we are using this information to decide if we are stalemated, but I assume this was already decided in another way.)

Most pseudo-legal moves are also legal, so the common case is that you have to do both tests. And then the order does not matter. But t seems to me that it would occur more frequently that I save testing the legality (because the position after the move produces a stand-pat cutoff if it does not deliver check), than that I would save testing the checking (because the move was illegal). Because most moves do not deliver check, while most moves wil be legal. So deterimining if illegal moves deliver check might actually make sense.

[Alessandro Damiani]

Should I first test the legality (if the move puts myself in check) and then the checking status (if and how I put the opponent in check)? Then I don't waste time on the checking status in case the move was illegal.

Or should I reverse the order, and test if the move is checking first? The point is that this information might cause me to realize that I don't want to search this move at all, near the leaves, (futility pruning). I need the in-check information to decide if standing pat is allowed, and if it is, and causes a cutoff, the move would already have been proved poor enough not to affect the search, without the need to know if it is also illegal. (Except, of course, if we are using this information to decide if we are stalemated, but I assume this was already decided in another way.)

You may do it conditionally:

Code: Select all

if futility-pruning is applied ->
     determine in-check;
     if futile -> exit fi;
     if move is illegal -> exit fi
[] futility-pruning is not applied ->
     if move is illegal -> exit fi;
     determine in-check
fi

[mcostalba]

I need the in-check information to decide if standing pat is allowed, and if it is, and causes a cutoff, the move would already have been proved poor enough not to affect the search, without the need to know if it is also illegal.

Evaluation is an order of magnitude slower then legality check otherwise your legality check is seriously broken.

If you know a move is illegal you don't evaluate the position for stand pat and this saves you the day.

Anyhow, as always, only quantitative data counts. My guess is that it is an unuseful complication...and could even slow things down due to spurious evaluation of illegal positions (that is also seriously bugs prone in itself).

[hgm]

Evaluation is an order of magnitude slower then legality check otherwise your legality check is seriously broken.

Not necessarily: material is acocunted differentially, and thus can be checked instantly. And if you are up a Rook there, you might as well take the cutoff.

[mcostalba]

Evaluation is an order of magnitude slower then legality check otherwise your legality check is seriously broken.

Not necessarily: material is acocunted differentially, and thus can be checked instantly. And if you are up a Rook there, you might as well take the cutoff.

Ok, you are talking about a quick evaluation, not a full position evaluation (something on this later).

Material is updated in do_move() or something similar, when you update incrementally all that you can.

But checking for legality is in any case much cheaper then calling do_move(), and I think, if you don't discard the move before becuase illegal, that at least a call to do_move() is needed before checking the material.

Now we come back to quick evaluation: I have never seen (probably my bad and due to little browsing on my side) a "stand pat" logic implemented using quick eval instead of full eval.

[hgm]

Now we come back to quick evaluation: I have never seen (probably my bad and due to little browsing on my side) a "stand pat" logic implemented using quick eval instead of full eval.

This is most likely so because you know it under a different name: futility pruning. There you (usually) make a quick eval estimate by adding captured material to the full eval of the current node, and anticipate any predicted stand pat by not making the move at all. There is then no reason to redo such a test in the node itself, as obvious stand-pat cutoff cases will never reach that stage, bing intercepted by futility in the parent.

But to decide about the futility, I need to know if the move delivers check, as I don't want to pune checking moves. But I can prune them without having to know if they are legal.

So perhaps the best order is

1) test if the move delivers check
2) decide about futility based on a quick eval estimate
3) perform the move
4) test if the move was legal
5) decide about stand-pat cutoff based on full eval.

It might be better to swap 3 and 4, but I assumed testing the move before it is made is more cumbersome than after it is made, (e.g. King 'stepping into its own shadow' problems). If more than 90% of the moves are legal, you save one MakeMove every 10 moves by doing the legality test before it, but if that drives up the cost of the test by 10% of the cost of MakeMove, it already offsets this.

It is not obvious at all to me that in my case checking for legality is on the average cheaper than calling MakeMove. In many cases it requires one or two ray scan over the board, from the King, in the direction of the from and two squares.

[mcostalba]

It is not obvious at all to me that in my case checking for legality is on the average cheaper than calling MakeMove. In many cases it requires one or two ray scan over the board, from the King, in the direction of the from and two squares.

Probably this is the point.

In my case, using bitboards, legality check is quite fast when is not a king move, and moderatly fast when the moving piece is the king.

[hgm]

Yes, and in that case MakeMove is probably quite slow compared to what I have to do for it.

But you have a good point that in cases where a quick eval is not decisive in indicating the cutoff, it might be better to make sure the move is legal before doing a full eval.