The optimal strategy for $n=13$ odd is to try $2,\ldots,n-1=12$ first, which will catch the opponent if an only if she started on an even number; if the opponent is still not caught, one is sure she started on odd an is now (after $n-2=11$ moves) on an even number (in particular not on $n=13$), and trying $12,11,\ldots2$ is sure to catch her, for a total of $2*11=2n-4=22$ tries.
The same scheme works for $n=12$ even: try $2,\ldots,n-1=11$ first, which will catch the opponent if an only if she started on an even number; if she still not caught, one is sure she is now (after $n-2$ moves) again an odd number (in particular not on $n=12$), and trying $n-1=11,\ldots2$ is sure to catch the opponent, for a total of $2*10=2n-4=20$ tries.
Added: Here is the full anaylsis of the game. It clearly splits into two parallel games, one where the opponent starts odd and another where she starts even. The opponent chooses a game at the start and has to stick to it, but we don't know which it is, so we need to reduce to number of remaining potential positions in both games to $0$. On each move we remove one of the potential positions, but then the remaining possible positions are replaced by the set of all their neighbours; this also happens in the game we didn't play in. If one switches back-and-forth between games (playing game $A$, then at leat once game $B$ then again game $A$), then the before the second move in game $A$ the number of potential positions in game $A$ (if the first move didn't reduce it to $0$) has again grown to at least the same number it was before the previous move in $A$, so this gains nothing; an optimal strategy therefore should avoid such swithching. We must therefore choose a game to play in first, terminate that game entirely, and then start plaing in the other game.
Now focussing on one game (so the parity of the possibilities at each point in time is known), one may verify that the only type of move that actually reduces the number of remaining possibilities is where those possibilities form an "interval" (in the sense of the numbers of a given parity in a given interval) containing one of the extremities of the total set: by playing the other end of the interval, the possibilities are reduced to those of the opposite parity between the ends of the original interval. (The claim "only" is not entirely true: (1) whenever the possibilities have been reuced to a singleton, one can play that to reduce it to $0$, and (2) if $n$ is odd and all odd numbers remain possible, their number is bound to decrease regardless of our move. However these possibilities are marginal and do not affect our analysis.) After such a move one cannot reuce the number again on the next move, but by playing again on the same end of the (new) interval one can at least prepare do decrease it on the move after that.
There are four types of games, according to the parity of $n$ and of the initial possibilities. The two variants with $n$ even are left-right mirror images, and the "initial even" one can be won in $n-2$ moves by playing $2,3,\ldots,n-1$. So can the "initial even" game with $n$ odd. The game with $n$ odd and initial possibilities odd however needs $n-1$ moves: the very first move makes no difference whatsoever, and then the "initial even" game remains. Since we have the choice which game to play in first, and since for $n$ odd the "initial even" game requires an odd number of moves, we can play that first and have transformed the other game into another "initial even" game, so in the end we can still win in $2(n-2)$ moves, regardless of the parity of $n$.