SameGame is a simple but extremely addictive game in which the idea is to remove all the balls on the screen. Balls can only be removed if they are next to a ball of the same color, in which case that ball is also removed. The more balls that are removed each turn, the higher the score. The precise score is equal to the square of the number of balls you remove.  As balls are removed, the ones above and to the right of them fall down to fill in the gaps. 

 Programming SameGame is a great way to learn a new language that allows event-driven programming and GUI’s (graphical user interfaces).  However, since that is not the main purpose here, your game may use just ASCII characters if you wish.

The goal of this lab is to learn the important lesson that you can program a machine to perform a task better than you yourself could do it.  Just because you supplied all the knowledge and methods to the program, doesn’t mean you can easily predict what the program is going to do.  In this lab, you will pit your own intuition against a program that you create yourself to see, in some way, how well you can compete with yourself!
 

1.  Write a program to let a user play SameGame.

The main data structure in programming SameGame is something to represent the connectivity of the balls.  You will need to find connected components of the same color on this graph, and then update the data structure.  The standard choice for this would be a graph data structure.  The search for connected components should use a depth first, or breadth first search strategy.
 

2.  Add a feature to your program that lets the computer suggest a move.

The Lookahead

Once you get a working version up and running for problem 1, you must add an option for the computer to look ahead and evaluate the best score possible from a given position.  Here is a plan for how the computer will accomplish this.

The computer will generate all possible moves from a given position, and recursively evaluate each one.  Then for each move, it will compute the current score plus the recursively returned value, and return the maximum of these values.  The program should also return which move is associated with that score.  When the board is empty, the function can simply return 0.
 
The problem with this strategy is that the number of possibilities until the board is empty is astronomical, and the machine will never be able to complete the recursion in our lifetime.  In order to handle this, we use a kind of hybrid between depth and breadth first search called iterative depth first search.  With this kind of search, each recursive call is passed a parameter indicating the number of levels searched so far.  When this number reaches some predetermined value (you can experiment with this), the program stops recursing.  Instead of calling itself on all the possible moves, it simply returns an estimate of the best score for that position.  This kind of estimate is called a heuristic.

As each new move is made, the search starts from scratch again from the new position.  At some point, the program will be able to actually reach the empty board, and get precise values instead of an estimate for its look-ahead.

Estimating a Position with Heuristics – The Evaluation Function

In order to choose between moves in this game, a person or computer needs a method of evaluating which resulting position is better than which.  Of course the current score is a big help but using that alone is naïve, because different positions will allow different additional scores.  An evaluation function is a program that evaluates quantitatively an estimate of the score for a given position.  An example of a simple evaluation function for a position in SameGame is to add the current score to the squares of the number of remaining balls of each color.  This naively assumes that we might be able to click and remove all the balls of each remaining color all at once, but at least it is some way to distinguish one position from another which hopefully has some bearing on reality.

This heuristics for your evaluation function will be completely up to you – and you can and should experiment with it.  Our simple example above used the current score plus sum of the squares of all connected color groups, (as if the game could be finished by just clicking on each group simultaneously).  Test your intuition of the game by trying to quantify your own instincts about what makes one position better than another one, and then incorporating your idea into your own evaluation function.

3.  Testing and Experimenting

Play your SameGame all the way through without using any of the computer’s suggestions.  Then play the same game using only the computer’s suggestions.  Then play the game using the computer’s suggestion whenever you feel it might help – that is, let the computer help you if you like.  From different start positions see which method gives the highest overall scores.  Tabulate and analyze your results.