Simple game design... math problem... help! - Gambling and Probability

Trying to solve for a single variable in the game below.

The game is completely random, the only input a player has is to choose which character they will be. Then the game plays out until it ends, and the player either loses or wins.

First: player chooses team A "Bombers" or team B "Savers"
Then: player then chooses character number 1, 2, 3, 4, 5 from their selected team.

There is a NPC called a 'bomb', it can be in the state "defused", "set", or "exploded". It starts "defused".

Game timer is just over X seconds.

Every second, one of the following occurs;
- 9% character A1 killed, if already dead then reroll
- 9% character A2 killed, if already dead then reroll
- 9% character A3 killed, if already dead then reroll
- 9% character A4 killed, if already dead then reroll
- 9% character A5 killed, if already dead then reroll
- 9% character B1 killed, if already dead then reroll
- 9% character B2 killed, if already dead then reroll
- 9% character B3 killed, if already dead then reroll
- 9% character B4 killed, if already dead then reroll
- 9% character B5 killed, if already dead then reroll
If bomb set:
- 5% bomb is defused
- 5% bomb explodes
If bomb defused:
- 10% bomb is set

The game ends when one of the following occurs;
- the player's chosen character is killed
- all characters other than the player's chosen are killed
- team A are all dead
- team B are all dead
- bomb explodes
- timer reaches zero

The round resolves as winner or loser per following hierarchy;
chosen killed - lose
all nine players other than chosen killed - win
chosen is from team A, and is alive when bomb explodes - win
chosen is from team B, and is alive when bomb explodes - lose
chosen is from team A, and is alive when timer is zero - lose
chosen is from team B, and is alive when timer is zero - win
chosen is from team A, and is alive when team B all killed - win
chosen is from team B, and is alive when team A all killed - win

It is obvious that characters 1/2/3/4/5 within a team all have the same chance of winning if chosen.

It is obvious that character from team A and characters from team B have a different chance of winning if chosen, and this depends on the length of the game (X).

So the challenge is; what value of X makes choosing a character team A or team B approximately equal in terms of probability of winning?

Second question: given the optimum value of X, what is the value of an individual player winning one game?

I'm paypal a few bucks for a correct answer with work shown. Bonus if you show the curve for various values of X.

Last edited by David Lyons; 12-17-2018 at 01:15 PM.

Quote

12-17-2018 , 11:57 PM

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

I don't know what you're asking in the 2nd question.

A transition matrix is an easy way to solve the 1st question.

From a team perspective we can model this with 2 absorbing states: bomb exploded or a team is all dead. We don't need to distinguish between the teams because they both have the same probability of going extinct. Nor do we need to distinguish between different times. After raising the matrix to the power of X, the probability of time expiration is the sum of the probabilities of being in each non-absorbing state after time X.

Including the initial state, there are 2 * (5 multichoose 2) = 30 non-absorbing states: 0-4 players from each team can be dead while the bomb is set or diffused.

I'll code the matrix tomorrow if no one has solved the problem by then.

Quote

12-18-2018 , 07:13 AM

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

Since we have a great volunteer to tackle an analytical solution, I programmed a simulation tonight.

I will put the results into a spoiler so as not to unduly influence the analytical effort.

Spoiler:

I did this late tonight and have given little time to reviewing the results, but I hope they are correct. Here are results of simulations over different game timings (X). I ran each simulation over each of the five members of each team (A or B) for 100,000 games, so these are essentially averages over 500,000 trials.

Seconds	Member of Team A Win Pct	Member of Team B Win Pct
1	0.0000	91.0614
2	0.4100	81.7268
3	1.0682	72.2238
4	1.8730	62.9290
5	2.6816	53.7322
6	3.6758	44.9840
7	5.1100	36.9326
8	7.3226	29.7252
9	11.0058	23.8216
10	14.7256	19.7830
11	17.4446	17.2192
12	18.9884	15.9188
13	19.6370	15.2406
14	20.0394	14.9614
15	20.1460	14.8570
16	20.2650	14.7004
17	20.2862	14.7280
18	20.3426	14.7062
19	20.3228	14.7214
20	20.3022	14.6888

Last edited by whosnext; 12-18-2018 at 07:19 AM.

Quote

12-18-2018 , 12:28 PM

David Lyons

old hand

Join Date: May 2003 Posts: 1,459

Thanks both.

Whosnext - are those %s including all game end triggers inc. bomb / timeout? If so, then that suggests approximate balance at 11 seconds. Are you prepared to share your simulation code?

HeeHaww - to answer your question, what I mean is that "given an optimum value of X (seems to be 11), if a player chooses e.g. player A4 what is their chance of getting a win?"

Quote

12-18-2018 , 01:22 PM

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

I didn't use code because it wouldn't have been any faster than manually entering the data. I used an online matrix calculator to compute a few powers. The following matrix can be pasted into said calculators:

Code:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0.9 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.9 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0.3 0.6 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.3 0 0.6 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0.225 0 0 0.675 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.225 0 0 0 0.675 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0.18 0 0 0 0 0.72 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.18 0 0 0 0 0 0.72 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0.15 0 0 0 0 0 0 0.75 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.15 0 0 0 0 0 0 0 0.75 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0.9 0 0 0 0 0 0 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0.9 0 0 0 0 0 0 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0.36 0 0 0 0 0 0.54 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0.36 0 0 0 0 0 0.54 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0.6 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0.3 0 0 0 0 0 0.6 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0.257 0 0 0 0 0 0.642857 0 0 0.05 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0.257 0 0 0 0 0 0.642857 0.1 0 0 0 0 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0 0 0 0 0 0 0.05 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0 0 0 0 0.1 0 0 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3857 0 0 0 0.5142857 0 0 0.05 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3857 0 0 0 0.5142857 0.1 0 0 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3375 0 0 0 0.5625 0 0 0.05 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.3375 0 0 0 0.5625 0.1 0 0 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0 0 0 0 0.05 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0 0 0.1 0 0 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.4 0 0.5 0 0 0.05 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.4 0 0.5 0.1 0 0 0
0.05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0 0 0.05
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.9 0.1 0

I easily could have entered something wrong, because my result is a little different than whosnext's sim: I get X=10.

When you raise that matrix T to the power of 10, the information we need is on the first two columns of the bottom row:
P(bomb exploded) = T¹⁰[32, 1] = .1223
P(an entire team was killed) = T¹⁰[32, 2] = .7969
Hence, P(bombers win) = .1223 + (.7969/2) = 52.075%

By the same method, with 9 seconds I calculate 55/45 in favor of the bombers.
With 11 seconds, it's 60/40 in favor of the savers.

To answer the 2nd question, I'll have to insert more absorbing states so as to capture the additional information necessary. When the bomb explodes, there can be 6-10 people alive. When a team dies off, the other team can have 1-5 living members. Thus, there are 10 absorbing states and I'll need a 40x40 matrix. I'll do it later, as well as code my own sim if necessary.

Quote

12-18-2018 , 01:59 PM

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

