Lab 3: Connect Four

Lab 3: Connect Four
Due Feb. 13 by midnight

Connect Four is a type of connection game, which begins with an empty rectangular board. Players take turns dropping pieces from the top of the board so that they land in the lowest empty spot in some column. A player who connects four of their pieces in a line (orthogonal or diagonal) wins. The examples below show the starting board, a board where white has won, and one where black has won (winning connections highlighted in blue).

 -------------
|· · · · · · ·|
|· · · · · · ·|
|· · · · · · ·|
|· · · · · · ·|
|· · · · · · ·|
|· · · · · · ·|
 -------------

 -------------
|· · · ● · · ·|
|· · · ○ · · ·|
|· · ● ● ○ · ·|
|○ ● ○ ○ ● · ·|
|● ○ ○ ○ ● · ·|
|○ ○ ● ○ ● · ●|
 -------------

 -------------
|● · ○ · ○ · ·|
|● · ○ · ○ · ●|
|● · ● ● ○ ● ●|
|○ ● ○ ● ● ○ ○|
|● ○ ● ○ ● ○ ●|
|● ○ ○ ● ○ ○ ○|
 -------------

In this lab you will create an AI Connect Four player.

Starting point code

You should begin by cloning the starting point code from your github repository.

cd ~/cs63/labs
git clone git@github.swarthmore.edu:...

Introduction

The objectives of this lab are to:

Use the bounded min-max algorithm to play Connect Four.
Improve the efficiency of min-max by adding alpha-beta pruning.
Create an informative static evaluation function for Connect Four.
Test your min-max player against other opponents.

You will only need to modify one python file, MinMaxPlayers.py, butyou will also use the following files:

ConnectFour.py, which implements (generalized) Connect Four.
BasicPlayers.py, which contains several simple players.

Try running ./ConnectFour.py -h to see the available command line options. Then try playing against a really terrible opponent by running:

./ConnectFour.py random human --show

Connect Four

Begin by completing the following steps:

Open the file ConnectFour.py and review the methods that have been provided. Notice that the board is represented as 2-dimensional array of integers. Blank spaces are 0, the first player's pieces are +1, and the second player's pieces are -1.
When you execute this file you can play a game against a random player. Try playing several games to be sure you understand how the game operates.
Be sure you understand how the winner determination method works. The static evaluation functions you write will make use of similar logic.
Open the files BasicPlayers.py and MinMaxPlayers.py to see how we will be implementing Connect Four players. The HumanPlayer and RandomPlayer classes are provided to make your testing easier.

Bounded Minimax

Next focus on the MinMaxPlayers.py file, and complete the following steps:

Implement the basicEval method to score boards based on the longest connected run of pieces each player possesses.
Implement the MinMaxPlayer.getMove method to run bounded min-max search and return the best move found. Bounded min-max does a depth-first traversal of the game tree and backtracks when it hits a leaf or the depth limit. You are welcome to implement either pseudocode version from the lecture slides. You will probably want to add at least one recursive helper function. Remember that at internal nodes, we need to return the value, but at the root node, we need to return a move. Here is (yet another) version of min-max search pseudocode, this time with a depth bound:
```
bounded_min_max(node)
    if node's depth is at limit
        return staticEval(node's state)
    if node's state is terminal
        return staticEval(node's state)
    initialize best value
    get all possible moves from the node's state
    for each move
        determine the next state
        create a node for the next state
        # Recursive call
        value = bounded_min_max(next node)
        if value better than best value # depends on player
            update best value
    return best value
```
Thoroughly test min-max. During testing, add print statements during single games to verify that your evaluation function is working correctly and that min-max is picking correct moves according to that value.
Once you are certain that min-max is working properly, comment out the print statements and do more extensive tests using a series of games. With a depth limit of 2, your MinMaxPlayer should win the majority of games against a random player. Try playing against it yourself!

Better Static Evaluation Function

Come up with an improved static evaluator for Connect Four and implement it in the betterEval function.

Your goal is to create an evaluator that will beat the basicEval function when tested in a series of games using minimax players with equal depth limits.

Your static evaluator should:

Not consider the past or future, but just evaluate the current board.
Be efficient to calculate.
Be deterministic (always returns the same value for the same board).
Score terminal states correctly with maximal positive values for the first player and maximal negative values for the second player.
Generate scores that are correlated with the chances of winning.

Write a clear and thorough comment with your betterEval method to describe how it works. If you add helper functions, be sure to include comments describing these as well.

Alpha-Beta Pruning

We will cover this pruning technique in class later this week. For now you can look ahead to Wednesday's reading, read the description of alpha-beta pruning in the Poole & Mackworth textbook, or check out the alpha-beta pruning Wikipedia article.

Note that alpha-beta pruning should always return the same scores as Minimax would, but it can potentially do so much more efficiently by cutting off search down branches that will not change the outcome of the search.

Playing against your friends

The shell script package_agent.sh runs the following commands:

mkdir username1-username2_agent/
touch username1-username2_agent/__init__.py
cp *.pyc username1-username2_agent/
tar -zcf username1-username2_agent.tar.gz username1-username2_agent/

The result is a compressed directory called username1-username2_agent.tar.gz that contains your .pyc files. If you don't have pyc files for some of your code, just run python and import the file you want compiled. You should edit the script to actually reflect your usernames. If you have your friend's tarball (suppose it's called bwieden1-agent.tar.gz), you can run

tar -xzf bwieden1-agent.tar.gz

To get a directory with the same name: bwieden1-agent. Once you have this directory, you can add a line to your python code to import your friend's agent:

from bwieden1-agent import MinMaxPlayers.TournamentPlayer as FriendAgent

and then test against their implementation.

Tournament

Next week, we will hold a tournament among the agents you submit. I will run your MinMaxPlayers.TournamentPlayer agent against those of your classmates. Your TournamentPlayer, should use your PruningPlayer with a heuristic of your choice, and whatever depth limit you deem best. Your agent must run on a single CPU and will be limited to five seconds per move (if it takes longer, a random move will be chosen).

None of the points for the assignment depend on outcomes in the tournament; it's strictly for fun. If you would like to opt out of the tournament, you may do so by sending me an email before the submission deadline.

Submitting your code

Before submitting, ensure that you have added your name(s) to the top-level comments. To submit your code, you need to use git to add, commit, and push the files that you modified.

git add MinMaxPlayers.py
git commit -m "final version"
git push