c++ - What is a good random number generator for a game?

Question

What is a good random number generator to use for a game in C++?

My considerations are:

1. Lots of random numbers are needed, so speed is good.
2. Players will always complain about random numbers, but I'd like to be able to point them to a reference that explains that I really did my job.
3. Since this is a commercial project which I don't have much time for, it would be nice if the algorithm either a) was relatively easy to implement or b) had a good non-GPL implementation available.
4. I'm already using rand() in quite a lot of places, so any other generator had better be good to justify all the changes it would require.

I don't know much about this subject, so the only alternative I could come up with is the Mersenne Twister; does it satisfy all these requirements? Is there anything else that's better?

Edit: Mersenne Twister seems to be the consensus choice. But what about point #4? Is it really that much better than rand()?

Edit 2: Let me be a little clearer on point 2: There is no way for players to cheat by knowing the random numbers. Period. I want it random enough that people (at least those who understand randomness) can't complain about it, but I'm not worried about predictions. That's why I put speed as the top consideration.

Edit 3: I'm leaning toward the Marsaglia RNGs now, but I'd still like more input. Therefore, I'm setting up a bounty.

Edit 4: Just a note: I intend to accept an answer just before midnight UTC today (to avoid messing with someone's rep cap). So if you're thinking of answering, don't wait until the last minute!
Also, I like the looks of Marsaglia's XORshift generators. Does anyone have any input about them?

Answer 1

Sometimes game developers don't want true randomness and a shuffle bag is more appropriate.

If you do want randomness, the Mersenne twister satisfies your requirements. It is fast, statistically random, has a long period and there are plenty of implementations out there.

Edit: rand() is typically implemented as a linear congruential generator. It's probably best if you make an informed choice of whether or not it's good enough for your purposes.