Scute Swarmがエンジニアを苦しめる理由、Magicの指数関数的な挙動
Exponential Behavior in Magic: The Gathering

Magic: The Gatheringはチューリング完全なほど複雑で、Scute SwarmやLilianaのemblemのように能力が指数関数的に増殖するカードが存在する。著者は独自のルールエンジンArcanaを開発中で、約40万ゲームのランダム対戦をクラスタで実行したところ、Lilianaのultimateが発動した局面でemblem1回の解決に35秒かかる停止が発生。指数関数的挙動が実装者を襲う実例を、数式とコードを交えて解説する。
指数関数的な挙動とは、我々のような凡庸な計算機科学者にとっての敵なのだ。
HNでの議論
30- khaliostr
最近、オープンソースのMagicルネサンスがちょっとした盛り上がりを見せていて、すごくクールだと思っています。
Forgeはずっと前からありますが、Manabrew [1] を使ってWASM経由でブラウザ上で動かせるようになりました。私はメンテナーの一人で、主に友人とCommanderをもっと快適に遊びたいという理由で作っています。
一方、PhaseとIronsmithはRustで新しいエンジンを開発中で、GorgeはGoでエンジンを作りつつボットやクロスエンジンのテストツールも手がけていて、プロジェクト間のコラボレーションも始まっています。
Magicは実装するのがとんでもなく難しいゲームなので、これだけ多くの人が余暇に取り組んでいるのは本当に素晴らしいと思います。
Magicとソフトウェアエンジニアリングが好きなら、ぜひ私たちのところに遊びに来てください。いろいろなことが進行中で、参加できる余地もたくさんあります :)
- apitman
> このゲームは驚くほど複雑で、チューリング完全でもあり、入り組んだキーワードと膨大なメカニクスがある
ソフトウェアエンジニアはMTGにおける複雑さのあり方から多くを学べます。メカニクスの数は膨大ですが、比較的浅いです。タップ、マナ、ターンフェイズ、スタックなど、かなり小さなコアルールのセットを一度覚えてしまえば、通常は短いテキストを読むだけで新しいメカニクスを知識に追加できます。
通常、相互に作用するメカニクスはほんの一握りで、ゲーム中に馴染みのないものを調べる必要があるのもせいぜい1つか2つです。これはある種のプラグインシステムのようなものです。Unixも思い出させますね。
- gravitronic
MTGOの最大の欠点は、仮想カードに実際のお金を払う必要があり、時には紙のカード自体より高くつくことです。
Endstep.ccはこの分野の新参者で、サーバー上でforgeエンジンを動かしてオンラインプレイを可能にしています。今では私のお気に入りのフォーマット(pauper)を遊ぶのに一番好きな場所です。
- amluto
確かに、この特定の問題は理論的には(ほとんど)カードやカードのスタック(カードと付随するトークンなど)のコピー数を追跡するエンジンで対処できるでしょう。
「ほとんど」と言うのは:
- 確かに、N体のトークンクリーチャーをさまざまなカウンターの範囲で生成し、それでも指数関数的に多くの異なるスタックが存在するようにする方法はあるでしょう。
- 十分に速く成長する山は、保存するのに指数関数的なビット数(あるいはそれ以上)を必要とするかもしれません。
しかし少なくとも、元記事の特定の問題には対処できるはずです。
- thom
HNでこの古典を投稿するのはおそらくこれが唯一の機会だと思う: