An "x-y" grid game that I know as "Find Merkle" [M
] requires a player [H
] to begin at (0,0) and zero in on a hidden co-ordinate location of the creature by nominating one of the 4 cardinal directions
and an integer distance. Upon failure to land on that location you are given just one cardinal direction towards that site.
Supposing "Merkle" is hiding at (5,5) and you are at (3,8) after your second play, which was either E3 or N8, you are told E or S, nothing more.
Let us allow two changes to this
Firstly the player is told to move in one of 8-point compass rose directions
Secondly, upon failure to capture, "Merkle", having no knowledge of the hunter's location, randomly relocates to any of his immediately adjacent 8 locations except for one if already occupied by the hunter.
- This is exemplified if "H" has been told "SE" and has relocated to (6,5).
Oh, and the hunter only knows "Merkle's" location upon capture.
Given that the hunter is astute and multiple games are played, what is the most likely number of moves to capture "Merkle" within an NxN grid?
Well, this is confusing. Brianjn, can you confirm (or correct) these 8 understandings (or misunderstandings):
Understanding 1) M cannot start on (0,0)
Understanding 2) Merkel's initial location is random. He is equally likely to start on on any location that is not (0,0). In particular, he will not initially favor a location that is unreachable from (0,0).
Understanding 3) An N X N grid has (N,N) as the corner opposite (0,0). In other words, an NXN grid has (N+1)*(N+1) locations.
Understanding 4) The direction given towards Merkel's location is BEFORE Merkel relocates
Understanding 5) The direction given toward's Merkel's location is still given as one of 4 cardinal directions.
Understanding 6) If there are two possible cardinal directions which can be indicated, the direction given is chosen randomly from those two (i.e., not given by some opposing force trying to provide as little additional info as possible to the Hunter)
Understanding 7) Merkel's new location is always adjacent to Merkel's old location, in one of 8 direction.
Understanding 8) Despite the syntax above, the Hunter is not "Told" in which direction to move. The hunter has total control over which direction to move. If this assumption is wrong, then we need an explanation of how the direction in which the hunter is forced to move is determined.
I think that's all for now. I would provide some initial results, but they depend far too heavily on the understandings above, and the probability that all of these understandings are what Brianjn intended is somewhere south of 10%. Or maybe southeast.
Edited on January 18, 2012, 9:19 pm