Home  |   Notes  |   Homework  |   Labs  |   Programs
Program 4: Tetris Brain

Due midnight the evening of 10/26

Goal

 
Learning Objectives
  •  Exposure to interfaces
  •  Exposure to using library classes
  •  Exposure to stepwise refinement
  •  Familiarity with control constructs
  •  Familiarity with writing test cases
  •  Familiarity with loops
  •  Mastery of the Web-CAT Grader

    • In your fourth programming assignment, you will be writing the core features of a computerized Tetris player. For us old-timers who grew up before the popularization of Quake and Half Life, Tetris was one of the coolest things around. Try playing it for 27 hours and see if you don't agree. If you play Tetris enough, you may begin to have Tetris dreams.

    If you have never played Tetris before, you should try it. Download this tetris.jar file. Then, from the command line (in the directory where you have saved this jar file), you can try: 

    java -jar tetris.jar

    Play is simple. Use the keyboard to move and rotate each piece as it falls. Once a horizontal row is completely filled with blocks, it will be erased to make more room. You continue to play until blocks build up too deeply. The basic controls for this version of Tetris are:

    Keyboard   Command   Keypad  
    j move left 4
    k rotate 5
    l (little L) move right 6
    n drop 0 (zero)

    If you want more information, just google "tetris".

    The Tetris Architecture

    This program assignment involves writing the "AI" for a computerized Tetris player using classes from an existing Java implementation of Tetris. The Tetris implementation we are using consists of four classes and one interface, all located in the cs1705.tetris package:

    These Tetris classes provide a framework for a complete Tetris application. Writing your own "brain" AI code turns out to be surprisingly easy, and fun too! The JTetris GUI allows you to play Tetris yourself, or load in your own brain class to see how it plays on its own. The remainder of the Tetris classes require a bit more experience to implement, so we won't be doing that in this assignment. At the same time, however, they provide a good example of how one can dividing a rather large and difficult problem, like implementing Tetris, into several classes that cooperate to solve the whole thing, and that can be implemented and tested separately.

    The Brain Interface

    You will be implementing a Tetris brain. All brains must provide a common set of features, that are defined by the Brain interface: 

    public interface Brain
{
    public void bestMove( Board board,
                          Piece piece,
                          int   heightLmit,
                          Move  move );
}

    You can call your brain class anything you want, but it must implement the Brain interface, like this:

    import cs1705.tetris.*;

public class NoBrainer
    implements Brain
{
    public void bestMove( Board board,
                          Piece piece,
                          int   heightLimit,
                          Move  move )
    {
        // ... some code here to chose the right move ...
    }
}

    All a brain really needs to do is provide one method to choose the "best move", given the current state of the board and the current piece that is falling. Before we look at brains in more detail, lets look at the core classes that brains have to deal with in order to do their job.

    The Piece Class

    There are seven pieces in standard Tetris.

    The "T"
    The Square
    The Stick, or
    The Long Skinny One
    The L, or
    The Periscope
    (Left and Right Isomers)
    The Dog
    (Left and Right Isomers)

    Each standard piece is composed of four blocks. The two "L" and "dog" pieces are mirror images of each other, but we'll just think of them as similar but distinct pieces. A chemist might say that they where "isomers" or more accurately "enantiomers" (Not that I actually know that word--I looked it up to make the handout more impressive).

    A piece can be rotated 90° counter-clockwise to yield another piece. Enough rotations get you back to the original piece--for example rotating a dog twice brings you back to the original state. Essentially, each Tetris piece belongs to a family of between one and four distinct rotations. The square has one, the dogs have two, and the L's have four. For example, here are the four rotations (going counter-clockwise) of the left hand L:

    Our abstraction will be that a Piece object represents a single Tetris piece in a single rotation, so the above diagram shows four different piece objects.

    Each piece is defined by a number of blocks known as its "body". The body is represented by the (x, y) coordinates of its blocks, with the origin in the lower-left corner.

    So the body of this piece is defined by the (x, y) points :  (0, 0), (1, 0), (1, 1), (2, 1).

    The Piece class and the Board class (below) both measure things in this way--block by block with the origin in the lower-left corner. As a design decision, the Piece and Board classes do not know about pixels--they measure everything block by block. Or put another way, all the knowledge of pixels is isolated in the JTetris class.

    Each piece responds to messages like getWidth(), getHeight(), and getBody() that allow the client to see the state of the piece. Fortunately, our brain code won't need to worry about the individual bodies of particular pieces (if you are an advanced student and are comfortable using arrays, feel free to browse the Piece documentation on-line).

    To allow the client to access the various piece rotations that are available, the Piece class provides a nextRotation() method. Starting with any piece, the nextRotation() message returns the "next" piece object that represents the next counter-clockwise rotation of the piece receiving the message. Enough calls to nextRotation() gets the caller back to the original piece.

    The Board Class

    An instance of the Board class stores the state of the 2-dimensional Tetris board. The client uses the place() message to add the blocks of a piece into the board. Once the blocks are in the board, they are not connected to each other as a piece any more; they are just 4 adjacent blocks that will eventually get separated by row-clearing. The two basic methods provided by Board to modify its contents are:

    Board also provides many methods that allow the client to look at a Board's state.

    Board Undo

    The Board also supports a 1-deep undo() facility that allows the client to undo the most recent placement and/or row clearing. The undo facility is rather limited--the client can do a single place() and a single clearRows(), and then use undo() to return to the original state. Although simple, the undo facility is fast. It turns out that a useful Brain needs exactly this facility of a simple but fast undo. Here's how undo works...

    Incidentally, there is also a commit() operation that marks the current state as the new committed state, but Brains never call it. Instead, that is how the JTetris class moves the game inexorably forward.

    The Move Class

    Brains need an easy way to talk about what move they want to make, and that role is filled by the Move class. Each time a new piece appears on the board, the brain is asked what move it would like to make--that is, what final position does the brain want to steer the piece toward? Brains don't have to worry about the little details of how many times to "press keys", or actually moving the piece one step at a time. Instead, a brain just says where it wants to place the piece when it finally comes to rest, and the remainder of the program takes care of the other details.

    So a Move object represents where a brain wants to place a piece. Conceptually, a Move object holds four related pieces of information: the piece to be placed (which reflects the final rotation, of course), the x and y coordinates on the board where the piece's origin should land, and a score. The score is really a measure of how costly this move will be, with a higher score reflecting a move that will make the board position worse.

    Move objects respond to four accessor messages that let you read the information stored inside:

    Move objects also provide four mutator methods that allow you to change the information stored inside:

    Brain Strategies

    One nice property of the Brain interface is that it completely separates the "brain" work of figuring out what move to make next from everything else that is going on inside the program. When you write a brain class, you do not need to worry about how the board is being maintained, how the animation happens, how pieces are chosen, or anything else. Instead, when you are writing a brain, you only need to be concerned about one thing: given the current board and the current piece, where do you want that piece to end up?

    When you first start JTetris, it already has a brain loaded called the LameBrain. This brain is a truly bad player that simply lets pieces drop right where they fall. You can watch it in action by starting JTetris. Before starting the game, click the "Brain active" check box before clicking the "Start" button, and then watch this AI play by itself. When letting a brain play automatically, you can turn up the speed slider to move things along, and also uncheck the "Animate fall" if you want even more speed.

    The LameBrain class is implemented like this: 

    import cs1705.tetris.*;

