First off, I am so addicted to Quinn, lately i have been playing it for hours a day. Thank you so much for making it available.

I did, however want to bring up two interesting issues, i'm not sure if they're by design, or a glitch, so I thought maybe some clarification would be in order.

As most long-time Quinn/Tetris/etc players are aware, as a piece moves downward to the point that it's "on" the blocks below it, there is a period of time that the piece floats and is still capable of being moved left or right before it's "locked" into place. What I have noticed with Quinn is that at the end of the game, when the penultimate piece comes on to the board such that the top of the piece graces the top of the board, that piece immediately "locks" without giving the user a chance to move it left or right. So the next piece then immediately falls and the game is over. Having the chance to move that next-to-last piece like all the previous ones is an opportunity to clear a line or two and extend the game, so I'd like to request in future builds that piece get treated like any other piece coming on to the board.

Also, i've noticed the "randomness" of the piece selection doesn't seem to be so random. Frequently Quinn seems to get "stuck" serving the same one or two pieces over and over, and then move on to another couple after 5 or 10 seconds. Would it be possible to get the randomness tweaked just a little bit. Something has to be awry when it is pretty much guaranteed during every game I get served 9 or 10 square peices in a row.

Thanks so much for looking into this Simon!

Tetris?  What's this "Tetris" you speak of? (;

I'm a bit confused by the first issue you describe, it sounds to me like normal operation, but I can't say for sure.

As to to the second point, I think (and Simon can confirm this) that the piece selection is as "random" as can be.  If you do happen to get 10 of the same piece in a row, well, that's just bad luck.  I've heard this argument before, as it seems that some of the newer versions of Tetris™®®™™ all employ some type of anti-repeat code, but to me that just seems, well, not very random (:

The 10 or so in a row is only one example. Generally it seems to be loose patterns (e.g., only T's and squares for a while, then only L's and I's for a while, then just squares for a while, etc). I am also a software engineer, and observing the periodic repetitive patterns in Quinn's piece selection leads me to believe there is a deficiency in the actual random number generator being used.

Is rand()/srand() being used in Quinn? The behavior I am describing is a known issue with the rand when used in any form. That is why it is generally considered obsolete by the software development community. random()/srandom() is included in most C++ packages (including cocoa) and generally considered to be completely random when seeded correctly.

We'll have to wait for Simon to answer those questions for you.  I am a but a lowly web developer (;

I must say that I cannot confirm the behavior you describe. I did the following: I dropped all pieces until only two blank rows were left at the top, like in picture 1. Then the brown L-shaped piece came in (picture 2), and I was still able to move it left or right. Is this the situation you mean? Otherwise, could you clarify it?


I know that this is sometimes annoying, but it is a purely random effect. There's a way to count piece repetitions: Quit Quinn, go to the Terminal, and enter the command

defaults write Quinn QuinnStatisticsFlag YES

After that, Quinn will write a short statistic to the Console at the end of each game, which includes a repetition count (the number of times that a new piece is equal to the previous one), and the number of repetitions divided by the total number of pieces. That last number should be close to 0.143 = 1/7 for a purely random piece selection, and it usually is, provided the game was sufficiently long.

(Note: Due to a bug, the repetition counter currently only gives correct results for the very first game after starting Quinn. I already fixed this, so it will work in the next release.)


The random number generator for new pieces is a very simple algorithm suggested by Knuth, which is said not to have such effects as rand(). I can tell you the algorithm if you're interested.

Interesting, I must have been dreaming this one up. I cannot reproduce anymore.  Sorry, i'll try to find a situation where it happens again and let you know!

However, I did run across something else while trying to duplicate that one. It seems that you can make a piece indefinitely float by alternating left/right movements very quickly (left/right/left/right/left/right/etc) while it's directly atop another piece and hasn't locked into place yet.


Just because the counter reads around 1/7 doesn't necessarily confirm randomness. If there are cyclic patterns that shift throughout the game, then periods of repitition would go unnoticed in a single counter while the overall game may appear random. If there was a way to log each piece that falls, we could chart the distribution in a histogram and see if any patterns arise.


Yes, I would love to look at it for my own satisfaction. I don't actually on a copy of 'The Art of Computer Programming' from Knuth, but I'm assuming it's the one he publishes there? Thanks!

Yes, that's true ... but actually I don't see why it is a problem. In the original Tetris earlier implementations of falling-blocks games, a similar behavior existed, which gives the user a "last chance" to move a piece before it freezes.


You are right in that the counter does not confirm pure randomness. Currently there's no way to log the pieces, although this would not be difficult to implement. However, as far as I understand you, you were only talking about the same piece coming several times in a row, and I never observed cyclic patterns either or heard from users who did.


Here's the code -- as said, really simple:

static unsigned gKnuthRandomNext;

unsigned QuinnRandom( unsigned n )
{
   gKnuthRandomNext *= 1114525;
   gKnuthRandomNext += 1013904223;
   return gKnuthRandomNext % n;
}

Unfortunately, I don't recall where I took it from; it may well be from "The Art of Computer Programming."

Cool, thanks!

You should definitely give a thorough study at the wikipedia aritcle on Linear Congruential Generator (link below), since that appears to be what you are utilizing. Note the 1114525 constant should actually be 1664525 from everything I've read including that article. It suggests that the level of randomness is very sensitive to your choise of inputs, including your two constants and your value of N. Further, LCG's are well-documented to be pseudo-random because they are incredibly unreliable in the low-order bits, which would apply in the case of Quinn having only seven possible outputs. For these reasons, 'best practice' dictates LCGs only be used when a system lacks the memory power to use more thorough randomization techniques. (As an aside, It would be interesting to know how you initialize gKnuthRandomNext and if n is always 7.)

Knuth's older publications cover LCG's, but in the past few years, he has endorsed his own randomization routines (not based on LCG's) that have passed rigorous randomization tests, including the de-facto RNG tester known as 'diehard' which identifies patterns and deficiencies in random number generators. random() also does very well in diehard tests, while LCG algorithms consistently fail.

Related Reading:
http://en.wikipedia.org/wiki/Linear_congruential_generator

http://www-cs-faculty.stanford.edu/~uno/programs/rng.c

http://www-cs-faculty.stanford.edu/~uno/news02.html#rng

http://en.wikipedia.org/wiki/Diehard_tests

http://www.csis.hku.hk/~diehard/

The thing with using "pure" randomness is that you can get a lot of repeated pieces.
Why not use an algorithm like this one? http://tetris.wikia.com/wiki/TGM_randomizer
It's really easy to implement and I think it would work just fine.
To be honest I'd implement it myself if Quinn was OSS (or if I had access to the source code) because this is the only thing that really bugs me about Quinn.

Sorry to post on such an old thread but it seemed the most appropriate solution.

beat:

If either the TGM_randomizer or bag logic were employed, the top speed would have to be increased by a lot, or the high score list would become even more meaningless than having undo makes it.

[hrrgmek, haldrrn, lastobelus]