JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

Connect 4 AI

Introduction

Connect 4 is a classic and popular game for two players, with easy rules. The first player to line up 4 tiles of his color wins. Let’s code Connect 4 in Python.

import numpy as np
import random, shelve
import pygame, time 
import sys, math, configparser
from menu import *
BLUE = (0, 0, 255)
BLACK = (0, 0, 0)
RED = (255, 0, 0)
RED_LIGHT = (255, 60, 60)
YELLOW = (255, 255, 0)
YELLOW_LIGHT = (255, 255, 120)
WHITE = (255, 255, 255)
PLAYER = 0
AI = 1
PLAYER_PIECE = 1
AI_PIECE = 2  
EMPTY = 0

class Player: # It represents the player, both the AI and the gamer.
    def __init__(self, type, turn):
        self.type = type
        self.turn = turn

    def set_turn(self, new_turn):
        self.turn = new_turn

    def get_turn(self):
        return self.turn

Game’s core

class Game: # It represents the game itself
    def __init__(self):
        self.game_over = False
        self.running, self.playing = True, False
        pygame.init() # It initializes all imported pygame modules.
        size = (Board.WIDTH, Board.HEIGHT)
        self.screen = pygame.display.set_mode(size) # It sets the display mode and creates an instance of the pygame.Surface class.

We will use the ConfigParser module to manage user-editable configuration files for our application. It provides a structure similar to what’s found in Microsoft Windows INI files. Our config file resources/connect.ini is quite simple:

[BASIC] # The file consists of sections, each of which contains keys with values. 
Depth = 6 # The depth of the minimax algorithm. 
Debug = Yes # It is used for debugging purposes.
        pygame.display.set_caption('Connect4') # It changes the icon of the pygame window.
        self.config = configparser.ConfigParser() # We create an instance of the main configuration parser.
        self.config.read("resources/connect4.ini") # We read the configuration file.
        self.depth = int(self.config['BASIC']['Depth']) # We access the Depth and the Debug values from the BASIC section. 
        self.debug = self.config['BASIC']['Debug'] == "Yes"
        self.board = Board(self.screen, self.debug, self.depth) # It creates an instance of our Game's board.
        self.player = Player(PLAYER, True) # It creates an instance of the human player.
        self.ai = Player(AI, False) # It creates an instance of the ai player.
        self.myfont = pygame.font.Font("resources/Halloween Morning.ttf", 30) # It creates a new Font object from a file.
        self.winner = self.player # A variable is used to indicate who is the winner.
        self.UP_KEY, self.DOWN_KEY, self.START_KEY, self.BACK_KEY, self.MOUSEMOTION = False, False, False, False, False
        self.MOUSEBUTTONDOWN = False
        self.posx = 0
        self.main_menu = MainMenu(self) # Our game will have a menu implemented by a few classes. We create instances of them in our Game class.
        self.difficulty = DifficultyMenu(self)
        self.credits = CreditsMenu(self)
        self.curr_menu = self.main_menu # It defines the current menu.

    def display_end(self): # Before letting the user go, it gives him or her some information.
        d = shelve.open('connect4.txt') # The shelve module provides a very simple and yet effective object persistence mechanism.
        score = 42
        try:
            score = d['score'] # We read the score from the disk. We define the best score as a human player who beats the AI and he does it in the minimum number of movements. It raises a KeyError exception if there is not such a key.
            if self.winner==self.player and score > self.board.occupied_cells(): # If the player is the winner and the score is greater than the board's occupied positions.
                score = self.board.occupied_cells() # Update the new record.
                d['score'] = self.board.occupied_cells() # We store the data at score. 
        except KeyError as e: # If a KeyError exception was raised, we create the key.
            if self.winner==self.player and score > self.board.occupied_cells():
                d['score'] =  self.board.occupied_cells()
            else:
                d['score'] = 42   
            pass    
        d.close()

        self.screen.blit( pygame.image.load("resources/splashScreen.jpg"), (0,0)) # pygame.image.load loads an image from a file, screen.blit draws the image to the surface.
        if self.winner==self.player:
            self.draw_text("Congratulations! Your score is " + str(self.board.occupied_cells()), 20, 220, 80)
        else:
            self.draw_text("I am sorry. You've lost. Try again!", 20, 220, 80)

        self.draw_text("The record is " + str(score), 20, 220, 130)
        pygame.display.flip() # It will update the full display surface to the screen.
        pygame.time.wait(3000)

    def draw(self): # It draws the actual state of the game.
        self.board.draw_board() # It draws the current board.
        pygame.display.update() # It will update the full display surface to the screen.

    def check_events(self): # Pygame handles all its event messaging through an event queue. This method checks all these events. 
        for event in pygame.event.get(): # It gets events from the queue.
            if event.type == pygame.QUIT:
                self.running, self.playing = False, False
                self.curr_menu.run_display = False
                sys.exit()

            if event.type == pygame.MOUSEMOTION:
                self.MOUSEMOTION = True
                self.posx = event.pos[0]

            if event.type == pygame.KEYDOWN:
                if event.key == pygame.K_RETURN:
                    self.START_KEY = True
                if event.key == pygame.K_BACKSPACE:
                    self.BACK_KEY = True
                if event.key == pygame.K_DOWN:
                    self.DOWN_KEY = True
                if event.key == pygame.K_UP:
                    self.UP_KEY = True

            if event.type == pygame.MOUSEBUTTONDOWN:
                self.MOUSEBUTTONDOWN = True
                self.posx = event.pos[0]

