Is there an optimal strategy for winning this simple game?

  • Thread starter Loren Booda
  • Start date
  • Tags
    Game
In summary, two players are given identical tapes divided into even N blank spaces, each with N/2 marks. They then compare their tapes and score points based on the following rules: 1) A point is awarded for each string of marks that is longer than the corresponding string of the opponent. 2) A point is deducted for each string of marks that is shorter than the corresponding blank string of the opponent. There is no optimum strategy for this game, but there are some near-optimal strategies that can reduce the average loss to half a point per round. One of these strategies is to have a 50% chance of repeating the pattern 1001 and a 50% chance of repeating the pattern 011
  • #1
Loren Booda
3,125
4
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?
 
Mathematics news on Phys.org
  • #2
I'm confused by the rules. Can you explain them, perhaps with the aid of a simple example. :smile:
 
  • #3
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.
 
  • #4
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.
 
  • #5
Aha, so for example:

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

Would score a lot of points for B, Correct?
 
  • #6
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
 
  • #7
Great thanks, Hurkyl! You're a regular polymath.
 
  • #8
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.
 
  • #9
Got it! Makes sense now. Nice work Hurkyl.
 

1. What is the objective of the game?

The objective of the game is to win by achieving a specific outcome or reaching a certain goal.

2. What is the game's rule set?

The rule set of the game outlines the specific actions and limitations that players can take while playing the game. This includes things like how to win, how to score points, and any special conditions that affect gameplay.

3. Is there a specific strategy that guarantees a win?

No, there is no one optimal strategy that guarantees a win in every situation. The outcome of the game may depend on factors such as luck, the actions of other players, and the game's rule set.

4. Are there any patterns or techniques that can improve my chances of winning?

While there is no guaranteed winning strategy, there may be certain patterns or techniques that can improve your chances of winning. These can include analyzing past games, studying the behavior of other players, and adjusting your tactics based on the current game situation.

5. How do I determine the best strategy for a specific game?

The best strategy for a specific game may vary depending on the objectives, rule set, and other players involved. It is important to understand the game's dynamics and experiment with different strategies to determine what works best in a given situation.

Similar threads

Replies
1
Views
967
Replies
4
Views
565
Replies
9
Views
2K
  • General Math
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
870
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
Back
Top