Jump to content
  • Advertisement
Sign in to follow this  
Onolt

Minimax for Tic Tac Toe

This topic is 2186 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on a Tic Tac Toe game using SDL and C++. So far 2 people can play but recently I've been trying to implement AI so I heard about the minimax algorithm and how it's used for games like Tic Tac Toe. From what I understand you have recursive functions that look through a game-tree for the best move for either the max player or the min player to minimize or maximize their win case. I understand that much of it but what I don't understand is how would you represent all the moves that the AI could make if the Tic Tac Toe board is a 9 element array? Sorry if this is in the wrong section.

Share this post


Link to post
Share on other sites
Advertisement
Well assuming you have a class called 'Board' or something and that contains an array of 9 tiles, you could have the tiles be a seperate class and contain a data member such as:

bool inUse; // yes i know its a crappy name, you can be more creative though

that you could use in your algorithm to determine whether or not a tile is available. if it is available then you know that this tile is a possible move, or so to speak.

Im not sure if thats what you ment, ive never used the minimax algorithm, because ive never made a tic tac toe game so yeah.

good luck!

Share this post


Link to post
Share on other sites
I'm having troubles having the AI make out different moves based on the array still. Thanks for the help though.

[Edited by - Onolt on February 13, 2010 11:19:02 PM]

Share this post


Link to post
Share on other sites
Maybe go for some simpler AI that follows a certain structure first.
For example an AI following these instruction( see below ) is smarter than
an AI that just places O or X in an open spot :

AI instruction :

1) Check if AI can win, if so then place it there.
2) Check if player can win, if so then block the win by placing X or O there.
3) Check if Middle is open, if so then place it there.
4) Check if one of the four corners are open if so then :
-check if player has a spot placed in a corner if so, then place it in opposite
spot[ ex. player has a corner at index (0,0 [top left] ) then tell AI
to place X or O at (2,2[ bottom right] )
5) If all corners are occupied then place it anywhere open because it will be a
draw game


If those decision are ran by AI then AI should be pretty good against beginners
and even some intermediate. Although it does not always guarantee a win, I will
guess it about 80% of the time, it will be either a draw game or AI wins against
beginner and some intermediate.

Share this post


Link to post
Share on other sites
Would something like this:

struct node
{
node *moves[9];
int boardState[9];
int endState;
};


Be a move in the right direction? If so how would I assign the different tic tac toe move values for each possible move to the pointer to the array of 9 nodes?

Share this post


Link to post
Share on other sites
If you are trying to create minmax trees, then realize that its a function
that takes the current board and outputs the best move. Its not a data-structure.

Share this post


Link to post
Share on other sites
Quote:
Original post by Concentrate
Maybe go for some simpler AI that follows a certain structure first.
For example an AI following these instruction( see below ) is smarter than
an AI that just places O or X in an open spot :

AI instruction :

1) Check if AI can win, if so then place it there.
2) Check if player can win, if so then block the win by placing X or O there.
3) Check if Middle is open, if so then place it there.
4) Check if one of the four corners are open if so then :
-check if player has a spot placed in a corner if so, then place it in opposite
spot[ ex. player has a corner at index (0,0 [top left] ) then tell AI
to place X or O at (2,2[ bottom right] )
5) If all corners are occupied then place it anywhere open because it will be a
draw game


If those decision are ran by AI then AI should be pretty good against beginners
and even some intermediate. Although it does not always guarantee a win, I will
guess it about 80% of the time, it will be either a draw game or AI wins against
beginner and some intermediate.


I once tried to implement a hardcoded tic tac toe strategy, but it is much harder than it sounds. Even after exploiting all the symmetry, there are still so many cases that it is nearly unmanageable.

The minimax solution is much simpler and infinitely more elegant.



In fact, the first program I ever wrote in C++ was a console Tic Tac Toe game with minimax and alpha beta pruning.

Share this post


Link to post
Share on other sites
So all I would have to do is have my "int board[9]" array as the board that's passed into the function and the function will do the heavy lifting or is there more about the board that needs to be set up?

Share this post


