Booster color balancing algorithm has several problems (biased against colorless cards, etc.)

[awjackson]

First of all, I am aware that the preferred solution to booster generation issues is the new collation system under development by @theelk801 based on reverse-engineered information from The Collation Project. However, this information is not available for all sets and may or may not ever become available, so I believe that improvements to the "legacy" booster generation system are still meaningful and useful to xmage.

Booster generation uses an algorithm validateColors which usually rejects a booster unless it contains at least one monocolor card of each color, or the equivalent if multicolor cards are treated as a fraction of a card of each of their colors. There are several problems with this algorithm, mainly affecting artifact-themed and multicolor-themed sets.

First, multicolor cards are treated as a fraction of a card, but colorless cards (e.g. lands and most artifacts) don't count toward any color. This means that booster generation is systematically biased against colorless cards and this bias becomes more severe the more colorless cards are in a set. This is an especially bad problem for multicolor sets like Shards of Alara or Khans of Tarkir because those sets contain a large number of mana-fixing artifacts and lands which are crucial in Limited, and xmage systematically "underprints" all of that fixing.

The color balancing algorithm works particularly badly with Devoid because cards with Devoid are not equally represented in all colors. There are many more black, blue and red Devoid cards than green ones and there is only one white Devoid card and it's a rare. The algorithm sees Devoid cards as colorless cards and requires boosters to contain a non-Devoid card of each color. The result is that the non-Devoid cards of colors that have many Devoid cards are overprinted in boosters.

Another problem is that a booster with all red and green commons would be accepted as "color balanced" if it has a white, a blue and a black uncommon. This is not how real booster collation works at all. Each rarity is normally collated independently and print runs are designed to ensure that boosters are (somewhat) color balanced within each rarity that a booster contains more than one card of (i.e. common and uncommon)

Finally, a few sets (Torment and Judgment) are intentionally color-imbalanced--the sets actually contain more cards of some colors than others. Applying the validateColors algorithm to boosters of these sets causes cards from the less-represented colors to be overprinted and cards from the more-represented colors to be underprinted.

[awjackson]

Commons opened in 5000 Mirrodin boosters; color of each card added by hand:

Mirrodin - boosters opened: 5000. Found cards: 75000
C Skyhunter Patrol: 588         WHITE
C Neurok Spy: 577               BLUE
C Blinding Beam: 570            WHITE
C Seething Song: 570            RED
C Consume Spirit: 570           BLACK
C Terror: 568                   BLACK
C Moriok Scavenger: 564         BLACK
C Override: 563                 BLUE
C Spikeshot Goblin: 562         RED
C Krark-Clan Grunt: 562         RED
C Fists of the Anvil: 559       RED
C Inertia Bubble: 558           BLUE
C Thoughtcast: 558              BLUE
C Chimney Imp: 555              BLACK
C Skyhunter Cub: 554            WHITE
C Deconstruct: 554              GREEN
C Shatter: 554                  RED
C Dream's Grip: 551             BLUE
C Annul: 551                    BLUE
C Irradiate: 548                BLACK
C Loxodon Mender: 546           WHITE
C Ogre Leadfoot: 546            RED
C Lumengrid Warden: 544         BLUE
C Incite War: 543               RED
C Disciple of the Vault: 537    BLACK
C Wurmskin Forger: 536          GREEN
C Awe Strike: 536               WHITE
C Nim Shrieker: 536             BLACK
C Wanderguard Sentry: 536       BLUE
C Tel-Jilad Archers: 536        GREEN
C Tel-Jilad Chosen: 534         GREEN
C Contaminated Bond: 533        BLACK
C Predator's Strike: 531        GREEN
C Turn to Dust: 530             GREEN
C Arrest: 529                   WHITE
C Battlegrowth: 529             GREEN
C Dross Prowler: 528            BLACK
C Regress: 527                  BLUE
C Journey of Discovery: 527     GREEN
C Molten Rain: 526              RED
C Tel-Jilad Exile: 525          GREEN
C Groffskithur: 524             GREEN
C Goblin Striker: 523           RED
C Wail of the Nim: 522          BLACK
C Krark-Clan Shaman: 521        RED
C Somber Hoverguard: 521        BLUE
C Electrostatic Bolt: 520       RED
C Leonin Den-Guard: 519         WHITE
C Auriok Transfixer: 517        WHITE
C Neurok Familiar: 517          BLUE
C Sphere of Purity: 517         WHITE
C Fangren Hunter: 514           GREEN
C Disarm: 514                   BLUE
C Leonin Elder: 514             WHITE
C Wrench Mind: 511              BLACK
C Viridian Joiner: 511          GREEN
C Alpha Myr: 510
C Raise the Alarm: 509          WHITE
C Copper Myr: 507
C Vulshok Berserker: 500        RED
C Razor Barrier: 498            WHITE
C Nim Lasher: 498               BLACK
C Tooth of Chiss-Goria: 495
C Yotian Soldier: 490
C Welding Jar: 482
C Titanium Golem: 481
C Leaden Myr: 478
C Ancient Den: 477
C Myr Adapter: 475
C Myr Enforcer: 473
C Dross Scorpion: 472
C Soldier Replica: 472
C Tanglebloom: 471
C Viridian Longbow: 470
C Hematite Golem: 468
C Goblin War Wagon: 468
C Chromatic Sphere: 468
C Vault of Whispers: 467
C Steel Wall: 467
C Frogmite: 467
C Scale of Chiss-Goria: 459
C Clockwork Beetle: 459
C Cobalt Golem: 457
C Omega Myr: 455
C Clockwork Condor: 454
C Silver Myr: 454
C Slagwurm Armor: 452
C Sunbeam Spellbomb: 451
C Goblin Replica: 450
C Lifespark Spellbomb: 449
C Seat of the Synod: 448
C Leonin Scimitar: 447
C Wizard Replica: 446
C Necrogen Spellbomb: 445
C Elf Replica: 445
C Vulshok Gauntlets: 442
C Bonesplitter: 441
C Great Furnace: 438
C Aether Spellbomb: 436
C Cloudpost: 436
C Nim Replica: 435
C Malachite Golem: 435
C Neurok Hoversail: 435
C Vorrac Battlehorns: 433
C Pewter Golem: 428
C Iron Myr: 426
C Galvanic Key: 420
C Tree of Tales: 417
C Pyrite Spellbomb: 416
C Gold Myr: 412

