|
The program cannot win more than 50% of the time because its opponent may always copy the program's strategy and win half the time by symmetry. In order for the best strategy to achieve this maximum, any one choice made by the opponent should have no more than 50% chance to win. In fact, since the opponent can win 50% by symmetry, we can show that the opponent has exactly 50% chance to win if he chooses any of the elements that the program occasionally may choose.
Let the optimal probability of picking each thing be named by the first letter. If the opponent picks, for example, Life, his chance of winning is shown by the following equation:
(E+W+A)/(1-L)
Since we know this must be less than 1/2, we can simplify:
1/2 ≥ (E+W+A)/(1-L)
1/2 - L/2 ≥ E+W+A
1/2 ≥ L/2 + E+W+A
1 ≥ L + 2(E+W+A)
If L isn't 0, then ≥ can be changed to = (referring to the last sentence of the first paragraph).
Already, we can set up a system of 6 equations, and solve for the optimal probabilities.
The rest of the problem is figuring out an efficient way of solving the six inequalities. There are many ways to do this, and you may look to the comments to see other users’ thoughts.
I personally solved this by using a calculator to calculate inverse matrices. The matrix multiplication looked like this for the first version of the game:
[1 2 2 2 0 0] [L] [1]
[0 1 2 2 2 0] [W] [1]
[0 0 1 2 0 2] [A] = [1]
[0 0 0 1 2 2] [E] [1]
[2 0 2 0 1 2] [F] [1]
[2 2 0 0 0 1] [C] [1]
This method has its flaws, since it solves it as if there were no inequalities, which is only a correct assumption if all the variables are greater than zero. I had to do guesswork to find out which variables were zero.
The results:
In the first version of the game, the program's best strategy is to never pick Air, and pick each of the other elements 1/5 of the time. In the second version, the program should never pick Earth, but pick Water and Fire 1/3 of the time each, and the rest of the elements 1/9 of the time each.
|
