MTGを科学しよう

MTG(magic the gathering)のツールを作成したり、科学的に最適なプレイを考えてみたい

チェスや将棋のAIについて調べてみた

数学 ソフトウェア

　MTGの最適プレイに向けたシミュレーションを行うため、既存のゲームAIの手法と研究の進展状況について調べてみた。

　調べてみると、やはり完全情報ゲームのほうが研究は進んでいるようで、完全情報ゲームだる将棋はプロと対等に戦えるレベルまできている一方で、多人数不完全情報ゲームのポーカーはヘッズアップ（１対１で分岐が小さい）ならばプロレベルという程度のようだ。

 

ゲームAIを作る上での難易度はそのゲームの探索空間の大きさ（＝複雑さ）に強く依存する。オセロ＜チェス＜将棋の順に探索空間が大きい。オセロは完全に木の探索が終わっており、完全な解がわかっている。チェスはチャンピオンを倒しており、将棋もプロと渡り合えるレベルまで来ているようである。

チェスのＡＩ

　チェスでは、木探索と評価関数を使用するだけのAIでプロを破るまでになった。木探索とは展開ゲームの枝分かれをたどって行き、どう動くと何ターン先にどういう状態になるかを調べることである。当然いきつく先が一番いい状態になる手をプレイするのだが、この良い状態なのかどうかを判断するのが評価関数である。相手の駒を減らしたら加点、自分の駒を減らしたら減点、という具合に評価するのだが、駒の配置がよくなったということに対して何点与えるのかといったことが難しそうである。

 

将棋のＡＩ

　将棋においても中盤戦ではチェスと同様に木探索と評価関数が用いられ、主要な研究はこのふたつに当てられているようである。

　木探索の研究では、余計な探索を減らして必要な探索を深く行う方法の研究が多く、「激指」というAIではもっともらしいを見積もった後に、もっともらしいものから深く探索していく手法がとられている。

　評価関数の研究では、BonanzaというAIは、評価関数のパラメーターをできるだけプロの棋譜と同じように打つように調整されていて、その調整に多量の棋譜を読み込んで機械学習を行うという手法がとられた。

 

MTGとの対比

　MTGのほうが評価関数はいわゆるアドバンテージを数式化したものである。幸い、MTGにはカードアドバンテージやテンポアドバンテージ、ライフアドバンテージといった用語がすでに存在し、序盤はカード・テンポに重きをおき、ゲームが進むにつれてライフを気にするようになることを知っている。これらのアドバンテージの比重はお互いのデッキタイプや展開によって異なる。これらをどう数式化するかが課題である。

　探索については、将棋と違いランダムの要素がある。将棋では相手もベストの手を打つとして考えることで結果が一意的に決まるがランダムが入ることでそうはいかないだろう。次は不完全性ゲームについて調べ、探索方法についてのアルゴリズムを探さがしてみる。

 

 

MTGゲーム理論 展開ゲーム

MTG 数学

 MTGというゲームについて、ゲーム理論的な言葉をあてはめていく。

　まず、MTGのプレイヤーは2人で、勝ち負けを競うため非協力関係のゼロ和ゲームであり、順番にプレイを行う展開型のゲームである。また、ドローという偶然要素が含まれ、相手の手札は非公開の情報であり、情報不完備のゲームであるといえる。

展開型ゲームとは

　ここでいう展開型のゲームとはプレイヤーの選択によって局面がかわっていくゲームのことである。まず下の図を見てほしい。プレイヤーP0,P1,P2がいて、初めにプレイヤーP0がO1でe1かe2の行動を選択する。仮にe2を選んだとして、次にプレイヤーP1がO3の位置でLかRの行動を選択する。ここでも仮にRを選んだとして、次にP2がO6の位置でLかRを選択する。Rを選んだとするとt5という結果が得られる。このように前の選択が後の選択に影響するようなものが展開型ゲームである。

f:id:Delver:20150720130025j:plain

画像は　鈴木光男 著　共立出版 [ゲーム理論入門] P.91より

 

