Archive for August, 2009

Auto-drafter, cont’d

Mr Shellshear pointed out to me last night that the record of our M10 draft had the seating arrangement in the wrong order. So the auto-drafted results in my last post were still interesting, but didn’t necessarily boil down to actual packs with the right rarity distribution and whatnot.

The results with the correct seating order are below the fold. I also turned up the bias towards already-drafted cards. I still wouldn’t call the behaviour sensible, but I wouldn’t be totally upset with the pool it drafted. (In particular, I made good use of Whispersilk Cloak on the night, especially alongside an Enormous Baloth. And I seem to have picked up a Protean Hydra somehow.)

Read more

No comments

Magic auto-drafter

This is kind of cool.

I’ve had an idea for a while to make an automatic draft picker for Magic: the Gathering. The idea was to use a sort of naive Bayes approach, using the records of previous drafts to estimate:

  • the probability that a player, given a pack with cards A and B, will pick A over B;
  • the probability that a player, given a pack with card A and having already drafted card B, will pick A over the other cards in the pack.

The idea is that the former gives an estimate of card quality, and the latter estimates the influence of earlier picks on each card. To use this in a draft, you (that is to say, the program that’s doing it for you) just multiply all the probabilities together for each card, and pick the one with the highest score.

So I finished coding it up this morning. Then I trained it using four Magic 2010 drafts from the MtG website (e.g. this one), then re-ran our draft from a couple of weeks ago, to see what would have happened if we were all replaced by auto-drafters.

The results are below the fold. And it’s not completely ridiculous. It’s probably less focused in colours than it could be; maybe there’s some tweaking to be done by weighting the influence of previous picks. But at a glance, I can’t see anyone’s card pool that couldn’t be made into, say, a two-colour deck with a third splash. (Edit: Now that I think about it, this is probably true of any 45 random cards. Hmm. Well, most of the pools have a strong leaning towards two or at most three colours, and Andrew C could almost get away with mono-green.)

Bizarrely, it’s drafted a red-blue deck for me instead of the white-green deck I actually played (although I did feel bad about not using that first-pick Lightning Bolt in the second pack).

There are a few hiccups because the training set of four drafts wasn’t big enough – there’s no way Ajani should have gone fifth pick, for example. I’m optimistic that throwing more data at it would make it better. In an ideal world, I’d somehow get hold of the results of every Magic Online draft to pump through it, and it would represent the collective wisdom of every online player everywhere.

In fact, if anyone from Wizards would like to do this, let me know. :)

Actually, that’s not as silly as it sounds. (Well, letting me do it probably is.) There’s already an AI of some kind controlling the online draft simulator. That could be something similar to my system, or it could just be a hand-crafted pick order along with some kind of futzing to get it to pick roughly consistent colours. It’d be interesting to find out how it works. (But they’ll never tell us.)

Interestingly, some kind of auto-picker could be useful for Magic Online. If you don’t pick a card within the time limit in an online draft, it randomly picks one for you. (At least, it was random last time I checked. I haven’t drafted online for a while.) MO has recurring problems with lag and dropped connections, so it would make a lot of people very happy to have an auto-drafter that makes vaguely intelligent choices when they can’t do it themselves.

Now, it can’t be too good, or you could start relying on it to do the draft for you. This could be a showstopper, since the outcome of a draft is supposed to depend on the players’ skill. (In fact, there’s a good chance that someone in Wizards has already had this conversation.) But maybe an auto-drafter that’s not a genius, but knows not to take the basic land and will generally pick playable cards in your colours, would be just enough of a safety net that people wouldn’t be driven to mass killings when their connection drops. Maybe.

I might put the code up later (after I do a cleanup and/or rewrite – it’s pretty ugly right now). Meanwhile, keep reading for the results of the re-draft.

Edit 2: I tried doubling, then quadrupling the effect of the already-drafted cards on the next pick. This puts nearly everyone solidly into two colours. (Unfortunately it leaves Mr Shellshear with an impressive blue-white deck, and anyone who remembers our first Lorwyn draft will realise what a bad idea that is. Apparently some people do just open all the good cards.) I’d post the new results, but I’m wary of picking at this too much, and would rather just leave the original results as they are until I get around to cleaning up the code.

Read more

No comments

Maintenance

Finally got around to fixing the “solve today’s” link on my Target solver.

My but that’s some ugly code. The fix was pretty simple but I’m fighting the urge to throw it away and start again.

No comments

Multicolour Magic

In last night this morning’s post I talked a bit about how I missed Magic: the Gathering’s ability to support mono-colour decks during the recent tri-colour-focused Alara block. So now I’m going to jot down some thoughts about how a Magic expansion could revisit a multi-colour theme (which it probably will) without giving up the reward for focusing on one colour.

The high concept is a plane that’s struggling against segregation based on mana colour alignment. (There’s an obvious political/moral statement in here that Wizards would probably be well-advised to avoid.) The inhabitants of the plane have, for most of their history, kept separate communities that are very strongly aligned with one colour. However, in more recent times a growing number of radicals have started coming together as a “mixed” faction that blends all five colours.

Naturally, there’s tension between these groups. The new faction sees this as an opportunity to combine the best of each of the colours, compensate for the weakness of each, and create something new that’s better than the sum of its parts. The traditional, segregated communities (most of which consider their own colour to be self-evidently superior to the others) see this multi-colour business as heresy, a watering-down of the pure, separate sources of mana that are at the foundation of magic. Paradoxically, there’s a kind of uneasy consensus among the mono-colourists that the new threat is a bigger problem than their existing diffences; they’re not going to actively cooperate with each other, but they might develop attacks that are more effective against “mixed” heretics than against each other (example).

