Announcement

Collapse
No announcement yet.

Semi-Scientific Study of the Civ3 Random Number Generator

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Semi-Scientific Study of the Civ3 Random Number Generator

    The following are the results of tests I have performed to help determine whether or not the random number generator used by Civ3 is in fact faulty. Many have alleged, including myself, that the random number generator is too "streaky." The following numbers are the results of 10,000,000 simulated encounters* between common ancient attackers and defenders. All combat is assumed to transpire on level ground with a 10% combat modifier to the defender. Each column displays the total number of each type of streak that occurred during all of simulated combat.

    Now, in order to determine whether Civ3's random number generator is delivering an appropriately random result we will need results taken from the game. As yet, I do not have these results. It would be a lot easier if it had a cheat mode with which I could instantly put down 1,000 test subjects, but it doesn't. So, I call on the collective data gathering power of this entire forum to help collect the necessary data.

    I would ask each of you to go fight an ancient era war and return the results of each combat. We want to know the exact number of each type of streak that occurred during combat. Once we have enough results, we can compare them to expected results. This will, hopefully, either prove that there is indeed something wrong with the random number generator, or that there is indeed nothing wrong with the random number generator.

    Sorry about this PHP stuff, but it was the only way I could figure out to make the board not delete all of my tabs. It totally destroyed my tables. I don't know what PHP is supposed to do, and so I can't predict if it will show up properly, but it looks like it works on my end. It is still a big mess, but it is better than not having any spaces at all!

    PHP Code:
    The following is an example of what the data means.  If a battle follows the pattern,
    Attacker                            Defender
    X
    X
                                X
    X
                                X
                                X
                                X
    Defender Dies
    then the results of this combat are:
                            
    One          Two         Three             Four                                                        
    Attacker              1              0              1              0                                                        
    Defender              1              1              0              0                                                        


    4HP vs
    4HP
    Results from 10
    ,000,000 Confrontations
    Attacker              One              Two              Three              Four
    Archer                 8
    ,964,266     4,360,764         2,011,396          1,000,836
    Defender             One              Two              Three              Four
    Spearman               9
    ,730,149     4,518,276          2,041,995          1,361,879
    Results from 10
    ,000,000 Confrontations
    Attacker              One              Two              Three              Four
    Archer                10
    ,462,044    4,287,162      1,954,495            2,641,432
    Defender             One              Two              Three              Four
    Warrior                6
    ,337,550     3,517,345     1,813,553                   369,421
    Results from 10
    ,000,000 Confrontations
    Attacker               One               Two              Three              Four
    Swordsman          10
    ,300,304        4,533,003        2,034,088            1,859,570
    Defender              One               Two              Three              Four
    Spearman              7
    ,885,837     4,052,129            1,947,714         673,142
    Results from 10
    ,000,000 Confrontations
    Attacker              One              Two              Three              Four
    Swordsman               9
    ,597,199     3,542,791      1,723,552          3,897,640
    Defender             One              Two              Three              Four
    Warrior               4
    ,326,225      2,690,371      1,581,916              137,632
    3HP vs
    3HP
    Results from 10
    ,000,000 Confrontations
    Attacker              One              Two              Three              
    Archer                 6
    ,918,570     3,383,259     1,943,113              
    Defender             One              Two              Three              
    Spearman            7
    ,422,891     3,470,202      2,445,965              
    Results from 10
    ,000,000 Confrontations
    Attacker              One               Two              Three              
    Archer                 7
    ,884,940      3,306,257      3,976,614              
    Defender              One              Two              Three              
    Warrior                5
    ,131,003      2,843,250     921,083              
    Results from 10
    ,000,000 Confrontations
    Attacker              One              Two              Three              
    Swordsman          7
    ,784,038    3,471,340      3,080,190              
    Defender              One              Two              Three              
    Spearman             6
    ,197,744     3,195,090      1,445,633              
    Results from 10
    ,000,000 Confrontations
    Attacker              One              Two              Three              
    Swordsman         7
    ,294,638      2,806,963     5,253,033              
    Defender             One              Two              Three              
    Warrior                3
    ,674,535    2,273,300      436,849   
     
    End of Table 
    *These numbers were generated using the srand() and rand() functions of C++ using the Visual C++ 6.0 compiler. The results were found to be consistent with minor random variation between multiple computers. The srand() function was seed with the current time using the time() function.

  • #2
    I'd love to help out but I'm scratchin' me head tryin' to figure the tables out... A little further explanation of them would help.
    "You don't have to be modest if you know you're right."- L. Rigdon

    Comment


    • #3
      Originally posted by cassembler
      I'd love to help out but I'm scratchin' me head tryin' to figure the tables out... A little further explanation of them would help.
      Sorry that the formatting is so messed up.

      Basically, each column is the tells you the number of each type of streak that occured during 10,000,000 simulated trials with the stated units. The "Three" column, for example, gives the number of times the unit scored three consecutive hits against its enemy during the 10,000,000 simulated battles. Does that make sense?

      The idea is that we get enough results from the game to compare with these charts and see if there is a significant difference in the number of streaks. A difference in the relative ocurrence of the streaks would indicate that there is something screwy with the Civ3 random number generator.

      Comment


      • #4
        Why not make your life easier by eliminating all units from the game except the warrior and the galley and paving the world with grassland? Then you only have one kind of battle: 1 vs 1.1

        You can also simplify things by giving everything 1hp, so that you don't have injured units running around.

        Xerxes
        Last edited by Xerxes314; November 25, 2001, 00:56.

        Comment


        • #5
          Originally posted by Xerxes314
          Why not make your life easier by eliminating all units from the game except the warrior and the galley and paving the world with grassland? Then you only have one kind of battle: 1 vs 1.1
          Good idea, I've put together a scenario that makes testing it easier. The entire map is grassland, still affording a 10% terrain bonus since I couldn't figure out how to change that. Cities, fortifications, forts, etc., however, now provide no defensive bonus at all. The only units available in the game are the worker, settler, explorer, scout, and warrior. Conscripts and regulars have 3 HP, while veterans and elites have 4 HP.

          Keeping track of the streaks when the AI attacks is a little bit like a maddening game of "Simon," but it is managable if you only try to remember the first battle of every AI turn.

          Originally posted by Xerxes314 You can also simplify things by giving everything 1hp, so that you don't have injured units running around.

          Xerxes
          Wouldn't that invalidate the entire point of the data collection? I'm testing to determine whether or not the streaks in combat are more than one would expect from random chance. If there is only one hitpoint, there are no streaks.

          Currently my policy is to not count any combat in which either combatant has less than 3 HP. If a 4HP unit is damaged 1 HP before combat, it counts in the results as being a 3HP unit.

          Thus, there are four valid combinations:

          3HP vs. 3HP
          4HP vs. 4HP
          3HP vs. 4HP
          4HP vs. 3HP

          So far, from the small amount of testing I've done today, these are the current results.

          3HP vs. 3HP

          3HP Attacker
          One hit streaks: 37
          Two hit streaks: 16
          Three hit streaks: 6

          3HP Defender
          One hit streaks: 37
          Two hit streaks: 13
          Three hit Streaks: 15

          4HP vs. 4HP


          4HP Attacker
          One hit streaks: 1
          Two hit streaks: 0
          Three hit streaks: 1

          4HP Defender
          One hit streaks: 0
          Two hit streaks: 1
          Three hit streaks: 0

          3HP vs. 4HP

          3HP Attacker
          One hit streaks: 5
          Two hit streaks: 2
          Three hit streaks: 0
          Four hit streaks: 1

          4HP Defender
          One hit streaks: 10
          Two hit streaks: 2
          Three hit streaks: 0

          4HP vs. 3HP

          4HP Attacker
          One hit streaks: 7
          Two hit streaks: 3
          Three hit streaks: 0

          3HP Defender
          One hit streaks: 7
          Two hit streaks: 3
          Three hit streaks: 0
          Four hit streaks: 0

          I tried to upload the scenario that I used for testing, but the board wouldn't allow that file extension. Does anyone know if I could just rename the file with a different extension, or would the board just scramble the file?

          Comment


          • #6
            Nice testing.

            It seems like the statistics are behaving normally. You could come up[ with some type of confidence test. But It looks ok to me. (looks like a normal distribution)

            Comment


            • #7
              I tried to upload the scenario that I used for testing, but the board wouldn't allow that file extension. Does anyone know if I could just rename the file with a different extension, or would the board just scramble the file?
              zip the file (if you have the tools you need)... it'll not only reduce the size by a lot, but the board is set to accept zip files.

              -- adaMada
              Civ 3 Democracy Game:
              PTW Game: Proud member of the Roleplay Team, and Ambassador to Glory of War
              Intersite PTW Game: Member of Apolyton

              Comment


              • #8
                Originally posted by adaMada


                zip the file (if you have the tools you need)... it'll not only reduce the size by a lot, but the board is set to accept zip files.

                -- adaMada
                Good thinking! Here it is...
                Attached Files

                Comment


                • #9
                  Originally posted by GP
                  It seems like the statistics are behaving normally. You could come up[ with some type of confidence test. But It looks ok to me. (looks like a normal distribution)
                  I'd agree, except for this:

                  "3HP Attacker
                  One hit streaks: 37
                  Two hit streaks: 16
                  Three hit streaks: 6

                  3HP Defender
                  One hit streaks: 37
                  Two hit streaks: 13
                  Three hit Streaks: 15"

                  Why are there more three hit streaks for the defender than two hit streaks?[list=1][*]Is it simply the result of small sample size?[*]Is that what a random distribution of streaks for two warriors should look like?[*]Is it a bug in the Civ3 random number generator?[/list=1]

                  I just simulated 10,000,000 warrior vs. warrior encounters using the program I wrote. The results were as follows:

                  3HP Attacker
                  One hit streaks: 6,918,029
                  Two hit streaks: 3,386,429
                  Three hit streaks: 1,943,773

                  3HP Defender
                  One hit streaks: 7,420,790
                  Two hit streaks: 3,471,117
                  Three hit Streaks: 2,444,853

                  As you can see, there is no corresponding increase in the number of three hit streaks for the defender. Thus, I'm rather inclined to rule out #2.

                  Comment


                  • #10
                    I'm inclined to say that's a combination of small sample size and the 10% defensive bonus for grasslands. BTW, you can remove that on the terrain tab of the editor.

                    Comment


                    • #11
                      Well, I got lost with your syntax. but the new tests seem to make sense for what you'd expect. get one of the math/stat jocks over at Civ2 or 3 strat to calculate the probability of each result. I bet we come pretty close.

                      I assume the difference between defenders and attackers is from the 10% bonus and/or the "defender wins ties" rule.

                      Comment


                      • #12
                        These are the results,

                        3HP Attacker
                        One hit streaks: 6,918,029
                        Two hit streaks: 3,386,429
                        Three hit streaks: 1,943,773

                        3HP Defender
                        One hit streaks: 7,420,790
                        Two hit streaks: 3,471,117
                        Three hit Streaks: 2,444,853

                        of 10,000,000 warrior vs. warrior encounters that I simulated using a C++ program I wrote for the purpose. The idea is that this is the ratio that the streaks should occur within the game if the random number generator is functioning properly.

                        Streaks are considered to have stopped at the end of a battle, that is why the maximum length of a streak is 3. This is taken into account in the simulation. The 10% grassland bonus is accounted for in this simulation, that is why the defender has more of every type of streak.

                        My point was that from the defender in the 3HP vs. 3HP battles I have recorded actually had more 3 hit streaks than 2 hit streaks. This is not what one would expect based on these simulated battles. This may very well be the result of small sample size. It could also be the result of something screwy with the random number generator in civ3.

                        Either way, we still need more results from the game to reach a conclusion.

                        This is a screenshot from the scenario I used to create the results from the game.
                        Attached Files

                        Comment


                        • #13
                          DOH!! I thought you had written a program that did these many real tests!!

                          Anyway. Have a look at some of the threads in Civ3 and 2 strat. These guys did some very similar/extensive testing on civ2. They may have some insights for you.

                          Comment


                          • #14
                            New results for 3HP vs. 3HP warriors from my continued testing.

                            3HP Attacker
                            One hit streaks: 94
                            Two hit streaks: 43
                            Three hit streaks: 21

                            3HP Defender
                            One hit streaks: 97
                            Two hit streaks: 42
                            Three hit Streaks: 36

                            I ran a chi-square on the results and it returned a 0.43, not anywhere near a statistically significant result. It looks like Civ3's RNG is working properly.

                            Comment


                            • #15
                              The numbers look right to me. However, I think it would be more usefull to encode the data in terms of number of 'dice rolls' won rather then streaks. It doesn' t really matter, I bet the distribution works out correctly anyway.


                              My current guess on how the random number generator works, (and ways around it)

                              Dice rolls are precomputed (or seeded) somehow at the beginning of every turn.

                              Some value between 0 and 1 is chosen for the defense and offsense - the value is then multiplied times the corrisponding defending and offensive strengths. Defender gets some bonus.

                              Thus, if it is important to win a battle it appears effective to use junk units - that is, one that is sure to be beaten, if you know that the first 'n' seed values are so low that the computer is going to win regardless.


                              The real problem with the battle system has nothing to do with the probality distribution, its just a noise problem. With few units (i.e. early in the game), the amount of randomness in battles is huge. In modern times,with dozens of units even for a small war, the noise cancels out.

                              Comment

                              Working...
                              X