Help with the min-max algorithm
Hi. A couple of days ago I posted the code for a dumb tic-tac-toe game I wrote and asked for ideas on how to make it smart. People told me to use the min-max algorithm and also provided me with source code to look at. Since then, I've read a lot about the min-max algorithm and looked at other people's source code but I am having a REALLY hard time trying to implement it on my code. Can someone look at my code and give me some hints on how to do it? Thanks a lot.
Code:
#include <iostream>
#include <string>
#include <cctype>
#include <windows.h>
void show_board(void);
void human_move(void);
void computer_move(void);
bool valid_coordinate(std::string &);
char check_board(void);
char board[3][3];
int main()
{
char result = ' ';
SetConsoleTitle("Tic-Tac-Toe");
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
board[i][j] = ' ';
show_board();
while(result == ' '){
human_move();
show_board();
result = check_board();
if(result == 'X')
{
std::cout << "\nYou win!\n";
break;
}
computer_move();
show_board();
result = check_board();
if(result == 'O')
{
std::cout << "\nI win!\n";
break;
}
}
std::cin.get();
return 0;
}
void show_board(void)
{
// Change or remove this if the compiler gives you erros
system("cls");
std::cout << " A B C\n\n";
for(int j = 0; j < 3; j++){
std::cout << j + 1 << " "
<< board[j][0] << " | "
<< board[j][1] << " | "
<< board[j][2] << '\n';
if(j != 2)
std::cout << " ---|---|---\n";
}
std::cout << '\n';
}
void human_move(void)
{
std::string coordinate;
do{
std::cout << "Coordinates for X: ";
std::getline(std::cin, coordinate);
}while(!valid_coordinate(coordinate));
}
bool valid_coordinate(std::string &coordinate)
{
if(coordinate.length() == 0){
std::cout << "You must provide the coordinates for X ";
std::cin.get();
show_board();
return false;
}
if(coordinate.length() > 2){
std::cout << "Coordinates cannot be more than two characters long ";
std::cin.get();
show_board();
return false;
}
if(!isdigit(coordinate[0]) || !isalpha(coordinate[1])){
std::cout << "Type a number followed by a letter. Ex: 1a ";
std::cin.get();
show_board();
return false;
}
int x = coordinate[0];
x -= 48;
if(x < 1 || x > 3){
std::cout << "Number out of range 1-3 ";
std::cin.get();
show_board();
return false;
}
// C++ starts counting at 0, that's why I do this
x--;
char z = coordinate[1];
if(toupper(z) < 'A' || toupper(z) > 'C'){
std::cout << "Letter out of range A-C ";
std::cin.get();
show_board();
return false;
}
int y;
switch(toupper(z)){
case 'A':
y = 0;
break;
case 'B':
y = 1;
break;
case 'C':
y = 2;
break;
}
// Check if the position is free
if(board[x][y] != ' '){
std::cout << "This position is already taken ";
std::cin.get();
show_board();
return false;
}
// Makes the move
board[x][y] = 'X';
return true;
}
char check_board(void)
{
int i;
for(i = 0; i < 3; i++)
if(board[i][0] == board[i][1] && board[i][0] == board[i][2])
return board[i][0];
for(i = 0; i < 3; i++)
if(board[0][i] == board[1][i] && board[0][i] == board[2][i])
return board[0][i];
if(board[0][0] == board[1][1] && board[1][1] == board[2][2])
return board[0][0];
if(board[0][2] == board[1][1] && board[1][1] == board[2][0])
return board[0][2];
return ' ';
}
void computer_move(void)
{
// ????????
}