On not leaving the King in check

[Fguy64]

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.

[hgm]

I am not sure if you are talking about your own king or the opponent. Are you doing this for determinig if your moves are legal, or to determine if they should be extended?

[Fguy64]

I am not sure if you are talking about your own king or the opponent. Are you doing this for determinig if your moves are legal, or to determine if they should be extended?

I don't think extension has anything to do with it. It's part of normal MoveGen and searching. Currently my alphaBeta() searches only legal positions, and all legal positions.

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.

[Sven]

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.

I assume you are talking about your implementation of legality check. I think your current solution is not really bad but can be slightly improved. What you are doing is not uncommon: after making a move on the board within the search, you check whether this move left your own king in check. So in fact you are not performing this check during move generation but within search, so you avoid to do unnecessary legality checks for many moves that will never be made on the board due to cutoffs. And it's fine this way.

An optional, small (or perhaps medium) improvement is possible if you restrict the expensive "enemy king in check" test to only those moves which may have any potential to be illegal. A pseudo-legal move is illegal if it either puts the own king into a check that was not present before, or if it does not escape from a check that was given. So you can write a test function that decides whether the move that thas just been made on the board may have been illegal at all, and return "true" if either

- in the previous position, your king had been in check (this requires an "in check" flag per historical position), or
- your move is a king move (with special care about castling), or
- you are moving a pinned piece,

otherwise "false". You probably won't save a lot but it should be measureable.

Your other proposal is not really new, this would turn your engine into something that is well known as "king capture engine". It is possible to do it that way but today most programmers seem to agree that other methods of legality checking are more efficient than "king capture". I skip the details here; to my knowledge one of the key points is that in positions where the king of the moving side is in check, "king capture" is quite inefficient since there are many illegal moves.

Sven

[Sven]

It's part of normal MoveGen and searching. Currently my alphaBeta() searches only legal positions, and all legal positions.

As far as I know, your code looks different, though, it is of the following form:

Code: Select all

int alphaBeta( String pStr, ... ) {
	GENERATE_MOVES( pStr );
	for( "m in ALL MOVES" ) {
		p1Str = MoveGen.checkMove( pStr, m[0], m[1] );
		if( p1Str.equals("false") ) continue;
		// ...

where MoveGen.checkMove() makes the move on the board (pStr) and then finally does the legality check. So you are generating all pseudo-legal moves, and this check is not done for moves that are never made on the board due to a cutoff.

Maybe you have changed this part in the meantime?

Sven

[hgm]

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.

[Fguy64]

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.

I assume you are talking about your implementation of legality check. I think your current solution is not really bad but can be slightly improved. What you are doing is not uncommon: after making a move on the board within the search, you check whether this move left your own king in check. So in fact you are not performing this check during move generation but within search, so you avoid to do unnecessary legality checks for many moves that will never be made on the board due to cutoffs. And it's fine this way.

...

I'll just focus on this one point for now, cause I am not sure we are on the same page. Yes, the final legality check, which deals with epTarget, castling rights, and leaving the king in check, is called from within the iterative loop that is part of the the alphaBeta method, but that call is made before the recursive call, and only the nodes that pass this final legality check get passed to the next depth of search. In that sense, I hadn't considered my final legality check to be "part of search". Does that change your answer?

the following line of code in my search method causes the recursive call to be bypassed

if( p1Str == "false" ) continue;

by changing my current method, that will eliminate a call to isSquareAttacked for every single node generated, and instead rely on the simple test for the existance of a king to do the work.

edit, sorry, make that p1Str.equals(false); anyways, if the final legality check is passed, p1Str is the updated c"cloned position, so I don't exactly make a move then undo it.

[Fguy64]

OK, so you were talking about your own King.

...

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.

[Sven]

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.

I assume you are talking about your implementation of legality check. I think your current solution is not really bad but can be slightly improved. What you are doing is not uncommon: after making a move on the board within the search, you check whether this move left your own king in check. So in fact you are not performing this check during move generation but within search, so you avoid to do unnecessary legality checks for many moves that will never be made on the board due to cutoffs. And it's fine this way.

...

I'll just focus on this one point for now, cause I am not sure we are on the same page. Yes, the final legality check, which deals with epTarget, castling rights, and leaving the king in check, is called from within the iterative loop that is part of the the alphaBeta method, but that call is made before the recursive call, and only the nodes that pass this final legality check get passed to the next depth of search. In that sense, I hadn't considered my final legality check to be "part of search". Does that change your answer?

the following line of code in my search method causes the recursive call to be bypassed

if( p1Str == "false" ) continue;

by changing my current method, that will eliminate a call to isSquareAttacked for every single node generated, and instead rely on the simple test for the existance of a king to do the work.

No, it does not change my answer.

Read carefully. You wrote that you would only search legal moves because your legality check were part of your move generation. I showed that this is not the case since you perform your legality check only for moves that are made on the board, not on all generated moves. That makes the difference. Note that a cutoff often occurs after the first or only very few moves being searched.

Think about it again ...

Maybe you try to implement your idea, solve everything that is caused by doing so - including mate/stalemate detection -, and then compare with the current method to get an idea which way is better.

Please don't forget that with the "king capture" approach, you make an illegal move on the board, generate moves for the new position, make a move that captures the king, and only then detect that the previous move was illegal, which requires a whole ply more than usual in case of an illegal move. Depending on your implementation this could easily outweigh the gain you get by skipping the isSquareAttacked() call for each move that is in fact legal.

Sven

Sven

[Fguy64]

Please don't forget that with the "king capture" approach, you make an illegal move on the board, generate moves for the new position, make a move that captures the king, and only then detect that the previous move was illegal, which requires a whole ply more than usual in case of an illegal move. Depending on your implementation this could easily outweigh the gain you get by skipping the isSquareAttacked() call for each move that is in fact legal.

Sven

ok yes, I can see from this concluding parargraph that we are on the same page. OK, I will take some time to consider all of this, and let you know what comes of it.

thanks again.