Divider Connect on Facebook Connect on Instagram Connect on Twitter YouTube email Email RSS Icon >

Algorithms

Analyzing Near-Infinite Data Sets

Analyze Near-Infinite Data Sets
Find all the other Tic Tac Toes!
List All Possible Moves
Build a Game Tree
10249 Possibilites
Reduced to 17.5 Million Possibilites
November 13, 2006 at 2:14am

Predictive Analytics

Yash Singh
CIS4914, Senior Project
Department of Computer &
Information Science & Engineering
University of Florida

Advisor: Dick Deason,
rdeason@health.ufl.edu
ITCenter, HSC
Assistant Director
Systems Administration

Date of Talk: 5 Dec 2005

Contents

Abstract

The meteoric rise of Google Inc. is clear evidence of our desperate need for efficient methods for searching through information. Search engines have revolutionized the way information can be accessed. At the same time we are now faced with the problem of making use and sense of the vast amounts of information we have access to. Data warehousing is a field that gives us a solution to this problem. At the core of this field lie extraordinarily efficient data-mining algorithms that use data from the past to predict the future.

I am adding to this storehouse of knowledge by developing an algorithm that uses Game Theory and Group Theory to analyze the search space of the Tic Tac Toe game in 3-dimensions (6x6x6 board). I show that the second player can force a draw (assuming he plays intelligently). This entailed creating a game tree (a directed graph whose nodes are positions in a game and whose edges are moves); reducing its size using the concept of group automorphisms, intelligent moves; and then searching it to show that no matter what moves the first player made the second player could always block and force a draw.

Introduction

There are many open problems in Game Theory that have defied all analytical techniques. Computers have made it possible to demonstrate solutions to some of these problems using intelligent brute forcing. Developing techniques (such as using Group Theory for game tree pruning) help bring a number of unsolvable problems into the domain of the solvable. For example the method I use to generate the group of Automorphisms for the Tic Tac Toe board could be used by researchers tackling other open problems that have symmetry.

I have focused on the open problem regarding the 6x6x6 Tic Tac Toe board, namely proving that the second player can force a draw in this game. I present a computer aided solution that demonstrates the truth of this assertion. My research is supported my Gammilli’s [9] conjecture that the second player can force a draw if there are more points (total number of positions in the board) than lines (number of straight lines that form a Tic Tac Toe). Moreover Hales and Jewett [2] conjectured that the second player can force a draw whenever there are at lease twice as many points as lines.

The program and methods designed in this project will further help in the analysis of various other Tic Tac Toe boards. The program can generate pruned game trees for any 2-dimensional or 3-dimensional board, and with a small modification can handle any n-dimensional board as well.

1.1. Problem Domain

Problems regarding games such as Tic Tac Toe belong to Game theory. Game theory is a branch of applied mathematics that studies strategic situations where players choose different actions in an attempt to maximize their returns. My solution on the other hand relies heavily on Group Theory (group automorphisms) even though it uses certain concepts (game tree, strategic moves, and tactical moves) from Game Theory.

Progress has been made since the 1960’s when in their 1963 paper Hales and Jewitt [2] showed, using Hall’s well known marriage theorem, that the second player could force a draw on certain Tic Tac Toe Boards. Erdos and Selfridge [1] improved on the Hales Jewett result by further restricting the conditions under which the second player can force a draw. Paul [3] further added to the Hales Jewitt result by showing that whenever for a k-long board (the side of the board is k positions long) in n-dimensions the following holds k ≥ n+1 the second player can force a draw. Paul further improved the condition by showing that for the case that n ≥ 4, a draw position exists when k ≥ n. (For a complete discussion of draw positions see [7], [9].)

Moreover Gammilli’s [9] conjectured that the second player can force a draw if there are more points (total number of positions in the board) than lines (number of straight lines that form a Tic Tac Toe). Also Hales and Jewett [2] conjectured that the second player can force a draw whenever there are at lease twice as many points as lines. Finally Prof. Jonathan King of the math department at the University of Florida informed me about the work of his friend Oren Patashnik who showed in 1980 that the 4x4x4 Tic Tac toe is a first player win. I am greatly indebted to both Prof. King and Oren Patashnik for providing me with the basic approach for tackling the 3-d Tic Tac Toe board.

2. Technical Approach (Solution)

