CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2022
The reading for this assignment is
Search
in The Elements of Artificial Intelligence with Python.
Due Wednesday, October 26
at 11:59 PM. This is a partnership assignment and students
may work in partnerships of 2 or work individually. Those in partnerships
are eligible for the optional early-bird and collaboration-retrospective extra credit (5 points).
To qualify, turn in a working version of the first agent (backgammon_dsbg.py must pass all Autograder tests)
and the partnership information file (partnership.txt) by Friday, October 21 at 11:59 PM,
and later include the collaboration retrospective in your final report. Please read section J on
what to submit to Gradescope.
Before turining in your final submission, please make sure that you are able to run a full game with both of your agents.
After the assignment deadline, we will run all of your DSBG agents in a round-robin tournament. The class winner will be awarded
5 extra points on this assignment.
A. Introduction
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.
B. Reading
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.
C. Game Rules
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 former lead TA Amir Mola'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 checker always goes first;
a player can only pass if the player cannot move any checker with that roll;
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.
SkeletonAgent.py & randomAgent.py: These are two default agents that play 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.
backgammon_dsbg.py: edit this file to implement your DSBG agent.
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.
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.
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
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.
E. What to Implement
You should create two agents. One will be able to play DSBG (Minimax + Alpha-Beta Pruning). The other will be able
to play SSBG (Expectimax). 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
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).
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.
In order for gamemaster.py to run a game, it calls on the
move(state, die1=1, die2=6) method to get the move for your agent at each round.
Note that since this is DSBG, the roll of the die is fixed (1 and 6). In this method,
your agent should use Minimax 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.
Now that we have our Minimax implemented, we want to speed up our search. One way to do this is to offer
Alpha-Beta pruning as a feature. Meaning that our agent will be able to run Minimax or Alpha-Beta
pruning in the move(state, die1=1, die2=6) method. 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).
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 be shared by all instances
and thus possibly not give accurate, per-agent results.
useAlphaBetaPruning(prune=False) 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=2).
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. Your own code may employ a depth limit
as part of an iterative-deepening strategy during normal competitive play.
Your second agent should play Stochastic Simplified Backgammon (SSBG).
Instead of Minimax search and Alpha-Beta pruning, it should use Expectiminimax search.
Here are the major differences/similarities between DSBG and SSBG:
SSBG should still implement setMaxPly(maxply=2) and useSpecialStaticEval(func)
as described in DSBG. You are more than welcome to change your staticEval(someState) method
or you can keep the same one as DSBG.
Your move(state, die1, die2) method will implement Expectimax. Note that unlike DSBG
we do not know the roll of the die and therefore, it is determined immediately before gameMaster.py calls on this method.
Please note that in your search, you need to assume the uniform distribution (equal probabilities) for the 36
possible dice-throw outcomes.
Note that in Expectimax we do not have any sort of cutoff or pruning. Therefore, we do not need to implement
useAlphaBetaPruning(prune=False) or statesAndCutoffsCounts() methods.
Be sure to read section J about the Autograder on Gradescope. Before submitting any file to the Autograder, first
make sure that your file runs locally and you are able to play a game (without any errors). If you submit your file to
the autograder and do not see an output or see the following message:
"The Autotrader failed to execute correctly. Contact your course staff for help in debugging this issue.
Make sure to include a link to this page so that they can help you most effectively."
that means that the autograder failed to run your file and you have an error.
F. How to Run a Game
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.
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
If your Python environment is controlled by Conda or Anaconda, or if you
are not sure, click on this
help file.
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
If you want to run one of your own agents (SSBG or DSBG) you need to
change one of the players (in the imports) to be your BackgammonPlayer. If you run
SSBG, make sure to change the value of DETERMINISTIC to False.
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
and then open log.txt to see the game details.
If you want to run one of your own agents (SSBG or DSBG) you need to
change one of the players (in the imports) to be your BackgammonPlayer. If you run
SSBG, make sure to change the value of DETERMINISTIC to False.
G. Commenting your Code
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.
H. Report
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
Partner 2 name
"Assignment 3 for CSE 415, Autumn 2022, University of Washington"
Deterministic Simplified Backgammon Agent
Who did what for this agent (not required if working alone).
How the static evaluation function works. Explain each component in details.
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).
I. What to Turn In
Submit the following files to GradeScope.
If you are submitting for the early-bird option, submit
one GradeScope submission (for the team) that includes
these files:
backgammon_dsbg.py
partnership.txt
The partnership.txt file should include the name and
uwnetid of each partner.
J. Notes about Autograder
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. please do not change or add
any additional import statement to any of the agent files.
Autograder Turn-in:
If you are participating in the Early Bird part of this assignment, please use Assignment 3 Early Bird (DSBG only)
turnin. You will receive 5 points of extra credit, if you get full points on DSBG and are in a partnership of two. Be sure to tag your partner
in your final submission. Then turn in both DSBG and SSBG to Assignment 3 (DSBG + SSBG) when you are done.
If you are not particpating in Early Bird, then use Assignment 3 (DSBG + SSBG). Keep in mind that if you need to submit both files in order
for the autograder to run.
Please note that you can submit multiple times to the Autograder and we will only keep your most recent submission for grading purposes.
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.
Red to Bear Off < White to Bear Off < White Hit From Bar < Red Hit From Bar < White About to Win.
Red to Bear Off < White to Bear Off: because the white to bear off is a better state for the white
checkers and therefore, the static eval needs to return a larger value for it!
White Hit From Bar < Red Hit From Bar: In both of these test cases, the checkers are still bearing
off but one of their checkers gets hit by the opponent. For example, consider how you can arrive at white hit from bar:
There is a single red checker on the bar, but the white checker home base is completely full so the red checker
cannot sit back down. So you start bearing off white checkers and the red checker still cannot sit back down.
In this case, you bear off let's say 3 white checkers, which means that you are at a better stage compared to white to bear off.
However, by luck, the red checker rolls and sits back down and actually hits a single white checker(s). So in other words there are
now white checker(s) on the bar and the bearing has stopped until you can bring back that one white checker to the home base. This case
is better than the white to bear off because you already have some checkers removed but you have also been hit so it is worse than red hit from bar.
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.
K. Academic Integrity
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.
L. Acknowledgements
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.
Updates and Corrections
If necessary, updates and corrections will be posted here and/or mentioned in class or in
ED.