MTGを科学しよう

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

ブラウザ上で動作するドラフトビュアーを作った

MOのドラフトビュアー作りました

前にローカルで動作するドラフトビュアーをつくったんですが、 やっぱりオンライン上で動かないと面倒で使われませんでした。 オンラインのビュアーはDraft Converter - Imagesをよく使わして頂いてたのですが、 MO上のように、過去ピックが見えないとわかりづらいと思うんです。

なので、かわりのものを自分で作ってみました。 ぜひ以下のURLから飛んで一度試して見てください。

http://draftmania.net/

外観

f:id:Delver:20170108175948p:plain

特徴

  • 過去のピックが一覧できる

　　灰色のゾーンが過去のピック

  • カードをクリックすると拡大する

  • ディスプレイが小さい場合に、１行に表示するカードの枚数が自動で少なくなる

使い方

  1. フォルダのマークをクリック
  2. MOのピック譜のデータを選択
  3. submitボタンをクリック
  4. Nextボタンで次のピックへ

今後の更新

まだ作ったばかりで、使い勝手が悪いと思います。

使いにくいところがあればコメント欄に書いていただけると嬉しいです。

今後の更新予定は

  • カードの日本語対応
  • サイトの見た目（センスある人助けて。。。）
  • ピック譜の共有

を考えています。

ピックの共有は、ピック譜を読み込んだときに、 そのピック譜のドラフトが閲覧できるURLを生成して、 そのURLをみなさんのブログやtiwtterに貼ることで、 ピック譜の共有をできればいいなと思っています。

戦乱のゼンディカーのMOリリースから５日　ドラフト点数表を作ってみた　～環境初期のみんなのカード評価～

みんなが納得できるドラフト点数表の作成に向けて

　一人のプロプレイヤーが考えたドラフト点数表よりもみんなの英知を集めた点数表のほうが優れているのではないだろうか？ そのような考えのもと先日模擬的にKTKのドラフト点数表の作成した。 *1

　今回は戦乱のゼンディカー(BFZ)のカードの評価を行った。自分のピック譜と協力いただいた方のピック譜を合わせて22の譜からデータを作成した。ご協力頂いた方ありがとうございます。

全アンコモン＋コモン

アンコモンとコモンの点数は以下の表のようになった。

