Cultris II randomizer analysis

Started by Sisu, March 14, 2013, 01:14:05 PM

Previous topic - Next topic

Sisu

Happy Pi Day!

Here is a large piece sequence from the C2 randomizer:

http://ge.tt/6QqO22b/v/0?c

I cannot share what information can be derived from this data because...erm...I am not good at such analysis.  

gogogo

EDIT:
Quote from: NikC2 randomizer isn't memoryless. Over the long run, you'll get an even distribution over all tetrominoes, there are no guaranties though about the order over a certain amount of pieces.
Quote from: NikC2 picks every new piece at random, but the probability for each type isn't the same. It is based on the previous picks.
So there are no absolute guaranties about the picks, but it isn't a memoryless randomizer.

simonlc

#1
10 MB of text, impressive.

EDIT: I did some analysis, "JIZLOTS" appears 38 times.

FelipeMayrink

#2
Quote from: simonlc
EDIT: I did some analysis, "JIZLOTS" appears 38 times.
[insert generic expected joke about "Lots of Jizz" here]

EUHUEHEUHEUHEUHEUHEUHEUHEUHEUHEUHUEHUEHUEH BRBR

Pineapple

You know... I completely forgot about Pi Day until I saw it mentioned on IRC when I woke up. Am slightly annoyed, as I missed my traditional 2am pie moment...

One question, since the data does not make this clear: Is this output from a single game, or is it multiple games of length 100, or is it something else? I get a fairly significant change in the lower intervals when treating it as one long game compared to games of length 100.

My initial observations are that the randomizer is unbiased, strongly excludes interval 1 (the same piece twice in a row), weakly excludes interval 2 (the same piece appearing with just one other piece in between), and makes no attempt to prevent droughts.

[!--quoteo--][div class=\\\'quotetop\\\']QUOTE[/div][div class=\\\'quotemain\\\'][!--quotec--]I did some analysis, "JIZLOTS" appears 38 times.[/quote]
I am immediately reminded of Finding sequences of digits in pi, and not just because of the day. This might be something to look at, in the future...
It is only when you open your mind, that you will be able to see how beautiful the world is...

Sisu

Quote from: Pineapple
Is this output from a single game
yes

Integration

Pineapple has well summarized the behaviour of the Cultris 2 randomizer:

Quote from: PineappleMy initial observations are that the randomizer is unbiased, strongly excludes interval 1 (the same piece twice in a row), weakly excludes interval 2 (the same piece appearing with just one other piece in between), and makes no attempt to prevent droughts.
-----------

I have prepared some pics. And I will also describe randomisers which create similar piece sequences.

First of all, Cultris randomizer is unbiased. The sequence consisted of 10,000,000 pieces and the number of I,L,J,O,T,S,Z pieces just differed by a few 1000 - that's roughly as much as you would expect to get with memoryless randomizer ( there the standard deviation lies at sqrt( 10,000,000 * (6/7)*(1/7) ) = 1106 pieces ).

[!--ImageUrlBegin--][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i49.tinypic.com/18k5dk.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

This image shows the chances of getting the current kind again within the next 7 pieces ([a href=\\\"http://i49.tinypic.com/vhufc6.png]here in comparison to memoryless randomizer
). There's just roughly a 2.7 % chance for repetions - this isn't even a fifth of memoryless randomizer! Chances that the 2nd and 3rd next piece is from the same kind is also a bit reduced.

But then chances stay the same! And that's a very interesting point. I am quite sure some theoretical result was used to assure this. This is harder to achieve than you might think. Let's take for example a randomizer, that keeps a history of the 2 most recently generated pieces and lowers the chance to generate one of those as the next piece. Let's say you currently got an I. Then chances are reduced that you get an I as next or 2nd next piece, which results in a bigger chance for an I as the 3rd next piece - although the 3rd next piece doesn't depend directly on your current piece. I hope you understand what I mean. In the case, Cultris 2 randomizer is some kind of history randomizer, it uses at least a history of the 5 last pieces, e.g. I counted 539652 sequences of the kind ITOLJI 1079304 (5th next piece the same as first, the rest is different) and 2*546973 sequences of the kind ITOLJS (now 6th piece is different!). Those numbers differ by more than 1 %.

[!--ImageUrlBegin--][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i49.tinypic.com/282lwg4.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

This image shows how long you have to wait until you get the same kind again ([a href=\\\"http://i46.tinypic.com/4fveag.png]here in comarison to memoryless randomizer
). Droughts of 29 or more pieces are possible, but not as common as for memoryless randomizer (as there are less repetitions). This statistic has a standard deviation of 5.258 (i.e. most often you have to wait 7 +/- 5.258 pieces) in comparison to sqrt( 8 ) = 2.828 pieces for bag randomizer and sqrt(42) = 6.481 pieces for memoryless randomizer.

[!--ImageUrlBegin--][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i49.tinypic.com/i2vuac.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

This image shows how often you get a certain piece sequences of length 3 ([a href=\\\"http://i49.tinypic.com/1eump0.png]here in comparison to memoryless randomizer
). I used those percentages to create a history randomizer which keeps track of your last 2 pieces:

If the last 2 pieces are of the same kind, repeat it with a chance of 2.8105 % or hand out one of the other 6 kinds with a chance of 16.1982 %. Otherwise (last 2 pieces different), repeat the last with a chance of 2.7055 %, repeat the 2nd with a chance of 11.7361 % or hand out one of the other 5 kinds with a chance of 17.1117 %.

I created a 10,000,000 piece sequence with this randomizer. Here the first 2 pics in comparison to the Cutris 2 sequence.

[!--ImageUrlBegin--][a href=\\\"http://i47.tinypic.com/5wxm41.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i47.tinypic.com/5wxm41.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

The 2-history randomizer overshoots the chance of getting the same kind after 3 pieces (as I tried to explain a bit above). Beside that it's very similar.

[!--ImageUrlBegin--][a href=\\\"http://i45.tinypic.com/im6mpu.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i45.tinypic.com/im6mpu.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

As you can see, droughts of length 15 or more is very similar, which also shows that Cultris 2 randomizer doesn't use mechanics to reduce droughts.

And I also created a 3-history randomizer by evaluating the numbers of length 4 sequences:

last 3 pieces of the same kind: (e.g. III)
give last = 2.7719 %
give other = 16.2047 %

3rd last = 2nd last, but last different (e.g. IIT)
give last = 2.9313 %
give 2nd last = 11.8981 %
give other = 17.0341 %

3rd last = last, but 2nd last different (e.g. ITI)
give last = 2.6498 %
give 2nd last = 11.6954 %
give other = 17.1310 %

2nd last = last, but 3rd last different (e.g. ITT)
give last = 2.8116 %
give 3rd last = 15.1683 %
give other = 16.4040 %

all 3 last pieces different (e.g. ITO)
give last = 2.7061 %
give 2nd last = 11.7366 %
give 3rd last = 15.5810 %
give other = 17.4941 %


Here the results:

[!--ImageUrlBegin--][a href=\\\"http://i45.tinypic.com/260wmyp.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i45.tinypic.com/260wmyp.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

[!--ImageUrlBegin--][a href=\\\"http://i47.tinypic.com/2ennhvp.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i47.tinypic.com/2ennhvp.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

[!--ImageUrlBegin--][a href=\\\"http://i49.tinypic.com/20jlmjb.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i49.tinypic.com/20jlmjb.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

vipjun

#6
nice analysis misttake !!

A few months ago I tried to make a similar analysis but with only ~2000 pieces entered manually.

Total (2.83% 11.82% 13.41% 11.95% 10.37% 8.68% 7.2% 5.96% 4.88% 3.99% 3.28% 2.7% 2.2% 1.85% 8.88%) Total: 2153

Each percentage represents how likely the same piece will show up after x pieces or droughts

I was able to load about ~1M into the same program and the results are pretty close


With the analysis you made I tried to make a weight distributed randomizer

Total (2.76% 11.5% 13.11% 12.27% 10.41% 8.58% 7.15% 5.97% 4.96% 4.1% 3.4% 2.8% 2.29% 1.93% 8.75%) Total: 1000000

The file is here
You also need the racket program http://racket-lang.org

Usage
(make-sequence 10000) ; generates a piece sequence of 10000
(analyze-result); does the analysis on the piece generated
you can edit the numbers in weights

caffeine

Thanks integration. This is useful intel for c2 decision-making.

virulent

Integration = miss take? I never knew!
I wonder why the c2 randomizer is so much more difficult to adjust to than most other games? Is memory less not used much except on kos and possibly np customized rooms?
I was gunna ask a question about droughts but then I read more n you already answered it @.@ so thorough
Also, you must spend a lot of time analyzing these kinds of things o.o kudos to you! The Tetris world needs ppl like you~
[div align=\\\"center\\\"]
[/div]


Integration

Virulent should look more on the forums to see my pretty face. Or she is as Dory as me. Or as trolly. BTW happy birthday viru!!!

Quote from: virulentThe Tetris world needs ppl like you~
YES THE WORLD IS 2 FLAWLES!!! IT NEEDS MORE ERORS AND MISSTAKES!!!

Quote from: virulentIntegration = miss take? I never knew!
I wonder why the c2 randomizer is so much more difficult to adjust to than most other games? Is memory less not used much except on kos and possibly np customized rooms?

Perhaps C2 randomizer is difficult to adjust to, because there is no game with a similar randomizer. I would classify it as semi-random to random (bag randomizer = opposite of random, memoryless = pure random), so only guideline players should have problems to adapt to it.

Memoryless in KOS? I thought mindzy would be a bag fanatic. I get mad at people thinking C2 is memoryless.  Probably, memoryless is the most used randomizer, as it is the easiest way to program a randomizer (each piece has the same chance to appear next). I am sure all games prior to 1988 use memoryless. Apart from that, there are not many official games using memoryless. Tetris & Dr. Mario on SNES and Microsoft Entertainment Pack Tetris are the only ones I know of. 1989 Gameboy Tetris is also pretty similar. From the multiplayer capable games: Multris and Dualtris/Palatris. Tetrinet should also be memoryless, but it uses a 12 wide well. And Quadra, but it uses recursive gravity and 3 previews. And Cultris 1, but it uses time based combo system, so you don't stack for Tetrises.

----------------

I made this randomizer comparison with TGM and NES, too. Standard Deviations of the droughts statistic are as following:

Bag: 2.828
TGM: 3.184
Cultris2: 5.258
NES: 5.713
Memoryless: 6.481

Here the comparison to TGM randomier. TGM uses a 4-history randomizer, that chooses a random piece and accepts it, if it's different from the last 4 pieces you got. The piece can be denied up to 3 times, before it will be accepted anyway.
[!--ImageUrlBegin--][a href=\\\"http://i45.tinypic.com/106aw77.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i45.tinypic.com/106aw77.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

[!--ImageUrlBegin--][a href=\\\"http://i50.tinypic.com/2l9o4e8.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i50.tinypic.com/2l9o4e8.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

[!--ImageUrlBegin--][a href=\\\"http://i46.tinypic.com/9pvq4o.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i46.tinypic.com/9pvq4o.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]


And here the comparison to NES randomizer, which is a 1-history randomizer. The piece will be from the same kind as the last with a chance of 1/28 = 3.57 %. All other 6 piece kinds have a chance of 9/56 = 16.07 %.
[!--ImageUrlBegin--][a href=\\\"http://i50.tinypic.com/5mea74.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i50.tinypic.com/5mea74.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

[!--ImageUrlBegin--][a href=\\\"http://i47.tinypic.com/6xtdex.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i47.tinypic.com/6xtdex.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]

[!--ImageUrlBegin--][a href=\\\"http://i45.tinypic.com/358qu1c.png\\\" target=\\\"_new\\\"][!--ImageUrlEBegin--][img width=\\\"400\\\" class=\\\"attach\\\" src=\\\"http://i45.tinypic.com/358qu1c.png\\\" border=\\\'0\\\' alt=\\\"IPB Image\\\" /][!--ImageUrlEnd--][/a][!--ImageUrlEEnd--]