Connect4 Vs AI agent

Play Connect4 against an intelligent AI agent using Minimax Algorithm with and without Pruning

Deployment

To Run Graphical Interface:

 python GUI.py

Algorithms Used

Minimax Algorithm Pseudocode:

def minimax(board, depth, maximizingPlayer):
    if the game is over or depth == 0:
        return evaluate the board
    
    if maximizingPlayer:
        maxEval = -infinity
        for each child of board:
            eval = minimax(child, depth - 1, false)
            maxEval = max(maxEval, eval)
        return maxEval
    
    else:  # minimizing player
        minEval = +infinity
        for each child of board:
            eval = minimax(child, depth - 1, true)
            minEval = min(minEval, eval)
        return minEval

Minimax Algorithm with Alpha-Beta Pruning Pseudocode:

def minimax_alpha_beta(board, depth, alpha, beta, maximizingPlayer):
    if the game is over or depth == 0:
        return evaluate the board
    
    if maximizingPlayer:
        maxEval = -infinity
        for each child of board:
            eval = minimax_alpha_beta(child, depth - 1, alpha, beta, false)
            maxEval = max(maxEval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break
        return maxEval
    
    else:  # minimizing player
        minEval = +infinity
        for each child of board:
            eval = minimax_alpha_beta(child, depth - 1, alpha, beta, true)
            minEval = min(minEval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break
        return minEval

Heuristic Function

 A = 100000
 B = 5000
 C = 200
 D = -100
 E = -4000

Analysis for Runtime

• The following analysis is done on a random state
• The time is measured in seconds

Without Pruning:

Depth	States Expanded	Time Taken
1	7	0.009
2	57	0.043
3	400	0.25
4	2775	1.53
5	19608	6.63
6	135885	9.88

With Pruning:

Depth	States Expanded	Time Taken
1	7	0.009
2	27	0.039
3	84	0.185
4	235	0.65
5	1111	2.8
6	25506	4.2
7	142546	9.86
8	508643	30.84