An instance of the "flyswatter game" is defined by a graph $G$ and positive integer $k$. There are two players, A (the 'fly') and B (the 'swatter'). Essentially, the fly moves around $G$ and the swatter tries to guess where the fly will be $k$ steps in the future.
Formally, the game is played in two stages:
(1) Player A chooses an infinite walk $w_1, w_2, \dots$ on $G$ (but player B doesn't see it).
(2) Player B goes through the walk one step at a time. At step $t$ (having already observed $w_1, w_2, \dots, w_t$) he gets to either go to step $t+1$ (revealing $w_{t+1}$) or he can 'swat' by picking a vertex $v$ (which ends the game -- so he can only do it once). Player B is allowed to observe as many steps of the walk as he wants before swatting.
Player B wins if and only if $w_{t+k} = v$, where $t$ is the step where he decided to swat $v$ (i.e. the fly gets hit).
Even simple examples (e.g. $G$ is a 3-cycle, $k = 2$) give interesting behavior. I'd be surprised if nobody has ever studied this game, but I can't find it anywhere. Has anyone seen this before?
EDIT: As per Kaveh's suggestion (on the CSTheory copy -- now deleted), here's a bit of background about this.
I'm interested in this question as a simplification of a continuous problem about finding a maximally unpredictable random process for generating a path on the real line (for a particular measure of unpredictability). Thus, one thing I'd like to know in particular is an optimal strategy for the fly on the integer line (which can be simulated by using a cycle of size $2k + 1$ instead).
What I've proven:
Let $p_A(G, k)$ be the probability of winning for player A. Then (for any $G$) $k_1 < k_2$ implies that $p_A(G, k_1) \leq p_A(G, k_2)$ (player A prefers larger $k$).
If $G$ has $n$ vertices, $p_A(G, k) \leq \frac{n-1}{n}$ (this is trivial, as player B can simply guess a random vertex).
What I strongly suspect to be true (not yet proven):
There is always an optimal strategy for player A which generates the walk using an order-$k$ Markov chain.
If $k = 1$, the optimal strategy for player A is to find the subgraph $G^*$ of $G$ which has largest minimum degree (there is a poly-time algorithm to find this), and then do a random walk on $G^*$.
An interesting case: $C_3$ with $k = 2$.
The best strategy I've found so far for A to generate his walk is:
begin at any vertex; at first move, move CW or CCW with probability $1/2$ each.
for all subsequent moves, with probability $\frac{\sqrt{5} - 1}{2}$ repeat the previous move (CW or CCW); otherwise switch.
This gives player B a winning probability of $1 - \frac{\sqrt{5} - 1}{2} \approx 0.382$ (the probability for A to be back where he started after 2 moves, or to have moved twice in the same direction as his previous move).