In this assignment, you will be getting practice with the minimax algorithm. We will be using the game Connect 4 as the adversarial game. In Connect 4, the board (shown below) is a 6 by 7 board.
Players alternate selecting a column to place a token and the token falls to the last unoccupied space. To win the game, you must get 4 tokens adjacent to each other. They can be horizontal, vertical, or diagonal.
On Moodle, I have provided three files: connect4.py,
minimax.py, and driver.py. In your repository,
create a folder called hw-2. In this folder, create four
files: connect4.py, minimax.py,
driver.py, and hw2-write-up.txt. Copy the
contents of each file you downloaded into the appropriate file. Please
follow these naming conventions.
On Moodle, I have provided three files: connect4.py,
minimax.py, and driver.py. In your repository,
create a folder called hw-2. In this folder, create four
files: connect4.py, minimax.py,
driver.py, and hw2-write-up.txt. Copy the
contents of each file you downloaded into the appropriate file. Please
follow these naming conventions.
Throughout this assignment, you should only edit
minimax.py. You may now play the Connect 4 game by running
the following command in the folder where these files exist:
python3 driver.py
The three files used in this project work together as follows. The
connect4.py file defines the Connect4 class which can be
used to play Connect 4. It can determine if a move is valid, what
possible actions can be taken, and when the game is over. The
driver.py file allows users to play the game. It also
allows for a minimax agent to play the game. The minimax.py
file has an (unfinished) implementation of the minimax algorithm. It is
used by driver to run the game with minimax.
Currently, the implementation of minimax in minimax.py
is unfinished.
Finish implementing the minimax function in
minimax.py.
To run the code with an AI agent, you can use the following command:
python3 driver.py -x ai
This will have a human player be O and an AI agent be X. If you run this now, it will likely never finish. This is because Connect 4 has a very large game tree. Let’s make it more feasible.
Edit the implementation of the minimax function in minimax.py to use alpha beta pruning.
If you want to run the game with two AI agents, use the following command:
python3 driver.py -o ai -x ai
There is a good chance the tree is too large to run even with alpha beta pruning.
Edit the implementation of the minimax function in
minimax.py to use depth limited minimax. Use the
max_depth input variable to represent the maximum depth and
the cur_depth input variable to represent the current
depth. If the current depth equals the maximum depth and you are not at
a terminal state, the function should return 0 as the utility score and
None as the action.
You should now be able to run the game with a AI agents.
Play against an agent. In hw2-write-up.txt, describe
their first couple moves and general strategy. Explain why this is their
strategy based on our implementation. Play until you are able to beat
the agent. Describe the strategy you developed to beat them.
The crux of depth limited minimax is the agents ability to score a non-terminal state. To do this, we need to define a heuristic. Currently, the heuristic is “return 0”, since that is what the algorithm does in a non-terminal state.
A heuristic for non-terminal states.
In hw2-write-up.txt, describe a heuristic for
scoring a non-terminal state. Describe why you think this is a good
heuristic for the game.
Define a function called heuristic in the minimax
file that implements your heuristic. When the search tree is at a
maximum depth and not at a terminal state, it should use your heuristic
to score the state.
I’ll form a bracket of the students in class and pit each person’s
heuristic against each other. The top three algorithms will win fame,
fortune, and the universal acclaim of their peers.1
Make sure you have not edited connect4.py or
driver.py. If your code works with these, it should be
fine.
Observe the game tree shown below:
In traditional minimax, the max player would either make the move
towards the middle or right. Assume there is some randomness in the
game: with probability 1/4, the game
forces the player to make a random decision. In
hw2-write-up.txt, answer the following:
In this scenario, which decision should the max player make? Why?
Why would minimax not make this decision?
How could you augment the minimax algorithm to account for this?
Once you have finished, make sure to push your code and write-up to CSGit!
Also, I might bring in treats.↩︎