I want to revive this old thread about the king capture problem
(actually it's subject was 'move generation'):

Mike Gleason Jr Couturier wrote:
I'm creating a chess engine and I have one question
concerning pseudo-legal moves...

A lot of people are not checking if a move leave the king
in check while generating their moves.. They say it is better
to delay the validation when you are searching... Because
you maybe will never have to search for a move in the list
so you don't have to know in advance if the move is legal...

1. How this is done ? I use alpha-beta...
Is it : if the score returned by a move is alpha, I then check
if the move don't leave the king in check.. if so, we can continue
with the search, else we invalidate the move.

2. How can I invalidate the move while searching ? (ie.: it
leaves the king in check) ? We just return beta ?

There are several ways to solve this problem, but one way is to simply
return a sufficiently low score when the side to move's king is gone. A
return of -INFINITY should take care of the problem. -INFINITY should
never be greater than alpha so no move with that score will be used in
any variation. The problem comes when you run into a case where no move
gets a score -INFINITY. Are you currently in check/stalemate or did
it happen down the line somewhere? You can help this problem a bit by
adding the ply to the score when you are returning -INFINITY. Or you
can simply resign.

Legal moves are easier to deal with, but cost more to generate. This is
why many chess engines don't check for king safety during generation
unless the king is currently in jeaprody. Having the king missing as a
score of -INFINITY really helps, but you have to decide what to do in
hopeless situations.

You can also simply have the king's value sufficiently high that its
loss creates a score beneath a certain point. The problem I ran into
with this solution is that in hopeless situations the engine will pick
the line that has the greatest value - not necissarily a legal line.
For instance if you pin a rook to the king, and that rook could take
your queen if it wasn't moving into check, and the engine realizes that
you are going to beat it anyway...well it makes the capture because the
value of that line is than if it didn't.

You see the problem is I don't see how this could work: the king
capture problem has been on my mind for a couple of days and I think
forward pruning (checking for being in check after do_move, if yes:
undo_move and continue with next move, etc.) is the *only* way to deal
with this: Both kings can be captured at the leaves without the
evaluation function transferring a very big positive or negative value
back to the node. Anyone else any thoughts about how to cut-off king
captures?


I am also a relative beginner, but it seems to me that most engines that
use pseudo-legal moves have some variation of the above. Simply make
the loss of the king so outrageous that the engine will do everything it
can to stop it. This works flawlessly until the moment of hopelessness
where you must decide what your engine will do.


Thank you very much !!

pd42 wrote:
I want to revive this old thread about the king capture problem
(actually it's subject was 'move generation'):

Mike Gleason Jr Couturier wrote:
I'm creating a chess engine and I have one question
concerning pseudo-legal moves...

A lot of people are not checking if a move leave the king
in check while generating their moves.. They say it is better
to delay the validation when you are searching... Because
you maybe will never have to search for a move in the list
so you don't have to know in advance if the move is legal...

1. How this is done ? I use alpha-beta...
Is it : if the score returned by a move is alpha, I then check
if the move don't leave the king in check.. if so, we can continue
with the search, else we invalidate the move.

2. How can I invalidate the move while searching ? (ie.: it
leaves the king in check) ? We just return beta ?

There are several ways to solve this problem, but one way is to simply
return a sufficiently low score when the side to move's king is gone. A
return of -INFINITY should take care of the problem. -INFINITY should
never be greater than alpha so no move with that score will be used in
any variation. The problem comes when you run into a case where no move
gets a score -INFINITY. Are you currently in check/stalemate or did
it happen down the line somewhere? You can help this problem a bit by
adding the ply to the score when you are returning -INFINITY. Or you
can simply resign.

Legal moves are easier to deal with, but cost more to generate. This is
why many chess engines don't check for king safety during generation
unless the king is currently in jeaprody. Having the king missing as a
score of -INFINITY really helps, but you have to decide what to do in
hopeless situations.

You can also simply have the king's value sufficiently high that its
loss creates a score beneath a certain point. The problem I ran into
with this solution is that in hopeless situations the engine will pick
the line that has the greatest value - not necissarily a legal line.
For instance if you pin a rook to the king, and that rook could take
your queen if it wasn't moving into check, and the engine realizes that
you are going to beat it anyway...well it makes the capture because the
value of that line is than if it didn't.

You see the problem is I don't see how this could work: the king
capture problem has been on my mind for a couple of days and I think
forward pruning (checking for being in check after do_move, if yes:
undo_move and continue with next move, etc.) is the *only* way to deal
with this: Both kings can be captured at the leaves without the
evaluation function transferring a very big positive or negative value
back to the node. Anyone else any thoughts about how to cut-off king
captures?


That isn't possible if you do this correctly. When generating moves and
you capture a king, you return a special result that says "this position is
illegal because I just captured your king." Any such position will always
be illegal. And I don't give you a chance to capture mine back...




I am also a relative beginner, but it seems to me that most engines that
use pseudo-legal moves have some variation of the above. Simply make
the loss of the king so outrageous that the engine will do everything it
can to stop it. This works flawlessly until the moment of hopelessness
where you must decide what your engine will do.


Thank you very much !!


--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170

"Robert Hyatt" wrote:
pd42 wrote:
I want to revive this old thread about the king capture problem
(actually it's subject was 'move generation'):

Mike Gleason Jr Couturier wrote:
I'm creating a chess engine and I have one question
concerning pseudo-legal moves...

A lot of people are not checking if a move leave the king
in check while generating their moves.. They say it is better
to delay the validation when you are searching... Because
you maybe will never have to search for a move in the list
so you don't have to know in advance if the move is legal...

1. How this is done ? I use alpha-beta...
Is it : if the score returned by a move is alpha, I then check
if the move don't leave the king in check.. if so, we can continue
with the search, else we invalidate the move.

2. How can I invalidate the move while searching ? (ie.: it
leaves the king in check) ? We just return beta ?

There are several ways to solve this problem, but one way is to simply
return a sufficiently low score when the side to move's king is gone.
A
return of -INFINITY should take care of the problem. -INFINITY should
never be greater than alpha so no move with that score will be used in
any variation. The problem comes when you run into a case where no
move
gets a score -INFINITY. Are you currently in check/stalemate or did
it happen down the line somewhere? You can help this problem a bit by
adding the ply to the score when you are returning -INFINITY. Or you
can simply resign.

Legal moves are easier to deal with, but cost more to generate. This
is
why many chess engines don't check for king safety during generation
unless the king is currently in jeaprody. Having the king missing as a
score of -INFINITY really helps, but you have to decide what to do in
hopeless situations.

You can also simply have the king's value sufficiently high that its
loss creates a score beneath a certain point. The problem I ran into
with this solution is that in hopeless situations the engine will pick
the line that has the greatest value - not necissarily a legal line.
For instance if you pin a rook to the king, and that rook could take
your queen if it wasn't moving into check, and the engine realizes that
you are going to beat it anyway...well it makes the capture because the
value of that line is than if it didn't.

You see the problem is I don't see how this could work: the king
capture problem has been on my mind for a couple of days and I think
forward pruning (checking for being in check after do_move, if yes:
undo_move and continue with next move, etc.) is the *only* way to deal
with this: Both kings can be captured at the leaves without the
evaluation function transferring a very big positive or negative value
back to the node. Anyone else any thoughts about how to cut-off king
captures?


That isn't possible if you do this correctly. When generating moves and
you capture a king, you return a special result that says "this position
is
illegal because I just captured your king." Any such position will always
be illegal. And I don't give you a chance to capture mine back...



I understand that it can be done during move generation and do_move, (so
forward pruning). However, I don't want to detect king capture during move
generation but use the return value of AlphaBeta, because I think it would
be
faster if it can be done...
BTW I am using an offsett board representation (first program), and testing
for
checks or king captures in do_move or the move generator can be costly.

You see the problem is I don't see how this could work: the king
capture problem has been on my mind for a couple of days and I think
forward pruning (checking for being in check after do_move, if yes:
undo_move and continue with next move, etc.) is the *only* way to deal
with this: Both kings can be captured at the leaves without the
evaluation function transferring a very big positive or negative value
back to the node. Anyone else any thoughts about how to cut-off king
captures?
That isn't possible if you do this correctly. When generating moves and
you capture a king, you return a special result that says "this position
is
illegal because I just captured your king." Any such position will always
be illegal. And I don't give you a chance to capture mine back...

I understand that it can be done during move generation and do_move, (so
forward pruning). However, I don't want to detect king capture during move
generation but use the return value of AlphaBeta, because I think it would
be
faster if it can be done...
BTW I am using an offsett board representation (first program), and testing
for
checks or king captures in do_move or the move generator can be costly.

You should distinguish a King capture with other pieces' captures. The
main difference is that a King capture is ALWAYS a leaf of search tree
when normal captures can be leaves or inter nodes. Kings are special
pieces, the game should stop right when any one of them is taken out.
It means that after capturing a King, you should stop searching
immediately, otherwise, you may see the exchange of Kings (both Kings
are captured as you mentioned). Thus, you should not avoid detecting
King captures (or checks) somewhere in search (usually after DoMove or
in Generator).

BTW, IMO, there are several ways to do King capture/check detector...
but all that work (in case of perfect design and implementation) may
help you to speed up maximun 1-3% or add to your engine maximun 1 elo
(compare with popular and good techniques). Thus, it may be better if
you quickly select one design, implement it, find and fix all bugs and
then focus on other and more important things such as fixing bugs on
other parts, evaluation, move ordering...

Good luck
Pham

Thanks Pham, you confirm what I was afraid of.
After activating the last line below in AlphaBeta:

for (i = 0; i mov.size(); i++) {
do_move(mov, i);
// if (in_check(side)) { undo_move(mov, i); continue; }

.... the search is 1.2% slower, so it's not that bad.
The in_check function scans all attack lines to the King