Computer Science Project Abstract
ANALYSIS OF TIC-TAC-TOE USING C++
Presenter:
Kyle B. Rader, Illinois Mathematics and Science Academy, 1500 West Sullivan Road, Aurora, IL, 60506; kyle@imsa.edu
Mentor:
Dr. Patrice Godefroid, Bell Laboratories Lucent Technologies, 2701 Lucent Lane (Room 9G-537), Lisle, IL, 60532; 630-713-4766; 630-713-4982; god@bell-labs.com
Abstract:
Is there a winning strategy for the game of tic-tac-toe? One can model this simple game using an AND/OR graph, which consists of two types of nodes, AND and OR. The analysis of the game focused on finding a winning strategy for the player who goes first. The graph consists of a single OR node at the top, representing Player 1's choice in opening moves. Each of the succeeding nodes would be AND nodes, representing the possible moves that Player 2 could take, and so on. An algorithm was developed using C++ that traverses the entire tree, and searches for a winning strategy. Some of the key components of the algorithm included information such as if one of the nodes below an AND node is false, meaning there is no winning strategy from that node, then that current AND node is automatically false. This means that the program would not have to analyze any succeeding games from that current node. This eliminated thousands of situations that the program normally would have to run through. After developing and running this algorithm, it was determined that there is not a winning strategy in tic-tac-toe for the first player.