Example Code

A full featured 4x4 Tic Tac Toe Game

Code and Documents

Attachment

Summary

This demo project is a simple game: 4x4 Tic Tac Toe.

 

The program provides an easy to use and intuitive user interface, yet provides a wealth of features. There are several levels of playing strength (the highest playing perfectly), undo history, play against a human for either side, or self play with selectable strength for each side. There is full coaching functionality via an intuitive color system if desired, either to get hints or to explore the depths of the game. It also contains a set of difficult problem positions to entertain the user interested in puzzles.

 

The game

The game takes place on a 4x4 board and involves two players, X and O. X starts and players take alternate turns. The object of the game is to place four of your pieces in a row, either vertically, horizontally, or diagonally. If this is achieved, the game ends in a win, otherwise the game ends in a draw once no more moves are possible.

 

How to play

From the default settings after start of the program, simply click  on one of the 16 positions of the board to start playing. Or set O to “manual” and press “Play!” to have the computer start as X instead. Explore the controls for more options. All (or most) controls have context help and tip strips, so hover over a control for quick details or press ctrl+h for the context help if desired.  Press the "about" button for the welcome dialog containing a few tips.

 

The Game AI (artificial Intelligence)

While it might not pass the turing test, the program has full knowledge of the game, obtained from a retrograde analysis of all possible positions. It has an embedded database of all 462327 decisive positions, any position not in the database is known to be a tie (or impossible to reach). The computer opponent can play perfectly and will randomly pick among all equally best possible moves. Under perfect play, the outcome is always a tie. To give the player a chance, the computer opponent playing strength can be reduced to two easier levels. When set to “weak”, the computer will also include one “second-best” move in the pick list, thus there is a chance that it makes mistakes like a human. When set to “random” all possible moves have an equal chance of being played, the weakest setting available. (Of course we could program an even weaker setting where the computer picks only among the worst moves, but what fun is that?)

Each side can have a different strength setting and the computer can play against itself.

 

Undo buffer

For each game, the computer maintains a history of all moves, so a finished game can be inspected move by move in both directions. Enable hints during replay to see where mistakes were made. From any position a new move can be initiated to try a different line.

 

Hint system

Since the quality of each possible move is known at all times, the program is configured to give hints to the users if desired. Hints can be permanently enabled via a check box or shown only temporarily as long as a button is pressed. Hints are shown via a color code on all empty fields. Winning moves are shown in green, the color intensity indicating the number of moves needed to win. The more intense, the quicker the win. Similarly, losing moves are shown in shades of red. The more intense, the quicker the loss. Neutral fields are colored yellow.

 

Problem mode

From an extensive mining of the database, the longest forced win is “win in four moves” and there are several hundred such positions (or about 8 times more, considering symmetry related transformations). Among those, there are 32 such positions that have exactly one solution, so these are considered the hardest problem for a human. These 32 positions can be called up and the human will have a chance to try to win against a perfect computer opponent. One mistake and it's a tie or worse, so think twice :D.
You can of course give up and ask for a hint.

 

Whenever a new problem position is selected, hints are automatically disabled again in order not to spoil the fun.

 

Code Notes

The main program is designed as a simple event based state machine to handle user events.

The board recalculation is done in the timeout case as needed. Any regular event that needs a board recalculation sets the timeout to zero to trigger it. If recalculation is not needed, the timeout is set to infinite (-1). Nothing fancy such as objects, user events, or x-controls, the code should be understandable by most. Still, all code sections are optimized to the best of my knowledge, so studying the code and trying to understand it might prove insightful as a learning tool.

 

There is extensive documentation via diagram comments, no need to repeat it here.

 

The game database is contained in a diagram constant. While it was generated in LabVIEW a couple of years ago for the tic tac toe challenge, the retrograde analysis is not included here. The code is quite esoteric and uses extensive caching, binary searches, and bit-wise operations to speed things up. Maybe I will have another stab at it in the future and bring the code in a presentable form at a later time. Boards are stored as single U32 integers, with the bits representing the pieces present. The score for each position is an I8 constant. Only unique positions are stored. Eliminating all symmetry related transformations reduces the database significantly. Since only decisive positions are included and all tied or impossible positions are eliminated from the database, the final size is manageable (<2MB). Scores are grouped by the number of pieces present, so only a subset of the database needs to be searched for any given table look-up.  (Except for the database, this program has little to do with the earlier published TTT-trainer that just provided a database lookup, without any play options)

 

