This assignment is to write a pair of game-playing agents that can play two simplified versions of the game Backgammon. This game normally involves rolling dice. In the first version of the game, there is no dice-rolling. Instead, it's as if one die had only 1s on all six of its faces and the other die had only 6s on all six if its faces. This adaptation removes the stochastic element of Backgammon, and it allows Minimax and Alpha-Beta pruning to be the appropriate techniques of choice for an agent. We'll call this variation of the game "Deterministic Simplified Backgammon" (DSBG).

In the second version of the game, the dice rolling works normally, so expectiminimax search is the way to go, and neither Minimax nor Alpha-Beta is appropriate. We'll call this variation of the game "Stochastic Simplified Backgammon" (SSBG).

In both versions, several of the rules of normal Backgammon are removed or simplified so that the new versions are easier to play.

The reading for this option consists of four parts: (a) some optional background on the game and its recent resurgence in popularity, (b) Search in The Elements of Artificial Intelligence with Python, which includes material on minimax search and alpha-beta pruning, (c) the lecture slides on Expectimax search linked from our course calendar, and, if needed, (f) the article on expectiminimax search at Wikipedia.

To get started with this option, read the standard rules of Backgammon.

The boards for Backgammon come in many different color arrangements, as do the "checkers" and dice. Above are photos a couple of different ones. The one on the right is courtesy of lead TA Amir's parents. The version of the board implemented in our A3 starter-code initial state and game master is like the board on the left, but flipped upside down, so white is moving clockwise and red is moving counter-clockwise.

Here are the simplifications we are assuming in both of our simplified versions of the game (deterministic and stochastic):

• no doubling cube or doubling of the betting stakes -- in fact betting is ignored, too;
• if a player gets matching dice on a turn (e.g., a pair of fours), nothing special happens -- the player does not get to move four pieces instead of two, for example;
• white always goes first;
• a player can pass on using both dice;
• a player does not have to use the higher-valued die when only one or the other can be played;
• bearing off a checker requires either an exact roll of a die, or if the checker is a farthest one from the goal, a die roll one greater.

The starter code contains the following files:

• agents/
  1. SkeletonAgent.py & randomAgent.py: These are two default agents that plays the game by choosing random or first possible move and you can see how it interacts with genmoves.py, so you can make your own agent do that.
  2. backgammon_dsbg.py: edit this file to implement your DSBG agent.
  3. backgammon_ssbg.py: edit this file to implement your SSBG agent.
• client.py: This is the main file that runs a game between two agents. Details on how to run a game are given below in section F.
• ui/: This directory is for the GUI. You SHOULD NOT change anything in any of the files in this folder.
• game_engine/:This directory contains code that provides the logistic about the board and generates the move. You SHOULD NOT change anything in any of the files but defintely take a look at explanations below.
  1. boardState.py:This file provides a representation for the states in both versions of the game. Your agents will make moves by receiving from the game master a reference to the current state, plus the result of rolling the dice (in the case of SSBG) or just two fixed pseudo-dice values (in the case of DSBG), and then returning the description of a legal move. There is a sample agent file that you can examine to see what the data format is for the legal move.
  2. genmoves.py: Provides functionality to generate one or more (or all) legal moves from a given state. To see an example of using this functionality, look at SkeletonAgent.py
  3. testStates.py: This file contains some example states in Simplified Backgammon -- basically either DSBG or SSBG, that you might find useful when analyzing to see how your agent does in some special situations.

You should create two agents. One will be able to play DSBG. The other will be able to play SSBG. These two agents can be very similar, except that the algorithms they use for choosing a best move should be different. As mentioned above, starter files are included for these agents: backgammon_dsbg.py and backgammon_ssbg.py

For DSBG, your agent should use Minimax search. You should also implement Alpha-Beta pruning for this search. At some point you'll probably want to have your agent play itself. In that scenario, you'll probably be creating two instances of the class.

Your DSBG agent should have two counter variables. One will count the number of states created by your agent (from whenever the counter is most recently reset). The other will count the number Alpha-Beta cutoffs (also from whenever this counter is most recently reset). The counters will be "instance variables" accessed from "self" and not class variables, which would shared by all instances and thus possibly not give accurate, per-agent results.

You'll need to be able to turn Alpha-Beta pruning on or off, so that you can compare the results of searches using it vs. not using it. The way to expose this choice is to implement a method in your agent called useAlphaBetaPruning(prune=False) This method should not only turn on or off the Alpha-Beta pruning but it should also reset both the counters for states created and for Alpha-Beta cutoffs to 0. The Alpha-Beta pruning counter should be incremented by your agent code whenever a cutoff is found. In order to make the values of these counters available to an autograder, you should also implement a method statesAndCutoffsCounts() that returns a tuple containing the current count of states created and the current count of cutoffs. Note that this call should NOT reset the counters but simply read and return their values.

Your agent for DSBG should also provide a method setMaxPly(maxply=-1). This will be used by an autograder to set a specific limit on the depth of your agent's searches, so that a specific best move can be defined. Note that a maxPly value of -1 means no limit is forced. Your own code may employ a depth limit as part of an iterative-deepening strategy during normal competitive play.

