The design and analysis of tic tac toe

ZhangYi+Heng

【Abstract】Tic tac toe is a small-scaled application developed to simulate a situation of the game tic tac toe， with two players： computer and the user. The application intends on guaranteeing a winning or at least a draw outcome for the computer by playing its each move. Based on the objected-oriented idea， the application is also developed to show the branch of artificial intelligence and game theory using the simple game as an example. Therefore， the essay presents the applications algorithms and its theory behind it with an aim to further explain the theoretical and practical use of the application.

【Key words】small-scaled application； object-oriented； game theory

1. Introduction

Tic tac toe is developed and achieved based on the notion programming. It also adopts theories， such as game theory， to simulate an imaginary game between two players.

It appears simple to create the chessboard and have a game with players and similarly simple for the computer to take moves according to tactics and strategies that often depend highly on game designs to take effect. Nevertheless， the application aims not on the calculation and deduction capable of applying only on the game tic tac toe， but the game theory behind it. The theory， in this context， enables the optimal calculation considering all results and is theoretically applicable to all types of chessboard game. But unlike the naive solution， the theory wisely omits a considerable part of calculation and ensures a winning or at least a draw for the computer side.

The theory is achieved though the design of the application which is divided into two parts： main game process and interaction and an additional part attaching to the game process —the AI. The game process creates the situation of the game， including the simulation of a chessboard， some chessmen， two players （one is AI）， a judge and a loop. The interaction part passes the users operations to the game process and sends back the calculated information， including the computers move and the location of the chessmen to the user interface （UI） back to the user with an aim to continue the game loop.

2. Basic theory

2.1 Game theory

Wildly used as it appears in maths， logic and typically computer sciences， the game theory guides and helps play correct moves on the computer side， profits maximized while losses minimized. In a zero-sum game like the tic tac toe， where one participants gains are exactly balanced by other participants —in this game， the opponents—losses， players are forced to make their max gains at each move. Hence， theoretically speaking， the prediction of opponents move is only and clear. Then what is left to search through is a tree that considers both sides moves and ends once the result is clear. By avoiding any branches leading to losing and preferring those of winning， the computer is unbeatable because of the game its self is designed all but fair（regardless to the first-move advantage）， 50-50 chance for either side to win.

3. The design

3.1 The game process and interaction

The object-oriented application completes the game process by two steps： the static items， roles and rules and the dynamic game loop. Using constructors， the application begins with the creation of the elements， including chessmen， chessboard， the AI， the judge and the encapsulation of these elements into the class play， and finally reset each element to initialize a new game before it starts. During the loop， the not only object- but user-oriented game take the loop in a convenient way， in which the loop pauses and continues only after the user has taken a legal move. Therefore， the loop is not normally constructed by a pausing function for UI-background interaction named button click， which transits the users operation into computer data and calls AI afterwards. Under the direction of this function， the game loop is designed to work from button click to AI and back to button click as normal players are playing the game in turns.

3.2 AI

The AI achieves an adoption of the game theory to the application. It instructs the computer to think like a common human with a thousand folds more of calculation ability. Normally， a human player would avert all the potential results that lead to failure if none is left of those that prove advantageous， similar to minimax. Based on the game theory， so does the computer think like human players， Diagram is shown in figure 1.

4. Conclusion

For both entertainment and study purposes， the application recreates a game， establishes Artificial intelligence applying in that game and thus shifts the calculation successfully from human to computer. The development of tic tac toe specifies the transition between theories and application， visible images and digital data， and between reality and virtual simulation. In the meantime， it stresses and put into practice the framework and outline design that clear thinking and programming problems to a significant extent.

References：

[1]Game theory is “the study of mathematical model of conflict and cooperation between intelligent rational decision-makers”，which is mainly used in economy，political science and psychology，as well as computer science，according to https：//en.wikipedia.org/wiki/Game_theory.

[2]A Zero-Sum Games is a mathematical representation of a situation in which each participant's gain（or loss）of utility is exactly balanced by the losses（or gains）of the utility of the other participant（s）.More information on https：//en.wikipedia.org/wiki/Utility.

[3]Minimax is a decision rule used in decision theory，game theory，statistics and philosophy for minimizing the possible loss for a worst case scenario.More information on https：//en.wikipedia.org/wiki/Minima.