Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A simple game

  1. Apr 27, 2003 #1
    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?
  2. jcsd
  3. Apr 27, 2003 #2
    I'm confused by the rules. Can you explain them, perhaps with the aid of a simple example. :smile:
  4. Apr 27, 2003 #3
    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.
  5. Apr 27, 2003 #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.
  6. Apr 27, 2003 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Aha, so for example:

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

    Would score a lot of points for B, Correct?
  7. Apr 27, 2003 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:

    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 gonna compute it again right now.

  8. Apr 27, 2003 #7
    Great thanks, Hurkyl! You're a regular polymath.
  9. Apr 27, 2003 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  10. Apr 30, 2003 #9
    Got it! Makes sense now. Nice work Hurkyl.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: A simple game
  1. A strange game (Replies: 5)

  2. Fair Games (Replies: 3)

  3. Funny game (Replies: 1)

  4. Football Game (Replies: 12)

  5. Cheating in the game (Replies: 3)