Description

Guidelines for this assignment
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.
Part 0: Getting started
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.
• “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.
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.
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
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.)
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,
,
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.
What to turn in