MTGにおける「プレイヤー」とは

 　さて、ここではプレイヤーが3人としているが、MTGにおいてもプレイヤーは３人と扱われる。その残り一人のプレイヤーは偶然手番 と呼ばれるもので、MOでいうところのシャッフラーさんである。シャッフラーさんのプレイ(e1かe2の選択）はランダムに決められる。mtgにおいては雑にいうとプレイヤー１→シャッフラー→プレイヤー２→シャッフラー→プレイヤー１→。。。の順にプレイする。

 

MTGの複雑さについて

　この枝はターン数を重ねるにつれて指数的に広がっていき、頂点tの数は膨大になる。絵では行動が２通りなのでまだ枝別れが少ないが、クリーチャーが5体いればアタックフェイズにそれぞれのクリーチャーについてアタックするかしないか選択するので2^5=32通り存在し、ブロックフェイズでは３体のアタックに対してブロッカーが５体いれば4^5=1024通り存在する。メインフェイズにはどのスペルをプレイするかの選択があり最大で2^7=128程度で、ドローについても最大で53枚の中からの選択となる。これらは掛け算で増えていき、これらの数字から計算すると1ターンで10^8程度の頂点が存在する。MTGは大体15～30ターン程度のゲームで、30ターンとするとゲーム全体で10^240程度の頂点があることになる。将棋の場合の数が10^220程度らしく同程度であるので、プレイヤーのAI化を行うにあたっては計算量を落とす方法の検討として将棋のAIは参考にしたい。

 

思考方法について

　最終的な頂点tの利得（結果）は勝ち負けであるが、この大きな木をすべて試行するのは不可能である。そのため、数ターン先までの枝分かれを計算して、その時点での利得を調べてプレイを選択する。ここでの利得はMTGで言うアドバンテージにあたり、数ターン先の状況を呼んでどういったアドを優先してプレイするかを選択するという多くのプレイヤーが行っている行動に近いものである。

　将棋のAIなんかも何手先かまで計算して、盤面を評価してプレイを選択しているはずである。この辺のアルゴリズムについて調べてみたほうがよさそうだ。

 

 

MTGのドラフトビュアーを作ってみた

MTG ソフトウェア

MOのピック譜を確認するときに、draft converterのサイトだとブラウザの制約があって見づらいと思っていたのでローカルでピックを確認できるソフトを作りました。SSは以下のとおり。

 

f:id:Delver:20150719234027j:plain

 公開先URL:

http://yahoo.jp/box/yDm5XB

 

カードの画像を含んだ状態で公開すると怒られるので、使用するには個々でwizardsの公式サイトの画像をダウンロードして頂く必要があります。私的利用の範囲で使用するようにしてください。結構面倒ですが、以下の手順に従ってインストールできます。

 

インストール方法：

    1. http://yahoo.jp/box/yDm5XB

      よりzipファイルをダウンロードして解凍します。解凍先を仮に「D:\download\」とします。
    2. KTK(タルキール覇王譚)の画像をダウンロードする場合を例に説明します。D:\download\draft\url\KTKurl.txtに画像ファイルのurlが書かれているのですべてダウンロードします。
    3. Free download manager (http://www.vector.co.jp/soft/winnt/net/se498615.html)をインストールし、起動します。
    4. メニューバーの「ファイル」→「インポート」→「URLリストをインポート」をクリックする。
    5. ダイアログが開くので、D:\download\draft\url\KTKurl.txtを選択して開く。

    6. 下の画像のダイアログが出てくるので赤枠で囲った部分のボタンを押す。

      f:id:Delver:20150720095523j:plain

    7. 保存先のフォルダをD:\download\draft\ドラフトビュアー\KTK\に変更する。

    8. OKを押してダウンロードを開始します。
    9. D:\download\draft\リネームファイル\KTK.csvのファイルをテキストエディタ（メモ帳）開きます。
    10. 中身は現在のファイル名, 変更後のファイル名, ファイルがあるフォルダ位置の順に並んでいます。デフォルトではD:\download\KTK\としているが、これをさきほど画像を保存したフォルダに 変更します。メモ帳の場合はCTRL+Hを押して検索する文字列に「D:\download\KTK\」を置換後の文字列に「D:\download \draft\ドラフトビュアー\KTK\」を入力してすべて置換します。
    11. ファイルを保存します。
    12.  ダウンロードしたファイルはjp_ZluAaiwZMF.pngのような名前になっていますので、これを英語のカード名に変更します。ここでは「お～瑠璃ね～む」というソフトを使用させていただきます。
    13. お～瑠璃ね～む（http://beefway.sakura.ne.jp/download.html）をダウンロードし解凍してallrename.exeを起動します。
    14. メニューバーの「ファイル」→「csvファイルの読み込み」を押します。
    15. ダイアログが開いたら先ほど変更したリネーム用のファイルを選択します。
    16. 正しく読み込めたら変更ファイル名のリストのところにリネームの情報が表示されます。もし表示されない場合は、画像を保存したときのファイル名を変更しているかフォルダ名が正しくないと思われます。
    17. 右下の実行のボタンを押してリネームを行います。
    18. 2～17の操作を必要に応じて他のエクスパンションに対しても行ってください。
    19. 完了したら、これでインストールは終了となります。/ドラフトビュアー/ドラフトビュアー.exeを起動してMOのピック譜を読み込んで動作することを確認してください。

 

このソフトはピック譜内に書かれたカード名を元に、exeファイルから見て「\エクスパンション３文字\英語カード名.png」の画像を表示するというソフトですので、新しいエクスパンションが出た際や、キューブなんかもフォルダと画像を用意すれば動作します。

 

要望等あればコメントに書いて頂けると対応するかもしれません。

 

追記 2015-9-21

BFZのurlリスト追加

 

追記 2015-10-17

BFZのリネームファイル修正

jpgの対応

 

追記　2017-1-8

ブラウザ上で動作するビュアーを作りました

http://mtgtheory.hatenablog.com/entry/2017/01/08/180111

 

ゲーム理論とは

数学

MTGの最適なプレイを求めるにあたって、確率的な考え方をする必要があるので、
数学のゲーム理論という考え方についてつらつらと書いていく。（専門じゃないので違うかも）

もともとはギャンブル（たぶんポーカー）に勝つために考えられた数学理論である。
じゃんけんの話をすると、じゃんけんは「ぐー・ちょき・ぱー」から選択するゲームで、
何を出すのが正解かというとグぐー・ちょき・ぱーを同じ確率で出すのがいい。
これはだいたいの人が無意識にやっていることで、俺はグーしかださないって人はそうそういないだろう。

これをゲーム理論の言葉でいうと、戦略 p(ぐー, ちょき, ぱー) を使用するじゃんけんの最適戦略は
混合戦略 p* = (1/3, 1/3, 1/3)である、ということになる。

この最適戦略はあくまでも相手の情報が全くない場合で、グーを多く出す癖があるという情報がある場合は、パーを増やしてグーを減らした戦略が最適になる。
あるいはグーチョキパーのどれで勝つかによってに得られるものが異なる場合、
例えば「グリコ」の場合であればグリコ=3、パイナツプル=6、チヨコレイト=6の勝ったときの得と、逆に負けたときの損から
最適戦略を計算される。
本当はこれを行列にして解くんだろうけど知識がないので割愛。

MTGもいわゆる運ゲーで、得られた情報から戦略を選択して勝つゲームなので、この考え方が役にたつはずである。（まだ書きながら考えてるんだよね実は）

はじめに

カードゲームmagic the gathering (mtg)のプレイの基本を理論的に調べていくサイトです。

先日、タルキール竜紀伝のPTのニコ生を見ていて、
糸谷竜王が「mtgにはプレイを理論的にまとめられた本やサイトが足りない」とおっしゃっていたのに深く共感しました。
経験則についてはプロの方が書かれることに遠く及ばないので、科学的に正しいプレイとは何か、強いデッキとは何かをシミュレーションを使いながら考えていこうと思っています。