Sign in to follow this  
Onolt

Minimax for Tic Tac Toe

Recommended Posts

Onolt    105
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
CodeCriminal    290
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
Onolt    105
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
Concentrate    181
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
Onolt    105
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
Storyyeller    215
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
Onolt    105
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
Concentrate    181
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
cignox1    735
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
Ohforf sake    2052
Quote:
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.


Are you sure about this? I once heard that all cases could fit on a single sheet of paper.

One detail to keep in mind about pure minimax is that it plays towards the best outcome given that both players play optimal, which in tic tac toe is a draw.
It doesn't try to fool the opponent into traps, because it assumes that the opponent won't fall for them.

Edit: fixed typo...

Share this post


Link to post
Share on other sites
Crowseye    308
Quote:
Original post by Ohforf sakeOne detail to keep in mind about pure minimax is that it plays towards the best outcome given that both players play optimal, which in tic tac toe is a draw.
It doesn't try to fool the opponent into traps, because it assumes that the opponent won't fall for them.


This is the one problem with using minimax for TTT. The computer will play a guaranteed winning move at any point in the game if one exists, but it otherwise doesn't differentiate between moves that it anticipates leading to a draw as it assumes the player will always make the proper move. For example, even though playing a corner to start forces the opponent into a single move (in the middle), the computer will play anywhere because it assumes the player will always play in the middle if it chooses a corner, etc. etc.


At any rate, I have a TTT game written in C++ in which my AI uses minimax. I have it set up with a Board class, but that isn't strictly necessary. You should also be able to implement it similar to the following pseudocode.

You will want a function that returns a "score" from the perspective of the computer player using the function you use to check your game board for the current game state:


int EvaluateBoard(board)
{
int nGameState = CheckGameState(board);
if(nGameState == computer wins) return large positive int; (LARGE_INT)
if(nGameState == player wins) return large negative int; (-LARGE_INT)
if(nGameState == draw) return 0;
return -1; //still playing
}



A function that generates a container of available moves from a board is also helpful:


container<int> GetValidMoves(board)
{
container<int> nContainer;
for(each location on the board)
{
if(location is not occupied)
nContainer.push_back(location);
}
return nContainer;
}



Your Minimax function takes a board and returns a move. It will utilize a Min (and via Min, a Max) function that takes a board and returns a score.

int MiniMax(board)
{
int nBestScore = -LARGE_INT; //stores the best score evaluated, initially set to the value associated with a human player win
container<int> nBestMoves; //container to store the moves yielding the nBestScore;

container<int> nValidMoves;
nValidMoves = GetValidMoves(board) //valid moves for the board

while(!(nValidMoves.empty())) //we're going to loop over all of the valid moves
{
SetSquare(board, nValidMoves.front(), ComputerPiece); //set the square associated with the first valid move to the computer's piece
int nScore = Min(board); //call the int Min(board) function which ultimately will return a score based on the final board state
if(nScore > nBestScore)
{
nBestScore = nScore; //the score becomes our new best score
nBestMoves.clear(); //we have a new best score, so our best moves are no longer the best, get rid of them
nBestMove.push_back(nValidMoves.front()); //add the move to the best moves container
}
else if (nScore == nBestScore)
{
nBestMove.push_back(nValidMoves.front()); //add the move to the best moves container
}
SetSquare(board, nValidMoves.front(), EmptyPiece); //return the square to its original state
nValidMoves.pop_front(); //we're finally done with the move, discard it
}

return (random move from your nBestMoves container); //choose a random move from your best moves to add some variety
}



int Min(board) returns a score based on the final board state, it calls Max (which in turn calls Min), until a GameOver state is reached:

