Assignment 2: Games and Bayesian Classifiers

CS B551 - Assignment 2: Games and Bayesian Classifiers
This assignment will give you practice with game playing and probability. Please read the instructions below
carefully; we cannot accept any submissions that do not follow the instructions given here. Most importantly:
please start early, and ask questions on Q & A Community or in office hours.
Guidelines for this assignment
Coding requirements. For fairness and efficiency, we use a semi-automatic program to grade your submissions. This means you must write your code carefully so that our program can run your code and understand
its output properly. In particular: 1. You must code this assignment in Python 3, not Python 2. 2. Make
sure to use the program file name we specify. 3. Use the skeleton code we provide, and follow the instructions
in the skeleton code (e.g., to not change the parameters of some functions). 4. You may import standard
Python modules for routines not related to AI, such as basic sorting algorithms and data structures like
queues, as long as they are already installed on the SICE Linux servers. 5. IMPORTANT: In addition
to testing your programs on your own, test your code on silo.sice.indiana.edu using test scripts that we will
provide. We will post more details on the test scripts on Q&A Community.
For each of these problems, you will face some design decisions along the way. Your primary goal is to
write clear code that finds the correct solution in a reasonable amount of time. To do this, you should
give careful thought to the search abstractions, data structures, algorithms, heuristic functions, etc. To
encourage innovation, we will conduct a competition to see which program can solve the hardest problems
in the shortest time, and a small amount of your grade (or extra credit) may be based on your program’s
performance in this competition.
Groups. You’ll work in a group of 1-3 people for this assignment; we’ve already assigned you to a group (see
details below) according to your preferences. You should only submit one copy of the assignment for your
team, through GitHub, as described below. All the people on the team will receive the same grade, except
in unusual circumstances; we will collect feedback about how well your team functioned in order to detect
these circumstances. The requirements for the assignment are the same no matter how many teammates you
have, but we expect that teams with more people will submit answers that are significantly more “polished”
— e.g., better documented code, faster running times, more thorough answers to questions, etc.
Coding style and documentation. We will not explicitly grade based on coding style, but it’s important
that you write your code in a way that we can easily understand it. Please use descriptive variable and
function names, and use comments when needed to help us understand code that is not obvious.
Report. Please put a report describing your assignment in the Readme.md file in your Github repository. For
each problem, please include: (1) a description of how you formulated each problem; (2) a brief description
of how your program works; (3) and discussion of any problems you faced, any assumptions, simplifications,
and/or design decisions you made. These comments are especially important if your code does not work as
well as you would like, since it is a chance to document how much energy and thought you put into your
solution.
Academic integrity. We take academic integrity very seriously. To maintain fairness to all students in
the class and integrity of our grading system, we will prosecute any academic integrity violations that we
discover. Before beginning this assignment, make sure you are familiar with the Academic Integrity policy
of the course, as stated in the Syllabus, and ask us about any doubts or questions you may have. To briefly
summarize, you may discuss the assignment with other people at a high level, e.g. discussing general strategies
to solve the problem, talking about Python syntax and features, etc. You may also consult printed and/or
1
online references, including books, tutorials, etc., but you must cite these materials (e.g. in source code
comments). We expect that you’ll write your own code and not copy anything from anyone else, including
online resources. However, if you do copy something (e.g., a small bit of code that you think is particularly
clever), you have to make it explicitly clear which parts were copied and which parts were your own. You can
do this by putting a very detailed comment in your code, marking the line above which the copying began,
and the line below which the copying ended, and a reference to the source. Any code that is not marked in
this way must be your own, which you personally designed and wrote. You may not share written answers
or code with any other students, nor may you possess code written by another student, either in whole or in
part, regardless of format.
Part 0: Getting started
For this project, we are assigning you to a team. We will let you change these teams in future assignments.
You can find your assigned teammate(s) by logging into IU Github, at http://github.iu.edu/. In the
upper left hand corner of the screen, you should see a pull-down menu. Select cs-b551-fa2021. Then in the
box below, you should see a repository called userid1 -a2, userid1-userid2 -a2, or userid1-userid2-userid3 -a2,
where the other user ID(s) correspond to your teammate(s). Now that you know their userid(s), you can
write them an email at userid@iu.edu.
To get started, clone the github repository:
git clone git@github.iu.edu:cs-b551-fa2021/your-repo-name -a2
If that doesn’t work, instead try:
git clone https://github.iu.edu/cs-b551-fa2021/your-repo-name-a2
where your-repo-name is the one you found on the GitHub website above.
Part 1: Raichu
Raichu is a popular childhood game played on an n × n grid (where n ≥ 8 is an even number) with three
kinds of pieces (Pichus, Pikachus, and Raichus) of two different colors (black and white). Initially the board
starts empty, except for a row of white Pichus on the second row of the board, a row of black Pichus on the
third row of the board, and a row of black Pichus on row n − 2 and a row of black Pikachus on row n − 1:
Two players alternate turns, with White going first.
In any given turn, a player can choose a single piece of their color and move it according to the rules of that
piece.
A Pichu can move in one of two ways:
• one square forward diagonally, if that square is empty.
2
• “jump” over a single Pichu of the opposite color by moving two squares forward diagonally, if that
square is empty. The jumped piece is removed from the board as soon as it is jumped.
For example, for the highlighted Pichu in the following board at left, there are two possible moves, shown in
the right two boards:
Initial board Possible move #1 Possible move #2
A Pikachu can move in one of two ways:
• 1 or 2 squares either forward, left, or right (but not diagonally) to an empty square, as long as all
squares in between are also empty.
• “jump” over a single Pichu/Pikachu of the opposite color by moving 2 or 3 squares forward, left or
right (not diagonally), as long as all of the squares between the Pikachu’s start position and jumped
piece are empty and all the squares between the jumped piece and the ending position are empty. The
jumped piece is removed as soon as it is jumped.
For example, for the highlighted Pikachu in the following board at left, here are some (not all) possible
moves:
Initial board Possible move #1 Possible move #2 Possible move #3
A Raichu is created when a Pichu or Pikachu reaches the opposite side of the board (i.e. when a Black
Pichu or Pikachu reaches row 1 or a white Pichu or Pikachu reaches row n). When this happens, the Pichu
or Pikachu is removed from the board and subsituted with a Raichu. Raichus can move as follows:
• any number of squares forward/backward, left, right or diagonally, to an empty square, as long as all
squares in between are also empty.
• “jump” over a single Pichu/Pikachu/Raichu of the opposite color and landing any number of squares
forward/backward, left, right or diagonally, as long as all of the squares between the Raichu’s start
position and jumped piece are empty and all the squares between the jumped piece and the ending
position are empty. The jumped piece is removed as soon as it is jumped.
3
For example, some (not all) possible moves of the highlighted white Raichu are:
Initial board Possible move #1 Possible move #2 Possible move #3
Note the hierarchy: Pichus can only capture Pichus, Pikachus can capture Pichus or Pikachus, while Raichus
can capture any piece. The winner is the player who first captures all of the other player’s pieces.
Your task is to write a Python program that plays Raichu well. Your program should accept a command
line argument that gives the current state of the board as a string of .’s, w’s, W’s, b’s, B’s, @’s, and $’s, which
indicate which squares have no piece, a white Pichu, a white Pikachu, a black Pichu, a black Pikachu, a
white Raichu and a black Raichu respectively, in row-major order. For example, if n = 8, then the encoding
of the start state of the game would be:
........W.W.W.W..w.w.w.w................b.b.b.b..B.B.B.B........
More precisely, your program will be called with four command line parameters: (1) the value of n, (2) the
current player (w or b), (3) the state of the board, encoded as above, and (4) a time limit in seconds. Your
program should then decide a recommended single move for the given player with the given current board
state, and display the new state of the board after making that move. Displaying multiple lines of output
is fine as long as the last line has the recommended board state. The time limit is the amount of time that
your program should expect to have to make its decision; our testing code will kill your program at that
point, and will use whichever was the last move your program recommended. For example, a sample run of
your program might look like:
[djcran@macbook]$ python3 ./raichu.py 8 w '........W.W.W.W..w.w.w.w................b.b.b.b..B.B.B.B........' 10
Searching for best move for w from board state:
........
W.W.W.W.
.w.w.w.w
........
........
b.b.b.b.
.B.B.B.B
........
Here's what I decided:
..........W.W.W..w.w.w.wW...............b.b.b.b..B.B.B.B........
Your program should work for any reasonable value of n and reasonable time limit, although we plan to test
it only for values of n close to 8 and time limits around 10-30 seconds.
The competitions. To make things more interesting, we will provide a way for your program to play against
other groups’ programs. We will release this code at least 1 week before the deadline. While the majority of
your grade will be on correctness, programming style, quality of answers given in comments, etc., a portion
may be based on how well your code performs against others, with particularly well-performing programs
eligible for prizes including extra credit points.
4
Hint: Since our grading program only looks at the last solution that you output, your program can output
multiple solutions. In other words, you can choose to completely ignore the time parameter passed to your
program and simply output multiple answers until you run out of time and we automatically kill your
program.
Note: Your code must conform with the interface standards mentioned above! The last line of the output
must be the new board in the format given, without any extra characters or empty lines. Also, note that
your program cannot assume that the game will be run in sequence from start to end; given a current board
position on the command line, your code must find a recommended next best move. Your program can write
files to disk to preserve state between runs (although this is not required or necessarily recommended), but
should correctly handle the case when a new board state is presented to your program that is unrelated to
the last state it saw.
Part 2: The Game of Quintris
The game of Quintris will likely seem familiar. It starts off with a blank board. One by one, random pieces
(each consisting of 5 blocks arranged in different shapes) fall from the top of the board to the bottom. As
each piece falls, the player can change the shape by rotating it or flipping it horizontally, and can change its
position by moving it left or right. It stops whenever it hits the ground or another fallen piece. If the piece
completes an entire row, the row disappears and the player receives a point. The goal is for the player to
score as many points before the board fills up.
We’ve prepared a simple implementation of Quintris that you can play from the command line! To try it,
run:
python3 ./quintris.py human animated
To play, use the b and m keys to move the falling piece left and right, the n key to rotate, the h key to flip,
and the space bar to cause the piece to fall. (This works on the SICE Linux machines and should work
on Mac OS command line. It may or may not work on Windows or other platforms because of the way it
handles keyboard input. If it doesn’t work for you, you can use a simpler but less-fun interface by running
python3 ./quintris.py human simple.)
Your goal is to write a computer player for this game that scores as high as possible. We’ve provided a really
simple automatic player that can be run using the command line options computer animated and computer
simple. The code for this is in tetris.py, whereas the other python files contain the “back end” code that
runs the game. You should not modify the other source code files.
We’d recommend starting with the simple version as opposed to the animated version. In the simple version,
your program issues a sequence of commands which are then executed immediately before the piece begins to
fall. This is simpler but prevents your program from making complicated moves (like moving left and right
as the piece falls to try to wedge a piece into an awkward spot in the board). Then, consider the animated
version, which also introduces an implicit time limit (since your decisions have to be made before the piece
reaches the bottom of the board.)
This version of Tetris has one twist which you may want to use to get as high a score as possible: the falling
pieces are not chosen uniformly at random but based on some distribution which your program is not allowed
to know ahead of time. However, it may be able to estimate the distribution as it plays, which may let it
make better decisions over time.
The tournament. To make things more interesting, we will hold a competition among all submitted solutions
to see whose solution can score the highest across several different games. While the majority of your grade
will be on correctness, programming style, quality of answers given in comments, etc., a small portion may
5
be based on how well your code performs in the tournaments, with particularly well-performing programs
eligible for prizes including extra credit points.
Part 3: Truth be Told
Many practical problems involve classifying textual objects — documents, emails, sentences, tweets, etc. —
into two specific categories — spam vs nonspam, important vs unimportant, acceptable vs inappropriate,
etc. Naive Bayes classifiers are often used for such problems. They often use a bag-of-words model, which
means that each object is represented as just an unordered “bag” of words, with no information about the
grammatical structure or order of words in the document. Suppose there are classes A and B. For a given
textual object D consisting of words w1, w2, ..., wn, a Bayesian classifier evaluates decides that D belongs to
A by computing the “odds” and comparing to a threshold,
P(A|w1, w2, ..., wn)
P(B|w1, w2, ..., wn)
> 1,
where P(A|w1, ...wn) is the posterior probability that D is in class A. Using the Naive Bayes assumption,
the odds ratio can be factored into P(A), P(B), and terms of the form P(wi
|A) and P(wi
|B). These are
the parameters of the Naive Bayes model.
As a specific use case for this assignment, we’ve given you a dataset of user-generated reviews. User-generated
reviews are transforming competition in the hospitality industry, because they are valuable for both the guest
and the hotel owner. For the potential guest, it’s a valuable resource during the search for an overnight stay.
For the hotelier, it’s a way to increase visibility and improve customer contact. So it really affects both the
business and guest if people fake the reviews and try to either defame a good hotel or promote a bad one.
Your task is to classify reviews into faked or legitimate, for 20 hotels in Chicago.
We’ve provided skeleton code and a training and testing dataset to get you started. You can run it like this:
python3 ./SeekTruth.py deceptive.train.txt deceptive.test.txt
The code currently does not do anything interesting. Your job is to write a program that estimates the Naive
Bayes parameters from training data (where the correct label is given), and then uses these parameters to
classify the reviews in the testing data.
Hints: Don’t worry, at least at first, about whether the “words” in your model are actually words. Just
treat every unique space-delimited token you encounter as a “word,” even if it’s misspelled, a number, a
punctuation mark, etc. It may be helpful to ignore tokens that do not occur more than a handful of times,
however.