efficient in_check routine

Main

Date: 19 Jan 2007 11:34:05
From: Loomis Philanthrope
Subject: efficient in_check routine

Hi all,

I am trying to write an efficient routine to determine whether the king
is in check. Any ideas you know of are welcome.

I am using the 0x88 board representation. My current method is to loop
over the opponents pieces and use the difference between the king square
the the piece square as an index into an array that tells me if the
piece could attack the king from that square. Then for sliding pieces I
traverse the direction of attack to see if all the squares between are
empty. Then I check the two squares where pawns could attack from to see
if they're occupied by opponents pawns.

Is there a more efficient way to do this? My understanding is that
bitboards make this kind of thing faster. I don't have the time to
implement a full bitboard representation, but would it be worth it to
store a couple bitboards just for this purpose? For example, a bitboard
of occupied squares might make checking whether sliding pieces are
blocked faster.

Thanks,
Loomis

Date: 19 Jan 2007 13:45:41
From: Mr. Question
Subject: Re: efficient in_check routine

"Loomis Philanthrope" <[email protected] > wrote in message
news:[email protected]...

> I am using the 0x88 board representation. My current method is to loop
> over the opponents pieces and use the difference between the king square
> the the piece square as an index into an array that tells me if the piece
> could attack the king from that square. Then for sliding pieces I traverse
> the direction of attack to see if all the squares between are empty. Then
> I check the two squares where pawns could attack from to see if they're
> occupied by opponents pawns.

That's not too bad of a way, although if you use piece lists, you can cut
out some of the board scanning.

> Is there a more efficient way to do this? My understanding is that
> bitboards make this kind of thing faster. I don't have the time to

Yes, this is one area where bitboards can be faster. Notice I said 'can
be'...

Bit boards can be faster in one area but slower in another. As a whole,
they aren't necessarily better, just different.

They have different strengths and different weaknesses.

There are a lot of very clever advances in bitboards these days. Gerd and
some of the others in the TalkChess & WinBoard forums have developed new
ways to do attack detection and move generation and so on. Very clever
stuff.

The days of having to use the 'classic' method or even the 'rotated' methods
are over.

But it can still be a pain to work with bitboards.

> implement a full bitboard representation, but would it be worth it to
> store a couple bitboards just for this purpose? For example, a bitboard

Probably not. That's just yet more information to update with every move.

> of occupied squares might make checking whether sliding pieces are blocked
> faster.

Some people have done hybrid programs. But it can be tedious to mesh
together the two well.

If you are going to go bitboards, then it's usually better to just go all
the way. Many still have a 64 element mailbox board just so they can easily
get a piece type or something, but most prefer to go all the way.

But doing bitboards really requires a change in thinking.

Now, having said all of that, the reality is that you rarely need to do
incheck detection.

Only when you generate castling moves (or make them, if you'd rather do it
that way), and when there aren't any legal moves, so you can tell the
difference between checkmate & stalemate.

Most of the time you don't need incheck(). (Note that the infamous perft
tests heavily use it, but that's not representative of a real search. Perft
behaves very differently and should only be used as a way to check your move
logic to make sure things are working.)

Most people just generate pseudo-legal moves and let the search figure it
out if the move is ever actually made.

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Date: 19 Jan 2007 15:31:48
From: Loomis Philanthrope
Subject: Re: efficient in_check routine

Mr. Question wrote:
> "Loomis Philanthrope" <[email protected]> wrote in message
> news:[email protected]...

> Now, having said all of that, the reality is that you rarely need to do
> incheck detection.
>
> Most of the time you don't need incheck(). (Note that the infamous perft
> tests heavily use it, but that's not representative of a real search. Perft
> behaves very differently and should only be used as a way to check your move
> logic to make sure things are working.)
>
> Most people just generate pseudo-legal moves and let the search figure it
> out if the move is ever actually made.

My move generator doesn't check whether it generates legal moves. But my
make_move function will return false for an illegal move (so that I can
remove it from the list). I think this is necessary for me. I tried
various things allowing illegal moves but making them evaluate as very
poor, but nothing quite worked right. I don't like that there is the
possibility of illegal moves, inevitably, my engine will try to make one
;-).

Loomis

Date: 19 Jan 2007 22:47:02
From: Mr. Question
Subject: Re: efficient in_check routine

"Loomis Philanthrope" <[email protected] > wrote in message
news:[email protected]...

> My move generator doesn't check whether it generates legal moves. But my
> make_move function will return false for an illegal move (so that I can

Some people do the valid castling incheck stuff there, but I don't think
many do.

> remove it from the list). I think this is necessary for me. I tried
> various things allowing illegal moves but making them evaluate as very
> poor, but nothing quite worked right. I don't like that there is the
> possibility of illegal moves, inevitably, my engine will try to make one
> ;-).

I can understand that feeling. I've written a few chess programs over the
years and I often included a few extra checking things just to make sure my
program wouldn't do something stupid.

Basically though, all the search routine has to do is:

1) see if the king is being captured. If it is, then immediately return an
'invalid move' score to the previous level. This can be done either in
MakeMove() or the search. Where ever convenient.

2) If the search has returned an 'illegal move' score, then you know that
the move you just tried was illegal.

3) If the best score ends up being 'illegal move' (meaning there were no
legal moves, else the score would be something else) then you know you are
either in stalemate or checkmate. Then you can do InCheck().

There are a few other complications, of course, depending on whether you
generate all the moves or just some of them, but the key is that capturing
the king will result in an immediately returned absolute worst possible
score.

Still, there are lots of ways of doing a chess program. Whatever makes you
happy is all that really counts.

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Date: 19 Jan 2007 16:40:50
From: Gian-Carlo Pascutto
Subject: Re: efficient in_check routine

Loomis Philanthrope wrote:
> Hi all,
>
> I am trying to write an efficient routine to determine whether the king
> is in check. Any ideas you know of are welcome.
>
> I am using the 0x88 board representation. My current method is to loop
> over the opponents pieces and use the difference between the king square
> the the piece square as an index into an array that tells me if the
> piece could attack the king from that square. Then for sliding pieces I
> traverse the direction of attack to see if all the squares between are
> empty. Then I check the two squares where pawns could attack from to see
> if they're occupied by opponents pawns.
>
> Is there a more efficient way to do this?

Remember what the last move was. Determine whether that move could have
put the king in check. No need to look at all pieces.

--
GCP

Date: 19 Jan 2007 13:32:02
From: Mr. Question
Subject: Re: efficient in_check routine

"Gian-Carlo Pascutto" <[email protected] > wrote in message
news:[email protected]...
> Loomis Philanthrope wrote:
>> Hi all,
>>
>> I am trying to write an efficient routine to determine whether the king
>> is in check. Any ideas you know of are welcome.
>>
>> I am using the 0x88 board representation. My current method is to loop
>> over the opponents pieces and use the difference between the king square
>> the the piece square as an index into an array that tells me if the
>> piece could attack the king from that square. Then for sliding pieces I
>> traverse the direction of attack to see if all the squares between are
>> empty. Then I check the two squares where pawns could attack from to see
>> if they're occupied by opponents pawns.
>>
>> Is there a more efficient way to do this?
>
> Remember what the last move was. Determine whether that move could have
> put the king in check. No need to look at all pieces.

Don't forget about special handling for enpassant & promotion moves. Most
people remember the promotions but forget about enpassant, which changes
three squares.

You'll still need a full, general purpose method for castling and other
times.

Most 0x88 programs use piece lists, too. That can speed things up a bit.
But you'll still need to do some grunt work at times. You'll still have to
go through the possible squares and check.

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Date: 19 Jan 2007 15:26:24
From: Loomis Philanthrope
Subject: Re: efficient in_check routine

Mr. Question wrote:
> "Gian-Carlo Pascutto" <[email protected]> wrote in message
> news:[email protected]...
>
>>Loomis Philanthrope wrote:
>>
>>>Hi all,
>>>
>>>I am trying to write an efficient routine to determine whether the king
>>>is in check. Any ideas you know of are welcome.
>>>
>>>I am using the 0x88 board representation. My current method is to loop
>>>over the opponents pieces and use the difference between the king square
>>>the the piece square as an index into an array that tells me if the
>>>piece could attack the king from that square. Then for sliding pieces I
>>>traverse the direction of attack to see if all the squares between are
>>>empty. Then I check the two squares where pawns could attack from to see
>>>if they're occupied by opponents pawns.
>>>
>>>Is there a more efficient way to do this?
>>
>>Remember what the last move was. Determine whether that move could have
>>put the king in check. No need to look at all pieces.
>
>
> Don't forget about special handling for enpassant & promotion moves. Most
> people remember the promotions but forget about enpassant, which changes
> three squares.
>
> You'll still need a full, general purpose method for castling and other
> times.
>
> Most 0x88 programs use piece lists, too. That can speed things up a bit.
> But you'll still need to do some grunt work at times. You'll still have to
> go through the possible squares and check.

I have a general purpose is_attacked() method so that I can check if any
particular square is attacked by one side or the other. That is what I
am currently using to determine move legality.

Thanks for the enpassant reminder! I might have missed that one. In the
technique I am planning, checking whether promotions are legal isn't
different from any other move. Of course, checking whether they deliver
check is.

Yes, I use a piece list and the board array contains pointers to the
piece addresses. That way I can loop over the piece list instead of the
board to do things like generate moves.

Date: 19 Jan 2007 14:16:54
From: Loomis Philanthrope
Subject: Re: efficient in_check routine

Gian-Carlo Pascutto wrote:
> Loomis Philanthrope wrote:
>
>>Hi all,
>>
>>I am trying to write an efficient routine to determine whether the king
>>is in check. Any ideas you know of are welcome.
>>
>>I am using the 0x88 board representation. My current method is to loop
>>over the opponents pieces and use the difference between the king square
>>the the piece square as an index into an array that tells me if the
>>piece could attack the king from that square. Then for sliding pieces I
>>traverse the direction of attack to see if all the squares between are
>>empty. Then I check the two squares where pawns could attack from to see
>>if they're occupied by opponents pawns.
>>
>>Is there a more efficient way to do this?
>
>
> Remember what the last move was. Determine whether that move could have
> put the king in check. No need to look at all pieces.
>

Ok, after reading your source, I have an idea of how to write a more
efficient way to determine whether I have moved into check by moving a
pinned piece. I will do it a bit different from you just to keep the
code simpler (I think I'll sacrifice just a tiny bit of efficiency for
that, but it will still be much better than my current approach).

My current method of determining move legality was just to check
is_attacked() on the king square after every move. If I understand your
code, I still have to do this if I move the king, right? But I can be
more clever if I have moved another piece.

Thanks for your help, this has to be worth at least 3 or 4 ratings
points ;-).

Date: 19 Jan 2007 13:48:03
From: Loomis Philanthrope
Subject: Re: efficient in_check routine

Date: 19 Jan 2007 13:24:30
From: Loomis Philanthrope
Subject: Re: efficient in_check routine

Gian-Carlo Pascutto wrote:
> Loomis Philanthrope wrote:
>
>>Hi all,
>>
>>I am trying to write an efficient routine to determine whether the king
>>is in check. Any ideas you know of are welcome.
>>
>>I am using the 0x88 board representation. My current method is to loop
>>over the opponents pieces and use the difference between the king square
>>the the piece square as an index into an array that tells me if the
>>piece could attack the king from that square. Then for sliding pieces I
>>traverse the direction of attack to see if all the squares between are
>>empty. Then I check the two squares where pawns could attack from to see
>>if they're occupied by opponents pawns.
>>
>>Is there a more efficient way to do this?
>
>
> Remember what the last move was. Determine whether that move could have
> put the king in check. No need to look at all pieces.

It sounds nice on the face of it. But you've left out how to determine
whether the move could have put the king in check. If all I had to do
was check whether the moving piece is now attacking the king, that would
be simple, but I have to consider discovered checks. That means I have
to determine if the moving piece was between the king and any of the
sliding pieces. This doesn't seem any easier than checking all the
pieces to begin with (maybe your idea avoids checking the knights and
pawns).

Most often though I'm using this to determine whether a potential move
is legal. I want to make sure I'm not moving into check. Unless I want
to keep track of whether or not pieces are pinned, I don't see how to
use your idea. And determining for each piece whether it is pinned or
not seems less efficient than just checking if the king is attacked.

If I've missed something that makes your idea work, please let me know.

Loomis