Checkmate

[MadCow257]

I haven't been able to find any web pages telling how to determine wether or not a checkmate or stalemate has occured. Can anyone help me with this? BTW I'm using the bitboard representation. I could probably come up with something hackish on my own, but I need this to be optimized as it will probably be the number 1 called function in my program.

Thanks,
-MC

[IfYouSaySo]

You really should probably try to write it yourself first. And then look at the source code to Crafty:

http://www.cis.uab.edu/info/faculty/hyatt/hyatt.html

Here's how I would guess it's written:

Firstly the conditions for checkmate are:
a) King is in check
b) King can't move out of check.
c) Check can't be blocked
d) checking piece can't be captured

So the main key is having a function that determines if the king is in check. We could do this as follows:

1) Generate a bitboard that is the bitwise AND of all the opponent's pieces attack boards.
2) AND that board with the location of the king, if the result is non-zero, then the king is in check.

Next you need to generate all pseudo-legal moves (meaning we don't look at if we're moving into check or if the resulting position leaves us in check), and as a heuristic we do it in the following order:
1) all king moves first
2) all captures next
3) other moves last

Then since we're using alphabeta (presumably) the other side will go into the evaluate function, and if we left the king in check in the previous step, then it will see that it can capture the king on this move (using the in-check test from above). In that case return some very large number (or very small number, as the case may be).

If all legal moves leave the king in check, then you have your answer. It's checkmate. This should even handle double checks, discoveries, smothered mates, etc.

Let me know if you find crafty's way to be significantly different. It would be interesting to know, and eventually I'll be writing my own game, after I finish connect four, and then probably checkers, gin, hold'em, and finally maybe chess...

[gunder]

I have quite a few articles at home about chess programming. I havn't looked at them all in depth but I'm sure some of them will have some info on this. If you'd like I can take a look later and upload them.

[fischerandom]

Think about if it is better to always check for mate or to search one ply deeper. What consumes more processing time?