The method game_loop controls the overall flow for the entire game program. There are three tasks: 1. Check all events. 2. Process these events and take action accordingly. 3. Draw the current state of the game so the player can see what is going on.

def game_loop(self):
 # If the player is actually playing, we draw the board.            
        while self.playing: 
            pygame.draw.rect(self.screen, BLACK, (0, 0, Board.WIDTH, Board.SQUARESIZE))
            self.board.draw_board()
            pygame.draw.circle(self.screen, RED, (self.posx, int(Board.SQUARESIZE/2)), Board.RADIUS)
            pygame.draw.circle(self.screen, RED_LIGHT, (self.posx, int(Board.SQUARESIZE/2)), 3*Board.RADIUS/4)
            pygame.display.update()
            self.check_events() # It checks all the events.

            # Now, we are going to process the events.    
            if self.MOUSEMOTION: # The user is moving the mouse and deciding where to place its piece.
                if self.player.get_turn(): # If the player's turn is now, we draw the board.
                    pygame.draw.rect(self.screen, BLACK, (0, 0, Board.WIDTH, Board.SQUARESIZE))
                    self.board.draw_board()
                    pygame.draw.circle(self.screen, RED, (self.posx, int(Board.SQUARESIZE/2)), Board.RADIUS)
                    pygame.draw.circle(self.screen, RED_LIGHT, (self.posx, int(Board.SQUARESIZE/2)), 3*Board.RADIUS/4)
                    pygame.display.update()

            if self.MOUSEBUTTONDOWN: # The mouse button is released. The player has already decided his or her next move.
                pygame.draw.rect(self.screen, BLACK, (0, 0, Board.WIDTH, Board.SQUARESIZE))
                if self.player.get_turn():

