Tic-Tac-Toe

Read the article on Gamedev about chess programming. The article talks about chess programming, but the concepts are the same for any board game of this type. In other words, the same concepts are used in chess, checkers, tic-tac-toe, etc.

Read that article and pay attention to the things that aren''t necessarily chess specific. To make AI for tic-tac-toe, you will need a way to evaluate who is winning, a way to generate all of the possible moves that can be made on the board, and a method for making a move on the board, as well as undoing a move that was played on the board. In other words:

1. A way to evaluate a position and tell who is winning
2. A way to generate legal moves
3. A way to make moves
4. A way to undo moves after they have been made.

Anyway, read that article and pay attention to those things, and then come back here with any questions that you have after you read that article. Until you understand the basic idea of how it works, you will probably only get more confused by code. I (and probably others) will help you along once you do a little research on your own. It''s ok if you don''t understand everything after doing your research, but at least then you can ask better questions instead of just saying, "I want to make a tic-tac-toe program so tell me everything I need to know."

Russell

I wrote a kind of AI in the next way (it''s done by checking per turn):

1st Turn: Computer player checks if the human player played on the middle square.

2nd Turn: - Comp player checks if the human player is about to win, if so, blocks him, if not, plays in other square, trying to win.

And so and on...

Well, I was wondering if there was a shorter way of writting the 2nd turn, cause I use ''if'' statements for each square. That means a long code.

Check this out:

http://www.gametutorials.com/Tutorials/Console/Console_Pg1.htm

Very simple AI and very detailed comments (although the code is a bit clunky).

I just went through a huge set of threads where various AI concepts were kindly explained to me, both here and on usenet. Study up on the minmax (or minimax) algorithm and how it works with recursion to test the leafs of a tree.

The easiest AI to make for tic-tac-toe imo would be an expert system, aka a list of if statements. There are a few basic rules that you can follow to almost never lose in 3*3(standard board size) tic-tac-toe:

1) If you can win, place you marker in the appropraite square to win.
2) If you oppnent is about to win, attempt to block.
3) If the opponent went in the center, place your marker in a corner.
4) If the center is open, place your marker there.
5) If the opponent went in a corner, place your markeron a side (any place but a corner or center)
6) If the opponent chose in a side, choose a corner.

(when choosing a corner or side, randomly pick one. Actually, it might be good to pick one next to an opponent piece if you are just trying to tie every time)

It was a long time ago that I used those rules in my Tic-Tac-Toe AI so they might not be 100% correct but iirc there is only 1 way to beat it and it requires a little luck.

"The Requested Information Is Unknown Or Classified" -Anonymous

Since the board is so small (only 3x3), and there are only 0''s or X''s in each square, it is possible to make the AI perfect - that is it would never lose, but might draw. This of course makes a boring game if you are playing against the computer, but then tic-tac-toe isn''t the world''s most interesting game in the first place .

A simple way to get the AI to be this good is to make is by using the methods described by Russell and green_guy, taking them to the extreme, and evaluating the moves right until the end of the game. This is possible (as mentioned above), due the the very small ''size'' of the game.

What is effectively done is to try each possible move from the current position (like placing a X or O in each possible free position), and then simulate each of the possible moves the opposition could do from the resulting position. By doing this right to the end of the game (a full board), it is possible to determine a move (or selection of moves) from the current position that will definitely result in either a win, or a draw.

This way of doing things doesn''t require tactics as such, and is simply brute force. But if implemented correctly, should work just fine. If someone made a really really super computer (whose performance would have to be quite unimaginable), it would be possible to have a computer play chess perfectly, by using this method.

Hope that all makes sense...

hi,
in 3x3 case you can do simple "learning algorythm" because the no of all possible cases is finite and resonably small.
Let start with DUMB computer player and as game proceeds store all moves - in such a case computer looses at first but comes to draw at the very end. Unfortunately it doesn''t seek for possible wins.

The more interesting problem is where you play on infinite board and try to score 5 in a row.
you gotta have more universal approach
can someone comment it?
Pet

I recently made a 3D Tic-Tac-Toe game for a college class, and we had to implement 3 distinctly different AI difficulties. For the first (and easiest), the computer basically followed these steps:

1. Complete a row if all but one squares belong to the computer.
2. Block a player-owned 3-in-a-row if one exists.
3a. Pick a random, empty (or computer-controlled) "row" to persue and pick a point in that row.
3b. If a row is already chosen, make sure the human has not placed a piece in it. If he has not, pick a square in that row. If he has, use 3a.

For the medium difficulty, each square was given a value based on the number of potentially winnable rows it was in. For example, the center piece in a 2D board is in 4 potentially winnable rows (1 horizontal, 1 vertical, and 2 diagonal), corner squares are in 3, and edges are in 2. Agter the points are all added up, the square with the highest score is picked.

Uhhh...I have to run to work right now, so I''ll finish this later.

The third AI strategy used the technique Miles suggested: A recursive function that plots all the possible moves, counter-moves, counter-counter-moves, etc. until the board is full. If you''re tricky, you can use this method to "trap" the human (which is simple for a 3x3 board, but much harder as more dimensions and planes are added). To avoid a draw, make the AI revert to the second, or even the first strategy if no "trap" is found.

Here's a link to an interesting article involving the use of matchboxs to create an AI which can learn on it's own.

http://www.atarimagazines.com/v3n1/matchboxttt.html

However if your looking to create an AI the easiest by far is simply to create a tree search by expanding all the different moves possible. Then it becomes a question of how to implement such a process. You'll need to follow a procedure like the following.

1. Examine the current state.
2. If only one move can be made make it and apply some heuristic function to the end state.
3. Calculate all possible moves and then add the new states to a list. Remove initial state from the list.
4. Go to 1 until the list is empty.

The mechanism for adding to the list will change the behaviour of the program slightly. By appending the new states to the front of the list we create a depth first search. By apending new states to the end of the list we create a breadth first search which will be exhaustive over the whole search space.

Now the question fall to what to choose for a heuristic function. The easiest to implement will be a "find the first solution" type function. We evaluate the board state and the first we find as showing us winning we will move towards that goal. However a potentialy better strategy would be to assign a value of 2 for a victory, 1 for a draw and a 0 to each leaf on the tree then calculate a heuristic value for the parents of a group of leafs by adding togehter the heuristic value of the leafs. By working our way back up just short of the original node we can choose our goal by finding the node with the highest heuristic value.

For example.


Current State AI
/ | \
2 0 1 Player
/ \ / \ / 1 1 0 0 1 0 AI
| | | | | |
1 1 0 0 1 0 Player

Interepret this as meaning we have played a game for 5 turns in total. 4 moves are remaining to be made (the depth of the tree)

We have to decide which path to take. There are three possible moves. We can see quite clearly form this what action we wish to take, the first since it has the highest value. Taking the second guarantees a loss and the third is a guaranteed draw. The player makes the decision at the second node so decides whether the game shall fall to a 1 or a 0.

This is actually roughly how Deep Blue works, it's simply vastly more powerful and does lots of clever things to eliminate duplicate states by mirror images of the board.

Much of the difficulty you'll face will come from implementing the list's properly. I did all this work in Prolog at University which is really nice for writing such problem solvers in since it's recursive and handles list's easily.

We can use this technique on this sort of problem because we can see the state of the board and calculate each of the possible moves, just like we can in chess and Go. Go is interesting to consider with this technique because the size of the tree generated is larger than the number of atoms composing the Earth!

[edited by - Mirsha on July 24, 2002 7:02:44 PM]

You know, I heard on the radio the other day that they have successfully trained chickens to play perfect tic-tac-toe. They take them to casinos and they let people play against the chickens. If you beat the chicken you win $10,000 I think. I think they said that the chickens have lost a total of like 3 games in like 10 years. Maybe there is hope for us humans after all

Russell

mmmm... yea right

[edited by - Pet on July 25, 2002 6:07:40 AM]

Ok, here''s a list of what I would do (and believe me, I''ve done a Tick-Tack-Toe engine before and this AI is really good)
1. See if you can win this turn -> Win.
2. See if he''s going to win next round -> Block him.
3. Create a list of avaliable moves and rate them.
4. Find the move with the highest rating and do that.

Moves should be rated as to how the enemy would use them. For example. The middle sometimes get''s ignored, so a low rating unless the following example: ox
x o
oox
where the enemy could place one in the middle and then into the top-right and win.

Lastly, make sure your AI looks about three turns ahead and plots all avaliable moves. This can take time, but it pays off.

MBDYProductions - Mike Brough - Programmer