Listing presents the source code to the version ttt.h header file, and also the source code ttt.c. ////////////////////////////////// // // TTT.H // // Tic Tac Toe header file. // // Constant definitions. #define EMPTY 0 #define X 1 #define O 2 #define DRAW 3 #define FALSE 0 #define TRUE 1 #define HUMAN 0 #define COMP 1 #define NO_MOVE 10 #define FORCED 1 #define UNFORCED 0 #define OFFSET 11 #define GAMES 100 #define MEM_SIZE (GAMES * OFFSET) #define NOT_ALLOWED 1 #define ALLOWED 0 // Special type definitions. typedef int board_t[3][3]; // Function prototypes. int game_over(board_t board, int turn); void print_board(board_t board); void copy_board(board_t board1, board_t board2); int get_human_move(board_t board); void make_move(board_t board, int move, int turn); void print_message(int player); int get_comp_move(board_t board, int turn, int counter, int move_type[9], int memory[MEM_SIZE], int moves[9], int mem_count, int second_moves[9][9]); int random_move(board_t board); int check_loss(board_t board, int turn); void analyze_loss(int moves[9], int move_type[9], int memory[MEM_SIZE], int counter, int *mem_count, int second_moves[9][9]); void add_loss(int memory[MEM_SIZE], int *mem_count, int move, int change, int moves[9]); int old_loss_check(int counter, int memory[MEM_SIZE], int moves[9], int mem_count); void open_data_base(int memory[MEM_SIZE], int *mem_count, int second_moves[9][9]); void close_data_base(int memory[MEM_SIZE], int *mem_count, int second_moves[9][9]); void analyze_second(int moves[9], int second_moves[9][9]); int learned_second_move(board_t board, int moves[9], int second_moves[9][9]); /////////////////////////////////// // // TTT.C // // Tic Tac Toe demo program. // #include #include #include #include #include #include #include #include "ttt.h" ////////////////////////////////////////////////// // game_over checks if a given player // has three in a row on a given board. // It returns either TRUE or FALSE. // int game_over(board_t board, int turn) { int i, j; // loop variables for (i= 0; i < 3; i++) { // Examine all three rows. if ((board[i][0] == turn) && (board[i][1] == turn) && (board[i][2] == turn)) { return TRUE; } // Examine all three columns. if ((board[0][i] == turn) && (board[1][i] == turn) && (board[2][i] == turn)) { return TRUE; } } // Examine both diagonals. if ((board[0][0] == turn) && (board[1][1] == turn) && (board[2][2] == turn)) { return TRUE; } if ((board[2][0] == turn) && (board[1][1] == turn) && (board[0][2] == turn)) { return TRUE; } // No wins for the player. return FALSE; } ////////////////////////////////////////////////// // print_board prints out a given board // using X's, O's, and numbers to // represent the nine different positions // on the board. // void print_board(board_t board) { int i, j; // loop variables for (i= 0; i < 3; i++) { printf("\n"); for (j= 0; j < 3; j++) { // For each square, print piece if occupied. // Otherwise, print corresponding number. if (board[i][j] == X) { printf(" X "); } else if (board[i][j] == O) { printf(" O "); } else { printf(" %d ", (3*i+j) ); } } } printf("\n"); } /////////////////////////////////////////////////// // copy_board copies the first // board to the second. // void copy_board(board_t board1, board_t board2) { int i, j; // loop variables for (i= 0; i < 3; i++) { for (j= 0; j < 3; j++) { board2[i][j]= board1[i][j]; } } } ////////////////////////////////////////////////// // get_human_move prompts the player and accepts // a number from 0-8 that represents a square // on the board. It repeats the prompt until // a legal move is entered. // int get_human_move(board_t board) { int move; do { // Prompt player. printf("\nenter move (0-8) : "); // Get player's move. scanf("%d", &move); // Return if legal move (square is empty). if (board[move / 3][move % 3] == EMPTY) { break; } } while (TRUE); return move; } ////////////////////////////////////////////////// // make_move takes a number from 0-8 and // puts a given piece in the corresponding place // on the given board. // void make_move(board_t board, int move, int turn) { int row, col; row= move / 3; col= move % 3; board[row][col]= turn; } ////////////////////////////////////////////////// // print_message prints the appropriate message // after the game is over. The winner of the // game is passed. // void print_message(int player) { if (player == HUMAN) { printf("\nYou win - I learn\n"); } else if (player == COMP) { printf("\nI win - sucks for you\n"); } else { printf("\nIt's a draw\n"); } } ////////////////////////////////////////////////// // get_comp_move makes the computer move using // different functions, such as checking for wins // and losses, using learning from losses, and // making a random move as the last resort. // int get_comp_move(board_t board, int turn, int counter, int move_type[9], int memory[MEM_SIZE], int moves[9], int mem_count, int second_moves[9][9]) { int move, opponent; opponent= (turn == X) ? O : X; // Use learning on the second move. if (counter == 1) { move= learned_second_move(board, moves, second_moves); move_type[counter]= UNFORCED; return move; } // Make move for win if possible. move= check_loss(board, opponent); if (move != NO_MOVE) { move_type[counter]= FORCED; return move; } // Make move to block loss if needed. move= check_loss(board, turn); if (move != NO_MOVE) { move_type[counter]= FORCED; return move; } // Make move based on previous loss. move= old_loss_check(counter, memory, moves, mem_count); if (move != NO_MOVE) { move_type[counter]= UNFORCED; return move; } // Make random move as last resort. move_type[counter]= UNFORCED; return (random_move(board)); } ////////////////////////////////////////////////// // check_loss looks to see if the passed player // has to block a loss. It uses an extra board // to simulate moves and then checks to see if // the opponent has won. // int check_loss(board_t board, int turn) { board_t board2; // board for simulated moves int i, opponent; opponent= (turn == X) ? O : X; // Go through all possible moves. for (i= 0; i < 9; i++) { copy_board(board, board2); // Make move if possible. if (board2[i / 3][ i % 3] == EMPTY) { make_move(board2, i, opponent); // If move produces loss, return it to block. if (game_over(board2, opponent)) { return i; } } } return NO_MOVE; } ////////////////////////////////////////////////// // random_move makes a random move. // int random_move(board_t board) { int move; while (TRUE) { randomize(); move= random(1000) % 9; // Return move if legal. if (board[move / 3][move % 3] == EMPTY) { return move; } } } ////////////////////////////////////////////////// // analyze_loss examines the record of the moves // and the types of moves of a lost game. It then // uses the forced move algorithm to find which // move to change and which move to make instead. // In this version, if the move to be changed is // the second one, then a special function is used // to apply the second type of learning. // void analyze_loss(int moves[9], int move_type[9], int memory[MEM_SIZE], int counter, int *mem_count, int second_moves[9][9]) { int move, change; // Start at computer's last move. move= counter - 2; // Go to last unforced move. while (move_type[move]==FORCED) { move -= 2; } // Use second type of learning if at second move. if (move == 1) { analyze_second(moves, second_moves); return; } // New move is player's next move. change= moves[move+1]; // Add record to memory buffer. add_loss(memory, mem_count, move, change, moves); } ////////////////////////////////////////////////// // add_loss saves a record of the game in the // proper format into the memory buffer if there // is enough room. // void add_loss(int memory[MEM_SIZE], int *mem_count, int move, int change, int moves[9]) { int *begin, i; // Return immediately if the maximum // number of games has already been saved. if (*mem_count == GAMES) { return; } // Start at beginning of available buffer. begin= (memory + (*mem_count * OFFSET)); // First save point in game of change. *begin++= move; // Save move to make instead. *begin++= change; // Save list of moves of game. for (i= 0; i < 9; i++) { *begin++= moves[i]; } // Increment counter of records. ++(*mem_count); } ////////////////////////////////////////////////// // old_loss_check uses the memory buffer to see // if the sequence of moves has been played before // and returns the correct move if it has. // int old_loss_check(int counter, int memory[MEM_SIZE], int moves[9], int mem_count) { int i, j, found; int move; // Search through all records. for(i= mem_count-1; i >= 0; i--) { // Proceed only if record specifies change // at this particular move. if (memory[(i*OFFSET)] == counter) { found= 1; // Go to next record if moves up to this // point are not the same. for(j= 0; j < counter ; j++) { // Compare each move to moves in the record. if (moves[j] != memory[(i*OFFSET) + j + 2]) { found= 0; break; } } // If record is valid, return saved move. if (found) { move= memory[(i*OFFSET) + 1]; return move; } } } return NO_MOVE; } ////////////////////////////////////////////////// // open_data_base reads in the memory buffer, // record counter, and second_move array from // the file "memory.dat" . If the file // doesn't exist, all arrays are initialized. // void open_data_base(int memory[MEM_SIZE], int *mem_count, int second_moves[9][9]) { int handle, i; // Open memory.dat. handle= open("memory.dat", O_CREAT | O_TRUNC | O_BINARY, S_IREAD | S_IWRITE); // If file doesn't exist, initialize arrays. if(handle == -1) { *mem_count= 0; memset(memory, MEM_SIZE, 0); for (i= 0; i < 9; i++) { // All second moves are initially allowed, memset(second_moves[i], 9, ALLOWED); // but the second move can't be the same as the first. second_moves[i][i]= NOT_ALLOWED; } return; } // Read in record counter. if (read(handle, mem_count, 2) == -1) { printf("\n read error \n"); } // Read in memory buffer. if (read(handle, memory, MEM_SIZE) == -1) { printf("\n read error \n"); } // Read in second_moves array. for (i= 0; i < 9; i++) { if (read(handle, second_moves[i], 9) == -1) { printf("\n read error \n"); } } // Close file. close(handle); } ////////////////////////////////////////////////// // close_data_base writes the memory buffer, // record counter, and second_move array to // the file "memory.dat". // void close_data_base(int memory[MEM_SIZE], int *mem_count, int second_moves[9][9]) { int handle, i; // Erase existing file. remove("memory.dat"); // Open file for writing. handle= open("memory.dat", O_CREAT | O_TRUNC | O_BINARY, S_IREAD | S_IWRITE); if(handle == -1) { printf("\nerror opening file\n"); // Exit immediately on error. exit(1); } // Write record counter to file. if(write(handle, mem_count, 2) == -1) { printf("\n write error \n"); } // Write memory buffer to file. if(write(handle, memory, MEM_SIZE) == -1) { printf("\n write error \n"); } // Write second_moves array to file. for (i= 0; i < 9; i++) { if(write(handle, second_moves[i], 9) == -1) { printf("\n write error \n"); } } // Close file. close(handle); } ////////////////////////////////////////////////// // analyze_second looks at the list of moves and // remembers which move leads to a loss following // a certain first move. // void analyze_second(int moves[9], int second_moves[9][9]) { // Since a loss occured, this second move should // not be allowed. second_moves[(moves[0])][(moves[1])]= NOT_ALLOWED; } /////////////////////////////////////////////////// // learned_second_move uses the second_moves array // to make a move that doesn't lead to a loss. // int learned_second_move(board_t board, int moves[9], int second_moves[9][9]) { int move; move= random_move(board); // Get a random move that doesn't lead to a loss. while (second_moves[(moves[0])][move] == NOT_ALLOWED) { move= random_move(board); } return move; } void main() { board_t board= {{EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}, {EMPTY, EMPTY, EMPTY}}; int turn= X; int player= HUMAN; int move; int counter; int moves[9]; int move_type[9]; int memory[MEM_SIZE]; int mem_count= 0; int second_moves[9][9]; open_data_base(memory, &mem_count, second_moves); counter= 0; while (TRUE) { print_board(board); // Get the next move. if (player == HUMAN) { move= get_human_move(board); move_type[counter]= 0; } else { move= get_comp_move(board, turn, counter, move_type, memory, moves, mem_count, second_moves); } make_move(board, move, turn); // Record move and increment counter. moves[counter]= move; ++counter; if (game_over(board, turn)) { print_board(board); print_message(player); // Learn from loss if computer loses. if (player == HUMAN) { analyze_loss(moves, move_type, memory, counter, &mem_count, second_moves); } // End program. break; } // Check if game is a draw. if (counter == 9) { print_board(board); print_message(DRAW); break; } // Switch player and turn. player= (player == HUMAN) ? COMP : HUMAN; turn= (turn == X) ? O : X; } close_data_base(memory, &mem_count, second_moves); }