First, we calculate the column where the user has released the mouse. Second, if the column is a valid movement, we find out which is the row where the piece is to be placed, and finally we save or “drop” the piece into the board.

                    col = int(math.floor(self.posx/Board.SQUARESIZE))
                         if self.board.is_valid_location(col):
                                row = self.board.get_next_open_row(col)
                                self.board.drop_piece(row, col, PLAYER_PIECE)  

                 # If the player has won, we display a message, update the Game's winner property and change the game's variable state "game_over" to True.   
                 if self.board.winning_move(PLAYER_PIECE): 
                    label = self.myfont.render("Player 1 wins!!", 1, RED) 
                    self.winner = self.player
                    self.screen.blit(label, (40, 10))
                    self.game_over = True

                self.player.set_turn(False) # We change the turn from player to our AI.
                self.ai.set_turn(True)
                 
                if self.debug: # This is an example of using a parameter defined on the configuration file resources/connect4.ini for debugging purposes.
                    self.board.print_board()                 

                self.draw() # We draw the game's board.
                          
            # If the turn belongs to the AI player and the game is not over yet. This level of indentation corresponds to "if self.MOUSEBUTTONDOWN:"
            if self.ai.get_turn() and not self.game_over: 
                # We use the board's minimax method to find out the best movement.
                col, minimax_score = self.board.minimax(self.depth, -math.inf, math.inf, True) 
                # If the column is a valid movement, we find out which is the row where the piece is to be placed, and we save or "drop" the piece into the board.
                if self.board.is_valid_location(col): 
                    row = self.board.get_next_open_row(col) 
                    self.board.drop_piece(row, col, AI_PIECE)
                    # If the AI has won, we display a message, update the Game's winner property and change the game's variable state "game_over" to True.
                    if self.board.winning_move(AI_PIECE): 
                        label = self.myfont.render("Player 2 wins!!", 1, YELLOW) 
                        self.screen.blit(label, (40, 10))
                        self.game_over = True  
                        self.winner = self.ai 

                    self.draw() # We draw the game's board.
                    self.ai.set_turn(False) # We change the turn from AI to the player.
                    self.player.set_turn(True)

           
            if self.game_over: # If the game is over.
                time.sleep(3)
                self.display_end() # We invoke the game's display_end method to display relevant information to the user.
                self.playing = False 
                self.running = False

            self.reset_keys() # We reset the keys as we have already processed the key's associated event.

    def reset_keys(self): # Reset all the keys
        self.UP_KEY, self.DOWN_KEY, self.START_KEY, self.BACK_KEY = False, False, False, False
        self.MOUSEBUTTONDOWN = False
        self.MOUSEMOTION = False

    def draw_text(self, text, size, x, y ):
        text_surface = self.myfont.render(text, True, WHITE)
        text_rect = text_surface.get_rect()
        text_rect.center = (x,y)
        self.screen.blit(text_surface,text_rect)    

if __name__ == '__main__':
    game = Game() # The main function is quite simple. We create an instance of our Game class.
    while game.running: # While the state of the game is running
        game.curr_menu.display_menu() # We display the menu.
        game.game_loop() # We call the game's game_loop function.

Pygame menu

We will create a new file menu.py where we will implement a class base “Menu” and three classes derived from it: MainMenu, DifficultyMenu, and CreditsMenu. Navigation through the menu is accomplished by using the arrow keys and the “Enter” key to select an option.

import pygame
BLACK = (0, 0, 0)
ROW_COUNT = 6
COLUMN_COUNT = 7
SQUARESIZE = 100
BOARDWIDTH = COLUMN_COUNT * SQUARESIZE
BOARDHEIGHT = (ROW_COUNT+1) * SQUARESIZE

class Menu():
    def __init__(self, game):
        self.game = game # We need to have a reference to the Game's object.
        self.mid_w, self.mid_h = BOARDWIDTH / 2, BOARDHEIGHT / 2
        self.run_display = True # This property specifies if the Menu is active/being displayed or not.
        self.cursor_rect = pygame.Rect(0, 0, 20, 20) # This is the cursor that helps our users to navigate through the menu's options.
        self.offset = - 120

    def draw_cursor(self):
        self.game.draw_text('*', 15, self.cursor_rect.x, self.cursor_rect.y)

    def process_events(self):
        pygame.draw.rect(self.game.screen, BLACK, (0, 0, BOARDWIDTH, SQUARESIZE)) # pygame.draw.rect(screen, color, (x, y, width, height)) draws a rectangle where the screen is the target Surface, (x, y) are the coordinates of the upper left corner, width and height are the width and height of the rectangle. 
        pygame.display.update() # It updates the entire display.
        self.game.reset_keys() # Reset all the keys.

class MainMenu(Menu):
    def __init__(self, game):
        Menu._init__(self, game)
        self.state = "Start" # A property that indicates the menu's state or the user's selected option
        self.startx, self.starty = self.mid_w, self.mid_h + 30
        self.optionsx, self.optionsy = self.mid_w, self.mid_h + 80
        self.creditsx, self.creditsy = self.mid_w, self.mid_h + 130
        self.cursor_rect.midtop = (self.startx + self.offset, self.starty)
