The Chess players among you have another opportunity to excel this month. Back in 1995 (have I really been writing this column for that long?), we had a Challenge that required readers to identify all possible chess positions from a given board position. Gary Beith won that Challenge, and you might want to refer back to his solution when thinking about this month’s problem, which invites you to solve the chess end game.

This month’s problem is formulated as a C++ class. The prototype for the code you should write is:

typedef enum {
  kEmpty=0, kPawn, kKnight, kBishop, kRook, kQueen, kKing
} ChessPiece;

typedef enum {
  kNone=0,kWhite=1, kBlack
} Player;

typedef struct Square {
  ChessPiece piece;
  Player player;
} Square;

typedef struct PieceLocation {
  char row;
  char col;
} PieceLocation;

typedef Square Board[8][8];
  /* indexed as [row][col] */
  /* white start row is 0 */
  /* columns numbered left to right viewed from row 0 */

typedef struct ChessMove {
  Board board;
    /* board before move is made */
  Player playerMoving;
    /* which player is making this move */
  PieceLocation pieceBeingMoved;
    /* which piece is being moved */
  PieceLocation destination;
    /* where is pieceBeingMoved being moved to */
  ChessMove *alternativeMove;
    /* list pointer for alternative moves by playerMoving;
      NULL if no more alternatives */
  ChessMove *subsequentMove;
    /* subsequent move in this move tree, made by opponent to playerMoving,
      NULL if no subsequent move is possible */
  bool moveIsCapture;
    /* true if this move is a capture */
  bool moveIsCheck;
    /* true if this move places the opponent in check (but not mate) */
  bool moveIsMate;
    /* true if this move mates the opponent */
  bool moveIsPromotion;
    /* true if this move promotes a pawn at the 8th rank */
  ChessPiece pieceAfterPromotion;
    /* valid only if moveIsPromotion is true, set to value of new piece */
} ChessMove;

class EndGame {
  Board board;
  ChessMove *initialMove;
  /* add other private members as you see fit */
public:
  EndGame(Board initialBoard, Player playerToMove);
    /* your constructor code goes here */
  ~EndGame(void);
    /* your destructor code goes here */
  ChessMove *Solve();
    /* your code goes here */
    /*return moveTree; */
};

The constructor for your EndGame class is provided with the initial board configuration (board) and the identity of the player who moves first (playerToMove). When your Solve method is called, your job is to choose an initial move that leads to checkmate in the minimum number of moves possible. You also need to compute the possible opposing moves with which the other player might respond, and your response to each of those moves, and so on, until each branch of the tree results in checkmate.

Either your constructor or the Solve routine should allocate storage for your first move (moveTree). The ChessMove structure contains the board configuration prior to making the move, the identity of the player making the move, the location and destination of the piece being moved, and some boolean values indicating the results of the move. It also contains a pointer to the next ply of the move tree (subsequentMove), and a pointer to alternative moves in the current ply (alternativeMove). The former contains moves made by the opposing player in response to this move, while the latter contains other moves that could be made by the current player instead of this move. Together, they allow you to describe the entire move tree.

Your destructor needs to free any memory allocated for the ChessMove data structure.

In calculating moves, you can assume that any castling that might take place has already done so. You can also ignore the possibility of en passant pawn moves. You do need to consider the possibility of promoting a pawn by moving it to the 8^th rank of the board. The ChessMove data structure makes provision for specifying the type of the promoted piece.

The winner of this Challenge will be the entry that correctly solves all test cases in the least amount of execution time. Correctness means identifying all moves in the move tree, and guaranteeing checkmate in the minimum number of moves. Timing will include the constructor, a call to your solve routine, and a call to your destructor for a sequence of boards. I am eliminating the subjective evaluation factor for this Challenge because of questions about fairness, but both readers and I appreciate code that is clear and well commented.

This will be a native PowerPC Carbon C++ Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X.

Test code for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 15th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".