Last active
December 31, 2015 18:39
-
-
Save pirate/8028532 to your computer and use it in GitHub Desktop.
Early version of C tictactoe
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Nick Sweeting 2013/09/09 | |
Tic Tac Toe in C++ (non OOP) | |
MIT Liscense | |
save as tictactoe.cpp, then run | |
`g++ tictactoe.cpp -o tic && ./tic` to run | |
*/ | |
#include <stdlib.h> | |
#include <iostream> | |
using namespace std; | |
enum square {EMPTY=' ', O='O', X='X'}; // define a new enum "square" with 3 possible values (used for array board[]) | |
square board[9] = {EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY}; // initialize the board with all empty squares | |
bool allow_skip = true; // allow the human to skip their turn and have the computer play itself (debug only) | |
// print user help board showing square numbering | |
void print_help() { | |
cout << 1 << '|' << 2 << '|' << 3 << endl; // 1|2|3 | |
cout << 4 << '|' << 5 << '|' << 6 << endl; // 4|5|6 | |
cout << 7 << '|' << 8 << '|' << 9 << endl; // 7|8|9 | |
} | |
// print current board highlighting last human move and last computer move (sorry for line noise, ansi escapes are ugly) | |
void print_board(square board[9], int recent_human_move, int recent_computer_move) { | |
string tmp_board[9]; | |
for (int i=0; i<9; i++) { | |
if (i == recent_human_move) tmp_board[i] = "\033[1;31m" + string(1,board[i]) + "\033[0m"; // red for human's last move (using ASCII escape codes) | |
else if (i == recent_computer_move) tmp_board[i] = "\033[1;33m" + string(1,board[i]) + "\033[0m"; // yellow for computer's move | |
else tmp_board[i] = string(1, board[i]); | |
} | |
cout << tmp_board[0] << '|' << tmp_board[1] << '|' << tmp_board[2] << endl; // X|O|X | |
cout << tmp_board[3] << '|' << tmp_board[4] << '|' << tmp_board[5] << endl; // O|X|O | |
cout << tmp_board[6] << '|' << tmp_board[7] << '|' << tmp_board[8] << endl; // X|O|X | |
} | |
// check to see if the game is over, return an int status | |
int check_for_winner(square board[9]) { // returns int winner X=0, O=1, tie=2, unfinished=-1 | |
int solutions[8][3] = {{0, 3, 6}, // vertical solutions | |
{1, 4, 7}, | |
{2, 5, 8}, | |
{0, 1, 2}, // horizontal solutions | |
{3, 4, 5}, | |
{6, 7, 8}, | |
{0, 4, 8}, // diagonal solutions | |
{2, 4, 6}}; | |
// check for win by a player | |
int index1; | |
int index2; | |
int index3; | |
for (int i=0; i<8; i++){ | |
index1 = solutions[i][0]; | |
index2 = solutions[i][1]; | |
index3 = solutions[i][2]; | |
if (board[index1] == board[index2] && board[index2] == board[index3] && board[index1] != EMPTY) { | |
if (board[index1] == X) return 0; | |
else if (board[index1] == O) return 1; | |
} | |
} | |
// check for a tie | |
for (int b=0; b<9; b++) if (board[b] == EMPTY) return -1; // return -1 if any squares are empty (game unfinished) | |
// if no winner is found, and squares are not empty, return tie | |
return 2; | |
} | |
// checks move validity, and places the move if valid then returns the int move, if invalid returns -1 | |
int place_move(square board[9], int move, square player_symbol) { | |
if (player_symbol == EMPTY) return -1; // placing an EMPTY is always invalid | |
else if (board[move] != EMPTY) return -1; // placing your move where one already exists is always invalid | |
else { | |
board[move] = player_symbol; | |
return move; | |
} | |
} | |
// asks the human for input, then places the move if its valid | |
int human_move(square board[9], square human_symbol) { // returns the move made or -1 if invalid | |
int move = -1; | |
int input_square = -1; | |
while (input_square == -1) { | |
cout << "Which square do you pick: "; | |
cin >> input_square; | |
cin.clear(); // will cause infinite loop unless input buffer is cleared between inputs | |
if (input_square == 0 && allow_skip) { | |
return 0; | |
} | |
if (input_square < 1 || input_square > 9) { | |
cout << "\nYou idiot, type numbers between 1-9 only.\n"; | |
input_square = -1; | |
} | |
else move = input_square-1; | |
} | |
int final_move = -1; | |
final_move = place_move(board, move, human_symbol); | |
if (final_move == -1) { | |
cout << "\nPlacing an " << string(1, human_symbol) << " at " << move+1 << " is invalid.\n"; // if spot is taken | |
return human_move(board, human_symbol); | |
} | |
else return final_move; | |
} | |
/* AI Functions: | |
Alpha-Beta Pruning algorithm (Minimax) | |
Big O worst case: O(|E|+|V|) -- type: depth-first | |
*/ | |
// dumb AI for gameplay demonstration and debugging when minimax_ai is broken | |
int fallback_ai(square board[9]) { | |
int sorted_board[9] = {4,0,2,6,8,1,3,5,7}; // play center, then corners, then everything else | |
for (int i=0;i<9;i++) { | |
if (board[sorted_board[i]] == EMPTY) { | |
return sorted_board[i]; | |
} | |
} | |
} | |
// returns +1, 0, or -1 for scoring of the move to determine whether it helps the computer, human, or neither | |
int judge_move(int winner, square current_player, square computer_symbol) { | |
int player; | |
if (winner == 2) return 0; // handle ties straight off the bat | |
if (current_player == X) player = 0; // convert player symbol to int for easier processing X=0, O=1 | |
else if (current_player == O) player = 1; | |
int score; | |
if (winner == player) score = 1; | |
else if (winner != player) score = -1; | |
// flip score if computer is not player who placed move | |
if (computer_symbol != current_player) { | |
if (score == 1) return -1; | |
else if (score == -1) return 1; | |
} | |
else return score; | |
} | |
// calculates which moves are viable by seeing which squares are EMPTY, returns array of bools viable_squares[] | |
bool* calc_viable(square board[9]) { | |
bool *viable_squares; | |
viable_squares = new bool [9]; | |
int a = 0; | |
for (int i=0;i<9;i++) { | |
if (board[i] == EMPTY) viable_squares[i] = true; | |
else viable_squares[i] = false; | |
} | |
return viable_squares; | |
} | |
// the recursor function that plays out every possible game and calulates scores for each, places scores in the score[] int array | |
void minimax_recursor(square *tmp_board, int score[9], square current_player, square computer_symbol) { | |
bool *viable_squares = calc_viable(tmp_board); | |
for (int m=0;m<9;m++) { | |
if (viable_squares[m] == true) { | |
tmp_board[m] = current_player; // place actual move on temporary board | |
int winner = check_for_winner(tmp_board); | |
if (winner == -1) { | |
//cout << "Begin recurse for " << m+1 << endl; | |
// flip flop the players | |
if (current_player == X) current_player = O; else current_player = X; | |
minimax_recursor(tmp_board, score, current_player, computer_symbol); | |
tmp_board[m] = EMPTY; // undo move so simulation can continue | |
if (current_player == X) current_player = O; else current_player = X; | |
} | |
else { | |
//cout << "Score[" << m+1 << "] += " << judge_move(winner, current_player, computer_symbol) << endl; | |
//print_board(tmp_board, -1, m); | |
//score[m] += judge_move(winner, current_player, computer_symbol); | |
int square_score = judge_move(winner, current_player, computer_symbol); | |
if (score[m] >= 0 && square_score > 0) { | |
score[m] += square_score; | |
} | |
else if (score[m] <= 0 && square_score < 0) { | |
score[m] <= square_score; | |
} | |
tmp_board[m] = EMPTY; // undo move so simulation can continue | |
} | |
} | |
} | |
} | |
// starts the minimax_recursor with a starting set of viable_moves, chooses the move with the best score and returns int move_made | |
int ai_move(square board[9], square computer_symbol) { | |
// copy board into tmp_board to prevent direct modification during ranking | |
square tmp_board[] = {EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY}; | |
for (int a=0;a<9;a++) tmp_board[a] = board[a]; | |
cout << "starting AI" << endl; | |
print_board(tmp_board, -1, -1); | |
// score all the possible moves recursively | |
int score[9] = {0,0,0,0,0,0,0,0,0}; | |
minimax_recursor(tmp_board, score, computer_symbol, computer_symbol); | |
int best_score[2] = {-1,0}; // position, score | |
for (int y=0;y<9;y++) { | |
cout << "Position: " << y+1 << ". Score: " << score[y] << endl; | |
if (score[y] < best_score[1]) { | |
best_score[0] = y; | |
best_score[1] = score[y]; | |
} | |
} | |
if (best_score[1] == 0) { | |
for (int y=0;y<9;y++) { | |
if (score[y] > best_score[1]) { | |
best_score[0] = y; | |
best_score[1] = score[y]; | |
} | |
} | |
} | |
int result = place_move(board, best_score[0], computer_symbol); | |
if (result == -1) { | |
cout << "\nMimixax Error: " << string(1, computer_symbol) << " at " << best_score[0]+1 << " is invalid.\n"; | |
result = place_move(board, fallback_ai(board), computer_symbol); | |
} | |
cout << "Computer chose: " << result+1 << endl; | |
return result; | |
} | |
int main () { | |
// ask user to pick which symbol they want to use | |
cout << "Choose your weapon (X/O): "; | |
char tmp_human_symbol; | |
cin >> tmp_human_symbol; | |
cin.clear(); // will cause infinite loop unless input buffer is cleared between inputs | |
square human_symbol, computer_symbol; | |
if (tmp_human_symbol == 'x' || tmp_human_symbol == 'X') { | |
human_symbol = X; computer_symbol = O; | |
} | |
else { | |
human_symbol = O; computer_symbol = X; | |
} | |
print_help(); | |
int recent_human_move, recent_computer_move = -1; | |
// Game loop | |
while (check_for_winner(board) == -1) { | |
recent_human_move = human_move(board, human_symbol); | |
if (check_for_winner(board) != -1) break; | |
recent_computer_move = ai_move(board, computer_symbol); | |
if (check_for_winner(board) != -1) break; | |
print_board(board, recent_human_move, recent_computer_move); | |
} | |
// Endgame Text | |
cout << endl; | |
print_board(board, -1, -1); // print ending state of the board with no recent moves highlighted | |
string winner; | |
int end_result = check_for_winner(board); // its a tad innefficient to keep calling this every time, who cares, its only an extra 15ms | |
if (human_symbol == X && end_result == 0) winner = "You won. (X)"; | |
else if (human_symbol == O && end_result == 1) winner = "You won. (O)"; | |
else if (computer_symbol == X && end_result == 0) winner = "Computer won. (X)"; | |
else if (computer_symbol == O && end_result == 1) winner = "Computer won. (O)"; | |
else winner = "It was a tie."; | |
cout << "\nGame is over. " << winner << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment