Project Proposal
Wei Chen (wc3@andrew.cmu.edu), Ran You (rany2@andrew.cmu.edu)
SUMMARY
We will implement a parallel solver of the Chess with the Multiverse Time Travel game using MPI, OpenMP, and Cilk on the GHC machines.
Contents
Background
Chess with Multiverse Time Travel is a chess game that allows pieces to travel back in time and travel through timelines. In this game, chess pieces can travel to the past, upon which a new timeline (or chess board) will be created exactly as it was at that point in time with the travelled piece added to it. In addition, chess pieces can also travel between timelines. At each turn, players must play a move on all of the active boards. And the game ends when checkmate happens on any chess board.
Source: https://steamcommunity.com/sharedfiles/filedetails/?id=2204910380
In the case when the entire board gets too large, we will prune the earliest created boards if there are more than 16 currently active boards in order to reduce search space as well as parallel processes.
Source: https://steamcommunity.com/app/1349230/screenshots/
This is an application largely based on an AI of the original chess game. Despite the additional communication, synchronization, and optimization across chess boards, the game proceeds in the exact same rules as normal chess. Our goal is to build a parallel program to solve the game, i.e., find a relatively good move at each step, but not to build a good parallel game interface, although the program will include both a game engine and a game solver.
Things to parallel include searching for the best move on all chess boards, where parallelization is across chess boards. As the search space (4D) is much larger than normal chess, it’s essential to parallelize the searching process within one chess board, where parallelization is across search space. Since different chess boards have data dependencies (chess pieces can move from one chess board to another), and the optimization is carried over all temporal and parallel boards, it requires communication (shared state or message passing) and synchronisation over different processes.
In case this game is too hard to simulate, one fallback option is bughouse, which has two parallel chess boards, and pieces can be moved across these two boards.
Challenges
- Game logic: The logic of this game is more complex than the original chess, because there are multiple concurrent boards, game state is much larger, search space is much larger, and different chess boards have data dependencies.
- Utility function: The utility function is not trivial, and is critical to the optimization. Some basic ideas include maximizing distance between the king and opponent’s pieces (or the other way around), maximizing the number of steps taken for the opponent to eat any of the pieces, minimizing the number of eaten pieces, etc. We will mostly learn from available sources to build the utility function.
- Optimization algorithm: We will base our optimization algorithm on the Minimax Algorithm. We hope to make the optimization logic as simple as possible in order to focus on parallelization.
- Historical game states: We need to design a data structure (boards or moves between boards) in order to recreate any historical board efficiently, and these boards should be easily accessible during optimization.
- Data dependencies: There are data dependencies across boards when searching for the best move, since pieces can move across boards. There are also data dependencies across game states within one board during the monte carlo tree search.
- Work assignment: We are still unsure about how exactly to map work to resources. And one of our goals in this project is to experiment with different work assignments.
- Load balancing: The search space can differ across different boards and timestamps.
- Communication and synchronization: Different chess boards need to communicate and synchronize in this game. We plan to compare the shared address space model with the message passing model using MPI, OpenMP, and Cilk.
- Evaluation: There is a tradeoff between a better move and better speedup. We need to figure out how to evaluate the quality of a move, how to evaluate speedup, as well as clearly define the evaluation metrics.
Resources
We plan to build our game program from scratch, although we will largely learn from available sources:
We will also learn from available sources about building chess AI, the optimization algorithms, and how to construct a reasonable utility function.
Goals and Deliverables
We will implement a game engine and a game solver, the game solver is based on a simple AI using the Minimax algorithm, and our main focus is to parallelize and optimize the entire game simulation process. The performance of our program is based on the quality of the searched results and the time it takes to solve a step at a fixed number of concurrent chess boards.
In the end, we want to demonstrate a game simulation using visuals (hopefully videos). We will present our algorithm, which parts are parallelized, the optimization results, the speedup results, and a comparison across models and frameworks.
Plan to Achieve
- Build a parallel game simulation (including a game engine and a game solver).
- Compare the shared address space model with the message passing model.
- Compare the three parallel programming frameworks (MPI, OpenMP, and Cilk).
- Parallelize the Minimax algorithm, evaluate speedup compared with sequential version.
- Parallelize the multiverse chess game, evaluate speedup compared with sequential version.
Hope to Achieve
- More complicated chess AI using other heuristics or optimization algorithms.
- Analyze tradeoff between optimization and speedup.
Platform
We will be using the GHC machines for development, testing, and experiments. We hope to use Bridges-2 in order to leverage more parallelism, if that’s possible.
Schedule
| Week | Tasks |
|---|---|
| Week 2: 11/12 - 11/14 | Draft new proposal |
| Week 3: 11/15 - 11/21 | Research about Chess with Multiverse Time Travel Design and implement the sequential version |
| 11/22 | Milestone Report |
| Week 3: 11/22 - 11/28 | Parallelize the program using different parallel frameworks |
| Week 4: 11/29 - 12/05 | Optimize the parallel implementation |
| Week 5: 12/06 - 12/09 | Conduct experiments and analysis on the parallel program Write project report and prepare for project presentation |
| 12/09 | Project Report |
| 12/10 | Poster Session |