Is there an optimal strategy for winning this simple game?

[Loren Booda]

Two players given identical tapes ruled with even N blank spaces each mark N/2 of them. They then compare the tapes, with the goal of scoring the most points as follows:

1. A point is awarded for each string of marks including and longer than that correspondent of the opponent.

2. A point is deducted for each string of marks included by and shorter than a blank string correspondent of the opponent.

Is there an optimum strategy for the players?

 

[Pauly Man]

I'm confused by the rules. Can you explain them, perhaps with the aid of a simple example.

 

[STAii]

Originally posted by Loren Booda
Two players given identical tapes ruled with even N blank spaces each mark N/2 of them. They then compare the tapes, with the goal of scoring the most points as follows:

1. A point is awarded for each string of marks including and longer than that correspondent of the opponent.

2. A point is deducted for each string of marks included by and shorter than a blank string correspondent of the opponent.

Is there an optimum strategy for the players?

How about putting all your marks in a single string ?
This way it is impossible for the opponent to make a string longer (in order to include it), so it will end up either as a tie, or you will win.
This is from my way of understanding the rules, maybe if you make the rules a little bit clearer it would be better.

 

[Loren Booda]

Say I give player A and player B each a tape marked off into, e. g., twenty blank spaces. Each fills his tape with ten (20/2) marks so that (amended thanks to STAii):

1. A point is awarded for each string of marks including and longer than that correspondent of the opponent.

2. A point is awarded for each string of remaining blank spaces included by and shorter than that correspondent of the opponent.

Take the following example (x is a mark, - is an originally blank space, and 0 a remaining blank space). Upon comparing tapes:


A x0xxxx0xxx00000xx000
>>--------------------
B 0xx00000xxx000xxxxxx


No point is awarded under rule #1 to player A, but player B's last string of marks awards him one point here, since these 6 marks cover and exceed the corresponding 2 of player A.

One point is awarded under rule #2 to player A for his inclusion of his second 0 string by B's second string of 0's, and one point is awarded B for his third string of 0's included in A's third string of 0's.

B wins, 2 to 1.

 

[Hurkyl]

Aha, so for example:

A: --------xxxxxxxx
B: -x-x-x-xxxxx----

Would score a lot of points for B, Correct?

 

[Hurkyl]

For any tape sizes greater than 4, no deterministic strategy is optimal.

Proof: I wrote a program that enumerated all possible games for tapes of length 6, 8, and 10, and observed that no choice could guarantee a tie or better. Apply "engineering induction" to extend the result to all tape sizes. (Just teasing, engineers!)

(Since the game is perfectly symmetric between A and B, the optimal strategy guarantees that you will do, on average, no worse than tie any strategy your opponent uses)


For a size 4 tape, the optimal game is:
0110


For a size 6 tape, some optimal games are 50% choices between:
011001 & 100110
010110 & 011010
001110 & 011100
011010 & 001110


For a size 8 tape, some optimal games are 50% choices between:
00011110 & 01111000
01001110 & 01110010
(these are all of the optimal games that can be played by making 50% decisions)


For a size 10 tape, no optimal game is as simple as making a 50% choice between two alternatives, though a simple one like

0000111110 & 0111110000

is near optimal yielding on average a half of a point loss to an opponent who only picks 0001111001

No 33% choice between three alterantives is optimal either, but you can reduce your average loss to a third of a point with:

0101110100 & 1000101110 & 1111000001
which is foiled by 0000111101

or for a simpler one:
0000111110 & 0111110000 & 1110000011
which is foiled by 0001001111


You can bump your losses down to a quarter of a point on average with a 25% - 25% - 50% choosing scheme, but I didn't write the answer down and it takes a while for my program to run, so I'm not going to compute it again right now.


Hurkyl

 

[Loren Booda]

Great thanks, Hurkyl! You're a regular polymath.

 

[Hurkyl]

Hehe thanks.

Incidentally, I don't think one can get much further with raw brute force unless they're willing to spend a few days waiting for the results, or have access to a cray for recreation. The number of iterations are getting humongous, and the cache array needed to keep the runtime tolerable is getting too big to fit in memory.

Interestingly, for the 12 size tape, a near optimal (you lose half a point per round on average to optimal play) strategy is the very simple:

50% 100110011001 and 50% 011001100110

For size 8, the same pattern performs the same (half a point lost per round)

50% 10011001 and 50% 01100110

For size 4, this pattern really is optimal

50% 1001 and 50% 0110


I conjecture that for tape sizes divisible by 4, if your strategy is:
50% chance of repeating 1001 until end of tape or
50% chance of repeating 0110 until end of tape
then your expected losses can be no worse than half a point per play.


I might spend some work on coming up with an attack that doesn't require brute force exhaustion, I might get some more interesting results that way.

 

[Pauly Man]

Got it! Makes sense now. Nice work Hurkyl.