Introduction
Connect 4, also known as "Four in a Row" or "4 Wins," is a timeless strategy game that has captivated players since its introduction in 1974. Despite its simple rules—be the first to connect four pieces in a row—the game offers surprising strategic depth. In this article, we'll explore the journey of implementing a modern version of Connect 4, complete with an AI opponent that can challenge even experienced players.
The Foundation: Understanding Connect 4
Before diving into code, it's crucial to understand what makes Connect 4 tick. The game is played on a 6×7 grid where players take turns dropping colored discs into columns. Gravity pulls each disc to the lowest available position in the chosen column. A player wins by creating a line of four consecutive discs horizontally, vertically, or diagonally.
What makes Connect 4 particularly interesting from a computational perspective is that it's a solved game—meaning that with perfect play, the first player can always force a win. This mathematical certainty provides an excellent foundation for implementing AI strategies.
Architecture Overview
Our implementation follows a modular design with three key components:
1. Game Logic Core: Handles board state, move validation, and win detection
2. AI Engine: Implements the minimax algorithm with position evaluation
3. User Interface: Provides both terminal and web-based interaction
The Game Logic Core
The heart of our implementation is the `Connect4` class, which manages the game state through a NumPy array. This choice of data structure offers several advantages:
self.board = np.zeros((self.rows, self.cols), dtype=int)
Using NumPy provides efficient array operations and makes it easy to extract rows, columns, and diagonals for win checking. The board representation uses:
- 0 for empty cells
- 1 for human player pieces
- 2 for AI player pieces
Move Validation and Execution
One of the critical aspects of any board game implementation is ensuring moves are valid. In Connect 4, this means:
1. The selected column must be within bounds (0-6)
2. The column must have at least one empty space
The `make_move` method handles this elegantly by scanning from the bottom up:
for row in range(self.rows - 1, -1, -1):
if self.board[row][col] == 0:
self.board[row][col] = player
return True
This approach mimics the physical game where pieces fall to the lowest available position.
The AI Brain: Minimax Algorithm
The AI's intelligence comes from the minimax algorithm, a decision-making algorithm for turn-based games. The core idea is simple yet powerful: assume both players play optimally, and choose the move that maximizes your minimum guaranteed outcome.
Understanding Minimax
Minimax works by building a game tree where:
- Each node represents a game state
- Each edge represents a possible move
- Leaf nodes are evaluated with a scoring function
The algorithm alternates between maximizing (AI's turn) and minimizing (human's turn) layers, propagating scores up the tree.
Alpha-Beta Pruning
Pure minimax can be computationally expensive, examining every possible game state. Alpha-beta pruning optimizes this by eliminating branches that won't affect the final decision:
alpha = max(alpha, value)
if alpha >= beta:
break # Beta cutoff
This optimization can reduce the number of nodes examined from O(b^d) to O(b^(d/2)) in the best case, where b is the branching factor and d is the depth.
Position Evaluation
The quality of AI play heavily depends on how well it evaluates board positions. Our evaluation function considers multiple factors:
1. Center Column Control: Pieces in the center column have more winning possibilities
2. Window Scoring: Groups of 2-3 pieces with empty spaces score higher
3. Threat Assessment: Blocking opponent's potential wins
def evaluate_window(self, window: List[int], player: int) -> int:
score = 0
opponent = 3 - player
if window.count(player) == 4:
score += 100
elif window.count(player) == 3 and window.count(0) == 1:
score += 5
elif window.count(player) == 2 and window.count(0) == 2:
score += 2
User Interface Design
Terminal Interface
The terminal version prioritizes clarity and simplicity. Using Unicode box-drawing characters creates a clean, professional appearance:
0 1 2 3 4 5 6
┌───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┤
│ │ │ ● │ ○ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┘
The use of filled circles (● and ○) provides clear visual distinction between players.
Web Interface
The web version leverages modern CSS for an engaging visual experience:
- Responsive Design: Scales appropriately across devices
- Visual Feedback: Hover effects indicate valid moves
- Smooth Animations: CSS transitions make piece placement feel natural
- Color Psychology: Red and yellow pieces mirror the classic physical game
Performance Considerations
Computational Complexity
Connect 4 has approximately 4.5 × 10^12 possible game positions. Our AI needs to balance:
- Search Depth: Deeper searches yield better play but take longer
- Response Time: Players expect moves within 1-2 seconds
- Memory Usage: Storing game trees can quickly exhaust memory
Optimization Strategies
1. Move Ordering: Evaluating center columns first improves alpha-beta pruning
2. Transposition Tables: Caching evaluated positions avoids redundant calculations
3. Iterative Deepening: Provides good moves quickly while calculating better ones
Challenges and Solutions
Challenge 1: Preventing Infinite Loops
Early implementations sometimes trapped the AI in analysis paralysis. Solution: Implement time limits and iterative deepening.
Challenge 2: Balancing Difficulty
An AI that always wins isn't fun. We addressed this by:
- Making search depth configurable
- Adding slight randomization to move selection
- Implementing different difficulty levels
Challenge 3: State Management in Web Version
Managing game state across HTTP requests required careful design:
- Server maintains authoritative game state
- Client sends only move intentions
- Server validates all moves before applying
Future Enhancements
The current implementation provides a solid foundation for several exciting enhancements:
1. Machine Learning Integration: Train a neural network on game histories
2. Opening Book: Pre-computed optimal moves for common opening sequences
3. Multiplayer Support: WebSocket integration for real-time play
4. Tournament Mode: Track statistics and implement ELO ratings
5. Mobile App: Native implementations for iOS and Android
## Lessons Learned
Building this Connect 4 implementation reinforced several software engineering principles:
1. Separation of Concerns: Keeping game logic, AI, and UI independent enables flexibility
2. Test-Driven Development: Unit tests for win detection caught edge cases early
3. User Experience Matters: Small touches like hover effects significantly improve engagement
4. Performance vs. Perfection: Sometimes "good enough" AI is better than perfect but slow AI
Conclusion
Implementing Connect 4 with an AI opponent demonstrates how classic games can be enhanced with modern technology. The combination of traditional game theory (minimax), optimization techniques (alpha-beta pruning), and contemporary web technologies creates an engaging experience that honors the original while adding new dimensions.
The beauty of Connect 4 lies not just in its simplicity but in the depth that emerges from that simplicity. Our implementation captures this essence while showcasing how artificial intelligence can create challenging, enjoyable opponents for human players.
Whether you're a game developer looking for inspiration, a student learning about AI algorithms, or simply someone who enjoys a good game of Connect 4, this implementation provides both entertainment and educational value. The code is open for modification and enhancement—perhaps your contribution will be the next evolution in this classic game's digital journey.
Happy connecting, and may your fours be ever in a row!
The Actual Code
Terminal Version (Python)
import numpy as np
import random
from typing import List, Tuple, Optional
class Connect4:
def __init__(self):
self.rows = 6
self.cols = 7
self.board = np.zeros((self.rows, self.cols), dtype=int)
self.current_player = 1 # 1 for human, 2 for AI
def display_board(self):
"""Display the current board state"""
print("\n 0 1 2 3 4 5 6")
print("┌───┬───┬───┬───┬───┬───┬───┐")
for row in range(self.rows):
print("│", end="")
for col in range(self.cols):
if self.board[row][col] == 0:
print(" ", end="│")
elif self.board[row][col] == 1:
print(" ● ", end="│") # Human player
else:
print(" ○ ", end="│") # AI player
print()
if row < self.rows - 1:
print("├───┼───┼───┼───┼───┼───┼───┤")
print("└───┴───┴───┴───┴───┴───┴───┘")
def is_valid_move(self, col: int) -> bool:
"""Check if a column has space for a new piece"""
return col >= 0 and col < self.cols and self.board[0][col] == 0
def make_move(self, col: int, player: int) -> bool:
"""Place a piece in the specified column"""
if not self.is_valid_move(col):
return False
# Find the lowest empty row
for row in range(self.rows - 1, -1, -1):
if self.board[row][col] == 0:
self.board[row][col] = player
return True
return False
def check_win(self, player: int) -> bool:
"""Check if the specified player has won"""
# Check horizontal
for row in range(self.rows):
for col in range(self.cols - 3):
if all(self.board[row][col + i] == player for i in range(4)):
return True
# Check vertical
for row in range(self.rows - 3):
for col in range(self.cols):
if all(self.board[row + i][col] == player for i in range(4)):
return True
# Check diagonal (top-left to bottom-right)
for row in range(self.rows - 3):
for col in range(self.cols - 3):
if all(self.board[row + i][col + i] == player for i in range(4)):
return True
# Check diagonal (bottom-left to top-right)
for row in range(3, self.rows):
for col in range(self.cols - 3):
if all(self.board[row - i][col + i] == player for i in range(4)):
return True
return False
def is_board_full(self) -> bool:
"""Check if the board is completely filled"""
return np.all(self.board != 0)
def get_valid_moves(self) -> List[int]:
"""Get list of valid column moves"""
return [col for col in range(self.cols) if self.is_valid_move(col)]
def evaluate_window(self, window: List[int], player: int) -> int:
"""Evaluate a window of 4 positions"""
score = 0
opponent = 3 - player
if window.count(player) == 4:
score += 100
elif window.count(player) == 3 and window.count(0) == 1:
score += 5
elif window.count(player) == 2 and window.count(0) == 2:
score += 2
if window.count(opponent) == 3 and window.count(0) == 1:
score -= 4
return score
def score_position(self, player: int) -> int:
"""Calculate a score for the current board position"""
score = 0
# Score center column
center_array = [int(i) for i in list(self.board[:, self.cols // 2])]
center_count = center_array.count(player)
score += center_count * 3
# Score horizontal
for row in range(self.rows):
row_array = [int(i) for i in list(self.board[row, :])]
for col in range(self.cols - 3):
window = row_array[col:col + 4]
score += self.evaluate_window(window, player)
# Score vertical
for col in range(self.cols):
col_array = [int(i) for i in list(self.board[:, col])]
for row in range(self.rows - 3):
window = col_array[row:row + 4]
score += self.evaluate_window(window, player)
# Score diagonal
for row in range(self.rows - 3):
for col in range(self.cols - 3):
window = [self.board[row + i][col + i] for i in range(4)]
score += self.evaluate_window(window, player)
for row in range(self.rows - 3):
for col in range(self.cols - 3):
window = [self.board[row + 3 - i][col + i] for i in range(4)]
score += self.evaluate_window(window, player)
return score
def minimax(self, depth: int, alpha: float, beta: float, maximizing_player: bool) -> Tuple[Optional[int], int]:
"""Minimax algorithm with alpha-beta pruning"""
valid_moves = self.get_valid_moves()
is_terminal = self.check_win(1) or self.check_win(2) or len(valid_moves) == 0
if depth == 0 or is_terminal:
if is_terminal:
if self.check_win(2): # AI wins
return (None, 100000000000000)
elif self.check_win(1): # Human wins
return (None, -100000000000000)
else: # Draw
return (None, 0)
else: # Depth is 0
return (None, self.score_position(2))
if maximizing_player:
value = -float('inf')
best_col = random.choice(valid_moves)
for col in valid_moves:
# Make a copy of the board
temp_board = self.board.copy()
self.make_move(col, 2)
new_score = self.minimax(depth - 1, alpha, beta, False)[1]
self.board = temp_board
if new_score > value:
value = new_score
best_col = col
alpha = max(alpha, value)
if alpha >= beta:
break
return best_col, value
else: # Minimizing player
value = float('inf')
best_col = random.choice(valid_moves)
for col in valid_moves:
# Make a copy of the board
temp_board = self.board.copy()
self.make_move(col, 1)
new_score = self.minimax(depth - 1, alpha, beta, True)[1]
self.board = temp_board
if new_score < value:
value = new_score
best_col = col
beta = min(beta, value)
if alpha >= beta:
break
return best_col, value
def get_ai_move(self, difficulty: int = 5) -> int:
"""Get the AI's move using minimax algorithm"""
col, _ = self.minimax(difficulty, -float('inf'), float('inf'), True)
return col
def play(self):
"""Main game loop"""
print("Welcome to Connect 4!")
print("You are ● and the AI is ○")
print("Enter a column number (0-6) to place your piece")
while True:
self.display_board()
if self.current_player == 1: # Human turn
try:
col = int(input("\nYour turn! Enter column (0-6): "))
if not self.make_move(col, 1):
print("Invalid move! Try again.")
continue
except (ValueError, KeyboardInterrupt):
print("\nGame ended by user.")
break
else: # AI turn
print("\nAI is thinking...")
col = self.get_ai_move()
self.make_move(col, 2)
print(f"AI placed in column {col}")
# Check for win
if self.check_win(self.current_player):
self.display_board()
if self.current_player == 1:
print("\n🎉 Congratulations! You won!")
else:
print("\n😔 AI wins! Better luck next time!")
break
# Check for draw
if self.is_board_full():
self.display_board()
print("\n🤝 It's a draw!")
break
# Switch players
self.current_player = 3 - self.current_player
if __name__ == "__main__":
game = Connect4()
game.play()
```
Web Version (Flask + HTML/CSS/JavaScript)
`app.py` (Flask Backend)
from flask import Flask, render_template, jsonify, request
import numpy as np
from connect4 import Connect4 # Import the Connect4 class from above
app = Flask(__name__)
game = None
@app.route('/')
def index():
return render_template('index.html')
@app.route('/new_game', methods=['POST'])
def new_game():
global game
game = Connect4()
return jsonify({
'board': game.board.tolist(),
'message': 'New game started! Your turn.'
})
@app.route('/make_move', methods=['POST'])
def make_move():
global game
if game is None:
return jsonify({'error': 'No game in progress'}), 400
data = request.json
col = data.get('column')
# Human move
if not game.make_move(col, 1):
return jsonify({'error': 'Invalid move'}), 400
# Check if human won
if game.check_win(1):
return jsonify({
'board': game.board.tolist(),
'winner': 'human',
'message': '🎉 Congratulations! You won!'
})
# Check for draw
if game.is_board_full():
return jsonify({
'board': game.board.tolist(),
'draw': True,
'message': '🤝 It\'s a draw!'
})
# AI move
ai_col = game.get_ai_move()
game.make_move(ai_col, 2)
# Check if AI won
if game.check_win(2):
return jsonify({
'board': game.board.tolist(),
'winner': 'ai',
'message': '😔 AI wins! Better luck next time!',
'ai_move': ai_col
})
# Check for draw after AI move
if game.is_board_full():
return jsonify({
'board': game.board.tolist(),
'draw': True,
'message': '🤝 It\'s a draw!',
'ai_move': ai_col
})
return jsonify({
'board': game.board.tolist(),
'ai_move': ai_col,
'message': 'Your turn!'
})
if __name__ == '__main__':
app.run(debug=True)
`templates/index.html`
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Connect 4 - AI Game</title>
<style>
body {
font-family: Arial, sans-serif;
display: flex;
justify-content: center;
align-items: center;
min-height: 100vh;
margin: 0;
background-color: #2c3e50;
color: white;
}
.container {
text-align: center;
}
h1 {
margin-bottom: 20px;
}
.board {
display: inline-block;
background-color: #3498db;
padding: 10px;
border-radius: 10px;
box-shadow: 0 4px 6px rgba(0, 0, 0, 0.3);
}
.row {
display: flex;
}
.cell {
width: 60px;
height: 60px;
margin: 5px;
background-color: #34495e;
border-radius: 50%;
cursor: pointer;
transition: background-color 0.3s;
position: relative;
}
.cell:hover {
background-color: #4a5f7a;
}
.cell.player1 {
background-color: #e74c3c;
}
.cell.player2 {
background-color: #f1c40f;
}
.cell.disabled {
cursor: not-allowed;
}
.message {
margin: 20px 0;
font-size: 18px;
min-height: 30px;
}
button {
background-color: #27ae60;
color: white;
border: none;
padding: 10px 20px;
font-size: 16px;
border-radius: 5px;
cursor: pointer;
transition: background-color 0.3s;
}
button:hover {
background-color: #2ecc71;
}
.column-numbers {
display: flex;
margin-bottom: 5px;
}
.column-number {
width: 60px;
margin: 5px;
text-align: center;
font-weight: bold;
}
</style>
</head>
<body>
<div class="container">
<h1>Connect 4 - Play Against AI</h1>
<div class="message" id="message">Click "New Game" to start!</div>
<div class="board" id="board">
<div class="column-numbers">
<div class="column-number">0</div>
<div class="column-number">1</div>
<div class="column-number">2</div>
<div class="column-number">3</div>
<div class="column-number">4</div>
<div class="column-number">5</div>
<div class="column-number">6</div>
</div>
</div>
<div style="margin-top: 20px;">
<button onclick="newGame()">New Game</button>
</div>
</div>
<script>
let gameActive = false;
let board = [];
function createBoard() {
const boardElement = document.getElementById('board');
// Clear existing board except column numbers
const rows = boardElement.querySelectorAll('.row');
rows.forEach(row => row.remove());
for (let row = 0; row < 6; row++) {
const rowElement = document.createElement('div');
rowElement.className = 'row';
for (let col = 0; col < 7; col++) {
const cell = document.createElement('div');
cell.className = 'cell';
cell.dataset.row = row;
cell.dataset.col = col;
cell.onclick = () => makeMove(col);
rowElement.appendChild(cell);
}
boardElement.appendChild(rowElement);
}
}
function updateBoard(boardData) {
board = boardData;
const cells = document.querySelectorAll('.cell');
cells.forEach(cell => {
const row = parseInt(cell.dataset.row);
const col = parseInt(cell.dataset.col);
const value = board[row][col];
cell.className = 'cell';
if (value === 1) {
cell.classList.add('player1');
} else if (value === 2) {
cell.classList.add('player2');
}
if (!gameActive) {
cell.classList.add('disabled');
}
});
}
async function newGame() {
try {
const response = await fetch('/new_game', {
method: 'POST',
headers: {
'Content-Type': 'application/json'
}
});
const data = await response.json();
gameActive = true;
updateBoard(data.board);
document.getElementById('message').textContent = data.message;
} catch (error) {
console.error('Error starting new game:', error);
}
}
async function makeMove(column) {
if (!gameActive) return;
try {
const response = await fetch('/make_move', {
method: 'POST',
headers: {
'Content-Type': 'application/json'
},
body: JSON.stringify({ column: column })
});
if (!response.ok) {
const error = await response.json();
document.getElementById('message').textContent = error.error || 'Invalid move!';
return;
}
const data = await response.json();
updateBoard(data.board);
document.getElementById('message').textContent = data.message;
if (data.winner || data.draw) {
gameActive = false;
}
} catch (error) {
console.error('Error making move:', error);
}
}
// Initialize board on page load
createBoard();
</script>
</body>
</html>
Installation and Usage
Terminal Version:
1. Save the first code block as `connect4.py`
2. Install numpy: `pip install numpy`
3. Run: `python connect4.py`
Web Version:
1. Install Flask: `pip install flask numpy`
2. Create the following structure:
connect4_web/
├── app.py
├── connect4.py (the terminal version code)
└── templates/
└── index.html
3. Run: `python app.py`
4. Open browser to `http://localhost:5000`
Features
- AI Opponent: Uses minimax algorithm with alpha-beta pruning
- Difficulty Adjustment: Can modify the `difficulty` parameter in `get_ai_move()`
- Visual Board: Clear representation of the game state
- Win Detection: Checks for horizontal, vertical, and diagonal wins
- Draw Detection: Recognizes when the board is full
- Responsive Web Interface: Clean, modern design with hover effects
The AI evaluates positions based on:
- Center column control
- Potential winning combinations
- Blocking opponent's winning moves
- Creating multiple threats
You can adjust the AI difficulty by changing the depth parameter in the `get_ai_move()` method. Higher values make the AI stronger but slower.
No comments:
Post a Comment