One of the primary goals of my ongoing research is to explore the issues related to efficient parallel code on a distributed network as opposed to a supercomputer. I chose to use a distributed network to gain varied exposure to parallel interaction. To do this, I explore several aspects of game theory, in the context of the game Othello.
The challenges faced in parallel programming on a distributed network differ from those faced with a supercomputer in several ways. Primarily, communication between processors is much slower and less reliable. Thus creating an efficient program, one that can overcome such pitfalls and delays, is more difficult. At the same time, workstations are individually more reliable and accessible than supercomputers, allowing more confidence in response and greater productivity. Lastly, due to the general accessibility of workstations, there is a wider range of software and tools available to optimize and debug programs.
Othello is particularly attractive because, unlike other strategy board games, it is rather easy to implement while remaining a challenging game to play. In order to examine the merits of a parallel version of the game, I used an optimized sequential version of the game for timing comparisons. Since I am dealing with a game, the benchmark for performance is the actual time elapsed while the move is chosen because a human player is less inclined to play a game with long time delays between moves However, for the computer to play a challenging game, it must examine the repercussions of its actions many moves in the future.
The minimax algorithm, especially with alpha-beta cutoffs is an interesting candidate for parallelization. Like Othello, it is very straightforward and and easy to implement, while being computationally intensive and complex. In addition, because the work is a tree search rather than a homogeneous system, it provides unique challenges to parallelization. Such a solution has wide application due to the number of pruned tree-searches that occur in a variety of situations.