Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one (checkmate).

The assumption is that the other player stops playing after the inputted position and only one player plays from there on.

My initial assumption is that simply bfs might help, but I don't think this should give the minimum number of moves always. Just wondering is this an well known problem? then how to solve it?

share|improve this question
1  
BFS will give you the optimal number of moves, but the tree you have to traverse with BFS is going to be huge since you have a lot of possible moves in each steps, at least if there is many pieces left. –  utdiscant Sep 23 '12 at 6:51
2  
BFS will give the minimal number of moves, because it examines all the positions that can be reached in one move, then all the positions that can be reached in two moves, and so on in order. –  MJD Sep 23 '12 at 6:52
add comment

1 Answer

If you are seeking a helpmate from a given chess position, then breadth-first search (BFS) will be able to find one in the minimum number of moves. It "looks at" each position at depth $1$, then depth $2$, and so on. As soon as it finds a win, it can return the result, and it is guaranteed to be at least equal best.

  • If there was a strictly shorter win, the algorithm would have already returned it, and exited.
  • There might be alternative wins at that depth (if the user is also interested in these, the algorithm can keep running until it's finished at that depth).

Note that BFS will often have impractically large memory requirements (perhaps storing all possible positions at depth $d$). A way around this is to use an iterative deepening depth-first search: i.e., we run depth first search to depth $1$, then if no helpmate is found, we run depth first search to depth $2$, and so on.

This repetition might seem wasteful, but if the branching factor is large (which it often is in chess), running DFS for depths $1,2,\ldots,d$ comprises only a small portion of the time, compared to running DFS for depths $1,2,\ldots,d+1$.

(If you (or the reader) is after a forced checkmate see Minimax.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.