figure 1

Figure 1 shows our typical game board. Black wins by moving one piece to the opposite side, row index 5. White 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 blacks code work seamlessly for white as well.

figure 2

You can 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. 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.

Code is required for make_move() function of AI class 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].

Include reasoning behind:

Algorithms implemented,

Data structures used,

Evaluation function

Helper functions are given as follows:

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 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 wont 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 blacks code. So, when it is time for white to make its move, we invert the board using this function to see everything from white sides 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 blacks 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.

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.

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.

Figure 1. Game Board Figure 2. Possible Moves