There is one solution to the problem and many ways to implement it. Basically you need to search all the possble states of the game considering each of your moves then each of the opponent's possible counter-moves, then your counter-counter-moves, and so on until you hit a certain victory.
The problem occurs when your search space is too large and you have to decide how to prune the search tree. So while the basic technique will work for tic-tac-toe, it does not scale up to chess. So in order to allow the solution to be found without having to search the entire space you can change the way things work. The simplest to implement is a depth-first traversal of the problem set so you make the first move and pursue it through all of the possibilies until you hit victory or loss at the bottom, then back track up to the top (see fig 1). A breadth-first traversal would try each possible first move, then try each counter move progressing through the options one level of the tree at a time (see fig 2).
Fig 1: Depth-first
1
/ \
2 6
/ \ / \
3 5 7 8
/
4
Fig 2: Depth-first
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
There is no immediate benefit to changing the search order. But you can assign a timeout and stop the search after you reach a certain depth, or have searched N nodes, or after N seconds have elapsed. Then you can devise a way to score each state of the game and pick the best current state of the board and make the move that takes you there. If you use a breadth-first search you will have explored more openings so may embark on a better high-level strategy, whereas if you chose a depth-first you may have explored one opening fully and not even looked at the others.
There are many other strategies for guided search of a problem space. A* being a fairly popular and effective one. Most of these require you to be able to give some guidance through a function that computes the current state of the board. You would tend to explore the initially promising openings more deeply until you hit a problem with them then it would backtrack and try a different one. Genetic algorithms are cool in that you define the problem set and the operators and try to evolve a solution. The downside is that they take a lot of CPU time to run and they may find a local optimum and get 'stuck' on it.
Please note that this only works for games where there is no chance involved. For games with chance the techniques are similar but more complex since you have to compute the probabilities of each outcome everytime you make a decision. You may also need to work in ways to guess at what secret information they have based on play. Fortunately there are lots of games where chance is not involved (such as Tic-Tac-Toe).
Check out Games of No Chance if you are interested in the topic.
-benIn reply to Re: Tic Tac Toe quasi-AI
by knobunc
in thread Tic Tac Toe quasi-AI
by Sprad
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |