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.
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.
December 11, 2020
Hey diego, I run your project and it keeps saying that The identifier “Common” isn’t declared in the current scope.”, so is there any way to get ride of this parser error. And also hats off for this beautiful code.
December 11, 2020
Interesting. It sounds like the Common script is not being autoloaded. Go to AutoLoad tab in the project settings. You’ll want to autoload the “Common.tscn” file as a singleton.