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?
(In reply to re: Clarify please.
On my first move, I go to (2500, 2500). If Merkle says he's "West", he could be in Quadrant II or III. Perhaps I try to isolate the approximate x-coordinate. I could go to (1250, 2500), but he could say "North" (if he's at (2000, 3000)) or "East" (if he's at (2000, 3000)) or "South" (if he's at (2000, 2000)) or "West" (if he's at (1000, 4000). I would really gain little or no information this way.
Perhaps a better strategy would be to travel east by say 5 each move, until he says "West" (or "Northwest"), then travel north until he says "South" (or "Southeast" or "Southwest"). This is a very sloppy algorithm, since he might say "North" even after I've passed his x-coordinate. And I still can't figure out an endgame.
In the morning tomorrow, I think I might work on a strategy for when Merkel stands still, and then try to modify that strategy to find him when he's moving.
Posted by Dustin
on 2012-01-19 06:56:45