Wednesday, August 19, 2015

Game of Tic-Tac-Toe.

It would probably be difficult to find anybody that has never played a classic 3x3 Tic-Tac-Toe game. I remember that at school it was one of the time killing methods during boring activities we were made to attend. We played many different variants of the game, mostly going beyond the 3x3 boundaries (we played often 5x5 variant or until the space was available on the piece of paper). Anyway, while experimenting on my C-128 with CP/M system and Aztec C compiler, I thought that Tic-Tac-Toe would be a good project for a game running in such environment as it requires no graphics, text mode being sufficient for presentation and player input. Well, I started the development on that platform, however the cycles of code changing/compiling/testing took awfully long time (due to CP/M and compiler slowness on C-128), therefore I decided to move the development to a modern computer. This proved a fun casual programming project, the goal was to create an unbeatable computer AI playing classic 3x3 Tic-Tac-Toe game.

The game rules:

Players play on a 3x3 square board:

 In the empty spaces of the board, using pencils on a paper (or a computer generated board) players put their symbols taking turns. One player plays with 'O' (circle) and another with 'X' - cross. In my version if human player selects 'O' symbol, he/she begins the game. Otherwise, computer AI performs the first move. It does not matter which symbol really starts the game, but we must establish some laws. A different approach could be to select the 1-st player randomly and this would also be fine.
The goal of the game is to win by putting the player's 3 symbols in a row in any horizontal, vertical or diagonal line. This game, if both players make no mistakes and play with proper tactic, can not be lost or won and shall always end-up in a tie.
For the benefit of this article and explanation of the algorithm, I will name the board columns A, B C and rows 1, 2 and 3. The corner spots are A1, A3, C1, C3. The edge spots are B1, A2, C2 and B3. The center spot is B2.

Because the development started on a limited in resources platform (CP/M OS, 8-bit hardware), I established some development directives to prevent the system running out of resources playing such a simple game, which would make the programmer look rather lame.

The rules are:

  • Do not use recursion (stack limitations).
  • Use as few local function variables as possible (stack limitations).
  • Game works in text mode (CP/M limitation) in a scroll-down fashion (not using potentially incompatible terminal control characters, aimed for portability here).

When approaching such problem from programming perspective I always use top-down programming method. I write main() function first and invoke whatever functions I might need, implemented or not, inventing them along the way. Later I proceed to implement the rest of the needed functions using exactly the same method. I repeat the process until all the required functions are implemented. Then it is time to make the code to compile/link properly. At this point the process of debugging starts which consists of the cycles of testing/debugging/correcting code until the program is up to my expectations and bugs free.

As with any game, we should start with the main program loop, which basically consists of initialization function, presentation function, user input function, game logic function and game-end test.

In pseudo-code, we might end-up with something like this:

repeat until game_not_ended
   if game_ended
      if play_again
   if game_ended
      if play_again

