[Solved] Project 3 Play Tetris

Overview

Tetris (Links to an external site.)Links to an external site. was arguably the most popular single-player computer game of all time by the early 1990s. Its incredibly simple and fun to play, and even to this day its widely considered to be among the best games of all time.

In case youve never seen it, the game consists of a 10-unit wide by 24-unit tall well, into which randomly-selected geometric 4-unit pieces begin to fall one at a time. The player manipulates each piece as it falls, by moving it horizontally within the well, and rotating it in 90 increments. Once the piece can fall no further, it becomes locked in place, taking up space in the well. However, if the player forms one or more full horizontal (10-unit by 1-unit) rows, those rows are removed, with all rows above shifting downward. The goal is to continue playing as long as possible, so the player must attempt to pack the pieces strategically. Eventually, though, the well fills upward to a limit line, and if any portion of a piece is locked in place above this line, the game is over.

Youll see all of this in action soon enough, and its actually quite easy to understand once youve played it for just a few minutes.

Requirements

Building a full-functional Tetris application requires a little more Java than what weve covered yet this term, so youll be provided a working application that you can download and play. Its a somewhat simplified version, with a very rudimentary scoring mechanism, but its still just as enjoyable and challenging as the original.

So, if the application is already provided, what is this assignment all about? The goal here is to develop a basic Artificial Intelligence (AI) system, capable of controlling the game as if it were the player.

Implementing an Interface

In previous assignments, you were given a class file with method declarations, Javadoc comments, and placeholder implementations. In this assignment, youll be given an interfaceinstead. An interface contains the method declarations and the Javadoc comments, but no code at all (not even placeholders). Your task is to implement this interface, which means youll develop a class that provides code for all the methods declared in the interface. In addition to the methods specified by the interface, you will likely need to develop several private helper methods in order to fully implement it without redundancies.

System Description

The interface you will implement is called edu.vt.cs5044.tetris.AI and your implementation class must be called edu.vt.cs5044.TetrisAI. You will need to develop the code needed to implement the methods defined by the interface. One of the methods will be the overall AI system. This method receives some parameters, defining the current state of the game board and the shape to be placed, and will need to find the best placement for that shape. The other methods are responsible for intermediate calculations. These methods would normally be private, and not specified by the interface, but for academic purposes were exposing these methods to ease the testing requirements. Speaking of tests, your JUnit test file must be called edu.vt.cs5044.TetrisAITest.

Downloads

tetris5044.jar library file containing all the compiled game engine classestetris5044-api.jar library file containing the Javadocs for the game engine

Setting up Eclipse

Download the provided files to your computer, and place them in a convenient folder. Open Eclipse and create a new Java Project for this assignment. Right-click the project and select Build Path | Configure Build Path, then select the Libraries tab. Click Add External JARs and navigate to where you placed the downloaded JAR files, select tetris5044.jar, and click OK. You should now see that file listed along with the JRE System Library.

Now click the little triangle to expand the new file, select Javadoc location: (None), and click the Edit button. Here be sure to select Javadoc in archive first, then click Browse. Navigate again, this time selecting tetris5044-api.jar, and click Validate. It should tell you the location is likely valid, so click OK, then OK, to get back to the Libraries tab.

Now click the Add Libraries button, select JUnit, then select JUnit version 4 (this is not the default!). Click Finish and ensure you see three libraries now: JRE System Library, JUnit 4, and tetris5044.jar. Click Apply and Close to return to your project.

Finally, right-click your project name, select New | Source Folder, and name it test then right-click the new test folder and add a New | Java Package called edu.vt.cs5044 where you will eventually develop your test class.

Shall We Play a Game? (better than tic-tac-toe)

At this point, you can right-click your project and select Run As | Java Application to play Tetris! Go ahead and try it now

A window should appear with an empty game board and a prompt to type P to play. Once you type P, you will see a new random piece near the top, slowly falling toward the bottom of the well. There are several alternative keyboard controls you can use, but for now just type J and L to move the piece left and right, and type I to rotate the piece. Once the piece is situated as you wish, you can use K (or the space bar) to drop the piece immediately, or you can just enjoy watching the piece fall gently into place.

Zombie (brains?)

You can type ? into the game at any time to produce a listing in the Eclipse console of all of the available options and keyboard controls. Try this now. Some of these options will be extremely useful during the assignment. Youll probably notice some interesting options, including a way to enable the Player AI by typing Ctrl-P. When you enable this mode, just before a new shape appears in the game, the AI is asked how to best rotate then position the shape. Go ahead and type Ctrl-P now. Nothing will happen, except youll see a warning in the console that your implementation couldnt be found, which is perfectly understandable at this point.

Trying to Take Over the World (no, not that Brain)

Close the game for a moment now, while we get some of the basics for the code in place. First, create a new package in your src folder called edu.vt.cs5044 then right-click within that package select New Class.

Before you enter the class name, click the Add button to the right of the Interfaces section. In the search box at the top, type AI and you should soon see the AI interface (in the edu.vt.cs5044.tetris package) selected. Click Ok to add that interface. For now, un-check the option to create Inherited abstract methods (if checked) and enter the class name as TetrisAI then click Finish.

