Peg Game: best place to place ball such that it lands in the target cell

Question

Source: Facebook Hacker Cup Qualification Round 2011

At the arcade, you can play a simple game where a ball is dropped into the top of the game, from a position of your choosing. There are a number of pegs that the ball will bounce off of as it drops through the game. Whenever the ball hits a peg, it will bounce to the left with probability 0.5 and to the right with probability 0.5. The one exception to this is when it hits a peg on the far left or right side, in which case it always bounces towards the middle.

When the game was first made, the pegs where arranged in a regular grid. However, it's an old game, and now some of the pegs are missing. Your goal in the game is to get the ball to fall out of the bottom of the game in a specific location. Given the arrangement of the game, how can we determine the optimal place to drop the ball, such that the probability of getting it to this specific location is maximized?

The image below shows an example of a game with five rows of five columns. Notice that the top row has five pegs, the next row has four pegs, the next five, and so on. With five columns, there are four choices to drop the ball into (indexed from 0). Note that in this example, there are three pegs missing. The top row is row 0, and the leftmost peg is column 0, so the coordinates of the missing pegs are (1,1), (2,1) and (3,2). In this example, the best place to drop the ball is on the far left, in column 0, which gives a 50% chance that it will end in the goal.

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x
 G

x indicates a peg, . indicates empty space.

Answer 1

Start at the bottom and assign a probability of 1 to the goal and 0 to other slots. Then for the next row up, assign probabilities as follows:

1) if there is no peg, use the probability directly below.
2) for a peg, use the average of the probabilities in the adjacent columns one row down.

This will simply propagate the probabilities to the top where each slot will be assigned the probability of reaching the goal from that slot. No tree, no recursion.

Answer 2

We can solve this problem using probability theory. We drop the ball in a position and recursively split the ball's path in its one (at the sidewall) or two possible directions. At the first step, we know with probability 1 the position of the ball (we are dropping it after all!). At each subsequent split into two directions, the probability halves. If we end up at the bottom row in the target location, we add the probability of path taken to our total. Repeat this process for all starting positions and take the highest probability of reaching the target.

We can improve this algorithm by removing the recursion and processing row-by-row using dynamic programming. Start with the first row set to all 0, except for the starting location which we set to 1. Then calculate the probabilities of reaching each cell in the next row by starting with an array of 0's and. For each cell in our current row, add half its probability to the cell to its left in the next row and half to its right, unless its against the sidewall in which case we add the full probability to the single cell. Continue doing this for each row until reaching the final row.

So far we've neglected the missing pegs. We can take them into account by having three probabilities for each cell: one for each direction the ball is currently travelling. In the end, we sum up all thre as direction doesn't matter.