Connect Four in Python

Connect Four in Python

Remember that the entry point to our program is:

if __name__ == '__main__':   
    game = Game() # Game's constructor: 

In other words, __init__(self):…. self.running, self.playing = True, False. It means that the game is running, but the player is still not playing this classic board game. […] self.main_menu = MainMenu(self) […] self.curr_menu = self.main_menu, our property curr_menu is initialized inside the constructor to main_menu.   

    while game.running:    
        game.curr_menu.display_menu() # We invoke the current_menu's display_menu.    
        game.game_loop()

This is the first screen/menu which appears on the game. It is the initial “state” of our game.

    def display_menu(self):  
        while self.run_display: # self.run.display is set to True by the Menu's (the parent class) constructor.
            self.game.check_events() # We check all the events.
            self.process_events() # And process the events.
            self.game.screen.fill((0, 0, 0)) # We draw the Main Menu.
            self.game.draw_text('Main Menu', 20, self.game.board.WIDTH / 2, self.game.board.HEIGHT / 3 - 20)
            self.game.draw_text("Start Game", 20, self.startx, self.starty)
            self.game.draw_text("Difficulty", 20, self.optionsx, self.optionsy)
            self.game.draw_text("Credits", 20, self.creditsx, self.creditsy)
            self.draw_cursor()
            self.process_events() # Finally, we update the menu.
Connect Four Game in Python

Connect Four Game in Python

    def move_cursor(self): # If the user presses the arrows up and/or down, we need to change the "state" property and the cursor's position.
        if self.game.DOWN_KEY: 
            if self.state == 'Start':
                self.cursor_rect.midtop = (self.optionsx + self.offset, self.optionsy)
                self.state = 'Difficulty'
            elif self.state == 'Difficulty':
                self.cursor_rect.midtop = (self.creditsx + self.offset, self.creditsy)
                self.state = 'Credits'
            elif self.state == 'Credits':
                self.cursor_rect.midtop = (self.startx + self.offset, self.starty)
                self.state = 'Start'
        elif self.game.UP_KEY:
            if self.state == 'Start':
                self.cursor_rect.midtop = (self.creditsx + self.offset, self.creditsy)
                self.state = 'Credits'
            elif self.state == 'Difficulty':
                self.cursor_rect.midtop = (self.startx + self.offset, self.starty)
                self.state = 'Start'
            elif self.state == 'Credits':
                self.cursor_rect.midtop = (self.optionsx + self.offset, self.optionsy)
                self.state = 'Difficulty'

    def process_events(self):
        self.move_cursor()
        if self.game.START_KEY: # If the user has pressed pygame.K_RETURN, the enter key...
            if self.state == 'Start': # and the "state" is 'Start',
                self.game.playing = True # we set the property "playing" of our instance of the class Game (self.game) to True so he can start playing our game. 
                self.game.MOUSEMOTION = True
                self.game.posx = 0
            elif self.state == 'Difficulty':
                self.game.curr_menu = self.game.difficulty # We change the "curr_menu" property of our instance of the class Game (self.game) to self.game.difficulty, an instance of the class DifficultyMenu.
            elif self.state == 'Credits':
                self.game.curr_menu = self.game.credits # We change the "curr_menu" property of our instance of the class Game (self.game) to self.game.credits, an instance of the class CreditsMenu.
            self.run_display = False # Finally, we update the display property to False.

