# List number of moves to defeat the opponent

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?

-
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
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

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.
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$.