views:

53

answers:

1

I am writing a program that play Checkers against human, with a min-max game tree. Everything went fine until facing a problem. Here is the scenario described as an illustration.

->Let X be a black cell, 0 be an empty cell, B be a black stone and W be a white stone; ->The board is showed as follows;

| X | B | X | B | X | B | X | B | X |

| W | X | B | X | B | X | B | X | B |

| X | 0 | X | 0 | X | 0 | X | 0 | X |

| 0 | X | 0 | X | 0 | X | 0 | X | 0 | 

( and there is no stone underneath)

-> It is White players turn and white player does not any moves to play. He/she only have one stone and it got stuck.

What is the outcome of this game, i.e. who wins and who loses. Should I declare a draw? How can I solve this deadlock? Is there any official reference that states a rule for this kind of deadlock?

Thank you very much.

+3  A: 

According to this site:

http://boardgames.about.com/cs/checkersdraughts/ht/play_checkers.htm

13 A player wins the game when the opponent cannot make a move. In most cases, this is because all of the opponent's pieces have been captured, but it could also be because all of his pieces are blocked in.

So I guess in such a situation, the black would be a winner since all of the white's pieces are blocked.

I have never messed with min-max trees, how ever, you might check to see if the at least one of the pieces that a side has, either black or white, has one possible move, ie. a child. If no nodes have children, then, it would mean that no moves can be done, thus, the opposing side has won the game.

npinti