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).

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

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

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

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

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]

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?

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.

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.

http://web.archive.org/web/20040316060526/http://www.cogs.susx.ac.uk/local/books/ai-through-search/ch05/ch05.html

http://web.archive.org/web/20090312083041/http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic11/

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.

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial