# Thread: Help with the min-max algorithm

1. ## 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)
{
// ????????
}```

2. Considering you haven't even started to write the function, its kind of hard to help. Do you have a specific question on min-max functions in general? As long as you have a function that can evaluate a board-state, most min-max's are pretty much the same.

3. Ok, so first I need a function to evaluate the board and look for a winner or a draw? Does this function have to return a specific type? Thanks.

4. caduardo21, min-max requires a min function that searches for the best evaluation with respect to the other player and a max function that searches for the best evaluation with respect to the player who's turn it is to move. Along with these two functions, you need an eval function which will statically evaluation the board. But just return an integer value here; you know this can only return three values: -1, 0, 1.

5. I'll try to understand all of this and I ask you guys to bare with me please
Code:
```int evaluate_board(const char &player)
{
int i;

for(i = 0; i < 3; i++)
{
if(board[i][0] == player && board[i][0] == player)
{
if(player == 'X')
return 1;

else
return -1;
}
}

for(i = 0; i < 3; i++)
{
if(board[0][i] == player && board[0][i] == player)
{
if(player == 'X')
return 1;

else
return -1;
}
}

if(board[0][0] == player && board[1][1] == player)
{
if(player == 'X')
return 1;

else
return -1;
}

if(board[0][2] == player && board[1][1] == player)
{
if(player == 'X')
return 1;

else
return -1;
}

// It would be good to check for a draw here also, right?

return 0;
}```

6. Have you looked on the AI board yet? You might find something vaguely useful over there. And when you figure it out, maybe you can explain to me how to write negamax.

7. I'm trying to get the min-max thingy going first, function by function

I think I've looked at your tic-tac-toe game but as I said, I am having a hard time understand this algorithm.

So, is this how the evaluation function must look like?

Thanks.

8. its not hard.

first look for a win in 1 move
if no win look to see if opponent can win in 1 move
if he can in more than 1 place then place random mark as its unstoppable
if he can win in 1 sqaure only go there
otherwise look for a strategic sqaure. how you do this is up to you.

9. What the evaluation function looks like will depend on what your board implementation looks like. For my board implementation, I chose to use two short integers to represent the moves. The first short was the moves for player 1, the other short for player 2. As an example, if the player 1 short was value 000 000 001b, that would indicate that player 1 chose to place an x in the bottom right corner, while if it was 100 000 000b, that would indicate that player 1 chose to x the top left corner. Assuming this is your board representation, you could check for a win by looking for one of the following ints:
111 000 000b
000 111 000b
000 000 111b
100 100 100b
010 010 010b
001 001 001b
(etc.)

So is your board representation correct? I have no idea. But it should return 1 if player 1 is winning, 0 if it is a cats game, and -1 if player 2 is winning. The rest depends on your particular board representation.

10. I'm using a simple multi-subscripted array:
char board[3][3];

So I think my evaluation function is correct. It returns 1 if X wins, -1 if O wins and 0 if nobody wins. Any ideas on how to catch a draw?

11. In Tic-Tac-Toe, it's very simple to give fields a tactical importance. Just calculate how many ways of winning it provides. You come up with:

3 2 3
2 4 2
3 2 3

Say, the player then places a piece in the center. The ways of winning are reduced:

2 1 2
1 X 1
2 1 2

Thus, the CPU randomly chooses one of the twos. A CPU piece does not reduce possibilities, it increases them (e.g. by 2), but it can't raise them from zero.

O 3 4
3 X 1
4 1 2

The player makes his move. This gives him a row-of-two, which leads to a big importance boost of 5.

O 0 X
3 X 0
9 1 2

The next move gives us a winning field, which raises importance by 10.

O 0 X
13X 0
O 3 4

O 0 X
X X 5
O 3 4

O 0 X
X X O
O 3 4

O 5 X
X X O
O X 4

O O X
X X O
O X 4

O O X
X X O
O X X

Draw.

Here's a winning game, CPU starts and player makes a mistake:

5 4 4
3 O X
5 4 4

O 4 4
3 O X
5 4 14

O 4 9
3 O X
4 3 X

O14 O
3 O X
14 3X

O X O
3 O X
14 0X

O X O
3 O X
O 0 X

To sum up:
1) Way a field participates in winning: +1
2) Way a field participates in winning, with another spot of such a way taken by own piece: +2 (but not if importance after 1 is 0).
3) Field is winning move for opponent: +5
4) Field is winning move for self: +10
5) Choose random among highest importances.

12. How to catch a draw: I assume that your array:

char board[3][3];

begins initialized to something like all 0. So a draw is when there are no zeros left (all slots have been chosen by 'x' or 'o'), AND there is not a win for 'x' or 'o'.

13. Since the sample space for board states is so small for tic-tac-toe, there is never a reason to evaluate the board before the end. If you simply have a function that says 'X' won, 'O' won, or all spaces are taken and noone won, then you have all you need for the min-max. The way you have it set up as -1,0,1 is perfect.

Popular pages Recent additions