On not leaving the King in check

[Fguy64]

OK, I tried it out, and while my tests so far have not been exhaustive, upon reflection the results were not surprising. In the majority of cases, a straight-up fixed depth search was appreciably faster, as long as check did not play a prominent role. But if additional ply was required to solve a tactic, and sometimes more than one additional ply was required, then the extra ply outweighed the benefits.

[hgm]

I don't understand this remark. In alpha beta search I think about side to move and side not to move. at one level it's white, at the next level it's black. This check test I talk about is done at every level.

When talking about negamax, I always think from the stm point of view. So own king is that of the stm, enemy king is that of the side not to move.

[mcostalba]

My suggestion involves searching positions in which the king is in check. Thus one of the "legal" replies will be capturing the king, and when that move is searched, the first thing that happens is that the next occurrence of alphaBeta() will say Hey! this guy has no king, and return an extreme eval without considering any replies.

What if THAT move is the fourth or fifth tried on that node ?

The position is illegal (because opponent king is under check) but you don't know it. Then, for instance, generate captures and start try them and after 4-5 moves you finally generate the king capture and discover position is illegal.

I would say really too late, you have spent time searching moves possibly at big depth for nothing.

[bob]

OK, it has been suggested that my current method of making sure the king is not exposed to check is very inefficient. In my current setup, the last thing that moveGen does with every candidate move, before it is searched, is run an issquareAttacked method on the king in the resulting position.

So I've been thinking this over, and it occurs to me that all I need to do is remove this check check from MoveGen, and add a line at the beginning of alphaBeta() that determines whether or not the side to move in the current node has a king. If the answer is no, then return an appropriately extreme value. Sound ok?

Anyways, it's a simple idea, I could just try it, but I thought I'd bounce it off the board, such questions usually generate interesting discussion. The idea is intuitive enough that if it is correct, then I imagine it is probably de rigeur.

The main idea is "never do now what you can defer to later, because with alpha/beta, "later" may never come (if you get a cutoff). So no, do as little as possible when generating, and then only check for legality at the point where you are really ready to search the move. I've always done it this way because of the performance advantage.

[bob]

OK, so you were talking about your own King.

In micro/Max I do it more or less as you proposed, except that I do´t realy do a check for presence of a King in the daughter node, but I do a check for capture of the King when generating the moves. This is actually a much easier test, and wen neither side has more than one King, it is equivalent.

Disadvantage is that you do catch illegal moves quite late.

In Joker I do not generate moves that expose my King in the first place. This saves time both in generation and on checking them. Before MoveGen I determine which pieces are pinned, starting from the enemy sliders (which are at most 5). And then I exclude those pinned pieces from move generation (except along the pin line). I only have to check King moves for legality (and an occasional e.p. capture).

Only when I am in check by a distant checker I screen all moves for legality (by testing if they end on the check ray). For contact checks I selectively generate captures of the checker, and then try only King moves (which need legality testing, like always). I do the occasional legality testing not during MoveGen, but during MakeMove.

There are issues with null-move and searching illegal moves. You don't want to leave your own king in check, and then flip sides and do a null-move search, as the result will be bogus and can cause search problems.

[Fguy64]

My suggestion involves searching positions in which the king is in check. Thus one of the "legal" replies will be capturing the king, and when that move is searched, the first thing that happens is that the next occurrence of alphaBeta() will say Hey! this guy has no king, and return an extreme eval without considering any replies.

What if THAT move is the fourth or fifth tried on that node ?

The position is illegal (because opponent king is under check) but you don't know it. Then, for instance, generate captures and start try them and after 4-5 moves you finally generate the king capture and discover position is illegal.

I would say really too late, you have spent time searching moves possibly at big depth for nothing.

Well, I did end up doing move ordering so that any king captures are evaluated first, if that makes a difference.

anways all these replies will require some thought. I'll come back to this.

[hgm]

There are issues with null-move and searching illegal moves. You don't want to leave your own king in check, and then flip sides and do a null-move search, as the result will be bogus and can cause search problems.

Indeed, in micro-Max this initially was a big problem, and precluded me from using check extension: you could end up in positions where both Kings were in check, leading to infinite recursion and stack overflow.

But I finally used the same solution as Fred. By redesignng micro-Max' QS, so that it would silp in an extra iteration before the QS iteration, which would never search moves, but use their MVV/LV value as score, and suppress any cutoffs in that iteration except on King capture, illegal branches are prned without searchin any further moves beyond the illegal one.

This is also done before null move, which is not searched before the one-ply iteration that comes after the QS iteration. (So no null move in QS.)

[mcostalba]

My suggestion involves searching positions in which the king is in check. Thus one of the "legal" replies will be capturing the king, and when that move is searched, the first thing that happens is that the next occurrence of alphaBeta() will say Hey! this guy has no king, and return an extreme eval without considering any replies.

What if THAT move is the fourth or fifth tried on that node ?

The position is illegal (because opponent king is under check) but you don't know it. Then, for instance, generate captures and start try them and after 4-5 moves you finally generate the king capture and discover position is illegal.

I would say really too late, you have spent time searching moves possibly at big depth for nothing.

Well, I did end up doing move ordering so that any king captures are evaluated first, if that makes a difference.

Also before TT move ?

[hgm]

If King captures are considered first in the static move ordering in absence of a hash move, the hash move can only be a King capture when a King capture is possible, not?

Micro-Max, when asked to search a position where it can capture the King to depth d=N when it has a hash hit on a position with draft d<N would start searching the hash move at depth d+1, which would always be the King capture.

In fact I immediately upgrade the depth of any King capture to d=98, before storing it in the hash, so I guess even the above could not happen in the current version: a lower bound of +INF (= King-capture score) plus a draft of 99 would always produce a sufficient-depth hit with OK bounds for any window, so the node would return without generating or searching moves. I cannot do that in versions that use depth-preferred hashing (with which I sometimes experiment), as the whole depth-preferred table would be poisoned by d=98 King capture engines which would never go away.

[Fguy64]

My suggestion involves searching positions in which the king is in check. Thus one of the "legal" replies will be capturing the king, and when that move is searched, the first thing that happens is that the next occurrence of alphaBeta() will say Hey! this guy has no king, and return an extreme eval without considering any replies.

What if THAT move is the fourth or fifth tried on that node ?

The position is illegal (because opponent king is under check) but you don't know it. Then, for instance, generate captures and start try them and after 4-5 moves you finally generate the king capture and discover position is illegal.

I would say really too late, you have spent time searching moves possibly at big depth for nothing.

Well, I did end up doing move ordering so that any king captures are evaluated first, if that makes a difference.

Also before TT move ?

Well, I don't have a TT (transposition table) yet. But in the absence of a full understanding of the issues involving TT and my idea, it makes sense to me intuitively to place a king capture before all other moves, so that the original move that leaves the king in check is repudiated as soon as possible.