The image above was created using AI. More specifically, this was the fourth image generated by Stable Diffusion, when given the prompt “Harvard AI”.

Today officially marks the end of the second week of my participation in the Harvard Summer School Program. I therefore felt it appropriate to post about my experiences in my courses, which is why the following posts will most likely be about interesting projects and assignments I do here. In this post, I will (in broad strokes due to Academic Integrity reasons), discuss my first project of the course, tictactoe.py.

For our first project in this course, we were essentially tasked with coding an algorithm in which a computer, running the algorithm, would play optimal moves, and therefore would either win or tie. For the full instructions from OpenCourseWare, click here. At the core of this program was supposed to be integrated an algorithm called the Minimax algorithm.

In the context of Tic-Tac-Toe, the Minimax algorithm is a decision-making algorithm used to determine the optimal move for a computer player. The algorithm explores all possible moves and their outcomes by simulating the game from the current state, doing this by constructing a game tree that represents all possible moves and their subsequent states.

The algorithm assigns a score to each terminal state (win, loss, or draw). The goal of the computer player is to maximize its score while minimizing the opponent’s score. The algorithm achieves this by assuming that the opponent plays optimally and recursively exploring all possible moves and their outcomes. It therefore optimizes its priorities to be as balanced and consistent as possible.

Starting from the current state, the algorithm evaluates all possible moves by simulating each move and recursively applying the same evaluation process to the resulting states. This continues until a terminal state is reached, at which point a score is assigned. The algorithm then backtracks, propagating the scores from the leaf nodes up to the root node, keeping track of the best move and the corresponding score.

By considering all possible moves and their outcomes, the Minimax algorithm can determine the optimal move for the computer player. It guarantees that the computer will never make a losing move if a winning move exists and will choose the best possible move to maximize its chances of winning or forcing a draw.

An example of this can be represented in the following graphic:

Here, we have a board (on the very top), that the minimax algorithm is evaluating. For the purposes of simplicity, the player scores a board in which it is winning as 1, a board in which it is losing as -1, and a board which is a draw as a 0. One layer deep into the Minimax algorithm, it considers the three boards on the second row. It checks if the game is over on all boards, and if it is not, will recursively continue this algorithm until every possible position has been considered. After it does so, it looks at its most favorable outcomes. In this case, it has detected a situation in which it wins in the next move (board value of 1), making that board worth the most points, as the maximum value possible in any situation is 1. The algorithm therefore plays that move, winning the game.

In this way, although the vanilla Minimax algorithm is not always the most efficient, it will always output optimal moves, as it can essentially see into every future.

On another note, I really wanted to include some of my own code, but after a discussion with the Head Teaching Fellow of the class, was told that such would constitute an “unreasonable act” and would therefore be a violation of the course’s academic integrity policy.