Checkmate

This is a discussion on Checkmate within the General AI Programming forums, part of the Cprogramming.com and AIHorizon.com's Artificial Intelligence Boards category; I haven't been able to find any web pages telling how to determine wether or not a checkmate or stalemate ...

  1. #1
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735

    Checkmate

    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

  2. #2
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    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...
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    34
    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.
    -gunder

    if (problem)
    postcount++;

  4. #4
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    Think about if it is better to always check for mate or to search one ply deeper. What consumes more processing time?
    Bobby Fischer Live Radio Interviews http://home.att.ne.jp/moon/fischer/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Checkmate!
    By FearOfTheDark in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 04-20-2003, 06:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21