同人版 Magic: the Gathering のAIルーチンが興味深い

2014/04/25M:tG, ゲーム

Magic: the Gathering という時間と金を食い尽くすゲームがある。

私が知ったのは日本語第４版発売後なので1996年ごろ。REXAに改築される前のベスト電器那覇店が扱い始めたのがきっかけ。
JAVY地下の大会の決勝でカウンターポストに負けたんだよなあ。

カードゲームというジャンルが M:tG 以前と以後に分けられるほど画期的なゲームで、ポケモンカードゲームや遊戯王などの派生ゲームがワラワラ誕生したのも懐かしい記憶だ。

Amazon:MAGIC The Gathering The Online Plus完全日本語版

コンピュータ版 Magic: the Gathering

沖縄には碁会所や雀荘は多く存在するのだが、マイナーゲームは対戦相手を探すのが一苦労。将棋ですら道場は少ない。まして舶来のゲーム。人間の相手は探しづらいので、コンピュータに相手をさせたくなるのは自然の成り行きだ。

さらにTCG自体が金食い虫のゲームなので、コンピュータで代行できれば安上がり。私も市販のソフトやiPadアプリも含めて色々と試している。

Microprose版 M:tG を再発売して欲しいのだけど…

Microprose版 Magic: the Gatheringは、Magic初期のPower9と呼ばれる（1枚数万円のプレミアがついている）カードを思う存分使えて楽しめる。
私も最近までVMware+Windows98で遊んでいた。それぐらい面白い。WindowsXPですら過去のものになった今となっては、さすがにWindows98は古すぎる。Virtual Machineを使わずに遊びたいと思う。
(最近のマシンでは速すぎて操作が難しいのだ。VMの速度落とせないかな？）

でも、発売元の Microproseは亡くなったし、M:tG発売元の Wizards of the Coast は最新のカードを売るのに忙しい（そりゃそうだよね）。

私のように再販を望む人が多かったのか、対局可能な２つの同人ソフトが開発されている。

Forgeとmagarenaだ。どちらもそれなりに面白い。

M:tGはコンピュータには難しい

Magicは恐ろしくルールの複雑なゲームだ。現時点のルールはテキストファイルで620KBにも及ぶ。

あまりにも複雑なゲームなので、普通に人とコンピュータが対戦すれば当然のように人間側の圧勝になる。
それではゲームとして面白くないため、初期のゲームプログラムは特殊ルールを付け加えたり・コンピュータ側に積み込みを許すことでバランスを保っていた。まるで、お正月に放映されていた大逆転将棋のように。

ちなみに、ドリームキャスト版のラスボスは極悪なまでに積み込んでくるので、対策デッキでないとまず勝てない。

Forgeのシステム

20140425-forge

同人版M:tGの Forgeは作者のブログの記述から推測するとMicroprose版の後、ほどなくして開発が始まったようだ。20世紀終盤のころだろうか？ (svnには最近の情報しかないので、詳細不明）。

現在の完成度は非常に高く 99%近くのカードが収録されており、新カードへの対応も素早い。

カードの情報は1枚ごとに定義ファイルに記載されている。 Giant Growth/巨大化 は、日本語ならこう書かれているカードだが、

Giant Growth / 巨大化 (緑)
インスタント
クリーチャー１体を対象とする。それはターン終了時まで+3/+3の修整を受ける。

Forge の定義ファイルではこうなる。

Name:Giant Growth
ManaCost:G
Types:Instant
A:SP$ Pump | Cost$ G | ValidTgts$ Creature | TgtPrompt$ Select target creature | NumAtt$ +3 | NumDef$ +3 | SpellDescription$ Target creature gets +3/+3 until end of turn.
SVar:Picture:http://www.wizards.com/global/images/magic/general/giant_growth.jpg
Oracle:Target creature gets +3/+3 until end of turn.

（強調は私による）



コンピュータに分かりやすく記述するために、 A: の後ろに所定の書式で効果が書かれている。昔のコンピュータの定義ファイルってこうだったよなーと思う。

forge の思考ルーチンはそれほど強くなく、ゲームを楽しむために CPU側に有利な設定も行えるようになっている。ライフが最初から400点あるとか（人間側は20点）。

magarenaのシステム

201400425-magarena

Magicや麻雀などはプレイヤーから見えてない要素があり、不完全情報ゲームに分解される。見えてない部分をどう扱うかが難しく、麻雀などでも強いAIを作るのは四苦八苦している状況だ。

Magicでも状況は同じで、とりあえず現時点での手札や場の情報だけで行き当たりばったりにプレイするプログラムが作られていた。目前しか見ないので、ぎりぎりまで犠牲ブロック（champ block)しないし、除去の優先度も変だったりする。

ところが！ magarena は何と αβ法で先読みをする思考ルーチンや、コンピュータ囲碁でも使われている Monte-Carlo Tree Search が実装されている。しかも CPU同士の対戦でMCTSで深く読むと強いという結果まで得られているようだ。凄いね。

思考ルーチンの概略や対戦結果については下記のページに書かれている。詳しく知りたい方は、公開されているソースを読むといいだろう。

magarena では、カードの定義も今風になっている。

effect= にカードの効果を書くのだが、この部分は人間向けの定義(Orcale)とほぼ一緒だ。定型の英文を解析し、自動的にカードの定義を生成している。

name=Giant Growth
url=http://magiccards.info/query?q=%21giant%20growth
image=http://mtgimage.com/card/giant%20growth.jpg
value=4.228
rarity=C
type=Instant
cost={G}
effect=Target creature gets +3/+3 until end of turn.
timing=pump

（強調は私による）



Magic のカードにはとても定型では表現できないような壊れたカードもあり、そのようなカードは Groovy を使って別途記述できる。

こちらは Spirit of the Night の例。
標準的に書ける部分は ability欄に記述。追加コードがあることを requires_groovy_code にて要求している。

name=Spirit of the Night
url=http://magiccards.info/mr/en/44.html
image=http://magiccards.info/scans/en/mr/44.jpg
value=4.437
rarity=R
type=Legendary,Creature
subtype=Demon,Spirit
cost={6}{B}{B}{B}
pt=6/5
ability=flying;trample;haste;protection from black
timing=main
requires_groovy_code

ImplementingCards – magarena – Implementing new cards – Fantasy card strategy game against computer opponent

（強調は私による）


Oracle では　“夜のスピリットは、それが攻撃しているかぎり先制攻撃を持つ” に当たる部分が groovy で書かれている。攻撃時だけ First strike のフラグを立てている。

[
    new MagicStatic(MagicLayer.Ability) {
        @Override
        public long getAbilityFlags(final MagicPermanent source,final MagicPermanent permanent,final long flags) {
            return permanent.isAttacking() ?
                flags | MagicAbility.FirstStrike.getMask() :
                flags;
        }
    }
]

ImplementingCards – magarena – Implementing new cards – Fantasy card strategy game against computer opponent

デッキの自動対戦場 firemind.ch

将棋プログラムには floodgateという対局場があって、コンピュータ同士がずーっと対局を行っている。

Magicにも magarena を使ったデッキ同士の対局場(Project Firemind)が存在する。思考ルーチンには手を加えられないが、自分で考えたデッキを投入し各種デッキと戦わせることができる。

人間とコンピュータではプレイイングが異なるので、人間が使って強いデッキがCPU思考でも強いとは限らない。このような対戦場の存在はコンピュータが使うデッキのチューニングに大いに役立つと思う。

201400425-firemind

magarena と Forge の比較


利口な思考ルーチンやAI同士の対戦場があるのは magarena だけの利点だ。ただし、magarena は その代償として AIでは扱いづらいカードをバッサリ切り捨てている。

下記1項目の制限により、Contagion のような、複数の対象を取るカードが使えないのは辛い。猫カードかわいいのに。

Here is where the real work of the AI comes into play. When the player controlling the event is an AI player and a choice must be made, then it must try to find the best choice. Limiting the number of choices that can be made has a big influence on the speed of the AI. These are some of the decisions made to accomplish this :

  • Avoid cards that have multiple targets like Incremental Blight or Arc Lightning
  • No Planeswalker cards because each creature can choose to either attack the opponent or a Planeswalker controlled by the opponent and combat is already stressful

AIMinimax – magarena – Description of the MiniMax AI in Magarena – Fantasy card strategy game against computer opponent



Forge には「最初は貧弱なデッキだけが与えられ、敵を倒してカードを集めてだんだん強くなる」という簡単なゲームモードが組み込まれている。Microprose版のゲームモードをさらに簡易化したものだが、これはこれで楽しい。ほぼすべてのカードが使えるのも魅力だ。
（でも、なぜか Autumn Willow がないんだよな… 実装が難しいのだろうか）

参考リンク

ソフト名

動作環境

ゲーム種別

カード種別

費用
Microprose版 Magic: the Gathering

Windows95/98

対CPU（拡張により対人）

LEA,LEB, 2ED,3ED,4ED, ARN,ATQ,LEG,DRK

パッケージソフト
マジック・ザ・ギャザリング

ドリームキャスト

対CPU

6ED+α

パッケージソフト
マジック2014

PS3, Xbox360, iPad, Android, Windows等

対CPU、対人

構築済デッキ

DLC課金あり
Forge

Java (Windows,Mac,Linux)

対CPU

ほぼ全部

無料
ManaLink 3.0 – Slightly Magic

Windows

対CPU

ほぼ全部?

無料
magarena

Java+Groovy(Windows,Mac,Linux)

対CPU

6200枚

無料
Firemind

Web base

CPU対CPU

magarena+α？

無料

Dreamcast版について以前書いた記事。

調べてみたら、麻雀でもモンテカルロAIがつくられてますね。世の中進歩してるなあ…

M:tG, ゲーム

Posted by ず＠沖縄