CSE373—Data Structures and Algorithms for Nonmajors

Programming Assignment #1

due: Wednesday, 10/26/05, 10:00 PM

Overview:

This assignment introduces you to some concepts in Artificial Intelligence while letting you practice using lists, iterators, stacks, and queues. The assignment attempts to solve a MineSweeper board using explicit rules and discovered rules, both in a local neighborhood and globally (for the endgame, when the total number of mines remaining beomes significant and the size of the problem becomes tractable.)

An explicit rule, implemented as ZerosMineStrategy, is:

0
	?

The rule is that the middle square can be safely explored, because it’s neighbor says that it has no mines as neighbors.

It has 7 other forms (the zeros in the other neighboring squares).

Another explicit rule, implemented as CountMineStrategy, is:

	m
	2
m		?

The rule is that the bottom-right cannot be a mine, because there are already two mines around the middle square.

The number 2 is generalized to n, and the ? can be in the other corners.

1	m	2
2	4
m	3	?

The same rule applied contrarily. The bottom-right must be a mine, because the only two remaining squares need to be mines for the 4 in the center to be correct.

The number 4 is generalized to n, and the ? can be in the other corners.

More complicated deductions can be made, for example:

0	0	0
1	2	1
	?

The ? has to be empty, because if it were a mine, one of the remaining squares would have to be a mine too (to satisfy the 2). But if one of those other squares were a mine, then the 1-neighboring-mine constraint would be violated.

It becomes impossible to explicitly define and implement all such more complicated rules, so other techniques must be employed instead. The alternative that we will use is to sample the space of possible configurations and see if there are any consistencies. For example, consider

m	3	1
?	?	?

There are 8 combinations for ???: ---, *--, -*-, --*, **-, *-*, -**, ***, of whch only **- and *-* satisfy the constraints. Both of those possibilities have a mine in the first position, but they differ in the locations of the other mine. So we can conclude that there’s a mine in the first position. When we do this same analysis on a larger space (5x5), the total combinations become much larger, so large that we can’t possibly try them all. So instead we try a random percent of them, the idea being that we’re unlikely to get so unlucky that we’ll get a falsely consistent result.

The DeriveRuleStrategy performs such an analysis on 5x5 windows, while the EndGame performs such an analysis on all remaining squares. The other main difference between the two is on the significance of the number of remaining mines. For the former, if there are a lot of remaining mines, the probability of a mine at a given square is independent of any other square. But for the latter, when the amount of mines are few, a mine somewhere could force the existence of a mine nearby, but there may not be a mine available… it’s like counting cards in a cardgame – it becomes most useful at the end.

Programming (70%):

We are giving you several skeleton files, though you will only be adding code to two.

· DrawingPanel.java – simple interface for mostly static graphics (hides AWT/Swing details, has changed from hw0 – needed paintImmediately())

· Scanner.java – a simplification of the Java 1.5 Scanner (only necessary if using 1.4.2)

· MineCell.java – defines the legal values of a single cell.

· MineBoard.java – The state of the board and game is stored and modified in this file. (has changed since hw0 – new constructors and a mine print – add in your methods from hw0)

· MineStrategy.java – interface for the local strategy deciders

· ZerosMineStrategy.java – implements the classic Minesweeper 0 floodfill

· CountMineStrategy.java -- makes a simple counting decision

· DeriveRuleStrategy.java – analyzes random samples to discover complex rules

· GuessWindow.java – windowing code for DeriveRuleStrategy

· MineUI.java – graphics and UI code. (has changed since hw0 – access modifiers)

· SmartMineUI.java – extends MineUI. (Your automation code goes here.)

· EndGame.java – class that computes the endgame analysis (Your endgame code goes here)

Part 1: Automation (35%) [ unofficial recommended checkpoint: 10/19/05 ]

Method	Description
Point removeNext(LinkedList ll)	Returns an item from ll. That item is no longer present in ll. Must mimic the behavior of dequeue() or pop().
void explore(Point bp)	First explores the location bp (likely a message from the UI). Then successively explores and marks neighbors using a sequence of strategies from faster to slower. A location should be tested on a faster strategy before being tested on a slower strategy, and slower strategies should not be used until all locations have been tested on the faster strategies. Invokes the endgame analysis if appropriate. Stops if no more can be deduced from the given information. You may define helper methods. You are encouraged to use existing methods. RECURSION WILL RECEIVE ZERO CREDIT.

The method removeNext should be only a few lines. See the Java API for details on the methods that refer to the front or back of a linked list. As written, you will need to do a cast to Point on the object you get from the list, because get returns an Object. This code is 1.4.2-compliant. If you wish, you can rewrite the code to use 1.5 generics. As long as your code works in 1.5, you will not be graded either way for your choice.

The explore method is more complex, but we’ll build up to it. Let’s start using only one strategy, say strategies[0]. First, declare two LinkedLists, activeList and nextList, and instantiate them (as empty). Then call the parent class’s explore on bp. Add the neighbors of bp to the activeList. We’re going to have a loop that repeats until activeList is empty. It removes the next item from active list, and if that item still can be explored/marked (i.e. is “useful”), then we see if the strategy can decide anything on it. If so, then we call the parent’s explore or [the parent’s] mark, as appropriate. We also add its neighbors to the list, as they now have more information about themselves, and the list continues on.

