Some exposition for those who may not be too familiar with the game:
A Feebas is a fish-like pokemon which only appears in one location in the entire game - Route 119. To be specific, it can be encountered only on the waters of Route 119, by fishing.
There are 400 water "tiles" in Route 119. Among these 400, Feebas can appear in exactly 6 specific tiles, with a probability of 0.5. These tiles are randomly chosen when a new game is initialized, and their locations are unknown to the player.
If a player can determine that a particular tile contains Feebas however, he can always find Feebas in that specific tile with a 50% probability.
According to Bulbapedia, if a player fishes exactly once in each of the 400 tiles, he approximately has a 1.6% chance of not finding any Feebas (or alternatively, a 98.4% chance of finding at least one).
This calculation is fairly simple - the probability of finding at least one Feebas by searching just once (S = 1) in each tile (T = 400) is:
$P(F>=1|T=400,S=1) = 1 - 0.5^6 = 0.984375$
While this is great, this approach requires a player to make 400 search operations. In fact, if the player fishes twice in each tile, at the cost of 800 operations, his probability of finding at least one fish goes up to:
$P(F>=1|T=400,S=2) = 1 - (0.5^2)^6 = 0.999755$
So I was wondering if this problem can be approached a bit differently, maybe from the perspective of optimal stopping problems?
What would be a good strategy to minimize the number of search operations/tiles explored, while retaining a reasonable probability $P >= 0.9$ of finding at least one Feebas?
Last tidbit: it is actually possible for the player to manually reset the locations of the Feebas into 6 new random unknown positions. (This can perhaps facilitate a different class of strategies, like searching only in 40 tiles, and then resetting the random 6 positions, again trying in those 40 tiles and so on. Not sure how good or bad this would be - just putting it out there.)
$\endgroup$ Reset to default