Notice that the new file declaration says public class TetrisAI implements AI. This is what tells Java that we intend to be compatible with any system that can work with the AIinterface. Youll also notice Eclipse is already showing an error on the class declaration line. Click the tiny red X in the margin and double-click Add unimplemented methods from the pop-up. This asks Eclipse to generate all the method placeholders for you! (The option you un-checked earlier would have done the same thing; this way youre able to see exactly what its doing.) Save the file, and check out your new code. Its already compatible with the game system, even though all it does is return placeholders. Thats not very useful, of course, but its actually plenty to get started. Lets see if its recognized by the game engine.

Launch the application again, type Ctrl-P to activate the Player AI, and confirm that the console says the Player AI is now on. If so, go ahead and type P to start the game. Well, thats not very exciting. The console just keeps saying that the AI selected an invalid move for each shape, and we still have to manually place the pieces. Thats fair enough, since all we have are placeholders that Eclipse generated for us, but at least we know the game found our AI and seems to be communicating with it. Close the game again now so we can code a little more.

Lets at least provide a valid suggestion, even if its always exactly the same suggestion. In the findBestPlacement() method, lets replace the placeholder:

return null;

with this:

return new Placement(Rotation.NONE, 0);

Eclipse will complain that it doesnt know about the Rotation class yet, so again click the tiny X in the margin and double-click to import the Rotation class from the edu.vt.cs5044 package. That should resolve the error, so save your file again. This really doesnt seem like much of an improvement, but well try it anyway.

Launch the game and use Ctrl-P then P to check it out. Now its just placing everything against the left edge (column 0) without any rotation, which is still fairly uninteresting. However, its clear that our AI is actually placing the pieces automatically for us! Things can only get better from here. Close the game once youre ready to code again.

Need More Input (accidental AI, maybe)

Obviously we need to examine the shape and the state of the board in order to make some reasonable decisions. Lets take a look at all those Javadocs that make up the API. In your source file click within the word AI of implements AI and type Shift-F2. This should open the Javadocs for the AI interface using an internal browser within Eclipse. You can set it to use an external browser, if you prefer, but this is fine for now.

Reading the Javadocs, click the findBestPlacement() method and youll see it actually provides a brief outline of a strategy. We apparently need to iterate over each possible rotation, and for each rotation we need to iterate over every possible column placement. For each of these, we need ask the Board object to tell us what the result of any hypothetical move would be. Click the method Board.getResultBoard() to see how that works. The Javadocs say that the original board instance is not modified, and well get a new board instance that we can examine.

That will meet our needs, but how do we examine one of these hypothetical results? There are only a few other methods available in the Board class. One provides a human-readable rendering of the board, which might prove very useful to visualize whats happening while debugging, and another promising method seems to let us query any location within the board to see which locations are occupied by fixed blocks.

There are also some static constants that tell us the overall size of the board, plus two constructors. One of the constructors allows us to generate arbitrary board configurations, which is exactly what well need in order to create some nice test cases. Dont forget about TDD!

Click the Package link at the very top of any Javadoc page to see the package overview, then navigate throughout the various pages to see what each class and enum can do, along with the requirements for the interface. A fundamental part of this assignment is to learn how to use Javadocs to explore unknown libraries, as well as to see how a somewhat larger scale system is divided into multiple classes, each with its own purpose.

Note that class Tetris5044 is for internal use only; you wont need it at all. Also, classes RandomMode and ShapeStream are only needed for the optional challenge section below.

Strategy Games

Theres no such thing as a perfect Tetris strategy, so we wont even try. We are necessarily taking the heuristic (Links to an external site.)Links to an external site. approach to this problem, and there will necessarily be trade-offs involved. In every placement decision, there are advantages and disadvantages. How can we hope to find the best placement? Now is probably a good time to look at those other methods in the interface.

Costs and Benefits

From the API, it seems the remaining methods of the interface are related to making some measurements to evaluate a board position. The idea here is that well compute four distinct cost scores, or factors, which tell our system something about how bad (or good) a particular placement might be. Well need to develop those method first, before we can hope to have a working AI system.

Were still focusing on TDD, so start with some fairly straightforward test cases to ensure the individual scoring methods work. Just construct a test board object, then assert the cost score you expect your implementation to compute.

Once all of your individual cost scoring methods are working properly as expected, its time to put it all together. The findBestPlacement() method will need to iterate through all the possible placements, and for each it will combine these individual cost scores in a weighted sum, then choose the lowest cost to return to the game engine. The weightings are important so that certain factors can have more influence on the overall decision than others. At first you can just set all the weights to 1, by simply summing the individual scores together, even though eventually well need to adjust the weights to achieve better results.

Strategic Default

Luck plays a starring role in Tetris. Even with the best of strategies, its critical to recognize that some games simply provide a more fortunate sequence of shapes than others. Thus it can be difficult to objectively judge exactly how good a particular strategy might be. To help with this, our implementation provides a set of 4 repeatable test sequences we can use as a benchmark. The average number of pieces placed from these 4 test sequences will act as a very reasonable metric of how well our strategy is working overall.

