Soccer and Probability

Question

MOTIVATION: I will quote Wikipedia's article on a soccer goalkeeper for the motivation:

Some goalkeepers have even scored goals. This most commonly occurs where a goalkeeper has rushed up to the opposite end of the pitch to give his team an attacking advantage in numbers. This rush is risky, as it leaves the goalkeeper's goal undefended. As such, it is normally only done late in a game at set-pieces where the consequences of scoring far outweigh those of conceding a further goal, such as for a team trailing in a knock-out tournament.

The mathematical question: Consider the following game (simplified soccer):

A single player starts with a score of 0.5 and plays N turns. In each turn, the player has to choose one of 2 strategies: $(p_{-1},p_0,p_1)$ or $(q_{-1},q_0,q_1)$ (these are probability vectors) and then her score is increased by -1, 0 or 1 according to the probabilites dictated by the chosen strategy. The player wins if at the end of the game she has a positive score, and loses if she has a negative score (the player's objective is to win, the only thing that matters is whether the final score is positive or negative).

What is the optimal global strategy given $N$, $(p_{-1},p_0,p_1)$ and $(q_{-1},q_0,q_1)$?

A global strategy is a function of the number of turns left, the current score and the 2 probability vectors (which are constant for all turns).

If this question is hard, it may still may interesting to approximate an optimal global strategy (in what sense?).

Answer 1

In the case where you know the number of turns in advance, you can construct an optimal strategy in time $O(N^2)$ by reasoning backwards from the last round.

If, before the last turn, you find yourself with score $-0.5$, choose your strategy by comparing $p_1$ to $q_1$. On the other hand, if the score is $0.5$, compare $p_{-1}$ to $q_{-1}$. If the score is anything else, it's too late to make a difference: either you have already won, or already lost.

Now you know the "value" of the game (that is, the probability of eventually winning, given optimal play) after $N-1$ turns, as a function of your score at that time.

Then look at your options before the second-to-last turn. For each possible score you have the option of playing $p$s or $q$s, and each of this will give you a certain probability of eventually winning, which you can easily compute because you already have a table of the probabilities after the turn. The optimal play at each score is, of course, the one that will yield you the best probability of winning.

Continue this backwards until the first turn. What you end up with is a two-dimensional table that tells you, given the number of turns left and your instant score, what your chance of winning is, and whether you should play $p$ or $q$. This table constitutes an optimal strategy.