use pygame to write a Gobang game, and adding an AI using max-min
- User
use pygame to write a Gobang game, and adding an AI using max-min
- Assistant
Creating a Gobang (also known as Five in a Row) game using Pygame with an AI opponent that utilizes the Minimax algorithm is an exciting project. Below, I'll guide you through building this game step-by-step. We'll cover:
- Setting Up the Game Environment
- Creating the Game Board
- Handling Player Inputs
- Implementing the AI with Minimax Algorithm
- Putting It All Together
Prerequisites
Before we begin, ensure you have Python installed on your machine. Additionally, you'll need to install the Pygame library. You can install it using pip:
pip install pygame1. Setting Up the Game Environment
First, we'll set up the basic Pygame environment, including initializing the game window and defining some essential constants.
import pygame import sys import math import copy # Initialize Pygame pygame.init() # Screen dimensions WIDTH, HEIGHT = 600, 600 screen = pygame.display.set_mode((WIDTH, HEIGHT)) pygame.display.set_caption("Gobang (Five in a Row)") # Colors WHITE = (255, 255, 255) BLACK = (0, 0, 0) RED = (255, 0, 0) # Board settings GRID_SIZE = 40 BOARD_SIZE = 15 # 15x15 board OFFSET = GRID_SIZE GRID_WIDTH = GRID_SIZE * (BOARD_SIZE - 1) + OFFSET * 2 # Fonts font = pygame.font.SysFont(None, 24) # Player definitions HUMAN = 1 AI = -1 # Game state board = [[0 for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)]2. Creating the Game Board
Next, we'll create functions to draw the game board and render the stones on the board.
def draw_board(): screen.fill(WHITE) # Draw grid lines for i in range(BOARD_SIZE): pygame.draw.line(screen, BLACK, (OFFSET, OFFSET + i * GRID_SIZE), (OFFSET + GRID_SIZE * (BOARD_SIZE - 1), OFFSET + i * GRID_SIZE)) pygame.draw.line(screen, BLACK, (OFFSET + i * GRID_SIZE, OFFSET), (OFFSET + i * GRID_SIZE, OFFSET + GRID_SIZE * (BOARD_SIZE - 1))) # Draw stones for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] == HUMAN: pygame.draw.circle(screen, BLACK, (OFFSET + x * GRID_SIZE, OFFSET + y * GRID_SIZE), GRID_SIZE//2 - 2) elif board[y][x] == AI: pygame.draw.circle(screen, RED, (OFFSET + x * GRID_SIZE, OFFSET + y * GRID_SIZE), GRID_SIZE//2 - 2) pygame.display.update()3. Handling Player Inputs
We'll handle the player's mouse clicks to place stones on the board. The AI will make its move after the human player.
def get_mouse_pos(): pos = pygame.mouse.get_pos() x = round((pos[0] - OFFSET) / GRID_SIZE) y = round((pos[1] - OFFSET) / GRID_SIZE) if 0 <= x < BOARD_SIZE and 0 <= y < BOARD_SIZE: return y, x return None def is_valid_move(y, x): return board[y][x] == 04. Implementing the AI with Minimax Algorithm
Implementing a full Minimax algorithm for Gobang can be computationally intensive due to the large search space. To manage this, we'll incorporate the following optimizations:
- Depth Limitation: Restrict the search depth to prevent long computation times.
- Heuristic Evaluation: Assign scores to board states to estimate the desirability of positions.
- Alpha-Beta Pruning: Eliminate branches that won't be selected, improving efficiency.
Here's a simplified version of the AI:
def evaluate(board): # Simple heuristic: +10 for each 4 in a row for AI, -10 for Human # This can be expanded for better intelligence score = 0 # Evaluate rows, columns, and diagonals for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] != 0: score += evaluate_position(board, y, x, board[y][x]) return score def evaluate_position(board, y, x, player): score = 0 directions = [(1,0), (0,1), (1,1), (1,-1)] for dy, dx in directions: count = 1 open_ends = 0 # Check forward for i in range(1,5): ny, nx = y + dy*i, x + dx*i if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE: if board[ny][nx] == player: count += 1 elif board[ny][nx] == 0: open_ends +=1 break else: break else: break # Check backward for i in range(1,5): ny, nx = y - dy*i, x - dx*i if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE: if board[ny][nx] == player: count +=1 elif board[ny][nx] == 0: open_ends +=1 break else: break else: break if count >=5: if player == AI: score += 100000 else: score -= 100000 elif count ==4: if open_ends >0: if player == AI: score += 1000 else: score -= 1000 elif count ==3: if open_ends >0: if player == AI: score += 100 else: score -= 100 return score def check_win(board, player): # Check all possible directions for a win for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] == player: # Check horizontal, vertical, and two diagonals directions = [(1,0), (0,1), (1,1), (1,-1)] for dy, dx in directions: count = 1 for i in range(1,5): ny, nx = y + dy*i, x + dx*i if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE and board[ny][nx] == player: count +=1 else: break if count >=5: return True return False def get_available_moves(board): moves = [] for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] == 0: # To optimize, only consider empty cells adjacent to occupied cells for dy in range(-1,2): for dx in range(-1,2): ny, nx = y + dy, x + dx if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE: if board[ny][nx] !=0: moves.append((y, x)) break else: continue break if not moves: # If the board is empty moves.append((BOARD_SIZE//2, BOARD_SIZE//2)) return moves def minimax(board, depth, alpha, beta, maximizingPlayer): if check_win(board, AI): return None, 100000 if check_win(board, HUMAN): return None, -100000 if depth ==0: return None, evaluate(board) moves = get_available_moves(board) if not moves: return None, 0 # Draw if maximizingPlayer: maxEval = -math.inf best_move = None for move in moves: y, x = move board[y][x] = AI current_eval = minimax(board, depth-1, alpha, beta, False)[1] board[y][x] = 0 if current_eval > maxEval: maxEval = current_eval best_move = move alpha = max(alpha, current_eval) if beta <= alpha: break return best_move, maxEval else: minEval = math.inf best_move = None for move in moves: y, x = move board[y][x] = HUMAN current_eval = minimax(board, depth-1, alpha, beta, True)[1] board[y][x] = 0 if current_eval < minEval: minEval = current_eval best_move = move beta = min(beta, current_eval) if beta <= alpha: break return best_move, minEval def ai_move(): print("AI is thinking...") move, score = minimax(board, 2, -math.inf, math.inf, True) # Depth can be adjusted if move: y, x = move board[y][x] = AINotes:
-
Depth Limitation: The
minimaxfunction above uses a depth of2. Increasing this depth can make the AI stronger but will significantly impact performance. Depending on your machine's capabilities, you might experiment with this value. -
Heuristic Evaluation: The
evaluateandevaluate_positionfunctions provide a basic heuristic. For a more intelligent AI, consider enhancing these functions to recognize more patterns and assign better scores. -
Optimization: The AI's performance can be optimized further by implementing techniques like move ordering or more sophisticated pruning strategies.
5. Putting It All Together
Finally, we'll integrate all components into the main game loop.
def main(): clock = pygame.time.Clock() draw_board() turn = HUMAN # Human starts first while True: for event in pygame.event.get(): if event.type == pygame.QUIT: pygame.quit() sys.exit() if event.type == pygame.MOUSEBUTTONDOWN and turn == HUMAN: pos = get_mouse_pos() if pos: y, x = pos if is_valid_move(y, x): board[y][x] = HUMAN draw_board() if check_win(board, HUMAN): print("Human wins!") pygame.quit() sys.exit() turn = AI if turn == AI: ai_move() draw_board() if check_win(board, AI): print("AI wins!") pygame.quit() sys.exit() turn = HUMAN clock.tick(30) # Limit to 30 FPS if __name__ == "__main__": main()Complete Code
For convenience, here's the complete code combined:
import pygame import sys import math import copy # Initialize Pygame pygame.init() # Screen dimensions WIDTH, HEIGHT = 600, 600 screen = pygame.display.set_mode((WIDTH, HEIGHT)) pygame.display.set_caption("Gobang (Five in a Row)") # Colors WHITE = (255, 255, 255) BLACK = (0, 0, 0) RED = (255, 0, 0) # Board settings GRID_SIZE = 40 BOARD_SIZE = 15 # 15x15 board OFFSET = GRID_SIZE GRID_WIDTH = GRID_SIZE * (BOARD_SIZE - 1) + OFFSET * 2 # Fonts font = pygame.font.SysFont(None, 24) # Player definitions HUMAN = 1 AI = -1 # Game state board = [[0 for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)] def draw_board(): screen.fill(WHITE) # Draw grid lines for i in range(BOARD_SIZE): pygame.draw.line(screen, BLACK, (OFFSET, OFFSET + i * GRID_SIZE), (OFFSET + GRID_SIZE * (BOARD_SIZE - 1), OFFSET + i * GRID_SIZE)) pygame.draw.line(screen, BLACK, (OFFSET + i * GRID_SIZE, OFFSET), (OFFSET + i * GRID_SIZE, OFFSET + GRID_SIZE * (BOARD_SIZE - 1))) # Draw stones for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] == HUMAN: pygame.draw.circle(screen, BLACK, (OFFSET + x * GRID_SIZE, OFFSET + y * GRID_SIZE), GRID_SIZE//2 - 2) elif board[y][x] == AI: pygame.draw.circle(screen, RED, (OFFSET + x * GRID_SIZE, OFFSET + y * GRID_SIZE), GRID_SIZE//2 - 2) pygame.display.update() def get_mouse_pos(): pos = pygame.mouse.get_pos() x = round((pos[0] - OFFSET) / GRID_SIZE) y = round((pos[1] - OFFSET) / GRID_SIZE) if 0 <= x < BOARD_SIZE and 0 <= y < BOARD_SIZE: return y, x return None def is_valid_move(y, x): return board[y][x] == 0 def evaluate(board): # Simple heuristic: +100000 for each 5 in a row for AI, -100000 for Human # +1000 for each 4 in a row with open ends, etc. score = 0 # Evaluate rows, columns, and diagonals for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] != 0: score += evaluate_position(board, y, x, board[y][x]) return score def evaluate_position(board, y, x, player): score = 0 directions = [(1,0), (0,1), (1,1), (1,-1)] for dy, dx in directions: count = 1 open_ends = 0 # Check forward for i in range(1,5): ny, nx = y + dy*i, x + dx*i if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE: if board[ny][nx] == player: count += 1 elif board[ny][nx] == 0: open_ends +=1 break else: break else: break # Check backward for i in range(1,5): ny, nx = y - dy*i, x - dx*i if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE: if board[ny][nx] == player: count +=1 elif board[ny][nx] == 0: open_ends +=1 break else: break else: break if count >=5: if player == AI: score += 100000 else: score -= 100000 elif count ==4: if open_ends >0: if player == AI: score += 1000 else: score -= 1000 elif count ==3: if open_ends >0: if player == AI: score += 100 else: score -= 100 return score def check_win(board, player): # Check all possible directions for a win for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] == player: # Check horizontal, vertical, and two diagonals directions = [(1,0), (0,1), (1,1), (1,-1)] for dy, dx in directions: count = 1 for i in range(1,5): ny, nx = y + dy*i, x + dx*i if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE and board[ny][nx] == player: count +=1 else: break if count >=5: return True return False def get_available_moves(board): moves = [] for y in range(BOARD_SIZE): for x in range(BOARD_SIZE): if board[y][x] == 0: # To optimize, only consider empty cells adjacent to occupied cells for dy in range(-1,2): for dx in range(-1,2): ny, nx = y + dy, x + dx if 0 <= ny < BOARD_SIZE and 0 <= nx < BOARD_SIZE: if board[ny][nx] !=0: moves.append((y, x)) break else: continue break if not moves: # If the board is empty moves.append((BOARD_SIZE//2, BOARD_SIZE//2)) return moves def minimax(board, depth, alpha, beta, maximizingPlayer): if check_win(board, AI): return None, 100000 if check_win(board, HUMAN): return None, -100000 if depth ==0: return None, evaluate(board) moves = get_available_moves(board) if not moves: return None, 0 # Draw if maximizingPlayer: maxEval = -math.inf best_move = None for move in moves: y, x = move board[y][x] = AI current_eval = minimax(board, depth-1, alpha, beta, False)[1] board[y][x] = 0 if current_eval > maxEval: maxEval = current_eval best_move = move alpha = max(alpha, current_eval) if beta <= alpha: break return best_move, maxEval else: minEval = math.inf best_move = None for move in moves: y, x = move board[y][x] = HUMAN current_eval = minimax(board, depth-1, alpha, beta, True)[1] board[y][x] = 0 if current_eval < minEval: minEval = current_eval best_move = move beta = min(beta, current_eval) if beta <= alpha: break return best_move, minEval def ai_move(): print("AI is thinking...") move, score = minimax(board, 2, -math.inf, math.inf, True) # Depth can be adjusted if move: y, x = move board[y][x] = AI def main(): clock = pygame.time.Clock() draw_board() turn = HUMAN # Human starts first while True: for event in pygame.event.get(): if event.type == pygame.QUIT: pygame.quit() sys.exit() if event.type == pygame.MOUSEBUTTONDOWN and turn == HUMAN: pos = get_mouse_pos() if pos: y, x = pos if is_valid_move(y, x): board[y][x] = HUMAN draw_board() if check_win(board, HUMAN): print("Human wins!") pygame.quit() sys.exit() turn = AI if turn == AI: ai_move() draw_board() if check_win(board, AI): print("AI wins!") pygame.quit() sys.exit() turn = HUMAN clock.tick(30) # Limit to 30 FPS if __name__ == "__main__": main()Running the Game
-
Save the Code: Save the complete code above into a Python file, e.g.,
gobang.py. -
Run the Game:
python gobang.py -
Gameplay:
- Human Player: Click on the desired grid intersection to place a black stone.
- AI Player: After your move, the AI will calculate and place a red stone.
- Winning Condition: The game will print a message in the console when either the human or AI wins.
Enhancements and Optimizations
The provided AI is quite basic and may not play optimally, especially with a limited search depth. Here are some ways to enhance the AI and overall game:
-
Improve the Heuristic Evaluation: Incorporate more complex patterns and scoring mechanisms to make the AI's decisions smarter.
-
Increase Depth with Optimizations: Implement more advanced pruning techniques or iterative deepening to allow deeper searches without significant performance penalties.
-
UI Enhancements: Add visual indicators for the current player, highlight winning sequences, or provide a restart option.
-
Animation and Effects: Animate stone placements and add visual feedback for better user experience.
-
Multiplayer Mode: Allow two human players to play against each other.
-
Move Ordering: Order moves in a way that better moves are evaluated first, enhancing the effectiveness of alpha-beta pruning.
-
Transposition Tables: Cache previously evaluated board states to avoid redundant calculations.
By iterating on these aspects, you can develop a more robust and intelligent Gobang game.