Link to post
Share on other sites
Quote:
Original post by Storyyeller
Quote:
Original post by Concentrate
Maybe go for some simpler AI that follows a certain structure first.
For example an AI following these instruction( see below ) is smarter than
an AI that just places O or X in an open spot :

AI instruction :

1) Check if AI can win, if so then place it there.
2) Check if player can win, if so then block the win by placing X or O there.
3) Check if Middle is open, if so then place it there.
4) Check if one of the four corners are open if so then :
-check if player has a spot placed in a corner if so, then place it in opposite
spot[ ex. player has a corner at index (0,0 [top left] ) then tell AI
to place X or O at (2,2[ bottom right] )
5) If all corners are occupied then place it anywhere open because it will be a
draw game


If those decision are ran by AI then AI should be pretty good against beginners
and even some intermediate. Although it does not always guarantee a win, I will
guess it about 80% of the time, it will be either a draw game or AI wins against
beginner and some intermediate.


I once tried to implement a hardcoded tic tac toe strategy, but it is much harder than it sounds. Even after exploiting all the symmetry, there are still so many cases that it is nearly unmanageable.

The minimax solution is much simpler and infinitely more elegant.



In fact, the first program I ever wrote in C++ was a console Tic Tac Toe game with minimax and alpha beta pruning.


I didn't think it was that hard. I had an unbeatable AI following similar logic
path.

Share this post


Link to post
Share on other sites
In case you find it useful, here is the code of a minmax tree implementation I did several years ago in Java. Sorry for the lack of documentation (and for it being in italian), I don't have the time to translate it right now...
Note that the game is not Tic Tac Toe though.


//Movegen.java

/***
Questa classe si occupa di generare una mossa valida data una particolare partita.

Autore: Alessandro Caviola
***/


import java.util.Random;

