minmax in tictactoe

Question

0.00/5 (No votes)

See more:

Search through the web but i m not clever enough to understand the theory of minmax with alpha beta in tic tac toe.

Anyone guide me how to start implement this minmax as a function?

My understanding is it use a score value,at final depth x win 10 if o win -10 if draw 0.And it going up to its parent node and assign another value
to its until it reach the root node.

It will be great if someone can explain a little bit of it to me.

Posted 7-Oct-10 6:58am

tuolesi

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

E.F. Nijboer · Answer 1 · 2010-10-07T08:40:00

A nice way to think about it is that player 1 needs positive points and player 2 needs negative points. Because it is about a two player game the move will give the opponent the opposite score. If player 1 a does a good move then he counts this as +3. If player 2 can then make a move that counts -4, you could actually think of this move as a loss of -1 for player 1. So, this means that the actual score for a single move is the sum of the score of all the moves for player 1, minus the score of all the moves for player 2. In most cases the moves in between are not really that important because the score is not a part of the result you end up with. A good example is checkers. If both player each has 5 pieces left and player 1 has the choice to do a move that would cost him 4 pieces but also means that he can take all the pieces of player 2, it actually doesn't matter. Player 1 had to sacrifice 4 stones but this also means he wins. The sacrifice of those 4 stones isn't relevant because the goal of the game is to end up with only your peaces of the board. So you don't have to think about the moves in between but only what the end result is.

When you would make your own game, like checkers, with a good AI, you will be surprised (or even think your code is somehow broken) when you see it makes a move that let's you simply take 5 pieces at once. But you are surprised within a few moves after that, because it has forced you to lose even more pieces you could have foreseen or is already telling you that you have lost. You would have to use alpha beta cutoff as well because otherwise you do not have enough memory to keep it in memory (for tic tac toe this isn't a problem of course). But a good tip would be not to do the cutoff right from the start because it would leave moves out that could actually be quite promising later. So first go 4 or 5 deep before clipping away the bad looking moves.

Good luck!

tuolesi · Answer 2 · 2010-10-08T17:49:00

Finally i managed to found this solution code.

int ticBestMove ( int player, int &bestMove )
{
  int bestScore, score;
  
  if ( fullBoard() )		//terminal position ( full board or 3 marked )
    return DRAW;		//static evaluation
  else if ( marked3 ( player )) //row, col or diagonal marked
    return WIN;			//static evaluation
  else if ( marked3 ( 1 - player )) //row, col or diagonal marked by opponent
    return LOSS;
  else {			//need to go further down
    bestScore = LOSS;
    int not_used;
    for ( int i = 0; i < 9; ++i ) {	//try each square
      if ( isEmpty ( i ) ) {
	mark ( i, player );		//execute move
	/*
	  set to negative of opponent's best move; we only need the returned score;
	  the returned move is irrelevant.
	*/
	score = -ticBestMove (1-player, not_used );
							
	if ( score > bestScore ) {
	  bestMove = i;			//update best move
	  bestScore = score;		//and score
	}
	unmark ( i );		  
        //undo the move ( restore board )
      }
    } 
  }
  return bestScore;
}

But i found one problem that is computer always choose the first best solution,How do i add the random function in it?
Maybe if bestscore==score i store the bestmove into an array,
and count the length of array then random a number between the length of array to choose a move?

Somebody please guide me...

minmax in tictactoe

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0