Skip to main content

Click on on link to clone

Cilk: Parallel game AI

The purpose of this assignment is to give you experience writing programs with Cilk.

What is Cilk?

Cilk is a parallel extension to the C/C++ programming language. For this assignment you will be using “Cilk Plus” included with the GCC 6 compiler suite. Cilk adds a few keywords to C (cilk_spawn, cilk_sync, cilk_for, etc). From Wikipedia: The biggest principle behind the design of the Cilk language is that the programmer should be responsible for exposing the parallelism, identifying elements that can safely be executed in parallel; it should then be left to the run-time environment, particularly the scheduler, to decide during execution how to actually divide the work between processors. It is because these responsibilities are separated that a Cilk program can run without rewriting on any number of processors, including one.

Game AI Introduction

For this assignment you will be parallizing an AI for the game Othello. Othello (also known as Reversi) is a strategy game played on an 8 x 8 gameboard. The rules to the game and a brief explanation of strategy issues are available on the Wikipedia page for Reversi.

A webite with an interactive program to play the game is https://www.mathsisfun.com/games/reversi.html.

These files include the main program (othello.c) and two players, a human player (othello-human.cpp), and a simple AI player (othello-simple-ai.cpp). The simple AI chooses a random move from all of the available moves and is included to test your “good” AI against. The Simple AI can give a unique game every time. However, do NOT run experiments with a completely random AI. The seed chosen in the template gives an “interesting” game and should be used when running experiments. You can uncomment the random seed in main while debugging to produce more than one game scenario.

Also included in the template is a timing library. It times the second player of the game, giving both total runtime and per-turn runtime.

Part 1 (Implement Serial minmax)

Template file:othello-good-ai-serial.cpp

To implement an AI for Othello you will us the minimax algorithm, detailed on Wikipedia. The minimax algorithm is a recursive algorithm for choosing the next move in an n-player game, usually a two-player game. Information on minimax can also be found in Russel, Norvig: Artificial Inteligence: A Modern Approach. From Wikipedia, the psuedocode for the algorithm is

function integer minimax(node, depth) if node is a terminal node or depth <= 0: return the heuristic value of node obj +=... for child in node: # evaluation is identical for both players obj = max(obj, -minimax(child, depth-1)) return α

The minimax algorithm turns out to naturally fit into Cilk’s task parallel programming model due to its recursive nature.

For example, searching 1 move ahead for Player 1 means selecting best legal move for Player 1 based only on comparing the board states that would result from any of the possible legal moves for Player 1. Searching 2 moves ahead for Player 1 means selecting the move that would result in the best board position after Player 1’s move followed by Player 2’s best move. This process of considering alternating moves generalizes naturally to consider lookaheads of n moves.

Note that if one player cannot move, his opponent can move again if any legal moves remain; your search should account for this accordingly. Note: Constructing a sophisticated board evaluator to compute the best strategic move is beyond the scope of the assignment. A simple board evaluator that computes the best move by maximizing the difference between the number of your disks and the number of the opponents disks on the board will suffice. However, if you want to implement a more complicated evaluations function feel free.

TODOs

  • Implement a sequential version of GoodAITurn. This is where you will implement the minimax algorithm with a depth of DEPTH(the depth parameter found in othello-good-ai.c)

Part 2 (Parallelize minmax)

You will write a shared-memory parallel program in Cilk that enables the computer to play the game. Implement the computer player as a parallel function that plays Othello/Reversi by searching n moves ahead to select the “best board position” for its move.

A template has been provided: othello-good-ai-parallel.cpp. You may use this program as you see fit to get a jump start on your assignment. Feel free to use the code directly as the basis for your parallel solution.

Implement the parallel version of GoodAITurn. You may choose to implement a new version of GoodAITurn, or keep a single version of GoodAITurn which is parallel and add “-cilk-serialize” to the CFLAGS for the sequential version of Othello. Hint: You may want to use reducer objects. How reducers and other hyper-objects are implemented can be found here and how to use reducers can be found here.

Report

  • Compile variants of othello-parallel to have the good AI player use lookahead depths 1, 2, 3, 4, 5, 6 and 7. Graph your measurements of timings with respect to the lookahead depth. Give a couple sentences of why you think the graph looks like it does. Did it look like what you expected?
  • Run both your parallel and sequential versions of othello on one of the amoeba nodes for lookahead depths of 1,2,3,4,5. For a depth of 5, run your parallel version with 1,2,4,8,16 threads. You can specify the number of threads for Cilk CILK_NWORKERS=N othello-parallel -cilk_set_worker_count=n.
  • How does your parallel version of othello scale with the number of threads? Is this what you expected?

Building

CLI Game of Othello.

mkdir -p build
cmake ../
# if you want to serialize and request Cilk to serialize tasks cmake -DCMAKE_CXX_FLAGS="-DSERIALIZE" ../

