いま読まれている記事

『マジック・ザ・ギャザリング』は「現在もっとも複雑なゲームのひとつである」という研究論文が公開。アルゴリズムが最善手を計算できない場面も

article-thumbnail-190513b

 ウィザーズ・オブ・ザ・コーストの『マジック・ザ・ギャザリング』(Magic: The Gathering、以下MTG)は、1993年に発売された世界初のトレーディングカードゲームとして知られている。今やカードの種類は約2万枚、共通ルールだけでなくカードが追加されるごとに増える特殊ルールの量は、膨大な数にのぼっている。

 その長い歴史や膨大なカードの種類ゆえかさまざまな形で研究が行われており、カード同士のコンボとデッキ構築といったゲーム戦略をテーマにしたものだけでなく、『MTG』のルールは万能チューリング機械を再現できる「チューリング完全」であるという証明など、一風変わった研究もなされている。

 そんななか、「現実で遊ばれるゲームの中で『MTG』はどれくらい複雑なのだろうか?」という問いに対する興味深い研究結果が論文として発表された。

『マジック・ザ・ギャザリング』は「現在もっとも複雑なゲームのひとつである」という研究論文が公開。アルゴリズムが最善手を計算できない場面も_001
(画像は“Magic: The Gathering” is officially the world’s most complex gameより)

 前述の『MTG』がチューリング完全であることを証明したボードゲームデザイナーであるアレックス・チャーチル氏と研究グループは、コンピュータやチューリングマシンでプレイできるようにゲームを変換し、ゲームの複雑さを定量的に測定した。これまでのゲーム理論の研究は、主に仮想的なゲームで行われることが多かったという。この研究では、実際にプレイされている現実のゲームを対象にしていることが特徴だとチャーチル氏は説明している。

 その研究の結果チャーチル氏らは、『MTG』が現実に存在するゲームの中でもっとも複雑なゲームのひとつである結論づけた。ある特定の条件下では、勝利のための最善手のアルゴリズムを導き出すことができないことが証明されたという。

 論文では、これを現実世界に勝利戦略の決定が計算不可能なゲームが存在することを証明する最初の結果、とまとめている。また、最初に報じたMITテクノロジーレビュー誌は、「全てのゲームは計算可能でなければならない」という仮定に反証した最初の現実世界のゲームだとしている。

『マジック・ザ・ギャザリング』は「現在もっとも複雑なゲームのひとつである」という研究論文が公開。アルゴリズムが最善手を計算できない場面も_002
(画像はMagic: The Gathering is Turing Completeより)

 研究に使用されたデッキは、これまで発売された禁止カード以外のすべてのカードが使用できる「レガシー」ルールで構築可能なものだ。すべての色のクリーチャーと土地カードをコントロールしていた場合ゲームに勝利できる「合同勝利/Coalition Victory」や、任意のクリーチャーを自分のコントロール下に置き、対戦相手がクリーチャーを召喚すると必ずそちらとコントロール権を交換する「錯覚の利得/Illusory Gains」など、特殊な効果を持つカードも多い。

 たとえばチェスや将棋、囲碁といった、お互いの手が盤面に開示され駒の種類が限られているゲームで、コンピュータが人間に勝利したという情報がニュースになる。最近ではお互いの情報が断片的にしかわからない『Starcraft II』で、AIがプロゲーマーに勝利したことがニュースとなった。これらすべてが最善手をなぞって完璧に人間に勝利したというわけではないが、研究によって最善手が見つかりつつあるゲームだといえる。

 しかし駒が14種類ある将棋であれば、局面数は約10^69種類であることが推測されている。さらに膨大な数のカードが存在する『MTG』の最善手を見つけ出す手段が難しいことは想像に難くない。

『マジック・ザ・ギャザリング』は「現在もっとも複雑なゲームのひとつである」という研究論文が公開。アルゴリズムが最善手を計算できない場面も_003
(画像はSteam |  『Magic Duels』より)

 最善手が存在しない場合があるゲームとはいえ、『MTG』には多数のコンピューターゲームがリリースされている。プレイヤーと対戦するAIは、まともに対戦すれば人間には勝てない。そのため、AIが扱いにくいカードが除外されたり、いわゆる積み込みやAIにのみ許された特殊なルールでチートをすることもある。

 非公式ゲームの『Magarena』は、2016年に人類最強の囲碁棋士を破った「AlphaGo Zero」でも採用されたモンテカルロ木探索と、ミニマックス法を応用したAIが実装されているという。チャーチル氏の研究はプレイヤーに直接影響することはおそらく無いが、こういった『MTG』のAIデザインには潜在的な影響があるだろう。

 今回の研究は、ウィザーズ・オブ・ザ・コーストも自覚している『MTG』自体の複雑さと新規参入障壁の問題を補強するひとつの例として見ることができる。経験的にわかっていることでも、実際に理論として発表することには大きな意味がある。「証明されたゲームの中で」というくくりではあるが、『MTG』が世界でもっとも複雑なゲームのひとつであることが証明された。コンピューターでは計算できない「勝ちに不思議あり」は、経験則だけでなくどうやら確かに存在するようだ。

ライター/古嶋誉幸

関連記事:

DeepMindのAIがストラテジーゲーム『StarCraft II』のプロプレイヤーに圧勝、多方面での応用に期待がかかる

面白さの評価関数は作れるか? 麻雀対局中の思考を真面目に再現したらゲームAIになっていた──ゲームアーツ創業者宮路洋一氏が説く試行錯誤の大切さ、そして80年代【聞き手:三宅陽一郎】

ライター
『マジック・ザ・ギャザリング』は「現在もっとも複雑なゲームのひとつである」という研究論文が公開。アルゴリズムが最善手を計算できない場面も_004
一日を変え、一生を変える一本を!学生時代Half-Lifeに人生の屋台骨を折られてから幾星霜、一本のゲームにその後の人生を変えられました。FPSを中心にゲーム三昧の人生を送っています。
Twitter: @pornski_eros

本ページはアフィリエイトプログラムによる収益を得ている場合がございます

Amazon売上ランキング

集計期間:2024年3月29日19時~2024年3月29日20時

新着記事

新着記事

ピックアップ

連載・特集一覧

カテゴリ

その他

若ゲのいたり

カテゴリーピックアップ