fork download
copy 
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <time.h>
  5. using namespace std;
  6.  
  7. static const float    CONTROL_WR = 0.8f;
  8. static const float    AGGRO_WR   = 0.65f;
  9. static const unsigned STARS      = 5 * 5 + 5 * 4 + 5 * 3; //From rank 20: 5 ranks with 3 stars, 5 ranks with 4, 5 with 5
  10. static const unsigned REPEATS    = 10000; //Higher is slower and more accurate estimate of expected number of games needed
  11.  
  12. //Flip a coin that lands on "heads" with probability p
  13. bool trial(float p)
  14. {
  15.     float r = (float)((float)rand() / (float)RAND_MAX);
  16.     return r < p;
  17. }
  18.  
  19. class RunningStat //See: http://w...content-available-to-author-only...k.com/blog/standard_deviation/
  20. {
  21. public:
  22.     RunningStat() : m_n(0) {}
  23.  
  24.     void Clear()
  25.     {
  26.         m_n = 0;
  27.     }
  28.  
  29.     void Push(float x)
  30.     {
  31.         m_n++;
  32.  
  33.         // See Knuth TAOCP vol 2, 3rd edition, page 232
  34.         if (m_n == 1)
  35.         {
  36.             m_oldM = m_newM = x;
  37.             m_oldS = 0.0;
  38.         }
  39.         else
  40.         {
  41.             m_newM = m_oldM + (x - m_oldM)/m_n;
  42.             m_newS = m_oldS + (x - m_oldM)*(x - m_newM);
  43.  
  44.             // set up for next iteration
  45.             m_oldM = m_newM; 
  46.             m_oldS = m_newS;
  47.         }
  48.     }
  49.  
  50.     int NumDataValues() const
  51.     {
  52.         return m_n;
  53.     }
  54.  
  55.     float Mean() const
  56.     {
  57.         return (m_n > 0) ? m_newM : 0.0;
  58.     }
  59.  
  60.     float Variance() const
  61.     {
  62.         return ( (m_n > 1) ? m_newS/(m_n - 1) : 0.0 );
  63.     }
  64.  
  65.     float StandardDeviation() const
  66.     {
  67.         return sqrt( Variance() );
  68.     }
  69.  
  70. private:
  71.     int m_n;
  72.     float m_oldM, m_newM, m_oldS, m_newS;
  73. };
  74.  
  75. int main(int argc, char* argv[]) 
  76. {
  77.     //Initialize a random seed.
  78.     //Can consider using something better than the standard built-in rand(). Google: Mersenne Twister
  79.     srand(time(NULL));
  80.  
  81.     RunningStat stat;
  82.     float    wr = AGGRO_WR;
  83.  
  84.     for (unsigned iteration = 0; iteration < REPEATS; ++iteration)
  85.     {
  86.         unsigned cur_stars = 0; //This is unsigned and zero-based because we're simulating from rank 20. If you want to start at 10 or something, change to signed and take into account negatives
  87.         unsigned streak    = 0; //Streak length
  88.         unsigned games     = 0; //How many games played
  89.         while (cur_stars < STARS)
  90.         {
  91.             ++games;
  92.             if (trial(wr)) //if we won the game
  93.             {
  94.                 ++cur_stars;
  95.                 ++streak;
  96.             }
  97.             else
  98.             {
  99.                 if (cur_stars > 0)
  100.                 {
  101.                     --cur_stars;
  102.                 }
  103.                 streak = 0;
  104.             }
  105.  
  106.             if (streak > 2)
  107.             {
  108.                 ++cur_stars;
  109.             }
  110.         }
  111.         stat.Push((float)games);
  112.     }
  113.  
  114.     cout << "After " << REPEATS << " attempts, it took an average of " << stat.Mean() << " games at a win-rate of " << wr << " with a standard deviation of " << stat.StandardDeviation() << endl;
  115.  
  116.     //std::cout << std::endl << "Hurray! It took " << games << " games at a win-rate of " << wr << " to reach Rank 5" << std::endl;
  117.  
  118.     return 0;
  119. }
Success #stdin #stdout 0.03s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
After 10000 attempts, it took an average of 105.12 games at a win-rate of 0.65 with a standard deviation of 28.0303
https://ideone.com/5b22a1
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!