271 lines
No EOL
5.7 KiB
C++
271 lines
No EOL
5.7 KiB
C++
#include <iostream>
|
|
#include <string>
|
|
#include <vector>
|
|
#include <climits>
|
|
|
|
using namespace std;
|
|
|
|
int game_over(const int dimension, vector<vector<int>> &grid);
|
|
int min(const int dimension, vector<vector<int>> &grid, int &x, int &y);
|
|
int max(const int dimension, vector<vector<int>> &grid, int &x, int &y);
|
|
|
|
void print_grid(const int dimension, vector<vector<int>> &grid) {
|
|
for (int y = 0; y < dimension; y++) {
|
|
for (int x = 0; x < 2 * dimension + 1; x++) {
|
|
cout << '-';
|
|
}
|
|
cout << endl;
|
|
for (int x = 0; x < dimension; x++) {
|
|
if (x == 0) {
|
|
cout << '|';
|
|
}
|
|
if (grid[x][y] > 0) {
|
|
cout << 'X';
|
|
} else if (grid [x][y] < 0) {
|
|
cout << 'O';
|
|
} else {
|
|
cout << ' ';
|
|
}
|
|
cout << '|';
|
|
}
|
|
cout << endl;
|
|
if (y == dimension - 1) {
|
|
for (int x = 0; x < 2 * dimension + 1; x++) {
|
|
cout << '-';
|
|
}
|
|
cout << endl;
|
|
}
|
|
}
|
|
}
|
|
|
|
int max(const int dimension, vector<vector<int>> &grid, int &x, int &y) {
|
|
int n = game_over(dimension, grid);
|
|
if (n == 2) return 0;
|
|
else if (n == 1) return 1;
|
|
else if (n == -1) return -1;
|
|
|
|
int value = INT_MIN;
|
|
for (int y_ = 0; y_ < dimension; y_++) {
|
|
for (int x_ = 0; x_ < dimension; x_++) {
|
|
if (grid[y_][x_] != 0) continue;
|
|
int old_x = x;
|
|
int old_y = y;
|
|
grid[y_][x_] = 1;
|
|
int next_val = min(dimension, grid, x, y);
|
|
if (next_val > value) {
|
|
value = next_val;
|
|
x = x_;
|
|
y = y_;
|
|
} else {
|
|
x = old_x;
|
|
y = old_y;
|
|
}
|
|
grid[y_][x_] = 0;
|
|
}
|
|
}
|
|
return value;
|
|
}
|
|
|
|
int min(const int dimension, vector<vector<int>> &grid, int &x, int &y) {
|
|
int n = game_over(dimension, grid);
|
|
if (n == 2) return 0;
|
|
else if (n == 1) return 1;
|
|
else if (n == -1) return -1;
|
|
|
|
int value = INT_MAX;
|
|
for (int y_ = 0; y_ < dimension; y_++) {
|
|
for (int x_ = 0; x_ < dimension; x_++) {
|
|
if (grid[y_][x_] != 0) continue;
|
|
int old_x = x;
|
|
int old_y = y;
|
|
grid[y_][x_] = -1;
|
|
int next_val = max(dimension, grid, x, y);
|
|
if (next_val < value) {
|
|
value = next_val;
|
|
x = x_;
|
|
y = y_;
|
|
} else {
|
|
x = old_x;
|
|
y = old_y;
|
|
}
|
|
grid[y_][x_] = 0;
|
|
}
|
|
}
|
|
return value;
|
|
}
|
|
|
|
/*
|
|
Check if game is over.
|
|
returns:
|
|
-1 if bot won
|
|
0 if game is not over
|
|
1 if player won
|
|
2 if tie
|
|
*/
|
|
int game_over(const int dimension, vector<vector<int>> &grid) {
|
|
// check rows
|
|
for (int y = 0; y < dimension; y++) {
|
|
int sum = 0;
|
|
for (int x = 0; x < dimension; x++) {
|
|
sum += grid[x][y];
|
|
}
|
|
if (sum == dimension) {
|
|
return 1;
|
|
} else if (sum == -dimension) {
|
|
return -1;
|
|
}
|
|
sum = 0;
|
|
}
|
|
|
|
// check columns
|
|
for (int x = 0; x < dimension; x++) {
|
|
int sum = 0;
|
|
for (int y = 0; y < dimension; y++) {
|
|
sum += grid[x][y];
|
|
}
|
|
if (sum == dimension) {
|
|
return 1;
|
|
} else if (sum == -dimension) {
|
|
return -1;
|
|
}
|
|
sum = 0;
|
|
}
|
|
|
|
// check first diagonal
|
|
int sum = 0;
|
|
for (int n = 0; n < dimension; n++) {
|
|
sum += grid[n][n];
|
|
}
|
|
if (sum == dimension) {
|
|
return 1;
|
|
} else if (sum == -dimension) {
|
|
return -1;
|
|
}
|
|
|
|
// check second diagonal
|
|
sum = 0;
|
|
for (int n = 1; n <= dimension; n++) {
|
|
sum += grid[dimension - n][n - 1];
|
|
}
|
|
if (sum == dimension) {
|
|
return 1;
|
|
} else if (sum == -dimension) {
|
|
return -1;
|
|
}
|
|
|
|
// check if grid is full
|
|
for (int y = 0; y < dimension; y++) {
|
|
for (int x = 0; x < dimension; x++) {
|
|
if (grid[x][y] == 0) return 0;
|
|
}
|
|
}
|
|
return 2;
|
|
}
|
|
|
|
bool parse_move(string move, int &x, int &y) {
|
|
// split string on comma
|
|
string x_str;
|
|
string y_str;
|
|
int pos = move.find(',');
|
|
|
|
// error if no comma found
|
|
if (pos == string::npos) {
|
|
return false;
|
|
}
|
|
|
|
// split on ','
|
|
x_str = move.substr(0, pos);
|
|
y_str = move.substr(pos + 1, move.length() - 1 - pos);
|
|
|
|
// convert to int
|
|
int x_local = stoi(x_str);
|
|
int y_local = stoi(y_str);
|
|
|
|
// check conversion and return expected result
|
|
if (x_local != -1 && y_local != -1) {
|
|
x = x_local;
|
|
y = y_local;
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
void player_move(const int dimension, vector<vector<int>> &grid) {
|
|
string move;
|
|
int x;
|
|
int y;
|
|
while (true) {
|
|
print_grid(dimension, grid);
|
|
cout << "Enter a valid move. (Format is 'x,y')" << endl;
|
|
cin >> move;
|
|
if (!parse_move(move, x, y)) {
|
|
cout << "Couldn't parse move." << endl;
|
|
continue;
|
|
}
|
|
if (x < 0 || y < 0 || x >= dimension || y >= dimension) {
|
|
cout << "Coordinates out of bounds." << endl;
|
|
continue;
|
|
}
|
|
break;
|
|
}
|
|
grid[x][y] = 1;
|
|
}
|
|
|
|
void computer_move(const int dimension, vector<vector<int>> &grid) {
|
|
int x;
|
|
int y;
|
|
min(dimension, grid, x, y);
|
|
grid[y][x] = -1;
|
|
}
|
|
|
|
|
|
/* Play one game of tic tac toe,
|
|
/* returns 0 if the player won and 1 if the computer won.
|
|
*/
|
|
int play_game(const int dimension) {
|
|
/* Grid representing the tic-tac-toe field.
|
|
0 is empty,
|
|
1 is human,
|
|
-1 is computer.
|
|
*/
|
|
vector<vector<int>> grid;
|
|
for (int y = 0; y < dimension; y++) {
|
|
grid.push_back({});
|
|
for (int x = 0; x < dimension; x++) {
|
|
grid[y].push_back(0);
|
|
}
|
|
}
|
|
// Query for starting player
|
|
int startPlayer = -1;
|
|
while (startPlayer != 0 && startPlayer != 1) {
|
|
cout << "Which player should start? (0 - You, 1 - Program)" << endl;
|
|
cin >> startPlayer;
|
|
}
|
|
|
|
// Do move according to startPlayer
|
|
if (startPlayer == 1) {
|
|
computer_move(dimension, grid);
|
|
}
|
|
|
|
while(true) {
|
|
player_move(dimension, grid);
|
|
if (game_over(dimension, grid) != 0) break;
|
|
computer_move(dimension, grid);
|
|
if (game_over(dimension, grid) != 0) break;
|
|
}
|
|
|
|
|
|
return 0;
|
|
}
|
|
|
|
int main(int argc, char *argv[]) {
|
|
// for (int y = 0; y < DIMENSION; y++) {
|
|
// for (int x = 0; x < DIMENSION; x++) {
|
|
// grid[x][y] = 1;
|
|
// }
|
|
// }
|
|
|
|
play_game(3);
|
|
|
|
} |