Overview

Breakthrough was the winner of the 2001 8 × 8 Game Design Competition, sponsored by About.com and Abstract Games Magazine. When Dan Troyka formulated it, it was originally for a 7×7 board. We’re going to play it on a 6×6 board to limit the complexity. In terms of our terminology for the agent environment, Breakthrough is a fully observable, strategic, deterministic game. The game always results in a win for one of the two players. So what are you going to do? You are going to play the game of Breakthrough – not as yourself but through the surrogate of your program.

How exactly do you code an AI to play this game? Well, like everything else in this course, we code an agent. An agent takes sensory input and reasons about it, and then outputs an action at each time step. You thus need to create a program that can read in a representation of the board (that’s the input) and output a legal move in Breakthrough. You then need a evaluation function to evaluate how good a board is to your agent. The better your evaluation function, the better your agent will be at picking good moves. You need to put some thought into the structure of your evaluation function.

Aside from the evaluation function, you also need to decide a strategy for exploring the search space. Certainly you can use minimax search but you may want to decide whether you want to use alpha-beta pruning on top of this. You would want to make the best move that you can given the limited time for each move (further provided clarification below).

Required Files:

• template.py: contains code for playing breakthrough between two different game playing agents. Your minimax algorithm will be written in this file.
• utils.py: contains some utility functions that can be used directly.

Honour Code: Note that plagiarism will not be condoned! You may discuss with your classmates and check the internet for references, but you MUST NOT submit code/report that is copied directly from other sources!

Breakthrough Technical Description

Figure 1. Game Board

Figure 1 shows our typical game board. Black (B) wins by moving one piece to the opposite side, row index 5. White (W) wins by moving one piece to row index 0. Kindly follow the same indexing as provided in Figure 1, and write code only for moving Black. A simple board inversion will make black’s code work seamlessly for white as well. This technique has been used in the game playing framework of template.py for managing this two player game (the invert_board function is provided in util.py).

Figure 2. Possible Moves

Pieces move one space directly forward or diagonally forward, and only capture diagonally forward. The possible moves have been illustrated in Figure 2. In this figure, the black pawn at (3, 2) can go to any of the three spaces indicated forward. The black pawn at (0,4) can either choose to move by going diagonally right or capture by going diagonally left. It cannot move or capture by moving forward; its forward move is blocked by the white pawn. Note that your move is not allowed to take your pawn outside the board.

Your program will always play black, whose objective is to move a black pawn to row index 5. Given a move request, your agent should output a pair of coordinates in the form of a pair of one dimensional lists using the coordinate system shown in the figure. For example, for moving the black pawn standing at (0,4) in Figure 2 to (1,3), your agent should make a move that returns the two lists: [0, 4] and [1, 3].

Your agent should always provide a legal move. Moves will be validated by the game playing framework provided in template.py. Any illegal moves will result in a decrease in the score of your assignment. If your player makes an illegal move, the competition framework will choose the next available valid move on your behalf. Your agent must always make a move; it is not allowed to skip moves. Your program cannot take more than 3 real-time seconds to make a move. If your program does not output a coordinate within 3 seconds, it will decrease your assignment score further and the competition framework will choose a random move on your behalf.

Submission Details

1. You will need to submit your code written for make_move() function of PlayerAI class (see template.py) in Coursemology — you will have to write your minimax algorithm with alpha beta pruning here. This function takes the board configuration as its parameter and should return the move to be made by utilizing your designed game playing algorithm based on alpha beta pruning (you are allowed to write as many assisting function as you want).

The board configuration is passed as the parameter of the function in the form of a two dimensional list of size 6 × 6 (initially, board configuration will look like Game Board in Figure 1). It is represented as a 2D list containing three types of characters: (1) "W" for denoting white pawns, (2) "B" for denoting black pawns, and (3) "_" for denoting empty cells. The move to be made has to be returned in the form of two lists (source position of move, destination position of move). For example, if your function returns [0,4], [1,3], that means the black pawn will move from position [0,4] to [1,3].

2. Apart from your code implementation, you should also wrote a report to let us know the thought process behind your solution. Take this opportunity to convince your grader that you have understood the concepts taught in class and are able to apply it. Your response should include any information you want the grader to know about your submission (see text response question in coursemology). This includes, but is not limited to, descriptions of:

1. your algorithms implemented,
2. your data structures used,
3. your evaluation function(s)

Your grader should be able to understand everything about your solution from reading this response. That said, your code will also be analyzed for correctness and consistency. Note that the report is expected to be (on average) 2-3 pages worth of report on an A4 word document.This mini-project is a journey and not just a destination. Our hope is that you will try out different things to make your agent better. Instead of only documenting your final solution, you would also be given credit for describing the approaches that did not quite work.

It is okay to try something and fail. The key is to understand why.

Provided Utility Functions

You can use the functions provided in util.py file as you see fit. These functions have mainly been used by the game playing framework in template.py to facilitate the two player game. A short description of these functions is given below:

• generate_init_state(): It generates initial state (Game Board in Figure 1) at the start of the game.
• print_state(board): It takes in the board 2D list as parameter and prints out the current state of the board in a convenient way (sample shown in Possible Moves in Figure 2).
• is_game_over(board): Given a board configuration, it returns True if the game is over, False otherwise.
• is_valid_move(board, src, dst): It takes in the board configuration and the move source and move destination as its parameters. It returns True if the move is valid and returns False if the move is invalid.
• state_change(curr_board, src, dst, in_place=True): Given a board configuration and a move source and move destination, this function changes board configuration in accordance to the indicated move.
• generate_rand_move(board): It takes in the board configuration as its parameter and generates an arbitrary valid move in the form of two lists. You likely won’t need to use this function. This function is used by the game playing framework in one of two cases – (1) an invalid move has been made by the game playing agent or, (2) the game playing agent has taken more than 3 seconds to make its move. This function updates the board configuration by modifying existing values if in_place is set to True, or creating a new board with updated values if in_place is set to False.
• invert_board(curr_board, in_place=True): It takes in the board 2D list as parameter and returns the inverted board. You should always code for black, not for white. The game playing agent in main.py has to make move for both black and white using only black’s code. So, when it is time for white to make its move, we invert the board using this function to see everything from white side’s perspective (done by inverting the colors of each pawn and by modifying the row indices). An example of inversion has been shown in Figure 3 Board Inversion Illustration later. In your minimax algorithm, you need to consider both black and white alternatively. Instead of writing the same code twice separately for black and white, you can use invert_board() function to invert your board configuration that enables you to utilize black’s codes for white pawns as well. That is enough for hints, I guess. This function inverts the board by modifying existing values if in_place is set to True, or creating a new board with updated values if in_place is set to False.

Other functions are used to play the game or test your solution. You don’t need to use those functions when you implement your PlayerAI.

Testing Your Game Playing Agent

Fill in make_move(board) method of the PlayerAI class with your game playing agent code (you can write as many assisting function as you deem fit). The PlayerNaive class has been provided for you to test out your agent against another program. Always code for Black (assume Black as max player) in both these class functions. The game playing framework calls the make_move(board) method of each agent alternatively. After you complete PlayerAI, simply run the template.py file. You will see the two agents (PlayerAI and PlayerNaive) playing against each other.

Always remember to return your move within 3 seconds. You should check for time passed during every recursive call in minimax algorithm to follow this 3 second rule. Whenever you see that 3 seconds is almost over, immediately return the best move you have at your disposal. That is all the hint I can give you. This is really important because the machine where we will run your code maybe much slower than your local machine.

Figure 3. Board Inversion Illustration

You have chance to be innovative mainly in 3 areas – (1) the evaluation function used to evaluate the goodness of a state, (2) effective exploration strategy maintaining the time constraint and (3) modifying the alpha beta pruning algorithm for more efficient search. Ultimately, we shall be playing all the student designed agents against each other. So, it will be a small breakthrough tournament. The top players will get some bonus marks.

Grading Guidelines

This mini-project will constitute 10% of your overall grade for CS2109S. The following is the criteria under which your submission will be graded.

Your code will constitute 60% of this mini-project grade. We look for:

• Making Valid Moves (5%): Ensure your moves are valid and complete every move within 3 seconds to get full marks for this section.
• Performance Against Baseline Agent (15%): Your submitted agent code will be run against our baby agent and a base agent. You should win all our agents and make less than or equal to 3 random moves to get the full credit for this section.
• Algorithm Implementation Check (30%): If you implement the minimax algorithms and the alpha beta correctly, you receive these marks irrespective of the performance of your agent.
• Evaluation Function Check (10%): Remember this is a zero-sum game, so your evaluation function should maximize your probability of winning while minimize other player’s chance of winning.

The other 40% will be graded purely based on how well your agent perform against other students’ agents.

Additional note: As a non-exhaustive list, you are not allowed to:

1. Change the testing framework / timer
2. Use python to compile C++ script as this is hardware advantage
3. Use of multi-process as this is hardware advantage

The maximum size of code you can upload is 10MB.Try your best and enjoy!

Note for Windows users

Note that although the Jupyter notebook should work in Windows, we recommend using WSL to test your code. Here are some instructions to help you install WSL and setup Jupyter notebook. (optional)

1. Open PowerShell or Windows Command Prompt in administrator mode by right-clicking and selecting “Run as administrator”, enter the wsl –install command, then restart your machine. You may find more information about WSL here.

$ wsl --install

2. Once WSL is installed, look for the Ubuntu app in the Windows Start menu and open it. Although Python comes preinstalled with most of the Linux distributions, it unfortunately doesn’t comes with WSL. So you have to install it manually. To do that write the following commands in the Ubuntu shell:

$ sudo apt update && upgrade
$ sudo apt install python3 python3-pip ipython3

3. This will install Python 3 in your WSL. To check python version type

$ python3 --version

4. Install Jupyter by typing the following command in your Bash Shell.

$ pip3 install jupyter

5. WSL uses a separate file system from your Windows system. To move files from Windows to WSL, open file explorer and navigate to \\wsl$\Ubuntu\home\<username>. Files stored in this folder will appear in the Linux root directory in WSL.
6. Move your Mini Project folder into WSL. In the Ubuntu shell, change directory into the Mini Project folder and run the following command:

$ jupyter notebook

7. Jupyter will start a server using the python distribution in WSL. Follow the url to open jupyter notebook in your browser.

Task 1: Make Valid Move Given a Board Representation

Input: A board state represented as a 2D list

Output: two 1D lists representing source and destination of your move

Note: Your move has to be valid and it has to be made within 3 seconds

Task 2: Report

Describe your implemented algorithm, data structure, evaluation function and any other information that you want the grader to know about. Write your response in the coursemology textbox, or paste it there after you are done writing.

Submission

Once you are done, please submit your work to Coursemology, by copying the right snippets of code into the corresponding box that says ‘Your answer’, and click ‘Save’. After you save, you can make changes to your submission.

Additional note: Please read the detailed submissions instructions under Coursemology question description. The first three questions requires you to paste the exact same code. The difference is that the first question test on whether your agent make a valid move within the given time limit. The second question and third question are playing the actual game against our agents. Note that each public test case can take a maximum of 5 minutes to complete, and you have maximum 20 attempts for question 2 and 3 respectively.

Once you are satisfied with what you have uploaded, click ‘Finalize submission.’ Note that once your submission is finalized, it is considered to be submitted for grading and cannot be changed. If you need to undo this action, you will have to email your assigned tutor for help. Please do not finalize your submission until you are sure that you want to submit your solutions for grading.