The answer depends upon, of course, if the players make their moves intelligently or stupidly. In either case, build an alpha-beta tree of move sequences and search either depth-first or breadth-first, stopping and backtracking as winning configurations are found. However, there are some rigorous points you have not defined about this question, including whether perhaps it came to you as a homework problem. Hoping that this is not the case, here's a take on it:
Yes, if $n=2$, then the first player to move obviously wins by picking any one of the four open spots, and the game is over. If $n=3$ (which you don't define for odd $n$, but lets say for odd $n$, $(n+1)/2$ spaces wins, then the first player to move wins automatically also, because no matter which space they take in the $3 \times 3$ grid, the next player can only block one space, and in the 2nd round, first player easily wins.
For $n=4$, the first player wins, with the same strategy as shown for $n=3$. $A$ picks any square in the $4 \times 4$ grid, $B$ picks any other square but can only block $A$ in one of the two dimensions in which this grid lies, therefore on the first step of the second round, $A$ wins by picking a square adjacent to his first square.
Are you sure that you've thought this out for the smaller grid games?
So for the $4 \times 4$ configuration, assuming that $A$ plays intelligently, there are
$4 \times 4 = 16$ first moves for $A$
$16 - 1 = 15$ first moves for $B$, if $B$ plays stupidly, or either $2, 3,$ or $4$ moves if $B$ plays intelligently
$4 \times 1 + 8 \times 2 + 4 \times 3 = 4+16+12=32$ second moves for $A$ which win the game and end the game ($A$ could have picked one of the $4$ corners, $B$ blocks one way leaving $1$ way for $A$ to play, if $A$ picks one of the non-corner edge pieces (8 ways to do that), then $B$ blocks one way leaving two ways for $A$'s second winning move, and if $A$'s first move is a center piece, $B$ can block one of the $4$ adjacent squares, leaving $3$ adjacent squares for $A$ to pick and win.
So if $A$ and $B$ both play intelligently, the sum of these are the possible games for a $4 \times 4$ grid:
$4 \cdot 2 \cdot 1 + 8 \cdot 3 \cdot 2 + 4 \cdot 4 \cdot 3 = 8 + 48 + 48 = 104$
If $A$ and $B$ do not play intelligently, then the number of possible games is much larger, and the number of "winning configurations" or "end positions" is much larger.
Let $\oplus$ denote the bitwise xor operation on natural numbers. It is both well-known and easy to verify that a Nim position $(n_1,\dots,n_k)$ is a second player win in misère Nim if and only if some $n_i>1$ and $n_1\oplus\cdots\oplus n_k=0$, or all $n_i\le1$ and $n_1\oplus\cdots\oplus n_k=1$.
If I understand it correctly, this translates to the following structure. Let $A=(\omega,\oplus,0)$ (in other words, $A$ is the direct sum of countably many copies of the two-element abelian group), let $A_0=\{0,1\}$ be its submonoid, and let $B=(\{0,1\},\lor,0)$ be the two-element semilattice. Then the underlying monoid of the misère quotient of Nim is the submonoid $Q=(A\times\{1\})\cup(A_0\times\{0\})$ of the product monoid $A\times B$, the misère quotient itself being $(Q,\{(0,1),(1,0)\})$. If $(n_1,\dots,n_k)$ is a Nim position, its value in $Q$ is $(n_1\oplus\cdots\oplus n_k,u)$, where $u=0$ if $n_i\in\{0,1\}$ for each $i$, and $u=1$ otherwise. $Q$ has (as a commutative monoid) the infinite presentation $\langle \{a_n:n\in\omega\},b\mid a_n+a_n=b+b=0,a_n+b=a_n+a_0\rangle$. Finitely generated submonoids of $Q$ are finite, hence $Q$ itself is not finitely generated.
(Note that the monoid corresponding to normal play Nim is just $A$.)
Best Answer
The formulation of the question is very unclear, so I'll make some guesses about what was meant. First, I assume that all vertices have the same sort of data available, namely how many winning positions (not how many sequences of moves leading to those positions) there are for one or the other player after any number of subsequent moves. (In particular, the statement "'C' vertex contains different data" means only that the numbers are different for C, not that a different sort of information is given there.) Second, I'll assume that the *condition "if the game is not finished" means merely that the indicated number of moves should make sense. (I'll comment below on the alternative interpretation that, at a vertex corresponding to a finished game, we are not told who won.) Third, I'll assume that the absence of that *condition in the "3 moves" line of the example is not significant, mainly because I can't think of anything general to infer from that absence.
With all these assumptions, I'd find optimal moves for Player 1 by the following standard method for analyzing game trees. First, discard the information at most of the vertices; keep only the information at the leaves of the tree, telling who won the finished plays. Second, work backward from the leaves toward the root, labeling each vertex with the following information: Who has a winning strategy from that vertex? How many moves will it take to win (against the opponent's best delaying strategy)? If the player who has the winning strategy from this vertex is the one who is to move, then what is the first move of that strategy? It is easy to assemble all this information for a vertex given the corresponding information for all its children, so we can work backward from the leaves and fill in the information throughout the game tree. (Note that there is nothing probabilistic about the solution, or, for that matter, about the problem.)
In the (intuitively very strange) case that the *condition was intended to say that we don't know who wins at which terminal position, then, in general, there is not enough information to design an optimal (or even a reasonable) strategy. Perhaps in this situation, probability can become relevant if we assume that the opponent also doesn't know the winning conditions of the game and therefore uses some mixed strategy. In that case, the theory of equilibrium mixed strategies might be relevant, but I think this interpretation of the question is too improbable to be worth any more comment.