Numismatics

The questions below are due on Friday May 10, 2019; 05:00:00 PM.

You are not logged in.
If you are a current student, please Log In for full access to this page.

In this problem, we will consider the following game, a mix between Defender and Super Mario Bros:

You are piloting a spaceship in a 2-dimensional world, with coins randomly placed throughout the world. On every timestep, your ship moves one space to the right, and can adjust its vertical position by at most one space. The goal of the game is to collect as many coins as possible before reaching the end of the world.

Information about the world is contained in an input list coin_map that lists the vertical location of a coin in each horizontal space. So for example if coin_map[5] is the value 9, it means that at horizontal space 5, there is a coin at vertical space 9.

Write a function called max_coin_collection which takes in two arguments, an input list describing the world (coin_map, and a starting vertical location starting_y, which specifies your spaceship's beginning vertical position in space 0 at the start. The function max_coin_collection should return a list of spaceship y-dimension locations for every time-step in chronological order that maximize possible coin collection given the world and starting position.

Results will be plotted as shown:

Coins are represented by yellow circles. The spaceship's flight path is traced out in blue (here, the spaceship started at a height of 12). Coins that are successfully grabbed are indicated in green. In this particular case, 15 coins are grabbed before the end of the world is reached. This is the maximum obtainable for this world, and therefore You're Winner.

Hints:

We have imported uniform_cost_search for you from the lib601.search library
What is your goal function in this problem?
What is a good choice of state for this problem? Make sure that, from the information stored in the state, you can compute the child states and test whether the goal condition is satisfied.
Think about what "cost" should be in this problem. What event should have a cost? Importantly, your cost function must assign non-negative costs to each action.
What is the highest vertical position you need to consider? How can you determine this from coin_map and/or starting_y?
Keep in mind that, depending on the maze, there may be more than one path that grabs the maximum number of coins.

Implement max_coin_collection. It may be best to write and test your procedure in IDLE before inputting into the tutor.