Deep Copy and Recursion

  1. 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.


  2. 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.


  3. 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}.


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


  5. 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;
    	}
    }
    


  6. 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);
    }
    


  7. 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?


  8. 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.


  9. Click on the "Project submission" link on the main class page to submit your archive file. If you have any difficulties with the submission server, please e-mail your submission directly to the grader.


Rubrick:

If your code builds and runs on the grader's first attempt and it behaves as described, you will receive full credit (minus any late penalty). If the grader notices any problem, he will notify you by e-mail and give you no credit until you submit working code.

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++;
    		}
    	}
    }