Deciding whether the second player can force a draw in the 6x6x6 Tic Tac Toe game requires one to build a game tree (Assuming we are aiming at a computer aided solution). This in turn involves estimating the hardware/software that would be required to do so. Finally we use group theory to prune the tree and show that player two can always block player one from winning. The following steps were taken to solve this problem:

  1. Set Up The Processing Environment: I set up a Server and Client on a Local Area Network. I used a Windows 2000 Server (with Microsoft SQL Server) and a Windows XP Machine (with IIS 5.1 and PHP 5.0). I tweaked the LAN for moving big chunks of data across the network by increasing the RWIN (TCP receive window) and using windows scaling. I set up Windows SQL Server to use a high speed hard drive. In addition both machines were configured to devote maximum possible RAM to the calculation of the game tree.
  2. Developed Mathematical Tools: This was the hardest part of the project and involved coming up with an algorithm that would prune the top layers of the tree. The idea is best illustrated by the use of examples. Consider the complete game tree of the 2x2 Tic Tac Toe board –
    We immediately see that the four boards in the second row are all equivalent since for player X all four positions are equivalent (It does not matter which corner of the game you pick to start the game. Keeping this equivalence in mind we can shrink the game tree to (Figure 2):

    Figure 2

    Figure 3

    Finally we note that at level 2 the last two boards are equivalent to the first one. The reasoning here is a bit more tricky. The idea is that you can take a board and change it to some other state as long as you maintain all the Tic Tac Toes (all possible lines e.g. XX, 00 etc.).

    The intuitive idea of equivalence is embodied in and central to Automorphism Groups. One can think of Automorphisms as the set of all boards that are equivalent to each other. The problem that the mathematician is faced with is to generate that Group. How do you do it?! I solved this problem my noting that:
    1. I can do something (e.g. rotate- 0,90,180,270 degrees or flip along horizontal, vertical, diagonal axis) to the board and still keep all Tic Tac Toes intact.
    2. I can move certain positions of the board in a special way (e.g. on a 4x4 board exchange all the centers with the corners) and still maintain all Tic Tac Toes.
    The important observation here is that there are two classes of automorphisms the ones where individual adjacent squares in the board are moved around (so that they are no longer adjacent to each other) to create an automorphism and in another where adjacency is maintained (for example a flip along the diagonal will preserve adjacency). The former can be generated by the symmetries of the board and the latter though a special algorithm that I use (refer to presenation slides).

    Once we know the Automorphisms we can rule out equivalent boards from the search tree. To give an example: In the 4x4x4 board we can cut down the initial (first three moves) tree size from 64x63x62 to 1x7x1. We effectively reduced tree size by a quarter of a million. In the 6x6x6 case we cut down the size by nearly 3 million game boards.
  3. Wrote Game Tree to database: This part of the project involved selecting data structures that would be efficient for calculating the game tree. The tree had to be built incrementally and placed into a database. Moreover the program had to build the tree intelligently i.e. It had to make both players play well (they would try to win when faced with the possibility of a win).
  4. Recursive Search on Game Tree: Finally to show that the second player can draw the 6x6x6 game I ask if the first player can win. If the first player can not win then we know that the second player forces a draw (second player can never win in Tic Tac Toe, Hall [3]). First Player can win only if for ever possible second player move there exists a first player move that guarantees victory.

3. Results

  1. The program designed to play Tic Tac Toe and build the game tree performed well. It constructed the 2x2 Tic Tac Toe tree flawlessly. Note: The 2x2 game board is represented as a string under column board.
  2. 2. For the 3x3 Game board I noted that all the wins were made at moves 5 and 6. This means that it is easier to consider the question whether or not the game is a first player win since we don’t have to dig deep into the tree. All wins are made at level 5,6 There are no wins beyond level 7
  3. I create the 6x6x6 game tree:
  4. Over 17.5 Million records:
  5. The first player cannot secure a win in each and every possible second player move. A recursive check of the tree fails to show a first player win.

4. Conclusions

5. Acknowledgements

The author would like to thank his advisor, Dick Deason, for his guidance, advice, and encouragement toward successful completion of this project. Additional thanks go to Prof. Jonathan King of the Department of Mathematics, for teaching me the basic concepts of Group Theory.

6. References

Appendix A



All wins are made at level 5,6