hi,

Im developing tic tac toe game in which i had tried most algorithms. Still i like to have a complex algo to make the player defeated. Anyone could give me any idea about it

Also I try to zoom out the squares of tictactoe when it loads but i failed to do so.

i think you want to stretch the image loaded.

use stretch_sprite()

Just make sure the computer can play itself. That could save the world some day.

Let me see if I can do this from memory...

If you go first, do:

1. Go center

2. If they take a non-corner

3. Take a corner next to their move

4. You have 100% odds of winning

5. Goto "General"

6. If they take a corner

7. Take opposite corner

8. You have 66% odds of winning

9. Goto "General"

If you go second, use these rules for deciding moves:

• If center is open

• Go center

• Block them

• Move to a random non-corner.

• Take a corner touching one of their pieces. (you may touch diagonally)

• Goto "General"

[/list]

"General"

• If they are about to win

• Block them

• Move there

• Move in that corner

• Move randomly.

[/list]

If you make a logical algorithm (instead of recursive), the steps are quite a few less. Pretend for example you are player 2 and player 1 just made his first move to the center square. It appears you have 8 moves, but in reality you only have 2.

Sure there are lots of ways to solve the problem. But as the worst case is to search through 9! combinations we're dealing with a trivial problem.

I think we can all agree that if you go first taking the center is the way to go. This because that position interfer (for the enemy) or enables (for you) a solution from each of the 8 remaining positions.

That way we have reduced the problem to a 8! search which is only 40320 combinations to look through at the second move. Piece of cake for a modern computer! After that we're dealing with a 7! search, which is 5040 game states. And so on.

I would say that this is a typical case where brute force search is a nice solution.

Picollos suggestion to use Min-Max is what I would suggest as well. There is a nice tutorial here: http://ai-depot.com/articles/minimax-explained/

Yes I do agree with you.

Still Dustins algorithm and other "hand crafted" algorithms are nice and fun to think about.

[Edit] The more I think about it the more I like a hand crafted algorithm specifically for Tic Tac Toe. I still feel that a search is a clean and nice solution to the problem and that it's easier to not mess up and introduce a human error. But if we can do it without a search that's pretty appealing too.

Yeah sure. It gives a rough estimation though and it's enough to conclude that the problem isn't very hard and that search algorithm could be used, like Min-Max (without Alfa-Beta pruning as it's not necessary).

I'm leaning more towards this as well now that I've thought more about it (as I wrote above). But if you've got the Min-Max algorithm implemented in a generic and robust way already, then that's what I'd use.

I can see that's a sneaky way to fool people who aren't used to the game, I don't necessarily think they're stupid though.

It would be interesting to see all paths to a certain victory. That is, if there are more paths than one. If there's only one it feels logical that it should start in the center position. If there are multiple they're center and one of the corners.

In theory, yes. But not all victories are equal. You want to pick the route that produces the most wins. That might not be equivalent to picking the first move that produces the most number of winning possibilities. Starting in a corner might fool people more often. (I don't know.) If it does, then starting in the corner could possibly be better, despite it leading to fewer winning paths.

Regardless of which approach has a higher probability of winning, letting the AI use multiple starting locations will feel more natural and will probably end up stumping the player more often (if he can be stumped at all).

My teacher says then when programing Game AI you must all way assume the player play well and make the best moves all the time. you will lose playing the first move in the corner when playing an AI. But if you want to give the 2nd player a chance you can random the first move then apply the AI algorithm to the rest of the game.

well ill say that if the you play in the corner you can not win playing someone who is good you can say the same for the middle as well. if both players play well the game will always end up in a tie.
edit fixed

Sorry to break the fun, but doesn't 3*3 tic-tac-toe always end in draw if both players make the best moves?
The best the computer can do is avoid losing moves and choose the winning move if you make a mistake, and that's it.

Couldn't you represent the chosen squares as bits in a 32 bit int? Each side would use 16 bits, high & low halves.

   |   |
   |X  |
-----------
   |   |
   |O  |X
-----------
  O|   |
   |   |

          (unused X bits)     (valid X bits)  (unused O bits) (valid O bits)
would be  0000 0000 00         010 001 000    0000 0000 00     000 010 100

so that the top 3 squares would be the most significant "valid" bits, next row etc.

Then you could store these in a two int struct that would have the sought pattern (sorted for binary search) with an optimal bit pattern for the next move (one more bit set than the sought int). You could have several optimal moves if possible for variety, set the most significant unused bits for "not possible" flags, e.g. if X started in a corner there'd be only 3 possible (1 optimal) move.