Steps to execute code

Extract the attached zip file into a new folder and open the project.

Open the toplevel VI (4x4TicTacToeGame.vi). Inspect code at leisure, or run the VI to play.

 

Any suggestions for improvements are welcome of course. I am sure there are bugs.

 

Screenshot

 

TicTacToePanel.png

 

An example game with both sides manual and hints enabled.

X has to move and can win by playing the upper left corner. A move near the center will lose, and a move on the other corners will keep the game tied under optimal play.

With hints disabled, all empty fields are white (and the player is in the dark :D)

 

VI Snippet

TTT-Scoring.png

Sorry, no snippet just a screenshot of the scoring function.

The code is too complex for a snippet and would not run standalone anyway.

 

VI attached below

Zip File of project in LabVIEW 2010. This is the official entry, uploaded before the deadline.

 

(I also included a 8.0 and 8.6 version for legacy users. No guarantee that they work. The LabVIEW 8.0 needed a minor code change in the move generator to eliminate the conditional FOR loop terminal.)

Example code from the Example Code Exchange in the NI Community is licensed with the MIT license.

Comments
altenbach
Knight of NI Knight of NI
Knight of NI
on

I am not sure why the 8.6 version is only 1.1MB, vs 2MB for the LabVIEW 10 version. I hope nothing got lost in the down-conversion. I was not able to convert to 8.0, because I use the FOR loop with the conditional terminal, which is not available in 8.0.

Darin.K
Trusted Enthusiast
Trusted Enthusiast
on

Strange game, the only winning move is not to play...

Probably just dated myself, and those who get the joke....

altenbach
Knight of NI Knight of NI
Knight of NI
on

OK, after spending a day at the NI technical seminar, I made a quick modification so I can downconvert to 8.0. The 8.0 version is now also attached and has a minor change in 4x4TTTMove80.vi to make it compatible. The other versions use 4x4TTTMove.vi.

I also noticed that I could separate the compiled code in the LabVIEW 2010 version, which would reduce the zip size to ~1MB. Good to know for next time.

Something I don't quite understand is the fact that if I separate the compiled code, the compiled code cache AND the subVI of 4x4TTTEvaluate.vi are both about 1MB. Seems like the large diagram constant is stored in both places. Seems redundant, but I guess that's simply how it is.

altenbach
Knight of NI Knight of NI
Knight of NI
on

Darin.K wrote:


                       

Strange game, the only winning move is not to play...


                   

Sorry, I haven't seen the movie, even though I am pretty "dated"....Besides, that was 3x3.

The object of the human here is to keep a tie (not lose!) against a perfect computer player. Seems easy for us, but some kid might have fun with it.

Try some of the problem positions instead! Maybe it will keep you occupied for a few lazy minutes to solve all 32.

Ben_Phillips
Member
Member
on

How is this buried after only four months?  I found this only by accident.  Fantastic example.  I've seen quite a bit of code that is not interesting that gets more kudos than this.

altenbach
Knight of NI Knight of NI
Knight of NI
on
> How is this buried after only four months? This document was an entry of the 2010 example code contest. It was later moved to a new permanent place and probably lost the earlier ratings during the move. Not sure. And yes, I agree with you, the code showcases quite a few neat (IMHO) programming tricks that could be useful in other situations. 🙂
altenbach
Knight of NI Knight of NI
Knight of NI
on
_Faust
Member
Member
on
You're my hero; I learn a lot from the way you organize your block diagrams and your conding. thanks!
_Faust
Member
Member
on
You're my hero; I learn a lot from the way you organize your block diagrams and your conding. thanks!
_Faust
Member
Member
on
_Faust
Member
Member
on
sh*t triple post due to the message "An unexpected error has occurred. Please make sure that your session did not expire while viewing this page." Apologies!
altenbach
Knight of NI Knight of NI
Knight of NI
on
I had the same problem earlier. There site shows an error, but the answer is posted anyway....
StevenHowell
Member
Member
on

love that movie...one of my favorite 80s movies....still laugh when I see the size of the floppy disk's and the telephone modem....those things actually worked!

Steven Howell
Controls and Instrumentation Engineer
Jacobs Technologies
NASA Johnson Space Center
Contributors