Project_Overview

Tetris (https://en.wikipedia.org/wiki/Tetris) 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.

There are some animations in the link above, but basically the game consists of a narrow 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 rows, those rows are removed, with all blocks above shifting downward by 1 unit. 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 almost 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 interface instead. 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 .

Additional Library: JavaFX

The user interface for our custom version of the game was developed with a technology called JavaFX, that is unfortunately no longer distributed as a standard part of the JDK. As a result, we need to download the JavaFX library (currently branded as Gluon) within Eclipse before we get started.

Go to the JavaFX download (https://gluonhq.com/products/javafx/) page and scroll down to the Latest Release section. Find the SDK version 13 for your operating system, and click the associated Download link. Extract this archive into a location, similar to where you installed the JDK (see Install Java page in Canvas).

In Eclipse, select Preferences | Java | Build Path | User Libraries and click the New button. Name the library JavaFX13 and click OK, then click Add External JARs to browse to the installation location, and then into its lib subdirectory. Select all 8 jar files from this subdirectory, and click OK, then Apply and Close. This will allow you to add JavaFX13 as a library to any Eclipse project.

Downloads

tetris5044.jar library file containing all the compiled game engine classes tetris5044-api.jar library file containing the Javadocs for the game engine Launcher.java class file with main() method used to run the application

Setting up Eclipse

Download all the files from the links above to your computer, placing them in any convenient folder. Your

Eclipse workspace is fine, as long as its not within any project folder. Open Eclipse and create a new Java Project for this assignment. Do NOT create the module-info file, if prompted. If you accidentally created it, or youre not prompted just please be sure to delete it now.

Right-click the project and select Build Path | Configure Build Path, then select the Libraries tab. Select Classpath then 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 in the Classpath section (along with the JRE System Library in the Modulepath section).

Now click the little triangle to expand the new library, select the node called 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 the _{tetris5044-api.jar} file, and click the Validate button. It should tell you the location is likely valid so click OK, then OK, to get back to the Libraries tab.

Now select Classpath again, and click the Add Library button, select JUnit, then select JUnit version 4 (this version is not the default!) and Finish. Select Classpath once again, and click Add Library as before. This time select User Library and click Next, then check the JavaFX13 library and click Finish.

Ensure you see all these libraries now:

Modulepath

JRE System Library [JavaSE-12]

tetris5044.jar

Javadoc location: [path to tetris5044-api.jar]

JavaFX13

JUnit 4

Note that its perfectly fine if these appear in a different order within each category, as long as theyre all listed in the correct categories. Click Apply and Close to accept this build path and return to your project.

Right-click your project name, select New | Source Folder, and name it test and then add a New | Java Package called edu.vt.cs5044 to both source folders (src and test).

Finally, import the Launcher.java file into the edu.vt.cs5044 package of your src source folder.

Shall We Play a Game?

At this point, you can right-click the Launcher file, and select the Run As | Java Application to play Tetris! Go ahead and try this now, to see the game in action

A game window should appear with an empty game board and a prompt to type P to play. (For macOS only: if the application appears to launch but the game window doesnt appear, please see Piazza @134.) 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.

You can type ? into the game (click the game screen before doing so, to ensure the game receives the keystroke) 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 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.

Try actually typing Ctrl-P into the game window. Nothing will happen within the game itself, whether youre in the middle of a game or not. However, you should see a text warning in the console that your implementation couldnt be found, which is perfectly understandable at this point.

Back To Work

Close the game for a moment now, while we get to our coding tasks for a while. First, right-click the edu.vt.cs5044 package of the src source folder, and 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 then enter the class name as _TetrisAI and 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 _AI interface. 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, and 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 null move (which is invalid) 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 successfully found our AI, and seems to be communicating with it. Close the game again, so we can code a little more.

Not Very Deep Thoughts

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 might complain that it doesnt know about the Placement and Rotation classes yet; if so double-click to import these classes from the edu.vt.cs5044.tetris 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.

Read All About It

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.

Browse through the Javadocs, to get familiar with the interface, and the classes youll be using to implement it. For example, click the findBestPlacement() method of the interface, and youll see it actually provides a brief outline of a strategy we can use. 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 new 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 (https://en.wikipedia.org/wiki/Heuristic) 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 anything approaching a best placement? Now is probably a good time to look at those other methods youll need to implement in the _AI interface. Costs and Bene ts

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 methods 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, only then will it be 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 Limitations

Luck in the form of randomness 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. The same strategies that do very well in some games may do very poorly in others. 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 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 should place exactly 62.5 pieces, averaged over the four provided TEST sequences. Standards of Learning

Can we do better? Sure! As a start, reasonable weight ranges for the selected factors will be 0 through 9. 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 modes.

To earn full credit, your AI must be able to place at least 125 pieces, averaged across the provided TEST sequences. This is double the performance of setting all weights to 1. To achieve this, manually adjust the weights, in increments of 3, meaning you should use combinations of weight values of 0, 3, 6, and 9, for each of the cost factors. Of all these possible combinations, about 15% will result in an acceptable level of performance, so even just guessing the weights will eventually yield a suitable combination.

Please note that you cant (unless youve completed the optional challenge below) develop a JUnit test to verify the level of performance of your weight combinations. Instead, you must confirm this by manually, by actually running the game in all four TEST modes (using Turbo mode to greatly speed up the process) and making note of the displayed scores for each mode. Fuller 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, with reasonably complex boards, for each interface method. You can satisfy this by creating at least 5 distinct test boards which you will simply share among assertions involving all the test methods. The test boards are expected cover a reasonably wide range of board layouts. Youre also encouraged to generate several simple test boards, to exercise cases like an empty board or an almost empty board. These trivial boards dont count toward your required 5 test cases mentioned above. 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. Your code will be inspected during the human review for redundancies, so be sure to develop helper methods as appropriate.

OPTIONAL: Automating the Automation

This section is presented as a challenge that is purely optional, and will NOT affect your score in any way.

You might have noticed that it got bit tedious to try lots of combination of 0, 3, 6, and 9, 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 on your own, without any user interface at all!

As a challenge, see if you can identify the best combination of 0, 3, 6, and 9 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 new method will need to be exercised by at least one assertion, just to be sure its covered within your own JUnit tests. The best weights among these combinations will place an average of exactly 872 pieces for the TEST sequences. Thats quite an improvement, unless you happened to get very lucky in your trial and error phase!

This process shouldnt take more than a minute or so to run, but of course the time depends on the system on which its running, and the performance efficiency of your code. Once youve found the optimum combination, you can hard-code those values as defaults into your _TetrisAI as the defaults in order to watch them in action. You can just call your own setWeights() method from the constructor. Confirm that this is all working as expected, and that youre definitely placing the expected average number of pieces over the TEST sequences, before the next part of the challenge.

It should then be a fairly simple change to your code to try stepping by 2 instead of stepping by 3. This means you should test combinations of 0, 2, 4, 6, and 8, for every weight (you may safely just ignore 9 in this case). This process takes much longer to run than stepping by 3. You can expect something closer to a couple of minutes, so you might want to println() some intermediate results to ensure everything is going well. If everything is working properly, youll only need to do this once, and youll discover that your newlytuned weights will average over 2,750 pieces placed for the TEST sequences. Thats over 3 times our best score found when stepping by 3, so well call that a definite win!

Still not satisfied? Well, you can always try stepping by 1 instead, meaning all possible weight combinations of 0 through 9. Again its a trivial code change at this point, but note that this process will take even longer to run than stepping by 2, so were likely talking about dozens of minutes, possibly up to an hour or so. Also, were reaching a point of diminishing returns, so this wont be such a dramatic improvement. However, youll still essentially double your high score again, as your newly-optimized AI will possess the astonishing capability of averaging just over 5,500 pieces placed for the TEST sequences! (By the way, to save yourself some processing time, you can just stop the iterations when you reach this goal; theres nothing better to find when stepping by ones.)

Use these optimized weights in your solution, and watch this particular combination in action via the graphical interface. Its quite interesting to compare the variation in results between TEST3 (the worst) and TEST4 (the best) as these scores differ by a factor of 40.

If you make any progress with this OPTIONAL challenge, please share your thoughts about it in Piazza. However, please DONT post your WeightFinder code, or any of your weightings.