Here is the program I wrote in R to perform the simulations. I am admittedly not a good programmer and I am sure the code is very inefficient. But for this purpose I valued transparency. I tried to faithfully follow the rules to David's game but I could easily have made one or more mistakes along the way.

Code:

dlyonsgamesim=function(maxseconds,charab,trials)
{
  # fn to simulate david lyons' computer game from 2+2 dec 2018
  
  # set.seed(1234)
  
  wintally=0
  lostally=0
  
  if(charab<6) team=1 else team=2
  notme=setdiff((1:10),charab)
  
  for(gamey in 1:trials)
  {
    endround=0
    bomb=1
    abteam=rep(1,10)
    
    for(roundy in 1:maxseconds)
    {
      validdraw1=0
      
      for(draw1 in 1:100)
      {
        drawkill=sample.int(100,1)
        
        if((drawkill>=1) & (drawkill<=9))
        {
          if(abteam[1]==1)
          {
            abteam[1]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=10) & (drawkill<=18))
        {
          if(abteam[2]==1)
          {
            abteam[2]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=19) & (drawkill<=27))
        {
          if(abteam[3]==1)
          {
            abteam[3]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=28) & (drawkill<=36))
        {
          if(abteam[4]==1)
          {
            abteam[4]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=37) & (drawkill<=45))
        {
          if(abteam[5]==1)
          {
            abteam[5]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=46) & (drawkill<=54))
        {
          if(abteam[6]==1)
          {
            abteam[6]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=55) & (drawkill<=63))
        {
          if(abteam[7]==1)
          {
            abteam[7]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=64) & (drawkill<=72))
        {
          if(abteam[8]==1)
          {
            abteam[8]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=73) & (drawkill<=81))
        {
          if(abteam[9]==1)
          {
            abteam[9]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=82) & (drawkill<=90))
        {
          if(abteam[10]==1)
          {
            abteam[10]=0
            validdraw1=1
          }
        }
        
        if((drawkill>=91) & (drawkill<=100))
        {
          validdraw1=1
        }
        
        if(validdraw1==1) break
        
      }
      
      if(bomb==2)
      {
        drawb2=sample.int(100,1)
        if((drawb2>=1) & (drawb2<=5)) bomb=1
        if((drawb2>=6) & (drawb2<=10)) bomb=3
      }
      else
      {
        if(bomb==1)
        {
          drawb1=sample.int(100,1)
          if((drawb1>=1) & (drawb1<=10)) bomb=2
        }
      }
      
      if((abteam[charab])==0) imdead=1 else imdead=0
      if((sum(abteam[notme]))==0) othersalldead=1 else othersalldead=0
      if((sum(abteam[1:5]))==0) alladead=1 else alladead=0
      if((sum(abteam[6:10]))==0) allbdead=1 else allbdead=0
      if(bomb==3) bexplode=1 else bexplode=0
      if(roundy==maxseconds) timesup=1 else timesup=0
      
      if(imdead==1)
      {
        lostally=lostally+1
        endround=1
      }
      else
      {
        if(othersalldead==1)
        {
          wintally=wintally+1
          endround=1
        }
        else
        {
          if(bexplode==1)
          {
            if(team==1) wintally=wintally+1 else lostally=lostally+1
            endround=1
          }
          else
          {
            if(timesup==1)
            {
              if(team==1) lostally=lostally+1 else wintally=wintally+1
              endround=1
            }
            else
            {
              if((team==1) & (allbdead==1))
              {
                wintally=wintally+1
                endround=1
              }
              else
              {
                if((team==2) & (alladead==1))
                {
                  wintally=wintally+1
                  endround=1
                }
              }
            }
          }
        }
      }
      
      if(endround==1) break
      
    }
    
  }
  
  total=wintally+lostally
  return(c(wintally,lostally,total))
}

Quote

12-18-2018 , 10:44 PM

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Some corrections:

Quote:

Originally Posted by me

By the same method, with 11 seconds I calculate 55/45 in favor of the bombers.
With 9 seconds, it's 60/40 in favor of the savers.
...
When the bomb explodes, there can be 2-10 people alive.
...Thus, there are 14 absorbing states and I'll need a 44x44 matrix.

FMP

Here is the 44x44 matrix:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
.05 0 0 0 0 0 0 0 0 .9 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 .9 0 0 0 0 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 .05 0 0 0 0 0 0 0 0 .3 0 0 0 .6 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 .3 0 0 0 0 .6 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 .05 0 0 0 0 0 0 0 0 .225 0 0 0 0 .675 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 .225 0 0 0 0 0 .675 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 .05 0 0 0 0 0 0 0 0 .18 0 0 0 0 0 .72 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 .18 0 0 0 0 0 0 .72 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 .05 0 0 0 0 0 0 0 0 .15 0 0 0 0 0 0 .75 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 .15 0 0 0 0 0 0 0 .75 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 0 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 0 0 0 0 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .36 0 0 0 0 0 .54 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .36 0 0 0 0 0 .54 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .3 0 0 0 0 0 .6 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .3 0 0 0 0 0 .6 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .257 0 0 0 0 0 .642857 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .257 0 0 0 0 0 .642857 .1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 0 0 .1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .3857 0 0 0 .5142857 0 0 .05 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .3857 0 0 0 .5142857 .1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .3375 0 0 0 .5625 0 0 .05 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .3375 0 0 0 .5625 .1 0 0 0 0 0 0 0
0 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 0 0 .05 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 .1 0 0 0 0 0
0 0 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .4 0 .5 0 0 .05 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .4 0 .5 .1 0 0 0
0 0 0 0 0 0 0 0 .05 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 0 0 .05
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .9 .1 0

Raising it to the power of 10 produces this bottom row:

Code:

.0108  .0159  .0188  .0184  .0170  .0149  .0124  .0091  .005  .4089  .2368  .1072  .0366  .0075  0  .0538  .0239  0  0  .0013 .0001  0  0  0  0  .0013  .0003  0...0

P(explosion) = sum of first 9 entries = .1223
P(team death) = sum of entries 10-14 = .797
P(bomber team wins) = .5208

P(win as a bomber) = (.2*.0108 + .3*.0159 + ... + .005) + (.1*.4089 + .2*.2368 + ... + .5*.0075) = .06739 + .1388 = .20619
P(win as a saver) = .1388 + (.2*.0538 + .3*.0239 + .4*.0013 + .5*.0001 + .7*.0013 + .8*.0003) = .15845

Tomorrow I'll write a sim. Once I either verify or fix my results, I'll compute more cases.

Quote

12-19-2018 , 04:34 AM

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

In case this helps, I ran my simulations for 9-11 seconds with 1,000,000 trials for each member of each team (meaning that the averages below are over 5,000,000 trials).

I think standard sampling theory suggests the figures below are very likely to be within around .03% of the true values (assuming my simulations correctly reflect the game rules).

Seconds	Member of Team A Win Pct	Member of Team B Win Pct
9	11.03%	23.82%
10	14.75%	19.72%
11	17.42%	17.22%

