This is from a Linkedin post here:
You are playing a video game in which you kill aliens who have come to our planet! There are N aliens. K < N of them are evil while others are good. Every time you kill an evil alien you win 1 point whereas every time you kill a good alien you lose 1 point. Assuming you don’t know who is evil and you can stop any time, what’s the optimal strategy? You know K and N, and you find out if an alien was good or bad once you kill it. What’s the expected points if you play optimally?
My initial thought was to define a matrix of solutions dp[n][k] for the maximum points you can get starting from n aliens total and k bad ones.
Then, it seems relatively straightforward to note that:
dp[n][k] = max(0, k/n * (1 + dp[n-1][k-1]) + (n-k)/n * (-1 + dp[n-1][k]))
indeed, if you kill a bad alien, you go from the state n,k to n-1,k-1; for a good alien - n-1,k.
The problem is boundary conditions for the recurrence. My initial thought was dp[n][k] = 0 as long as 2*k <= n since marginally it seems useless to keep shooting at this point (i.e. a given shot will have a non-positive marginal expectancy). However, you can see that for 2 aliens total and 1 bad one (dp[2][1]) the optimal strategy is to shoot once and stop if you killed a bad alien. This would give you 0.5 *(1+dp[1][0]) + 0.5 *(-1 + dp[1][1]) = 0.5 points in expectation.
Note the 'conservation law', score + (k - (n-k)) = 2K - N, i.e. every time you kill an alien, either your score increases by 1 but the difference between bad and good ones decreases, or the other way around. Using my naive stopping rule k <= n/2 you would then conclude that score_opt + 0 = 2K - N, i.e. optimal score is 2K - N.
Using a more accurate stopping rule above (the 'max(0, ...) part) with the boundary condition dp[1][1] = 0 and just brute-forcing it in Python shows that 2k-n is the "baseline" to which you have some small corrections. i.e. for N = 10000 the first K for which you have positive expectancy is 4958 and not 5001.
Any ideas for an exact solution?
