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

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.