xbe.at

Data visualisation

Minesweeper AI Solver in Python with Matplotlib

6 min read, 15 sections

Contents
  1. Introduction to Minesweeper AI
  2. Representing the Game Board
  3. Visualizing the Game Board
  4. Uncovering Tiles
  5. Counting Surrounding Mines
  6. Uncovering Neighbors
  7. Game Loop
  8. AI Logic: Simple Algorithm
  9. AI Logic: Probability-based Algorithm
  10. Calculating Probabilities
  11. Getting Neighbors
  12. Advanced Strategies
  13. Constraint Propagation
  14. Pattern Recognition
  15. Machine Learning Approach

Introduction to Minesweeper AI

Minesweeper is a classic game that involves uncovering a grid of tiles while avoiding hidden mines. Creating an AI to solve Minesweeper can be an exciting project that combines logic, probability, and Python programming. In this slideshow, we'll explore the development of a Minesweeper AI using Matplotlib and Python.

import matplotlib.pyplot as plt
import numpy as np

Representing the Game Board

To create a Minesweeper AI, we need to represent the game board in a data structure. We can use a 2D NumPy array to store the state of each tile, with values representing mines, uncovered tiles, or the number of surrounding mines.

board = np.full((10, 10), -1)  # Initialize a 10x10 board with -1 (covered)
board[3, 4] = -2  # Set a mine at (3, 4)

Visualizing the Game Board

We can use Matplotlib to visualize the game board and provide a user interface for the AI to interact with the game. We'll define functions to create a visual representation of the board and update it as tiles are uncovered.

def visualize_board(board):
    plt.matshow(board, cmap='Blues')
    plt.xticks([])
    plt.yticks([])
    plt.show()

Uncovering Tiles

The AI needs to be able to uncover tiles on the board. We'll create a function that takes the board and a tile coordinate as input and updates the board according to the game rules.

def uncover_tile(board, row, col):
    if board[row, col] == -1:
        # Uncover the tile
        board[row, col] = count_surrounding_mines(board, row, col)
        # If the tile has no surrounding mines, uncover neighbors
        if board[row, col] == 0:
            uncover_neighbors(board, row, col)

Counting Surrounding Mines

To determine the number of surrounding mines for a tile, we'll create a function that checks the neighboring tiles and counts the mines.

def count_surrounding_mines(board, row, col):
    count = 0
    for i in range(-1, 2):
        for j in range(-1, 2):
            if 0 <= row + i < board.shape[0] and 0 <= col + j < board.shape[1]:
                if board[row + i, col + j] == -2:
                    count += 1
    return count

Uncovering Neighbors

If a tile has no surrounding mines, we need to recursively uncover its neighbors. We'll create a function that takes the board and a tile coordinate as input and recursively uncovers neighboring tiles until it encounters tiles with surrounding mines.

def uncover_neighbors(board, row, col):
    for i in range(-1, 2):
        for j in range(-1, 2):
            if 0 <= row + i < board.shape[0] and 0 <= col + j < board.shape[1]:
                if board[row + i, col + j] == -1:
                    uncover_tile(board, row + i, col + j)

Game Loop

To play the game, we'll create a game loop that allows the AI to make moves and update the board accordingly. This loop will continue until all non-mine tiles are uncovered or a mine is hit.

game_over = False
while not game_over:
    # AI logic to choose a tile
    row, col = ai_choose_tile(board)
    uncover_tile(board, row, col)
    visualize_board(board)
    if board[row, col] == -2:
        game_over = True
        print("Game Over! You hit a mine.")
    elif np.all(board != -1):
        game_over = True
        print("Congratulations! You won the game.")

AI Logic: Simple Algorithm

For a simple AI algorithm, we can start by selecting a random uncovered tile on the board. This approach may not be optimal, but it serves as a starting point for more advanced strategies.

def ai_choose_tile(board):
    uncovered = np.argwhere(board == -1)
    if len(uncovered) > 0:
        row, col = uncovered[np.random.randint(len(uncovered))]
        return row, col
    else:
        return None, None

AI Logic: Probability-based Algorithm

To improve the AI's performance, we can use probability and knowledge of surrounding mine counts to make more informed decisions. The AI can prioritize uncovering tiles with lower probabilities of containing mines.

def ai_choose_tile(board):
    probabilities = calculate_probabilities(board)
    min_prob = np.min(probabilities[probabilities != -1])
    coords = np.argwhere(probabilities == min_prob)
    row, col = coords[np.random.randint(len(coords))]
    return row, col

Calculating Probabilities

To calculate the probability of a tile containing a mine, we'll create a function that uses the surrounding mine counts and the remaining uncovered tiles to estimate the likelihood of each tile being a mine.

def calculate_probabilities(board):
    probabilities = np.full(board.shape, -1)
    uncovered = np.argwhere(board == -1)
    for row, col in uncovered:
        neighbors = get_neighbors(board, row, col)
        known_mines = sum(board[neighbors] == -2)
        unknown = len(neighbors) - known_mines - sum(board[neighbors] >= 0)
        if unknown > 0:
            probabilities[row, col] = known_mines / unknown
    return probabilities

Getting Neighbors

To calculate the probabilities, we need a function that returns the coordinates of the neighboring tiles for a given tile.

