Exploring Artificial Intelligence Through 4 x 4 x 4 Tic-tac-toe

Author

Franziska M. Plagwitz

Publication Date

12-5-2021

Document Type

Website

First Advisor

Freedman, Reva

Degree Name

B.S. (Bachelor of Science)

Legacy Department

Department of Computer Science

Abstract

Artificial intelligence is a fascinating computer science concept that has been popularized during the last few decades. Today, many processes are controlled by these programs, such as suggestion programs. The important concept that divides an artificial intelligence program from a standard program is that artificial intelligence means to emulate processes that are usually only possible with human decision making. However, instead of attempting to emulate human decision making directly, an artificial intelligence algorithm uses the computer’s extremely fast computation time to its advantage. This can be displayed in an A.I. opponent in video games, where the artificial opponent is programmed to make a calculated decision rather than a random one. For my capstone, I decided to explore artificial intelligence using two game decision algorithms for a game of 4 x 4 x 4 tic-tac-toe, as a means of creating a working A.I. opponent, as well as to compare the two algorithms implemented. For the game’s development, I used Unity as a framework and game engine. I was able to use Unity’s UI to create several objects for the game’s visuals. These included the scene in which the game objects would be set, the camera, a lighting object, and several canvas objects that are displayed at the start of the game as well as at the end of the game. As part of these canvas objects, I created text objects and buttons to be employed by the user to decide what kind of game to play, or to reset the game. The tic-tac-toe boards and pieces were generated using internal scripts that were attached to the objects in the Unity scene. These scripts were programmed using C#, and apart from creating the tic-tac-toe layout, added functionality to the above pieces as well as to some internal programs with which the user did not interact, such as the two A.I. algorithms and scoring algorithms. There are two modes in which a user can play: user vs. user, where a user can play against another user on the same terminal; and user vs. A.I., where the user can play against an A.I. opponent. I also implemented camera controls to allow ease of access to all pieces on the board, as well as a zoom feature. The finished product was converted to WebGL, an API that can be used to host Unity projects on an HTML page and hosted online via AWS CloudFront. The artificial intelligence algorithms used for the A.I. opponent were minimax and minimax with alpha-beta pruning. The two are quite similar, the only difference being that the latter is meant to optimize the former. Standard minimax simulates a game between two artificial players, the maximizer and the minimizer. These two artificial players have separate goals, the maximizer’s being to obtain the highest score of the simulated game, and the minimizer’s being to obtain the lowest score of the simulated game. A game is simulated for each possible move the A.I. can make, and overall, the highest score is chosen. The score produced is determined by which player wins the simulated game, as well as the number of turns needed to finish the game. Ultimately, the goal of each is to succeed in their task as quickly as possible, thus, procuring the optimal move for the A.I. to play given the current state of the board. Minimax with alpha-beta pruning is the same, except in order to optimize the decision making, it cuts out all moves that will result in a worse score than the current best scores for either virtual opponent, these comparison scores being called alpha for the maximizer and beta for the minimizer. The result of this pruning is that the algorithm will simulate fewer moves before coming to a final decision. In my implementation of minimax and minimax with alpha-beta pruning, I used a general tree data structure to traverse a game of 4x4x4 tic-tac-toe. A tree consists of smaller connected data structures known as nodes, where movement is solely unidirectional. A previous node can only be visited after reaching the end of the current tree branch, which is called a leaf/terminal node. In my implementation of the algorithm, the leaf node was reached when either the board was completely full, or a win was produced. For each node traversed, if applicable, child nodes were produced for each possible traversal from the current/parent node. The contents of the child nodes were inherited from the parent node and changed to fit the current state if a child node would be played. This included playing the child move as either the minimizer or the maximizer, changing the potential grandchild node to be played by the opposite player, and increasing the depth in the tree, and decreasing the score for the minimizer and maximizer to make the choice less appealing compared to a game state that finishes in a shorter amount of time. Every time a node is traversed, it is added to a running total of expanded nodes (expanded meaning that we had to view its inner contents). The theorized result when employing this calculation as a comparison between the standard and optimized minimax algorithms would be that standard minimax would expand far more nodes than minimax with alpha-beta pruning, since it would search through all possible games rather than cutting out branches that can be determined to be worse than the results of the previously simulated games. Overall, while difficult to see on a game of 4 x 4 x 4 tic-tac-toe, the fewer nodes expanded results in faster performance. This theory was confirmed from the results calculated after playing five completely random games using minimax and minimax with alpha-beta pruning. Minimax with alpha-beta pruning expanded consecutively fewer nodes than standard minimax. This project has been a very interesting experience. It allowed me to use software such as Unity, WebGL and AWS, which, apart from Unity, I had never had the opportunity to use before. As a result of using Unity, I also had to program all of my scripts in C#, which is a language I had never used before. Additionally, I was able to gain a more concrete understanding of the minimax algorithms as well as tree data structures. Importantly, this was also the first massive programming project that I completed on my own starting entirely from scratch. In my previous coursework, all other programs I wrote had concise guidelines for implementation, however, for this project, I had to decide how to implement the game by myself, which was quite a gratifying experience that has certainly increased my confidence in programming. In my opinion, this is the best result to receive as a graduating senior who is about to enter the workforce. If I had more time to add to my game, I would implement a greater range of camera controls, as well as changing the graphical UI of my game to make it easier to use. It would also have been interesting to allow a user to choose the dimensions of the game, making it an N x N x N game of tic-tac-toe, since this would allow one to see the difference in performance between minimax and minimax with alpha beta pruning for games where N is larger than the given 4 boards.

Comments

The game can be accessed via this link: https://d98ftdn2f1ctp.cloudfront.net/

Recommended Citation

Plagwitz, Franziska M., "Exploring Artificial Intelligence Through 4 x 4 x 4 Tic-tac-toe" (2021). Honors Capstones. 520.
https://huskiecommons.lib.niu.edu/studentengagement-honorscapstones/520

Language

eng

Publisher

Northern Illinois University

Rights Statement

In Copyright

Rights Statement 2

NIU capstones are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.

Media Type

Other