カード名 点 流れてきた回数 マナコスト レアリティ
Rolling Thunder 26.6666666666667 1 X R R U
Coastal Discovery 53.3333333333333 2 3 U U
Grip of Desolation 53.3333333333333 2 4 B B U
Drana's Emissary 53.3333333333333 2 1 W B U
Ruination Guide 53.3333333333333 2 2 U U
Brood Monitor 53.3333333333333 2 4 G G U
Kor Bladewhirl 106.666666666667 4 1 W U
Bane of Bala Ged 106.666666666667 4 7 U
Touch of the Void 121.2 12 2 R C
Sheer Drop 131.3 13 2 W C
Gideon's Reproach 131.3 13 1 W C
Windrider Patrol 133.333333333333 5 3 U U U
Vile Aggregate 133.333333333333 5 2 R U
Ulamog's Despoiler 133.333333333333 5 6 U
Benthic Infiltrator 151.5 15 2 U C
Stasis Snare 160 6 1 W W U
Ulamog's Nullifier 160 6 2 U B U
Turn Against 160 6 4 R U
Adverse Conditions 160 6 3 U U
Angel of Renewal 160 6 5 W U
Retreat to Emeria 160 6 3 W U
Kozilek's Channeler 161.6 16 5 C
Complete Disregard 181.8 18 2 B C
Carrier Thrall 186.666666666667 7 1 B U
Hedron Archive 186.666666666667 7 4 U
Roil's Retribution 186.666666666667 7 3 W W U
Eldrazi Skyspawner 191.9 19 2 U C
Deathless Behemoth 213.333333333333 8 6 U
Transgress the Mind 213.333333333333 8 1 B U
Mist Intruder 222.2 22 1 U C
Smite the Monstrous 222.2 22 3 W C
Courier Griffin 232.3 23 3 W C
Kor Entanglers 240 9 4 W U
Skitterskin 240 9 3 B U
Tajuru Warcaller 240 9 3 G G U
Kalastria Healer 242.4 24 1 B C
Lifespring Druid 242.4 24 2 G C
Clutch of Currents 252.5 25 U C
Snapping Gnarlid 262.6 26 1 G C
Chasm Guide 266.666666666667 10 3 R U
Pilgrim's Eye 266.666666666667 10 3 U
Murasa Ranger 266.666666666667 10 3 G U
Roil Spout 266.666666666667 10 1 W U U
Retreat to Hagra 266.666666666667 10 2 B U
Encircling Fissure 266.666666666667 10 2 W U
Bloodbond Vampire 266.666666666667 10 2 B B U
Hagra Sharpshooter 266.666666666667 10 2 B U
Stonefury 272.7 27 3 R R C
Dominator Drone 282.8 28 2 B C
Nettle Drone 282.8 28 2 R C
Evolving Wilds 282.8 28 C
Incubator Drone 292.9 29 3 U C
Grove Rumbler 293.333333333333 11 2 R G U
Horribly Awry 293.333333333333 11 1 U U
Molten Nursery 293.333333333333 11 2 R U
Blighted Cataract 293.333333333333 11 U
Dampening Pulse 320 12 3 U U
Resolute Blademaster 320 12 3 R W U
Zulaport Cutthroat 320 12 1 B U
Tide Drifter 320 12 1 U U
Catacomb Sifter 320 12 1 B G U
Akoum Stonewaker 320 12 1 R U
Makindi Sliderunner 333.3 33 1 R C
Rising Miasma 346.666666666667 13 3 B U
Expedition Envoy 346.666666666667 13 W U
Tunneling Geopede 346.666666666667 13 2 R U
Serene Steward 346.666666666667 13 1 W U
Malakir Familiar 346.666666666667 13 2 B U
Blighted Fen 346.666666666667 13 U
Cryptic Cruiser 346.666666666667 13 3 U U
Halimar Tidecaller 346.666666666667 13 2 U U
Blighted Woodland 346.666666666667 13 U
Makindi Patrol 353.5 35 2 W C
Sludge Crawler 363.6 36 B C
Vampiric Rites 373.333333333333 14 B U
Herald of Kozilek 373.333333333333 14 1 U R U
Rot Shambler 373.333333333333 14 1 G U
Murk Strider 373.7 37 3 U C
Blisterpod 383.8 38 G C
Outnumber 383.8 38 R C
Valakut Predator 383.8 38 2 R C
Culling Drone 383.8 38 1 B C
Ondu Champion 383.8 38 2 R R C
Salvage Drone 393.9 39 U C
Unnatural Aggression 393.9 39 2 G C
Plated Crusher 400 15 4 G G G U
Grovetender Druids 400 15 2 G W U
Ondu Rising 400 15 1 W U
Breaker of Armies 400 15 8 U
Spell Shrivel 404 40 2 U C
Ondu Greathorn 404 40 3 W C
Valakut Invoker 414.1 41 2 R C
Eyeless Watcher 414.1 41 3 G C
Call the Scions 414.1 41 2 G C
Ghostly Sentinel 424.2 42 4 W C
Kozilek's Sentinel 424.2 42 1 R C
Kor Castigator 424.2 42 1 W C
Territorial Baloth 424.2 42 4 G C
Skyrider Elf 426.666666666667 16 X G U U
Unified Front 426.666666666667 16 3 W U
Oran-Rief Invoker 434.3 43 1 G C
Silent Skimmer 434.3 43 3 B C
Shadow Glider 444.4 44 2 W C
Tajuru Stalwart 444.4 44 2 G C
Titan's Presence 453.333333333333 17 3 U
Ulamog's Reclaimer 453.333333333333 17 4 U U
Retreat to Coralhelm 453.333333333333 17 2 U U
Vestige of Emrakul 464.6 46 3 R C
Lithomancer's Focus 474.7 47 W C
Kalastria Nightwatch 474.7 47 4 B C
Rush of Ice 474.7 47 U C
Firemantle Mage 480 18 2 R U
Crumble to Dust 480 18 3 R U
Cloud Manta 494.9 49 3 U C
Fertile Thicket 505 50 C
Anticipate 505 50 1 U C
Tightening Coils 505 50 1 U C
Mind Raker 505 50 3 B C
Coralhelm Guide 505 50 1 U C
Nirkana Assassin 505 50 2 B C
Felidar Cub 505 50 1 W C
Pathway Arrows 506.666666666667 19 1 U
Retreat to Kazandu 506.666666666667 19 2 G U
Processor Assault 506.666666666667 19 1 R U
Voracious Null 515.1 51 2 B C
Cliffside Lookout 525.2 52 W C
Eldrazi Devastator 525.2 52 8 C
Spawning Bed 533.333333333333 20 U
Jaddi Offshoot 533.333333333333 20 G U
Blighted Gorge 533.333333333333 20 U
Demon's Grasp 535.3 53 4 B C
Giant Mantis 535.3 53 3 G C
Swell of Growth 545.4 54 1 G C
Bone Splinters 545.4 54 B C
Tandem Tactics 545.4 54 1 W C
Natural Connection 555.5 55 2 G C
Oracle of Dust 565.6 56 4 U C
Tajuru Beastmaster 565.6 56 5 G C
Swarm Surge 565.6 56 2 B C
Fortified Rampart 575.7 57 1 W C
Sure Strike 575.7 57 1 R C
Reclaiming Vines 575.7 57 2 G G C
Belligerent Whiptail 585.8 58 3 R C
Scythe Leopard 586.666666666667 22 G U
Slab Hammer 586.666666666667 22 2 U
Forerunner of Slaughter 586.666666666667 22 B R U
Geyserfield Stalker 595.9 59 4 B C
Hedron Blade 606 60 1 C
Boiling Earth 606 60 1 R C
Void Attendant 613.333333333333 23 2 G U
Retreat to Valakut 613.333333333333 23 2 R U
Stone Haven Medic 636.3 63 1 W C
Wave-Wing Elemental 656.5 65 5 U C
Scour from Existence 656.5 65 7 C
Ruin Processor 656.5 65 7 C
Goblin War Paint 656.5 65 1 R C
Shatterskull Recruit 666.6 66 3 R R C
Looming Spires 666.6 66 C
Mire's Malice 666.6 66 3 B C
Reckless Cohort 666.6 66 1 R C
Sylvan Scrying 666.666666666667 25 1 G U
Earthen Arms 676.7 67 1 G C
Inspired Charge 676.7 67 2 W W C
Dutiful Return 686.8 68 3 B C
Angelic Gift 686.8 68 1 W C
Plummet 686.8 68 1 G C
Seek the Wilds 696.9 69 1 G C
Altar's Reap 707 70 1 B C
Grave Birthing 727.2 72 2 B C
Broodhunter Wurm 737.3 73 3 G C
Brilliant Spectrum 757.5 75 3 U C
Roilmage's Trick 767.6 76 3 U C
Sandstone Bridge 777.7 77 C
Mortuary Mire 777.7 77 C
Lavastep Raider 787.8 78 R C
Dispel 808 80 U C
Volcanic Upheaval 838.3 83 3 R C
Skyline Cascade 868.6 86 C
Blighted Steppe 880 33 U
Kitesail Scout 919.1 91 W C
Infuse with the Elements 986.666666666667 37 3 G U

ピックアップ

まずは一番ピックされている上位６枚を見てみる。誤差の範囲だが《とどろく雷鳴/Rolling Thunder(BFZ)》は唯一１度しか流れてこなかったカードで、 最高点数がついている。だれが見ても強いとわかる納得の１枚である。

そのほかのカードで見ると、《ドラーナの使者/Drana's Emissary(BFZ)》は多色であり、２パック目３パック目では２色ともあっていなければほぼ流すカードでありながら この点数がつくことからカードパワーの高さが伺える。 片方の色があっていたらタッチしてでも使う人も多いのではないかと考えれる。

６マナの除去がこの位置に入るのは意外に感じる。この環境において覚醒土地・能力持ちの土地破壊に意味を見出しているか、環境の速度的に遅い除去でも強いと考えれているのだろうか。

f:id:Delver:20151017155650p:plain f:id:Delver:20151017155833p:plain f:id:Delver:20151017155845p:plain f:id:Delver:20151017155853p:plain f:id:Delver:20151017155914p:plain f:id:Delver:20151017155929p:plain

ピックアップ　コモン

コモンだけに目を向けると以下のカードが上位となっている。１番はいろんなデッキで使いやすいリムーブ付きの火力である《虚空の接触/Touch of the Void(BFZ)》であった。

７枚の内４枚は除去であった。白の除去は上位に何枚かある一方でクリーチャーは少なく、コントロールが組みやすくビートはアンコ以上がないと難しいことがわかる。

f:id:Delver:20151017161326p:plain f:id:Delver:20151017161409p:plain f:id:Delver:20151017161345p:plain f:id:Delver:20151017161549p:plain f:id:Delver:20151017161637p:plain f:id:Delver:20151017161646p:plain f:id:Delver:20151017161726p:plain

終わりに