Teaching to the Test

Eventually well be making a linear combination of our four scores, which just means we multiply each score by some weight, then add the weighted scores. The equation is very straightforward:

overallCost = weight1*score1 + weight2*score2 + weight3*score3 + weight4*score4

Computing the individual scores really isnt too bad, but what about the weights? As noted above, we can start by simply setting all the weights to 1, and indeed that strategy will place an average of exactly 135 pieces across the four provided test sequences. If your weights are all 1, and your placement average is anything else, you very likely have an issue with either the weights or the algorithm for finding the best weights. You should resolve this before continuing (but please go ahead and read the rest now).

Standards of Learning

Can we do better? Sure! As a start, reasonable weight ranges for the selected factors will be 0 through 15. You can just use trial-and-error if you wish; watch your AI play the test games and try to figure out which factors need more or less emphasis. For example, if your AI is creating too many unnecessary gaps, try to increase the weight of the gap count score. Be sure to use Turbo mode in conjunction with all the Random TEST modes.

Your AI must be able to place at least 175 pieces, on average, across the provided test sequences. Try adjusting your weights in increments of 5, meaning weight values of 0, 5, 10, and 15. Of the 256 possible combinations of 0, 5, 10, and 15 as weights, about 12% will result in this level of performance, so guessing will eventually yield a good combination. You dont need to provide a JUnit test to demonstrate this performance, but Web-CAT will check whether your system meets this minimum or not.

More than Full Coverage

Unlike in the previous assignment, creating JUnit tests to cover all of your code will be very straightforward, since there arent very many branches involved in the solution. You can likely achieve full coverage with just one well-designed test case that asserts something about each method. As a result, complete coverage is not nearly enough to ensure you have correctly implemented your code. Therefore, you must generate at least 5 test cases for each interface method, with non-trivial test boards and non-trivial assertions. You can satisfy this by creating at least 5 distinct test boards to be shared among assertions involving all the test methods. Just be sure the test boards cover a reasonably wide range of board layouts. Note that Web-CAT wont (and cant) enforce this requirement, but the human grader will definitely be looking for this.

Functional Decomposition

Judicious use of helper methods can significantly reduce the overall amount of code you need to develop. For example, you might want to create a helper method that returns the height of one specified column. You can then call that method from within a loop of all columns, and use the return value to help compute some of the cost factors your. Your code will be inspected during the human review for redundancies, so be sure to develop helper methods wherever appropriate.

Automating the Automation (An OPTIONAL Challenge)

You might have noticed that it can get somewhat tedious to try every combination of 0, 5, 10, and 15 for each of the weights, even in Turbo mode. You might have also noticed that youve been given sufficient tools to run entire simulated games without the user interface at all.

As a challenge, see if you can identify the very best combination of 0, 5, 10, and 15 weights, by writing a separate class file called edu.vt.cs5044.WeightFinder with its own main() method. This file will be completely ignored by Web-CAT, and you dont need to generate any tests for it at all. Youll also need to add a public method, such as setWeights(int w1, int w2, int w3, int w4) to your TetrisAI implementation, to apply the various weight combinations. This method will need to be exercised by a single assert, just to be sure its covered within your own JUnit tests. The best weights among these combinations will place an average of over 675 pieces for the test sequences.

Once youve found the optimum combination, youll need to hard-code those values back into your AI implementation as the defaults, in order to watch them in action. Thats quite an improvement, unless you happened to get very lucky in your trial and error phase!

Confirm that this is all working as expected, and that youre definitely placing over 675 pieces on average for the test sequences before the next part of the challenge. It should be a simple change to your code to try stepping by 3 instead of 5 (meaning you should test every combination of 0, 3, 6, 9, 12, and 15 for every weight). This process takes about 5-10 times longer to run than stepping by 5. However, if everything was already working properly, youll only need to do this once, and youll discover that your newly-tuned weights will average over 2,700 pieces placed for the test sequences. Well call that a definite win!

Still not satisfied? You can always try stepping by 1 instead. Again its a trivial code change, but note that this process takes about 50-100 times longer to run than stepping by 3, so were likely talking about a few hours at this point. However, your newly-optimized AI possess the astonishing capability of averaging over 6,750 pieces placed for the test sequences! Its actually over ten times the best average you can achieve when iterating by fives. (By the way, you can stop your iterations when you reach this goal; theres nothing better to find than this when stepping by ones.) You might be somewhat surprised when you discover the optimum weightings. When you watch this particular combination in action, its interesting to compare the variation in results between TEST3 (the worst) and TEST4 (the best).

If you make any progress with this OPTIONAL challenge, please add a brief write-up in the comments of your WeightFinder class, just to let us know what you did, along with any thoughts youd like to share about the experience. Of course you may also discuss this in Piazza, although please dont post your code (or any weightings you find) to the entire class, so as not to spoil the fun for anyone else.

Hopefully you enjoyed this challenge!