Public Group

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.

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 on other sites
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 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 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 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 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 on other sites
Quote:
 Original post by ConcentrateMaybe go for some simpler AI that follows a certain structure first. For example an AI following these instruction( see below ) is smarter thanan 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 gameIf those decision are ran by AI then AI should be pretty good against beginnersand even some intermediate. Although it does not always guarantee a win, I willguess it about 80% of the time, it will be either a draw game or AI wins againstbeginner 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 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 on other sites
Quote:
Original post by Storyyeller
Quote:
 Original post by ConcentrateMaybe go for some simpler AI that follows a certain structure first. For example an AI following these instruction( see below ) is smarter thanan 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 gameIf those decision are ran by AI then AI should be pretty good against beginnersand even some intermediate. Although it does not always guarantee a win, I willguess it about 80% of the time, it will be either a draw game or AI wins againstbeginner 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 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 &lt; 6; x++)      for(int y = 0; y &lt; 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 &gt; alpha)       {        alpha = tmp;        _x = x;        _y = y;      }      if(beta &lt; 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 &lt; 6; x++)      for(int y = 0; y &lt; 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 &lt; beta)       {        beta = tmp;        _x = x;        _y = y;      }      if(beta &lt; 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 &lt; 6; x++)      for(int y = 0; y &lt; 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 &lt; 6) //Non essere circondati da colonne avversarie più alte valorizza la mossa      if(b.GetCelOwner(x+1, y) != player && b.GetCelCurrent(x+1, y) &gt; b.GetCelCurrent(x, y)) s = false;    if(x - 1 &gt;= 0)      if(b.GetCelOwner(x-1, y) != player && b.GetCelCurrent(x-1, y) &gt; b.GetCelCurrent(x, y)) s = false;    if(y + 1 &lt; 5)      if(b.GetCelOwner(x, y+1) != player && b.GetCelCurrent(x, y+1) &gt; b.GetCelCurrent(x, y)) s = false;    if(y - 1 &gt;= 0)      if(b.GetCelOwner(x, y-1) != player && b.GetCelCurrent(x, y-1) &gt; 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;  }}

1. 1
2. 2
3. 3
4. 4
Rutin
17
5. 5

• 11
• 34
• 12
• 12
• 11
• Forum Statistics

• Total Topics
631412
• Total Posts
2999939
×