プレイヤーとしてのレベルの問題であまりあれこれ各カードについて言及することはできないが、 私にとって意外に高い・低いと感じたカードはたくさんあったし、皆さんもそう感じられるカードがあったのではないかと思う。 このデータは２２ピック分しかないので、確度が低いがより多くのデータを集められると細かい点数がわかる。 また、このカードが回っているときはこれも回りやすいといったような相関関係も見れないだろうかと考えている。 定期的に点数化することでメタの変遷なんかも見れたりもするだろう。

ユーザー名の部分等は消して頂いて問題ないので、もし興味がございましたらぜひメールにてピック譜を送って頂けるとうれしいです。 ご協力いただいた方、本当にありがとうございました。

mail: delver0234@yahoo.co.jp

*1:みんなが納得できるドラフト点数表は作れるのだろうか ～ゼンディカーに向けて、いまさらKTK×3環境の点数表を作ってみた～ - MTGを科学しよう

みんなが納得できるドラフト点数表は作れるのだろうか　～ゼンディカーに向けて、いまさらKTK×3環境の点数表を作ってみた～

MTG

ドラフト点数表は信用していいのか？

　ドラフトのピックを行う上で、ドラフト点数表を参考にする方は多い。LSVは新セット発売のたびに個人的なカード評価を点数化して記事にしているし、wikiにも誰が書いているのかはわからないがカードの評価が書かれている。

http://mtgwiki.com/wiki/%E3%83%89%E3%83%A9%E3%83%95%E3%83%88%E7%82%B9%E6%95%B0%E8%A1%A8

　一方で、自分の過去のピックによって優先度は変わるのだからカードに点数つけて順番に取っていっても強いわけないから意味がないといった意見や、個人の感覚に依存した点数表は信頼できないといったことがよく言われる。確かにクリーチャーが取れてないからクリーチャーの点数を上げようなどということは多くのプレイヤーがやっていることであるし、デッキの完成をイメージしてピックしたほうがいい。アーキタイプドラフトの基本については行弘さんが記事を執筆されている。

http://www.hareruyamtg.com/article/category/detail/202

とはいってもみんなドラフト点数表は使う

　アーキタイプドラフトといっても、ファーストピックは一番点数の高いカードを取るケースが多い。また、～のカードが流れてきているからこの色・アーキタイプが空いているのだろうといった予想においても点数表を利用することになる。私のような初心者の助けにもなる点数表はなんだかんだいっても有用なものであると思う。2chなんかでも環境初期は○○より××のほうが強いなんていうレスはたくさんあり、なんだかんだでみんな点数表のことが大好きである。ただ、LSVのような強いプレイヤーであってもアドが取れるカードに高い点数をつけるやすいといったような好みが出るもので、ほかのプレイヤーに聞くと意見が分かれるものである。このような一人のアド厨の感覚に依存した点数表を信頼していいものだろうか？

もっといいドラフト点数表を作りたい　⇒ 集団知の利用

　私が感覚でカードに点数をつけたとして、当然LSVより有用なものを作ることはできない。私一人では点数をつけれないのであれば皆の力を借りればいいのである。そこで以下のブログの記事を見てほしい。

http://gigazine.net/news/20140716-forget-wisdom-of-crowds/

　「集団から得た意見は専門家1人で出した答えよりも正解に近づく」という考え方があるらしい。つまり一般のMTGプレイヤーの意見を統合すれば専門家(=LSV)よりも正解に近づくのだ。Wisdom Guidさんでこれと同じ考え方の点数表を作成されている。web上で2つカードを表示させてどっちとるかを閲覧者に選ばせてその結果を統計的にまとめられている。

http://whisper.wisdom-guild.net/apps/draftscore/

　おもしろい試みだと思うが、選択の本気度を考えるとMOのピック譜を利用すべきである。

ピック譜から点数表の作成

　点数化の方法として流れてきたカードを元に作成する。基本的な考え方として流れてきたカードは取られたカードよりも点数が低いので、何度も流れてくる回数を数えて少ないほうから並べればカードの優先順位となる。ただし、レアリティが低いと流れてくる回数は当然少なくなるのでパックに封入される確率を割ることで補正をかける。タルキール覇王譚の場合、コモンは101枚収録されており、パックには10枚のコモンが入っているので101/10をかけ、アンコモンは80枚収録でパックに3枚なので80/3をかける。 　私が最近の環境はあまりプレイできていないので、KTK×3の環境で私がプレイした30ゲーム分のデータを使って点数化してみた。レアはサンプルが少ないのでアンコモンとコモンだけを表にして下に示す。 　一番点数が高いのは、鷹匠、切断、戦僧侶となった。その下にも休息地の見張り、道の求道者と続いており、単純に点数で取ると白から入ることが多くなることがわかる。また白の参入者が多くなるため、武器を手になど思ったより高い点数で取られているカードもある。多色も上位は白がらみが多い。逆に青意カードはジェスカイの長老が最高点で、レアがないと入りにくい色であるといえる。こうして並べてみると、停止の場より点数が高いカードが5枚もあるから、停止の場が4手目くらいに流れてきたからといって白が空いているとは限らない一方で、荒野の後継者が流れてきたら緑は空いているといった考え方ができる。 　

戦乱のゼンディカーに適用（したい）

　実験的にKTK×3の環境で点数表を作ってみたが、同じ点数表を次の戦乱のゼンディカーの環境初期に作成すれば環境理解に役立つはずである。この点数表は30ゲーム分だが、アンコモンの順位をちゃんと決めるにはサンプル数が足りていない。もし興味を持って頂ける方がいれば、次環境でのMOでのピック譜をぜひメールで譲って頂けないでしょうか？まとめたものをアップしますので、よろしくお願いします。あと表が読みにくいのでそれの改善も考えていきます。

delver0234@yahoo.co.jp