public class LameBrain
    implements Brain
{

    public void bestMove( Board board,
                          Piece piece,
                          int   heightLimit,
                          Move  move )
    {
        // Leave the piece unrotated
        move.setPiece( piece );

        // Set the goal column to be the middle of the board
        move.setX( ( board.getWidth() - piece.getWidth() ) / 2 );

        // Set the goal row to be the bottom row
        move.setY( 0 );

        // Make up a score for this move (lower scores are better)
        move.setScore( 100000.0 );
    }
}

    When the brain is activated, the given brain's bestMove() method will be called once each time a new piece appears on the board. The brain computes a "move" which identifies the desired final position and rotation for the given piece, along with an estimate of the "cost" of this move (higher scores make the board worse for the player).

    It's pretty easy to write better brain logic, and that is your goal in this assignment. Here are some suggestions for building a better brain (or don't look at these if you want to puzzle it out yourself):

    Implementing a Brain

    After creating a BlueJ project to hold your solution, you need to make sure the tetris.jar resources are available in your project. Close BlueJ, and then use your preferred folder navigation tool (maybe Windows Explorer) to navigate to the folder for your new project. Within the BlueJ project folder, create a new folder called +libs (yes, the folder name starts with a plus sign). Then copy the tetris.jar file into this +libs folder. The next time you open the project in BlueJ, all of the cs1705.tetris classes will be available to you. Note that this only makes the given jar file resources available in this project, rather than in all BlueJ projects.

    After re-opening your project in BlueJ, you may wish to start by creating a brand new class. Use a name of your choice and just enter the LameBrain implementation of bestMove(). Compile your class, and then try it out. You can run the Tetris game from within BlueJ by adding this method to your brain: 

        public static void play()
    {
        JTetris.main( null );
    }

    This method is just a simple tool to start up JTetris within BlueJ, rather than from the command line. It is a static method, which means you do not have to have a brain object on the object bench in order to invoke it. Instead, after compiling your class, you can just right-click on your brain class and select play() from the menu to start up the game. [Note: be sure to comment this method out before submitting your solution to Web-CAT, since you won't want to be responsible for writing test cases for it!]

    Once the program has started, type the name of your brain class into the text box on the right and click the "Load Brain" button. Check the "Brain active" button before starting the game, and then watch your new creation play for itself.

    Now you are ready to branch out and set up your own brain logic. One useful strategy is to use stepwise refinement, which means breaking up the top-level problem into more manageable pieces that can be solved separately. If these problems are still too big, you can take each in turn and subdivide it further, repeating the process until you drill down to problems that are small enough to tackle easily.

    One good way to divide the top-level problem of finding the "best move" is to break it into two pieces. First, imagine that you had some magic formula that could tell you the "value" or "strength" of a given board position. Then you could take the given board and the current piece, and try dropping that piece in every possible orientation and every possible column position to see where it lands. By "scoring" the resulting board for each rotation/position combination, you can find the best-scoring result, and choose that as your best move.

    Of course, if you just start writing such a method blindly, you may end up with a result that is longer than you intended. A good way to break it up might be to create an outer loop (repeated for all rotations of the current piece) in one method--say, the bestMove() method--but then place the inner loop (try this rotation for all column positions) in a private support method. This support method also can be broken into smaller pieces if you desire. That might look something like this: 

        public void bestMove( Board board,
                          Piece piece,
                          int   heightLimit,
                          Move  move )
    {
        // First, pick a really enormous default score that at least
        // one move will be better than (1e20 is scientific notation
        // for 1.0 x 10^20)
        move.setScore( 1e20 );
        int rotationCount = 0;
        while ( rotationCount < piece.numRotations() )
        {
            // For this rotation of the piece, try to drop it from every
            // possible column and see which result scores the best
            tryAllColumns( board, piece, heightLimit, move );
            piece = piece.nextRotation();
            ++rotationCount;
        }
    }


    public void tryAllColumns( Board board,
                          Piece piece,
                          int   heightLimit,
                          Move  move )
    {
        int column = 0;
        while ( column < board.getWidth() - piece.getWidth() + 1 )
        {
            // drop piece in the current column (you can use a combination
            // of board.rowAfterDrop() followed by board.place())

            // clear any rows that were filled in by dropping the piece

            // compute the score of the resulting board state

            if ( thisScore < move.score() )
            {
                // This is the best move so far, so remember it
                move.setPiece( piece );
                move.setX( column );
                move.setY( /* what goes here? */ );
                move.setScore( thisScore );
            }

            // revert back to original situation for next try
            board.undo();
            ++column;
        }
    }

    Besides the Board methods listed in the method outline above (rowAfterDrop(), place(), clearRows(), and undo()), several methods provided by Piece also may be useful in writing this code:

    The second piece of this solution strategy would be some method for scoring a given board configuration so that you can compare alternative board arrangements to decide which is better. For example, you might consider adding a method like this to your class: 

        public double rateBoard( Board board )
    {
        // place your scoring code in here
    }

    At this point, it might be a good idea to just put a temporary placeholder in for the rateBoard() method--say, by making its body simply return a constant value, like "100.0". That at least will allow you to work on compiling and trying out your logic for searching through all possible moves.

    If you complete and try out a brain after you've reached this point, you'll notice that it still isn't very smart. The first step--setting up a search through all possible moves to find the best-scoring one--is a useful step, but by itself, it is just a brute-force search. Instead, all the "real" smarts comes from the scoring method, which you need to design on your own.

    When you are ready to build a real rateBoard() function, do not try to implement a large, complex strategy all at once. Instead, build it in increments. It helps to think about the elements of your strategy (are you going to count blocks? Count holes? Identify troughs? ...) Think about how you might subdivide the task of computing a complete board score into smaller steps, and then start with one of the smallest and simplest.

    For example, you might choose to start by just counting the number of blocks (more blocks translates into a weaker board position, which means a higher score). In implementing such a rating function, remember that the Board class provides several methods useful in this regard (see the section on this class earlier in this assignment).

    Next, think about the next "increment" you have identified (perhaps counting holes). Think about how to add it to your existing rating method. Is it suitable to separate it into a method of its own? Can it build on the work or results already produced by the prior increment?

    One possible way to organize a board rating method is to devise a main loop that repeats over all columns on the board. For each column, it calls one or more support methods that assess that specific column, and combines the results from each method to some form of running total. Separate support methods could be used to assess different kinds of features that you wish to avoid or reward. Such a method breakdown might look like this: 

        public double rateBoard( Board board )
    {
        int column = 0;
        double rating = 0.0;

        while ( column < board.getWidth() )
        {
            // You can call a support method to assess this column
            // on the board
            double colRating =
                countBlocks( board, column );

            // You can use as many support methods as you need, and
            // combine their ratings together in a way that makes sense
            // (you can add them, average them, multiply them by
            // weighting factors of your own divising, etc.)
            colRating = colRating + ...;

            // Combine individual column ratings into a composite
            // score as we go along (here simple addition is used,
            // but you can combine them any way you wish)
            rating = rating + colRating;

            // Move to next column
            ++column;
        }
    }


    public double countBlocks( Board board, int column )
    {
        // count blocks in this column
    }


    public double penaltyForHoles( Board board, int column )
    {
        // this method is not yet used above--it is just for ideas
        return countHoles( board, column ) * board.getColumnHeight( column );
    }
    Testing Your Brain

    Unlike some previous assignments, there is no single, "right" answer that must be produced by all student brain classes. Instead, you will have to judge the value of your own brain class by how well you think it performs "in action" in real games. Nevertheless, once you get a basic brain functioning, you will notice poor moves that you want it to avoid. Use these as the basis for test cases--with the desired move as the expected outcome.

    In writing test cases, you may find the following Piece methods useful:

    In addition, you might find the following Board methods useful:

    Although we have not discussed arrays yet, we will get to them soon. In the mean time, don't let the appearance of arrays in this Board constructor scare you--it is really just a convenient shorthand to allow us to "write out" board positions in a simple way. For example, consider the following declaration: 

            Board start = new Board( 10, 4, new String[]{
            "          ",
            "          ",
            "          ",
            "#### #####"
        });

    This statement creates a new Board object for a board that is 10 columns wide by 4 rows high. In between the "new String[]{" and the corresponding "}", we can list out a series of strings separated by commas. These strings represent the contents of the board, with space characters representing empty locations and "#" characters representing blocks.

    Thus, the bottom row of this board has 9 out of 10 positions filled with blocks, and the other three rows are completely empty. Of course, this is not a standard-sized Tetris board--the standard board size is 10 cells by 20 cells, with an additional 4 rows on top above the 20-row "height limit", for a total of 10x24 cells.

    It would be unwieldy to write out the explicit contents of all 24 rows in a standard-size board. Fortunately, this special constructor does not require us to write out all the empty rows. Instead, we need only write out the highest row containing a block, and all rows below it. Some examples: 

            Board start1 = new Board( 10, 24, new String[]{
            "#### #####"
        });

        Board start2 = new Board( 10, 24, new String[]{
            "# # # # # ",
            " # # # # #"
        });

        Board start3 = new Board( 10, 24, new String[]{
            "######### ",
            "          ",
            "          "
        });

    Note that the start3 board has row 0 and row 1 completely empty, with all of its blocks on row 2 (remember row numbering starts at zero).

    We can put this constructor to use in creating test cases. As an example, suppose we want to set up a test case where our board has one row filled with blocks except for one single cell. We want to test what our brain will do when a right L piece appears next. We can do it in a test case like this: 

        public void testLonRow0()
    {
        // First, set up the objects to use in this test
        Board board = new Board( 10, 24, new String[]{
            "#### #####"
        });
        Piece piece   = Piece.getPiece( Piece.RIGHT_L, 0 );
        Move  move    = new Move();
        Brain myBrain = new MyBrainClassName();

        // Now call the brain
        myBrain.bestMove( board, piece, 20, move );

        // Now apply the move and test the result
        board.apply( move );

        // This should produce a board like this:
        // |          |
        // |    ###   |
        // |##########|
        // ------------
        // But after clearing the resulting row, we end up with
        // just three blocks that fall to the bottom row.
        assertEquals( board,
                      new Board( 10, 24, new String[]{
                          "    ###   "
                      } ) );
    }

    In your test class, you may choose to move some of these declarations to your test fixture (like the move and brain objects) in order to simplify things. However, this general approach should make it easy to specify both the inputs (in this case, the piece and board state) to your brain, as well as test that the output is what you want. For debugging purposes, you can even print out the contents of a board, a piece, or a move using print() or println()

    Requirements for your Solution

    There are several requirements your solution must follow:

    Now Play Your Own Adversary

    The JTetris program has one more feature that is a cool example of modular code reuse. The GUI control panel has a slider called "Adversary" with a 0..100 range and an initial value 0.

    Internally, JTetris uses a method called pickNextPiece() to select the next piece that will fall from the top. Normally, pickNextPiece() just randomly selects one of the seven basic Tetris pieces. However, if you adjust the Adversary slider toward the right (above zero), it uses a different strategy.

    JTetris will generate a random number between 0 and 100. If that number is greater than the Adversary slider setting, it will choose a piece at random, as usual. However, if the number is less than the current slider setting, it secretly runs all seven pieces through the currently active Brain, generating a "best move" for each. Then, based on the move with the highest score (meaning the worst damage will be done), JTetris drops the worst possible piece instead of a random piece. In effect, the heuristics of the brain are being used to determine which piece will be the hardest for the player to deal with. "Oooh tough break, another dog. Gosh that's too bad. I'm sure the long skinny one will be along real soon."

    For fun, try playing against your own AI. Turn the Adversary slider up as high as you like. Each time a piece is picked at random, the "Ok" status in the control panel will show normally. When the adversary picks the piece, the status will change to "*Ok*".

    This approach works because of the abstraction and the separation between the classes. The Brain interface looks so reasonable. Little does the brain realize the bizarre context where it will be used--just the way modular code is supposed to work.

    It's absolutely vital that once you have the adversary working, you go test it on your roommate or other innocent person. Leave the adversary set to around 40% or so, and leave the speed nice and slow. "Hey Bob, I understand you're pretty good at Tetris. Could you test this for me? It's still pretty slow, so I'm sure you'll have no problem with it."

    For ironic enjoyment, have the brain play the adversary by enabling both at the same time.

    Submit Your Solution

    Program submissions work just like lab submissions. On BlueJ's main menu, click Tools->Submit.... Click on "Browse...", double-click to open the "CS 1705 Programs" folder, and select Program 4. Click "OK". Click "Submit". Click on the link provided in the submission response in order to view the results of the automated phase of program grading.

    If no "Program 4" entry is visible on BlueJ's submission menu, then the Web-CAT Grader is not yet accepting submissions for this assignment. Wait for a message posted to the course web site that submissions are being accepted, and try again.

    If any errors, warnings or suggestions are indicated, you can fix them and resubmit. You are expected to fix all such issues in your code. You may resubmit as many times as you like, up until the deadline. Be careful as the due time approaches--if you submit just over the deadline, a late penalty will be assessed.

     

    copyright © 2003 Virginia Tech, ALL RIGHTS RESERVED
    Last modified: October 22, 2003, 8:49:52 am EDT, by Stephen Edwards <edwards@cs.vt.edu>