The colored cards are almost perfectly clustered in the upper half. Only two colorless cards (artifacts) were opened more than the least-opened colored card.

[awjackson]

Commons opened in 5000 Shards of Alara boosters; colorless cards are noted by hand.

C Swamp: 1077
C Island: 1019
C Plains: 1012
C Forest: 964
C Mountain: 928
C Resounding Scream: 540
C Marble Chalice: 539
C Welkin Guide: 537
C Volcanic Submersion: 536
C Banewasp Affliction: 534
C Etherium Sculptor: 533
C Undead Leotau: 533
C Deathgreeter: 531
C Soul's Grace: 530
C Tortoise Formation: 528
C Branching Bolt: 526
C Windwright Mage: 524
C Mosstodon: 521
C Lush Growth: 521
C Cylian Elf: 521
C Vectis Silencers: 520
C Cavern Thoctar: 519
C Onyx Goblet: 518
C Oblivion Ring: 518
C Guardians of Akrasa: 517
C Executioner's Capsule: 517
C Wild Nacatl: 516
C Gustrider Exuberant: 516
C Goblin Mountaineer: 515
C Cathartic Adept: 513
C Resounding Roar: 513
C Call to Heel: 513
C Savage Hunger: 512
C Blister Beetle: 512
C Incurable Ogre: 510
C Resounding Wave: 509
C Shore Snapper: 509
C Blightning: 508
C Knight of the Skyward Eye: 507
C Rakeclaw Gargantuan: 507
C Shadowfeed: 506
C Kederekt Creeper: 506
C Goblin Deathraiders: 505
C Thorn-Thrash Viashino: 504
C Sanctum Gargoyle: 504
C Glaze Fiend: 503
C Agony Warp: 503
C Druid of the Anima: 502
C Soul's Fire: 502
C Outrider of Jhess: 502
C Cancel: 502
C Godtoucher: 501
C Courier's Capsule: 500
C Viashino Skeleton: 500
C Rip-Clan Crasher: 500
C Jhessian Lookout: 499
C Steelclad Serpent: 499
C Hindering Light: 497
C Waveskimmer Aven: 496
C Coma Veil: 496
C Gift of the Gargantuan: 495
C Court Archers: 495
C Resounding Silence: 495
C Carrion Thrash: 493
C Hissing Iguanar: 493
C Spell Snip: 492
C Elvish Visionary: 491
C Sighted-Caste Sorcerer: 490
C Bloodthorn Taunter: 490
C Yoked Plowbeast: 490
C Tidehollow Strix: 490
C Viscera Dragger: 487
C Dispeller's Capsule: 486
C Bloodpyre Elemental: 485
C Angelsong: 484
C Resounding Thunder: 484
C Vithian Stinger: 483
C Lightning Talons: 483
C Dreg Reaver: 480
C Bant Panorama: 480        COLORLESS
C Akrasan Squire: 478
C Dregscape Zombie: 478
C Deft Duelist: 477
C Jungle Weaver: 476
C Skeletal Kathari: 476
C Cloudheath Drake: 476
C Magma Spray: 476
C Sigil Blessing: 473
C Ridge Rannet: 471
C Excommunicate: 464
C Obelisk of Jund: 463      COLORLESS
C Kathari Screecher: 463
C Steward of Valeron: 461
C Obelisk of Bant: 460      COLORLESS
C Soul's Might: 460
C Dragon Fodder: 459
C Jund Panorama: 459        COLORLESS
C Bone Splinters: 458
C Naya Panorama: 454        COLORLESS
C Naturalize: 451
C Grixis Panorama: 448      COLORLESS
C Obelisk of Naya: 446      COLORLESS
C Esper Panorama: 446       COLORLESS
C Relic of Progenitus: 443  COLORLESS
C Obelisk of Esper: 436     COLORLESS
C Obelisk of Grixis: 432    COLORLESS

