MiniMax Algorithm

edvinson
edvinson used Ask the Experts™
on
I am trying to comprehend the MiniMax algorithm, specifically relating to a TIC TAC TOE game.

I have a basic understanding of how it works. I have read through the links below:


and many others.


I understand how the Heuristic score comes into play, actually this is the ONLY concept that I fully understand well enough.

It makes sense to assign values to rules, such as:

For each row, if there are both X and O, then the score for the row is 0.
If the whole row is empty, then the score is 1.
If there is only one X, then the score is 10.
If there are two Xs, then the score is 100.
If there are 3 Xs, then the score is 1000, and the winner is Player X.
For Player O, the score is negative.
Player X tries to maximize the score.
Player O tries to minimize the score.
If the current turn is for Player X, then the score of Player X has more advantage. give the advantage rate as 3.

Ok, so far so good. I fully understand that by enforcing those rules, the result should help determine the value of the move.

But here is where I am lost. And it is at the most fundamental level....

Let's assume our game uses a simple 2x2 array.

Our current board looks like this:

-- | x | --
0 | -- | --
0 | -- | --

and it is X's turn.

Using the widely available code example for minimax, such as the following:

http://www.codeproject.com/Articles/43622/Solve-Tic-Tac-Toe-with-the-MiniMax-algorithm

I want to understand how this works, or if it EVEN DOES work!!!

Using my example above, the code SHOULD have X block the O from winning in the top left corner.

The solution I am looking for is a clear explanation ,  whether psuedocode, or actually stepping through working code, on how this ( or a similar MiniMax algorithm ) would work using the Tic Tac Toe example above.

Thank you. I look forward to finally understanding this!

I have this question under VB, PHP, and General. I am familiar with them, so the language is not as important as a clear explanation.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
First of all, you have a 3x3 array (likely with indices from 0 to 2 for both dimensions).

Second, the rules seem to work perfectly well in this situation IF you apply the rules not only to the rules but also to the columns.  In other words, the rules, as you have laid them out, only talk about what happens in a ROW.  But tic-tac-toe is a two dimensional game, and therefore you would need to apply the rules in both dimensions.

So as I see it, each space really has 4 scores:
1 score for the X looking at rows
1 score for the X looking at cols
1 score for the O looking at rows
1 score for the O looking at cols.

Once you've gotten all 4 scores for each of the 9 spaces, you can determine what move to make.

Author

Commented:
I just am not getting it. Is there any way you could show me a small example using the minimax algorithm assuming it is X's turn, and there is one O on the board?

If I can see how to start with one move, I think I can get the rest.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial