DaWei

This tic-tac-toe game makes absolutely no logical evaluation in choosing its response to the player's move. Rather, it plays by experience. Each pattern carries a history of its win/loss/draw record. The history is built by training. The record is easily converted into probabilities for a win, loss, or draw. If you are familiar with probability and statistics, you will recognize that an index of effectiveness determined in this way is every bit as good as a similar index provided by exhaustive and accurate logical analysis. If the training is purely by observation, then the number of games observed must be large enough for the observed value for any pattern to converge on the true value attained by calculation.

The most interesting thing about this design was the development of a training process. There are a number of subtle and not-so-subtle gotchas. Brute force training is somewhat akin to swatting a fly with a battleship's broadside: it's distinctly effective, but a tad inelegant. The thing about the training is that it has to happen just once, ever. This would tend to suggest that one should bite the inelegance bullet, start the training, and just go away for a while. The probabilistic approach to solving the game, however, represents a possible solution for an entire class of similar problems. One example is pattern recognition for purposes of identification. The investment of time in researching various approaches may well provide, ultimately, a greater return.

Another major premise of the design is that all valid tic-tac-toe patterns may be reduced to a smaller subset, which I call the Basic Patterns. There are many such subsets, any one of which is as effective in driving the game as any other. The subsets exist because many patterns are equivalent. They will be found to be identical to other patterns if one subjects them to a transform comprising some number of rotations and or reflections. Consider that you have a transparent tic-tac-toe board containing some pattern. You may view the board from any of the sides, from above or below. Your visual perception of the pattern may assume up to eight different forms, but the pattern has not changed, nor has the most effective response. Consider, also, that as first player you have your choice of nine different places to make your move. In reality, you have only three: a corner, a side, or the center. If the upper-left corner, the top side, and the center are designated as being Basic Patterns, the other 6 possible moves are equivalent to one of the three.

The number of Basic Patterns is 850. If one tosses the patterns that would evolve after a game-ending condition (a win or a draw), the number drops to 765. The set of patterns forms a tree of pattern objects. The root is the initial, blank pattern. Level one contains all valid responses (first play) to this parent pattern, reduced to members of the set of Basic Patterns. Level two contains all valid responses to each of the members of level one. The tree is a sort of bastardized general tree. I say bastardized because two parents may have identical or equivalent children. When second and subsequent children are discovered, they are not stored again as children of the new parent. The parent is merely given a reference to where the initially discovered child lives. If the parent wishes to visit this child for hugs or to measure its shoe size, or for any other purpose, it takes the reference (an ordinal), lines up all its nieces, nephews, and children, in order of age, and counts down to number 4 (or whatever), and there the little booger is. A parent's list of children comprises the ordinal and a record of any transform needed to discover the equivalence of the original child to the current child. The ordinal is applied to the next level of the tree, of course, in order to access all members of the child object. Note that the level of any pattern in the tree is equal to the number of moves it contains.

A play is treated as a distinct entity. A pattern is submitted and a response is returned. Except when training, there is no "game" continuity beyond that which is inherent in the latest response being viewed as the next problem for the player. The start button begins a game at any time. The difficulty and aggression controls may be changed at any point in the game. The symbol and order of play controls are effective only at the time a game is started. The game ends when an ending condition (win or draw) occurs. A win is assigned to the player who chose the pattern with the winning condition. A loss is assigned to the other player.

What the hell is an "aggression control", you ask? The outcome of the game is, of course, ternary: a win, a loss, or a draw. The outcome may be viewed a binary; that is, it is either favorable or unfavorable. In conservative play, the machine chooses the response with the least probability of loss. In aggressive play, it chooses the response with the greatest probability of a win. In other words, aggression is in how one weighs the value of a draw. Aggressiveness is not a good strategy unless one is playing a brain-dead rock and can hope for a blunder against a flaky move that offers hope of a win, rather than a draw. Furthermore, not all responses offer choices that can be influenced by the probability of a draw.

At maximum difficulty, the machine chooses the strongest response. If there are two or more equally effective moves, one is chosen from among them at random. If the difficulty level is set at 50, the machine chooses at random from the top 50% of the available responses. If the difficulty level is set at zero, the machine chooses at random from the top 100% of the available responses (purely random play). And so it goes. Note that in the early and late stages of the game, where responses are few and some moves are equally effective, a difficulty level of 50 or upwards may be as good as a level of 100.

I believe, without having numerical proof at hand, that the machine is adequately trained. I think that if you play it at maximum difficulty and minimum aggression, and let down your guard, it will kick your ass.

There are two versions of the game: a web app and a stand-alone app. The web version is Python-cgi on the server side and Javascript on the client side. The play-response cycle is handled by asynchronous requests. There is some inevitable delay in returning the response. The stand-alone version is also written in Python, using wxWidgets. The code is deliberately written to serve as pseudo-code. You should be able to translate it into any of a half-dozen of your favorite languages. There is also a great deal of redundancy. Some of this is to provide hooks for testing and debugging. Primarily, though, it is for purposes of clarity and focus in understanding precisely what the cottonpickin' game is trying to do. I had to adjust some paths for the zipped stand-alone version, but it seems to work; if you have any problems, contact me. As far as the web version's server-side and Javascript, you'll need to adjust it for your own host's directory setup.

Usual caveats: the program may eat your machine, your dog, and his homework.

Play the game. See the attachment for the code.

Enjoy!

Attached Files

pTac.zip (52.8 KB, 32 views)

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Prm753

Intresting game. Won once, turned agressiveness down, and drew with the computer three times. On the fourth game, the computer couldn't decide what square to mark in (both would have resulted in a draw). After about 30 seconds, a Message Box came up with the words "Error: ".

Here's a screeny of the frozen game (after I closed the error box): http://bellsouthpwp.net/p/r/prprogramsstudios/error.gif :beard:

__________________
The world's first athletic computer geek!
The home of PrProgramsStudios
How not to post a question: <-- Please don't reply

DaWei

Aggressiveness makes the machine play worse. The error is when the asynchronous request breaks down (unless you see a message specifying that the Play procedure detected an anomaly). My site is servicing sales data for a few automotive dealerships. Some times of the day are worse than others. Maybe I should add a "resend" button on the web version, since the play is treated in a totally standalone manner, without any reliance on previous or subsequent plays.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Silvanus

DaWei- Have you never watched sci-fi? You have created an abomination and released it upon the unsuspecting masses. It's only a matter of time before it goes from playing me to a stand-still in Tic-Tac-Toe to taking over the world.

Seriously- nice little program.

__________________
:wq

DaWei

I'm somewhat embarrassed. After I translated the standalone version into the web version I didn't even look at it in IE. The layout sucks (IE doesn't recognize the table-row attribute), and I didn't hack in the Active-X control for the asynchronous request. I just found out yesterday. I'll be fixing it for IE.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Ooble

It's bloody cool - I'll have to check out the code. I'm hoping I'll understand it.

__________________
Me :: You :: Them

Mocker

I haven't checked out the actual game yet, but your write-up was pretty damn interesting.

I guess, this being a programming forum, I could look at the code, but how do you store and load the training? Is it preset or does it continue to learn with each game?

__________________
#programmingforums relay - http://thegupstudio.com/cgi-bin/pforelay.cgi
freelance scripts - http://ryanguthrie.com/index.html

Jessehk

I've just become a lot more clear on how these things are made. Thanks for great write-up!

__________________
Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

DaWei

The machine could continue to learn (acquire experience) with each game, but it doesn't except in training mode. One reason is that the web version does not keep track of an entire game. It treats each move independently. The appearance of a game is strictly because one move follows from the previous move. There is nothing that would prevent someone sending a single, externally generated move to the machine and getting a response. As a matter of fact, that's a mechanism in my test and debugging code. There would be some difficulty in assuring that the statistics weren't being manipulated in the web version. Consequently, I don't track the game.

The second reason is that the additional experience would represent about .1 percent of the experience currently in place. I had about lebenty four versions of training. The current one is more of a calculation which is conducted 'backwards', beginning with the ultimate moves. All of the final (ninth) moves result in either a win or a draw for the last player. This means that the player making the 8th move will always either lose or draw. This player can win only because there are winning positions earlier in the game. By working backwards, calculations involving a position only have to be made once, instead of each time a line of play incorporates that particular position.

The whole problem with observations is that, unlike a coin toss, the events are not independent. If one trains the game with moves chosen purely at random, there are positions that can have a fairly good probability of winning, simply because the opponent is also playing at random. Thus, blunders have a distinctly good chance of occurring, thereby rewarding poor play. The figure can only be rectified by training the machine against 'good' play, rather than random play. There is a sort of catch-22 here. Where does 'good' play come from? A huge part of it can come from random play, but, as I just mentioned, there are holes in the philosophy. Consequently, I use some actual calculations regarding the probability of outcome, rather than observing a large number.

Fortunately, the tree is somewhat like an overweight woman -- thick in the middle, and tapering at both ends. Still, if one begins all training games at the beginning, the beginning positions will be honed unnecessarily while the middle positions will be straining to acquire enough observations for the percentages to converge on the true percentages.

As I mentioned in the original post, the training is the most interesting part of the process.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

DaWei

Just an additional thought. This game and a number of test methods were designed before anything was ever coded. As a matter of fact, early parts were coded in C and PHP before the shift to Python. If you've looked at the code for the standalone dialog, you've seen a lot of stuff that you might wonder about. This is a shot of the game with training enabled.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers