magefree / mage

Magic Another Game Engine
http://xmage.today
MIT License
1.9k stars 774 forks source link

BoosterCollators are only shuffled once, at startup #8179

Closed awjackson closed 3 years ago

awjackson commented 3 years ago

boosterCollator.shuffle is only called in the constructor of ExpansionSet. There is a ShuffleCollator method in ExpansionSet but it is never called from anywhere (should it be called in createBoosterUsingCollator, perhaps?)

Because the collators for each set are only shuffled once, consecutive boosters are correlated with each other--each one follows the print runs exactly where the previously-generated booster left off. A player who has memorized the print runs would in theory be able to tell exactly what commons and uncommons every other player in their draft pod opened.

Theros Beyond Death - boosters opened: 5000. Found cards: 75000
C Forest: 1000
C Swamp: 1000
C Island: 1000
C Mountain: 1000
C Plains: 1000
C Setessan Training: 626
C Aspect of Lamprey: 626
C Temple Thief: 626
C Nexus Wardens: 626
C Plummet: 625
C Omen of the Dead: 625
C Nylea's Forerunner: 625
C Relentless Pursuit: 625
C Gift of Strength: 625
C Discordant Piper: 625
C Scavenging Harpy: 625
C Omen of the Hunt: 625
C Lampad of Death's Vigil: 625
C Blight-Breath Catoblepas: 625
C Underworld Charger: 625
C Moss Viper: 625
C Rage-Scarred Berserker: 625
C Soulreaper of Mogis: 625
C Loathsome Chimera: 625
C Nyxborn Marauder: 625
C Nyxborn Colossus: 625
C Skola Grovedancer: 624
C Sunmane Pegasus: 531
C Aspect of Manticore: 531
C Triumphant Surge: 531
C Sleep of the Dead: 531
C Nyxborn Seaguard: 531
C Nyxborn Courser: 531
C Vexing Gull: 531
C Stampede Rider: 531
C Thrill of Possibility: 531
C Riptide Turtle: 531
C Leonin of the Lost Pride: 530
C Karametra's Blessing: 530
C Transcendent Envoy: 530
C Wrap in Flames: 530
C Naiad of Hidden Coves: 530
C Underworld Rage-Hound: 530
C Heliod's Pilgrim: 530
C Indomitable Will: 530
C Ichthyomorphosis: 530
C Final Flare: 530
C Incendiary Oracle: 530
C Sentinel's Eyes: 530
C Triton Waverider: 530
C Starlit Mantle: 530
C Oread of Mountain's Blaze: 530
C Hero of the Games: 530
C Omen of the Sun: 530
C Portent of Betrayal: 530
C Nyxborn Brute: 530
C Elite Instructor: 530
C Glory Bearers: 530
C Stern Dismissal: 530
C Deny the Divine: 530
C Warbriar Blessing: 523
C Brine Giant: 523
C Final Death: 523
C Unknown Shores: 523
C Nylea's Huntmaster: 523
C Memory Drain: 523
C Arena Trickster: 523
C Inspire Awe: 523
C Irreverent Revelers: 523
C Altar of the Pantheon: 523
C Revoke Existence: 523
C Flummoxed Cyclops: 523
C Return to Nature: 522
C Pious Wayfarer: 522
C Mogis's Favor: 522
C Omen of the Forge: 522
C Captivating Unicorn: 522
C Fruit of Tizerus: 522
C Bronze Sword: 342
C Wings of Hubris: 334
C Grim Physician: 334
C Satyr's Cunning: 334
C Hero of the Pride: 334
C Traveler's Amulet: 334
C Hyrax Tower Scout: 334
C Chain to Memory: 333
C Infuriate: 333
C Iroas's Blessing: 333
C Thirst for Meaning: 333
C Ilysian Caryatid: 333
C Pharika's Libation: 333
C Dreadful Apathy: 333
C Mire's Grasp: 333
C Voracious Typhon: 333
C Witness of Tomorrows: 333
C Venomous Hierophant: 333
C Towering-Wave Mystic: 333
C Setessan Skirmisher: 333
C Omen of the Sea: 333
C Thaumaturge's Familiar: 333
C Daybreak Chimera: 333
C Flicker of Fate: 333
C Eidolon of Philosophy: 333
C Rumbling Sentry: 333
C Funeral Rites: 333
C Skophos Warleader: 333
U Fateful End: 188
U Commanding Presence: 188
U Soul-Guide Lantern: 188
U Siona, Captain of the Pyleas: 188
U Impending Doom: 188
U Alirios, Enraptured: 188
U Sweet Oblivion: 188
U Klothys's Design: 188
U Destiny Spinner: 188
U Renata, Called to the Hunt: 188
U The Birth of Meletis: 188
U Underworld Fires: 188
U Rise to Glory: 188
U Field of Ruin: 188
U One with the Stars: 188
U Agonizing Remorse: 188
U Daxos, Blessed by the Sun: 188
U Anax, Hardened in the Forge: 188
U Tymaret, Chosen from Death: 188
U Eutropia the Twice-Favored: 188
U Alseid of Life's Bounty: 188
U Hero of the Nyxborn: 188
U Nessian Wanderer: 188
U Escape Velocity: 188
U Pheres-Band Brawler: 188
U Inevitable End: 188
U Mystic Repeal: 188
U Staggering Insight: 188
U Dreamstalker Manticore: 188
U The Binding of the Titans: 188
U Acolyte of Affliction: 188
U Cling to Dust: 188
U Mire Triton: 188
U Elspeth's Nightmare: 188
U Lagonna-Band Storyteller: 188
U Sage of Mysteries: 188
U Furious Rise: 188
U Callaphe, Beloved of the Sea: 188
U Favored of Iroas: 188
U Entrancing Lyre: 188
U Phalanx Tactics: 188
U Shoal Kraken: 187
U Heliod's Punishment: 187
U Underworld Dreams: 187
U The Triumph of Anax: 187
U Threnody Singer: 187
U Archon of Falling Stars: 187
U Mischievous Chimera: 187
U Dawn Evangel: 187
U Chainweb Aracnir: 187
U Reverent Hoplite: 187
U Nyx Herald: 187
U Heroes of the Revel: 187
U Wolfwillow Haven: 187
U Pharika's Spawn: 187
U Shimmerwing Chimera: 187
U Minion's Return: 187
U Whirlwind Denial: 187
U Skophos Maze-Warden: 187
U Nessian Hornbeetle: 187
U Medomai's Prophecy: 187
U Hydra's Growth: 187
U Blood Aspirant: 187
U Stinging Lionfish: 187
U Devourer of Memory: 187
U Banishing Light: 187
U Setessan Petitioner: 187
U Sea God's Scorn: 187
U Hero of the Winds: 187
U Thundering Chariot: 187
U Enemy of Enlightenment: 187
U Glimpse of Freedom: 187
U Careless Celebrant: 187
U Warden of the Chained: 187
U Gray Merchant of Asphodel: 187
U Hateful Eidolon: 187
U Drag to the Underworld: 187
U Mirror Shield: 187
U Dreamshaper Shaman: 187
U Slaughter-Priest of Mogis: 186
R Allure of the Unknown: 84
R Phoenix of Ash: 84
R Gravebreaker Lamia: 84
R Temple of Enlightenment: 84
R Gallia of the Endless Dance: 84
R Enigmatic Incarnation: 84
R Ashiok's Erasure: 84
R Woe Strider: 84
R Protean Thaumaturge: 84
R Tectonic Giant: 84
R Mantle of the Wolf: 84
R Temple of Abandon: 84
R Temple of Deceit: 84
R Tymaret Calls the Dead: 84
R Erebos's Intervention: 83
R Dalakos, Crafter of Wonders: 83
R Shatter the Sky: 83
R Purphoros's Intervention: 83
R Bronzehide Lion: 83
R Nylea's Intervention: 83
R Nyx Lotus: 83
R Storm Herald: 83
R Dryad of the Ilysian Grove: 83
R Temple of Malice: 83
R Dream Trawler: 83
R Eidolon of Obstruction: 83
R Archon of Sun's Grace: 83
R The First Iroan Games: 83
R Storm's Wrath: 82
R Nadir Kraken: 82
R Thryx, the Sudden Storm: 82
R Haktos the Unscarred: 82
R Elspeth Conquers Death: 82
R Aphemia, the Cacophony: 82
R Shadowspear: 82
R Nightmare Shepherd: 82
R Nessian Boar: 82
R Temple of Plenty: 82
R Heliod's Intervention: 82
R Kunoros, Hound of Athreos: 82
R Idyllic Tutor: 82
R Atris, Oracle of Half-Truths: 82
R Thassa's Oracle: 82
R Underworld Breach: 82
R Eat to Extinction: 82
R Thassa's Intervention: 82
R Taranika, Akroan Veteran: 82
R Treacherous Blessing: 81
R Arasta of the Endless Web: 81
R Labyrinth of Skophos: 81
R The Akroan War: 81
R Setessan Champion: 81
R Wavebreak Hippocamp: 80
M Uro, Titan of Nature's Wrath: 42
M Kroxa, Titan of Death's Hunger: 42
M Kiora Bests the Sea God: 42
M Polukranos, Unchained: 42
M Erebos, Bleak-Hearted: 42
M Calix, Destiny's Hand: 41
M Elspeth, Sun's Nemesis: 41
M Ashiok, Nightmare Muse: 41
M Heliod, Sun-Crowned: 41
M Ox of Agonas: 41
M Nylea, Keen-Eyed: 41
M Nyxbloom Ancient: 41
M Thassa, Deep-Dwelling: 41
M Purphoros, Bronze-Blooded: 41
M Klothys, God of Destiny: 40

You can see that within each print run there is only a variance of +/- 1 in how many of each card are opened.

(There is also a massive imbalance between the four common print runs, but that's a separate issue...)

theelk801 commented 3 years ago

This is actually intentional, the idea was to mirror how real booster packs work.

awjackson commented 3 years ago

In paper Limited tournaments do they typically give each player boosters from a single booster box, in order? I expect that randomizing the boosters is more typical. The `Magic: The Gathering Tournament Rules Effective July 23, 2021' only has this to say about booster randomization:

If the Tournament Organizer allows players to provide their own product, that product must be pooled with the rest of the product for the tournament and randomly distributed.

There are war stories from GPs like this one of people opening three copies of some premium common or two of some uncommon in their Sealed pool. Certainly on MTGO the Sealed pools are much more random than those produced by xmage using the current collation code.

When old-school players talked about memorizing print runs to get edges in draft, I'm pretty sure they meant looking at a pack with one common or one uncommon missing and deducing what their neighbour took, not looking at their freshly-opened pack and deducing what their neighbours opened.

NibiruMTG commented 3 years ago

@theelk801 First off, I really appreciate what all of you are doing here - I love XMage and I can only imagine how much work went into getting it to where it is now. But I don't see the benefit of this whole print run thing. I'm no programmer, just someone who drafts a lot and this whole idea to mirror real packs doesn't seem worthwile to me.

A print run is an artifact of how paper packs are created where true randomization isn't possible, and is therefore certainly a flaw and not a feature. In my opinion, the goal for digital packs should always be perfect randomization. Maybe with some additional color balancing, sure, as long as that doesn't make certain cards more or less common like it currently seems to do. In paper print runs, there is also the problem of the short-printed 101st common which I hope is also something that isn't brought to XMage because it's very counterintuitive, unnecessarily confusing, and also definitely a flaw and not a feature.

And then, like awjackson said, paper packs always get shuffled before drafting, at the bare minimum by giving every player their 3 packs and thus breaking up the print run, so boxes definitely don't get drafted in the order of the print run. And doing so could absolutely lead to exploitable situations - I remember this once was a thing on Arena where you could tell which uncommon was taken out of the pack and it made drafts almost totally unplayable for me. Even if it is more complex here and not as easy to exploit, as long as there's still the chance to figure out which card your neighbor took, the new system feels like a step in the wrong direction.

And if you're intent on introducing these print runs, please at least give us the option to opt out of them via a simple checkbox in the draft settings. Same goes for the color balancing which is already optional on other sites like mtgadraft.tk. That would be really appreciated so everyone can draft the way they want to. Thank you for reading and keep up the great work!

theelk801 commented 3 years ago

@awjackson The thought process to me (which I'm open to changing) is that it was more like playing at a local store, where 8 players sit down to draft and the TO opens a booster box and pulls out packs from it. I considered setting up a system where the packs would get shuffled before each draft in a self-contained collator, but given that people can (and do) map print runs IRL it didn't seem like it was worthwhile to implement. I should also note that after asking in a few places, it doesn't seem like boosters are "shuffled" even at higher level events.

@NibiruMTG There's a lot to respond to here, so I'd like to start by saying that "true randomization" isn't necessarily desirable, and that there's a big difference between what the average person thinks is random and what's actually random. Here's a good article about the topic.

Magic collation is a complicated process, and if they wanted it to be truly random they likely could do it. They're not just balancing colors, either. They make sure that removal doesn't show up too much, and they make sure that concurrent packs don't have too much in common with each other. But more importantly, sets are designed with this collation in mind, that's why they still use it in digital products. It's a part of the whole.

If you really want, I suppose we could add an option to opt out of the collation, but I really don't advise it if you want an authentic draft experience.

awjackson commented 3 years ago

@theelk801

it doesn't seem like boosters are "shuffled" even at higher level events.

I used test_CollectBoosterStats to generate ten six-pack THB Sealed pools. None of the pools had more than one pair of duplicate commons, and none had any duplicate uncommons. There were actually as many duplicate rares (due to the separate print runs in this set for regular and premium versions) in the pools as there were duplicate commons.

These pool statistics simply do not resemble real-world paper Sealed events. Look at the deck lists from GP Melbourne 2018 or GP Warsaw 2018 (the most recent events for which I could find any Sealed lists, and unfortunately only the main decks and not the entire pools are shown). Excluding Guildgates, Justin Robb's deck from Melbourne has five pairs of duplicate commons, Taiga Tsujikawa's has two, and Shawn Khoo's has four. Taylor Dix's deck from Warsaw has two of the uncommon Goblin Banneret.

I also generated ten 24-pack Draft pods. None of the pods had more than 3 or fewer than 2 copies of any common. There is no way that this kind of extreme homogeneity is either authentic to paper Draft or desirable. If nothing else, think of the effect it has on "collect-em-all" commons like Seven Dwarves or the cycle from M20.

Note that your idea of generating sequential packs and then shuffling them among players in the pod does not solve the common homogeneity issue.

NibiruMTG commented 3 years ago

@theelk801

But more importantly, sets are designed with this collation in mind, that's why they still use it in digital products. It's a part of the whole.

Certainly not your version of the collation with the correlated packs. Are you aware that even on Arena you can get 5-7 copies of a common in a draft? It happens quite often actually. To me randomness means variance and throwing that all out of the window just seems like a terrible idea. One of the most fun drafts we did on XMage this year was 3x Coldsnap where someone happened to pick up 10x Sound the Call (one of the collect-them-all cards). Extreme outliers like this are what makes draft refreshing and replayable.

And to add onto what awjackson was saying - a draft where you're guaranteed to open 2-3 copies of every common at the table is just ridiculous. Just a few examples - in such a draft, you'll know that you'll never see a fourth copy of any common and passing the third means never getting another chance at it again. And even worse - when you have three copies of a card in your deck, then you know that your opponents in that pod can't have that card and so you don't need to play around it. You'd have to constantly keep track of the number of commons you see to maximize your win percentage. Needless to say that this is 100% not what WotC has in mind with their print runs, as evidenced by the fact that something this extreme doesn't even remotely happen on MTGO or Arena.

I would go a step further and say, as long as your system doesn't include the possibility of having at least as many copies of a single common as you can have on Arena, it is a flawed system. Even if it caps out at 5 it's bad. What WotC is trying to do is a lot closer to true randomness than you think it is.

Case in point: Here are two decks I've drafted last year on Arena which both had 6 copies of one of the best commons in the set:

2020-08-03 (M21) (3-0) RG Mindless Aggression

2020-04-29 (IKO) (7-1) RW Hyper Snare

tehtmi commented 3 years ago

Hi, I'm AKA Lethe, author of the collation project. @theelk801 invited me to comment here.

I'm going to limit my discussion to the topic at hand. I'm also mostly going to avoid giving my opinion.

The collation project mostly discusses the single pack model, so I have usually not provided data about how multiple packs from the same box should be modeled. This actually depends a lot on the printer. Japanese-printed and Belgian-printed packs generally do just have one string of commons and one string of uncommons running through the whole box (like what XMage is doing as I understand). But, this is not true for US-printed boxes. (I didn't check all the sets, but I guess XMage is usually or always trying to model US packs/boxes.)

There are two US-printing schemes in recent use (and some sets have used both). The older scheme (used exclusively in the US for large sets from Shards of Alara until pretty recently) has four different common strings and two uncommon strings running through each box. The newer scheme has two or three commons strings and one uncommon string.

Out of those recent sets for which I see XMage collators, THB and IKO use the older scheme. ZNR, KHM, and MH2 use the newer scheme with two common strings. (I haven't looked at the uncommons properly in US ZNR, so no comment there.) 2XM and STX use three common strings, except for the low as-fan run which has one string. AFR uses 2 runs for the lower as-fan A and C runs, and 3 for the higher as-fan B run. AFR uncommons are also weird, and the higher as-fan uncommon run also has 2 strings. CMR is weird, and only has one string for everything. (This stuff may be worth double checking, but it should be mostly right.)

I don't really have a model for how the different strings in a box are related. I think it would be reasonable to model them as independent, although this may not actually be true. In my experience, there is usually overlap, but I haven't analyzed it carefully. Note that since cards from different runs generally appear at a rate proportional to the period of the run, the periods tend to be naturally synced. (The connection between common runs and foils in the older scheme breaks this syncing in some instances, though.)

We could also look at box modeling in more detail. This is also something I don't really have a model for, but I can discuss it a little bit superficially. First, we should address whether a box actually contains 36 "consecutive" packs. This is usually true for all printing regions. When it is not true, usually there is only a minor deviation from this, such as a box containing 36 of a consecutive string of length 37 or 38. There are also rare cases where large numbers of packs are skipped, or I can't detect a correlation between all packs, but there is always some correlation between packs. It's possible that these deviations are not intended. The Japanese printing region seems to have accurate collation and never gets weirdness like this. US definitely gets it; not sure if Belgium gets it much, but I have the least Belgian data.

There is also the question of how the packs are arranged within the box. I'm intentionally not going to discuss this in much detail, but the packs in a box don't always appear in the same order. This depends on the printer, but even for the same printer, different boxes may use a different order (although I wouldn't describe it as being well randomized). If a drafter was taking packs out of the box without randomization, there are definitely cases where they could take consecutive packs, but they could also easily take packs that were not consecutive.

In summary, drafts out of a single US box probably have quite a bit more variability in common (and sometimes uncommon) duplication compared to what XMage is currently doing. For Belgian and Japanese boxes, it is probably similar.

The number of packs in a box also has some applicability here. Picking 24 at random from 36 shuffled packs is quite a bit different in terms of "common homogeneity" than just shuffling 24 consecutive packs. Also, real drafts will often mix the 12 leftover packs of one box with 12 packs from a different box. (Or with odd pod sizes, different mixes from two boxes will also happen naturally.) There is such a thing as case correlation (depending on the set and printer), but I guess this is not likely to have much impact on a real draft.

I didn't look closely, but it didn't seem like XMage was modeling foils. Foils can also add a little bit of variance to duplication.

Regarding the short-printed common, I will note that it seems almost always to be a card that is quite weak in draft. I think this is intentional. But, there is not always a short-printed common depending on the printer and set. (For example, Japanese printings never have a short-printed common due to using a different sheet size.) So, I think it is not really an intentional part of the environment, just a compromise of sorts.

I remember this once was a thing on Arena where you could tell which uncommon was taken out of the pack

Yes. With print runs, it will always be possible to improve your guess about what the previous player(s) took, and sometimes you can tell outright. IIRC, the uncommon runs on Arena were too repetitive which made this much too easy and it is probably not so easy in paper. And it will generally require some memorization or referring to outside materials. (But, it is a complicated issue.)

Maybe with some additional color balancing, sure, as long as that doesn't make certain cards more or less common like it currently seems to do.

Color-balancing is a real and intentional benefit of print runs. You also (maybe) allude to the fact that XMage's color-balancing algorithm causes problems. I didn't look at it too carefully, but it's probably true -- rejecting and re-rolling packs that are poorly balanced naturally creates a bias against colorless cards (and maybe for/against multicolored cards) (and maybe between colors if colors are naturally unbalanced). (But, this problem is not unsolvable.)

But more importantly, sets are designed with this collation in mind, that's why they still use it in digital products.

I haven't looked a digital collation, but my understanding is that MTGO actually used the real US paper print runs at one time (although obfuscated somewhat by MTGO re-sorting the pack, and possibly some of the collation mechanics were not identical even though the runs were the same). No idea if it still does. But, I also don't think anyone ever tried to determine if there was any dependence between packs in a pod.

(Note also, I guess, that the majority of play on MTGO these days seems to be league play as well, so pods are less relevant though obviously still important for the draft portion.)

There were actually as many duplicate rares (due to the separate print runs in this set for regular and premium versions)

This is a real phenomenon in paper as well. For certain printing regions and sets, you will also see duplicate regular rares due to the complexity needed to work out the rarities the way they wanted, but they seemed to have backed off of this for MH2 and AFR (maybe due to people complaining).

theelk801 commented 3 years ago

Hey everyone, just wanted to say that I’ve been busy lately but I’m not disregarding this issue. I’m definitely open to changing the collation setup if it gives results that do a better job reflecting real life booster distributions.

awjackson commented 3 years ago

@theelk801 I've found myself kind of evolving into a specialist on xmage booster-generation and Limited issues, if you understandably want to focus your own time on implementing new cards and mechanics and on fixing gameplay bugs. Right now I'm testing and iterating on an improved color balancing algorithm (#8177); I'm also working on fixes for OGW (#8173) and for FRF which I just noticed a problem with, and I still intend to check and if necessary submit fixes for the remaining sets that you have done BoosterCollators for (Strixhaven, Double Masters, MH2, TSR and AFR) as soon as I have time to.

The idea I had for this was to pregenerate a "booster box" of 36 sequential packs for each set (presumably as a member of ExpansionSet, like the cached inBoosterMap etc) and shuffle the order of those packs. Then createBoosterUsingCollator would return the next pack in the "box", recreating (and reshuffling) it once it becomes empty. shuffleCollator can then be called to manually regenerate a fresh "box" if greater randomness is desired for specific Limited formats. For example, for standard Draft, generating a fresh booster box between each round of packs might be a good compromise between complete randomness and the extreme homogeneity that is currently produced.

Alternately, if all of this is too complicated then we can just always shuffle the collator before generating each booster, but if nothing else it is handy to be able to generate sequential packs for the kind of testing I've been doing.

theelk801 commented 3 years ago

I definitely like the idea of creating a "booster box" type of thing, and I'm glad to have someone else working on this aspect of the project.