Now let’s make it more complicated. The ideas behind the multiple strategies for explore are: try faster strategies before slower ones. Exhaust all options for the faster strategies before deferring to the slower ones. Revert back to the faster strategies again when new information is obtained.

We want to try the faster ones first. Conveniently, they are sorted that way in the strategies array. If we have a location where the current strategy cannot make a decision, that location is added to the nextList (in the simplified example, it was just discarded). When the activeList becomes empty, it is swapped with nextList (i.e. the references), and we move onto the next strategy (all locations have been tried on the faster strategy first). Whenever any neighbors are added to the activeList, the strategy is reset to the fastest. When all strategies have been exhausted, the endgame is solved if appropriate (isEndGame returns true), and the method terminates.

You may define helper methods. You are encouraged to use existing methods.

RECURSION WILL RECEIVE ZERO CREDIT.

Part 2: The endgame (35%)

Method	Description
Endgame(MineBoard mb, int numSamples)	Constructs the object, creating appropriate arrays and lists. See the code already there.
analyze(List toExplore, List toMark)	After completion, toExplore will be augmented with locations that are safe to explore, and toMark will be augmented with the locations that are mines to be marked. You will want to define several helper methods; they will closely parallel the code in DeriveRuleMineStrategy.

1	2	1	2	1	2	2	3	2
m	4	m	4	m	4	m	m	m
m	(a)	(b)	(c)	m	4	m	(d)	m

Suppose the endgame configuration is as follows, and there is one mine left. Then that mine must go at (b), and everything else is safe. But if there are three mines left, then (a), (c), and (d) are mines, and (b) is safe. (If there are two mines, then it’s a tossup between b&d and a&c.)

The implementation of the endgame differs from DeriveRuleMineStrategy mainly in that we no longer have locale. A mine being at (a) influences a mine at (d) in the above example, and (d) could have been arbitrarily far away. It will no longer be convenient to use dense 2-d arrays to store information; instead it will need to have lists of locations (Points) along with their associated data.

There are some useful variables and methods already present. relevantAsk assumes that (i,j) is askable and returns true if there is something unknown neighboring it. numNeighborsTrue counts the number of trues neighboring (i,j) – something to compare against ask. The nested class EndGameChoice wraps a Point with a count.

The 2-d array mines should have true at (i,j) if the MineBoard is marked there, and false if (i,j) is askable there. If neither are true, then (i,j), wrapped into an EndGameChoice, should be in the unknowns list. The asks list should contain all askable locations that have passed the relevantAsk filter. This code is 1.4.2-compliant. If you wish, you can rewrite the code to use 1.5 generics. As long as your code works in 1.5, you will not be graded either way for your choice.

Your analyze should first walk through the unknowns, zeroing the count for each item. Then, for numSamples times, it records constrained random distributions of (numMines-numMarked) mines throughout unknowns. To construct a random distribution, the easiest way is to shuffle the order of unknowns (see Collections.shuffle) and, for the first (numMines-numMarked) elements, assign true to appropriate locations in the mines array, and false for the latter elements. Discard all random distributions that do not satisfy the constraints imposed by ask and numNeighborsTrue. For the remaining distributions, increment count if there is a mine at that location. Finally, if count is at a minimum or maximum, add the location to the appropriate list. YOU MUST USE ITERATORS TO RECEIVE FULL CREDIT. Once again, the code should parallel DeriveRuleMineStrategy.

There are three mine files that are included in the zipfile. The first and third can be solved to completion from a single click with the endgame analysis running. The second cannot be solved to completion from a single click near the center.

Short Answer Questions (30%):

Put your answers to the following in a file called questions.txt (you can use Notepad for editing). You will be graded on content, not on spelling or grammar.

1) The method addNeighbors puts items onto the back of a list. If your removeNext operates on the front of the list, are you emulating a stack or queue? If your removeNext operates on the back of the list, are you emulating a stack or queue?

Run explore with removeNext operating on the front of the list. Describe qualitatively the progression of the exploration. Run explore with removeNext operating on the back of the list. Describe qualitatively the progression of the exploration. How do they differ? (Adjust SLEEPTIME if necessary.)

2) Look at GuessWindow.java. In terms of n=size, what is the big-Oh of the runtime of numNeighborsTrue? Of isValidLayout?

3) Why does the mouseClicked method get called from running SmartMineUI, when it resides in MineUI? When mouseClicked calls explore, why does SmartMineUI’s explore get run? How can SmartMineUI’s explore run its parent’s explore?

Bonus (5%):

Put in questions.txt too.

Analyze through experimentation the number of samples needed for calls to DeriveRuleStrategy.decide. Characterize what inputs require more samples.

How much does the performance degrade when windows are increased to 7x7 or 9x9? (Don’t adjust addNeighbors.)

Turn in your work electronically from the “assignments” link on the class webpage.