class Movegen
{
protected int move_x, move_y; //Risultato della generazione di una mossa

protected int difficulty; //Grado di difficoltà del giocatore (1-3)
protected int tree_depth; //Profondità massima raggiunta dall'albero

protected Random ran;

//Valori informativi sullo stato dell'elaborazione
protected int cntr;
protected boolean test;

Movegen()
{
difficulty = 1;
tree_depth = 2;

cntr = 0;
test = false;

ran = new Random();
}

/***Genera una mossa valida per l'attuale stato della partita. Questo metodo costruisce un minmax tree
con alpha-beta pruning per selezionare una mossa. La prima mossa viene generata a caso. ***/

public String Generate(Board b, Board oldb)
{
if(b.GetTurn() == 0) //La prima mossa viene generata casualmente
{
move_x = Math.abs(ran.nextInt() % 6);
move_y = Math.abs(ran.nextInt() % 5);
return new String(Integer.toString(move_x)+Integer.toString(move_y));
}

cntr = 0;
long ttim = 0;

if(test == true) ttim = System.currentTimeMillis(); //Se richiesto registra il tempo necessario per ogni mossa

Max(b, oldb, -100000000, 100000000, tree_depth);

if(test == true) System.out.println("Calcolate "+Integer.toString(cntr)+" mosse in "+ Long.toString((System.currentTimeMillis() - ttim))+" millisecondi");
return new String(Integer.toString(move_x)+Integer.toString(move_y));
}

/***Metodo Max per la generazione del MinMax Tree. I parametri che richiede sono lo stato del gioco attuale, lo stato del gioco
precedente, il valore alpha ed il valore beta, e la profondità attuale.***/

protected int Max(Board b, Board oldb, int alpha, int beta, int depth)
{
cntr++;
int _x = 0, _y = 0;

int tmp = b.CheckForVictory(); //Controlliamo che non sia il termine della partita
if(tmp != 0)
{
if(tmp == 1) return 1000000*(tree_depth-depth); //Una vittoria più vicina è migliore
else if(tmp == 2) return -1000000*(tree_depth-depth);
}

if(depth == 0) return EvaluateGame(b, oldb, true); // Se abbiamo raggiunto la profondità massima, adottiamo l'euristica

//Nessuna vittoria
Board child = new Board();
for(int x = 0; x < 6; x++)
for(int y = 0; y < 5; y++)
{
if(!b.Verify(x, y)) continue;


child.CopyFrom(b);
child.AddFast(x, y);

tmp = Min(child, b, alpha, beta, depth-1);

if(tmp > alpha)
{
alpha = tmp;
_x = x;
_y = y;
}
if(beta < alpha)
{
move_x = _x;
move_y = _y;
return beta;
}
}
move_x = _x;
move_y = _y;
return alpha;
}

/***Metodo Min per la generazione del MinMax Tree. I parametri che richiede sono lo stato del gioco attuale, lo stato del gioco
precedente, il valore alpha ed il valore beta, e la profondità attuale.***/

protected int Min(Board b, Board oldb, int alpha, int beta, int depth)
{
cntr++;
int _x = 0, _y = 0;

int tmp = b.CheckForVictory(); //Controlliamo che non sia il termine della partita
if(tmp != 0)
{
if(tmp == 1) return 1000000*(tree_depth-depth); //Una vittoria più vicina è migliore
else if(tmp == 2) return -1000000*(tree_depth-depth);
}

if(depth == 0) return -EvaluateGame(b, oldb, false); // Se abbiamo raggiunto la profondità massima, adottiamo l'euristica

//Nessuna vittoria
Board child = new Board();
for(int x = 0; x < 6; x++)
for(int y = 0; y < 5; y++)
{
if(!b.Verify(x, y)) continue;

child.CopyFrom(b);
child.AddFast(x, y);

tmp = Max(child, b, alpha, beta, depth-1);
if(tmp < beta)
{
beta = tmp;
_x = x;
_y = y;
}
if(beta < alpha)
{
return alpha;
}
}
return beta;
}

/***Valuta lo stato del gioco assegnandone un valore alla bontà (= stima della probabilità di vittoria del giocatore 1).
Il calcolo è dato dalla somma del valore di ogni singola casella. I parametri sono lo stato del gioco attuale e quello precedente.***/

public int EvaluateGame(Board b, Board oldb, boolean player)
{
if(b.GetDiscs(false) == 0) return 1000;

int val = 0;
for(int x = 0; x < 6; x++)
for(int y = 0; y < 5; y++)
{
if(b.GetCelOwner(x, y) == player) val += EvaluateCell(b, oldb, x, y, player);
}
if(oldb != null) val += 100 * (b.GetDiscs(player) - oldb.GetDiscs(player));
return val;
}

/***Ritorna un punteggio relativo alla casella (x,y), basato sulla posizione sul tabellone di gioco presente, su quello precedente,
sulle pedine presenti e sullo stato delle caselle adiacenti.***/

private int EvaluateCell(Board b, Board oldb, int x, int y, boolean player)
{
int val = 0;

val += 50 * b.GetCelCurrent(x, y); //+50 per ogni pedina sulla casella

boolean s = true;
if(x + 1 < 6) //Non essere circondati da colonne avversarie più alte valorizza la mossa
if(b.GetCelOwner(x+1, y) != player && b.GetCelCurrent(x+1, y) > b.GetCelCurrent(x, y)) s = false;
if(x - 1 >= 0)
if(b.GetCelOwner(x-1, y) != player && b.GetCelCurrent(x-1, y) > b.GetCelCurrent(x, y)) s = false;
if(y + 1 < 5)
if(b.GetCelOwner(x, y+1) != player && b.GetCelCurrent(x, y+1) > b.GetCelCurrent(x, y)) s = false;
if(y - 1 >= 0)
if(b.GetCelOwner(x, y-1) != player && b.GetCelCurrent(x, y-1) > b.GetCelCurrent(x, y)) s = false;

if(s == true) val += 100; //+100 se vicino non ci sono colonne avversarie più alte

if(oldb != null) //Far esplodere una casella è positivo
if((oldb.GetCelOwner(x, y) == player) && oldb.GetCelMax(x, y) - oldb.GetCelCurrent(x, y) == 0) val += 100;

if(x == 0 || x == 5) val += 5; //+5 se è lungo i bordi, +10 se è agli angoli
if(y == 0 || y == 4) val += 5;

return val;
}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!