Quote

12-19-2018 , 08:06 AM

David Lyons

old hand

Join Date: May 2003 Posts: 1,459

Awesome work.

Both of you, please PM your paypal address and I'll ship you a little christmas cheer.

Quote

12-19-2018 , 11:08 AM

#10

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

I haven't earned it quite yet.

Update: I coded the solution and generalized it except for the number of players per team. However, I've yet to proofread whosnext's sim or write my own. I'll paste my code once I know my matrix is right (which, at the moment, it probably isn't). So far I coded it for finite time, but I'll also allow it to solve the infinite-time case.

Interestingly, the optimal time for team equality is not the optimal time for player equality. Player equality is maximized by t=9 seconds if my matrix is right.

Below, the output order is P(terrorists win), P(win as a terrorist), P(win as a counter-terrorist).

Code:

julia> counterstrike(10)
(0.5207579255495535,  0.20616676879062498,  0.15797064900044638)

julia> counterstrike(9)
(0.4000765135714285,  0.17916261315,  0.18848097069732142)

Quote

12-19-2018 , 01:12 PM

#11

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

I haven't looked at whosnext's code yet, but my own simulation agrees with my solution of 9 seconds, so now I'm confident.

All my code is in Julia language. Here is my sim:

Code:

@fastmath function bombsim(time::Int64, n=1000000)
    teamwins, lonewins, ctwins = 0, 0, 0
    for a=1:n
        t=0
        bombers, savers = 5, 5
        diffused = true
        while true
            p = rand(1:20)
            if p<19
                if rand(1:(bombers+savers)) ≤ bombers
                    bombers -= 1
                    if bombers==0
                        if rand(1:5) ≤ savers
                            ctwins += 1
                        end
                        break
                    end
                else
                    savers -= 1
                    if savers==0
                        teamwins += 1
                        if rand(1:5) ≤ bombers
                            lonewins += 1
                        end
                        break
                    end
                end
            elseif diffused
                diffused = false
            elseif p==19
                diffused = true
            else
                teamwins += 1
                if rand(1:5) ≤ bombers
                    lonewins += 1
                end
                break
            end
            t += 1
            if t==time
                if rand(1:5) ≤ savers
                    ctwins += 1
                end
                break
            end
        end
    end
    return teamwins, lonewins, ctwins
end

Result of 100 million trials, expressed as tallies out of 100 million:

Code:

julia> bombsim(9, 100000000)
(40004463,  17912186,  18852116)

Below is my codified matrix solution:

Code:

# Function counterstrike() assumes 5 players on each team.
# Optional parameters: b = P(explode),  d = P(diffuse), and s = P(set)
# For infinite time, input time<1
# Output: P(terrorists win), P(win as a terrorist), P(win as a CT)
# When time is infinite, there is a 4th output: E(time until explosion or a team is killed).

