Charles Petzold
This is turning out to be a lot harder than I thought it would be."
That's not an uncommon reaction after getting into a new programming project. If everything were as easy as it first seemed, deadlines would be met with no problem. But missing deadlines is a chronic problem in the software industry. The bigger the program, the worse the problem.
Most programs published in books and magazines are very small. The code is intended to show programming techniques in isolation from the often-considerable requirements of real applications. I believe this is perfectly legitimate, because the smaller the code sample is, the more inclined readers are to look at it and learn something from it. Those of us who write these small programs for books and magazines sometimes think that writing a real application is simply a matter of putting all these little techniques together. This is not so.
When the MSJ editors and I began to discuss writing a checkers program for OS/2 Presentation Manager (hereafter "PM"), one of our goals was to show the proper way to assemble a fairly large and complex PM program.
I believe now that that idea is fundamentally wrong. It is one thing to show how to set up parameters for a call to GpiBitBlt-where there can be very little variation in the code-and quite another to show the overall structure of a large program. There is no one right way to write a large program. The lessons to be learned are in the concepts and methodology rather than the execution.
As I'll describe, I have shown one possible solution to structuring CHECKERS, but it is not the only one. Every programmer who might design such a program would probably do it differently, whereas everyone's code to move a piece across the board using GpiBitBlt would probably look pretty much the same.
The New Installment
This installment of CHECKERS (which may be the last since I'm not sure if I am going to add additional functionality) has a new module, CKRSTRAT.C. It contains a checkers-playing strategy based on straightforward look-ahead techniques. This allows you to play a game with the program.
The source code for CHECKERS is now more than fifty pages long, so it's impractical to reprint it here. You can download the source code and CHECKERS.EXE from one of the MSJ bulletin boards.
Overall Structure
I decided to structure CHECKERS around the windowing and messaging mechanism built into PM. Each major component of the program uses a window procedure to send messages to (and receive messages from) the other components.
Figure 1 shows the six source code modules of the program and their relationships. Four modules contain window procedures. These modules communicate with each other using user-defined messages, which are messages that begin with WM_USER (the value 1000H). The other two modules contain support functions.
CHECKERS.C contains the program's main function and creates a standard window using ClientWndProc as the window procedure for the Client window. While processing the WM_CREATE message, ClientWndProc creates the program's other three windows. ClientWndProc also processes menu commands.
BoardWndProc (contained in CKRBOARD.C) is the window procedure for a child window that is the same size as the Client window and completely covers it. BoardWndProc is responsible for drawing the board (using functions in CKRDRAW.C), for processing keyboard and mouse messages to allow the user to move a piece on the board, and for moving a piece based on the result of the checkers-playing strategy.
Both JudgeWndProc (contained in CKRJUDGE.C) and StratWndProc (contained in CKRSTRAT.C) are window procedures for object windows. Object windows are not displayed on the screen but they can send and receive messages just like normal windows. JudgeWndProc controls the game. It instructs BoardWndProc when to allow the user to move a piece, it tells StratWndProc when to calculate the best move in response to the user's move, and it tells BoardWndProc to move a piece based on the decision made by StratWndProc.
JudgeWndProc can also service requests from BoardWndProc to determine legal moves. In effect, when the user attempts to pick up a piece with the mouse, BoardWndProc sends a message to JudgeWndProc asking if it's legal to pick up that piece. Based on routines contained in CKRMOVES.C, JudgeWndProc responds affirmatively or negatively.
I will refer to these four windows as the Client, the Board, the Judge, and the Strategy.
User-Defined Messages
The user-defined messages that the window procedures use for communication are defined in the CHECKERS.H header file. First, let's examine the messages that ClientWndProc sends to (and receives from) JudgeWndProc and BoardWndProc.
After ClientWndProc creates the other three windows, it sets up a NEWGAME structure (defined in CHECKERS.H) and sends a WM_NEW_GAME message to JudgeWndProc. This message initiates a new game. The message can also occur when the user selects "New Game" from the program's menu. In this case, ClientWndProc displays a dialog box that allows the user to select black or white pieces and a level of difficulty.
This NEWGAME structure is defined in CHECKERS.H and contains eight fields (see Figure 2).
The first two fields are the window handles of the two players in the game. (I will refer to these as the Player windows.) The next three fields are the handles of the Board, Judge, and Client windows. In the current version of the program, either hwndBlack or hwndWhite will be the same as hwndBoard, depending on whether the user wants to play the black or white pieces. The other is set to the handle of the Strategy window.
Conceivably, in a future version of the program hwndBlack and hwndWhite could refer to two windows that communicate with two different external dynamic-link libraries that also contain checkers-playing strategies. In this case neither hwndBlack nor hwndWhite would be the same as hwndBoard. The Board window would be used solely to show the user how the game is progressing.
The sixth field of the NEWGAME structure is a BOARD structure, which is also defined in CHECKERS.H:
typedef struct
{
ULONG ulBlack ;
ULONG ulWhite ;
ULONG ulKing ;
}
BOARD ;
As I've discussed in previous installments, these three 32-bit integers define the layout of the board, with each bit position corresponding to one of the 32 squares on which a piece may reside. A game begins with ulBlack equal to 00000FFFH, ulWhite equal to FFF00000H, and ulKing equal to zero. However, a special test mode (which I'll discuss toward the end of this article) allows overriding of this layout.
After receiving the WM_NEW_GAME message, the Judge sends the message on to the two Player windows and, if neither of the two Player windows is the same as the Board window, to the Board window also. Each window that receives the WM_NEW_GAME message (the Judge, the two Players, and the Board) extracts the fields important to it and saves them in static variables.
For example, the Judge saves the two Player window handles because it must instruct the Players when to make a move. It also needs the Board window handle to tell the Board when to move a piece based on the response of the Strategy window, and it needs the Client handle for notifying the Client that the game is over (as I'll describe shortly).
The Board window saves the Judge window handle because it will need to ask the Judge (through messages) whether a user is attempting to make a valid move. The Board window also saves the sBottom field, which indicates which color should be at the "bottom" of the board (the part of the board that seems closer to the user). Currently, this depends on whether the user is playing black or white pieces.
The Strategy window saves the Judge window handle because it will need to inform the Judge of the move it has decided is best. It also saves the sLevel field, which can range from 0 to 3 and indicates the level of difficulty used in the checkers-playing strategy.
When JudgeWndProc determines that the game is over, it sends a WM_TELL_CLIENT_GAME_OVER message back to the Client window, indicating which color (black or white) has won. In this version of the program, ClientWndProc simply displays a message box indicating the winner. This message and the WM_NEW_GAME message are the only two messages sent between the Client and the Judge.
When the user selects a menu option to change the color of the board, ClientWndProc sends a WM_TELL_BOARD_COLOR_DIALOG or a WM_TELL_BOARD_STANDARD_COLORS message to BoardWndProc. These messages instruct BoardWndProc to display a dialog box (whose dialog box procedure is contained in CKRDRAW.C) allowing the user to choose new colors, or to set the standard colors. These are the only two messages the Client sends to the Board. The Board does not send any messages to the Client.
Making Moves
The Judge window notifies the two Player windows when they should make a move by sending them WM_JUDGE_SAYS_MAKE_MOVE messages. It sends the first make-move message to hwndBlack and waits for a response. The second make-move message is then sent to hwndWhite. This continues until the game is over (which occurs when a player cannot make a move) or until the user chooses to begin a new game or ends the program. When sending this message, the Judge really doesn't care whether the message is going to the Board window or the Strategy window.
When the Strategy window calculates a best move in response tothe make-move message, it responds by posting the Judge a WM_TELL_JUDGE_STRAT_MOVE_ENDED message with the move. This and the make-move message are the only two messages between the Judge window and the Strategy window.
The messages between the Judge window and the Board window are more complex. When the Board window receives a WM_JUDGE_SAYS_MAKE_MOVE message, it displays a mouse pointer that looks like a little hand and allows the user to pick up a piece with the mouse and move it. During this time, the Board sends several messages to the Judge to determine if the move is legal. These messages include:
WM_QUERY_JUDGE_PICKUP_PIECE
WM_QUERY_JUDGE_PUTDOWN_PIECE
WM_QUERY_JUDGE_CONTINUE_MOVE
When the user has completed a move, the Board sends the Judge a WM_TELL_JUDGE_BOARD_MOVE_ENDED message. At this time the Judge sends the Strategy window a WM_JUDGE_SAYS_MAKE_MOVE message.
When the Judge receives a WM_TELL_JUDGE_STRAT_MOVE_ENDED message from the Strategy window, the Judge must inform the Board window to move the piece. It does this using three messages:
WM_JUDGE_SAYS_MOVE_PIECE
WM_JUDGE_SAYS_KING_PIECE
WM_JUDGE_SAYS_REMOVE_PIECE
On receipt of the WM_JUDGE_SAYS_MOVE_PIECE message, the Board window starts a timer by calling the WinStartTimer function. When it receives the WM_TIMER messages, the Board window progressively moves the piece from its origin square to its destination square. It does this by calling four new functions I've added to CKRDRAW.C specifically for this purpose:
CkdExternalSave
CkdExternalShow
CkdExternalRestore
CkdExternalMove
These functions are similar to those discussed in Part III of this series that move a piece based on the mouse pointer.
The Judge sends the Board a WM_JUDGE_SAYS_KING_PIECE to indicate to the Board that a piece has reached the end and must be kinged, and a WM_JUDGE_SAYS_REMOVE_PIECE to indicate to the Board that a piece has been jumped and must be removed from the board.
When the Board has finished moving a piece in response to a WM_JUDGE_SAYS_MOVE_PIECE message, the Board sends the Judge a WM_TELL_JUDGE_PIECE_MOVED message. At this point, the Judge instructs the Board to allow the user to move a piece by sending the Board a WM_JUDGE_SAYS_MAKE_MOVE message.
The Judge and the Strategy
As I mentioned, the Judge window informs the Strategy window when to calculate a best move by sending it a WM_JUDGE_SAYS_MAKE_MOVE message. The mp1 message parameter that accompanies this message is a pointer to a structure of type MOVE, defined in CKRSTRAT.H as follows:
typedef struct
{
SHORT sColor ;
SHORT sKing ;
SHORT cSubMoves ;
BOOL fNewKing ;
SUBMOVE asubmove [10] ;
}
MOVE ;
The Judge sets the sColor field to 0 for Black or 1 for White, depending on whether it wants the Strategy window to calculate the best Black move or best White move. The next three fields are initialized to zero.
The last field of the structure requires a bit of an explanation. A checkers program is complicated somewhat by the rules governing jumps. If a player's piece can jump an opponent's piece, then it must jump the piece. If after jumping that piece, another jump is available, it must make that jump also. This must continue until no more jumps are available. I refer to each of these jumps in a single move as a submove.
It is possible to set up a checkerboard so that a piece can jump nine pieces in a single move. This is highly unlikely, of course, and perhaps even impossible. Regardless, I've allowed for nine submoves by defining an array of ten SUBMOVE structures in the MOVE structure. (I'll discuss shortly why the extra array element is required.)
The SUBMOVE structure is defined in CKRSTRAT.H as follows:
typedef struct
{
BOARD brd ;
SHORT iBeg, iEnd, iJmp ;
}
SUBMOVE ;
Before passing a pointer to the MOVE structure to the Strategy window, the Judge initializes the BOARD structure in the first element of the SUBMOVE array. (I discussed the BOARD structure earlier.) This contains the current layout of the board.
When the Strategy window receives a WM_JUDGE_SAYS_MAKE_MOVE message, it can save the value of mp1:
pmove = PVOIDFROMP (mp1) ;
where pmove is defined as a pointer to a MOVE structure. The Strategy window knows what color piece to move by the value of:
pmove->sColor
It knows the current layout of the board by the BOARD structure obtained as follows:
pmove->asubmove[0].brd
The Strategy window already knows the difficulty level because of the sLevel field passed in the NEWGAME structure. This is the bare minimum of information the Strategy window needs to calculate a best move.
When the Strategy window has finished calculating the best move, it alters the MOVE structure in ways that I will describe below, and then posts a WM_TELL_JUDGE_STRAT_MOVE_ENDED message to the Judge window. The Judge can then determine which move was made by analyzing the MOVE structure whose pointer it passed to the Strategy window.
The Strategy window is responsible for setting the sKing field of the MOVE structure to 1 if the piece it moved is a king. The fNewKing field is set to TRUE if the piece becomes a king at the end of the move. The cSubMoves field is set to the number of submoves, which can range from zero (if no move was available) to nine (indicating it jumped nine of the opponent's pieces).
For each submove, the Strategy window is also required to set the fields of the SUBMOVE structures to define the move. For example, if cSubMoves is set to 1, which means that the move consisted of a non-jump or a single jump, then the following still represents the original layout of the board.
pmove->asubmove[0].brd
The iBeg and iEnd fields of the asubmove[0] structure are the board positions (ranging from 0 to 31) of the origin square and destination square of the piece that moved. The iJmp field is the board position of the opponent's piece that was jumped, or 1 for a non-jump move. The following is the layout of the board after the move.
pmove->asubmove[1].brd
If the move consisted of nine submoves, each submove is indicated in the elements of the SUBMOVE array, with the following indicating the final layout of the board.
pmove->asubmove[9].brd
In general, the layout of the board following the move can be obtained from:
pmove->asubmove[pmove->cSubMoves].brd
The Judge window uses the information in the MOVE structure to pass messages to the Board window to carry out the move on the board.
More Structures
The Strategy window uses a straightforward look-ahead system to determine the best move. Let's suppose that the Strategy window is playing the White pieces. Based on the current layout of the board (obtained from the MOVE structure as described above), the Strategy window can determine all legal White moves based on that board layout, all Black moves in response to all those White moves, all White moves in response to all those Black moves, and so forth.
Keeping track of all these possible moves requires a tree of self-referential structures. The Strategy window first uses a structure called MOVEBLOCK to store all the legal moves available in a particular board layout (see Figure 3).
The first field indicates the number of possible moves. The Strategy window must allocate memory for a MOVEBLOCK structure of sufficient size for cMoves MOVEP structures.
The MOVEP structure is similar to the MOVE structure except that it contains an additional field, a pointer to a MOVEBLOCK structure that contains all the moves in response to this move (see Figure 4). This pointer is defined as a VOID pointer because the structure is defined in the source code before the MOVEBLOCK structure is defined.
These two structures are used for building the tree of possible moves. Suppose the user is playing Black and the Strategy window is playing White and that there are five possible White moves. The Strategy window allocates a memory block sufficient to hold a MOVEBLOCK structure plus four additional MOVEP structures. The cMoves field is set to five and the five elements of the amovep array are set to the five possible moves.
For each of those five possible moves, there may be several countermoves by Black. Five additional blocks of memory (for each of these five sets of countermoves) are allocated for five MOVEBLOCK structures. Pointers to these five MOVEBLOCK structures are assigned to the pmoveblk fields of the five MOVEP structures in the original MOVEBLOCK structure.
In practice, however, it is usually impossible to determine the number of possible moves at the outset. The problem, as is typical with checkers programs, is in working with multiple jump moves. There may be a jump available, and after that jump there may be two possible second jumps. This requires that the MOVEBLOCK structure be reallocated as the moves are being determined.
Recursion
As you may have guessed by now, the checkers-playing strategy cries out for recursive functions (functions that call themselves). The CKRSTRAT.C module has several recursive functions.
The most obvious need for a recursive function is in determining moves and countermoves and counter-countermoves and so forth. This is handled by the CksGetCounterMoves function in CKRSTRAT.C.
Another recursive function is useful for analyzing multiple jumps. After the program has determined that a jump is available, it must search for additional jumps. This is handled by the recursive CksGetAllJumps function.
After all the MOVEBLOCK structures in this tree have been allocated and analyzed, it is necessary to free all the memory. A third recursive function, call CksFreeMoveBlock, handles this chore.
Checkers-Playing Strategy
This version of CHECKERS supports four different levels of strategy, Simple, Beginner, Intermediate, and Advanced. In this discussion I'll assume that the user is playing Black and the program determines the best White move in response to that.
The Simple level is indeed quite simple. The checkers-playing strategy makes random (but legal) moves. This is not quite as perverse as you might think: in the early stages of the game, it's sometimes difficult to determine whether you're playing a computer or a small child.
The playing level I call Beginner goes one level deep in the look-ahead. It surveys all the possible White moves and picks the one with the best score. The result of this is not very significant: if White has several possible jump moves, it will pick the one that jumps the most pieces.
The Intermediate playing level looks three levels deep. It looks at all the possible White moves, all the possible Black moves in response to those, and the White moves in response to those Black moves. When considering how to use this information, your immediate instinct, as programmer of this algorithm, might be to find the best White move in this third level, and take the original White move that would result in this. But that's wrong because it assumes that the user (playing Black) is stupid.
What you have to assume is that the user is almost as smart as the program, but not quite. For each of the first White moves, the program must find the best Black move in response to that move, and then the best White move in response to those best Black moves. The best White move then determines which original move to make.
For example, Figure 5 shows a simple three-level tree, assuming that there are three possible White moves, three Black moves in response to those, and three White moves in response to each Black move. For some of these moves, the player's board advantage (which I'll discuss shortly) is shown in a circle. For the White moves, this is the White advantage, and for the Black moves, it's the Black advantage. (Advantages don't need to be calculated for the moves with empty circles.)
Look at the Black moves first. For each of the original White moves, Figure 5 indicates the best Black countermove with a heavy circle. Now look at the White responses to those best Black moves. Again for each set, the best White move in each set is indicated with a heavy circle. Overall, the best White advantage is 300, which results from the best White move to the best Black move to the second original White move. So the program picks the second White move.
The Advanced level goes five levels deep. It picks the best Black move on the fourth level, the best White moves on the fifth level in response to those, and based on the best White move on the fifth level, determines the best original White move.
When determining the best moves, it may be that several moves result in the same advantage. In this case, the program chooses randomly among these best moves.
Calculating the Advantage
This version of CHECKERS calculates an advantage based on a simple analysis of the layout of the board. I'll discuss this based on the Black advantage; simply taking the negative of the number converts to a White advantage.
If there are no White pieces left, or if there are no legal moves or jumps that a White piece can make, then White has lost and the advantage is set at 10,000.
Similarly if there are no Black pieces or if Black cannot make a legal move or jump, then Black has lost and the advantage is set at 10,000.
Otherwise, the advantage is calculated by subtracting the number of White pieces from the number of Black pieces, where a non-king piece is counted as 100 and a king is counted as 175. (Thus, it is assumed that a king is worth 75 percent more than a non-king.)
This is perhaps the simplest approach to calculating the advantage. More sophisticated techniques involve searching for various advantageous patterns on the board and weighting each of them. The program could then change these weights based on experience. If you are interested in this, a good place to begin research are two papers by Arthur L. Samuel titled "Machine Learning Using the Game of Checkers" reprinted in Computer Games I (Springer-Verlag, 1988), edited by David N.L. Levy.
Testing the Code
Testing a program such as this can be difficult. For a while, I simply played games with the program and tried to make sure it wasn't making dumb moves. But this was obviously unsatisfactory.
The solution I chose was to include a special "Setup" option on the New Game dialog box. This creates another dialog box that allows you to interactively define the initial layout of the board. Restricting the board to just a few pieces allowed me to determine more easily if the program was performing correctly.
Of course, a programmer working alone is rarely able to debug any but the simplest programs entirely. Fortunately, I can call upon perhaps the finest group of beta-testers in the world for help-the readers of MSJ!