int Min(board)
{
int nMoveScore = EvaluateBoard(board);
if(!(nMoveScore == -1)) return nScore; //if we're not still playing, the game is over so return the score;

int nBestScore = LARGE_INT; //Min is from the player's perspective, from which LARGE_INT represents a loss
container<int> nValidMoves;
nValidMoves = GetValidMoves(board);

while(!(nValidMoves.empty()))
{
SetSquare(board, nValidMoves.front(), PlayerPiece); //set the square to the player piece
int nScore = Max(board); //we've made a move, so evaluate the board from the other player's perspective

if(nScore < nBestScore) //if we found a better move for the human player
{
nBestScore = nScore;
}
SetSquare(board, nValidMoves.front(), EmptyPiece); //reset the square;
nValidMoves.pop_front();
}

return nBestScore;
}



int Max(board) is the same as Min except from the computer player's perspective, so swap -LARGE_INT for LARGE_INT, (nScore > nBestScore) for (nScore < nBestScore), ComputerPiece for PlayerPiece, and Min(board) for Max(board).

I'm sure this can be streamlined, but for a Tic-Tac-Toe game where at most you are evaluating 9 moves, it's not really necessary IMO.

[Edited by - Crowseye on February 15, 2010 12:52:08 PM]

Share this post


Link to post
Share on other sites
jwezorek    2663
From wikipedia:
Quote:

A player can play perfect tic-tac-toe if they choose the move with the highest priority in the following table[3].

1. Win: If you have two in a row, play the third to get three in a row.
2. Block: If the opponent has two in a row, play the third to block them.
3. Fork: Create an opportunity where you can win in two ways.
4. Block Opponent's Fork:

Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)
Option 2: If there is a configuration where the opponent can fork, block that fork.

5. Center: Play the center.
6. Opposite Corner: If the opponent is in the corner, play the opposite corner.
7. Empty Corner: Play in a corner square.
8. Empty Side: Play in a middle square on any of the 4 sides.

Share this post


Link to post
Share on other sites
paso87    100
Hi guyz,

I am new to this forum so Hello to everyone.

I am working on my tic tac toe and i did not manage to get an ideea how to do AI player. I want to use min max algorithm but i cant get it ... i was searching on the internet and i got some solution but i didn't get them..
how can i do my AI ? how should i use min max? i am using c++. Does anyone has a TTT that is not so complicated to understand how min max is implemented in c++ ?
thank you

Share this post


Link to post
Share on other sites
alvaro    21266
It's probably best if you show us your own attempt. Explain what part you are having problems with and we'll help you.

If you don't know where to start, write a Board class that contains the game position and which can answer questions like "what moves are available" and "is the game over".

Share this post


Link to post
Share on other sites
paso87    100
Until now i have made the game for 2 players.
Now i must move the second player to AI.
I only have the code for 2player game. I replaced the 2nd player with a random move but i have no ideea how to get it on to be truly inteligent. I have pseudocode for minimax but i dont know how to implement it and build the tree.
My board consists of a vector with 9 positions.I have a function win that checks is there are 3 positions for winning.

should i post the code for 2 players?
Thanks.

Share this post


Link to post
Share on other sites
alvaro    21266
See if this helps you. I didn't comment it, but I wrote it in a straight-forward manner so it will be easy to follow. I wrote a function pick_move that analyzes the root and a separate function negamax that analyzes any other node. This might not be very important for this very simple case, but it's a good idea if you are going to use it for a more interesting game: pick_move is where you would do things like time control and iterative deepening.

[code]#include <iostream>
#include <cstdlib>
#include <ctime>
#include <limits>

int opponent(int player) {
return 3-player;
}

