🚀 go-pugleaf

In article <8408@charon.cwi.nl> dik@cwi.nl (Dik T. Winter) writes:
:In article <1992Dec17.164858.11378@wam.umd.edu> joel@wam.umd.edu (Joel M. Hoffman) writes:
: > Actually, TTT is one game where brute force seems to work better than
: > advanced theory.  There just aren't that many possibilities, even
: > supposing rotations are distinct.  It's not worth the trouble to
: > rotate a TTT board.
: > 
:Right.  There are (much less than) 3^9=19683 different positions.

Here's a brute-force program that also uses rotations and reflections.  (I
didn't post it when the subject first came up because I expected a flood of
them - after all it's something *everybody* writes at least once, but no-one
did so here's a token effort so as not to disappoint the people whose
interest was raised by the subject...)

/*
 *   Title:      Naughts & Crosses
 *   FileName:   xandoz.c
 *
 *   Author:     Graham Toal <gtoal@gtoal.com>
 *
 *   Created:    Wed 20/09/89 18:15
 *   LastEdit:   Thu 20/09/89 09:15
 *
 *   Purpose:
 *      To play the game of naughts and crosses.  The project was specified
 *   on page 65 of Computer Shopper UK, No.20, Oct 1989.  The specification
 *   implies that the human plays first: "Write a program which will accept
 *   an input from a player..."  The rules given are not sufficient to always
 *   force a win or draw: the simple game of:
 *
 *             X--  X--  X--  X-O  X-O  X-O  X-O
 *             ---  -O-  -O-  -O-  -O-  OO-  OO-
 *             ---  ---  --X  --X  X-X  X-X  XXX
 *   Following rule: 3         4         2
 *
 *   follows the algorithm correctly and loses.  However it is not obvious
 *   from the spec whether the client wants a winning game or one written
 *   to his rules, so I have implemented an algorithm which is table driven
 *   and can be simply adapted to any rules he desires at a later date.
 *   (The table supplied implements a winning game)
 *
 *   Revision history:
 *        Version 0.01 20/09/89   Initial implementation.
 *                1.00 21/09/89   Final release.
 *                                 1) Fixed entry in table (one 'o' should have
 *                                    been a '*')
 *                                 2) Tidied up endgame logic
 *                                 3) Speed improvement by moving state-loop
 *                                    from inner loop to outer loop
 *
 */

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define true (0==0)
#define false (0!=0)

/* ############ FINITE STATE MACHINE DESCRIBING FULL GAME TREE ############# */

char *known_board[] = {
  "-X--o----", "-XO-O-*XX", "-XO-O-XoX", "-XO-OX*-X", "-XOXO-*-X", "-XOXO-*X-", 
  "-XOXOX*--", "-Xo-O---X", "-XoXO----", "O*O-X--XX", "O*O-X-X-X", "O*O-XX--X", 
  "O*OOXXX-X", "O*OXX---X", "O--OXX*-X", "O--OXX*X-", "O--oXX---", "O-X*X-O-X", 
  "O-X*XXO--", "O-X-X-o--", "O-XOXX*--", "O-XXXoO--", "O-o-X---X", "O-oOXXX--", 
  "OOX*X-OXX", "OOXXXoOX-", "OOXoXXOX-", "OX*-OXOXX", "OX*XO-OXX", "OX--O-XX*", 
  "OX--O-oXX", "OX--OX-X*", "OX--X--o-", "OX-OXX*--", "OX-XO--X*", "OX-XXo-O-", 
  "OX-oXX-O-", "OXO-X--oX", "OXO-XoXOX", "OXOOXXXo-", "OXOXO-XX*", "OXOXO-XoX", 
  "OXOXOXX-*", "OXOXXo-OX", "OXOXXoXO-", "OXOoX-XOX", "OXOoXX-OX", "OXOoXXXO-", 
  "OXX*O-OXX", "OXX-O--X*", "OXX-X-Oo-", "OXX-X-oO-", "OXX-XXOO*", "OXX-XoOOX", 
  "OXXOXX-Oo", "OXXXX-OO*", "OXXXXOOo-", "OXXXXOoO-", "OXo-X--OX", "OXo-X-XO-", 
  "OXoOXX-OX", "OXoOXXXO-", "OXoXXO-OX", "OXoXXOXO-", "O*OOXXXX-", "OoX-X-OX-", 
  "OoXXXOO-X", "OoXXXOOX-", "X---o----", "X-O-OX*-X", "X-O-OX*X-", "X-OOOXXXo", 
  "X-OXOX*--", "X-OoOXX--", "X-o-OX---", "XO*-OXOXX", "XO*XO-OXX", "XO--O-X*X", 
  "XO--O-oXX", "XO--OX-*X", "XO-XO--*X", "XOX-O--*X", "XOX-O-X*-", "XOX-O-oX-", 
  "XOX-OX-*-", "XOX-OXOXo", "XOX-OoOXX", "XOXXO--*-", "XOXXO-OXo", "XXO-O-*-X", 
  "XXO-O-*X-", "XXO-OX*--", "XXOOO*X-X", "XXOOO*XX-", "XXOOOXX-*", "XXOOOXX-o", 
  "XXOXO-*--", "XXOoO-X--", "XXOoO-XOX", "XXo-O----", "Xo--O---X", "XoOOOXX-X", 
  "XoX-O----", "o---X----", "oX--O--X-", "oXO-OXXOX", "oXOXO-X--", "oXOXO-XOX", 
  ""
};

/* I/O functions at end */
void print_board(char *board);
void print_help(void);
void get_board(char *board);

/* support functions after main() */
int board_cmp(char *board, char *known, int *won);
void flip_board(char *b);
void rotate_board(char *b);

/* ######################## MAIN PLAYING CODE ############################# */

/* Normally I would comment a program which does sneaky things like this,
   but I'll not do so here to give the lads at Computer Shopper some
   amusement in working out how the program copes with reflections and
   rotations of the board, and getting the new move printed in the
   correct orientation.   Have fun!
 */

int main(int argc, char **argv) {
char board[3*3];
int x, y, move, move_found, won, flip, rotate, state;
   print_help();
   for (move = 0; move < 4; move++) {
      won = false;
      get_board(board);
      move_found = false;
      for (state = 0; *known_board[state] != '\0'; state++) {
        for (flip = 0; flip <= 1; flip++) {
          for (rotate = 0; rotate <= 3; rotate++) {
              if (!move_found && board_cmp(board, known_board[state], &won)) {
                strcpy(board, known_board[state]);
                move_found = true;
              }
            rotate_board(board);
          }
          flip_board(board);
        }
        if (move_found) break;
      }
      fprintf(stderr, "My move is:\n");
      print_board(board);
      if (won) fprintf(stderr, "He he he! I win!\n"), exit(0);
   }
   fprintf(stderr, "Your next move is obvious - it's a draw\n"), exit(0);
}

/* *********************** Support functions *************************** */

int board_cmp(char *board, char *known, int *won) {
int xy, matches, may_win;
  may_win = false;
  for (xy = 0; xy < 3*3; xy++) {
    if (board[xy] == known[xy]) {
    } else if ((board[xy] == '-') &&
               (known[xy] == 'o' || known[xy] == '*')) {
      may_win = (known[xy] == '*');
    } else return(false);
  }
  *won = may_win;
  return(true);
}

void flip_board(char *b) {
int temp;
  temp = b[1]; b[1] = b[3]; b[3] = temp;
  temp = b[2]; b[2] = b[6]; b[6] = temp;
  temp = b[5]; b[5] = b[7]; b[7] = temp;
}
void rotate_board(char *b) {
int temp;
  temp = b[0]; b[0] = b[6]; b[6] = b[8]; b[8] = b[2]; b[2] = temp;
  temp = b[1]; b[1] = b[3]; b[3] = b[7]; b[7] = b[5]; b[5] = temp;
}

/* ###################################################################### */

/* trivial stuff. */

void print_board(char *board) {
int x, y;
  for (y = 0; y < 3; y++) {
    for (x = 0; x < 3; x++) fprintf(stderr, "%c", board[x+y*3]);
    fprintf(stderr, "\n");
  }
}

void print_help(void) {
  fprintf(stderr, "Type in a board like this:\n\n---\nX--\n---\n\n");
}

void get_board(char *board) {
int x, y, ch;
  do {
    fprintf(stderr, "Please type in your board:\n");
    for (y = 0; y < 3; y++) {
      for (x = 0; x < 3; x++) {
        do {
          ch = fgetc(stdin); if ('a' <= ch && ch <= 'z') ch = toupper(ch);
        } while (ch != 'X' && ch != 'O' && ch != '-');
        board[x+y*3] = ch;
      }
    }
    fprintf(stderr, "This is what I think you typed:\n");
    print_board(board);
    fprintf(stderr, "Correct? (Y or N): ");
    do {
      ch = fgetc(stdin); if ('a' <= ch && ch <= 'z') ch = toupper(ch);
    } while (ch != 'Y' && ch != 'N');
  } while (ch != 'Y');
}