Hex Game with AI (Alpha–Beta Pruning)

Hex is a connection strategy game: one player links left–right edges, the other top–bottom, on an N×N hex grid. This implementation renders a 7×7 board with alternating turns and detects wins by checking path connectivity. The AI uses a Minimax search with Alpha–Beta pruning for efficient move selection.

Built in Python with pygame for graphics—simple to run locally and ideal for experimenting with search heuristics.

Python AI algorithms Game theory Minimax Alpha–Beta pruning pygame
View on GitHub Hire Me
Hex game hero

Features

Hex Board Rendering

Visualizes a 7×7 grid with offset columns and alternating turns.

AI Opponent

Minimax search with Alpha–Beta pruning for efficient decision-making.

PvP / PvAI

Human (Red) vs AI (Blue); extendable to PvP with minor changes.

Win Detection

Union–find (disjoint-set) checks edge-to-edge connectivity.

Move Validation

Enforces empty-cell placement to prevent illegal moves.

Heuristic Scoring

Evaluates proximity to target edge and local connectivity.

Architecture & Code

Design (separation of concerns)

  • Board & Rendering: pygame window, images, piece positions, input mapping.
  • AI Engine: Minimax(depth=3) with Alpha–Beta pruning; heuristic evaluation.
  • Connectivity: Disjoint-set (union–find) for edge-to-edge win checks.
  • Game Loop: Event handling → human move → win check → AI move → win check.

Key Parameters & Notes

  • Board size: 7×7 cells.
  • Minimax search depth: 3 plies with pruning.
  • Heuristic: edge proximity + adjacency bonuses (Blue vs Red objectives).
  • Connectivity: union neighbors on each placement; compare edge sets for a win.

Board state & positions (trimmed)

main.py 
# 7×7 empty board; '' means empty, 'R'/'B' are players
pieceSet = [["" for _ in range(7)] for _ in range(7)]
piecePos = [[(0, 0) for _ in range(7)] for _ in range(7)]

def setPosition():
    # compute on-screen pixel coords for each hex cell (staggered)
    for x in range(7):
        for y in range(7):
            piecePos[x][y] = 150 + (x * 70) + (y * 35), 85 + (y * 60)

Disjoint-set (union–find)

disjointSet.py 
class disjointSet:
    def __init__(self, elements):
        self.root = {e: e for e in elements}

    def find(self, a):
        if self.root[a] != a:
            self.root[a] = self.find(self.root[a])
        return self.root[a]

    def union(self, a, b):
        self.root[self.find(a)] = self.find(b)

Alpha–Beta pruning (depth=3)

main.py 
def minimax(isMax, depth, alpha, beta):
    if depth == 0 or gameOver:
        return evaluateBoard()

    if isMax:  # Blue (AI)
        best = -math.inf
        for x in range(7):
            for y in range(7):
                if pieceSet[x][y] == '':
                    pieceSet[x][y] = 'B'
                    best = max(best, minimax(False, depth-1, alpha, beta))
                    pieceSet[x][y] = ''
                    alpha = max(alpha, best)
                    if beta <= alpha: break  # prune
        return best
    else:      # Red (human)
        best = math.inf
        for x in range(7):
            for y in range(7):
                if pieceSet[x][y] == '':
                    pieceSet[x][y] = 'R'
                    best = min(best, minimax(True, depth-1, alpha, beta))
                    pieceSet[x][y] = ''
                    beta = min(beta, best)
                    if beta <= alpha: break  # prune
        return best

Evaluation function (heuristic)

main.py 
def evaluateBoard():
    blueScore = redScore = 0
    for x in range(7):
        for y in range(7):
            if pieceSet[x][y] == 'B':
                blueScore += (6 - x)  # closer to right edge
                for dx, dy in [(1,0),(1,-1),(0,1),(0,-1),(-1,0),(-1,1)]:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < 7 and 0 <= ny < 7 and pieceSet[nx][ny]=='B':
                        blueScore += 2
            elif pieceSet[x][y] == 'R':
                redScore += (6 - y)   # closer to bottom edge
                for dx, dy in [(1,0),(1,-1),(0,1),(0,-1),(-1,0),(-1,1)]:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < 7 and 0 <= ny < 7 and pieceSet[nx][ny]=='R':
                        redScore += 2
    return blueScore - redScore

Win check (Blue edge-to-edge via union–find)

main.py 
def blueWinCheck(x, y):
    # union with like-colored neighbors
    for dx, dy in [(1,0),(1,-1),(0,1),(0,-1),(-1,0),(-1,1)]:
        nx, ny = x+dx, y+dy
        if 0 <= nx <= 6 and 0 <= ny <= 6 and pieceSet[nx][ny] == 'B':
            dsBlue.union((x, y), (nx, ny))

    # if any row index i has left and right edges in same set → win
    for i in range(7):
        if dsBlue.find((0, i)) == dsBlue.find((6, i)):
            return True
    return False
Hire Me Repository