 ## MWS Shuffler

The MWS Shuffler is, contrary to popular belief, the best one out there.

The truth of that statement depends on how we define best. Well, we define best, in this instance, as "the shuffler that most closely conforms with Magic rules concerning shuffling."

From the Comprehensive Rules:

101.1. At the start of a game, each player shuffles his or her deck so that the cards are in a random order.

Shuffle To shuffle a deck, library, or pile is to make the order of that deck, library, or pile random.

Does the MWS shuffler randomize a deck?

Yes. The shuffler statistically randomizes a deck of up to 80 cards in one shuffle. A prismatic deck or Battle of Wits deck would require more shuffles, but standard limited and constructed decks are shuffled sufficiently upon connecting to an opponent and at each common instance (such as after searching your library). In general, there is no reason to ever manually shuffle on MWS.

But how can we know that such decks are randomized? We can take a sufficiently large sample of shuffles and see if they conform to the statistical expectations. We can also examine the shuffling algorithm to see if it produces a mathematically random arrangement. Both of these have been done.

For those who know computer programming or statistics, this is the code for the shuffler:

``` procedure Shuffle(T:TList);
var i,k,n;
begin
n:=T.Count;
for k:=0 to Min(60,n) do
for i:=0 to n-1 do
T.Move(i,i+RandomInt(n-i));
end;
```
``` - - - - -
```
``` var
_Seed:array<0..4> of LongWord;
```
``` procedure moaInitSeed();
var G : TGuid;
begin
ZeroMemory(@_Seed,SizeOf(_Seed));
_Seed<0>:=getTickCount();
CreateGUID(G); Move(G,_Seed<1>,SizeOf(G));
end;
```
``` { Mother-of-All pseudo random number generator}
{ This is a multiply-with-carry or recursion-with-carry generator.}
{ It has a cycle length of 3E+47.}
{ It was invented by George Marsaglia.}
function moaRandomLongWord(): LongWord;
var S  : Int64;
Xs,Xn : LongWord;
begin
S := 2111111111 * Int64(_Seed<0>) +
1492 * Int64(_Seed<1>) +
1776 * Int64(_Seed<2>) +
5115 * Int64(_Seed<3>) +
Int64(_Seed<4>);
Xs := LongWord(S shr 32);
Xn := LongWord(S);
_Seed<0> := _Seed<1>;
_Seed<1> := _Seed<2>;
_Seed<2> := _Seed<3>;
_Seed<3> := Xn;
_Seed<4> := Xs;
Result := Xn;
end;
```
``` function RandomInt(V:LongWord):integer; // value in <0,V-1>
var
r:LongWord;
begin
Result:=0; r:=moaRandomLongWord();
if V>0 then Result:=(r mod V);
end;
```

The following explanation of this code comes from Richard Shay of The Mana Drain, who was, at the time, a PhD student in computer science at Purdue:

Here is how it works, translated into English:

This assumes, of course, a 60 card deck.

Let's start by numbering the cards in the deck from 1 to 60. Now, starting with card #1, randomly swap that top card (Card #1) with any other card in the deck.

Then, move down to the second card in the deck -- let's call that Card #2. Now, swap this particular card with any card numbered from #2 to #60. So, this card -- the second card down -- can be swapped with any card in the deck, except for the card above it.

Now, repeat this process for the rest of the deck; going down the deck from top to bottom, for each card in the deck, switch that card with any card below it in the deck at random. A card may also be "swapped" with itself, meaning that it remains in place.

So, does this randomize the deck? Yes, it does. I've sat down and wrote out a proof showing that this particular method means that a card in the deck is no more likely to end up in one place in the deck than in any other place -- in other words, the algorithm that shuffles the cards is sound.

That only leaves the pseudorandom number generator. Why pseudorandom? Because it is impossible to generate a truly random number on a computer.

MWS uses the aptly named "Mother-of-all Pseudorandom Number Generators" invented by George Marsaglia of Florida State Univesity. If you really know your mathematics, you can read how it works here.

Suffice to say, the Mother of All generates numbers as close as you will find to true random.

All this is to say, the MWS shuffler is for all intents and purposes, random.

One of my favorite tests for a shuffler is the land-spell clump test, described quite eloquently by Michael A Rutter in this article at Star City Games, the relevant portion I reproduce below:

Assuming a sixty-card deck, there are n-1 pairs of adjacent cards, or 59 pairs. By multiplying the probability of seeing adjacent lands (.1559) times the number of possible pairs (59), the expected number of pairs observed is 9.2 pairs of adjacent land in a completely randomized deck of 60 cards (assuming 24 lands). In this analysis, a clump of three land is considered two sets of adjacent land, a clump of four lands is considered three pairs of adjacent land, etc.

Let's look at an example: I'll put my deck in its original state, with the twenty-four lands on top, and shuffle it as I described above. To me, this emulates the state of the deck at the start of the tournament, after I registered the deck for example and double checked to see if my land count was correct. Here are the 60 cards, in order (L=land, *=non-land) with the number of adjacent pairs counted:

L****L*L*L**L**LL**L**L***LLLL***LL*LLL*L*******L**L*L**LL**

This shuffle produced eight pairs of adjacent lands, which is pretty close to the 9.2 I was expected to get. I then pulled the top 20 cards - similar to a game in which thirteen turns were taken - separated out the land (since it would be separate in play) and repeated my shuffling technique. This produced nine pairs of adjacent land, which is where I would expect the count to be, given a sufficiently randomized deck.

What can we get from this analysis? The most startling point is that even if we shuffle like crazy for the full three minutes we are allowed, land will clump together. To double check my calculations, I used a computer to simulate 100,000 shuffles from the above deck, and the average number of adjacent pairs of land was 9.18 - right where the probability said it should be. I also had three clumps of three lands and a clump of four lands. Calculations, similar to the ones done above, show that you should expect three clumps of three lands and one clump of four land.

I have put the MWS shuffler to the test using the same statistics calculations as Mr. Rutter does for his shuffling technique. As would be expected, the shuffler returns the expected number of land clumps over a sample set of 100,000 shuffles.

Human beings have a hell of a time grasping the concept of true randomness. We usually understand random as a lack of order. But random includes every possible order.

. . . . .