Minimax and TicTacToe: choosing the BEST move

KyleG
KyleG used Ask the Experts™
on
Hey everyone,
I've just finished making a quick tic tac toe game where the user plays against the computer. It's in console, mainly because I'm just using it as way to introduce myself to minimax. At the moment, the computer doesn't choose the best possible move (i.e. it doesnt block wins, and sometimes doesn't finish a row of 3 to win the game), but I think I know why: for those of you that are familiar with minimax, you know that with tictactoe the only possible outcomes are -1 (loss), 0 (tie), and 1 (win). But, when my program searches through the results for the best move, it ends up taking the first move that makes a win possible/probable.

An example of the logic behind this problem is this:

if(1 > temp)
  temp = 1;
if(1 > temp)
  temp = 1;

Obviously this would be in a loop, and looks nothing like my actual code, but it gets the idea across (I hope!). It is possible that the second 1 (which means a win) has a better chance of winning than the first, or blocks a win by the user etc, but my program will never take it. How can I solve this problem???

Thanks for reading my novel :)
Kyle
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®

Commented:
You probably made a mistake somewhere else.
Minimax should always choose the best move (according to the eval function).  If several moves indicate the same outcome (a forced win in your case), it does not matter which one is chosen

Author

Commented:
eval funtcion? I must have REALLY screwed something up, because I use two funtions, max() and min(). I also use treeover() which checks to see if the "possible game" has been won, and who won. max() and min() call each other recursively, and I did it this way mainly because I have no idea how to properly use the minimax system. The source code I've seen has no comments, and the websites don't use code!!! The websites that do use code use "pseudo code" and still don't explain how to implement it in tec tac toe! Any help with this would be appreciated.

Thanks alot,
Kyle
Commented:
OK, some explanation:

Usually minimax is used when the computer cannot compute the whole game tree (as in chess).  As TTT has a very small game tree depth (9) you can hardcode it and not use minimax() at all.  However, TTT can still be a good excercise.

Now, if you cannot compute the whole tree, you stop at some arbitrary depth and evaluate the the board position.  The eval() function returns >0 if it considers the position favorable, <0 if unfavorable and =0 if a draw.  An actual win is represented by +infinity (actually, some very large number) and a loss by -infinity.  The idea is - the higher the number, the better the position.

In TTT, you can compute the whole tree, so your eval() becomes much simpler: it returns 1 for a win, -1 for a loss and 0 for a draw (only on the leaf positions of the game tree, otherwise, minimax continues).

Some links:
http://www.cogs.susx.ac.uk/local/books/ai-through-search/ch05/ch05.html
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic11/

[EDIT:  These links are now dead please go here for WebArchive versions - added by MASQUERAID 08/29/2011]
Become a Microsoft Certified Solutions Expert

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

Author

Commented:
Wow, that really cleared a lot of things up for me, thanks a lot. Please, correct me if I'm wrong, but are you saying that the computer only takes into account the values at the leaves and not the changes that players min and max would apply to it? I understand the concept of minimax, but the fundamentals seem to escape me, that is, how I would go about creating a program with minimax. I'll check out the sites you suggested, I'm sure they'll help.

Thanks again,
Kyle

Commented:
Check the links, if you still have questions then - I'll be glad to help.

Commented:
If you can calculate the whole tree you wouldn't need much of an eval function. But wouldn't you still need to use minimax to figure out which move to make?

Consider a position in which there are three possible moves left. If the first two wind up leading to leaves that are both win and loss positions, but the third contains only wins and ties, wouldn't you use minimax to decide to make the third move?

Commented:
>> If you can calculate the whole tree you wouldn't need much of an eval function.

Correct.

>> But wouldn't you still need to use minimax to figure out which move to make?

No, because you can solve the tree and propagate the values up just once and never have to do it in runtime.  Basically, you can store the best move for every (hashed) position.

Let's consider TTT as an example.  You have 9 board positions so you can encode a board using, say, a 9-digit integer (4 bytes are enough).  E.g., the following board position:

    X  0
      0X
    0X

will be encoded as 102021210.

Since you only have 9^3=243 positions, you can comfortably store them along with the suggested move for each position.  Use a hash table, accessing it takes constant time on the average and you're set.

Now consider chess.  The good programs all use tablebases(*) for the endgame and thus are able to instanteniously decide on the best move when they reach this kind of positions.

(*) TableBases are databases of all posible legal board positions with a small number (up to 6?) of pieces.  Currently, the  full set for 3, 4 and 5 pieces takes about 8GB of disk space.

Author

Commented:
I looked at the links and they helped a lot. What I'm still having trouble with though is creating the actual c++ code. I tried writing my minimax routine using the mcgill pseudo code, but for some reason after the player's first move (player goes first) my program solved the entire game. Obviously I did something very wrong, but I couldn't figure out why it was doing that, so I deleted that attempt. Does anyone (alexo in particular, you seem to know a lot about this stuff) know of a place where I can get c++ code for a VERY basic minimax system? I say basic because the more complicated it is, the harder it will be for me to understand the bare minimum needed to create a minimax routine.

Thanks again,
Kyle

Author

Commented:
I'm in the process of searching with google, but there is one more thing that I forgot to mention: I don't really know how to call minimax in a such a way that I can choose a move with it. It just returns the value of the best move, and not what that move actually is. How would I do this?

Kyle

Author

Commented:
Never mind, it finally works!!! Thanks for all your help, I couldn't have done it with out you. The major mistake I made was this: When generating the children nodes I forgot to switch between 1 and -1 depending on whose turn it was(1 = X, -1 = O). This resulted in a "confused" eval() function which returned the wrong winner etc. Another thing to keep in mind when using minimax is that the eval() function must be FLAWLESS in terms of how it decides who has won. This is very important, as the entire algorithm relies on what the eval() function returns.

Thanks again for all you help!
KyleG

Author

Commented:
Although this specific comment wasn't necessarily the one that solved my problem, I chose it because of all of the questions that it answered, i.e. exactly how minimax works, the links, etc. I've added another 50 points for your patience.

Again, thank you,
Kyle

P.S. Email me if you would like the source to my little program. There are no comments yet, but they will be added soon.

Commented:
Congratulations!
Your next step should be adding alpha-beta cutoffs.

Anyway, I suggest you try a different game.  TTT is too easy, chess is probably too hard, Othello (http://www.ugateways.com/bof4.html) seems to be just right.
Most Valuable Expert 2013

Commented:
Thanks for updating the links, the mcgill.ca link seems like it will be the most helpful, but it dives right into Minimax. As far as I understand, I need to first generate a game tree of all possible tic-tac-toe board positions, then use minimax to pick the best possible move.

At this point, I'm not clear on how to generate the game tree and unless I'm misunderstanding, this is where I need help first.
Please ignore above comment, posted in the wrong thread.

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