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