Final Report.We implemented and parallelized an algorithm that plays N-dimensional “ultimate” or “meta” tic-tac-toe against itself (NxN tic-tac-toe boards of size NxN running at the same time). Our algorithm is based on alpha-beta pruning, which we tried parallelizing in two different ways using OpenMP. While we achieved modest speedup, we discovered that parallelizing such a heavily recursive algorithm is probably not worth the effort.
|