Skip to content

Instantly share code, notes, and snippets.

@phoemur
Created April 11, 2018 22:34
Show Gist options
  • Save phoemur/4773972760823156e8bb10e6db751758 to your computer and use it in GitHub Desktop.
Save phoemur/4773972760823156e8bb10e6db751758 to your computer and use it in GitHub Desktop.
Exemplo para o VOL. Compilar com: g++ -o tictactoe tictactoe.cpp
#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <utility>
//print instructions
void instructions(const std::array<std::array<char, 3> ,3>& board)
{
std::cout << "Choose a cell numbered from 1 to 9 as below\n and play\n\n";
int C=1;
auto N = board.size();
for (decltype(N) i=0; i<N; ++i) {
for (decltype(N) j=0; j<N; ++j) {
std::cout << " " << C++ << (j < N-1 ? " |" : "\n");
}
if (i < N-1) {
std::cout << "-----------\n";
}
}
}
// print the board
void print_board(const std::array<std::array<char, 3> ,3>& board)
{
auto N = board.size();
for (decltype(N) i=0; i<N; ++i) {
for (decltype(N) j=0; j<N; ++j) {
std::cout << " " << board[i][j] << (j < N-1 ? " |" : "\n");
}
if (i < N-1) {
std::cout << "-----------\n";
}
}
std::cout << std::endl;
}
// check if the game is over
bool has_moves_left(const std::array<std::array<char, 3> ,3>& board)
{
for (auto& row: board)
for (auto& cell: row)
if (cell == ' ')
return true;
return false;
}
// returns (row, col) coordinate of given cell
// transforms the cell number [1..9] into coordinates (x,y) of matrix
inline std::pair<int,int> get_coordinates(int val)
{
if (val < 1 || val > 9) throw std::runtime_error("");
return std::pair<int,int> ((val-1)/3, (val-1)%3);
}
// This is the evaluation function as discussed
int evaluate(const std::array<std::array<char, 3> ,3>& b)
{
// Checking for Rows for X or O victory.
for (int row = 0; row<3; row++)
{
if (b[row][0]==b[row][1] &&
b[row][1]==b[row][2])
{
if (b[row][0]=='x')
return +10;
else if (b[row][0]=='o')
return -10;
}
}
// Checking for Columns for X or O victory.
for (int col = 0; col<3; col++)
{
if (b[0][col]==b[1][col] &&
b[1][col]==b[2][col])
{
if (b[0][col]=='x')
return +10;
else if (b[0][col]=='o')
return -10;
}
}
// Checking for Diagonals for X or O victory.
if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
{
if (b[0][0]=='x')
return +10;
else if (b[0][0]=='o')
return -10;
}
if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
{
if (b[0][2]=='x')
return +10;
else if (b[0][2]=='o')
return -10;
}
// Else if none of them have won then return 0
return 0;
}
// This is the minimax function. It considers all
// the possible ways the game can go and returns
// the value of the board
int minimax(std::array<std::array<char, 3> ,3>& board,
int depth,
bool isMax)
{
int score = evaluate(board);
// If Maximizer has won the game return his/her
// evaluated score minus depth (to make it smarter)
if (score == 10)
return score - depth;
// If Minimizer has won the game return his/her
// evaluated score plus depth (to make it smarter)
if (score == -10)
return score + depth;
// If there are no more moves and no winner then
// it is a tie
if (!has_moves_left(board))
return 0;
// If this maximizer's move
if (isMax)
{
int best = -1000;
// Traverse all cells
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
{
// Check if cell is empty
if (board[i][j]==' ')
{
// Make the move
board[i][j] = 'x';
// Call minimax recursively and choose
// the maximum value
best = std::max( best,
minimax(board, depth+1, !isMax) );
// Undo the move
board[i][j] = ' ';
}
}
}
return best;
}
// If this minimizer's move
else
{
int best = 1000;
// Traverse all cells
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
{
// Check if cell is empty
if (board[i][j]==' ')
{
// Make the move
board[i][j] = 'o';
// Call minimax recursively and choose
// the minimum value
best = std::min(best,
minimax(board, depth+1, !isMax));
// Undo the move
board[i][j] = ' ';
}
}
}
return best;
}
}
std::pair<int,int> find_best_move(std::array<std::array<char, 3> ,3>& board)
{
int bestVal = -1000, row = -1, col = -1;
// Traverse all cells, evalutae minimax function for
// all empty cells. And return the cell with optimal
// value.
for (int i = 0; i<3; i++)
{
for (int j = 0; j<3; j++)
{
// Check if celll is empty
if (board[i][j]==' ')
{
// Make the move
board[i][j] = 'x';
// compute evaluation function for this
// move.
int moveVal = minimax(board, 0, false);
// Undo the move
board[i][j] = ' ';
// If the value of the current move is
// more than the best value, then update
// best/
if (moveVal > bestVal)
{
row = i;
col = j;
bestVal = moveVal;
}
}
}
}
return std::pair<int,int>(row, col);
}
int main()
{
std::array<std::array<char, 3> ,3> board {{{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '}}};
instructions(board);
std::cout << "--------------------\n\n" << std::endl;
do {
print_board(board);
std::string input;
std::cout << "Enter your move: ";
getline(std::cin, input);
if (input == "exit") exit(0);
int val;
std::pair<int,int> coord;
try {
if (input.size() == 0) throw std::runtime_error("");
val = stol(input);
coord = get_coordinates(val);
if (board[coord.first][coord.second] == ' ') {
board[coord.first][coord.second] = 'o';
}
else {throw std::runtime_error("");}
}
catch (...) {
std::cout << "Invalid Input\n";
continue;
}
int score = evaluate(board);
if (score == -10) {
print_board(board);
std::cout << "YOU WIN!!\n\n";
exit(0);
}
else if (score == +10) {
print_board(board);
std::cout << "YOU LOOSE!!\n\n";
exit(0);
}
// Now Computer turn
auto best = find_best_move(board);
if (board[best.first][best.second] == ' ') {
board[best.first][best.second] = 'x';
score = evaluate(board);
if (score == -10) {
print_board(board);
std::cout << "YOU WIN!!\n\n";
exit(0);
}
else if (score == +10) {
print_board(board);
std::cout << "YOU LOOSE!!\n\n";
exit(0);
}
}
} while (has_moves_left(board));
print_board(board);
std::cout << "DRAW!!\n\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment