/* * Title: Naughts & Crosses * FileName: xandoz.c * * Author: Graham Toal * * 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 #include #include #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'); }