Hello people, i need your help! i've just finished a tic-tac-toe type game but the AI sucks, and i need to know what is the best way to approch this problem I wanted to make an impossible to beat computer (i.e. Impossible difficulty setting) plus easier modes, but the only way i thought to do that is through seting all possible combinations and since im using a 4*4*4 (64) grid thats 64! (factorial) which is a big ass number. so any suggestions in how to do this would be great and ill ive you credit in the game when its done, and no im not asking you to do it for me just point me in the right direction. Thanks!

You want a minimax algorith:
http://en.wikipedia.org/wiki/Minimax_algorithm
I suggest you implement it using Alpha-Beta pruning to reduce the number of nodes:
http://en.wikipedia.org/wiki/Alpha-beta_pruning

You probably can find all the info you need by googling for a time, maybe even a full tic-tac-toe implementation, good luck!

but the game is written already in C++ and OpenGL,
can i use the program with C++?

actully never mind that
thanks for the help guys ill check out that minimax thingy!!

I've written a ttt app that used a hand-made ann to work out the solutions. (of cource, it took forever to get the net to work properly).

I've also written another tt app which looks for patterns, then uses weighted squares.

What i would sugest (for a noobie such as yourself), if the weighted squares approach, with patterns once your used to it. (to patch up any faulty decision making).

You can adapt this for anything, from ttt to checkers. Some other games (like connect 4, virus, ect.), but most definatly not chess.

You can also use this in your evaluation function for ab. (well, use the weightings to determine points of interest, for eg. major attacks on squares vs. attacking a well protected square).

Heres a simple version.

Start off with a blank board.

Each square has a weighting.
These should go like this

1|0|1
0|1|0
1|0|1

Just to make it try and move in the corners or the center.

Now, the opponant makes a move.

So, O (your opponant) goes in the top square.

THe board is

O| | | | | |

now, you increment the weighting of the squares in the same row and coloumn by one

So, its now

2|1|2
1|2|0
1|0|1

For your move, you pick the square, that does not have a piece on it, and has the highest number. (if many do, then pick one at random)

So, say you pick the center.

The board is now

O| |
|X|
| |

And so on.
You an see that it made a mistake. (player goes in the lower right hand corner, bot goes in top right, player goes in lower left, then the player has 2 possible wins).

How do you correct this?

You use patterns.

So, for eg. one pattern would be
O| |
| |
| |

So, because that was what the board was like, we look at the accompnying table

which is

0|1|0
0|0|0
0|0|0

Which we then add to our normal grid.

This then gets it to favour the move, in the top center.
Which then leads it to a draw.

Overall, its a fast and simple approach.
And if you really want to do mm + ab, you can use this to decide in which order to make the moves. (which makes the search awhole lot faster, since it will usually lead the serch to find the best moves first.).

Also, once you get past 3x3, a full mm search is inpractical, but the weighted squares apprach would still work on 2000x2000.
From,
Nice coder

Quote:Original post by The Reindeer Effect
Like people before me have stated, min-max is a good way to go. The reason for this is because in a game of perfect information like tic-tac-toe (everything is known to every player) it is hypothetically possible to achive "perfect" play. Tic tac toe is so simple and has so little board possibilities that it is actually trivial to use a complete min-max search, one that encapsulates all possible game states ever. Chess, which has many many more complexities, can still do so but only to a certain move depth ... top quality chess AI's can hit 6, 7, even 8 moves in advance. But a chess game is a bit more than 8 moves long, so you aren't necessarily playing perfectly, you are only maximizing a few moves into the future.

Unfortunaly 4x4 ttt is too big to minimax to work effectively.

16! possible moves = 2.09227899 × 10^13 = 20,922,789,900,000 possible moves.

3*3 ttt, = 362,880 moves.

Now, since you might be able to do 3*3 ttt in about a second.

It would take you, maybe 240.083262 Years to do 4x4 ttt.

And quite a bit longer for 5x5 and 6x6 ttt.
For eg. 5*5 ttt = 1.35447672 × 10^13 years
6*6 ttt = 3.24833652 × 10^29 years

Weighted squares would work out a winning approach in < 1 second.

It is the best alternitive for games like this. Easy to code, easy to get working.

Applying minimax with alpha-beta to this problem is like trying to kill an ant with a nuclear missle, it works, its just overkill!.

From,
Nice coder

well thanks for the detailed tips nice coder!
the thing is that the game has a 4*4*4 grid (i.e. 3 dimentions)
so i think ill try the weighted apporach to get the AI to place pieces in the corners and middle.

I havnt checked the MM approach yet, but ill do that now.
Thanks again for the help and keep the idea coming!