Two versions are compiled by default, othello-serial and othello-parallel. othello-serial has the provided simple-ai (player X) play against a serial implementation of depth-limited minimax (player O). Similarly, othello-parallel faces simple-ai (player X) play against a parallel implementation of depth-limited minimax (player O).

_ Usage _

./build/othello-serial   [depth] [srand]
./build/othello-parallel [depth] [threads] [srand]

optional parameters:
  depth      		    Integer limiting the search depth of othello-good-ai.
						 Default = 4.
  threads		        Sets the number of cilk_nworkers.  Has no effect on
						 othello-serial.  Default = count_cpu_cores.
  srand		            For debugging, allows changing the seed of simple-ai
					     to get different games.  Default = 10.

Report and Testing.

We provide a sample report template: Report.docx and a set of testing scripts. The testing scripts are as follows.

Part A - Othello Parallel. Vary depth and study execution time (threads = 16)

cd repo/
source ./scripts/run-part-a.sh
# Depth varies 1--7. Threads fixed to 16. Random seed is 10. Trials = 5

This will create a folder output-a/ with a set of log files. Each file is named ($d(depth) $t(threads) $r(random seed) $n(run number)”.txt).

Each entry in the .txt file has output format (see next section). process the next file using the provided python script

cd output-a
python3 ../txt2csv.py > output-a.csv

output-a.csv will be a comma separated csv, which you can load into excel or another tool for plotting. Each row in csv summarizes data from a particular run.

DEPTH,THREADS,SEED,TRIAL,X_SCORE,O_SCORE,TIME(ns),TURN(ns)

When seed and trial fields are -1, that indicates an average calculated value for Time(ns), Turn(s) across other rows ib file.

Part B - Othello serial (vary depth and study execution time)

source ./scripts/run-part-b.sh
cd output-b/
python3 ../txt2csv.py > output-b.csv
# Depth varies 1 to 5. Random seed 10. 5 trials per depth.

Part C - Othello Parallel (2 sets of runs)

source ./scripts/run-part-c.sh
cd output-c/
python3 ../txt2csv.py > output-b.csv
# Experiment set 1: Depth varies 1 to 4. Random seed 10. 5 trials per depth. Number of threads 4.
# Experiment set 2: Depth set to 5. Random seed 10. 5 trials per parallelism. Number of threads vary from 1 to 16.

Example Output

A series of gameboards showing the moves of each player until neither player has a legal move. Then the winner is calculated and shown (or a declaration of a tie). Additionally, othello-good-ai (player O) has their move timings reported as the cumulative thinking time and average time per turn.

othello-serial

$ ./othello-serial
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X X . . .
6 . . . . X . . .
7 . . . . . . . .
8 . . . . . . . .
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . X O . .
7 . . . . . . . .
8 . . . . . . . .
.
.
.
  1 2 3 4 5 6 7 8
1 . X X X X X . O
2 O O O O O O O O
3 O O O X O O O O
4 O O O O O O O O
5 O O O O O X O O
6 O O O O O O O O
7 O O O O X O O O
8 O O O O O O O O
Game over.
X has 8 disks. O has 54 disks. O wins!
Total time: 497084802ns
Timer per turn: 16569493ns

Now, to change the look-ahead depth, use the first parameter.

$ ./othello-serial 7
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X X . . .
6 . . . . X . . .
7 . . . . . . . .
8 . . . . . . . .
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . X O . .
7 . . . . . . . .
8 . . . . . . . .
.
.
.
  1 2 3 4 5 6 7 8
1 O O O O O O O .
2 O O O O O O O O
3 O O O X O O O O
4 O . O O O O O O
5 O O O O X O O O
6 O O O O O O O .
7 . . O O O O O O
8 . O O O O O O O
Game over.
X has 2 disks. O has 56 disks. O wins!
Total time: 204218587772ns
Timer per turn: 7042020268ns

othello-parallel

Use the second parameter to change the number of worker threads.

$ ./othello-parallel 5 16 # 5 is depth to search. 16 is number of workers
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X X . . .
6 . . . . X . . .
7 . . . . . . . .
8 . . . . . . . .
  1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O O O . .
5 . . . X X . . .
6 . . . . X . . .
7 . . . . . . . .
8 . . . . . . . .
.
.
.
  1 2 3 4 5 6 7 8
1 X O O O O X X O
2 X O O O O O X X
3 O O X O X O O X
4 O O X X O O O O
5 O O O X X O O O
6 O O X O X X O O
7 O O X X X X X O
8 O O O O O O O O
Game over.
X has 21 disks. O has 43 disks. O wins!
Total time: 917826761ns
Timer per turn: 29607314ns

Comments

Start early.

  • Run multiple experiments to reduce the chances that your performance numbers are wrong due to contention.
  • Run using slurm to ensure users do not trample on each other when running experiments.