X
Black Hole
Workshop

Workshop

Outcomes

At the end of this workshop, you should:

  • Be more familiar with using unit testing to ensure requirements compliance
  • Understand how the Monte Carlo method can be used when developing software
  • Have cemented your knowledge of how arrays can be applied to a given problem

Aim

This workshop's app will be a game called Black Hole. Black Hole is a two-player strategy game where each player starts with 10 tiles numbered 1 through 10. The number on the tiles represent both their values and the order in which they must be placed onto a triangular board. The board has 21 spaces so one space remains uncovered. Once all the tiles have been placed, the tiles that surround the empty space are sucked into the black hole. The objective of the game is to have fewer points sucked into the black hole (so you have the higher overall score remaining on the board) than the other player.

Here is a screenshot of a game in progress:

Screen shot

You can see a demonstration of this game on YouTube.

Timing

In total, this workshop activity should take you around 3-4 hours to complete. The tasks have been divided up into milestones to provide you with bite-sized challenges which can be completed in about an hour.

The Board

Representing a triangular game board efficiently in software is somewhat challenging. In our app, we will use an array to store the tiles since it is memory efficient and practical as its size is fixed at 21. We can then use array indexes to refer to these tiles. But some operations are complicated when flattening our 2-D board into a one-dimensional data structure. In particular, it is tricky to determine the neighbors of a given tile. Consider the illustration below:

Board coordinates

Neighbors

How can you determine the neighbors of tile 8?

To facilitate this calculation we will consider the tiles to be organized in rows and columns (as shown above). This rows and columns notation makes it fairly easy to determine that each tile is neighbored by 6 other tiles:

  • on the row above, the tile with the same column number and the tile in the next column to the left
  • on the same row, the tiles to the right and left
  • on the row below, the tile with the same column number and the tile in the next column to the right

This is convenient but will require us to implement some way to convert between array indexes and row/column coordinates (and vice versa).

Tour of Code

Starter Code

You’ll find that again we’ve prepared some starter code to set you off on the right track.

This is made up of four Java classes:

  • MainActivity which is feature complete. It implements:
    • onCreate: instantiates the BlackHoleBoard
    • onClickHandler: this is a single handler for all the game spaces
    • markButtonAsClicked, handleEndOfGame, disableAllButtons and computerTurn: helpers for onClickHandler
    • onReset: handler for the reset button
  • BlackHoleTile: A convenience class to represent the state of a game tile by storing the player that claimed the tile and the value associated with the tile.
  • Coordinates: A convenience class to represent X-Y coordinates (in our case to represent tile locations).
  • BlackHoleBoard is the class that implements the game dynamics and where you will implement the missing code.
    • BlackHoleBoard: Constructor
    • copyBoardState: Copies board state from another board. Usually you would use a copy constructor instead but object allocation is expensive on Android so we'll reuse a board instead.
    • reset: It resets the board!
    • coordsToIndex: Converts from a column and row number to the corresponding array index.
    • indexToCoords: You will need to implement the math to invert the above calculation.
    • getCurrentPlayerValue: Gets the value of the next tile to be placed by the current player.
    • getCurrentPlayer: Gets the number of the current player.
    • gameOver: Determines whether the game is done (all tiles have been placed).
    • pickRandomMove: An unintelligent computer player that just picks a valid move.
    • pickMove: You will implement this to be a smart computer player.
    • setValue: Assigns the next turn (computer or human) to the specified array index.
    • getScore: Computes the final score of the board.
    • getNeighbors: Helper for getScore that finds all the neighbors of a tile.
    • safeGetTile: Gets a tile at the given coordinates but avoids going off the board.

Milestone 1: indexToCoords

After you familiarize yourself with the code, your first step will be to implement BlackHoleBoard.indexToCoords.

Triangular numbers

Wikipedia has an interesting but mathematically-intense article on triangular numbers which is a good read. You'll be particularly interested in the formula for the triangular root of a number.

The formula given in the Wikipedia article will give you the row number that corresponds to the given index. You'll need to do a little math to figure out the column number.

Getting these numbers just right is tricky and hard to test with the app so we'll be using some unit testing to verify your code. Take a look at BlackHoleBoardTest.java and run testIndexToCoords until it passes.

Once all tests pass you are ready to move on to Milestone 2.

Milestone 2: getScore

Your next task will be to implement BlackHoleBoard.getScore. You should loop over the tiles to find the empty one and then use the getNeighbors method to find and add the scores of its neighbors. This is also tricky to test since you have to play the game to the end to verify that it's getting the right solution. So implement BlackHoleBoardTest.testGetScore to verify that getScore returns the correct value for at least a couple of board configurations. This will also be a handy place to add more tests if you find a configuration that doesn't give the expected result in the future.

Stop and Check

At this point, you should have a working game with a poor computer player so try playing a few rounds of the game. This is also a good time to try to spot any bugs which might exist in your code. If you find any, make sure you rectify these before moving on to Milestone 3.

Milestone 3: pickMove

Next up will be implementing a better version of pickMove. It would be great to implement Minimax for the computer to be able to pick the optimum move at each turn, but the time needed for that exhaustive search is too much for a good user experience. Instead we will use the Monte Carlo method to find a good move for the computer:

  • create a new BlackHoleBoard object that's a copy of the current game
  • randomly pick moves for the computer and user to take until the game is over
  • store the resulting score in a HashMap that maps from the first move taken to a list of all final scores reached from that first move

Repeat the above steps NUM_GAMES_TO_SIMULATE times and analyze the content of the HashMap to determine the first move with the best average outcome.

Return that first move. Then play a little more to see how well the computer now does.

Extensions

  • Implement a hybrid of Monte Carlo and Minimax: when the game gets close to the end, evaluate all options instead of using randomness. Experiment with performance to determine how far from the end you can reasonably change your search strategy.
  • Create an animation to represent the tiles being sucked into the black hole at the end of the game (like in the video)
  • Create a 3-player version of the game. Expand the board to have one more row (28 tiles in total) and have each player place 9 tiles before declaring a winner. It is up to you whether to have two computer players or two human players.

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.