The C implementation may look similar to this:

    int n;


    do {
       n = end_game();
       if (0 == n) {
          n = end_game();
       if (1 == n) {
    } while(0 == n || 1 == n);

This part of course is not too difficult, even for a beginner. The devil is in details, as they say. The first two of the development directives that I made before imply that the game logic should be based on a simple heuristic evaluation. Computer should perform analysis of all possible moves in the next turn, assign the score to each possibility and then pick the best move based on this evaluation. That function is comp_move(), 

Before implementation, I needed to design a clear strategy based on the experience of playing the game and on game rules. The strategy I assumed is as follows (remember that computer will be only looking one move ahead and base its decision on existing game state):

  • The top most important directive is to prevent other player from winning.
  • Next priority is to favor the center spot, if not yet taken, make the move there.
  • If none of the above conditions occurred, then if the human player already occupies two opposite corners but remaining corners are free, make move to any edge spot.
       This hypothetical situation occurs when player has symbols in spots 
       A1, C3  and spots A3, C1 are free OR the opposite/symmetrical (player:
       A3, C1, free: A1, C3). 

       See graphical representation below:


  • If the player symbol occupies an edge and one of the corners on the opposite side of the board, the preferred position is a corner spot next to the player occupied edge spot and opposite to the player occupied corner spot.
       The above pattern occurs if player has one of A1, A3 combined with 
       C2 OR one of C1, C3 combined with A2 OR one of A1, C1 combined with 
       B3 OR one of A3, C3 combined with B1.

       See graphical representation below:


  • If player played a corner, also play a corner.
  • If player symbol occupies 2 adjacent edge spots, take a corner between them.
  • if player played an edge, also play an edge.

Above tactics are applied in the order as listed, from top to bottom.
Below is the code if my implementation:

 * A computer move routine (AI).
 * Looks unbeatable :-) (needs more testing).
   int i, j, k, l, m, n;

   k = l = -1; /* indexes of computer move */
   m = n = 0;  /* game evaluation results/scores for computer and player */

   /* evaluate heuristically each possible next move for player and computer */
   /* i - column index, j - row index */
   for (i=0; i<3; i++) {
      for (j=0; j<3; j++) {
         if (' ' == board[i][j]) {
            board[i][j] = plr_sym; /* simulate player's move */
            /* if player's move would result in winning, give this position */
            /* highest score to prevent human player from winning */
            if (cmc > 0 && n < 100 && 1 == game_done()) {
                n = 100; k = i;    l = j;
            } /* next - favor the center spot */
            else if (n < 50 && i == 1 && j == 1) {
                n = 50;    k = l = 1;
            } /* next - if human player occupies two opposite corners */
                          /* and remaining corners are free, prefer edge spot */
            else if (cmc > 0 && n < 25 && abs(j-i) == 1 &&
                       ((board[0][0] == plr_sym && board[2][2] == plr_sym
                               && board[0][2] == ' ' && board[2][0] == ' ')
                       || (board[2][0] == plr_sym && board[0][2] == plr_sym
                              && board[0][0] == ' ' && board[2][2] == ' '))) {
                n = 25;    k = i; l = j;
            } /* next - if player has a corner and edge on opposite sides */
              /* take the corner spot next to the player's edge piece */
            else if (cmc > 0 && n < 20 && abs(j-i) == 2
                               && board[i][1] == plr_sym
                              && ((i == 2 && (board[0][0] == plr_sym
                                 || board[0][2] == plr_sym))
                                 || (i == 0 && (board[2][0] == plr_sym)
                                 || board[2][2] == plr_sym))) {
                n = 20; k = i; l = j;
            } /* next - similar but simmetrical situation */
            else if (cmc > 0 && n < 20 && abs(j-i) == 2
                                   && board[1][j] == plr_sym
                                   && ((j == 2 && (board[0][0] == plr_sym
                                   || board[2][0] == plr_sym))
                                   || (j == 0 && (board[0][2] == plr_sym)
                                   || board[2][2] == plr_sym))) {
                n = 20; k = i; l = j;
            /* next - prefer corner spots if this is not the 1-st move */
            /* and player also played corner */
            else if (cmc != 0 && n < 12 && i != 1 && j != 1 && plr_nm_col != 1
                                         && plr_nm_row !=1) {
                n = 12; k = i; l = j;
            } /* next - if player occupies 2 adjacent edge spots and */
              /* the remaining edge spots are free, take corner between them */
            else if (cmc > 0 && n < 6 && i != 1 && j != 1
                         && board[i][1] == plr_sym && board[1][j] == plr_sym) {
                n = 6; k = i; l = j;
            } /* next - prefer edge spots if this is not 1-st move and */
              /* player also played edge */
            else if (cmc != 0 && n < 3 && abs(j-i) == 1
                               && abs(plr_nm_col-plr_nm_row) == 1) {
                n = 3; k = i; l = j;
            board[i][j] = comp_sym; /* simulate computer move */
            m = eval_game(comp_sym); /* evaluate the current game */
            /* if computer move gets higher score than player move and other */
            /* preferred strategies then take precedence and assign new */
            /* computer move to current location [i,j] */
            if (m > n) {
                n = m; k = i; l = j;
            board[i][j] = ' '; /* restore board to previous state */
   /* if move indexes were assigned, perform this move */
   if (0 <= k) {
        cmc++; mvc++;
       board[k][l] = comp_sym;
       printf("Computer move: %c%d\n", (char)('A'+k), l+1);

There is not much more to say about this simple game.
Download from here and enjoy not winning it ever :-)
Game runs in text mode (DOS) and should work under any modern version of windows system.
The program is written in C and is highly portable and will compile on Windows, Linux, AIX and even under CP/M 3.0 (Aztec C).


Marek K

No comments:

Post a Comment