class DifficultyMenu(Menu):
    def __init__(self, game):
        Menu._init__(self, game)
        self.state = 'Easy'
        self.easyx, self.easyy = self.mid_w, self.mid_h + 30
        self.mediumx, self.mediumy = self.mid_w, self.mid_h + 80
        self.expertx, self.experty = self.mid_w, self.mid_h + 130
        self.cursor_rect.midtop = (self.easyx + self.offset, self.easyy)

    def display_menu(self): 
        while self.run_display:
            self.game.check_events()
            self.check_input()
            self.game.screen.fill((0, 0, 0))
            self.game.draw_text('Difficulty', 20, BOARDWIDTH / 2, BOARDHEIGHT / 3 - 30)
            self.game.draw_text("Easy", 15, self.easyx, self.easyy)
            self.game.draw_text("Medium", 15, self.mediumx, self.mediumy)
            self.game.draw_text("Expert", 15, self.expertx, self.experty)
            self.draw_cursor()
            self.blit_screen()

    def check_input(self):
        if self.game.BACK_KEY: # If the user has pressed pygame.K_BACKSPACE, the backspace key...
            self.game.curr_menu = self.game.main_menu # the current menu is set to main_menu
            self.run_display = False
        elif self.game.DOWN_KEY:
            if self.state == 'Easy':
                self.state = 'Medium'
                self.cursor_rect.midtop = (self.mediumx + self.offset, self.mediumy)
            elif self.state == 'Medium':
                self.state = 'Expert'
                self.cursor_rect.midtop = (self.expertx + self.offset, self.experty)
            elif self.state == 'Expert':
                self.state = 'Easy'
                self.cursor_rect.midtop = (self.easyx + self.offset, self.easyy)
        elif self.game.UP_KEY:
            if self.state == 'Easy':
                self.state = 'Expert'
                self.cursor_rect.midtop = (self.expert + self.offset, self.expert)
            elif self.state == 'Medium':
                self.state = 'Easy'
                self.cursor_rect.midtop = (self.easyx + self.offset, self.easyy)
            elif self.state == 'Expert':
                self.state = 'Medium'
                self.cursor_rect.midtop = (self.mediumx + self.offset, self.mediumy)       
        elif self.game.START_KEY: # If the user has pressed pygame.K_RETURN, the enter key...
            if self.state == "Easy": # and the "state" is 'Easy',
                self.game.depth = 1 # we set the depth of the minimax search tree to be used as 2
            elif self.state == "Medium":
                self.game.depth = 4
            elif self.state == "Expert":
                self.game.depth = 6

class CreditsMenu(Menu):
    def __init__(self, game):
        Menu._init__(self, game)

    def display_menu(self):
        self.run_display = True
        while self.run_display:
            self.game.check_events()
            if self.game.START_KEY or self.game.BACK_KEY:
                self.game.curr_menu = self.game.main_menu
                self.run_display = False
            self.game.screen.fill(BLACK)
            self.game.draw_text('Credits', 20, self.game.DISPLAY_W / 2, self.game.DISPLAY_H / 2 - 20)
            self.game.draw_text('JustToThePoint', 15, self.game.DISPLAY_W / 2, self.game.DISPLAY_H / 2 + 10)
            self.process_events()

Implementing the game’s board

class Board: 

This class represents the game’s board. A big part of this game’s code is inspired by KeithGalli’s Connect4-Python licensed under the MIT License

    ROW_COUNT = 6 # This game is played on a vertical board which has seven columns and six rows. 
    COLUMN_COUNT = 7
    SQUARESIZE = 100
    RADIUS = int(SQUARESIZE/2 - 5)
    WIDTH = COLUMN_COUNT * SQUARESIZE
    HEIGHT = (ROW_COUNT+1) * SQUARESIZE
    WINDOW_LENGTH = 4
    def __init__(self, screen, debug, depth):
        self.board = np.zeros((self.ROW_COUNT, self.COLUMN_COUNT), int) # It returns a new array of self.ROW_COUNT*self.COLUMN_COUNT, filled with zeros.
        self.screen = screen # It is the display surface of our game.
        self.debug = debug # It is a config parameter passed by the game to enable debugging.
        self.depth = depth

    def occupied_cells(self): # How many places are occupied on our board?
        return np.count_nonzero(self.board) # np.count_nonzero counts the number of non-zero values in the array (EMPTY=0, EMPTY represents an empty square)

    def is_full(self): # Is the board full?
        return self.occupied_cells()==(self.ROW_COUNT*self.COLUMN_COUNT)
