CIT 591 Lines of Action: Testing for a win
Fall 2005, David Matuszek

One of the tricky parts of this assignment is deciding when the game is over; that is, deciding when all the pieces of one color are in a single group. Here's one way of going about that.

The general idea is this:

1. Start a group. Find any piece (of a given color), and put it in a group by itself.

2. Expand the group. Loop through all the pieces in the group, and for each piece, examine all 8 adjacent squares. For each piece of the same color that you find, if it is not already in the group, add it to the group.

3. Check if you added any pieces. See whether the previous step added any pieces to the group. You can do this by setting a boolean when you add something, or by comparing the size of the group before and after the previous step. If you did add pieces, go back to step 2.

4. Count pieces. Count the total number of pieces (of a given color) still on the board, and compare it to the number of pieces in the group you formed. If the numbers are equal, all the pieces of that color are in the group, and the game is over.

Of course you will want to do this separately for each color.

Notes:

Step 1: An ArrayList, or even better, a Set, is a good data structure to hold a group of pieces. A Set has the advantage that you don't have to check whether a piece is already in it; that happens automatically. The disadvantage of a Set is that we haven't talked about it in class, so you will need to look it up yourself in the API.

Step 2: The easiest way to do this is to set up a pair of nested for loops: One goes from row-1 to row+1, the other from column-1 to column+1. If either index is outside the bounds of the array, just continue (remember that statement?). You don't even need to make a special case for the piece in the center, because it's already in the group and won't be added again.

Step 3: You can see whether the previous step added any pieces to the group by (1) setting a boolean when you add something, or by (2) comparing the size of the group before and after the previous step. Either way, this is best done as another loop around step 2.

Step 4: Don't forget that, whichever side just moved, either side might win. If a move results in both sides having all their pieces in a single group, the player that made the move wins.

We haven't covered recursion in this course, but if you understand recursion, feel free to use it. The recursive solution is simpler.