Deep Copy and Recursion

This assignment will build on the previous one. In preparation, take some time to clean up your code. If you have superfluous member variables, or member variables in places that don't make sense, they will make this assignment more difficult than is necessary.

Implement a copy constructor for your model class that makes a deep copy. Using a debugger and a little bit of test code, convince yourself that your deep copy actually works as expected. Specifically, make sure the copy looks just like the original, and doesn't reference any of the same objects. Building on top of untested code will almost always result in much greater loss of time than testing your code.

Enumerate the actions that Mario can take. (You can use static final variables, or an enumerated type.) Possible actions are: {run, run_and_jump, run_and_shoot}.

Add member variables to track the number of jumps, fireballs thrown, the number of goombas torched, and Mario's horizontal position.

Add a method to your model named "evaluateAction". A parameter to this method should allow you to specify possible actions. The return value will indicate the estimated value of performing the specified action. This will be a recursive method. Here is some pseudocode. Examine it carefully and ask questions (in class, on the class forum, etc.) if you find it difficult to follow.

double evaluateAction(int action, int depth) {

	// Evaluate the state
	if(depth >= d)
		return marioPos + 20 * deadGoombas - fireballCount - jumpCount;

	// Simulate the action
	Model copy = new Model(this); // uses the copy constructor
	copy.doAction(action);
	copy.update(); // advance simulated time

	// Recurse
	if(depth % k != 0)
	   return copy.evaluateAction(run, depth + 1);
	else {
	   double best = copy.evaluateAction(run, depth + 1);
	   best = Math.max(best,
		   copy.evaluateAction(run_and_jump, depth + 1));
	   best = Math.max(best,
		   copy.evaluateAction(run_and_shoot, depth + 1));
	   return best;
	}
}

Make an AI agent that autonomously plays your game. Add a Controller.update method. Call it just before Model.update is called. In Controller.update, call Model.evaluateAction to evaluate each of the 4 possible actions in simulation. Then, perform the action that yielded the biggest value in simulation. Tune the values of d and k so that it behaves reasonably well. k should be smaller than d. (A good starting point might be d=35, k=6.) Here is some pseudocode:

void update() {
	// Evaluate each possible action
	double score_run = model.evaluateAction(run, 0);
	double score_run_and_jump = model.evaluateAction(run_and_jump, 0);
	double score_run_and_shoot = model.evaluateAction(run_and_shoot, 0);

	// Do the best one
	if(score_run_and_shoot > score_run_and_jump && score_run_and_shoot > score_run)
		do_action(run_and_shoot);
	else if(score_run_and_jump > score_run)
		do_action(run_and_jump);
	else
		do_action(score_run);
}

Ponder the elegance of what you just did. This AI agent works by recursively simulating possible actions, then picks the one that leads to the most desirable future. In theory, this simple approach is sufficient to make optimal decisions in arbitrarily complex situations. (In practice, the number of possible futures grows exponentially, so it is usually necessary to resort to some hackery to limit the computational complexity. That's what the "modulo k" thing was about.) Your AI agent will probably play your game more effectively than you can, and it will automatically adapt if you change the the game. So, how do you feel about AI machines that can surpass the capabilities of their creators?

Make a map that shows off the capabilities of your AI. Make sure it behaves consistently so the grader will see the the same behavior that you saw when you tested your code. If your code doesn't work for him, that is your problem.

FAQ:

Demo. Yours does not have to be this fast or face tubes this challenging.

Q: How does one make a deep copy of a linked list of sprites?
A: You have to write code to do that. Don't use the copy constructor that comes with the LinkedList class--it makes a shallow copies of all the objects Start by adding a copy constructor to your Bird, Tube, and Pie classes. Next, I would add an abstract method named "clone" to my Sprite class, like this:
```
abstract Sprite clone(Model newModel);
```
The Goomba implementation of this method might look like this:
```
Sprite clone(Model newModel)
{
	return new Goomba(this);
}
```
Then, you could copy the linked list like this:
```
this.sprites = new LinkedList<Sprite>();
Iterator<Sprite> it = that.sprites.iterator();
while(it.hasNext()) {
	Sprite s = it.next();
	this.sprites.add(s.clone(this));
}
```

Q: How does one debug a problem in this assignment? Set a breakpoing to stop right after you make a deep copy of the model. Examine the deep copy to make sure it exactly matches the original, but does not reference any of the same objects. If it looks okay, then you will need to systematically debug the problem. To do that, set k to 1 and d to 1 or 2 (so you won't have to deal with an excessive amount of recursion). Next, find a way to reproduce a problem with these parameters. Stop at a breakpoint in Controller.update, immediately before the bird makes a bad decision. For example, flapping when the bird is already very high is a bad decision. Not flapping when the bird is very low is also a bad decision. (You might need to add a frame counter and do a bit of fiddling to get it to stop at exactly the right moment.) Then, step through your code and see why it makes a bad decision at that point.

Q: When I add print statements in my model, it prints values for the real model as well as the hundreds of "fantasy" models, overwhelming me with useless information. How can I print values only in the real model?
A: Example:

class Model
{
	boolean isCopy;
	int frameCount;

	Model()
	{
		isCopy = false;
	}

	Model(Model that)
	{
		isCopy = true;
	}

	void update()
	{
		if(!isCopy)
		{
			System.out.println(Integer.toString(frameCount));
			frameCount++;
		}
	}
}

How do I make a deep copy of a Random object?
A: The Java random number generator provides no mechanism to make a deep copy, so if you use java.util.Random anywhere in your code, stop using it and replace it with this one instead:

class Random {
	long m_a;
	long m_b;

	Random(long seed) {
		setSeed(seed);
	}

	Random(Random that) {
		m_a = that.m_a;
		m_b = that.m_b;
	}

	void setSeed(long seed) {
		m_b = 0xCA535ACA9535ACB2l + seed;
		m_a = 0x6CCF6660A66C35E7l + (seed << 24);
	}

	long nextFullLong() {
		m_a = 0x141F2B69l * (m_a & 0x3ffffffffl) + (m_a >> 32);
		m_b = 0xC2785A6Bl * (m_b & 0x3ffffffffl) + (m_b >> 32);
		return m_a ^ m_b;
	}

	long nextLong(long range) {
		long n = (0xffffffffffffffffl % range) + 1;
		long x;
		do {
			x = nextFullLong();
		} while((x + n) < n);
		return x % range;
	}

	int nextInt(int range) {
		return (int)nextLong((long)range);
	}

	boolean nextBoolean() {
		return (nextLong(2) == 0 ? true : false);
	}
}