def get_neighbors(board, row, col):
    neighbors = []
    for i in range(-1, 2):
        for j in range(-1, 2):
            if 0 <= row + i < board.shape[0] and 0 <= col + j < board.shape[1]:
                if i != 0 or j != 0:
                    neighbors.append((row + i, col + j))
    return neighbors

Advanced Strategies

The probability-based algorithm can be further improved by incorporating more advanced strategies, such as constraint propagation, pattern recognition, and machine learning techniques. These approaches can lead to more efficient and robust AI solutions for solving Minesweeper.

# Constraint propagation algorithm
def constraint_propagation(board):
    # Implementation details...

# Pattern recognition algorithm
def pattern_recognition(board):
    # Implementation details...

# Machine learning approach
def train_ml_model(data):
    # Implementation details...

Constraint Propagation

Constraint propagation is an advanced strategy that can further improve the Minesweeper AI's performance. It involves using the known information on the board to deduce the state of other tiles, effectively reducing the search space and increasing the chances of making optimal moves.

def constraint_propagation(board):
    changed = True
    while changed:
        changed = False
        for row in range(board.shape[0]):
            for col in range(board.shape[1]):
                if board[row, col] >= 0:
                    neighbors = get_neighbors(board, row, col)
                    uncovered = [n for n in neighbors if board[n] == -1]
                    mines = [n for n in neighbors if board[n] == -2]
                    if len(mines) == board[row, col]:
                        for n in uncovered:
                            if board[n] == -1:
                                board[n] = -2
                                changed = True
                    elif len(uncovered) == board[row, col] - len(mines):
                        for n in uncovered:
                            if board[n] == -1:
                                uncover_tile(board, n[0], n[1])
                                changed = True

Pattern Recognition

Pattern recognition is another advanced strategy that can be employed in Minesweeper AI. It involves identifying known patterns on the board and using them to deduce the state of other tiles. This can be particularly effective in certain scenarios where constraint propagation may not be sufficient.

def pattern_recognition(board):
    patterns = [
        # 1-1 pattern
        np.array([[0, 1, -1],
                  [1, -1, -1],
                  [-1, -1, -1]]),
        # 2-2 pattern
        np.array([[-1, -1, 1],
                  [1, 2, 1],
                  [-1, -1, 1]]),
        # ... Add more patterns as needed
    ]

    for pattern in patterns:
        for row in range(board.shape[0] - pattern.shape[0] + 1):
            for col in range(board.shape[1] - pattern.shape[1] + 1):
                sub_board = board[row:row + pattern.shape[0], col:col + pattern.shape[1]]
                if np.all(sub_board[pattern >= 0] == pattern[pattern >= 0]):
                    for i in range(pattern.shape[0]):
                        for j in range(pattern.shape[1]):
                            if pattern[i, j] == -1 and sub_board[i, j] == -1:
                                uncover_tile(board, row + i, col + j)

Machine Learning Approach

Machine learning techniques can also be applied to Minesweeper AI, particularly for learning optimal strategies from large datasets of game boards and moves. This approach can potentially lead to more sophisticated and effective AI solutions.

import tensorflow as tf

def train_ml_model(data):
    # Preprocess data
    X = [preprocess_board(board) for board, _, _ in data]
    y = [next_move for _, next_move, _ in data]

    # Define the model
    model = tf.keras.Sequential([
        tf.keras.layers.Dense(64, activation='relu', input_shape=(X[0].shape,)),
        tf.keras.layers.Dense(64, activation='relu'),
        tf.keras.layers.Dense(2, activation='softmax')
    ])

    # Compile and train the model
    model.compile(optimizer='adam', loss='categorical_crossentropy', metrics=['accuracy'])
    model.fit(np.array(X), np.array(y), epochs=10, batch_size=32)

    return model

This concludes the slideshow on developing a Minesweeper AI using Matplotlib and Python. We covered various aspects, including board representation, visualization, game logic, simple algorithms, advanced strategies like constraint propagation and pattern recognition, and even a machine learning approach. Each slide provided code examples to illustrate the concepts and algorithms discussed.

More in Data visualisation

  1. Optimizing Bin Sizes for Effective Data Visualization11 min

    In histograms, bin width selection critically impacts data interpretation. The optimal bin width balances granularity and smoothness, revealing underlying...

  2. Mastering Matplotlib Visualizations in Python7 min

    Matplotlib is a powerful plotting library for Python, widely used for creating static, animated, and interactive visualizations. It provides a MATLAB-like...

  3. Outlier Detection in Python Visualizing and Analyzing Anomalies10 min

    Outliers are data points that significantly differ from other observations in a dataset. They can greatly impact statistical analyses and machine learning...

  4. Markov Process with Python Visualizations6 min

    Markov processes are stochastic models that describe a sequence of possible events where the probability of each event depends solely on the state attained...

  5. Pairplots The Data Scientist's Secret Weapon for Insightful Visualizations9 min

    A pairplot is a powerful visualization tool that creates a grid of relationships between multiple variables in your dataset. It generates scatterplots for...

  6. Machine Learning Stacking A Visual Guide8 min

    Stacking is an advanced ensemble learning technique that combines predictions from multiple models to create a more powerful and accurate predictor. This...