Is chi-squared valid in this scenario? I'd like to know whether I am misusing Pearson's chi-squared test. And if so, what should I be doing instead.
I've a game-playing program, a "bot", for a zero-sum two-player game. To improve it, many strategies are played against each other, iteratively finding better and better strategies.  (Where "strategy" means an arbitrary function whose input is the game position, in particular various features extracted from it, and whose output is a number to be maximized.)
When testing strategy A vs B, many A versus B games are played, starting from random positions.  Tests terminate when there is 95% confidence (using Pearson's chi-squared) that we can reject the null-hypothesis. Once a test terminates a small change is made to the winning strategy and a new test begins...
Question1: 
Binomial and this chi-squared test seem to be defined for rejecting the null-hypothesis, but that's not exactly what I am doing here. Let's say I am seeing more wins with B than A. Then rather than rejecting WinFrequency(A) = WinFrequency(B), the null hypothesis, I am rejecting WinFrequency(A) >= WinFrequency(B).
Question2: 
Given an infinite # of trials, we should always reach 95% confidence, one way or the other... an infinite # of times. Does this cast any additional doubt upon my results when there are "sufficiently large" number of tests and it is already believed that the difference between WinFrequency of A and B is no greater than some "sufficiently small" value? In short, I'm wanting a metric to determine when I should stop testing A and B. Ideally this would be parameterized - something like "stop testing when we are 95% certain that B has no more than X% advantage in WinFrequency.
Note: by "WinFrequency" I mean the frequency with which a strategy would beat another, given an infinite number of trials - the expected value.  Also note that draws are impossible - this game always ends in a win/loss.
 A: I think your chi-squared test would look like this? or am I missing something?
     Win     Loss
A   Win A   Loss A
B   Loss A   Win A

I don't believe a chi-squared test applies to this. Chi-squared test expects Poisson sampling (nothing fixed), multinomial/binomial sampling (total sample size fixed),  or independent multinomial/binomial sampling (row or column totals fixed). In this case, the rows/columns are dependent on each other. You only have one actual proportion to test and I would just test WinFrequency(A) = 0.5
Question 1
The statistical test should be decided before looking at results. Otherwise, you can run into increased Type I errors. Here is a short R simulation.
> estMean <- rbinom(10000, 1000, p=0.5)/1000
> stdErr <- sqrt(estMean*(1-estMean)/1000)
> aPrioriType1Error <- sum((estMean-1.96*stdErr) > 0.5 | (estMean+1.96*stdErr) < 0.5) / 10000
> aPrioriType1Error
[1] 0.0539
> postHocType1Error <- sum(sapply(estMean, function(m) {
+     se <- sqrt(m*(1-m)/1000)
+     if (m < 0.5) {
+         return (m+1.645*se) < 0.5
+     } else {
+         return (m-1.645*se) > 0.5
+     }
+ }))/10000
> postHocType1Error
[1] 0.499229

So the null hypothesis should be WinFrequency(A) = 0.5 and the alternative hypothesis should be WinFrequency(A) != 0.5
Question 2
I think you're looking the difference between statistical significance and practical significance. Though the test has 95% statistical significance, WinFrequency(A) = 0.51 may not actually be important. In this case, consider limiting the sample size to end your test. If your null hypothesis is $H_0: \,\, p = p_0\\$ and you want to detect a difference of $\delta = | p_1 - p_0| = | 0.51 - 0.5 |$ then
$$
\begin{align}
N &\ge  \left( \frac{z_{1-\alpha/2} \, 
       \sqrt{p_0 (1-p_0)} + z_{1-\beta} \, 
       \sqrt{p_1 (1-p_1)}}{| p_1 - p_0 |} \, \right)^2 \,  \\
& = \left( \frac{z_{1-\alpha/2} \, 
       \sqrt{0.5 (1-0.5)} + z_{1-\beta} \, 
       \sqrt{0.51 (1-0.51)}}{| 0.51 - 0.5 |} \, \right)^2 \, 
\end{align}
$$
Usually, $\alpha=0.05$ and $\beta=0.2$ where $\alpha$ is the significance level (probability of a Type I Error) and $\beta$ is chance of failing to detect a change of this difference (probability of a Type II Error). $1-\beta$ is called the power of a test.
A: You start with random positions. The better strategy is not the one that should win from any initial position. If all initial positions are equally likely, then the better strategy is simply the one that wins in most possible cases. If we denote the set of all initial positions from which strategy A wins as A, and the ones from which B wins B, then we can define a measure P(S) as simply a count of all positions in S. Assuming there are no draws, P(A)+P(B)=1, and the strategy A is better when P(A)>1/2.
So, yes, it seems that you can look at every game as Bernoulli trial. Hence, the distribution of number of wins $n_a$ and losses $n-n_a$ for A in $n$ games played is binomial.
With binomial you can directly compute the confidence intervals around $n_a$. For instance, you could use simple Wald's approximation for 95% confidence: $\hat p\pm\sqrt{\hat p(1-\hat p)/n}$, where $\hat p=n_a/n$. If you played 10,000 games and A was better in 51% of them, then it's enough to establish the supremacy with 95% confidence. However, 1,000 games would not be sufficient to establish that P(A)> 50% 