class Board {
int a[9];
int length;

public:
Board() : length(0) {
for (int i=0; i<9; ++i)
a[i] = 0;
}

int to_move() const {
return 1 + (length % 2);
}

int game_length() const {
return length;
}

bool is_valid_move(int square) const {
return square >= 0 && square < 9 && a[square] == 0;
}

int generate_moves(int *moves) const {
int n_moves = 0;

for (int i=0; i<9; ++i) {
if (a[i] == 0)
moves[n_moves++] = i;
}

return n_moves;
}

void play_move(int square) {
a[square] = to_move();
++length;
}

void undo_move(int square) {
a[square] = 0;
--length;
}

bool is_game_over(int *result) const {
if (a[4] == 1) {
if (a[0] == 1 && a[8] == 1) {*result = 1; return true;}
if (a[1] == 1 && a[7] == 1) {*result = 1; return true;}
if (a[2] == 1 && a[6] == 1) {*result = 1; return true;}
if (a[3] == 1 && a[5] == 1) {*result = 1; return true;}
}
else if (a[4] == 2) {
if (a[0] == 2 && a[8] == 2) {*result = 2; return true;}
if (a[1] == 2 && a[7] == 2) {*result = 2; return true;}
if (a[2] == 2 && a[6] == 2) {*result = 2; return true;}
if (a[3] == 2 && a[5] == 2) {*result = 2; return true;}
}

if (a[0] == 1) {
if (a[1] == 1 && a[2] == 1) {*result = 1; return true;}
if (a[3] == 1 && a[6] == 1) {*result = 1; return true;}
}
else if (a[0] == 2) {
if (a[1] == 2 && a[2] == 2) {*result = 2; return true;}
if (a[3] == 2 && a[6] == 2) {*result = 2; return true;}
}

if (a[8] == 1) {
if (a[7] == 1 && a[6] == 1) {*result = 1; return true;}
if (a[5] == 1 && a[2] == 1) {*result = 1; return true;}
}
else if (a[8] == 2) {
if (a[7] == 2 && a[6] == 2) {*result = 2; return true;}
if (a[5] == 2 && a[2] == 2) {*result = 2; return true;}
}

for (int i=0; i<9; ++i) {
if (a[i] == 0)
return false;
}

*result = 0;
return true;
}

void print() const {
for (int i=0; i<3; ++i) {
for (int j=0; j<3; ++j)
std::cout << "_xo"[a[6-3*i+j]] << ' ';
std::cout << '\n';
}
}
};

int negamax(Board &b) {
int result;
if (b.is_game_over(&result))
return result == 0 ? -100+(std::rand()%201) : -1000 + b.game_length();

int moves[9];
int n_moves = b.generate_moves(moves);

int best_score = -1000;
for (int i=0; i<n_moves; ++i) {
b.play_move(moves[i]);
int score = -negamax(b);
b.undo_move(moves[i]);
if (score > best_score)
best_score = score;
}

return best_score;
}

int pick_move(Board &b) {
int moves[9];
int n_moves = b.generate_moves(moves);

int best_score = -1000;
int best_move = moves[0];
for (int i=0; i<n_moves; ++i) {
b.play_move(moves[i]);
int score = -negamax(b);
b.undo_move(moves[i]);
if (score > best_score) {
best_score = score;
best_move = moves[i];
}
}

return best_move;
}

int main() {
std::srand(std::time(0));

Board b;
int result;
while (b.print(),!b.is_game_over(&result)) {
int move;
if (b.to_move() == 2) {
while (!(std::cin >> move) || !b.is_valid_move(--move)) {
std::cout << "Invalid move\n";
std::cin.clear();
std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}
}
else
move = pick_move(b);
b.play_move(move);
std::cout << '\n';

}
char const *result_names[3] = {"draw", "x wins", "o wins"};
std::cout << "Result: " << result_names[result] << '\n';
}

[/code]

Let me know if there's anything in there you don't understand. Notice how you don't actually need to build the tree at all: You simply explore branches of a virtual tree using depth-first search, but you never have more than one branch of the tree in memory at any given time.

EDIT: Oh, at the very least I should tell you that the players are 1 and 2, 0 means empty and you enter board positions using the numeric keyboard, although internally the program uses 0, 1, 2, 3, 4, 5, 6, 7, 8 instead of 1, 2, 3, 4, 5, 6, 7, 8, 9.

Share this post


Link to post
Share on other sites
Jeremy Stover    104
I was lookign through my code, and I founf my problem. It wasn't returning the game over right, and it was throwing me into an infinite loop lol. Sorry for being an ahole :P Edited by KadajettGaming

Share this post


Link to post
Share on other sites
Jaap85    263
i dont see the error in your code here yet. What happens to the value of nValidMoves.Count in the endless loop? Does it decrease and increase? Or does it stay the same? Also, what does the SetSquare function do exactly. Do you have the code for that?