点 流れてきた回数 カード名
53.3333333333 2 Abzan Falconer
53.3333333333 2 Murderous Cut
53.3333333333 2 Abzan Battle Priest
80 3 Watcher of the Roost
80 3 Seeker of the Way
80 3 Bellowing Saddlebrute
106.6666666667 4 Sultai Flayer
106.6666666667 4 Arc Lightning
133.3333333333 5 Take Up Arms
133.3333333333 5 Nomad Outpost
133.3333333333 5 Heir of the Wilds
133.3333333333 5 Abzan Charm
133.3333333333 5 Mardu Heart-Piercer
160 6 Mardu Charm
160 6 Suspension Field
160 6 Ruthless Ripper
186.6666666667 7 Mer-Ek Nightblade
186.6666666667 7 Icefeather Aven
186.6666666667 7 Armament Corps
186.6666666667 7 Highspire Mantis
186.6666666667 7 Mystic Monastery
186.6666666667 7 Dead Drop
186.6666666667 7 Pine Walker
202 20 Ainok Bond-Kin
213.3333333333 8 Tuskguard Captain
213.3333333333 8 Bear's Companion
213.3333333333 8 Death Frenzy
213.3333333333 8 Opulent Palace
232.3 23 Debilitating Injury
240 9 War-Name Aspirant
240 9 Raiders' Spoils
240 9 Incremental Growth
240 9 Timely Hordemate
252.5 25 Alabaster Kirin
252.5 25 Mardu Hordechief
262.6 26 Sultai Scavenger
266.6666666667 10 Kin-Tree Invocation
266.6666666667 10 Chief of the Edge
266.6666666667 10 Chief of the Scale
266.6666666667 10 Jeskai Elder
266.6666666667 10 Jeskai Charm
272.7 27 Feat of Resistance
272.7 27 Arrow Storm
292.9 29 Force Away
293.3333333333 11 Frontier Bivouac
293.3333333333 11 Ride Down
293.3333333333 11 Sandsteppe Citadel
303 30 Jeskai Windscout
320 12 Hordeling Outburst
320 12 Burn Away
320 12 Witness of the Ages
323.2 32 Abzan Guide
323.2 32 Jungle Hollow
333.3 33 Kill Shot
333.3 33 Mystic of the Hidden Way
343.4 34 Savage Punch
346.6666666667 13 Master the Way
346.6666666667 13 Mardu Roughrider
346.6666666667 13 Scion of Glaciers
363.6 36 Mardu Skullhunter
373.3333333333 14 Sultai Charm
373.3333333333 14 Warden of the Eye
373.3333333333 14 Secret Plans
373.3333333333 14 Temur Charger
373.7 37 Tranquil Cove
373.7 37 Disowned Ancestor
373.7 37 Alpine Grizzly
393.9 39 Thornwood Falls
393.9 39 Woolly Loxodon
393.9 39 Wind-Scarred Crag
393.9 39 Longshot Squad
400 15 Riverwheel Aerialists
400 15 Sultai Soothsayer
404 40 Scoured Barrens
404 40 Bring Low
414.1 41 Bloodfell Caves
426.6666666667 16 Winterflame
434.3 43 Abomination of Gudul
453.3333333333 17 Waterwhirl
453.3333333333 17 Mistfire Weaver
453.3333333333 17 Kheru Bloodsucker
464.6 46 Jeskai Student
464.6 46 Mardu Hateblade
474.7 47 Ponyback Brigade
474.7 47 Swiftwater Cliffs
480 18 Monastery Swiftspear
480 18 Swarm of Bloodflies
484.8 48 Archers' Parapet
484.8 48 Hooting Mandrills
505 50 Summit Prowler
505 50 Throttle
515.1 51 Dragonscale Boon
515.1 51 Smite the Monstrous
525.2 52 Blossoming Sands
525.2 52 Crippling Chill
533.3333333333 20 Temur Charm
533.3333333333 20 Dragon's Eye Savants
533.3333333333 20 Become Immense
533.3333333333 20 Horde Ambusher
535.3 53 Mardu Warshrieker
535.3 53 Dismal Backwater
545.4 54 Treasure Cruise
545.4 54 Snowhorn Rider
545.4 54 Leaping Master
565.6 56 Bitter Revelation
565.6 56 Efreet Weaponmaster
585.8 58 Unyielding Krumar
585.8 58 Sage-Eye Harrier
606 60 Bloodfire Expert
606 60 Scaldkin
616.1 61 Rush of Battle
616.1 61 Rugged Highlands
636.3 63 Tormenting Voice
636.3 63 Sagu Archer
640 24 Roar of Challenge
646.4 64 Monastery Flock
646.4 64 Valley Dasher
646.4 64 Trumpet Blast
646.4 64 Krumar Bond-Kin
646.4 64 Awaken the Bear
666.6 66 Glacial Stalker
666.6 66 Highland Game
666.6666666667 25 Blinding Spray
666.6666666667 25 Goblinslide
676.7 67 Smoke Teller
686.8 68 Defiant Strike
693.3333333333 26 Windstorm
693.3333333333 26 Venerable Lammasu
693.3333333333 26 Dazzling Ramparts
693.3333333333 26 Despise
707 70 Whirlwind Adept
707 70 Weave Fate
717.1 71 Singing Bell Strike
717.1 71 Sidisi's Pet
717.1 71 Kin-Tree Warden
746.6666666667 28 Stubborn Denial
747.4 74 Rakshasa's Secret
747.4 74 Salt Road Patrol
747.4 74 Canyon Lurkers
757.5 75 Rite of the Serpent
767.6 76 Wetland Sambar
777.7 77 Barrage of Boulders
797.9 79 Embodiment of Spring
797.9 79 Cancel
800 30 Quiet Contemplation
800 30 Set Adrift
800 30 Gurmag Swiftwing
808 80 Tusked Colossodon
818.1 81 Ainok Tracker
828.2 82 Disdainful Stroke
828.2 82 War Behemoth
828.2 82 Shambling Attendants
838.3 83 Act of Treason
838.3 83 Sultai Banner
848.4 84 Scout the Borders
868.6 86 Kheru Dreadmaw
868.6 86 Molting Snakeskin
880 33 Dragon Grip
880 33 Cranial Archive
888.8 88 Feed the Clan
888.8 88 Temur Banner
906.6666666667 34 Tomb of the Spirit Dragon
909 90 Abzan Banner
909 90 Firehoof Cavalry
919.1 91 Lens of Clarity
919.1 91 Siegecraft
959.5 95 Dutiful Return
960 36 Briber's Purse
969.6 96 Naturalize
969.6 96 Erase
969.6 96 Rotting Mastodon
969.6 96 Bloodfire Mentor
999.9 99 Jeskai Banner
999.9 99 Mardu Banner
1040 39 Mardu Blazebringer
1050.4 104 Shatter
1066.6666666667 40 Brave the Sands
1070.6 106 Taigam's Scheming
1093.3333333333 41 Seek the Horizon
1100.9 109 Swift Kick
1146.6666666667 43 Heart-Piercer Bow

論文の紹介 ~MTGのカード選択へのモンテカルロ探索の適応~

MTG ソフトウェア 数学

コメントで論文を紹介していただいたので早速読んでみた。

"Monte Carlo search applied to card selection in Magic: The Gathering"（和訳：MTGのカード選択へのモンテカルロ探索の適応） url: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5286501

　モンテカルロ法はmtgのAIに応用する場合においても有用であると主張する内容だった。私としても有用であろうというふうには思うんだけど、この内容がそれを裏付けるものになっているかは疑問に感じた。

論文の概要

