Tic-Tac-Toe

This project is an intelligent system demonstrating the application of adversarial search strategies in ensuring optimal gameplay. In particular, the agent plays tic-tac-toe (also known as noughts and crosses) against a human player. The system has six levels of rationality; while the level 0 agent selects its moves only randomly, winning against the levels 1 to 5 agents is guaranteed to be an impossibility. Moreover, in the interest of algorithm analysis, the program also tracks the match statistics and the decision time spent per move.

This application follows the classical version of the game, where two players take turns in placing their tokens (X's and O's) on a 3 x 3 board and the winner is the player who first places three of their tokens to form a complete row, column, or diagonal. It is to be noted that tic-tac-toe is a solved game resulting in a forced draw given perfect play from both parties.

Task

Tic-tac-toe is a major course output in an introduction to intelligent systems class under Dr. Judith J. Azcarraga of the Department of Computer Technology, De La Salle University. The goal of the agent is to form one of the eight winning configurations before its opponent, thus winning the game. This application exhibits six levels of rationality, distinguished by the complexity of their goals and their underlying algorithms:

• Level 0: The agent decides on its moves randomly as long as the position is unoccupied.
• Level 1: From this level onwards, the agent also aims to actively prevent its opponent from completing a winning configuration. In order to do so, it consults a hard-coded table of optimal moves per board configuration.
• Level 2: The agent employs the standard minimax algorithm (a depth-first search strategy for adversarial games).
• Level 3: The agent combines the standard minimax algorithm with alpha-beta pruning to decrease the size of the search space.
• Level 4: From this level onwards, the agent also aims to win in the least number of moves. In order to do so, it employs a depth-sensitive variant of the minimax algorithm.
• Level 5: The agent combines the said depth-sensitive variant of the minimax algorithm with alpha-beta pruning to decrease the size of the search space.

In addition to the match statistics and the decision time of both players, the evaluation of the agent is also displayed whenever applicable. Below is a screenshot of the gameplay:

The project consists of three folders:

• api - Javadoc documentation of this project
• out - .class files
• src - .java files (source codes)

Besides the Tic Tac Toe.jar file, it also includes the following document:

• Technical Report.pdf - Formal discussion of the levels of rationality and behavior of the agent

Built Using

This project was built using Java following the Model-View-Controller (MVC) architectural pattern, with the .class files generated via Java SE Development Kit 14. The graphical user interface was created using Swing, a platform-independent toolkit that is part of the Java Foundation Classes.

Authors

• Mark Edward M. Gonzales
  [email protected]
  [email protected]
  

• Hylene Jules G. Lee
  [email protected]
  [email protected]

Assets (images) are properties of their respective owners. Attribution is found in the file src/gui/assets/asset-credits.txt.