2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ When testing strategy A vs. B, are they only playing against each other? Or are there many strategies being tested/played simultaneously and we're only looking at A's and B's win frequency? $\endgroup$ – Eric Farng May 18 '15 at 10:44
  • $\begingroup$ Sorry if I was unclear. Although multiple CPUs may be testing different A/B, what I am focused upon is repeatedly testing a single A versus B. So in the above questions WinFrequency(A) == 1-WinFrequency(B). Assuming Pearsons is ok for this purpose (question #1) then all I need is to understand is when to give up on an apparently inconclusive test (question #2). $\endgroup$ – Conrad May 19 '15 at 8:30
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Conrad May 20 '15 at 23:43
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This looks quite useful, thank you. But what does the Zeta (z with subscript) signify in the above equation? $\endgroup$ – Conrad May 20 '15 at 8:32
  • $\begingroup$ $z$ is the value from the z-table. For $\alpha=0.05$, then look up $z_{0.975}$ and you'll find 1.96 $\endgroup$ – Eric Farng May 20 '15 at 10:39
  • $\begingroup$ @Conrad Aksakal makes a good point in the other answer. If possible, the best solution is to try all initial positions and see who wins the most. As stated below, this assumes all positions are equally likely. $\endgroup$ – Eric Farng May 20 '15 at 10:55
  • $\begingroup$ there are only a bit over 4000 starting positions, but an effectively infinite number of in-game positions. The bot must play well against humans, so I'm using random samples from the infinite position set. (Early on I tested as Aksakal and you suggest, but as there is no luck in the game, the relatively small set of starting positions skewed the results, producing a bot which was optimal versus other bots, but not ideal against a human.) $\endgroup$ – Conrad May 20 '15 at 22:42
  • $\begingroup$ A possibly interesting detail: each random position is played out twice, once with A moving first, and once with B moving first. Results are recorded only when A (or B) wins in both of the play-outs. $\endgroup$ – Conrad May 20 '15 at 22:49
1
$\begingroup$

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%

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.