　この論文では「メインフェイズのクリーチャーのプレイをモンテカルロ法で選択すると、ランダムでの選択や貪欲法での選択より強かった。」と主張している。計算条件として、

  • クリーチャーと土地だけの単色デッキ
  • デッキ内容は公開情報
  • マリガンについての記述なし（たぶんなし）
  • アタックとブロックの戦術は著者が考えたルールに従う場合とランダムの場合の2通り
  • 第２メインのカードプレイの戦術はルールに従う場合、ランダムの場合、モンテカルロ法に従う場合の３通り

　プレイヤーの戦略はアタック戦略がランダムかルールに従うか、ブロック戦略がランダムかルールに従うか、カードプレイ戦略がランダムかルールに従うかモンテカルロかの組み合わせで作られ、計12通りの戦略を相互に戦わせて勝率を調べる。メインフェイズでの戦術のルールは以下のとおり。

  1. ランドはあったら出す
  2. クリーチャーは一番重たいものから貪欲法で出す

アタックとブロックの戦術のルールは紙面の都合で詳しくは書かないとしてある。（超重要事項なんですが、、、）一応アタックは無駄死にしないように、クリーチャーの数とPTの合計が損をしないように選択し、ブロックは返しのフルパンでのダメージが大きくなるように、受けるダメージを抑えて相手のクリーチャーを殺せるようにブロックすると書かれている。

結果と自分の考え

　結果として、各プレイヤー間の200戦やったときの戦績表を載せる。RA_RB_RMといった表現は、RA=ランダムアタック、SA=ルールアタック、RB=ランダムブロック、SB=ルールブロック、RM=ランダムメインプレイ、SM=ルールメインプレイ、MC=モンテカルロメインプレイを表す。 f:id:Delver:20150817142135j:plain

　著者はモンテカルロの優位性について述べているが、そんなことよりブロックのルールがいくらなんでも弱すぎる。rarbrmとrasbrmのプレイヤーの勝率を比べると、どのプレイヤーを相手にした場合でもルールでブロックするプレイヤーが大きく劣っている。さすがにランダムより弱いnoobブロックでは検証の意味がないのではと思う。 さらに最後にモンテカルロの探索回数と勝率の関係を示すグラフが2つ載せられている。これによるとnoobブロック戦術をお互いに採用したときはルールに従うカードプレイに対して、モンテカルロ法は80%の勝率があるとしているが、この異常に高い勝率はモンテカルロ法にのみnoobブロックが行われることを予想できるために生じているに過ぎない。そのためプレイ戦術自体の評価としては不適切である。 　一方でランダムブロックを採用したときは、ほぼ50:50であり、2000回の探索を行った際にはモンテカルロ法がルールに従うプレイに対して負け越している。このデータからモンテカルロ法が優れているとするのは無理がある。むしろカードプレイはクリーチャー以外のスペルがない条件では貪欲法で決めるので十分であるとすら言える。

　著者は私と同じような思考を辿って、論文が必要で無茶したのかなと思う。もともとはアタックブロックもモンテカルロでやりたかったのではないだろうか。　 ブロックを適切に行うと、この条件では多くのゲームはライブラリアウトまで決着しない上に、ロングゲームになるので探索空間が広がりモンテカルロは弱くなる。そのためブロックルールを弱くせざる得なかったんだろう。私としては10体クリーチャーが並んだら引き分けにする等の処置をとるしかないと考えている。 　結果を見る限り、クリーチャーしか入ってないデッキであれば貪欲法で十分そうである。アタックとブロックについて考察してる論文があるといいなと思うので、自分でも論文を探してみることにする。

MTGの簡単なデッキでのゲームの全探索を行うコードを書いてみた　-　プレイヤー２人は全知全能の完全情報ゲームとしても常識的な時間で探索が終わらなかった　-

C# ソフトウェア MTG

　C#でMTGのゲームプレイの木探索を行うコードを書いてみたが意外と難しく、完成とは程遠いが意見等を頂けるとありがたいので途中経過を公開しようと思う。
　複雑なスペルや特殊なデッキを考えるとキリがなく、できるだけ単純なゲームから考えていきたいし、ソフトの雛形作りの意味もあるので簡単にしたいので、まずはその基本であるお互いバニラクリーチャーと土地だけのデッキの場合のシミュレーションを行うことにする。さらに面倒を省くために、プレイヤーはお互いのデッキの内容を知っていて除去とかバットリとかは飛んでこないことを知っているとする。するとプレイヤーはマナ効率だけを考えて漫然とクリーチャーをプレイすることになる。
　まずはお互いのプレイヤーがハンド・お互いの未来のドローを知っている状態（完全情報ゲーム）としてMin-Max法で全探索を行うコードを書いてみた。デッキはクリーチャーと土地のみでプレイヤーの選択肢はアタックとブロックのみで、カードのプレイは手なりに行うものとした。デッキ枚数は40枚とした。デッキのバランスをいじることで、適切なマナカーブや土地配分がわかるかと考えていたが、計算にかなり時間がかかるようで、３時間ほど動かしてみても１ゲームが終わらなかった。計算時間の見積もりもできてないし、無駄な探索が多いのも明らかである。
　次は無駄な探索を削ること、計算の進捗状況を知ることをやっていこうと思う。プログラムに詳しい人からこうしたらコードが読みやすくなるよとか、早くなるよとか教えて頂けるとありがたいです。

動作の概要

f:id:Delver:20150802164814p:plain

　**メイン関数

using System;
using GameSimulator.探索;

namespace GameSimulator {
    static class Program {
        [STAThread]
        static void Main() {         
            Player player1 = new Player(6); //先手ハンド６で初期化
            Player player2 = new Player(7);//後手ハンド7で初期化

            SecondMainPhaseNode node = new SecondMainPhaseNode();
            node.MyPlayer = player1;
            node.OppPlayer = player2;
            node.IsMaxPlayer = true;    //先手をmaxプレイヤーと指定
            var result = node.Eval();   //探索開始
           Console.WriteLine(result.WinningRate);
        
           var x =  Console.ReadLine();
        }
    }
}

評価

将来的には状況からの評価を行いたいが、今回は全探索を行うので、勝つ負けるの２値で扱っていて、WinningRagteにはMin()の値かMax()の値か0(引き分け）が入る

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GameSimulator {
    class Evaluation {
        #region プロパティ

        public int WinningRate { get; set; }
        #endregion

        #region コンストラクタ
        public Evaluation() {

        }
        public Evaluation(Evaluation ev) {

        }
        #endregion

        #region Static
        public static Evaluation Min() {
            var val = new Evaluation();
            val.WinningRate = int.MinValue;
            return val;
        }
        public static Evaluation Max() {
            var val = new Evaluation();
            val.WinningRate = int.MaxValue;
            return val;
        }
        #endregion
    }
}

カードをクラス化したもの

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections.ObjectModel;
using System.Collections.Specialized;

namespace GameSimulator {
    public enum CardType { None, Creature, Land };
    public class Creature : Card {
        public Creature()
            : base(CardType.Creature) {
        }
        public Creature(int P, int T)
            : base(CardType.Creature) {
            Power = P;
            Toughness = T;
        }
        public Creature(int P, int T, int cost)
            : base(CardType.Creature, cost) {
            Power = P;
            Toughness = T;
        }

        private int _Power;
        private int _Toughness;


        public int Power {
            get { return _Power; }
            set { _Power = value; }
        }

        public int Toughness {
            get { return _Toughness; }
            set { _Toughness = value; }
        }
        public bool Taped {
            get;
            set;
        }

        public override string ToString() {
            return Power + "/" + Toughness;
        }
    }

    public class Land : Card {

        public Land()
            : base(CardType.Land) {
        }
    }

    public class Card {
        #region フィールド
        private CardType _Type;
        private int _Cost;
        #endregion

        #region プロパティ
        public int Cost {
            get { return _Cost; }
            private set { _Cost = value; }
        }
        public CardType Type {
            get { return _Type; }
            private set { _Type = value; }
        }
        #endregion
        #region コンストラクタ
        public Card() {
            Type = CardType.None;
            Cost = 0;
        }
        public Card(CardType type) {
            Type = type;
        }
        public Card(CardType type, int cost) {
            Type = type;
            Cost = cost;
        }
        #endregion

        public override string ToString() {
            return "Land";
        }

    }
}

　**場・ハンド・ライフの情報保持
場のクリーチャーやハンドを管理する。カードのプレイはPlay(card)を通して行う。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections.ObjectModel;

namespace GameSimulator {
    public class Player {
        #region フィールド

        private Dictionary<Creature, bool> _CreatureIsTaped = new Dictionary<Creature, bool>();
        private List<Land> _Lands = new List<Land>();
        private List<Card> _Deck = new List<Card>();
        private List<Card> _Hand = new List<Card>();
        private int _Life = 20;
        private Player _Opponent;
        #endregion
        #region プロパティ
        public int Life {
            get { return _Life; }
            set { _Life = value; }
        }

        public List<Card> Hand {
            get { return _Hand; }
            set { _Hand = value; }
        }

        public List<Card> Deck {
            get { return _Deck; }
            set { _Deck = value; }
        }

        public List<Land> Lands {
            get { return _Lands; }
            set { _Lands = value; }
        }

        public Dictionary<Creature, bool> CreatureIsTaped {
            get { return _CreatureIsTaped; }
            set { _CreatureIsTaped = value; }
        }
        public ReadOnlyCollection<Creature> GetCreatures() {
            return new ReadOnlyCollection<Creature>(_CreatureIsTaped.Select(x => x.Key).ToList());
        }
        public IEnumerable<Creature> GetCreaturesIE() {
            return CreatureIsTaped.Select(x => x.Key);
        }
        public Player Opponent {
            get { return _Opponent; }
            set { _Opponent = value; }
        }

        #endregion

        #region コンストラクタ
        public Player() {
            Init();
        }
        public Player(List<Creature> creatures, List<Card> deck, List<Card> hand, List<Land> land) {
            Init();
            Deck = deck.ToList();
            Hand = hand.ToList();
            Lands = land.ToList();
        }
        public void Init() {
            Init(7);
        }
        public void Init(int handNum) {
            for (int i = 0; i < 17; i++) {
                Deck.Add(new Land());
            }
            for (int i = 0; i < 5; i++) {
                Deck.Add(new Creature(2, 2, 2));
            }
            for (int i = 0; i < 6; i++) {
                Deck.Add(new Creature(3, 3, 3));
            }
            for (int i = 0; i < 5; i++) {
                Deck.Add(new Creature(4, 4, 4));
            }
            for (int i = 0; i < 5; i++) {
                Deck.Add(new Creature(5, 5, 5));
            }
            for (int i = 0; i < 2; i++) {
                Deck.Add(new Creature(6, 6, 6));
            }

            Deck = Deck.OrderBy(x => Guid.NewGuid()).ToList();  //シャッフル
            Hand = new List<Card>();
            for (int i = 0; i < handNum; i++) {
                DrawACard();
            }
        }
        public Player(Player pl) {
            this.CreatureIsTaped = new Dictionary<Creature, bool>(pl.CreatureIsTaped);
            this.Lands = new List<Land>(pl.Lands);
            this.Deck = new List<Card>(pl.Deck);
            this.Hand = new List<Card>(pl.Hand);

        }
        public Player(int handNum) {
            Init(handNum);
        }
        #endregion

       

        //カードを引く
        public void DrawACard() {
            if (Deck.Count != 0) {

                Hand.Add(Deck[0]);
                Deck.RemoveAt(0);
            }
            else {
                throw new Exception();
            }
        }

        //カードをハンドから場に出す
        void Play(Card card) {
            if (card.Type == CardType.Creature) {
                PlayCreature((Creature)card);
            }
            else if (card.Type == CardType.Land) {
                PlayLand((Land)card);
            }

        }
        void PlayCreature(Creature card) {
            Hand.Remove(card);
            CreatureIsTaped.Add(card, false);
        }
        void PlayLand(Land land) {
            Hand.Remove(land);
            this.Lands.Add(land);
        }
        //出せる場合ランドをプレイする
        void PlayLandAuto() {
            var land = Hand.FirstOrDefault(x => x.Type == CardType.Land);
            if (land != null) {
                this.Play(land);
            }
        }
        //スペルプレイのアルゴリズム
        void PlaySpellAuto() {
            //プレイ可能なマナ数で初期化
            int mana = Lands.Count;
            //プレイ可能なカードで最大コストのカードからプレイ
            var query = from x in Hand where (x.Cost <= mana) && (x.Type != CardType.Land) orderby -x.Cost select x;
            foreach (var x in query) {
                if (x.Cost <= mana) {
                    Play(x);
                    mana -= x.Cost;
                }
            }
        }
        public void SecondMainPlay() {
            UntapAll();
            PlayLandAuto();
            PlaySpellAuto();
        }
        public void UntapAll() {
            var list = CreatureIsTaped.Select(x => x.Key).ToList();
            foreach (var x in list) {
                CreatureIsTaped[x] = false;
            }
        }
        public void TapCreatures(List<Creature> cre) {
            foreach (var x in cre) {
                CreatureIsTaped[x] = true;
            }
        }
        #region プライベート
        int Pow(int x, int y) {
            int val = 1;
            for (int i = 0; i < y; i++) {
                val *= x;
            }
            return val;
        }
        #endregion

    }
}

探索

　Nodeクラスがが枝分かれして探索する。NodeクラスはメンバとしてListクラスのNextListを保持し、Eval()関数でこれらのノードから最大あるいは最小の評価結果を返す。最大を返すか最小の結果を返すかはプレイヤーがMaxプレイヤーかMinプレイヤーかによって決め、IsMaxPlayerの値によってきまる。
NodeはAttakerNode, BlockerNode, MainPhaseNodeに継承され、AttakerNodeのNextListにはBlockerNodeが入り、BlockerNodeのNextListにはMainPhaseNodeが入り、MainPhaseNodeのNextListにはAttakerNodeが入り、これら３つを順にめぐる。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GameSimulator.探索 {

    class Node {
        #region フィールド

        Evaluation _Evaluation = null;
        private Player _MyPlayer;
        private Player _OppPlayer;
        private List<Node> _NextList = null;
        private Node _Previous = null;
        #endregion
        #region プロパティ

        public Evaluation CurrentEvaluation {
            get { return _Evaluation; }
            set { _Evaluation = value; }
        }
        public Player MaxPlayer {
            get {
                if (IsMaxPlayer) {
                    return _MyPlayer;
                }
                else {
                    return _OppPlayer;
                }
            }
        }
        public Player MinPlayer {
            get {
                if (IsMaxPlayer) {
                    return _OppPlayer;
                }
                else {
                    return _MyPlayer;
                }
            }
        }
        public Player MyPlayer {
            get { return _MyPlayer; }
            set { _MyPlayer = value; }
        }
        public Player OppPlayer {
            get { return _OppPlayer; }
            set { _OppPlayer = value; }
        }
        public bool IsMaxPlayer { get; set; }
        public List<Node> NextList {
            get { return _NextList; }
            set { _NextList = value; }
        }
        public Node SelectedNode { get; set; }


        public Node Privious {
            get { return _Previous; }
            set { _Previous = value; }
        }
        
        #endregion

        #region コンストラクタ
        public Node() { }
        public Node(Node node) {
            this.CurrentEvaluation = new Evaluation(node.CurrentEvaluation);
            this.MyPlayer = new Player(node.MyPlayer);
            this.OppPlayer = new Player(node.OppPlayer);
            this.IsMaxPlayer = node.IsMaxPlayer;
        }
        #endregion

        #region 公開関数
        public virtual Evaluation Eval() {
            if (NextList == null) {
                CreateNextNodeList();
            }
            if (CurrentEvaluation == null) {
                if (NextList.Count == 0) {
                    return CurrentEvaluation;
                }
                CurrentEvaluation = SelectNode().Eval();
            }
            return CurrentEvaluation;
        }

        public virtual Node SelectNode() {
            if (NextList.Count == 0) {
                return null;
            }
            Node node = null;
            if (IsMaxPlayer) {
                int evl = int.MinValue;
                foreach (var x in NextList) {
                    if (evl <= x.Eval().WinningRate) {
                        evl = x.Eval().WinningRate;
                        node = x;
                    }
                }
            }
            else {
                int evl = int.MaxValue;
                foreach (var x in NextList) {
                    if (evl >= x.Eval().WinningRate) {
                        evl = x.Eval().WinningRate;
                        node = x;
                    }
                }
            }
            return node;
        }
        public virtual void CreateNextNodeList() {

        }
        #endregion
    }
    class SecondMainPhaseNode : Node {
        #region コンストラクタ

        public SecondMainPhaseNode() {

        }
        public SecondMainPhaseNode(Node node)
            : base(node) {

        }
        #endregion
        public override void CreateNextNodeList() {
            this.NextList = new List<Node>();
            Player my = new Player(MyPlayer);
            Player opp = new Player(OppPlayer);
            my.DrawACard();
            my.SecondMainPlay();
            if(8 <my.CreatureIsTaped.Count
                && 8 < opp.CreatureIsTaped.Count) {
                    CurrentEvaluation = new Evaluation();
                    CurrentEvaluation.WinningRate = 0;
                    return; //クリーチャーの数がどちらも８超えたら引き分け
            }
            else if (my.Deck.Count < 10) {
                CurrentEvaluation = new Evaluation();
                CurrentEvaluation.WinningRate = 0;  // デッキ枚数が10きったら引き分け
            }
            AttakerNode node = new AttakerNode();
            node.MyPlayer = opp;
            node.OppPlayer = my;
            node.IsMaxPlayer = !this.IsMaxPlayer;
            node.Privious = this;
            this.NextList.Add(node);
        }
    }
    class BlockerNode : Node {
        #region プロパティ
        public List<Creature> Attackers { get; set; }
        Dictionary<Node, Dictionary<Creature, Creature>> Blockers { get; set; }  //keyブロッカー　val アタッカーor null
        #endregion
        #region コンストラクタ
        public BlockerNode()
            : base() {
        }
        public BlockerNode(List<Creature> attackers) {
            Attackers = attackers;
        }

        #endregion

        public override void CreateNextNodeList() {
            var cre = MyPlayer.GetCreatures().Where(x => !x.Taped).ToList();
            Dictionary<Creature, Creature> noBlock = new Dictionary<Creature, Creature>();
            foreach (var x in cre) {
                noBlock.Add(x, null);
            }
            List<Dictionary<Creature, Creature>> blkList = new List<Dictionary<Creature, Creature>>();
            blkList.Add(noBlock);
            foreach (var x in cre) {
                var add = new List<Dictionary<Creature, Creature>>();
                foreach (var y in blkList) {
                    foreach (var sel in Attackers) {
                        var blk = new Dictionary<Creature, Creature>(y);
                        blk[x] = sel;
                        add.Add(blk);
                    }
                }
                blkList.AddRange(add);
            }
            NextList = new List<Node>();
            foreach (var x in blkList) {
                var val = SolveCombat(x);
                if (val != null) {
                    NextList.Add(val);
                }
                else {
                    if (IsMaxPlayer) {
                        CurrentEvaluation = Evaluation.Min();
                    }
                    else {
                        CurrentEvaluation = Evaluation.Max();
                    }
                }

            }
        }

        //ダメージ割り振り解決
        private SecondMainPhaseNode SolveCombat(Dictionary<Creature, Creature> block) {
            SecondMainPhaseNode newNode = new SecondMainPhaseNode();
            newNode.MyPlayer = new Player(this.OppPlayer);
            newNode.OppPlayer = new Player(this.MyPlayer);
            newNode.IsMaxPlayer = !this.IsMaxPlayer;
            newNode.Privious = this;
            foreach (var atk in Attackers) {
                var blks = block.Where(x => x.Value == atk).Select(x => x.Key);
                if (blks == null) {
                    newNode.OppPlayer.Life -= atk.Power; //ブロックされていなければダメージが入る
                    if (newNode.OppPlayer.Life <= 0) {   //死判定
                        return null;
                    }
                }
                else {
                    int rest = atk.Power;
                    var b = blks.OrderBy(x => -x.Power);
                    foreach (var blk in b) {    //パワーの大きいブロッカーからダメージを割り振る
                        if (blk.Power <= rest) {
                            rest -= blk.Power;
                            newNode.OppPlayer.CreatureIsTaped.Remove(blk);
                        }
                    }
                    if (atk.Power <= blks.Sum(x => x.Power)) {
                        OppPlayer.CreatureIsTaped.Remove(atk);  // アタッカーの死判定
                    }
                }
            }
            return newNode;
        }
    }

    class AttakerNode : Node {
        public override void CreateNextNodeList() {
            var creatures = MyPlayer.GetCreatures();
            //0
            //1
            //01
            //11
            //001
            //101
            //011
            //111とふえていく
            List<List<Creature>> attacker = new List<List<Creature>>();
            attacker.Add(new List<Creature>());
            foreach (var x in creatures) {
                List<List<Creature>> add = new List<List<Creature>>();
                foreach (var y in attacker) {
                    var atk = y.ToList();
                    atk.Add(x);
                    add.Add(atk);
                }
                attacker.AddRange(add);
            }

            NextList = new List<Node>();
            foreach (var x in attacker) {
                BlockerNode node = new BlockerNode(x);
                node.MyPlayer = new Player( this.OppPlayer);
                node.OppPlayer = new Player(this.MyPlayer);
                node.OppPlayer.TapCreatures(x);
                node.IsMaxPlayer = !this.IsMaxPlayer;
                node.Privious = this;
                NextList.Add(node);
            }
        }
    }
}

MTGの単純化 - 探索の無駄をなくす -

MTG

前回の探索プログラム

前回、木探索のプログラムを書いてはみたものの、時間がかかりすぎて終わらなかった。できるだけ無駄な探索を減らして効率的な探索に修正する必要がある。

単純化

　プレイヤーが選択することはアタックとブロックである。すごく簡単にしたけど、これでもクリーチャーが５体ずつ並んでいる場合に、１体がアタックする場合のブロックの仕方は2^5通りある。2対の場合は3^5、3体の場合は4^5となり、１ターン中のアタックを選んでブロックを行うときのの場合の数は

f:id:Delver:20150725211030p:plain

36,232通りとなる。

この試行をライフが0になるまでランダムに繰り返す。こんなこと20ターンも繰り返せば終わるわけない。

 

条件の絞込み

　探索を行う上で誤った試行は省きたい。

アタック・ブロックの最低ルール
  1. 相手のライフを0以下にできるならすべてのクリーチャーでアタックする。
  2. 自分のライフが０以下になるブロックは行わない。
  3. 2/2が2体ブロッカーに立っている場合に3/3がアタックして2/2と3/3の交換になるような損なアタックは行わない。
  4. 2/2を残して3/3でチャンプブロックのようなメリットのないチャンプは行わない。

　

アタック・ブロックのルールの数式化

これらをプログラムに落とせるように数式で表現する。

  1. アタッカーがA(1) ~ A(n)までのn体いて、同様にブロッカーB(k){k=1,2,.....,m}がいるとする。このときAatk(1)  <= Aatk(2)<=.... <=Aatk(n)とする。

    f:id:Delver:20150726000355p:plain

    のとき、すべてのクリーチャーでアタックする。

  2.  [1,n]の範囲から攻撃を通すクリーチャーを選んで整数の集合Sとして表記する。

    f:id:Delver:20150726010841p:plain

    を満たすブロックが合法手である。

  3. A(k){k=1,2,..n}でアタックを試みる。すべてのブロッカーB(k){k=1,2,...,m}の集合をSとする。Sを部分集合の集合X1,X2,....Xnに分割するとき、すべてのkに対して

    f:id:Delver:20150726010844p:plain

    となる分割Xが存在する場合非合法である。
  4. アタッカーがA(1) ~ A(n)までのn体いて、同様にブロッカーB(k){k=1,2,.....,m}がいるとする。このときAatk(1)  <= Aatk(2)<=.... <=Aatk(n)であり、Batk(1)<=Batk(2)<=... <=Batk(m)とする。A(p)をB(q)でブロックするときBatk(q) < Aatk(p)を満たす場合、「Batk(k) < Batk(q)」かつ「B(k)はブロックを行わないかダブルブロック以上を行う」を満たすkが存在する場合非合法である。

 

・さらに、 MTGのルールではないが、最善手を見つけたらそれ以上そのノードの探索は行わない。を付け足す。

終わりに

　これで計算終わるのか？ひとまずコードにしてみようと思う。

 

 

不完全情報ゲーム例として大貧民のアルゴリズムについて調べた

数学 ソフトウェア

今回は不完全情報ゲームについて調べる。不完全情報ゲームは各プレイヤーが相手の手札などの知らない情報が存在するゲームのことで、MTGは当然これに含まれる。不完全情報ゲームの基本的なAIの動作に関しては情報処理学会誌に以下のような記述がある。

　ゲームの状態がわからないとモンテカルロ木探索などの探索的手法は適用できない。そこで可能なじょうたいからランダムに状態をサンプリングし、完全情報ゲームと同様にモンテカルロ木探索を実行することが行われている。これをモンテカルロサンプリングという。[情報処理学会誌より]

　

モンテカルロ木探索

　まず、見えないハンドをランダムに割り当てる。これに対して、何度もランダムにゲームが終わるまでプレイしてみて各プレイの勝率を調べる。また別のハンドを割り当てて同じことを行う。これを繰り返して勝率の高いプレイを選択するというのがモンテカルロ木探索である。囲碁で初めに使用された手法であるが、ランダムにプレイしてみるタイプは無駄な探索が多くとても弱いらしい。囲碁なんて適当に打ったら端っことかにも石を置くだろうし当然といえば当然であるが。そこで、もっともらしい手の比率を上げてランダムにプレイするという手法がとられている。結局このもっともらしさとは何かを調べるのが大変なのであろう。

参考：http://homepage1.nifty.com/ta_ito/fit2008/muramatsu-fit.pdf

　さらに、情報処理学会誌に書かれている内容に、ε-Greedy法というものあるが、これは初手はランダムでプレイして手が進むにつれてもっともらしい手を中心に打つようになるというものである。この手法は尤もらしさの評価により強く依存するようになっている。

次に考えること

　MTGのシミュレーションにはこのモンテカルロ木探索を使用することになるだろう。探索を効率的に行うために、明らかに誤った手とはなにか、もっともらしい手とは何かといったことを調べる必要がある。まずは単純なデッキで考察し、ソフト上で動作させてみたい。