Tic-Tac-Toe

Tic-Tac-Toe is often used in introductory computer science / game theory class as a basis for using a Minimax and game tree algorithm approach. If brute-force is used, moves appear to proliferate to tens of thousands. This is still feasible with computers. However, the more sophisticated game-theory approaches seem like the next sensible step especially when the professor is eager to find a simple enough game that can illustrate advanced concepts.

In practical terms game theory is overkill for Tic-Tac-Toe in particular.

I have searched the internet and have not found other simple Tic-Tac-Toe playing methods. That's why I decided to make this tutorial.

It started as a challenge in the late 70s in university to create the smallest unbeatable Tic-Tac-Toe program using APL. My second attempt resulted in a 'winning' entry. At home I implemented it in BASIC on a TRS-80 Model I just for fun.

Conditions:
    1) Person vs. computer
    2) Person moves first
    3) Computer never loses

Even forty years later there don't appear to be any efforts towards a minimal strategy solution.

Here I offer a description of my solution.

But first, here's a playable demonstration.

  Tic-Tac-Toe

Note: The computer's response is always preceded by a deliberate 0.8 second delay. This is to make game playing feel more natural. It greatly exaggerates the true computation time.

Although the last condition "computer never loses" would make game play boring for most people, it was essential to maintain perfect game quality from the computer's point of view. It is assumed to necessitate the most challenging logic.

If these conditions are not exactly what you require then this strategy will be of limited use to you. For example if the computer may move first then a different set of machine countermoves must be developed.

Strategy A, B

A) Primary objective for every move response is to either win, if possible, or block the person if required.

B) If there is nothing better to do: pick middle if not already occupied. Else pick any available corner at random or if they are occupied pick any available side at random. Randomness gives the games variety.

That's pretty much it. Well, most of it. There are a few exceptions.

In the diagrams below the person plays "x" and the computer plays "o".

Strategy C

One of the following special cases 1 and  2.


1) Person occupies diagonally opposing corners.
Computer Response: Pick any side at random instead of corners which are normally favored.
or
2) Person occupies a corner and a side or adjacent sides.
Computer Response: Pick intersecting corner.

What remains is to code efficient pattern recognition that takes into account board reflections and rotations.

Include the necessary logic to prevent a person from playing occupied squares and to announce "computer wins".  Some sort of graphical display finishes the program.

This completes the strategy. It's very simple!

As you can see there is no look-ahead logic at all. No move simulator or evaluation function. Just pattern recognition and canned responses.

 

Update 2015

While writing this online playable demo I have improved my strategy slightly. I modified case C(2) for the adjacent side pattern to have the computer's response include more corners.


Person occupies adjacent sides.
Computer Response: Pick any corner at random except the one diagonally opposite.
Plus I added one more special case:

Person occupies two corners and opposite side.
Computer Response: Pick any side at random.
This forces the person to block more. If the computer had responded with a customary corner move, it and subsequent moves would be pointless.

My fascination with Tic-Tac-Toe can be traced back to 1967 at the world's fair Expo 67 in Montreal, Canada. I was 12. The Bell Telephone Pavilion had a computer which played Tic-Tac-Toe with its visitors. The board was a large vertical screen set into the wall which had red and green Xs and Os rear projected on it. This somehow demonstrated telephone switching. Reading about it now I learned that the "computer" was implemented using relays such as would be used in telephone switching.

My second exposure to a Tic-Tac-Toe playing computer was at the Ontario Science Centre in the early 70s. The boards were represented on a Flip-disc display. In addition the keypads consisted of nine backlit buttons that lit up red or green. There were either six or nine such games going on simultaneously. I forget exactly. The computer they used was a HP2100 series minicomputer at one point and later a PDP-11 minicomputer.

I've always wanted to design a Tic-Tac-Toe machine made with relays. This minimal strategy logic, if fully implemented in relays, would however be a very complex project.


The following page describes the playable demonstration JavaScript program in more detail for those interested.

Revised 12 Oct 2015