user@pc:~$ python # Many times there is a need to copy one array to another. 
>>> A = np.array([[1,2,3],[4,5,6]], int) 
>>> B = A # This binds B to the existing object already named A. Afterwards they refer to the same object, so if you modify A or B, you'll see the change through the other one too. 
>>> B[0][0]=7 
>>> A array([[7, 2, 3], [4, 5, 6]])
    def copy(self): # It returns an exact copy of the board.
        myCopy = Board(self.screen, self.debug, self.depth)
        myCopy.set_board(self.board.copy())
        return myCopy

    def drop_piece(self, row, col, piece):  # It drops a "piece" in the board in the row and column specified by the row and col arguments.
        self.board[row][col] = piece

    def get_board(self):
        return self.board()

    def set_board(self, board):
        self.board = board

    def is_valid_location(self, col): # Is it possible or valid to drop a piece in the column specified by the col argument?
        return self.board[self.ROW_COUNT-1][col] == 0 # It is possible "if" and only "if" self.board[5][col] == 0. In other words, the top row is obviously the last one to be filled when we play the game. 

    def get_next_open_row(self, col): # What is the first row available in "col"? 
        for r in range(self.ROW_COUNT): # r iterates from 0 to ROW_COUNT-1
            if self.board[r][col] == 0:
                return r

    def print_board(self): # It prints our board in the terminal.
        if (self.debug): # It is just for debugging purposes.
            print(np.array2string(np.flip(self.board, 0), separator=','))

It flips the array vertically because we expect the last row to be seen as the first one. array2string prints the array with commas separating its elements, e.g.,:

[[1,0,0,0,0,0,0],
[1,0,0,0,0,0,0],
[2,0,0,0,0,0,0],
[1,0,0,0,0,0,0],
[1,0,0,2,0,0,0],
[1,1,2,2,2,2,0]]

    def winning_move(self, piece): # Checking for a winning board.
        for c in range(self.COLUMN_COUNT-3): # Checking horizontally.
            for r in range(self.ROW_COUNT):
                if self.board[r][c] == piece and self.board[r][c+1] == piece and self.board[r][c+2] == piece and self.board[r][c+3] == piece:
                    return True

        for c in range(self.COLUMN_COUNT): # Checking vertically
            for r in range(self.ROW_COUNT-3):
                if self.board[r][c] == piece and self.board[r+1][c] == piece and self.board[r+2][c] == piece and self.board[r+3][c] == piece:
                    return True

        for c in range(self.COLUMN_COUNT-3): # Checking / diagonally.
            for r in range(self.ROW_COUNT-3):
                if self.board[r][c] == piece and self.board[r+1][c+1] == piece and self.board[r+2][c+2] == piece and self.board[r+3][c+3] == piece:
                    return True

        for c in range(self.COLUMN_COUNT-3): # Checking \ diagonally.
            for r in range(3, self.ROW_COUNT):
                if self.board[r][c] == piece and self.board[r-1][c+1] == piece and self.board[r-2][c+2] == piece and self.board[r-3][c+3] == piece:
                        return True
Connnect Four in Python

Connnect Four in Python

The next function evaluates a part or window of our board (an array of four consecutive places in the board). It uses Numpy’s count to see how many pieces satisfy a particular condition, e.g., window.count(piece) counts how many times the piece given as a parameter is in the window (array).

    def evaluate_window(self, window, piece):
        score = 0
        opp_piece = PLAYER_PIECE
        if piece == PLAYER_PIECE:
            opp_piece = AI_PIECE
        # Obviously, if there are four occurrences of the piece in the window, the score is really high. 
        if window.count(piece) == 4: 
            score += 1000
        elif window.count(piece) == 3 and window.count(EMPTY) == 1: 
        # If there are three occurrences of the piece in the window, we add 10 to the score. 
            score += 10
        elif window.count(piece) == 2 and window.count(EMPTY) == 2:
            score += 3

        if window.count(opp_piece) == 3 and window.count(EMPTY) == 1: 
        # It also need to subtract points to the score when there are three occurrences of the opposite piece in the window.
            score -= 7
        return score

    # It evaluates a board. It is a position evaluation function and it indicates how good it would be for a player to reach that position.
    def score_position(self, piece):
        score = 0
        # It is better centered columns than columns along the board's sides. We consider the one in the very center -3- and add three times the number of center pieces to the score. 
        center_array = [i for i in list(self.board[:, 3])]
        center_count = center_array.count(piece)
        score += center_count * 3

        # Analyze horizontally
        for r in range(self.ROW_COUNT):
            row_array = [int(i) for i in list(self.board[r, :])]
            for c in range(self.COLUMN_COUNT-3):
                window = row_array[c:c+Board.WINDOW_LENGTH]
                score += self.evaluate_window(window, piece)

        # Analyze vertically
        for c in range(self.COLUMN_COUNT):
            col_array = [int(i) for i in list(self.board[:, c])]
            for r in range(self.ROW_COUNT-3):
                window = col_array[r:r+Board.WINDOW_LENGTH]
                score += self.evaluate_window(window, piece)

        # Analyze diagonally
        for r in range(self.ROW_COUNT-3):
            for c in range(self.COLUMN_COUNT-3):
                window = [self.board[r+i][c+i] for i in range(Board.WINDOW_LENGTH)]
                score += self.evaluate_window(window, piece)

        for r in range(self.ROW_COUNT-3):
            for c in range(self.COLUMN_COUNT-3):
                window = [self.board[r+3-i][c+i] for i in range(Board.WINDOW_LENGTH)]
                score += self.evaluate_window(window, piece)
        return score
