An Undefeatable Tic Tac Toe AI – Minimax Algorithm in GDScript

Getting Back Into Gamedev

I recently decided to get back into video game development and wanted to ease myself back into it with a project I knew wouldn't present too much of a challenge. I had been getting into board games recently, specifically Catan, Pandemic, and Go. I figured that would be a good lane to follow as board games have strict and well-defined rulesets. And as primarily a programmer, making the visuals for a board game seemed easy enough.

As I delved further into what board game I could make, the real project revealed itself. I wanted to write an AI that played against the human player.

To me, a good AI behaves how you would expect another human player to behave. But implementing that was going to be tough. Computers are only able to think binarily. Is this a 1 or a 0? Is this true or false? Sure you can program more complex logic by stacking this concept, but that's all that's really going on behind the scenes.

I knew I needed simple game since I had no idea how complex it would be to program a convicing AI. I settled on Tic Tac Toe. It's a children's game. Easy to learn, easy to play. And there was only 9 spots on the board. How hard could it be?

Tic Tac Toe in GDScript

I started off by making a 2D array; that is three arrays nested within an array, to result in a 3 x 3 grid. I populated each index with a value of 0.

const GAME_BOARD_SIZE = 3

func create_board():
	var board = []

	for x in range(GAME_BOARD_SIZE):
		board.append([])
		for _y in range(GAME_BOARD_SIZE):
			board[x].append(0)

	return board

By doing it this way I was able to use an x and a y value to access each index of the board, using the syntax board[x][y]. The upper left corner of the board can be accessed with board[0][0]. The upper right corner of the board can be accessed by changing the x value, which would be board[2][0]. The bottom right would be board[2][2].

The next step was to implement the visuals. I used a color generator website to come up with a color theme that had distinct colors. A dark background color, and three bright colors for the lines, the X's and the O's.

https://coolors.co/generator

The visual board reflected the state of the 2D array. A 1 represented the O's and a -1 represented the X's. I chose these values so that they would be compatible with the AI algorithms we would be using later. I wrote a function to map the 2D array index (ie board[1][1]) to the game window coordinate.

func map_to_board(coordinate: Vector2) -> Vector2:
	return Vector2(400 + coordinate.y * 400, (coordinate.x) * 400)

Random AI

The next step was to implement the AI algorithms. Each AI would have the same entry point function, get_move(). That function would take the board state as argument and return the index of the resulting move.

A completely random AI would be the easiest to write and the easiest to play against so that's where we started.

The first step was finding all the empty spots on the board. This was pretty straightforward, iterate through every spot and if it had a value of 0, add it to the resulting array.

func get_empty_spots(board) -> Array:
	var result = []

	for x in range(board.size()):
		for y in range(board[x].size()):
			if (board[x][y] == 0):
				result.append(Vector2(x, y))

	return result

We put this funcion in a Singleton class since every algorithm would need this function.

After getting all the empty spots in an array, we simply shuffled the array and returned the spot at the back of the array.

func get_move(board) -> Vector2:
	var empty_spots = Common.get_empty_spots(board)
	randomize()
	empty_spots.shuffle()
	return empty_spots.pop_back()

While this algorithm works, it is far too easy to defeat. It has zero strategy. It won't block the player from winning nor will it make the winning move if it has the chance. The next step was to fix that.

Random AI But Smarter

Obviously if the next move will result in the AI winning, that's the move it should make. And it can't win, then it should block the player from winning if it can.

We'll write two helper functions for this, win() and block_win(). They both check if any of the next possible moves will result in either scenario by playing the move as the AI and as the player.

func get_move(board) -> Vector2:
	var result = Vector2(-1, -1)

	var win = win(board)
	var block = block_win(board)

	if (win != Vector2(-1, -1)):
		return win
	elif (block != Vector2(-1, -1)):
		return block

	return get_parent().get_node("RandomAI").get_move(board)

func win(board) -> Vector2:
	var result = Vector2(-1, -1)

	var empty_spots = Common.get_empty_spots(board)

	for i in range(empty_spots.size()):
		if Common.check_for_win(board, empty_spots[i], 1):
			result = empty_spots[i]

	return result

func block_win(board) -> Vector2:
	var result = Vector2(-1, -1)

	var empty_spots = Common.get_empty_spots(board)

	for i in range(empty_spots.size()):
		if Common.check_for_win(board, empty_spots[i], -1):
			result = empty_spots[i]

	return result

And if no one can win in the next turn, then the AI will revert back to making a random move by calling upon the "RandomAI" get_move() function.

Humanlike AI