Mechanically, the cards (not all of them, necessarily – there could be some non-aligned cards, like in Ravnica block) would fall into two categories. Mono-colour cards would reward a heavy investment in that colour, with abilities like Chroma and heavily coloured costs like Overrun. Multicolour cards would reward colour diversity, revisiting Domain and WUBRG cards (Mark Rosewater said recently that he would have taken the five-colour theme out of Conflux in hindsight, so they could plausibly take another swing at it), and other shenanigans like Sunburst. Mana fixing and multilands would mostly fall in the latter category – something like the Ravnica block bouncelands that makes multi-colour costs easier to pay while making it hard to generate lots of the same colour.

The optimal decks – for constructed play, at least – should be (a) mono-colour and (b) five-colour. Ideally, both (technically, all six) of these archetypes should be feasible in draft as well. (I’m not sure how this would work for sealed.) Drafting a mono-colour deck with no splash would probably be a lofty goal rather than something you achieve in most drafts, but there should be cards that reward you the closer you get to it. (Quick idea: an undercosted mono creature with “whenever you play a non-[this creature's colour] spell, sacrifice [this]“.)

Anyway, that’s the idea. Thoughts? Job offers from WotC?

No comments

Can’t sleep

Was trying to get to sleep, got mentally worked up about something, and now I can’t. Sleep, that is. So here are some random thoughts about nothing.

The phrase “I don’t know” can be used in two completely different ways that are almost diametrically opposed in terms of what the speaker is implying. Observe:

  1. “I don’t know why the sky is blue.”
  2. “I don’t know why people like Britney Spears.”

There should be different words for these.

I’ve been messing around with a kd-tree to find nearest neighbours in a vaguely secret thing I’ve been working on (not very secret, or even interesting enough to justify calling it secret, which I’ve now done three times, so it’ll be really anti-climactic when I link to it, which I will as soon as it’s public). Wikipedia says this about the performance improvement for nearest-neighbour search:

These asymptotic behaviors only apply when N is much greater than the number of dimensions. In very high dimensional spaces, the curse of dimensionality causes the algorithm to need to visit many more branches than in lower dimensional spaces. In particular, when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points.

I’m starting to suspect that this statement is way too weak. My rough back-of-the-mental-envelope conclusion is that the performance boost only happens when the number of points is much higher than two to the power of the number of dimensions. I’m not confident enough in this statement to edit the Wikipedia article, but I’d be interested if anyone can explain why I’m wrong.

Mentioned Richard Buckland, lecturer extraordinaire, in an earlier post. Last week I took a few hours off work one afternoon to wander into one of his first-year uni lectures. It turned out to be one of the few lectures from this year that’s made it onto YouTube. (They’re all supposed to go up at some point, but anyone who’s ever dealt with video files knows that they have a kind of inertia or built-in procrastination field or something.)

After the lecture (actually, after the extension lecture that comes after this), I chatted to him for a while about some stuff, which has been mulling over in my head since then, and which I’m not going to say much about right now (what the hell kind of an introverted blog post is this)… um… yeah. More on this soon, maybe.

Finally started watching Firefly earlier tonight. I feel like I’m getting my geek credentials back in order.

Picked up a cheap-ish tablet laptop in an online auction a few weeks ago. It’s ex-lease or something. Not the ThinkPad that I really wanted, but a good starting point considering that I’m not entirely sure why I wanted it at all (at least, now that my career as a webcomic artist has been definitively shut away in the Closet of Things that are Unlikely to Happen). Anyway, it is really, really cool.

I installed Xubuntu on it. Xubuntu has come a long way. I’m not entirely converted away from mainline Ubuntu yet, but for a lower-performance machine – and in a scenario where screen real estate is particularly valuable and can be conserved with a panel that behaves well on the side of the screen, which is an act Gnome hasn’t quite gotten together yet – it behaves very nicely indeed.

We did a Magic 2010 draft at Mr Shellshear’s place last Friday. For me, it really captured the feel of old-school Magic. I’ve enjoyed Alara block, but one thing that bugged me about it is that mono- or even dual-colour decks were a non-option. I’ve always thought that one of the big appeals of the Magic mana system is the ability to choose between the breadth of a multi-colour deck and the smooth focus of a mono deck. In fact, I think one of the crucial moments in many a beginning casual player’s Magic education is when he (or she… but let’s face it, it’s probably he – apologies to Michelle and Kat) manages to corral enough cards of the same colour to make up a deck.

For me, many years ago, it was a green deck. Its theme was the somewhat high-concept “every green card and forest I own” and not much beyond that, but the payoff of freedom from mana problems is an experience I’ve never forgotten.

Alara block’s three-colour theme was an interesting design area, and would seem to have been a popular one, but it turned mana fixing from optional to mandatory. It changed the game from one where multi-lands and whatnot were one of the ways of getting your spells out reliably – the other being to focus on one colour, which is an interesting, flavourful, and personality-reflecting decision – to one where they were the only way. That took something away from the game in my mind, and I’m happy to be back on solid monocolour ground again.

Okay, I think I’m out of random thoughts, and am starting to get vaguely sleepy. G’night all.

8 comments

Uptime

Quick update on the status of my transplanted Ubuntu box.

Time since the start of that post: 44 days, 15 hours, 36 minutes.

Continuous uptime of the computer in question: 44 days, 14 hours, 48 minutes.

:)

No comments