The colorless cards (all but one of which are mana fixing) are heavily clustered in the lower half.

[awjackson]

Commons opened in 5000 Shards of Alara boosters; colorless cards are noted by hand.

Khans of Tarkir - boosters opened: 5000. Found cards: 75000
C Plains: 1035
C Swamp: 997
C Mountain: 996
C Island: 988
C Forest: 984
C Weave Fate: 545
C Bitter Revelation: 538
C Jeskai Student: 537
C Feat of Resistance: 537
C Alabaster Kirin: 536
C Canyon Lurkers: 536
C Swift Kick: 535
C Sage-Eye Harrier: 535
C Sidisi's Pet: 532
C Trumpet Blast: 532
C Woolly Loxodon: 529
C Longshot Squad: 527
C Bring Low: 527
C War Behemoth: 527
C Ainok Bond-Kin: 524
C Kin-Tree Warden: 523
C Feed the Clan: 521
C Dragonscale Boon: 521
C Valley Dasher: 520
C Rite of the Serpent: 520
C Crippling Chill: 520
C Bloodfire Mentor: 519
C Sagu Archer: 518
C Mardu Warshrieker: 518
C Taigam's Scheming: 516
C Molting Snakeskin: 515
C Salt Road Patrol: 514
C Dutiful Return: 514
C Summit Prowler: 514
C Debilitating Injury: 513
C Force Away: 512
C Savage Punch: 511
C Mardu Hordechief: 511
C Rush of Battle: 510
C Firehoof Cavalry: 509
C Bloodfire Expert: 508
C Kheru Dreadmaw: 507
C Shambling Attendants: 506
C Jeskai Windscout: 506
C Scout the Borders: 506
C Hooting Mandrills: 505
C Cancel: 504
C Whirlwind Adept: 504
C Tormenting Voice: 503
C Unyielding Krumar: 502
C Leaping Master: 501
C Ponyback Brigade: 500
C Monastery Flock: 500
C Highland Game: 500
C Naturalize: 499
C Arrow Storm: 499
C Awaken the Bear: 498
C Scaldkin: 497
C Sultai Scavenger: 497
C Barrage of Boulders: 495
C Krumar Bond-Kin: 495
C Treasure Cruise: 494
C Smite the Monstrous: 494
C Disdainful Stroke: 494
C Throttle: 492
C Abomination of Gudul: 492
C Disowned Ancestor: 491
C Mardu Skullhunter: 491
C Act of Treason: 490
C Mardu Hateblade: 490
C Alpine Grizzly: 484
C Kill Shot: 484
C Abzan Guide: 483
C Smoke Teller: 482
C Wetland Sambar: 480
C Erase: 480
C Ainok Tracker: 480
C Defiant Strike: 480
C Glacial Stalker: 479
C Singing Bell Strike: 478
C Archers' Parapet: 477
C Mystic of the Hidden Way: 476
C Snowhorn Rider: 474
C Rotting Mastodon: 473
C Siegecraft: 471
C Sultai Banner: 471            COLORLESS
C Tusked Colossodon: 469
C Embodiment of Spring: 469
C Shatter: 469
C Tranquil Cove: 467            COLORLESS
C Rakshasa's Secret: 461
C Mardu Banner: 460             COLORLESS
C Swiftwater Cliffs: 458        COLORLESS
C Efreet Weaponmaster: 457
C Thornwood Falls: 457          COLORLESS
C Jeskai Banner: 455            COLORLESS
C Rugged Highlands: 455         COLORLESS
C Lens of Clarity: 453          COLORLESS
C Dismal Backwater: 453         COLORLESS
C Jungle Hollow: 451            COLORLESS
C Temur Banner: 445             COLORLESS
C Bloodfell Caves: 442          COLORLESS
C Wind-Scarred Crag: 442        COLORLESS
C Scoured Barrens: 440          COLORLESS
C Abzan Banner: 438             COLORLESS
C Blossoming Sands: 431         COLORLESS

The colorless cards are clustered even more heavily at the bottom than in Shards of Alara, because there are more of them. Omitted to save space, but even the uncommon and rare cards opened in this sample were noticeably skewed.

[awjackson]

Commons opened in 5000 Battle for Zendikar boosters. The color of each card (including devoid or true colorless) is noted by hand.

Battle for Zendikar - boosters opened: 5000. Found cards: 75000
C Forest: 1026
C Swamp: 1017
C Plains: 996
C Mountain: 971
C Island: 953
C Dispel: 595               BLUE
C Roilmage's Trick: 585     BLUE
C Clutch of Currents: 578   BLUE
C Rush of Ice: 575          BLUE
C Geyserfield Stalker: 566  BLACK
C Kalastria Nightwatch: 566 BLACK
C Wave-Wing Elemental: 565  BLUE
C Altar's Reap: 563         BLACK
C Cloud Manta: 561          BLUE
C Nirkana Assassin: 556     BLACK
C Anticipate: 554           BLUE
C Natural Connection: 554   GREEN
C Kalastria Healer: 552     BLACK
C Coralhelm Guide: 550      BLUE
C Voracious Null: 550       BLACK
C Bone Splinters: 546       BLACK
C Reckless Cohort: 545      RED
C Valakut Predator: 544     RED
C Makindi Sliderunner: 543  RED
C Lifespring Druid: 542     GREEN
C Brilliant Spectrum: 536   BLUE
C Ondu Champion: 535        RED
C Demon's Grasp: 534        BLACK
C Dutiful Return: 533       BLACK
C Shatterskull Recruit: 531 RED
C Broodhunter Wurm: 528     GREEN
C Sure Strike: 525          RED
C Lavastep Raider: 524      RED
C Mire's Malice: 523        BLACK
C Tandem Tactics: 523       WHITE
C Stonefury: 523            RED
C Seek the Wilds: 522       GREEN
C Giant Mantis: 522         GREEN
C Goblin War Paint: 519     RED
C Valakut Invoker: 516      RED
C Plummet: 515              GREEN
C Outnumber: 514            RED
C Tightening Coils: 508     BLUE
C Swell of Growth: 507      GREEN
C Angelic Gift: 506         WHITE
C Reclaiming Vines: 504     GREEN
C Kitesail Scout: 504       WHITE
C Volcanic Upheaval: 504    RED
C Ghostly Sentinel: 503     WHITE
C Territorial Baloth: 503   GREEN
C Courier Griffin: 502      WHITE
C Shadow Glider: 501        WHITE
C Earthen Arms: 500         GREEN
C Ondu Greathorn: 499       WHITE
C Skyline Cascade: 499      COLORLESS
C Spell Shrivel: 499        DEVOID(U)
C Belligerent Whiptail: 496 RED
C Sheer Drop: 490           WHITE
C Tajuru Stalwart: 490      GREEN
C Lithomancer's Focus: 490  WHITE
C Gideon's Reproach: 490    WHITE
C Stone Haven Medic: 487    WHITE
C Boiling Earth: 485        RED
C Mind Raker: 484           DEVOID(B)
C Snapping Gnarlid: 484     GREEN
C Fortified Rampart: 481    WHITE
C Mist Intruder: 477        DEVOID(U)
C Sludge Crawler: 476       DEVOID(B)
C Murk Strider: 475         DEVOID(U)
C Tajuru Beastmaster: 475   GREEN
C Oran-Rief Invoker: 473    GREEN
C Fertile Thicket: 472      COLORLESS
C Cliffside Lookout: 472    WHITE
C Blisterpod: 472           DEVOID(G)
C Felidar Cub: 469          WHITE
C Inspired Charge: 468      WHITE
C Makindi Patrol: 466       WHITE
C Incubator Drone: 463      DEVOID(U)
C Benthic Infiltrator: 463  DEVOID(U)
C Nettle Drone: 463         DEVOID(R)
C Dominator Drone: 457      DEVOID(B)
C Kor Castigator: 454       WHITE
C Smite the Monstrous: 454  WHITE
C Culling Drone: 453        DEVOID(B)
C Scour from Existence: 452 COLORLESS
C Evolving Wilds: 451       COLORLESS
C Vestige of Emrakul: 449   DEVOID(R)
C Swarm Surge: 449          DEVOID(B)
C Silent Skimmer: 447       DEVOID(B)
C Looming Spires: 446       COLORLESS
C Grave Birthing: 444       DEVOID(B)
C Eyeless Watcher: 443      DEVOID(G)
C Oracle of Dust: 443       DEVOID(U)
C Ruin Processor: 442       COLORLESS
C Sandstone Bridge: 440     COLORLESS
C Mortuary Mire: 438        COLORLESS
C Call the Scions: 436      DEVOID(G)
C Kozilek's Sentinel: 435   DEVOID(R)
C Complete Disregard: 430   DEVOID(B)
C Kozilek's Channeler: 428  COLORLESS
C Touch of the Void: 425    DEVOID(R)
C Eldrazi Skyspawner: 419   DEVOID(U)
C Salvage Drone: 416        DEVOID(U)
C Hedron Blade: 413         COLORLESS
C Eldrazi Devastator: 412   COLORLESS
C Unnatural Aggression: 411 DEVOID(G)

