First I'd like to thank everyone who replied to my other Minimax question. I took your advice and implmented Tic-Tac-Toe using the Minimax algorithm (yes, I realize that I can use Negamax, alpha-beta, etc. for improvements, but for the time being I'd like to keep everything as simple as possible). I have everything coded up but I am running into a problem because I am not sure how the Evaluation function is supposed to score a given position. I mean, I understand how to code the heuristic, but I don't know *which* score to apply to a given node. For example, say a given position is a win for X, do I have my Evaluation function *always* return +Infinity for that position, or do I have to take the *current* player into account, etc.? I hope this make sense... I can post code if my question isn't clear. Thanks! BT

I wouldn't use +/- Infinity for anything but the initial values for minmax.

Anywho, the easiest way to score is this. If you are evaluating a MAX node, set the score to +WIN_VALUE. If youre evaluating a MIN node, set the score to -WIN_VALUE.

You can also set a global value that indicates which player is which (i.e. gComputerPlayer = 'X'). Then, in your position, store who just moved (i.e. position.lastMove = 'O'). Then in your evaluate:

if ( position.lastMove == gComputerPlayer)   score = +WIN else   score = -WIN;

Score tic-tac-toe is easy. Check for 3 in a row. :) 1 = win, -1 = loss, 0 = nothing. There is no need (like in chess) to create complex heuristics.


You're might be seeing some weird behaviour in your Tic-Tac-Toe for this reason:

- You're program may take the first win it finds, which may not be the quickest win.

To fix this, in your evaluation, subtract points based on how deep the win occurs. You want to encourage your program to always take the fastest path to victory (or tie).

Good luck!
Will

Quote: Original post by RPGeezus
If you are evaluating a MAX node, set the score to +WIN_VALUE. If youre evaluating a MIN node, set the score to -WIN_VALUE.

Once again, thanks Will - perhaps you should write up a little blurb about Minimax - your explanations are great!

I still need clarifaction on something though:

During Eval() the type of node is determined by who moved *last*, not the player *about* to move?

Thanks man!
BT

Quote: Original post by bittwiddler35

Quote: Original post by RPGeezus
If you are evaluating a MAX node, set the score to +WIN_VALUE. If youre evaluating a MIN node, set the score to -WIN_VALUE.

Once again, thanks Will - perhaps you should write up a little blurb about Minimax - your explanations are great!

I still need clarifaction on something though:

During Eval() the type of node is determined by who moved *last*, not the player *about* to move?

Thanks man!
BT

Thanks for the encouragement. :)

Look at it like this:

The computer JUST moved. You called Evalutate, and it reported a win. The computer MUST be the winner, since he placed the last piece.

If you're looking at moves the computer wants to make, then you should be MAXIMIZING the score.

       MAX     -- computers move    MIN        -- humans move  MAX  MAX     -- computers move   |    |  eval eval

It's not really important that the evaluation function knows who just moved.

In a game like tic-tac-toe, a victory can only be for the player who just moved. 3 in a row means the player who last moved is the winner.

If the computer just won (a MAX node) then you would represent the victory as a positive number.

If it was the opponent who just won, then you would want to represent the win as a negative number.

--or--

if this is too complicated, just keep a golbal variable that states which player the computer is (x or o). If Evaluate finds a win for the computer then return +WIN, or if it's a win for the opponent (i.e. a loss for the computer) return -WIN.


Will