2 Player Limited Information Game

Two robots, Aaron and Erin, are situated at the center of a unit circle. A flag is placed somewhere inside the circle, at a location chosen uniformly at random. Once the flag is placed, Aaron is able to deduce its distance to the flag, and Erin is only able to deduce its direction to the flag. (Equivalently: if (r, θ) are the polar coordinates of the flag’s location, Aaron is told r and Erin is told θ.)

Both robots are allowed to make a single move after the flag is placed, if they wish. Any move they make is without knowledge of what the other robot is doing. (And they may not move outside the circle.) Whichever robot is closer to the flag after these moves captures the flag and is declared the winner.

Erin is programmed to play a fixed distance along the detected angle θ. Assuming otherwise optimal play by both robots, what is the probability that Aaron will win?

For this question, I tried to solve it by setting up an equation such that Erin always moves distance X. If the radius is < X/2 then Aaron should not move becuase he has guarenteed the win, but if the radius is > X/2 then he has to move to have a chance at winning so I assumed that he would move randomly in a direction a distance equal to the radius. Based on some geometry from this math.SE post: https://math.stackexchange.com/questions/2266346/how-do-i-find-the-angle-of-intersecting-circles

I tried to set up an integral to find out the percent of the time that Aaron is able to get closer to the flag when it is between X/2 and 1 away from him (the second integral is just the time he wins all the time as already discussed).

$\int_{\frac{x}{2}}^{1}\frac{2}{\pi}\sin^{-1}\left(\frac{\left|r-x\right|}{2x}\right)2rdr\ +\ \int_{0}^{\frac{x}{2}}2rdr$

I then found the minimum of this function and decided that that was the optimal X for Erin to move since it minimized Aaron's chance of winning over all (r, θ) pairs.

I don't believe that this is correct, can you please go over my work/logic and help me out? Thanks!


Answers can only be viewed under the following conditions:
  1. The questioner was satisfied with and accepted the answer, or
  2. The answer was evaluated as being 100% correct by the judge.
View the answer

1 Attachment

Erdos Erdos
  • Thank you so much. This clears everything to me :)

The answer is accepted.
Join Matchmaticians Affiliate Marketing Program to earn up to a 50% commission on every question that your affiliated users ask or answer.