同人版 Magic: the Gathering のAIルーチンが興味深い
Magic: the Gathering という時間と金を食い尽くすゲームがある。
私が知ったのは日本語第４版発売後なので1996年ごろ。REXAに改築される前のベスト電器那覇店が扱い始めたのがきっかけ。
JAVY地下の大会の決勝でカウンターポストに負けたんだよなあ。
カードゲームというジャンルが M:tG 以前と以後に分けられるほど画期的なゲームで、ポケモンカードゲームや遊戯王などの派生ゲームがワラワラ誕生したのも懐かしい記憶だ。
コンピュータ版 Magic: the Gathering
沖縄には碁会所や雀荘は多く存在するのだが、マイナーゲームは対戦相手を探すのが一苦労。将棋ですら道場は少ない。まして舶来のゲーム。人間の相手は探しづらいので、コンピュータに相手をさせたくなるのは自然の成り行きだ。
さらにTCG自体が金食い虫のゲームなので、コンピュータで代行できれば安上がり。私も市販のソフトやiPadアプリも含めて色々と試している。
- Microprose版 Magic: the Gathering
- Windows95/98
- マジック・ザ・ギャザリング
– ドリームキャスト
- マジック2014
– PS3, Xbox360, iPad, Android, Windows等
- Forge – Java (Windows,Mac,Linux)
- ManaLink 3.0 – Slightly Magic – Windows
- magarena – Java+Groovy(Windows,Mac,Linux)
- Firemind – Web base
Microprose版 M:tG を再発売して欲しいのだけど…
Microprose版 Magic: the Gatheringは、Magic初期のPower9と呼ばれる（1枚数万円のプレミアがついている）カードを思う存分使えて楽しめる。
私も最近までVMware+Windows98で遊んでいた。それぐらい面白い。WindowsXPですら過去のものになった今となっては、さすがにWindows98は古すぎる。Virtual Machineを使わずに遊びたいと思う。
(最近のマシンでは速すぎて操作が難しいのだ。VMの速度落とせないかな？）
でも、発売元の Microproseは亡くなったし、M:tG発売元の Wizards of the Coast は最新のカードを売るのに忙しい（そりゃそうだよね）。
私のように再販を望む人が多かったのか、対局可能な２つの同人ソフトが開発されている。
M:tGはコンピュータには難しい
Magicは恐ろしくルールの複雑なゲームだ。現時点のルールはテキストファイルで620KBにも及ぶ。
あまりにも複雑なゲームなので、普通に人とコンピュータが対戦すれば当然のように人間側の圧勝になる。
それではゲームとして面白くないため、初期のゲームプログラムは特殊ルールを付け加えたり・コンピュータ側に積み込みを許すことでバランスを保っていた。まるで、お正月に放映されていた大逆転将棋のように。
ちなみに、ドリームキャスト版のラスボスは極悪なまでに積み込んでくるので、対策デッキでないとまず勝てない。
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のシステム
Magicや麻雀などはプレイヤーから見えてない要素があり、不完全情報ゲームに分解される。見えてない部分をどう扱うかが難しく、麻雀などでも強いAIを作るのは四苦八苦している状況だ。
Magicでも状況は同じで、とりあえず現時点での手札や場の情報だけで行き当たりばったりにプレイするプログラムが作られていた。目前しか見ないので、ぎりぎりまで犠牲ブロック（champ block)しないし、除去の優先度も変だったりする。
ところが！ magarena は何と αβ法で先読みをする思考ルーチンや、コンピュータ囲碁でも使われている Monte-Carlo Tree Search が実装されている。しかも CPU同士の対戦でMCTSで深く読むと強いという結果まで得られているようだ。凄いね。
思考ルーチンの概略や対戦結果については下記のページに書かれている。詳しく知りたい方は、公開されているソースを読むといいだろう。
- magarena – Overview of the AI – Fantasy card strategy game against computer opponent
- AIMinimax – magarena – Description of the MiniMax AI in Magarena – Fantasy card strategy game against computer opponent
- AIComparison – magarena – comparison of different AIs – Fantasy card strategy game against computer opponent
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
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;
}
}
]
デッキの自動対戦場 firemind.ch
将棋プログラムには floodgateという対局場があって、コンピュータ同士がずーっと対局を行っている。
Magicにも magarena を使ったデッキ同士の対局場(Project Firemind)が存在する。思考ルーチンには手を加えられないが、自分で考えたデッキを投入し各種デッキと戦わせることができる。
人間とコンピュータではプレイイングが異なるので、人間が使って強いデッキがCPU思考でも強いとは限らない。このような対戦場の存在はコンピュータが使うデッキのチューニングに大いに役立つと思う。
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
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がつくられてますね。世の中進歩してるなあ…
- mjai-manue/README.md at master · gimite/mjai-manue · GitHub(モンテカルロ+決定木学習)
- 多人数不完全情報ゲームにおける最適行動決定に関する研究(UCT探索)