Share this post


Link to post
Share on other sites
Jeremy Stover    104
Ok, I have been looking through this relentlessly, Still throwing me into an infinite loop. Could you guys look through my new code when you have a chance and see what my problem is. Thanks a bunch for all your help.

[source lang="csharp"] public Vector2 updateMINIMAX()
{
int bestscore = -1000;
List<Vector2> bestMoves = new List<Vector2>();

List<Vector2> nValidMoves;
nValidMoves = allNodes[0, 0].validMoves();

while (nValidMoves.Count != 0)
{
allNodes[0, 0].setNewMove(nValidMoves.First<Vector2>(), 2);

int nscore = Min(allNodes[0,0]);

if (nscore > bestscore)
{
bestscore = nscore;
bestMoves.Clear();
bestMoves.Add(nValidMoves.First<Vector2>());
}
else if (nscore == bestscore)
{
bestMoves.Add(nValidMoves.First<Vector2>());
}
allNodes[0, 0].setNewMove(nValidMoves.First<Vector2>(), 0);

nValidMoves.Remove(nValidMoves.First<Vector2>());

}

return bestMoves.First<Vector2>();

}




private int Min(Board tempBoard)
{
int moveScore = tempBoard.winCheck();
if (moveScore != 0)
return moveScore;

int nBestScore = 1000;
List<Vector2> nValidMoves;
nValidMoves = tempBoard.validMoves();

while (nValidMoves.Count != 0)
{
tempBoard.setNewMove(nValidMoves.First<Vector2>(), 1);

int nScore = Max(tempBoard);

if (nScore < nBestScore)
{
nBestScore = nScore;
}
allNodes[0, 0].setNewMove(nValidMoves.First<Vector2>(), 0);
nValidMoves.Remove(nValidMoves.First<Vector2>());
}

return nBestScore;
}



private int Max(Board tempBoard)
{
int moveScore = tempBoard.winCheck();
if (moveScore != 0)
return moveScore;

int nBestScore = -1000;
List<Vector2> nValidMoves;
nValidMoves = tempBoard.validMoves();

while (nValidMoves.Count != 0)
{
tempBoard.setNewMove(nValidMoves.First<Vector2>(), 2);

int nScore = Min(tempBoard);

if (nScore > nBestScore)
{
nBestScore = nScore;
}
allNodes[0, 0].setNewMove(nValidMoves.First<Vector2>(), 0);
nValidMoves.Remove(nValidMoves.First<Vector2>());
}

return nBestScore;
}
[/source]

Share this post


Link to post
Share on other sites
Jeremy Stover    104
[quote name='Jaap85' timestamp='1340828179' post='4953441']
i dont see the error in your code here yet. What happens to the value of nValidMoves.Count in the endless loop? Does it decrease and increase? Or does it stay the same? Also, what does the SetSquare function do exactly. Do you have the code for that?
[/quote]

The set Square function only sets the square in the copy of the current game board. And to be honest, it seems like nValid moves is working fine. Towards the start of the game, the count is 6, and after I let it run for a little while, the count is at 2, never at zero as far as I can see though. I do know that I never reach past the' int nscore = Min(allNodes[0,0]);'

BTW, setSquare is now setNewMove, It takes the board that we are testing, the position to place a chip, and either player, or an empty space to play there. You see at the bottom of the Min() and Max() function, I get rid of all the new spaces tested. I think at least. That what I intended.

the code for setNewMove() is...

[source lang="csharp"] /// <summary>
/// Sets the new move into the boardArray
/// </summary>
/// <param name="newMove"> vector2 position in the board array to set the new move</param>
public void setNewMove(Vector2 newMove, int player)
{
boardArray[(int)newMove.X,(int) newMove.Y] = player;

}[/source]


and that is part of my board class, which just holds the actual version of the board, and the one that is being cycled through.

:Thanks for your help btw, I really appreciate it.: Edited by KadajettGaming

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this