After a while of studying different programming languages, I decided to get my hands dirty by diving in and writing my own program. So I picked my favorite compiler (the free one of course) and started programming. After many faied attempts to write a program that would take over the world for me, I decided to make something simplier and made a tic tac toe game. Well I got it to work pretty decently (yeah right) but I hit a road block in programming the ai aspect of the game(being the great genius I am). So I was wondering if I could get some advice from you all wise and all knowing (do I really have to beg?) programmers. I managed to make the ai pick the winning move when it occurs. But know I''m wondering how I could make the ai more advanced. I want it to more agressive on the user, and for it to provide a more of a challenge. I was thinking of taking the brute force approach by programming in all the different types of strategies, but I was wondering if there was something better I could do( as well as easier). Thanks for the help and I hope you didn''t take my ideas for world domination to seriously ( haha suckers, they''ll never see me coming ... wait a sec, you''re not supposed to see this part ... DOH!) C:\Windows\System\Reality.sys crashed! Reboot Universe? [Y/N]

Tic Tac Toe doesn''t have much different situations. You could make a lookup table that for every situation you can pick the best solution.
Of course you have to fill in this table yourself, but the AI would be perfect. Maybe too perfect...

Basically, you just need to enumerate all the possible play combinations.

The hell you say! I just mean go "ok, an x can go in any of these nine positions. Then an o can go in any of these 8 positions..." only do it programmatically, of course

Symmetry reduces the number of situations you need to handle significantly, but brute force is pretty much fine for tictactoe b/c it''s got a weak maximum of only 9! = 9*8*7*6*5*4*3*2*1 = 362880 possible plays. A surprisingly small amount of time is needed these days to do so much work. Under a second if you''ve got an easy life, a little more if not.

Eliminate the symmetries (quadrilateral + rotational, effectively dividing by 8 in total). It''s a useful exercise to learn to do this on your own

Most ai profs will tell you to use min/max trees in this situation. Min/max trees basically "direct" your search, and eliminate a large number of choices before they''re encountered. The core element is the assumption that each player plays perfectly. So you might say that having an x on a line with 2 other open spots is a 1 and having two xes on a line with 1 other open spot is a 2 (you already know how to win, so this isn''t a problem). If the computer is playing X, it keeps a sort of "front line" of highest-value plays in memory. Meanwhile, it assumes that the other player will play to minimize the value of the board for x. This is basically a very simple version of something called A* (A-star). A further extension would be to subtract the o-values symmetrically with the added x-vals. In the example above, you''d give one o on an otherwise open line a value of -1 and two os with an open space on the same line a value of -2. This algorithm can be somewhat shortsighted. Exhaustive enumeration is still your best bet for simple games like tic tac toe. I once tried it on a 9x9 topologically nonuniform board, and it didn''t wuhk no moe, but you''re safe for the moment

mikey

I wrote the same thing years ago and unes minimax methods.

It works quite well and never lost a game. You just need to get the weightings right. I can''t remember offhand how I weighted mine, but if you''re desperate for that info I can look it up.

The previous posts are correct. For this situation (programming a tic tac toe game), using a tree searching, min/max method, you can easily make a game that will never lose a game.

There are only 9! = 362880 total possible positions in tic tac toe, and even if you are running it on a slow computer, it would only take a matter of seconds to solve the entire tree.

Read the article on chess programming if you want to know more about searching a game tree.