Another method your agent should support is useSpecialStaticEval(func). Normally, your agent should use a static evaluation function that you design and provide as part of your agent. In order to test the correctness of your Minimax and Alpha-Beta implementations the staff will call this function with a specific static evaluation function that they use in order to set up a standard test environment for your search algorithms. Then your search algorithms should use this function until called again with None as the value of the function. Then your agent should revert to using your own static evaluation function.

Your DSBG agent should expose a static evaluation method staticEval(someState) that will take any state and return a real number, based on whatever static evaluation method you design as part of your agent. This value should be positive when the state is relatively good for the maximizing player (white) and negative when relatively good for the minimizing player (red).

Your second agent should play Stochastic Simplified Backgammon (SSBG). Instead of Minimax search and Alpha-Beta pruning, it should use Expectiminimax search. In order to allow testing this under standardized conditions, the agent should do two things that your DSBG agent does and one new thing. The old things are: it should respect the setMaxPly calls, and it should respect the useSpecialStaticEval calls. The new thing is it should expose the following switch to set equal probabilities for the 36 possible dice-throw outcomes: useUniformDistribution. If your agent just assumes the uniform distribution then your implementation of this method can simply "pass" and not do anything. Otherwise, it should set up a uniform distribution. This affects the results of an expectimizing step in the search algorithm, and it can affect the choice of best move.

There are two ways to run a game: with the GUI or with only ASCII graphics. The GUI makes things look colorful and prettier in general, but if you have any trouble installing pygame, which the GUI needs, you can fall back to the ASCII graphics option.

With GUI: Use client.py. This is the main file that runs a game between two agents. Before running client.py you need to install a package known as pygame. For a typical Python installation, you can get pygame by executing the following command-line command.

pip3 install pygame

After you have pygame installed, you can run a full game with the imported agents from your agents/ directory. If you want to run one of your own agents (SSBG or DSBG) you need to change one of the players to be your BackgammonPlayer. If you run SSBG, make sure to change the value of DETERMINISTIC to False. Then to run a game enter

python3 client.py

Without GUI: If you are having problems with installing pygame or cannot get the GUI to work, you still can finish this assignment. In a command line window, simply run

bash run.sh

If you want to run one of your own agents (SSBG or DSBG) you need to change one of the players to be your BackgammonPlayer. If you run SSBG, make sure to change the value of DETERMINISTIC to False.

Each of your Python files should begin with a multiline string that gives, on the first line, your name(s) and UWNetID(s). It should identify the file (name and purpose), and explain if it is a modified version of starter code in CSE 415 or is a new file you created from scratch.

Follow reasonable commenting practice in your code.

You'll be turning in a "report" for this assignment in addition to your code (see below). The report should contain the following sections:

Partner 1 name (last name alphabetically earlier than Partner 2's)
Partner 2 name (last name alphabetically later than Partner 1's)

"Assignment 3 for CSE 415, Winter 2021, University of Washington"

Deterministic Simplified Backgammon Agent
  Who did what for this agent (not required if working alone).
  How the static evaluation function works.
  Any special considerations for Alpha-Beta pruning, such as
    ordering of successors best-first.
  Other comments on the implementation.

Stochastic Simplified Backgammon Agent
  Who did what for this agent (not required if working alone).
  Other comments on the implementation.

Partnership retrospective (required for the partnership bonus).
  What issues you faced or didn't face related to the
    partnership.
  Lessons you learned as a result of working in this
    partnership -- Partner 1. (Give Partner 1's name and
    2 to 10 lines describing AT LEAST ONE lesson.)
  Lessons you learned as a result of working in this
    partnership -- Partner 1. (Give Partner 2's name and
    2 to 10 lines describing AT LEAST ONE lesson.)

Optional additional comments. (Comparing the versions,
  insights on the games, or on the agents, for example).

Submit the following files to GradeScope.

backgammon_dsbg.py
backgammon_ssbg.py
A3-Report.pdf

backgammon_dsbg.py
partnership.txt

The staff is planning to autograde parts of your code. To do this, it is likely that your files will be imported as modules by the autograder. Your agent should not automatically start running when the agent module is imported.

The autograder provided in Gradescope will evaluate your code based on values returned for different test cases (you can find a couple in testStates.py) from your static evaluation function. When you submit on Gradescope, the first line prints out the values returned by your static evaluation function in the following order:[RED_TO_BEAR_OFF,WHITE_TO_BEAR_OFF,WHITE_HIT_FROM_BAR, RED_HIT_FROM_BAR, WHITE_ABOUT_TO_WIN] (You do not have access to all these states in testStates.py).

Make sure you return unique and reflective values. In order to get full credit these values must be in increasing order (and the increase is significant) as these test cases are getting better and better for the white checker. The difference between the last test case (WHITE_ABOUT_TO_WIN) and the rest of the test cases should be large enough, as that state is the best state to be in for the white checkers.

Furthermore, in order to check that your Alpha-Beta pruning is actually working, we check the number of states explored as well as the number of cutoffs made.

For full credit, your Alpha-Beta should be exploring less than 0.8 * number of states explored by minimax.

The code you submit for this assignment must be written by you and your partner. Code copied or "borrowed" from the web or from other students is not permitted. The staff makes spot checks for violations, and when found, these are reported to the administration.

The first backgammon game image is courtesy of Microsoft. The second backgammon game image is courtesy of the Mola family. The GUI was written by Alex Zhou with input from Amir Mola and Steve Tanimoto.

If necessary, updates and corrections will be posted here and/or mentioned in class or in ED.