How to cheat in casual Magic: The Gathering

It's not really about cheating, more about the different between uniformity and randomness. One of the more annoying things about Magic: The Gathering is that it depends on luck too much, especially early in the game. Drawing either too few or too many lands can seriously reduce your chances of winning before the game even starts. To simplify the maths let's define a "failure" as getting less than 3 or more than 5 lands among the first 10 cards, and let's assume that the deck contains 60 card, 25 of which are lands.

With fully randomized deck the chance of failure is very high (29.5%). On the other hand if lands are distributed fully uniformly - card, land, card, card, land, card, land, card, card, land, card, land - the failure cannot possibly happen:

	0	1	2	3	4	5	6	7	8	9	10
Random	0.232%	2.268%	9.452%	20.511%	27.105%	22.893%	12.416%	4.184%	0.842%	0.092%	0.005%
Uniform	0.0%	0.0%	0.0%	0.0%	83.382%	16.618%	0.0%	0.0%	0.0%	0.0%	0.0%

Of course there's no way one could use an unshuffled deck even in the most casual setting. Fortunately for us most players use not very effective shuffles. In one of such shuffles a bunch of cards from the middle is moved to front of the deck, and then a bunch of cards from the front of the deck is moved to the back.

We can use this knowledge to cheat very effectively. Just prepare a deck with uniformly distributed lands - and let the opponent shuffle it. The deck looks perfectly fine at the first glance, so nobody's going to suspect any cheating, and it takes much more shuffling than most people are willing to do before its lose its advantage over fully random decks.

	0	1	2	3	4	5	6	7	8	9	10
Random	0.232%	2.268%	9.452%	20.511%	27.105%	22.893%	12.416%	4.184%	0.842%	0.092%	0.005%
Uniform	0.0%	0.0%	0.0%	0.0%	83.382%	16.618%	0.0%	0.0%	0.0%	0.0%	0.0%
1 shuffle	0.0%	0.0%	0.0%	4.024%	75.43%	20.537%	0.009%	0.0%	0.0%	0.0%	0.0%
2 shuffles	0.0%	0.0%	0.025%	7.402%	68.883%	23.355%	0.335%	0.0%	0.0%	0.0%	0.0%
3 shuffles	0.0%	0.0%	0.154%	9.953%	64.043%	24.956%	0.89%	0.004%	0.0%	0.0%	0.0%
4 shuffles	0.0%	0.0%	0.286%	12.095%	59.593%	26.667%	1.34%	0.019%	0.0%	0.0%	0.0%
5 shuffles	0.0%	0.003%	0.571%	13.721%	56.026%	27.568%	2.077%	0.034%	0.0%	0.0%	0.0%
6 shuffles	0.0%	0.006%	0.8%	15.344%	53.053%	27.874%	2.834%	0.089%	0.0%	0.0%	0.0%
7 shuffles	0.0%	0.024%	1.169%	16.441%	50.614%	28.239%	3.397%	0.114%	0.002%	0.0%	0.0%
8 shuffles	0.0%	0.032%	1.468%	17.378%	48.324%	28.535%	4.109%	0.152%	0.002%	0.0%	0.0%
9 shuffles	0.0%	0.063%	1.87%	18.212%	46.556%	28.436%	4.645%	0.216%	0.002%	0.0%	0.0%
10 shuffles	0.002%	0.077%	2.26%	18.501%	45.127%	28.395%	5.278%	0.356%	0.004%	0.0%	0.0%
11 shuffles	0.001%	0.09%	2.527%	19.216%	43.362%	28.505%	5.882%	0.406%	0.011%	0.0%	0.0%
12 shuffles	0.002%	0.121%	3.002%	19.527%	42.365%	28.14%	6.33%	0.494%	0.019%	0.0%	0.0%
13 shuffles	0.0%	0.17%	3.336%	19.917%	40.831%	28.346%	6.751%	0.626%	0.022%	0.001%	0.0%
14 shuffles	0.001%	0.221%	3.592%	20.331%	39.897%	28.034%	7.15%	0.752%	0.022%	0.0%	0.0%
15 shuffles	0.006%	0.268%	4.031%	20.547%	39.156%	27.574%	7.49%	0.891%	0.035%	0.002%	0.0%
16 shuffles	0.007%	0.294%	4.275%	20.338%	38.34%	27.836%	7.884%	0.968%	0.056%	0.002%	0.0%
17 shuffles	0.01%	0.362%	4.564%	20.59%	37.582%	27.436%	8.291%	1.104%	0.059%	0.002%	0.0%
18 shuffles	0.015%	0.398%	4.829%	20.988%	36.751%	27.135%	8.526%	1.278%	0.076%	0.004%	0.0%
19 shuffles	0.016%	0.441%	4.989%	20.844%	36.309%	27.06%	8.952%	1.304%	0.084%	0.001%	0.0%
20 shuffles	0.02%	0.549%	5.154%	20.829%	35.648%	26.926%	9.386%	1.382%	0.104%	0.002%	0.0%
25 shuffles	0.036%	0.805%	6.337%	21.246%	33.365%	25.978%	10.09%	1.936%	0.194%	0.013%	0.0%
30 shuffles	0.064%	1.015%	7.237%	21.033%	31.85%	25.154%	10.924%	2.428%	0.277%	0.018%	0.0%

Even after 20 shuffles probability of failure is 16.6%, almost half of what you'd get if you were honest. The difference is going to be even more dramatic with multicolor decks - the chance of not getting any lands of the right kind in the first 10 cards is huge, and can be drastically reduced by making the deck more uniform.

Morals of the story:

• "Uniform" and "random" are completely different things. This has important implications in computer science, but it's much more fun to illustrate it with games.
  
• Every player should learn better shuffling techniques
  

All probabilities generated by 100 000 draws using the following Ruby program:

#!/usr/bin/ruby

class Array
  def random_start
    i = rand(size)
    self[i..-1] + self[0...i]
  end
  # Shuffling procedure is
  # Divide deck into three parts, move second to the front,
  # then .random_start
  # A B C -> B A C
  def shuffle(t)
    deck = self
    t.times{
      i, j = rand(size), rand(size)
      i, j = [i, j].min, [i, j].max
      a = deck[0...i]
      b = deck[i...j]
      c = deck[j..-1]
      deck = (b + a + c).random_start
    }
    deck
  end
end

def stats
  res = (0..10).map{0}
  100000.times{
    res[yield[0,10].select{|x| x}.size]+=1
  }
  puts "* "+res.map{|x|"#{0.001*x}%"}.join(' ')
  puts "* Change of failure: #{0.001*(100000-res[3]-res[4]-res[5])}%"
end

deck_unsorted = [true] * 25 + [false] * 35
deck_uniform = [false, true, false, false, true, false, true, false, false, true, false, true] * 5

puts "Fully random:"
stats { deck_unsorted.sort_by{rand} }
puts "Fully uniform:"
stats { deck_uniform.random_start }
(1..20).each{|i|
  puts "Uniform, shuffled #{i}x:"
  stats { deck_uniform.shuffle(i) }
}
25.step(80, 5){|i|
  puts "Uniform, shuffled #{i}x:"
  stats { deck_uniform.shuffle(i) }
}