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.

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

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:

• backgState.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.
• gameMaster.py: This file can run either type of game: DSBG or SSBG. It is set up in the starter code archive to play DSBG. To change that to SSBG, comment out DETERMINISTIC=True and uncomment the line DETERMINISTIC=False. You can also modify the game master file to import your own agent rather than the default agent.
• BackMan.py: This represents a kind of pseudo-agent for the games. It doesn't actually choose moves to make in the games, but it asks the user to input a couple of numbers, and then it formats those numbers and passes them to the game master. It demonstrates how your agent should interact with the game master program, but it has no artificial intelligence to choose moves.
• testStates.py: This file contains some example states in Simplified Backgammon -- basically either DSBG or SSBG, that you might find useful when testing to see if your agent is following the rules.

For DSBG, your agent should use Minimax search. You should also implement Alpha-Beta pruning for this search. You'll want to define a class for your agent. You can name it whatever you like. 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 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.

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)
Agent file name
"Assignment 3 for CSE 415, Winter 2020, University of Washington"

Deterministic Simplified Backgammon Agent
  Who did what for this agent.
  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.
  Other comments on the implementation.

Partnership retrospective.
  What issues you faced or didn't face related to the
    partnership.
  Any lessons you learned as a result of working in this
    partnership.

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

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.

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.

Here is a list of the files to include in your Canvas turn-in. Do NOT zip up the files, since that will interfere with the grading workflow. (To incentivize compliance on this, the staff will be deducting 2 points, if the files are zipped.)

[uwnetid1]_[uwnetid2]_dbg_agent.py
[uwnetid1]_[uwnetid2]_sbg_agent.py
A3_Report.pdf

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.

Last edited Tuesday, Jan. 21 at 1:35 PM. If necessary, updates and corrections will be posted here and/or mentioned in class or in ED.