Parallel Monte Carlo Tree Search (MCTS)

This repository contains a high-performance implementation of Monte Carlo Tree Search (MCTS) applied to a stochastic Gridworld pathfinding problem.

Implemented for the Project Work in Architectures and Platforms for Artificial Intelligence at the University of Bologna (a.y. 2025/2026).

Overview

The goal of the agent is to navigate a $60 \times 60$ grid with randomly placed obstacles to reach a target coordinates.

The project implements:

1. Serial MCTS: A baseline implementation.
2. Root Parallelization (OpenMP): Multiple independent MCTS trees are executed in parallel on different CPU cores. Their results are aggregated (ensemble method) to determine the final move.
3. Leaf Parallelization (CUDA): The tree search and selection logic remain on the CPU, while the computationally expensive rollout (simulation) phase is offloaded to the GPU. A batch of parallel simulations is executed for every expanded node.

Build Instructions

The project uses a Makefile to manage the build process for both the CPU and GPU executables.

To build the entire project run

make

This will create two directories:

• obj/: Intermediate object files.
• bin/: Final executables.

To clean the build artifacts run

make clean

To manually compile the two implementations run

gcc -std=c99 -Wall -Wextra -fopenmp \
    src/gridworld.c src/mcts.c src/main.c \ 
    -o bin/mcts_omp \
    -lm

for OMP and

nvcc -c src/cuda_rollout.cu -o cuda_rollout.o

gcc -std=c11 -Wall -Wextra -fopenmp -DENABLE_GPU \
    src/gridworld.c src/mcts.c src/main.c cuda_rollout.o \
    -o bin/mcts_cuda \
    -lm -lcudart

for CUDA

Running

OpenMP Version

to specify the number of threads, set the OMP_NUM_THREADS environment variable:

export OMP_NUM_THREADS=8

Then run the OpenMP executable:

./bin/mcts_omp [seed]

CUDA Version

run

./bin/mcts_cuda [seed] [rollouts]

Command-Line Arguments:

• seed: (optional) Random seed for reproducibility (default = 36).
• rollouts: (optional, CUDA only) Number of rollouts per simulation (default = 256).