HW#2 --- last modified September 26 2022 20:05:31.

Solution set.

Due date: Oct 7

Files to be submitted:
  Hw2.zip

Purpose: To reason about the hill-climbing, simulated annealing, and genetic algorithms. To code the minimax algorithm with alpha-beta pruning in a specific context.

Related Course Outcomes:

CLO2 -- Explain the advantages and disadvantages of the following techniques: (a) breadth-first search compared to depth-first search, (b) informed search compared to uninformed search, hill climbing, STRIPS/PDDL representations for planning.

CLO4 -- Apply alpha-beta pruning in adversarial search.

Specification: This homework consists of two parts: an experimental part, and a programming part.

For the experimental part please do the following and submit it in the file Hw2.pdf.

1. Make a 8x8 grid with values randomly chosen between 1-5 (do this programmatically) where a value i has probability determined by the procedure (flip an unbiased coin, if its heads treat it as a 1, it is tails, flip the coin again and if its heads treat it as a 2, if its tails flip the coin again ... -- If you get five tails in a row, restart the procedure). If you work out the probability a 1 should be twice as likely as a 2, etc. Include any test code you write with the homework. Start your agent in a uniformly at random chosen square and suppose your agent has the goal of finding a local maximum. In one time step your agent can sense one square, horizontally, vertically, or diagonally as well as the current square and then move one square is some direction from these choices. The goal is for your agent to find the maximum value square.
2. Do 10 trials (each trial with a different grid) of simulating the agent for 20 steps and determine the success rate of finding the maximum value.
3. Do 10 trials (each trial with a different grid) of simulating the agent for 10 steps with 1 restart (run 10 steps see value, run another 10 steps see value) and determine the success rate.
4. Do 10 trials (each trial with a different grid) of simulating the agent using local beam search with 2 beams running for a total of 20 steps and determine the success rate.
5. Modify the simulated annealing algorithm to this setting (include your modification in the write-up), conduct a similar experiment for this algorithm.

For the coding part of the homework, I want you to write a program to play deterministic Connect 4 Spin. This game is similar to the Hasbro Connect 4 Spin game. Like that game, it is a two player game played on 8 x 5 board. Each player determines their color from either red or yellow. The red player goes first. In a single move a player, can insert a token at a coordinate (i, j) on the board, and then optionally decide to flip any column of the board. The difference between this game and the Hasbro game is that in the Habsro game, when the player chooses to flip a column, it is with probability 0.5 that the flip is actually done. So our version is deterministic. The goal of the game is to get four tokens of one's color in a row either vertically, horizontally, or diagonally. The first person to do so wins the games. If all squares of the board have been filled in and no one has achieved this the game is a draw.

Your program will be run from the command line using the syntax:

python3 connnect4_spin.py

On this input, your program should output:

Which player would you like to play (R/Y)?

For our game the two players will be denoted R (for red) and Y (for yellow). If the answer to the prompt is R, then the human player gets to go first, otherwise, your AI agent player goes first. The state of the game after each move should be drawn, followed by a prompt for the next move or a statement that the game is over and who won or it is a draw. If the game is over the program can exit.

For example, if the human player is R, then the initial board should look like:

No moves yet
  1 2 3 4 5
 +-+-+-+-+-+
a|E|E|E|E|E|
 +-+-+-+-+-+
b|E|E|E|E|E|
 +-+-+-+-+-+
c|E|E|E|E|E|
 +-+-+-+-+-+
d|E|E|E|E|E|
 +-+-+-+-+-+
e|E|E|E|E|E|
 +-+-+-+-+-+
f|E|E|E|E|E|
 +-+-+-+-+-+
g|E|E|E|E|E|
 +-+-+-+-+-+
h|E|E|E|E|E|
 +-+-+-+-+-+

Please enter your move (format row-column-flip_column):

Notice, we are using the letter E to denote an empty square. If the human player typed:

d-4-n

It would mean that the play wants to place a tile at d-4 and the 'n' indicates that the player does not want to flip any column.

Your program should then print two boards, one after this move, and then one after the computer's response move. It then should prompt the player for a next move. Depending on the computer's move, this might look like:

Red moves d-3-n
  1 2 3 4 5
 +-+-+-+-+-+
a|E|E|E|E|E|
 +-+-+-+-+-+
b|E|E|E|E|E|
 +-+-+-+-+-+
c|E|E|E|E|E|
 +-+-+-+-+-+
d|E|E|R|E|E|
 +-+-+-+-+-+
e|E|E|E|E|E|
 +-+-+-+-+-+
f|E|E|E|E|E|
 +-+-+-+-+-+
g|E|E|E|E|E|
 +-+-+-+-+-+
h|E|E|E|E|E|
 +-+-+-+-+-+

Yellow moves e-4-3
  1 2 3 4 5
 +-+-+-+-+-+
a|E|E|E|E|E|
 +-+-+-+-+-+
b|E|E|E|E|E|
 +-+-+-+-+-+
c|E|E|E|E|E|
 +-+-+-+-+-+
d|E|E|E|E|E|
 +-+-+-+-+-+
e|E|E|R|Y|E|
 +-+-+-+-+-+
f|E|E|E|E|E|
 +-+-+-+-+-+
g|E|E|E|E|E|
 +-+-+-+-+-+
h|E|E|E|E|E|
 +-+-+-+-+-+

Please enter your move (format row-column-flip_column):

Notice we are use the letter n to indicate that the player does not want to spin any column. We see above that the computer spins column 3.

Red moves c-1-n
  1 2 3 4 5
 +-+-+-+-+-+
a|E|E|E|E|E|
 +-+-+-+-+-+
b|E|E|E|E|E|
 +-+-+-+-+-+
c|R|E|Y|E|E|
 +-+-+-+-+-+
d|E|R|Y|E|E|
 +-+-+-+-+-+
e|E|E|R|Y|E|
 +-+-+-+-+-+
f|E|E|E|R|E|
 +-+-+-+-+-+
g|E|E|E|E|E|
 +-+-+-+-+-+
h|E|E|E|E|E|
 +-+-+-+-+-+

Red wins! Game Over
>

Notice after the state we have been returned to the command line prompt. For a yellow win, we would have seen a line "Yellow wins! Game Over", for a draw we would see the line: "Draw! Game Over".

To make its move, your computer player should use the minimax algorithm with alpha beta pruning. At the top of your connnect4_spin.py program you should clearly say where to find the code for minimax and alpha-beta pruning. This completes the description of the homework.

Point Breakdown