M,n,K- game with AI Artificial intelligence (minimax, alphabeta pruning https://
ID: 3913073 • Letter: M
Question
M,n,K- game with AI Artificial intelligence(minimax, alphabeta pruning
https://en.m.wikipedia.org/wiki/M,n,k-game
implementation m, n, k with AI(artificial intelligence) and algorithms minimax and alphabeta pruning. Develop an algorithm in python, java,C# or C++ console should receive as input the dimensions m, n, j (the player), the gamehuman versus artificial intelligence.
the constant k is a state of the game Tic-tac-toe. The player "X" is represented by the integer 1,
the player "O" by the integer 2 and blank positions on the board by the integer 0. Example of
Possible valid entries include:
input terminal / console
with passage of arguments:
Example of a 3 — 3 entry, k = 3 being played by "X".
./a.out 3 3 1 3 0 0 0 0 0 0 0 0 0
Example of a 3 — 3 entry, k = 3 being played by "O".
./a.out 3 3 2 3 1 1 2 0 0 0 2 1 0
Example of a 4 — 4 entry, k = 2 being played by "O".
./a.out 4 4 2 2 1 2 1 2 0 0 0 0 0 0 0 0 0 0 1 0
output terminal / console:
The algorithm developed should print on the standard output of the operating system the result
of the game played by the BOT through a pair of indices ij, where (i Example of a valid output:
1 1
Example of a valid output:
2 1
Explanation / Answer
This is a C++ code run it on c++ 2011 and above for compilation:
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
using std::cout;
using std::cin;
using std::endl;
#define WIN 1000
#define DRAW 0
#define LOSS -1000
#define AI_MARKER 'O'
#define PLAYER_MARKER 'X'
#define EMPTY_SPACE '-'
#define START_DEPTH 0
// Print game state
void print_game_state(int state)
{
if (WIN == state) { cout << "WIN" << endl; }
else if (DRAW == state) { cout << "DRAW" << endl; }
else if (LOSS == state) { cout << "LOSS" << endl; }
}
// All possible winning states
std::vector<std::vector<std::pair<int, int>>> winning_states
{
// Every row
{ std::make_pair(0, 0), std::make_pair(0, 1), std::make_pair(0, 2) },
{ std::make_pair(1, 0), std::make_pair(1, 1), std::make_pair(1, 2) },
{ std::make_pair(2, 0), std::make_pair(2, 1), std::make_pair(2, 2) },
// Every column
{ std::make_pair(0, 0), std::make_pair(1, 0), std::make_pair(2, 0) },
{ std::make_pair(0, 1), std::make_pair(1, 1), std::make_pair(2, 1) },
{ std::make_pair(0, 2), std::make_pair(1, 2), std::make_pair(2, 2) },
// Every diagonal
{ std::make_pair(0, 0), std::make_pair(1, 1), std::make_pair(2, 2) },
{ std::make_pair(2, 0), std::make_pair(1, 1), std::make_pair(0, 2) }
};
// Print the current board state
void print_board(char board[3][3])
{
cout << endl;
cout << board[0][0] << " | " << board[0][1] << " | " << board[0][2] << endl;
cout << "----------" << endl;
cout << board[1][0] << " | " << board[1][1] << " | " << board[1][2] << endl;
cout << "----------" << endl;
cout << board[2][0] << " | " << board[2][1] << " | " << board[2][2] << endl << endl;
}
// Get all available legal moves (spaces that are not occupied)
std::vector<std::pair<int, int>> get_legal_moves(char board[3][3])
{
std::vector<std::pair<int, int>> legal_moves;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (board[i][j] != AI_MARKER && board[i][j] != PLAYER_MARKER)
{
legal_moves.push_back(std::make_pair(i, j));
}
}
}
return legal_moves;
}
// Check if a position is occupied
bool position_occupied(char board[3][3], std::pair<int, int> pos)
{
std::vector<std::pair<int, int>> legal_moves = get_legal_moves(board);
for (int i = 0; i < legal_moves.size(); i++)
{
if (pos.first == legal_moves[i].first && pos.second == legal_moves[i].second)
{
return false;
}
}
return true;
}
// Get all board positions occupied by the given marker
std::vector<std::pair<int, int>> get_occupied_positions(char board[3][3], char marker)
{
std::vector<std::pair<int, int>> occupied_positions;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (marker == board[i][j])
{
occupied_positions.push_back(std::make_pair(i, j));
}
}
}
return occupied_positions;
}
// Check if the board is full
bool board_is_full(char board[3][3])
{
std::vector<std::pair<int, int>> legal_moves = get_legal_moves(board);
if (0 == legal_moves.size())
{
return true;
}
else
{
return false;
}
}
// Check if the game has been won
bool game_is_won(std::vector<std::pair<int, int>> occupied_positions)
{
bool game_won;
for (int i = 0; i < winning_states.size(); i++)
{
game_won = true;
std::vector<std::pair<int, int>> curr_win_state = winning_states[i];
for (int j = 0; j < 3; j++)
{
if (!(std::find(std::begin(occupied_positions), std::end(occupied_positions), curr_win_state[j]) != std::end(occupied_positions)))
{
game_won = false;
break;
}
}
if (game_won)
{
break;
}
}
return game_won;
}
char get_opponent_marker(char marker)
{
char opponent_marker;
if (marker == PLAYER_MARKER)
{
opponent_marker = AI_MARKER;
}
else
{
opponent_marker = PLAYER_MARKER;
}
return opponent_marker;
}
// Check if someone has won or lost
int get_board_state(char board[3][3], char marker)
{
char opponent_marker = get_opponent_marker(marker);
std::vector<std::pair<int, int>> occupied_positions = get_occupied_positions(board, marker);
bool is_won = game_is_won(occupied_positions);
if (is_won)
{
return WIN;
}
occupied_positions = get_occupied_positions(board, opponent_marker);
bool is_lost = game_is_won(occupied_positions);
if (is_lost)
{
return LOSS;
}
bool is_full = board_is_full(board);
if (is_full)
{
return DRAW;
}
return DRAW;
}
// Apply the minimax game optimization algorithm
std::pair<int, std::pair<int, int>> minimax_optimization(char board[3][3], char marker, int depth, int alpha, int beta)
{
// Initialize best move
std::pair<int, int> best_move = std::make_pair(-1, -1);
int best_score = (marker == AI_MARKER) ? LOSS : WIN;
// If we hit a terminal state (leaf node), return the best score and move
if (board_is_full(board) || DRAW != get_board_state(board, AI_MARKER))
{
best_score = get_board_state(board, AI_MARKER);
return std::make_pair(best_score, best_move);
}
std::vector<std::pair<int, int>> legal_moves = get_legal_moves(board);
for (int i = 0; i < legal_moves.size(); i++)
{
std::pair<int, int> curr_move = legal_moves[i];
board[curr_move.first][curr_move.second] = marker;
// Maximizing player's turn
if (marker == AI_MARKER)
{
int score = minimax_optimization(board, PLAYER_MARKER, depth + 1, alpha, beta).first;
// Get the best scoring move
if (best_score < score)
{
best_score = score - depth * 10;
best_move = curr_move;
// Check if this branch's best move is worse than the best
// option of a previously search branch. If it is, skip it
alpha = std::max(alpha, best_score);
board[curr_move.first][curr_move.second] = EMPTY_SPACE;
if (beta <= alpha)
{
break;
}
}
} // Minimizing opponent's turn
else
{
int score = minimax_optimization(board, AI_MARKER, depth + 1, alpha, beta).first;
if (best_score > score)
{
best_score = score + depth * 10;
best_move = curr_move;
// Check if this branch's best move is worse than the best
// option of a previously search branch. If it is, skip it
beta = std::min(beta, best_score);
board[curr_move.first][curr_move.second] = EMPTY_SPACE;
if (beta <= alpha)
{
break;
}
}
}
board[curr_move.first][curr_move.second] = EMPTY_SPACE; // Undo move
}
return std::make_pair(best_score, best_move);
}
// Check if the game is finished
bool game_is_done(char board[3][3])
{
if (board_is_full(board))
{
return true;
}
if (DRAW != get_board_state(board, AI_MARKER))
{
return true;
}
return false;
}
int main()
{
char board[3][3] = { EMPTY_SPACE };
cout << "******************************** Tic Tac Toe AI ********************************" << endl << endl;
cout << "Player = X AI Computer = O" << endl << endl;
print_board(board);
while (!game_is_done(board))
{
int row, col;
cout << "Row play: ";
cin >> row;
cout << "Col play: ";
cin >> col;
cout << endl << endl;
if (position_occupied(board, std::make_pair(row, col)))
{
cout << "The position (" << row << ", " << col << ") is occupied. Try another one..." << endl;
continue;
}
else
{
board[row][col] = PLAYER_MARKER;
}
std::pair<int, std::pair<int, int>> ai_move = minimax_optimization(board, AI_MARKER, START_DEPTH, LOSS, WIN);
board[ai_move.second.first][ai_move.second.second] = AI_MARKER;
print_board(board);
}
cout << "********** GAME OVER **********" << endl << endl;
int player_state = get_board_state(board, PLAYER_MARKER);
cout << "PLAYER "; print_game_state(player_state);
return 0;
}
similarly you can implement it for any commbination as for simplicity I have done it for 3*3.
Thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.