Tic Tac Toe AI

I havent taken the time to learn java, so i cant give you any actual snippets of code, but i have a general idea of how to do it. Id have it check for 2 Os in a row (assuming the computer is O's) and place the O at the end of those 2 if there isnt an X, winning. If there isnt 2 O's, or 2 O's with an X at the end, then it would check for 2 X's in a row, and place the O to block that, unless the space at the end of that has an O already. Finally, if the above 2 moves cant be taken, then it would pick a spot adjacent to an already existing O, with an empty spot in the same row to make a winning move possible. If none of the above are applicable, then it would pick the spot with the biggest number of possible wins, with X's taking away a possible tic tac toe in that row.
Sorry if that wasnt worded very well, just ask if you need clarification on any of it

I am coding a tic tac toe game ( Human vs Computer ) . I want to make the computer unbeatable . Using random move is no AI i think . So what should i do? I have read about game tree's but they are confusing me . I just need to write a function which returns the best move.
I am using Java

You'll want to look into the "minimax" algorithm (a reasonable-looking article is here). It's a little difficult to get your head around, less so if you understand recursion well, but it's basically The Right Way To Do Tic-Tac-Toe AI.

Game trees are just descriptions of "how the game could go". Have you ever read one of those "Choose Your Own Adventure" books, where you pick which page to go to next? It's a little like that -- branching where one of the players gets to make a decision.

This picture is quite literally a visualization of the completely solved Tic-Tac-Toe game tree. Hopefully it'll help you see how things work a bit more clearly

The thing is that when you want to make a good AI player you have to think as a human. A human would predict next move, so your computer need this feature. I have a made a AI to Tic-Tac-Toe and I did like this.

First check if you can win

Then if you didn't win, check if the other player can win.

Last if no of these thing became truth, take a random spot.




You can make the AI player better if you let him go through all possible moves, and then find the best one. But try to think simple first, and then you can try to make a more advanced player.




-Tapped

First check if you can win

Then if you didn't win, check if the other player can win.

Last if no of these thing became truth, take a random spot.[/quote]

I used this technique as well when I wrote a Tic-Tac-Toe game myself...many years ago. Believe it or not, this simple process actually makes the AI play almost a never less than perfect game every time, the only way to win is to setup a situation successfully where you have 2 options of wining. Tic-Tac-Toe is a very simple game, I personally wouldn't over complicate it with algorithms, recursive functions etc.

**EDIT** But if you want to make it so the AI always wins/cats game than you need to replace step 3 with another list of checks for double win scenarios such as has player one entered a piece in spot 2 and spot 4 in the array below.
OPEN(1), P1(2), OPEN(3)
P1(4), P2(5), OPEN(6)
OPEN(7), P2(8), OPEN(9)
As you can see you would want to move to position 1 instead of just randomly generating a move. But honestly the chances are fairly low with the above approach that this scenario could happen. Like I said before it almost never plays a less than perfect game, if you put this strategy in before randomly moving it will always play a perfect game.

I have already tried the random move stuff and i am implementing it as the "easy" mode of the game. But for "hard" mode i need good AI , And i am not good at recursion cause i haven't studied it in much details.

0 1 2

3 4 5

6 7 8

Instead of using random spot, you could use a list of the best moves, like 4, 6, 2, 3... So it would first check if 4 is occupied if it is, then it would try 6 and so on. This was a random list, you should try to find the best moves by yourself. The worst AI is a AI which is unbeatable, so don't make a impossible AI player.

-Tapped

I agree; minimax is the right answer. It'll play perfectly, and, of the various ways to implement a Tic Tac Toe AI that exist, it's the one that you'll learn the most by implementing.

Also check out the applet here.

Minmax can indeed get you to a perfect tic tac toe playing ai. For the sake of fun (as we are talking about a game here), I suggest finding somewhere in the algorithm to introduce just a little bit of random so the player has at least a small chance at getting a win. Tic tac toe is one of those games that if played optimally, you literally NEVER lose. And a computer that NEVER loses isn't all that fun for the player.

Finally I found some one like me who codes the AI board games in Java.
Generally people advise that Java is slow language and for these ppurposes, its not a fit.I have to say thats correct on their part,as in Java there is an object created for almost everything which takes afinite time and hence generally Java games are about 15% slower than C/C++ programs by default if the margin is above 15%,that means the implementation is sloppy.

If this tic-tac-toe is an hobby project and you wanto learn the aspects of AI programing, algorithms or even something like comparing the efficiencies of the algorithms, then I suggest you to start with the basics of AI programing. I had done this game before, but never kind of looked into different areas of optimizations(tweaking the board representations and other stuffs.)

I help you out with this if you say so, I will just create a blog where in I will code and feed what ever is possible and you can join along,comment so it would be a nice thing to share with the fellow programmers.
Since this is your first approach with board game programing, its fine to start with tic-tac-toe. Later we can always move on to methods like connect-n in row(more than three and something else based on similar ideas). I would surely like to help you out as I could imagine myself in your position,when I started to code, an year and half ago. People on this forums have helped me a lot and now I take the opportunity to help you out.



PM me or reply this thread if you agree.
-Thank you.

thanks for offering the help , I have sent you a PM , please check it