Connect Four in Python

Connect Four in Python

The minimax algorithm

A minimax algorithm is a recursive algorithm for choosing the next move in a game. At each step it assumes that the player (or AI) is trying to maximize his chances of winning, while on the next turn AI (or the player) is trying to minimize his opponent’s chances of winning. We use a rule that if the result of a move is an immediate win for AI, then it would be assigned positive infinity as a score and if it is an immediate win for the player, negative infinity. Our AI is called the maximizing player and the player, the minimizing player.

The minimax function returns a heuristic value for leaf nodes (terminal nodes and nodes at the maximum search depth).

    def is_terminal_node(self): # It returns True if the node is terminal.
        return self.winning_move(PLAYER_PIECE) or self.winning_move(AI_PIECE) or self.is_full()
function  minimax(node, depth, maximizingPlayer) # This is extracted from Wikipedia.
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
            # If the internal node belongs to the AI player, we take its children's maximum value because he wants to make his final score as big as possible since the AI player always wants to win.
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        # If the internal node belongs to the human player, we take its children's minimum value because the player wants to make our AI's final score as low as possible.
        return value
Minimax

Minimax

The problem is that it takes a very long time to process the entire tree. Alpha-beta pruning seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It prunes away branches that cannot possibly influence the final decision.

We define two variables: alpha is the best already explored option along the path to the root for the maximizer (AI). Beta is the best already explored option along the path to the root for the minimizer.

(* Initial call *)
alphabeta(origin, depth, −∞, +∞, TRUE)
function alphabeta(node, depth, α, β, maximizingPlayer) # This is extracted from Wikipedia.
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then # If the maximizingPlayer (AI) finds a value that is higher than its current beta, it can discard the entire subtree because it is sure that his optimal path will not go through this. 
                break (* β cutoff *)
            α := max(α, value) # If the maximizingPlayer (AI) finds a value that is higher than alpha, it updates alpha.
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then # If the miximizingPlayer (player) finds a value that is lower than its current alpha, it can discard the entire subtree because it is sure that his optimal path will not go through this. 
                break (* α cutoff *)
            β := min(β, value)
        return value

Observe that as soon as the minimizer saw the 4 (node F; alpha=5, beta=4), he knew that the maximizer would never come this way because the maximizer was guaranteed a value of 5 or more (alpha=5), he can get a 5 on the left side (E). Minimax Algorithm

Minimax Algorithm