And while the RandomButSmarterAI won't make a game-ending mistake, it still makes poor early-game moves. Next we will make an AI that makes moves similar to how a human plays Tic Tac Toe.

Human players tend to focus their efforts on the center spot and the corners, since those have the most potential for victory. To improve the AI even further, we have it do just that. It will always go in the center spot if it can, and from there go in each corner. If it is able to win at any point, it will.

extends Node

func get_move(board) -> Vector2:
	var result = Vector2(-1, -1)

	var win = win(board)
	var block = block_win(board)

	if (win != Vector2(-1, -1)):
		return win
	elif (block != Vector2(-1, -1)):
		return block

	elif (board[1][1] == 0):
		return Vector2(1, 1)
	elif (board[0][0] == 0):
		return Vector2(0, 0)
	elif (board[2][2] == 0):
		return Vector2(2, 2)
	elif (board[2][0] == 0):
		return Vector2(2, 0)
	elif (board[0][2] == 0):
		return Vector2(0, 2)


	return get_parent().get_node("RandomAI").get_move(board)

func win(board) -> Vector2:
	var result = Vector2(-1, -1)

	var empty_spots = Common.get_empty_spots(board)

	for i in range(empty_spots.size()):
		if Common.check_for_win(board, empty_spots[i], 1):
			result = empty_spots[i]

	return result

func block_win(board) -> Vector2:
	var result = Vector2(-1, -1)

	var empty_spots = Common.get_empty_spots(board)

	for i in range(empty_spots.size()):
		if Common.check_for_win(board, empty_spots[i], -1):
			result = empty_spots[i]

	return result

Minimax AI

And now finally we reach the best AI of them all. It is impossible to defeat. It does this by utilizing a minimax algorithm. The minimax algorithm simulates every possible future outcome of play and assigns a score to that simulation path depending on who won. After considering every future scenario, it compares the scores and calculates the best possible move to make. A single mistake results in the AI winning the game. With perfect play, you can only achieve a tie. You cannot win against this AI.

You can read a great article on the subject here.

extends Node

func get_move(board): #move of the AI
	var empty_spots = Common.get_empty_spots(board)
	var move_scores = {}

	for i in range(empty_spots.size()):
		var board_copy = board.duplicate(true)
		board_copy[empty_spots[i].x][empty_spots[i].y] = 1
		var score_result = minimax(board_copy, -1)
		move_scores[i] = score_result

	var best_index = -1
	var best_score = -2

	for i in range(empty_spots.size()):
		if move_scores[i] > best_score:
			best_score = move_scores[i]
			best_index = i

	return empty_spots[best_index]


func minimax(board, player):

	# Get the empty spots
	var empty_spots = Common.get_empty_spots(board)

	# Check for a game-ending state
	# Win, loss, or tie
	var winner = Common.get_winner(board)

	# -2 means the game is not over
	# When the game is over, we return the score of that possibility
	# return who won
	if winner != -2:
		return winner

	# A dictionary to map all possible moves to a score
	# The index in empty_spots will map to a score
	var move_scores = {}

	for i in range(empty_spots.size()):
		# Play the move on a copy of the board as the player that was passed in to the function
		var move = empty_spots[i]
		var board_copy = board.duplicate(true)
		board_copy[move.x][move.y] = player

		# Recursively get the score, if the opposite player played a move
		if player == 1:
			var score_result = minimax(board_copy, -1)
			move_scores[i] = score_result
		else:
			var score_result = minimax(board_copy, 1)
			move_scores[i] = score_result

	# If it is the AI's turn, loop over the moves and choose the highest score
	# We will store the index of the best score that is in move_scores
	var best_index = -1

	if player == 1:
		var best_score = -2

		for i in range(empty_spots.size()):
			if move_scores[i] > best_score:
				best_score = move_scores[i]
				best_index = i
	else:
	# It is the player's turn, loop over the moves and choose the lowest score
		var best_score = 2

		for i in range(empty_spots.size()):
			if move_scores[i] < best_score:
				best_score = move_scores[i]
				best_index = i

	return move_scores[best_index]

Using a minimax algorithm is only possible because of the small play space of Tic Tac Toe. It is a 3 x 3 grid with 9 possible spots. And each spot can only be in three states, empty, X, or O. Thus we can calculate the number of possible board combinations 3^9 which is 19,683.

Similar games such as Chess and Go can theoretically be played using a minimax algorithm as well. In practical terms, however, you would need to limit how deep the recusion goes. Chess has approximately 10^120 possible board combinations. The game Go is played on a 19 x 19 board has 3^361 possible board combinations. Simulating every possible future scenario to completion in these games would take far too long. It's likely the computer would run out of memory before the caclulation was complete.

Download the Project