Randomizer Theory

Thread in 'Research & Development' started by colour_thief, 12 Jan 2007.

  1. <EDIT>

    I'm not one to split topics, but this deserved it I think. Also, as a disclaimer, the probabilities I mention in this post are wrong. [​IMG] It all gets worked out later though, with fancy pictures.

    =========


    It's far more likely that you go 12 pieces without the I piece in SRS than in TGM.


    SRS: 1/49 > 2%

    TAP: *a really complicated expression* < 0.5%


    So it's more than 4 times as likely to happen in SRS. 4.55 when I divide the actual numbers. Though to be fair to SRS, a gap of 13 is impossible, whereas it is technically possible to go, say, the entire game without getting an I piece in TGM. Needless to say that's so improbable that it's literally impossible (because of the finite randomizer seeds) and the longest observed stretch without them would be a much more reasonable length.


    Still though, I should actually compare SRS's 12 gap with TGM's 12+ gap.
     
  2. It shouldn't be too hard to generate a string of 1 million pieces using the TGM2 randomizer, and then have it count intervals, should it?


    I know that this won't give us an exact number, but it would still be better than nothing...
     
  3. I'M ON IT.
     
  4. with 1000000 pieces with the TGM2 randomizer I get around 4480 intervals that are 12 or larger


    next, SRS
     
  5. Well, I must apologize for an error in logic above. TAP will starve you for 12 pieces about 1.3% of the time, which is still better than 2%, but not as much as I stated.


    If I calculated it right, the probability of starving the player for 12+ pieces is about 4%. I must say that result surprised me, though I took some... shortcuts calculating it. I'm not sure how much it affects the result but probably not enough to make up for the difference.


    On the other hand, the odds of getting a piece twice in a row is:


    SRS: 1/49 > 2%

    TAP: < 0.9%


    So at a glance it would appear SRS gives more floods and less droughts than the TAP randomizer. In my opinion floods are more dangerous, what do you guys think?
     
  6. tepples

    tepples Lockjaw developer

    Random Generator, SRS, and hold are in the same guideline, and hold levels out floods and droughts to an extent.
     
  7. Well of course. [​IMG] Hold will smooth the edges of any randomizer by its very nature. I still think it's worth looking at the distribution patterns of each randomizer to get insights on their general character though.


    I've now got exact probabilities for going without a piece for all interval sizes in SRS, and an approximate way of finding the probabilities for TAP. When I get the chance I'll make up the appropriate charts so people can visualize this better.
     

  8. Oops, sorry I missed this post kotetsu. Can you double check your results? Because it's roughly 1 order of magnitude off the probability I calculated (which was admittedly fudged). I think I'll try and write a program that can calculate the probabilities with more accuracy.


    For TAP I'm using these 2 formulas, where In and Out are the probabilities of obtaining a piece inside or outside the history respectively.

    For an interval i < 4 pieces:

    (3/4(In) + Out)^i * 1/4(In)

    For an interval i >= 4 pieces:

    (3/4(In) + Out)^4 * (2/3(Out) + In)^i-4 * 1/3(Out)


    So i = 0 would be 2 consecutive pieces. The fudging is that I assume the history always has 4 different pieces... Otherwise you'd get a LOT of terms and In and Out would each have 4 possible values. Can anyone otherwise spot a logical flaw?


    SRS is dead easy to calculate without complications.

    1/49, 2/49, 3/49, 4/49, etc.

    Basically for each i from 0 to 12 it goes from 1/49 to 7/49 and then back down to 1/49.
     
  9. I guess there are no takers? It only takes highschool math people, so don't be shy.


    Anyhow, I checked and my TAP approximation sums to 1 so it can't be toooo off but I'm still working on a better calculation. I've made the appropriate graph to get a good comparison of the randomizers. The results are pretty interesting. (You'll need to click the thumbnail to get a good look.)





    So if you get a piece, the x-axis shows the probability of getting that piece again in x pieces. Obviously this approaches 1 as more pieces are dealt.


    Observations:

    -TAP far surpasses SRS in preventing floods of similar pieces.

    -TAP is significantly better at delivering each piece every 7 (+/- 2) pieces.

    -SRS is marginally better at preventing droughts.


    Though of course it depends on what you want in a randomizer, all in all, I'd say TAP has the superior algorythm.
     
  10. Nice graph but is it only using 4 rerolls for TAP? I thought the TGM randomizer increased to 6 rerolls from TAP onwards, unless I just suck at reading graphs.
     
  11. 4 history, 6 rerolls. It would probably be interesting to add to this a graph for TGM1 (4 history, 4 rerolls.)
     
  12. Ignore me, I was being thick :p
     
  13. Well, it was really, really non trivial but I think I solved the problem with my approximation. Depending on the number of distinct pieces in the history, the probabilities change. My approximation assumed that the piece history had 4 distinct pieces 100% of the time. In actual practice, it's more like:


    4 distinct: 95%

    3 distinct: 4.99%

    2 distinct: 0.01%

    1 distinct: 0.000000%


    Those number were generated entirely using probability. I've got some TGM3 videos transcribed, and the observed proportions in those samples closely match. [​IMG] I don't expect my original approximation to change much, but I'll work out how to use these proportions to produce a more accurate TAP curve. I guess I'll add TGM while I'm at it... it'll only take a minor tweak to calculate its different proportions.
     
  14. K

    K

    So,


    is that all those guru explanations will lead us to a copyleft functionnal and reliable randomizer ? [​IMG]
     
  15. yeah, i think you could do even better than 4 history 6 rerolls. have you tried it against 14 bag? find us the optimal randomizer. =]
     
  16. I would imagine the potential for regular floods and droughts in a simple 14 bag randomiser being pretty nasty, but maybe I'm wrong.


    I'd like to see what a 5 history, 6 rerolls randomiser looks like though.
     
  17. Yeah, you've got the right idea there Taratang. 14-bag would retain the S-curve shape and would fit somewhere in between 7-bag and pure random. So it would have worse floods and worse droughts and just generally be undesireable.
     
  18. I figured as much since I would expect bigger bags to tend towards true random anyway. Taken to the extreme for example, a 700 bag would be pretty much identical to the random curve.
     
  19. A 28 bag would likely convince the player that it was memoryless...


    Especially if you only gave them 21 pieces from it...
     
  20. keep memory of four pieces. initial memory is random. reroll six times. but, if a piece goes eleven times (or thirteen i guess) without occuring, it spawns on the next piece.


    you're garenteed no droughts and very few floods.
     

Share This Page