Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
Ray Hudson, announcing the 25th January Copa del Rey match involving Real Madrid, said "they are trying to solve the problem that is Barcelona. They might as well try to solve the Hodge Conjecture." This was on GolTV.. en.wikipedia.org/wiki/Ray_Hudson and en.wikipedia.org/wiki/Hodge_conjecture The game is being rerun on U.S. cable tv Wednesday, 8:00 Eastern time. –  Will Jagy Feb 1 '12 at 1:48
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.