Not logged inRybka Chess Community Forum
Up Topic The Rybka Lounge / Computer Chess / How to check for checkmate/stalemate programmatically?
- - By Valentin (*) Date 2008-11-22 12:01

I have a chessboard represented by byte array of length 64.
I need to check for checkmate/stalemate condition.
All ideas how to do this welcome!
Thanks in advance!
Parent - - By Vempele (Silver) Date 2008-11-22 12:23 Edited 2008-11-22 12:25
The simplest approach is to generate pseudolegal moves and see if there are any that don't leave you in check after makemove().
Parent - - By Valentin (*) Date 2008-11-22 12:36
    Does pseudolegal mean legal? If so, the idea is sound.

(if there_is_no_legal_moves)&&(my_king_is_under_check) =>player is checkmated
(if there_is_no_legal_moves)&&(my_king_is_not_under_check) => stalemate

The question here is how to implement check there_is_no_legal_moves() function in an effective way.
Checking every piece on board for a move it can make is not effective.
Parent - - By Vempele (Silver) Date 2008-11-22 12:58 Edited 2008-11-22 13:06

> Does pseudolegal mean legal?

Legal unless it leaves the king in check (hence pseudo).

> Checking every piece on board for a move it can make is not effective.

Fine. My engine does it like this:
1. Detect pins by looping over the opponent's slider list (I actually update them incrementally in makemove; it's a bit faster in perft) and disable the pinned pieces.
Now you only need to check king moves and en passant for legality.
2a. If not in check: if a pinned piece can move along its pin ray, it obviously isn't a stalemate.
3a. If not in check, generate the rest of the moves normally.
3b. Else if not in double-check, iterate over the checking ray to see if any of your pieces can block the check or capture the checking piece.
4. Generate king moves, checking whether the destination square is attacked.
4a. If in check, make sure you aren't moving away from a checking slider.

Stop at the first move found, of course.

Alternatively, you could do the pin test for each of your pieces individually; this is probably the fastest way if you don't have pin data handy.
Parent - By Valentin (*) Date 2008-11-22 14:31
Thank you VERY much.
Parent - - By Uly (Gold) Date 2008-11-22 23:28

>> Fine. My engine does it like this:

Vempele, is your engine private?
Parent - - By zwegner (***) Date 2008-11-22 23:43
And is it really named goaT? Also, is it bitboard?
Parent - By Vempele (Silver) Date 2008-11-23 09:35
It's private and 16x14 mailbox.

>And is it really named goaT?

Yes. Its original name was Placeholder, which, I think, proves that I suck at naming things. :)

I'll release it sometime between implementing DTS and coming up with a good parameter for how many search threads to use. I'm currently thinking "Processing power" as a percentage, so that e.g. 1 <thingy> on a quad would be 25%. It'd require some way to detect hyperthreading, though.

Perhaps a logarithmic scale would be better? :-p
Parent - - By h.g.muller (****) Date 2008-11-23 08:22

> Checking every piece on board for a move it can make is not effective.

It is actually more effective than you think, as in almost all positions in a search tree you can stop after the first move of the first piece that you find (after checking it was legal). Because as soon as you have found one legal move, you know it is neither checkmate nor stalemate. Only in the case where you are really stalemated, there is no way to know it without checking every pseudo-legal move of every piece. But this is unavoidable (although a little work can be saved by recognizing pins, and not try moves that stray from the pin line). Fortunately stalemates tend to occur only when you have very few pieces. You could refrain from doing it above a certain number of pieces, without any measurable consequence on the strength of an engine.

For checkmates the main filter is that you should be in check. If this is the case, you might have no legal moves despite the fact that you have many pieces. In theory you could limit move generation now to moves that explicitly resolve the check: move the King, capture the checker (not possible with double check), or interpose (not possible with double or contact checks). I could not find a time-saving algortithm for selectively generating interpositions in my non-bitboard engine. But I can selectively generate moves to a single square (to capture the checker) more efficiently than generating all moves. (By running through the piece list and doing an attack test.) So I do recognize contact checks and double checks, to use the more efficient move generation there. Only in the case of a single distant check I generate all moves, and test if they interpose / capture the checker.

Note that all this is only important for detecting mates in leaf nodes. In an internal node, you can afford to stumble on them 'by surprise', as mates are rare in the tree, and in 99.9% of the cases you would want to generate all moves anyway. So algorithms that generate all moves do not cause much overhead.
Parent - - By Valentin (*) Date 2008-11-28 19:56
Big thanks for answering my question, Mr muller.
    As you noted, it is more effective to check for stalemate condition using pins.
I must say that it really cuts time of performing full stalemate check.Without strict measurements, it seems that stalemate check performed by generating all possible "pseudolegal" moves and rejecting everyone of them takes 10 to 20 times more time than check using more clever algorithm checking for pins and blocked pieces.
    Quite a question for me now is a shortcut on checking if a piece can defend a king from long-distance check jumping at a square between the attacking piece and attacked king. Advice welcome & greatly appreciated.
Thanks for effort & your time.
Parent - By h.g.muller (****) Date 2008-12-04 09:44
In my engine Joker I have no special code for check evassion of distant checks. I simply generate all moves, and test them one by one for interposition or capture of the checker. For this I use the step-vector table of the 0x88 test: this tabulates the direction as a function of the difference between from and two-square. Once I detect a distant check, I rememmber stepVector[checker-myKing], and for every generated move I compare this with stepVector[toSquare-myKing]. If they are the same, I know that the move lands somewhere on the check ray, on the right side of the King. I still should check if it is between King and checker. For this I compare it with stepVector[checker-toSquare].

In principle this could be made faster, at the expense of a bigger table. There is very little to gain, though, as checks are rare in the tree. So whatever you do in in-check nodes, it hardly affects overall performance.

What you could do is make tables indexed by the difference between piece position and King position, one for each check direction and piece type. When you detect the distant check you will know the direction. You can then run through your piece list, and  use the piece type and location (fromSquare) of every piece to consult the table, which then contains a list of squares (relative to King) where a piece of that type could interpose. (This can be upto 3 squares, for a Queen.) For sliders you would then still have to make a ray-scan to see if they can actually get there. But in generating moves you would do such a scan for all directions, rather than just those which lead to an interposition square. And you don't have to test every square on the way for being an interposition in this new method, you only test he possible interposition squares themselves for being in between King and checker.
Up Topic The Rybka Lounge / Computer Chess / How to check for checkmate/stalemate programmatically?

Powered by mwForum 2.27.4 © 1999-2012 Markus Wichitill