Created December 2019
Source code available on Github >
Made in collaboration with a classmate
This project involved creating a functional game of Connect 4, and programming a playable computer bot. I personally handled the game rendering & user input with PyGame, and implementing the AI algorithm. My classmate created the board class that holds the state of the board, who's turn it is, etc.
For the AI player, I implemented the Minimax algorithm. In this description I assume familiarity and will not
explain it. To learn about the algorithm I heavily references these two videos:
Brief explanation with implementation by
Sebastian Lague
MIT Opencourseware lecture with instructor Patrick
Winston
In Connect 4, winning is achieved by getting a 4-in-a-row, so position evaluation is based on connections. Only connections with at least 1 open side are considered, because a 3-in-a-row with both sides closed can never become a 4-in-a-row. Longer connections are far more valuable than shorter ones, and so a quadratic scaling is used. Particularly, the following weighting:
| Connection | Weight |
|---|---|
| 1 | 0 |
| 2 | 4 |
| 3 | 9 |
| 4 | 1000 |
Originally, a connection of length 4 was assigned a weight of 16. However, the AI would sometimes not take the immediately winning move because it saw a future with more connections and thus a higher score. Now adjusted, the evaluator simply returns a 1000 when the tree search finds a connection of 4, not even taking into account other connections because all 4-in-a-rows are equally winning.
As is typical in static evaluations, each side's contributions count against each other, with one side's being negative and the other side's being positive.
Below is the actual implementation
def static_eval(board):
board_eval = 0
for con in board.connections:
multiplier = 1
# con[0] == 1 means player 1
# con[0] == 2 means player 2
if con[0] == 2:
multiplier = -1
length = len(con) - 1
if length == 2:
board_eval += multiplier * 4
elif length == 3:
board_eval += multiplier * 9
elif length >= 4:
return multiplier * 1000
return board_eval
In a game of Connect 4, there are typically 7 moves possible moves available. This means the search space expands very quickly with depth, at a rate of typically O(7n) . To reduce the search size, alpha beta pruning as well as a turn-order heuristic are implemented.
Alpha beta pruning (now referred to as pruning) is standard, so the actual algorithm will not be explained. Discussing its impact though, pruning generally leads to a square root factor reduction, i.e. what used to take 7n steps now only takes 7n/2 , i.e. it doubles the search depth. In practice, a search depth of 7 ran 4x faster after implementing pruning.
Within games, not all moves are equal. As an example in chess, capturing an opponent's piece is likely to be more interesting than pushing a pawn forward, so it is often ideal to consider capturing pieces before considering pushing pawns. For the game of connect 4, the heuristic is much simpler - consider moves in the center first, and then the edges. In the beginning of the game, the center of the board is often the most active. As time progresses however, columns fill up and with less available moves the search space naturally reduces in size - when 1 column is filled, the search space is 6n vs the baseline 7n
When a move is made or the end screen buttons show up, they don't snap into location and instead fall down and bounce with gravity. This is done via a simple procedural animations, and during the animations the user cannot give any input. Below I detail how the falling animation is implemented. This same system of 3 functions is used to make the AI move its piece around prior to locking in its move.
To track the state of an animation, each animation has a global dictionary associated with it. Throughout the animation this dictionary holds all state. For the falling animation it looks like so:
fall_anim = {
"pos": (0, 0),
"dest": (0, 0),
"y_vel": 0,
"Y_ACCEL": GRAVITY * (1.0 / FPS),
"bounce": 0,
"img": PLAYER_PIECE_IMG,
}
As well as a dictionary, every animation has 3 functions to control them.
For the falling animation, the three functions are called:
def set_falling_animation_parameters(board): ...
def handle_falling_animation(): ...
def finish_falling_animation(): ...
What's notable about the setup function is that it takes the board as a parameter. This allows the same code to work for both red & blue pieces, because it extracts from the board object which player to use.
The handle_falling_animation() is far more interesting.
It is called once every frame during the animation and contains the logic for simulating the bouncing object. During animation simulation, vertical velocity is increased every frame and position is updated according to velocity. When the position hits the destination y-coordinate, its velocity is inverted and decreased. This happens until a threshold number of bounces is reached, at which point the animation finishes.
This high level overview is mirrored in the code.
def handle_falling_animation():
'''Will draw and update values relating to a falling piece'''
global fall_anim
finished = False
clear_piece(tuple(fall_anim['pos']))
fall_anim['pos'] = list(fall_anim['pos'])
fall_anim['y_vel'] += fall_anim['Y_ACCEL']
fall_anim['pos'][1] += fall_anim['y_vel']
# check if it has reached the target y yet
if fall_anim['dest'][1] <= fall_anim['pos'][1]:
# this the position is never below the line
fall_anim['pos'][1] = fall_anim['dest'][1]
# play louder sound on first bounce
if fall_anim['bounce'] == 0:
hit_sound.play()
else:
quiet_hit_sound.play()
# exiting behaviour
if fall_anim['bounce'] + 1 >= NUM_BOUNCES:
finish_falling_animation()
finished = True
fall_anim['bounce'] += 1
# reverse direction and lose some speed
# -1 < BOUNCE_COEF < 0
fall_anim['y_vel'] *= BOUNCE_COEF
# redraw
fall_anim['pos'] = tuple(fall_anim['pos'])
draw_piece(fall_anim['pos'], fall_anim['img'])
return finished
When the AI makes its decision on what move to make, it doesn't immediately play it. It similarly has an animation which moves the piece over to the move the AI wants to make. Despite being a completely different animation, it too runs with just 3 functions which overall simplifies the main loop and makes the code more easily expandable.