import LinearAlgebra.I
@fastmath function counterstrike(time::Int64, b=.05, d=.05, s=.1)
    k = 1.0-s  # P(kill when bomb is diffused)
    x = 1.0-b-d  #P(kill when bomb is set)
    T = fill(0.0, 44, 44)
    for j=1:14 begin T[j,j]=1.0 end end  # Absorbing states
    # The following would be faster if set column-wise instead of row-wise.
    T[15,:] = [b,0,0,0,0,0,0,0,0,x,0,0,0,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[16,:] = [0,0,0,0,0,0,0,0,0,k,0,0,0,0,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[17,:] = [0,b,0,0,0,0,0,0,0,0,x/3,0,0,0,2x/3,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[18,:] = [0,0,0,0,0,0,0,0,0,0,k/3,0,0,0,0,2k/3,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[19,:] = [0,0,b,0,0,0,0,0,0,0,0,x/4,0,0,0,0,3x/4,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[20,:] = [0,0,0,0,0,0,0,0,0,0,0,k/4,0,0,0,0,0,3k/4,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[21,:] = [0,0,0,b,0,0,0,0,0,0,0,0,x/5,0,0,0,0,0,4x/5,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[22,:] = [0,0,0,0,0,0,0,0,0,0,0,0,k/5,0,0,0,0,0,0,4k/5,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[23,:] = [0,0,0,0,b,0,0,0,0,0,0,0,0,x/6,0,0,0,0,0,0,5x/6,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[24,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,k/6,0,0,0,0,0,0,0,5k/6,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[25,:] = [0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,x,0,0,0,0,0,0,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[26,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,k,0,0,0,0,0,0,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[27,:] = [0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2x/5,0,0,0,0,0,3x/5,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[28,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2k/5,0,0,0,0,0,3k/5,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[29,:] = [0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,x/3,0,0,0,0,0,2x/3,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[30,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,k/3,0,0,0,0,0,2k/3,s,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[31,:] = [0,0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2x/7,0,0,0,0,0,5x/7,0,0,d,0,0,0,0,0,0,0,0,0,0,0,0]
    T[32,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2k/7,0,0,0,0,0,5k/7,s,0,0,0,0,0,0,0,0,0,0,0,0,0]
    T[33,:] = [0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,x,0,0,0,0,0,0,d,0,0,0,0,0,0,0,0,0,0]
    T[34,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,k,0,0,0,0,s,0,0,0,0,0,0,0,0,0,0,0]
    T[35,:] = [0,0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3x/7,0,0,0,4x/7,0,0,d,0,0,0,0,0,0,0,0]
    T[36,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3k/7,0,0,0,4k/7,s,0,0,0,0,0,0,0,0,0]
    T[37,:] = [0,0,0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3x/8,0,0,0,5x/8,0,0,d,0,0,0,0,0,0]
    T[38,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3k/8,0,0,0,5k/8,s,0,0,0,0,0,0,0]
    T[39,:] = [0,0,0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,k,0,0,0,0,d,0,0,0,0]
    T[40,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,k,0,0,s,0,0,0,0,0]
    T[41,:] = [0,0,0,0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4x/9,0,5x/9,0,0,d,0,0]
    T[42,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4k/9,0,5k/9,s,0,0,0]
    T[43,:] = [0,0,0,0,0,0,0,0,b,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,x,0,0,d]
    T[44,:] = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,k,s,0]

    if time>0
        pvec = (T^time)[44,:]
        teamprob = sum(pvec[1:9]) + sum(pvec[10:14])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:9
            if j<6
                ctprob += pvec[j+9]*j/10
            end
            loneprob += (j+1)pvec[j]/10
        end
        loneprob += ctprob
        for j=15:44
            if j<17
                ctprob += .2*pvec[j]
            elseif j<19
                ctprob += .3*pvec[j]
            elseif j<21 || j==25 || j==26
                ctprob += .4*pvec[j]
            elseif j<23 || j==27 || j==28
                ctprob += .5*pvec[j]
            elseif j<25 || j==29 || j==30 || j==33 || j==34
                ctprob += .6*pvec[j]
            elseif j<37
                ctprob += .7*pvec[j]
            elseif j<41
                ctprob += .8*pvec[j]
            elseif j<43
                ctprob += .9*pvec[j]
            else ctprob += pvec[j] end
        end
        return teamprob, loneprob, ctprob
    else
        R = T[15:44, 1:14]
        Q = T[15:44, 15:44]
        F = inv(I-Q)
        P = (F*R)[30,:]
        duration = sum(F[30,:])
        teamprob = sum(P[1:9]) + sum(P[10:14])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:9
            if j<6
                ctprob += P[j+9]*j/10
            end
            loneprob += (j+1)P[j]/10
        end
        loneprob += ctprob
        return teamprob, loneprob, ctprob, duration
    end
end

Solution to the infinite-time case:

Code:

julia> counterstrike(0)
(0.562297214301327,  0.21553180366061836,  0.14754360663330884,  8.71631329265979)

Large time values indeed approach those values. The 4th number is the expected time before an end to the match.

The function has 3 optional parameters whose default values are those ITT.

In Julia, a function executes slowly on its first run of a session because that's when it compiles. This function is fast on its next runs. It can be sped up a bit by defining the matrix column-wise (like Julia prefers), which I didn't do because I already had it typed out row-wise.

Quote

12-19-2018 , 03:18 PM

#12

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

I have looked at heehaww's code and am not sure we are handling the "reroll" possibility in the same way.

Could this be why we are getting different results?

Quote

12-19-2018 , 04:08 PM

#13

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Oh good catch. I had it as a static 90% chance of someone dying, and then if someone dies, a 1/n chance that you die (where n = # living players). But rereading the OP, it should be a 9n/(9n + 10) chance of someone dying.

I'll tweak both codes accordingly.

Quote

12-19-2018 , 07:14 PM

#14

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

New sim:

Code:

@fastmath function bombsim(time::Int64, n=1000000)
    teamwins, lonewins, ctwins = 0, 0, 0
    for a=1:n
        t = 0
        bombers, savers, p = 5, 5, 10
        c = 1/(9p+10)
        bombset = false
        while true
            r = rand(1)[1]
            if r < 10c
                if !bombset
                    bombset = true
                elseif r < 5c
                    bombset = false
                else
                    teamwins += 1
                    if rand(1:5) ≤ bombers
                        lonewins += 1
                    end
                    break
                end
            elseif rand(1:p) ≤ bombers
                bombers -= 1
                if bombers==0
                    if rand(1:5) ≤ savers
                        ctwins += 1
                    end
                    break
                else
                    p -= 1
                    c = 1/(9p+10)
                end
            else
                savers -= 1
                if savers==0
                    teamwins += 1
                    if rand(1:5) ≤ bombers
                        lonewins += 1
                    end
                    break
                else
                    p -= 1
                    c = 1/(9p+10)
                end
            end
            t += 1
            if t==time
                if rand(1:5) ≤ savers
                    ctwins += 1
                end
                break
            end
        end
    end
    return teamwins, lonewins, ctwins
end

One million trials:

Code:

julia> bombsim(11)
(591894, 244983, 136680)

julia> bombsim(10)
(539063, 231280, 152511)

julia> bombsim(9)
(404276, 198618, 191671)

julia> bombsim(8)
(261545, 152924, 254020)

Different probabilities than before, but it still likes 9 seconds.

Result of 9 seconds after 10 million trials:

Code:

julia> bombsim(9,10000000)
(4048826, 1988009, 1913304)

I'll tweak the matrix tomorrow.

Quote

12-19-2018 , 08:09 PM

#15

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

Honestly, I have doubts about your results (no offense).

My simulation code is so simple that I cannot believe it can be wrong (I hate how that sounds). It truly walks through David's game rules one line at a time in a very obvious way.

If you have a minute, and it would literally take no more than a minute, could you take a look at my simulation code and see if you spot anything wrong and/or different than what you coded/think are the game rules.

My code takes as input the identify of the chosen player (a number from 1-10) and the number of seconds of game play. It walks through the game rules and then returns if the chosen player wins or loses that game.

My guess is that we have coded different game rules. Or perhaps we have different win/loss rules. Does every game in your simulation result in either a win or a loss no matter which is the chosen player? Do you faithfully follow David's win/loss assessment hierarchy?

P.S. For example, I cannot easily tell if we are assigning win/loss the same if the bomb explodes. Which is probably a failing on my part in not being able to follow your code.

.

Last edited by whosnext; 12-19-2018 at 08:22 PM.

Quote

12-19-2018 , 11:02 PM

#16

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Quote:

Originally Posted by whosnext

Honestly, I have doubts about your results (no offense).

None taken, I do too.

Quote:

Does every game in your simulation result in either a win or a loss no matter which is the chosen player?

Every game has a winning team, all of whose living members are winners. My sim doesn't involve choosing a player. It determines which team wins and then tallies the times you would have won had you chosen a random player from that team.

Quote:

Do you faithfully follow David's win/loss assessment hierarchy?

I'm not sure. I think you and I handled an edge case differently. If Bob is a bomber and the last saver dies during the last second, I count that as a win for Bob. It appears to me that you count it as a loss (unless his teammates are all dead) because you start the timer at 1 whereas i start it at 0. Philosophically I think it makes more sense to start it at 0 because the action happens during the second, not after the tick. And if we were counting down, it's like I started the timer at 10 while you started it at 9. The way I did it, the time can't expire at the same time as another end condition. Once the time expires, that's it, you can't kill someone after that. And vice versa: if you eliminate the enemy team, that's game over and the clock stops whether there are 5 seconds remaining or 0.5 seconds.

However, I doubt that scenario explains the large difference between our results.

Another small thing: it looks to me like you reroll 99 times. I'm referring to "for(draw1 in 1:100)". Instead, why not use a while-loop, allowing you to reroll as many times as necessary? (Or there's a more efficient route: shrink the sample space each iteration so that repeats are impossible, making rerolls unnecessary.)

Last edited by heehaww; 12-19-2018 at 11:12 PM.

Quote

12-19-2018 , 11:44 PM

#17

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

Quote:

Originally Posted by heehaww

Another small thing: it looks to me like you reroll 99 times. I'm referring to "for(draw1 in 1:100)". Instead, why not use a while-loop, allowing you to reroll as many times as necessary? (Or there's a more efficient route: shrink the sample space each iteration so that repeats are impossible, making rerolls unnecessary.)

I only reroll as many times as necessary (with a max of 99 times) due to the Break conditions. If I admit that while-loops are at the extremes of my programming capabilities, would you now believe that I am not a programmer? Please don't judge.

I don't know why we are getting such different results. The timing issue associated with that edge-case may be something (I tried to follow David's hierarchy) but I agree that it is unlikely to cause such large differences.

Quote

12-20-2018 , 04:51 AM

#18

nickthegeek

journeyman

Join Date: Sep 2011 Posts: 273

I'm not giving much contribution and I just gave a look at whosenext's code, being R more familiar to me. However, I spotted one thing that let me question whether I got the rules correctly.

Whosenext, it seems to me that you allow in a given second/round that the following might happen:

- a player is killed AND the bomb changes status;
- no player is killed AND the bomb doesn't change status.

By reading the rules, I had the impression that one and only one thing had to happen: there is a single roll (it seems to me that you roll twice, once for killing players and once for the bomb) and at the end something has to happen: someone is killed or the bomb changes status (but noth both).

The above interpretation has in no way to be correct; it is just suggested from the fact that probabilities sum always to 100%. It might also explain the differences you and heehaww are getting: as the players get killed, a bomb explosion gets more likely in my interpretation (not sure if it's the same than heehaww's), while for you it stays static for all the game.

Last edited by nickthegeek; 12-20-2018 at 05:04 AM.

Quote

12-20-2018 , 07:48 AM

#19

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

I think nickthegeek is right. The bomb status should only change if drawkill>90. Furthermore, every time drawkill>90, the bomb status should change. This is probably why our results differ. In my code, the bomb status changes XOR someone is killed.

Quote:

Originally Posted by whosnext

If I admit that while-loops are at the extremes of my programming capabilities, would you now believe that I am not a programmer? Please don't judge.

Lol! It never occurred to me that someone might know for-loops but not while-loops. I'm not judging, it only means you didn't spend the extra 15 seconds reading about while-loops. I'll do you one better: back in middle/high school, all my programming was in TI-Basic on my calculator. I wrote all kinds of spaghetti code with Goto/Label statements rather than spend literally one minute reading about for/while. Finally in college I had to take a Java course and Java has no goto's to speak of, so I was forced to learn for/while, making life easier ever since.

Anyway, instead of 99 rerolls you can have infinity by saying "while(validdraw1 < 1)", or better yet, "while(true)" with break conditions (and you wouldn't need the variable validdraw1*). In general, while() opens up the possibility of the code's execution never finishing, but if that happens you know the bug is in your while-loop break conditions.

*Actually you don't need it in the for-loop either. Instead of setting validdraw1=1, just break right then.

Another minor detail: you should use the "else" statement more. All your "if drawkill" conditions are mutually exclusive, so that part would be faster as an if-else chain (or equivalently, a switch statement, but let's not go there

). In this case we're talking microseconds but still.

Last edited by heehaww; 12-20-2018 at 07:56 AM.

Quote

12-20-2018 , 01:32 PM

#20

whosnext

Carpal \'Tunnel

Join Date: Mar 2009 Posts: 6,732

Yes, thanks nick, that is undoubtedly why we are getting different results. I will now happily bow out of the conversation.

Quote

12-31-2018 , 05:40 PM

#21

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

At long last, I redid the matrix. This time I generalized the code to handle any team size (but not unequal team sizes).

Code:

# Optional parameters: x = P(explode),  d = P(defuse),  s = P(set),  teamsize (teams assumed to be equal in size).
# If cplrs=0 then cplrs will match teamsize.
# For infinite time, input time ≤ 0
# Output: P(terrorists win), P(win as a terrorist), P(win as a CT)
# When time is infinite, there is a 4th output: E(time until explosion or a team is killed).
import LinearAlgebra.I
@fastmath function counterstrike(time::Int64, x=.05, d=.05, s=.1, teamsize=5)
    teamsize<1 && throw(DomainError(teamsize, "teamsize must be greater than 0"))
    players = 2*teamsize
    plrecip = 1/players
    b = x+d
    xrat = x/b
    k = (1-s)/players   # P(die when bomb is defused)
    z = (1-b)/players   # P(die when bomb is set)
    a = 3*teamsize - 1  # of abosrbing states
    NA = (teamsize+1)teamsize  # of non-absorbing states
    Len = a + NA
    T = fill(0.0, Len, Len)  # Transition matrix
    # The first (players-1) rows of T will be exploded states, in order from 2 to all players being alive at the time of explosion.
    # The next (teamsize) rows will be ones where a team is killed, in order from the winning team having 1 to all players alive.
        for j=1:a begin T[j,j]=1.0 end end
    # After that, rows of opposite parity represent opposite bomb states (activated vs defused).
    # Row a+1 represents the state of one player remaining on each team while the bomb is activated.
    # The next rows (of the same parity) decrease one team's player count.
    # Every so many rows (see "newDiag"), the player counts are equal again (but greater than the last time they were equal).
    newDiag = fill(1, teamsize)
    survivors = fill(0, NA)
    for j=2:(teamsize) begin newDiag[j] = 1 +2(j-1)teamsize -(j-1)*(j-2) end end
    for j=1:NA
        for m=2:teamsize
            if j<newDiag[m]
                survivors[j] = ceil((j+1-newDiag[m-1])/2) + 2m-3
                break
            end
        end
        if survivors[j]==0 begin  survivors[j] = ceil((j+1-newDiag[teamsize])/2) + players-1 end end
    end
    # Set the death transitions for the first (players) non-absorbing rows.
    Lcol = players
    Rcol = players+teamsize
    parityMatch = false
    T[a+1, Lcol] = 2k/(2k+b)
    T[a+2, Lcol] = 2z/(2z+s)
    for r=(a+3):(a+players)
        living = survivors[r-a]
        parityMatch = !parityMatch
        if parityMatch
            Lcol += 1
            killprob = k*living/(k*living + b)
        else killprob = z*living/(z*living + s) end
        T[r, Lcol] = killprob / living
        T[r, Rcol] = killprob*(living-1)/living
        Rcol += 1
    end
    # Set the death transitions for the remaining rows.
    Lcol += 1
    minority = 1
    isNewDiag = false
    for r=(a+players+1):Len
        living = survivors[r-a]
        parityMatch = !parityMatch
        if parityMatch begin killprob = k*living/(k*living + b) end
        else killprob = z*living/(z*living + s) end
        if parityMatch && in(r-a, newDiag)
            isNewDiag = true
            Lcol += 2
            minority += 1
            T[r,Lcol] = killprob
        elseif !parityMatch && isNewDiag
            T[r,Lcol] = killprob
            isNewDiag = false
        else
            T[r,Lcol] = killprob * minority / living
            T[r,Rcol] = killprob * (living-minority)/living
        end
        Lcol+=1; Rcol+=1
    end
    # Set the transitions to different bomb states.
    r = a+1
    for startCol=1:2:(players-1) , c = startCol:(startCol + teamsize - Int64((startCol+1)/2) )
        T[r,c] = xrat*(1-sum(T[r,:]))  # Explode
        r += 2
    end
    for j=(a+1):2:Len-1 begin T[j,j+1] = 1-sum(T[j,:]) end end  # Defuse
    for j=(a+2):2:Len   begin T[j,j-1] = 1-sum(T[j,:]) end end  # Activate
    # Ready to calculate.
    if time>0
        pvec = (T^time)[Len,:]
        teamprob = sum(pvec[1:(players-1)]) + sum(pvec[players : a])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:(players-1) begin loneprob += (j+1)pvec[j]*plrecip end end
        for j = players:a   begin ctprob += (j+1-players)pvec[j]*plrecip end end
        loneprob += ctprob
        for j=1:NA begin ctprob += survivors[j] * pvec[j+a] * plrecip end end
        return teamprob, loneprob, ctprob
    else
        R = T[(a+1):Len, 1:a]
        Q = T[(a+1):Len, (a+1):Len]
        F = inv(I-Q)
        P = (F*R)[NA,:]
        duration = sum(F[NA,:])
        teamprob = sum(P[1:(players-1)]) + sum(P[players:a])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:(players-1) begin loneprob += (j+1)P[j]*plrecip end end
        for j = players:a   begin ctprob += (j+1-players)*P[j]*plrecip end end
        loneprob += ctprob
        return teamprob, loneprob, ctprob, duration
    end
end

If you want to see the matrix it generated, then put "println(T)" between lines 85 and 87.

The results agree with my sim from post #14:

Code:

1 → (0.0, 0.0, 0.91)
2 → (0.005, 0.005, 0.81589010989011)
3 → (0.015379181258302125, 0.014341263132471912, 0.7189441818031874)
4 → (0.03161379859509388, 0.02733395700190532, 0.6205355070565856)
5 → (0.05634822908427707, 0.04528072849984882, 0.522167575287478)
6 → (0.0959105566388053, 0.07125578084606343, 0.42585231429052056)
7 → (0.16043761251058905, 0.10776071684429792, 0.33482976812502535)
8 → (0.2614147853178065, 0.1531586750055719, 0.2543038013283795)
9 → (0.40470396380767615, 0.19888750000520844, 0.1914073723866078)
10 → (0.5390129729040498, 0.23122395924484618, 0.15283551482067947)
11 → (0.5912088767940508, 0.24464846623616365, 0.13705128883275666)
12 → (0.6296702413651585, 0.25288855520432313, 0.12822582630539767)
...
100 → (0.6454111122434181, 0.25636435478904657, 0.1245021329656542)
...
∞ → (0.6454111122434181, 0.2563643547890465, 0.12450213296565416, 8.963023146388943)

(The pink .005's were actually 0.0049999999999999975 due to floating-point error.)

With infinite time, the average duration is 8.963 seconds. It is only a coincidence that the rounded average is the most equitable, because it's not with other parameters I tried.

Last edited by heehaww; 12-31-2018 at 05:46 PM.

Quote

01-01-2019 , 05:34 PM

#22

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

It occurred to me that we can easily extend this to continuous time. For instance, the probability of a transition in half a second is simply 1/2 the whole-second probability. We don't need to model "half-transitions" nor add more states.

If n is the time's integer part and f is the decimal part, then take T^n and multiply by a second matrix (call it V) with the f-second probabilities. To create V, first multiply all the non-absorbing states by f. Then, fill in the probabilities of staying in the same state (which can happen in a fractional second), which is 1-P(transition), where P(transition) is the sum of the rest of the row.

For the time input, the updated code below accepts either a Float64 or Int64. I've renamed the function to cs().

Code:

# Optional parameters: x = P(explode),  d = P(defuse),  s = P(set),  teamsize (teams assumed to be equal in size).
# If cplrs=0 then cplrs will match teamsize.
# For infinite time, input time ≤ 0
# Output: P(terrorists win), P(win as a terrorist), P(win as a CT)
# When time is infinite, there is a 4th output: E(time until explosion or a team is killed).
import LinearAlgebra.I
@fastmath function cs(time::Int64, x=.05, d=.05, s=.1, teamsize=5)
    fpart, ipart = modf(time)
    if time>0.0
        fracsec = (fpart>0.0)
        if fracsec begin wholesec = Int64(ipart) end
        else wholesec = Int64(time) end
    else fracsec=false end
    teamsize<1 && throw(DomainError(teamsize, "teamsize must be greater than 0"))
    players = 2*teamsize
    plrecip = 1/players
    b = x+d
    xrat = x/b
    k = (1-s)/players   # P(die when bomb is defused)
    z = (1-b)/players   # P(die when bomb is set)
    a = 3*teamsize - 1  # of abosrbing states
    NA = (teamsize+1)teamsize  # of non-absorbing states
    Len = a + NA
    T = fill(0.0, Len, Len)  # Transition matrix
    # The first (players-1) rows of T will be exploded states, in order from 2 to all players being alive at the time of explosion.
    # The next (teamsize) rows will be ones where a team is killed, in order from the winning team having 1 to all players alive.
        for j=1:a begin T[j,j]=1.0 end end
    # After that, rows of opposite parity represent opposite bomb states (activated vs defused).
    # Row a+1 represents the state of one player remaining on each team while the bomb is activated.
    # The next rows (of the same parity) decrease one team's player count.
    # Every so many rows (see "newDiag"), the player counts are equal again (but greater than the last time they were equal).
    newDiag = fill(1, teamsize)
    survivors = fill(0, NA)
    for j=2:(teamsize) begin newDiag[j] = 1 +2(j-1)teamsize -(j-1)*(j-2) end end
    for j=1:NA
        for m=2:teamsize
            if j<newDiag[m]
                survivors[j] = ceil((j+1-newDiag[m-1])/2) + 2m-3
                break
            end
        end
        if survivors[j]==0 begin  survivors[j] = ceil((j+1-newDiag[teamsize])/2) + players-1 end end
    end
    # Set the death transitions for the first (players) non-absorbing rows.
    Lcol = players
    Rcol = players+teamsize
    parityMatch = false
    T[a+1, Lcol] = 2k/(2k+b)
    T[a+2, Lcol] = 2z/(2z+s)
    for r=(a+3):(a+players)
        living = survivors[r-a]
        parityMatch = !parityMatch
        if parityMatch
            Lcol += 1
            killprob = k*living/(k*living + b)
        else killprob = z*living/(z*living + s) end
        T[r, Lcol] = killprob / living
        T[r, Rcol] = killprob*(living-1)/living
        Rcol += 1
    end
    # Set the death transitions for the remaining rows.
    Lcol += 1
    minority = 1
    isNewDiag = false
    for r=(a+players+1):Len
        living = survivors[r-a]
        parityMatch = !parityMatch
        if parityMatch begin killprob = k*living/(k*living + b) end
        else killprob = z*living/(z*living + s) end
        if parityMatch && in(r-a, newDiag)
            isNewDiag = true
            Lcol += 2
            minority += 1
            T[r,Lcol] = killprob
        elseif !parityMatch && isNewDiag
            T[r,Lcol] = killprob
            isNewDiag = false
        else
            T[r,Lcol] = killprob * minority / living
            T[r,Rcol] = killprob * (living-minority)/living
        end
        Lcol+=1; Rcol+=1
    end
    # Set the transitions to different bomb states.
    r = a+1
    for startCol=1:2:(players-1) , c = startCol:(startCol + teamsize - Int64((startCol+1)/2) )
        T[r,c] = xrat*(1-sum(T[r,:]))  # Explode
        r += 2
    end
    for j=(a+1):2:Len-1 begin T[j,j+1] = 1-sum(T[j,:]) end end  # Defuse
    for j=(a+2):2:Len   begin T[j,j-1] = 1-sum(T[j,:]) end end  # Activate
    # If there is a fractional second, create matrix V which scales down T's non-absorbing probabilities.
    if fracsec
        V = T*fpart
        for j=1:a begin V[j,j]=1.0 end end
        for j=(a+1):Len begin V[j,j] = 1-sum(V[j,:]) end end  # The probability of staying in the same state.
    end
    # Done creating matrices and ready to calculate.
    if time>0.0
        if fracsec begin pvec = ((T^wholesec)*V)[Len,:] end
        else pvec = (T^wholesec)[Len,:] end
        teamprob = sum(pvec[1:(players-1)]) + sum(pvec[players : a])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:(players-1) begin loneprob += (j+1)pvec[j]*plrecip end end
        for j = players:a   begin ctprob += (j+1-players)pvec[j]*plrecip end end
        loneprob += ctprob
        for j=1:NA begin ctprob += survivors[j] * pvec[j+a] * plrecip end end
        return teamprob, loneprob, ctprob
    else
        R = T[(a+1):Len, 1:a]
        Q = T[(a+1):Len, (a+1):Len]
        F = inv(I-Q)
        P = (F*R)[NA,:]
        duration = sum(F[NA,:])
        teamprob = sum(P[1:(players-1)]) + sum(P[players:a])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:(players-1) begin loneprob += (j+1)P[j]*plrecip end end
        for j = players:a   begin ctprob += (j+1-players)*P[j]*plrecip end end
        loneprob += ctprob
        return teamprob, loneprob, ctprob, duration
    end
end
function cs(time::Int64, x=.05, d=.05, s=.1, teamsize=5)
    return cs(Float64(time),x,d,s,teamsize)
end

The results make sense:

Code:

cs(8) = (0.2614147853178065, 0.1531586750055719, 0.2543038013283795)
cs(8.2) = (0.2900726210157803, 0.16230444000549918, 0.2417245155400252)
cs(8.4) = (0.31873045671375433, 0.17145020500542657, 0.22914522975167073)
cs(8.6) = (0.3473882924117282, 0.18059597000535382, 0.2165659439633165)
cs(8.8) = (0.3760461281097023, 0.1897417350052812, 0.20398665817496217)
cs(9) = (0.40470396380767615, 0.19888750000520844, 0.1914073723866078)

The benefit of fractional times is that you can get the individual player probabilities arbitrarily close to equal.

Via manual trial and error, I've found that 8.9311382266 seconds gets it pretty darn close:

Code:

cs(8.9311382266)[2] = 0.19573853202023522
cs(8.9311382266)[3] = 0.19573853202406527

Quote

01-02-2019 , 03:46 PM

#23

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

I've written two functions that call on cs() multiple times to optimize the time: one for player equality and one for team equality.

First, the algorithm starts with 5 seconds and doubles until the time is too large. Once that upper bound is determined, it has a finite range to search. It splits the range into two, tries the middle value of the middle of the range, and depending on whether that's higher/lower than optimum, repeats the process with the lower/upper half of the range.

It stops searching when the errMargin and probMargin inputs are satisfied.
errMargin specifies how many seconds the answer is allowed to be off by.
probMargin specifies how small of a probability difference you want.
You can specify both margins, or only errMargin, or you can set errMargin=0.0 and then a nonzero value for probMargin. Setting both to 0.0 will throw an error message to avoid a non-terminating loop.

The output of fairtime() is ( time, probability difference, P(bombers win) )
The output of teamfairtime() is (time, P(bomber team wins), probability difference)
The probability difference is not absolute; it's P(bomber wins) - P(saver wins)

Also, some changes to cs():
- I fixed the result cs(0). Rather than let that be infinite time, it should return (0,0,1). Infinite time is still possible with a negative input.
- I've inlined it, which might make it faster for the optimizer functions to call.
- I've reordered the outputs: P(bomber team wins) is now the 3rd element of the tuple instead of 1st.

Given those changes, I'll repaste all code. The optimizer functions are at the bottom.

Code:

# Optional parameters: x = P(explode),  d = P(defuse),  s = P(set),  teamsize (teams assumed to be equal in size).
# If cplrs=0 then cplrs will match teamsize.
# For infinite time, input time < 0
# Output: P(win as a terrorist), P(win as a CT), P(terrorists win)
# When time is infinite, there is a 4th output: E(time until explosion or a team is killed).
import LinearAlgebra.I
function cs(time::Int64, x=.05, d=.05, s=.1, teamsize=5)
    return cs(Float64(time),x,d,s,teamsize)
end
@inline @fastmath function cs(time::Float64, x=.05, d=.05, s=.1, teamsize=5)
    time==0.0 && return 0,0,1
    fpart, ipart = modf(time)
    if time>0.0
        fracsec = (fpart>0.0)
        if fracsec begin wholesec = Int64(ipart) end
        else wholesec = Int64(time) end
        else fracsec=false end
    teamsize<1 && throw(DomainError(teamsize, "teamsize must be greater than 0"))
    players = 2*teamsize
    plrecip = 1/players
    b = x+d
    xrat = x/b
    k = (1-s)/players   # P(die when bomb is defused)
    z = (1-b)/players   # P(die when bomb is set)
    a = 3*teamsize - 1  # of abosrbing states
    NA = (teamsize+1)teamsize  # of non-absorbing states
    Len = a + NA
    T = fill(0.0, Len, Len)  # Transition matrix
    # The first (players-1) rows of T will be exploded states, in order from 2 to all players being alive at the time of explosion.
    # The next (teamsize) rows will be ones where a team is killed, in order from the winning team having 1 to all players alive.
        for j=1:a begin T[j,j]=1.0 end end
    # After that, rows of opposite parity represent opposite bomb states (activated vs defused).
    # Row a+1 represents the state of one player remaining on each team while the bomb is activated.
    # The next rows (of the same parity) decrease one team's player count.
    # Every so many rows (see "newDiag"), the player counts are equal again (but greater than the last time they were equal).
    newDiag = fill(1, teamsize)
    survivors = fill(0, NA)
    for j=2:(teamsize) begin newDiag[j] = 1 +2(j-1)teamsize -(j-1)*(j-2) end end
    for j=1:NA
        for m=2:teamsize
            if j<newDiag[m]
                survivors[j] = ceil((j+1-newDiag[m-1])/2) + 2m-3
                break
            end
        end
        if survivors[j]==0 begin  survivors[j] = ceil((j+1-newDiag[teamsize])/2) + players-1 end end
    end
    # Set the death transitions for the first (players) non-absorbing rows.
    Lcol = players
    Rcol = players+teamsize
    parityMatch = false
    T[a+1, Lcol] = 2k/(2k+b)
    T[a+2, Lcol] = 2z/(2z+s)
    for r=(a+3):(a+players)
    	living = survivors[r-a]
        parityMatch = !parityMatch
        if parityMatch
            Lcol += 1
            killprob = k*living/(k*living + b)
        else killprob = z*living/(z*living + s) end
        T[r, Lcol] = killprob / living
        T[r, Rcol] = killprob*(living-1)/living
        Rcol += 1
    end
    # Set the death transitions for the remaining rows.
    Lcol += 1
    minority = 1
    isNewDiag = false
    for r=(a+players+1):Len
        living = survivors[r-a]
        parityMatch = !parityMatch
        if parityMatch begin killprob = k*living/(k*living + b) end
        else killprob = z*living/(z*living + s) end
        if parityMatch && in(r-a, newDiag)
            isNewDiag = true
            Lcol += 2
            minority += 1
            T[r,Lcol] = killprob
        elseif !parityMatch && isNewDiag
            T[r,Lcol] = killprob
            isNewDiag = false
        else
            T[r,Lcol] = killprob * minority / living
            T[r,Rcol] = killprob * (living-minority)/living
        end
        Lcol+=1; Rcol+=1
    end
    # Set the transitions to different bomb states.
    r = a+1
    for startCol=1:2:(players-1) , c = startCol:(startCol + teamsize - Int64((startCol+1)/2) )
        T[r,c] = xrat*(1-sum(T[r,:]))  # Explode
        r += 2
    end
    for j=(a+1):2:Len-1 begin T[j,j+1] = 1-sum(T[j,:]) end end  # Defuse
    for j=(a+2):2:Len   begin T[j,j-1] = 1-sum(T[j,:]) end end  # Activate
    # If there is a fractional second, create matrix V which scales down T's non-absorbing probabilities.
    if fracsec
        V = T*fpart
        for j=1:a begin V[j,j]=1.0 end end
        for j=(a+1):Len begin V[j,j] = 1-sum(V[j,:]) end end  # The probability of staying in the same state.
    end
    # Done creating matrices and ready to calculate.
    if time>0.0
        if fracsec begin pvec = ((T^wholesec)*V)[Len,:] end
        else pvec = (T^wholesec)[Len,:] end
        teamprob = sum(pvec[1:(players-1)]) + sum(pvec[players : a])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:(players-1) begin loneprob += (j+1)pvec[j]*plrecip end end
        for j = players:a   begin ctprob += (j+1-players)pvec[j]*plrecip end end
        loneprob += ctprob
        for j=1:NA begin ctprob += survivors[j] * pvec[j+a] * plrecip end end
        return loneprob, ctprob, teamprob
    else
        R = T[(a+1):Len, 1:a]
        Q = T[(a+1):Len, (a+1):Len]
        F = inv(I-Q)
        P = (F*R)[NA,:]
        duration = sum(F[NA,:])
        teamprob = sum(P[1:(players-1)]) + sum(P[players:a])/2
        loneprob, ctprob = 0.0, 0.0
        for j=1:(players-1) begin loneprob += (j+1)P[j]*plrecip end end
        for j = players:a   begin ctprob += (j+1-players)*P[j]*plrecip end end
        loneprob += ctprob
        return loneprob, ctprob, teamprob, duration
    end
end

# Function to optimize time for player equality, until within the desired time error margin or probability difference or both.
@fastmath function fairtime(errMargin::Float64, probMargin=0.0, x=.05, d=.05, s=.1, teamsize=5)
    errMargin==0.0 && probMargin==0.0 && throw(ErrorException("errMargin and probMargin cannot both be zero"))
    time=5.0; step=0.0
    p,q,w = 0.0, 0.0, 0.0
    while(true)
        p,q,w = cs(time)
        if p<q begin time*=2 end
        elseif p>q
            step = time/4
            time *= .75
            break
        else break end
    end
    pdiff = abs(p-q)
    while(step>errMargin || pdiff>probMargin)
        p,q,w = cs(time)
        if p<q begin time += step end
        elseif p>q begin time -= step end
        else break end
        step /= 2
        pdiff = abs(p-q)
    end
    return time, p-q, w
end
# Function to optimize team equality.
@fastmath function teamfairtime(errMargin::Float64, probMargin=0.0, x=.05, d=.05, s=.1, teamsize=5)
errMargin==0.0 && probMargin==0.0 && throw(ErrorException("errMargin and probMargin cannot both be zero"))
    time=5.0; step=0.0
    p,q,w = 0.0, 0.0, 0.0
    while(true)
        p,q,w = cs(time)
        if w<.5 begin time*=2 end
        elseif w>.5
            step = time/4
            time *= .75
            break
        else break end
    end
    pdiff = abs(w-0.5)
    while(step>errMargin || pdiff>probMargin)
        p,q,w = cs(time)
        if w<.5 begin time += step end
        elseif w>.5 begin time -= step end
        else break end
        step /= 2
        pdiff = abs(w-0.5)
    end
    return time, w, p-q
end

Demonstration:

Code:

fairtime(.00001) = (8.931140899658203, 2.362220092005929e-6, ...)
fairtime(0.0, .00001) = (8.931198120117188, -1.78150449983705e-6, ...)
fairtime(.0000000000001, .0000000000001) = (8.931138226635227, 1.199040866595169e-14, ...)
fairtime(.00000000000001) = (8.931138226635245, 3.885780586188048e-16, ...)

Quote

01-02-2019 , 11:33 PM

#24

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Brainfart earlier. To avoid a never-ending loop, you'd want both margins to be nonzero. But actually, the loop finishes regardless (and quickly), so you can have either/both equal to 0. I think what makes it finish is the fact that the floating-point number line isn't continuous. Once you get close enough to 0, the next smallest float is 0. I've defaulted both margin inputs to 0.

Also, for errMargin to do what I described, the function has to compare "step" to half the errMargin.

And I tweaked the outputs.

Code:

@fastmath function fairtime(errMargin=0.0, probMargin=0.0, x=.05, d=.05, s=.1, teamsize=5)
    errMargin /= 2
    ...
    return time, p, p-q, w

Code:

@fastmath function teamfairtime(errMargin=0.0, probMargin=0.0, x=.05, d=.05, s=.1, teamsize=5)
    errMargin /= 2
    ...
    return time, w, w-.5, p, q

Now, all the inputs are optional, so if you like the defaults then you can just type fairtime()

Code:

julia> fairtime()
(8.931138226635259, 0.19573853202184754, 0.0, 0.39483681687288674)

Last edited by heehaww; 01-02-2019 at 11:41 PM.

Quote

01-03-2019 , 11:41 AM

#25

heehaww

Pooh-Bah

Join Date: Aug 2011 Posts: 5,081

Quote:

step = time/4

Should be time/8. No effect on the answer, but there was a wasted iteration.

This is hopefully my last code post / bump ITT

Quote

Page 1 of 2

First

1 2

Last

Post Reply Subscribe

...

Page 1 of 2

First

1 2

Last