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 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.
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.
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.
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 .
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.
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)
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.
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 )
Sorry, no snippet just a screenshot of the scoring function.
The code is too complex for a snippet and would not run standalone anyway.
Zip File of project in LabVIEW 2010. This is the official entry, uploaded before the deadline.