How can I calculate the relative probability of each move resulting in a win, given historic win/loss data for the possible moves?

Question

We are at a position in a game where there is a decision to be made. As there are relatively few game positions and possible moves, we have collected statistics from previous occasions the game was played and we found ourselves with the identical game position.

For each move, we have recorded if selection eventually led to a win or a loss.

Move     Win    Loss
 A        3      5
 B        2      4
 C        0      0
 D        0      4

My goal is to randomly select a move while proportionally favouring those moves more likely to win. So for each of the possible moves, I would like to calculate the probability that that move is the most-winning one. Let's call these PA, PB, PC and PD. These should sum to 1.

Give the example data above, my intuition says:-

• Move A should be the most favoured, and so PA is the largest of the values.
• Move C has no data. It could be anything between always a loss and always a win. Might need to be treated as a special case as there is nothing from which to calculate?
• Move D appears poor so far. Perhaps this is just sampling luck, and over time we would fnid ourselves with 12 wins and 4 losses. There is still some chance it is really the most winning move.

Now I get a stuck. It's seems as though I should calculate the win ratio for each of the moves and apply some certainty-factor based on the total number of times that option has been selected to come up with distribution representing the likely win ratio for the underlying population. How would I combine these overlapping distributions and reduce them down to probabilities for each move? I'm not sure how I would combine all of these numbers to reach PA, PB, PC and PD. This seems a reminicent of an ANOVA?

In the actual problem there can be between 1 and 7 moves available. I'm assuming any answer can be generalised up to more possible moves. If it makes any difference, the game is not circular; having made a move we can never return to the same position within the game. It could only be reached again in a new game. There are, however, multiple ways to reach the same game position from the start of the game.

Answer 1

The first step is to get the probability of winning conditional on each move. This is simply the proportion win / (win + loss) for each choice. Regarding move C, you can use the overall probability of winning: The game was played 18 times and won 5 times, so you could set its probability of winning to 5/18.

Then the probabilities of winning conditional on move are: A = 3/8, B = 1/3, C = 5/18 and D = 0.

You might want to collect more data on Move D to discover if there is a nonzero probability. Otherwise in your random draws it will never be selected.

Next you want to make the random draws. To construct the distribution for this you simply normalize the above probabilities such that they sum to one. Define x = 3/8 + 1/3 + 5/18 + 0. Then the probability of selecting A = (3/8) / x. The probability of selecting B = (1/3) / x. Etc.

Answer 2

A big problem is that the probability of making a move and the probability of winning after making the move may not be independent. There may actually be only a tiny difference in the quality of the moves, but good players tend to make move A or slightly less often B, while bad players tend to make move D - the players who made move A or B might have done quite well doing move D as well, and the players who made move D might have lost after making move A or B as well.

With move C, it's not as if you have no information. You have the information that in 18 games, nobody made move C. That shows that out of 18 players, nobody believed that C was the best move. Which seems to indicate that it is indeed not a very good move. For the other moves, the more people picked that move, the more successful it was.

Answer 3

Normally this type of problem can be solved by regularizing the probability distribution. In brief, you can add a constant (usually 1 or 1/2) to the observed outcome frequencies for every condition. So the probability of winning after move A would be calculated as p(w|A)= (3+1) / (3+1 + 5+1), p(w|D)= (0+1) / (0+1 + 4+1), p(w|C)= (0+1) / (0+1 + 0+1).

This solution in general works fairly well. I am not sure that applies to your case, but it is possible that there are situations where the the probability of winning is very high/low regardless of the move (e.g., an already won-lost game), or the observed frequency of a move is related with the probability of winning if the movie was played (e.g., no chess player would start a game with e.g. A4).

If these or similar considerations are relevant, you might want to adjust the constants added to the observed frequencies. In the first case you could weight the constant added to the observed probability of winning / loosing by the expected outcome in the specific position (e.g., if the probability of wining is 9 out of 10, you might add 0.9 to the observed frequency of winning and 0.1 to the frequency of loosing). In the latter, you might decide to penalize the moves that have never been chosen (e.g., 0.1 to the probability of winning, 0.9 to the probability of loosing).