Sprad has asked for the wisdom of the Perl Monks concerning the following question:

I'm writing a Tic Tac Toe game for some AI practice. (not homework, just a personal project)

It's got several different AI modules that you can play against. Right now, I'm working on a simplistic rules-based AI. All it does is look for particular cases (such as being able to win on its next move), and take the appropriate action.

I'd like to smarten it up a bit, by adding an additional check for potential "traps" (situations where you can win two different ways, thus guaranteeing your victory). I'm wondering if there's an easier way to check for them than just hard-coding in all the possibilities. I'd like to extend this to 3-D Tic Tac Toe later, and that strategy obviously won't scale. Any suggestions on how to go about it?

Incidentally, I do know about the minimax algorithm, and that will be another of the AI subroutines available. But I'd like to get a strong rule-based one set up as well, so I can compare their speed and ability.

Here's my current subroutine for reference, and some explanation as to what's going on in it: 

# rulesAI($x_or_o, @board);
# Returns index of chosen move
# @board = 9-element array, initialized to ($c,$c,$c,$c,$c,$c,$c,$c,$c
+)
# $c - character representing unoccupied square
# sub legals() - accepts a @board, returns list of unoccupied spaces o
+n it
# sub check() - accepts a @board, returns "x" or "o" if x or o won, -1
+ if tie, 0 otherwise

sub rulesAI {
    my $mv = -1;
    my $col = shift;
    my @choices = legals(@_);
    # priorities:
    # 1. Win, if possible
    foreach $m (@choices) {
        $_[$m] = $col;
        if (check(@_) =~ /$col/) { $mv = $m; last; }
        $_[$m] = $c;
    }
    unless ($mv == -1) { return $mv; }
    # 2. Block opponent, if necessary
    my $opcol = ($col =~ /x/) ? 'o' : 'x';
    foreach $m (@choices) {
        $_[$m] = $opcol;
        if (check(@_) =~ /$opcol/) { $mv = $m; last; }
        $_[$m] = $c;
    }
    unless ($mv == -1) { return $mv; }
    # 3. Set up a trap
    # 4. Choose at random
    return $choices[(rand$#choices+1) % ($#choices+1)];
}

[download]
---
I'm too sexy for my .sig.

Replies are listed 'Best First'.
Re: Tic Tac Toe quasi-AI
by knobunc (Pilgrim) on Apr 06, 2001 at 21:14 UTC

    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.

    -ben
[reply]
Re: Tic Tac Toe quasi-AI
by stefan k (Curate) on Apr 06, 2001 at 19:17 UTC
    Well,
    I'd say don't go and code the AI rules yourself. Let it be evolved from a population of rules. Find yourself an "alphabet" that is able to code the input-situation and the field that should be set next (actually this sounds exactly like an cellular automaton). You might consider using my Simple Generalized Genetic Algorithm for the optimization (well, I'd be happy if anyone would use it *grin*)

    My experience with AI systems (and GA and G and ...) has been to put as few human-made rules into the system as possible and evolve a solution...

    GoodLuck!

    Regards Stefan K

[reply]
Re: Tic Tac Toe quasi-AI
by suaveant (Parson) on Apr 06, 2001 at 19:01 UTC
    Well.... the way most systems do it is to do a lookahead... check to see if you can win in n moves or your opponent can, and take the best path. This is pretty easy in tic-tac-toe do to the simplicity of the game. Of course, as long as you play in the corner in the first move (if you are second) or the center (if you are first) then it is very unlikely you will be trapped.
                    - Ant
[reply]
Re: Tic Tac Toe quasi-AI
by Falkkin (Chaplain) on Apr 07, 2001 at 01:21 UTC
    My own version of Tic-Tac-Toe AI is here; it actually learns by playing games, making a random move if it doesn't yet have a "preference". Admittedly, it learns slowly, but the Defensive player is unbeatable after about 60000 games against a random opponent.

    This is obviously not incredibly applicable to more advanced games like chess or even connect-four. It has no means of recognizing similar situations or common patterns, hence the search space gets huge quickly....

    Thanks for posting this node... now I feel like I should go back and improve that code. ;)

[reply]
Re: Tic Tac Toe quasi-AI
by jynx (Priest) on Apr 07, 2001 at 01:29 UTC

    This code works, for 2-D. When you get to three dimensions (if you do plan to) it becomes possible for the opponent to threaten win just to distract you. You would at that point want to decide what squares are more beneficial without tying yourself down to one branch of a search tree. The minimax algorithm, while useful for 2-D, has some significant fail cases for 3-D (most especially with odd sized boards, eg 3x3x3 or 5x5x5). Clipping the search space in 3-D can be detrimental to your algorithms health.

    As for checking for traps, the best way i came up with (probably not the best way) was to assign values to the moves which corresponded to whether squares in the same line were occupied or not. Then a trap would be more apparent because two different squares should have the same values. It took a lot of work to determine what a (valid) 3-D line was and how many pieces were in it. This method also has some serious drawbacks, in fact, the same ones that plague minimax (as its a derivation).

    In the end you will have to assign a value to a move, either qualitatively or quantitatively, and the accuracy of that value to judge a good move from a bad one will probably decide whether your algorithm works or not. It took me quite a few rewrites to come up with the ok scheme that i did. Sit down at the drawing board and think about how you want to assign values to moves. That's the most promising thing i can tell you.

    Hope This Helps,
    jynx

[reply]
Re: Tic Tac Toe quasi-AI
by mbond (Beadle) on Apr 06, 2001 at 23:08 UTC
    I would solve it using a dynamic system. Basically you generate a table of all posible outcomes and as you fill in the table you use the previous calculations to help with the current ones.

    Its a rather indepth topic, but very intresting. You might wanna check out amazon.com for some books on it, i know they have a bunch of good ones.

    Mbond.
[reply]
Re: Tic Tac Toe quasi-AI
by cei (Monk) on Apr 07, 2001 at 06:20 UTC
    Sorry, I don't have a hard & fast answer. I've never coded it myself, but I've given it a bit of thought over the years.

    Things to consider:

    1. When creating a Tic-Tac-Toe system, my personal preference is to have a 2D game at 3x3, a 3D game at 4x4x4 and a 4D game at 5x5x5x5. This gets fun, because there is no center square in 3D, and 4D just gets wacky.
    2. Think about "What is a win?" in terms of vectors, so that what you create is scalable.
    3. You want to write your rules so that they can be rotated. If you're playing in 2D, the board can be rotated in one of 4 positions. Write the rule once, if you're checking against board state, and then rotate those states. In 3D, you'll have 6x4 rotations and in 4D you'll have 8x6x4, I think...
[reply]

Back to Seekers of Perl Wisdom