Non-devoid blue and black cards are heavily clustered at the top while colorless, devoid and white cards (white has no devoid cards in this set) are clustered at the bottom.

[awjackson]

Commons opened in 5000 Judgment boosters; black cards are noted by hand.

Judgment - boosters opened: 5000. Found cards: 75000
C Cabal Trainee: 1226           BLACK
C Toxic Stench: 1218            BLACK
C Treacherous Werewolf: 1177    BLACK
C Rats' Feast: 1166             BLACK
C Earsplitting Rats: 1158       BLACK
C Trained Pronghorn: 1060
C Defy Gravity: 1056
C Liberated Dwarf: 1045
C Canopy Claws: 1045
C Grip of Amnesia: 1043
C Envelop: 1041
C Barbarian Bully: 1041
C Mental Note: 1039
C Flaring Pain: 1035
C Lava Dart: 1030
C Ray of Revelation: 1025
C Spellgorger Barbarian: 1023
C Swirling Sandstorm: 1022
C Ember Shot: 1021
C Sudden Strength: 1020
C Wormfang Newt: 1019
C Anurid Barkripper: 1019
C Nullmage Advocate: 1019
C Guided Strike: 1012
C Mirror Wall: 1011
C Aven Fogbringer: 1010
C Wormfang Drake: 1010
C Phantom Tiger: 1007
C Harvester Druid: 1006
C Centaur Rootcaster: 1004
C Phantom Nomad: 1001
C Funeral Pyre: 996
C Prismatic Strands: 996
C Lead Astray: 995
C Giant Warthog: 992
C Dwarven Scorcher: 992
C Vigilant Sentry: 990
C Shieldmage Advocate: 990
C Book Burning: 989
C Border Patrol: 988
C Keep Watch: 980
C Hapless Researcher: 978
C Krosan Wayfarer: 978
C Battlewise Aven: 976
C Battlefield Scrounger: 974
C Cagemail: 972
C Goretusk Firebeast: 966
C Benevolent Bodyguard: 966
C Ironshell Beetle: 963
C Folk Medicine: 954
C Venomous Vines: 952
C Arcane Teachings: 943
C Suntail Hawk: 941
C Nantuko Tracer: 920

There are only five black commons in this set and they are perfectly clustered at the top of the sample; almost 10% more copies of the least-opened black card were opened than of the most-opened nonblack card.

[awjackson]

There's another problem with the algorithm, that isn't obvious from the above statistics and that I didn't even notice until I'd been tinkering with it for days. Because it treats multicolor cards as fractions of a card of each color, it is biased toward packs with multicolor cards of overlapping color combinations over nonoverlapping ones, and especially favors packs with multiple cards of the exact same guild. I am pretty sure this is the exact opposite of what real print runs for multicolor sets are designed to do!

[JayDi85]

@awjackson Just as reminds -- there are plans for collation settings for tourney and games (#8079, #6811 -- choose between random, paper and cube). So both random and paper collation must be workable.