Aaron Gadberry

Help – v. helped, help·ing, helps

Was this site helpful?
My Amazon.com Wishlist

Rule-Based Tic Tac Toe

26th January 2006 - By Paradochs

Summary

This program is an implementation of a rule-based AI game. The game has 5 difficulty levels based on how good you want the computer to be. It can range from making many mistakes to being impossible to beat. There is also an option for who gets to move first.

Details

Difficulty levels were relatively easy to create. The simple concept is the make the computer “forget” to check specific rules. Problems arise if you take out rules, because then there will be specific patterns of play that will constantly win. What I did to put probability into the equation is simple. I generate a random number in a large range (1-32000 approx). I then take the modulus of the random number % difficulty level. This makes my new random number in a smaller or larger range, based on the difficulty level. The harder it is set on, the larger the range of the random number. A new random number is generated and scaled for every rule. Then the test is simple. If the random number = 1 then the rule is not calculated. This gives the program a 1 / (range of random #) to fail that rule. The special case is the perfect machine. The highest difficulty level means that all rules are checked all the time. For this I simply have a Boolean flag that must be true for any rules to fail.

The board is simple, just an array of characters. The players take turns back and forth until someone wins or until all of the spaces are filled. There is another menu option of choosing who moves first, which is also simple to implement.

The OpenGL was thrown together to put a graphical interface on the program. It is simply a few cylinders in different colors.

The Rules

The idea of the rules behind this game is easy. There are seven rules.

  1. If you can win, take the win.
  2. If you can block a win, block it.
  3. If you control center, he controls a side, and it’s only your second turn, take the adjacent side. This is a combo play and requires you to move in the corner between the previous side moves.
  4. If he has two adjacent sides then take the corner between them.
  5. If he has a corner and an opposing side, move in the other opposing side.
  6. If he has opposing corners and you control the center, move in any side.
  7. If no previous rule applies, take any space.

Here are the pictorial representations of the rules.
Codes on board

  • O = opponent’s space
  • X = my space
  • M = my choice of move
  • A = opponent’s assumed next move
  • P = my previous move of a strategy

C++ Code

This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.

One Response to “Rule-Based Tic Tac Toe”

  1. Jeffrey Landers Says:

    I found a 7th rule that is needed for UnBeatability. If Opponent goes to center than caddy corner rule 7 tells you to go to a corner.

    Of Course there are two unlisted rules, go to center if you can, and go to a corner against center 1st move.

    You found a good set of rules for unbeatablility with the 7th Rule addition.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>