Minimax for Tic Tac Toe
Author
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.
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!
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!
Author
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]
[Edited by - Onolt on February 13, 2010 11:19:02 PM]
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 :
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.
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 gameIf 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.
Author
Would something like this:
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?
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?
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.
that takes the current board and outputs the best move. Its not a data-structure.
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.
Author
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?
Quote:Original post by StoryyellerQuote: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.
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.
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; }}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