def minimax(self, depth, alpha, beta, maximizingPlayer):
        valid_locations = self.get_valid_locations(self.board) # It explores the nodes of a game tree. The branching factor of the tree is the number of children of each node (valid_locations(self.board).
        is_terminal = self.is_terminal_node()

        if depth == 0 or is_terminal:
            if is_terminal:
                if self.winning_move(AI_PIECE):
                    return (None, 10000000)
                elif self.winning_move(PLAYER_PIECE):
                    return (None, -10000000)
                else:  # Game is over, no more valid moves
                    return (None, 0)
            else:  # Depth is zero. We return the board´s evaluation.
                return (None, self.score_position(AI_PIECE))

        if maximizingPlayer: # Maximizing player, our AI
            value = -math.inf
            column = random.choice(valid_locations)
            for col in valid_locations:
                row = self.get_next_open_row(col)
                b_copy = self.copy()
                b_copy.drop_piece(row, col, AI_PIECE)

                if (depth==self.depth and b_copy.winning_move(AI_PIECE)): 
                # This is a modification of the minimax algorithm. If we find a winning move, we take it.
                    return (col, 10000000)

                new_score = b_copy.minimax(depth-1, alpha, beta, False)[1]
                if new_score > value:
                    value = new_score
                    column = col

                alpha = max(alpha, value) # The maximizing player updates alpha.
                if alpha >= beta:
                    break

Think about it, alpha and beta represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively.

Whenever the maximum score that the minimizing player (i.e. the “human” player, “beta”) is assured of becomes less than the minimum score that the maximizing player (i.e., the “computer”, “alpha”) is assured of (i.e. beta < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in the actual play.

            return column, value
        else:  # Minimizing player, our real human player
            value = math.inf
            column = random.choice(valid_locations)
            for col in valid_locations:
                row = self.get_next_open_row(col)
                b_copy = self.copy()
                b_copy.drop_piece(row, col, PLAYER_PIECE)
                new_score = b_copy.minimax(depth-1, alpha, beta, True)[1]
                if new_score < value:
                    value = new_score
                    column = col
                beta = min(beta, value) # The minimizing player updates beta.
                if alpha >= beta:
                    break
            return column, value
Minimax Algorithm

Minimax Algorithm

# It returns an array of valid places or locations to play   
def get_valid_locations(self, board):
	valid_locations = []
	for col in range(Board.COLUMN_COUNT):
		if self.is_valid_location(col):
			valid_locations.append(col)

	return valid_locations

# It draws the board. It is just a big rectangle drawn with COLUMN_COUNT*ROW_COUNT blue boxes and black circles. It draws a row extra for the player to drop his pieces on the board.     
def draw_board(self):
	for c in range(Board.COLUMN_COUNT):
		for r in range(Board.ROW_COUNT):
			pygame.draw.rect(self.screen, BLUE, (c*Board.SQUARESIZE, r * Board.SQUARESIZE+Board.SQUARESIZE, Board.SQUARESIZE, Board.SQUARESIZE))
			pygame.draw.circle(self.screen, BLACK, (int(c*Board.SQUARESIZE+Board.SQUARESIZE/2), int(r*Board.SQUARESIZE+Board.SQUARESIZE+Board.SQUARESIZE/2)), Board.RADIUS)

        # Every piece is drawn with two circles of similar colors.
	for c in range(Board.COLUMN_COUNT):
		for r in range(Board.ROW_COUNT):
			if self.board[r][c] == PLAYER_PIECE:
				pygame.draw.circle(self.screen, RED, (int(c*Board.SQUARESIZE+Board.SQUARESIZE/2), Board.HEIGHT-int(r*Board.SQUARESIZE+Board.SQUARESIZE/2)), Board.RADIUS)
				pygame.draw.circle(self.screen, RED_LIGHT, (int(c*Board.SQUARESIZE+Board.SQUARESIZE/2), Board.HEIGHT-int(r*Board.SQUARESIZE+Board.SQUARESIZE/2)), 3*Board.RADIUS/4)
			elif self.board[r][c] == AI_PIECE:
				pygame.draw.circle(self.screen, YELLOW, (int(c*Board.SQUARESIZE+Board.SQUARESIZE/2), Board.HEIGHT-int(r*Board.SQUARESIZE+Board.SQUARESIZE/2)), Board.RADIUS)
				pygame.draw.circle(self.screen, YELLOW_LIGHT, (int(c*Board.SQUARESIZE+Board.SQUARESIZE/2), Board.HEIGHT-int(r*Board.SQUARESIZE+Board.SQUARESIZE/2)), 3*Board.RADIUS/4)
Minimax in Python

Minimax in Python

Bitcoin donation

JustToThePoint Copyright © 2011 - 2024 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.