5
$\begingroup$

Imagine a very big number (2N) of people, who do not know each other, and play the following game:

  1. Players are divided into two equal groups: A and B. In each group players are numbered from 1 to N.

  2. Each A-player chooses a position for a white king on the chessboard.

  3. Each B-player chooses a position for a black queen on the chessboard.

  4. For each pair of players with the same numbers, the king and queen are placed on a void chessboard. If the queen checks the king, the B-player wins. If not, the A-player wins. If they are on the same square, we call it even.

Let's call a player a 0-level player if he chooses his piece position by uniform random distribution over the whole board. Let's call a player an L-level player if he chooses his piece position randomly between the most winning positions on the assumption that he is playing with an (L-1)-level player.

Suppose that all 2N players are M-level players. What is the optimal strategy for A- and B-players to win as many games as possible? What will the wining percent in each group be?

Please, consider the following cases:

  1. M = 2.
  2. M = 3.
  3. M = Infinity.

For example, for M = 1 [I do not know the solution, so, please be careful, mistakes can be here]:

  1. The B-player will suppose that king can be at any square with the same probability and will put queen at the positions where it covers as many cells as possible: enter image description here
    He will expect a winning probability of (6+7+7+7)/64 = 0.422 and a draw probability of 1/64 = 0.016.

  2. The A-player will suppose that the queen can be at any cell with the same probability, and will put king at the positions where the queen would cover as few cells as possible: enter image description here
    He will expect a winning probability of (64-7-7-7)/64 = 0.672 and a draw probability of 1/64 = 0.016.

  3. In reality, the winning probability for the A-player will be (30-8)/30 = 0.733, the winning probability for the B-player will be 8/30 = 0.267, and the draw probability will be 0.

$\endgroup$
  • $\begingroup$ Just to clarify: For M=2, player B would expect the level 1 player to put the king on the outside edge, and would therefore choose to put the queen in a corner, and then player A would assume the queens is somewhere in the middle and would put the king somewhere offset? $\endgroup$ – Bobson Jun 13 '14 at 14:29
  • $\begingroup$ @Bobson, this seems to be correct. $\endgroup$ – klm123 Jun 13 '14 at 14:32
  • $\begingroup$ This would be a very fun programming competition... especially if each hypothetical pair could watch all previous games! $\endgroup$ – kaine Jun 13 '14 at 18:39
  • $\begingroup$ @kaine, i'm not sure who to make competition from this. Since L-level will beat L-1-level only, not L-2 or others. $\endgroup$ – klm123 Jun 13 '14 at 18:41
  • $\begingroup$ @klm123 - Well, L might beat L-2, but it would be much more coincidentally than against L-1. $\endgroup$ – Bobson Jun 13 '14 at 18:54
5
$\begingroup$

grid

If one were to work through the way you describe (each player taking into account only the previous players plan), then a 12-unit loop would quickly be observed. Case $M=2$ is the same as case $M=14$ which is the same as case $M=26$ etc. This doesn't really help anything. This loop does not yield a perfect strategy for either player. Essentially, no $L$ level player will be against an $L-1$ level player so why plan as if he were? As there is a loop there isn't really an $M=\infty$.

chart

Lets pretend that a better player of level $L$ chooses a plan which assumes that the other player will randomly choose a strategy such that $ S < L $. So $ M=3$ takes into account $M=1$ and $M=2$ (but not the totally random case).

After 10,000 iterations of this done (by making a matrix of what position has what probability of beating what position multiplied by vectors describing the probability of each player choosing each position) I get the answers below for which the queen wins about 35% of the time while the king wins 64% with both players playing optimally.

another chart

Looking at it from the perspective of the queen trying to find a perfect strategy and the king reacting perfectly, this does not improve much over the queen just randomly picking any square!

I also designed a pseudo-evolutionary algorithm where 20,000 games are played. Each player chooses where he should go based on the third power of the percentage of times he won in that spot previously (plus a small mutation factor close to the value of 1 win). This isn't worth much, but it claims the king should: prefer A, B, and C; choose D, E, and F about 1/2 as much; and never choose H, I, and J. The queen should chose about all randomly, but prefer H, I, J, and E. I think there is too much noise though in this program, and I don't want to focus on it anymore.

Likely, the best strategy possible is the one that has no preferred placement of the kings, as everywhere is covered equally. I doubt that a strategy the would let the queen win more than 40% of the time if the king playing perfectly is possible.

$\endgroup$
  • $\begingroup$ Could you explain your tables please? $\endgroup$ – klm123 Jun 17 '14 at 15:42
  • $\begingroup$ Each strategy is a set of 10 probabilities that sum to one as to which type of position he should choose and he randomly picks one of those 8 or 4 squares. All A positions for instance are identical and are the corners. See the first figure for what each letter means. The second table shows one strategy for each team (example the queen team should never chose position C but should pick J about 5% of the time). The first table has the same kind of strategies but the top column is the L level. Aka L=0 is completely random. L=1 you showed in the question. L=3 to L=14 is a repeating unit $\endgroup$ – kaine Jun 17 '14 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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