選択肢の探索を簡略化するための思考フレームワーク
本記事は、Tobyさんが企画したShadowverse Advent Calendar 2021の11日夜の部の記事となります。
概要はこちら toby4108.hatenablog.jp
自分が参加している夜の部のカレンダーはこちら adventar.org
昼の部のカレンダーはこちら adventar.org
本記事の概要
本記事ではカードゲームのプレイ中に発生する選択肢を比較し、より良い選択肢を選ぶための手法について考察します。 特に近年のshadowverseでは選択肢の数が膨大であるため、厳密な選択肢の吟味が難しい場面が多い傾向にあります。 そこで本記事では特に選択肢の絞り込み、つまり不要な択をいかに効率よく除外する手法について、筆者が実際にプレイ中に行っている考え方を元に考察します。
※簡単な数学のお話などが付き纏いますが厳密に論じる気はなく、またイメージで伝えることを優先するので、理解していなくても読み進められるように記事を構成していますが、詳細が気になる方は自分で調べてみてください。
はじめに
カードゲームのプレイは基本的に
- 選択肢を発見する
- 選択肢を比較する
ことの繰り返しである(これらは必ずしも逐次的に実行されるというわけではない)。
このうち選択肢の比較というのは非常に難しい手順である。
Shadowverseの場合、ほとんどの(競技)プレイヤーは大まかに
- 1ターン後の具体的な盤面とライフ状況
- 2～3ターン後の大まかな盤面とライフ状況
- リーサルターンの検討
という情報を毎ターン扱っていると思われる。 リーサルまでの5,6ターン以上先までの情報を扱うとなると、例えば毎ターン5つしか選択肢しか存在しない場合でも、55の約3000パターンが存在する。 パターンだけでもこれだけの数が存在し、さらに相手の行動とランダム要素によって選択肢を評価する必要があるため、人間が90秒で処理するには到底不可能な情報量である。
そこで、扱う情報量を減らすスキルが必須となる。 パターン化はその際たる例で、すでにこのアドカレ企画ではGarbageさんやRumoiさんにその重要さを十二分に説いていただいた。
本記事ではさらに扱う情報量を減らすスキルとして汎用的に選択肢を効率的に比較する手法について考察する。
具体的には探索アルゴリズムの応用と平均・分散を利用した選択肢の評価を利用することで、選択肢を効率的に絞り込むことを考える。
※ 細かい話を抜きにして結論だけ見たい人はこの辺まで飛ばしても読めると思います。
探索について
探索とは
探索とは、特定の制約条件を満たす物を見つけ出す行動である。 特に探索アルゴリズムの文脈では現在の状態(state)と行動の結果状態がどう変化するか(action)を、目的の状態に到達するこれらの系列を発見する問題として定義されたものである。
選択肢の探索はその中でも木探索の構造に近く、これは15パズルや8パズルが代表的な問題として知られる。
探索アルゴリズム
木探索についてnaiveな手法は主に以下の2つ
簡単に説明すると、例えば毎ターン5つの選択肢が発生して3ターン先までの選択肢を検討するとき、 深さ優先探索では3ターン先の125個の状況を1つずつ比較して最善の選択肢を発見するのに対して、幅優先探索では毎ターンのすべてのパターンを並列に処理しながら5,25,125の選択肢を同時に検討するイメージ。
それぞれ前者では時間計算量、後者では空間計算量に大きく負荷をかけることになるが、人間の並列処理に使用可能なメモリはたかだか知れているため、人間が選択肢を検討する際は多くの場合深さ優先探索を利用することになるだろう。
しかし、125個の選択肢を90秒の間にすべて比較することは難しく、またその125の選択肢をそれぞれ脳が記憶したまま順番に比較するというのも難しい。
そこで、以下の2つで探索を効率化することが考えられる。
- ありえない選択肢を省く
- 探索する順番を考慮する
これは探索アルゴリズムにおけるA*に代表されるような最良優先探索の1つと言えるだろう。
簡単に説明すると、A*では現在地点に至るまでのコストとゴールまでの推定コストを合計したコストが最小になるものから探索することで、コストが低くなる可能性が高いものから順に探索することで効率的に実行する手法である。
これをカードゲームの選択肢の探索に応用するにあたって、筆者は以下のように定義した。
- 現在地点に至るまでのコスト：現在ターンにおける有利・不利状況
- ゴールまでの推定コスト ：その選択肢を取ったことによる評価値の分布
定義についてはこれが正解とは言えないため読者のみなさまにも色々と考えてみてほしい。
次章ではこの定義に基づき選択肢の評価値について議論する。
選択肢の評価値を分布で考える
確率分布として捉える
例えばある選択肢を取ったとき、その選択肢の点数が100%の確率で40点や60点などの点数になることはなく、多くの場合で20%の確率で40点になるが80%の確率で60点になるということが多い。 これは不確定な情報(対面の手札/対面が取る選択肢/自分と対面のドローするカード/その他のランダム要素)に起因するものであり、カードゲームである以上は必ず発生する現象である。
したがって、カードゲームの選択肢における評価値とは、それぞれが点数と発生確率を持つ確率分布と定義できる。
確率密度関数として扱う
選択肢の評価値を確率分布として定義したが、このまま扱うのは非常に難しい。
例えば、ある選択肢を取った事による評価値を3ターン後の状況から定義する場合を考える。 各ターンに5の選択肢がある場合、自分の選択の結果だけで25パターン、相手の選択の結果で25パターン。 さらにランダム要素としてドローのパターンが20パターンあったとして2人2ターン分etc...と考えると途方もなく、人間が処理することは到底不可能だろう。
解決方法の1つは最善/平均/最悪の3つのパターンだけを考えることである。 しかしこの方法だけでは発生確率を有効に考慮することが難しく、選択肢の比較をすることが難しい。
筆者はこの問題に対して、各選択肢を取ったときの評価値が膨大であることから連続値と見なして確率密度関数として扱い、さらに選択肢のそれぞれはほとんどがランダム要素に左右されることから、それが正規分布に従うと仮定した。
これにより各選択肢が持つパラメータを平均と分散の2つだけに絞ることができた。
平均と分散を利用して選択肢をマッピングする
パラメータを2つに絞ることで扱いやすくなったので、本来の目的である選択肢の比較を行いやすくする工夫をさらに考える。
筆者は平均と分散だけで脳内の処理を進めることもあるが、もう少しイメージしやすい状況を作りたいときに選択肢のマッピングするときがある。 具板的には各パラメータの大小で以下の4つのパターンで分類し、それぞれに選択肢をマッピングすることで絞り込みを行う手法を取っているのでその一例を紹介する。
| 分散/平均 | low | high |
|---|---|---|
| low | 妥協択 | 安定択 |
| high | 一か八か | 勝負手 |
各項目について軽く触れる。
安定択(平均high, 分散low)
平均が高く分散が低いということは、高い出力が安定して出せるということである。 多くの状況において、ここにマッピングされる選択肢を目指すことが最善となることが多い。
有利・フラットな状況ではほとんど有効に働くし、不利状況であっても最低保証としての価値が高い。 例えば極端に不利な状況で、平均値を大きく超えた評価値の選択肢を必要とするような状況においては他にマッピングされる選択肢が優先されることがある。
妥協択(平均low, 分散low)
平均も分散も低いということは、大きくリスクも背負わないが大きいリターンも得られないということである。 したがって有利な状況においては最低保証として有効に働くが、不利な状況においてはただ緩やかな死を迎える最低の択となることが多い。
勝負手(平均high, 分散high)
平均値も分散も高いということは最もハイリターンが得られる可能性が高いということである。 したがって不利状況においては積極的に狙いたい選択肢である。
一方で、分散が高いということは出力のブレが大きいため、一定値を下回る可能性は妥協択よりも高く、有利状況で無用なリスクを背負う原因ともなる。 競技プレイで最も重要なことは、有利状況において勝負手を打たないことだと筆者は考えている。
一か八か(平均low, 分散high)
平均が低く分散が高いということは不安定な上にあまりリターンも得られない、基本的には狙いたくない選択肢である。 しかし、不利状況において妥協択を選んでも何も状況が変わらないことがほとんどで、そういう場合に良い勝負手が存在しなければ妥協択よりも戦況を変える一手になる可能性が高い。
選択肢を絞り込む
選択肢に探索における2つのコストは
- 現在地点に至るまでのコスト：現在ターンにおける有利・不利などの状況
- ゴールまでの推定コスト ：その選択肢を取ったことによる評価値の分布
と定義した。
実践で手順としてはまず現状の状況判断をした後、以下のどちらかのパターンで進行するのが現実的であろう。
- 候補択を列挙した後、それらをマッピングして適切な候補を絞り込む
- 基準となる択を軸に、相対的に適切な選択肢を探索する
2の手順を踏む場合は
- まず基準となる選択肢の平均・分散を予測
- その択の平均的なリターンを得た場合に自分の状況が有利になっているか(すでに有利な場合は不利にならないか)を予測
という手順を踏むことで、平均値を大きく超えたリターンが必要かどうかを判断する。 必要な場合、多少平均値を下げてでも分散が大きい択の方が状況が好転しやすいし、 そうでない場合も多少平均値を下げても分散が小さい方が現状を維持しやすいのはこれまでの議論より明らかだろう。
状況に応じた選択肢の絞り込みの例
ここでは現在ターンにおける状況をおおまかに場合分けして、マッピングされた選択肢の優先順位を考える。
※実践では前述の通り、平均値を大きく超えたリターンが必要かどうかの判断が必要になるが、ある程度参考になるだろう。
フラットな状況における判断
安定択＞勝負手≧妥協択＞一か八か
アドバンテージを稼ぎたいため、基本的に平均＞分散の優先度で良い。 フラットだが有利寄りの状況判断をするなら、妥協択が優先されることもある。
有利状況における判断
安定択＞妥協択＞勝負手＞一か八か
有利な場合はその状態を維持することが大切になるため、リスクを負わないことを優先する。
不利状況における判断
勝負手＞安定択≧一か八か＞＞＞妥協択
不利状況においては平均値以上のリターンを得ることを優先したい。 不利度合いが激しいときは、自分でも予測不能の択を取ることも考慮に入れたい。
実際に選択肢を絞り込んでみる
ここからは実践に移る。
主に前節で説明した以下の2つの方法を利用して選択肢の絞り込みを行う。
以下、実際の試合の場面を用いて考察する。
マリガン
状況は以下の通り
- Bo3の1戦目
- 相手のNcは型不明
- 自分のNcは進化Nc
- 後攻
マリガン時の状況判断はマッチ相性と先後のみで決まるため最も状況判断が簡単である。
進化Ncミラーと仮定すると、後手は相手が順当に動いたときに後手4ケルヌンノス＋スージーを決めないとほぼ捲れないほどの不利だと自分は認識している。
一方で対ラスワNcを仮定すると相手の面が強くなるのはだいたい先5であり、墓地とドローを順当に回して後5に強く面を返す準備を整えればフラット～有利なゲームに持ち込めると認識している。
次に択の分類を考える。
今回は何も考えなければベルエンジェルを単キープしそうなハンドなので、相対的に択を分類する。
まずスージー単キープの択について。
この択のメリットは明確に後手4のケルヌンノスの受けを見れることである。
進化Ncミラーを仮定するとこのリターンが非常に欲しい展開である。
一方でデメリットは多く存在し、
などが考えられる。
したがってこの選択肢はベルエンジェルをキープする選択肢に比べて分散がかなり大きい択と言える。
この択の平均値についてはデメリットの多さからベルエンジェルをキープするよりやや低いと予測できるため、勝負手寄りの一か八かの択に分類できそうだ。
ではベルエンジェルとスージーを両方キープする択はどうだろうか。
スージーを単キープする択と比べて、ドロー枚数が変わらず(ワンドロー/マリガンの差)ラストワードが確実に1枚進んでいる点から一見すると、デメリットが解消され分散が小さくなるように思われる。
だが実際は、2枚目のベルエンジェルを引いた際に4Tまでにドローに変換できない可能性が高いことや、序盤のトレード性能がなく、ケルヌンノスを引けなかったときに4Tのボードが取り返しのつかなくなるほど悪くなる可能性が高いことから、最低値がさらに低くなることとケルヌンノスを引く期待値が下がることから分散が逆に大きくなることになる。
したがって、この状況は不利状況の度合いを鑑みて安定択か一か八かの択を選択するという問題に帰結する。
相手が進化Ncが確定している状況ならスージー単キープ優勢だったが、今回は対面が不明のため
相手がラスワNcである確率＋相手が進化Ncであるが序盤の動きが鈍い確率 ≒ 進化Ncで序盤からしっかり動く確率
であると判断し、筆者はベルエンジェルを単キープして様子を見る選択肢を取った。
後手4T
さて、筆者の目論見が外れてしまい、対面は進化Ncだし序盤はフルムーブで非常に困った、という後手4T。 スージーを残していればゲームになりそうだが、後悔してはいられないこのゲームの勝負所のターンである。
状況判断は言うまでもなく非常に不利。勝負手を探したいところである。
さてまずは手の形を見てどのような報酬が最も評価値が高くなるかを考える。 この状況で考えらえるわかりやすいリターンは
- このターンのドロー先がスージーであること
- 次のターンにネクロマンスを10以上消費できる形にすること
の2つである。 しかし前者は3/30=10%と非常に低く、このリターンだけを得るためだけに大きなリスクを背負うことはしたくない。 一方で後者の達成を考えても、現状墓地が盤面を含めても5しか稼げておらず、現状の手だけではかなり厳しくなるべくドローを進めたい。
以上からまずは基準択として、リスクの少ないドロー択として記憶の奇跡打ちから検討する。
この択はボードが自壊すれば墓地が6になりこのターンにシャオが起動することも含めメリットが大きい。
しかし、ラスワのカウントが3枚となり、たとえ上からスージーを引けたとしても再誕の受けに対して弱い形になってしまう。
引けなかった場合は、シャオから出た死門に進化を切れば達成するが、このターンか次のターンにベルエンジェルを切らないと有効に使えず動きに縛りが出来てしまい、相手の面が多く残ってしまうことが予想される。
進化Ncミラーにおいて、相手の盤面に残すこと=ライフをもらうことは非常に不利をもらいやすく、できるかぎり避けたい行為である。
一方で盤面に残すことはスケルトンレイダーのバリューを高めることにもなり6T以降に打点に換算されないボードは対機械Nmのように残さないという戦法もある。
そこで、リターンについて改めて検討してみる。
6Tにシャオ＋スケルトンレイダーの形で面を返しながら、7Tに＋αの打点(現状だとデッドスタンピード/うまく墓地が回ったときのケルヌンノス/山上のグリームニル)で差し切る展開を見る。
山上のスージーは相手の面を返し切ることは出来ておらず、このリターンを得られたとしても、実は試合を動かすほどのリターンにならないということが予測される。
この場合はむしろ記憶の軌跡は相手に差し切られない有効回復として残しておいたほうがよく、死門もこのターンに自壊せず相手の5Tに当たってもらうor残ったときに回復として有効に働き先7を耐える札になりうると予測できる。
ここから先程上げた2つのリターンは評価値(平均値)が低いリターンであると考え、打点を引き込むことがさらに大きいリターンであると判断できそうだ。 したがって記憶の軌跡を温存しながらドローを進める選択肢はかなりの安定択であり、ベルエンジェル進化を新たに基準択として設定した。
最後に、この選択肢より平均値が高くなりそう、または平均値が変わらず分散が高くなりそうな択を検討するが、おおよそ見つからなかったので筆者はベルエンジェル進化を選択した。
後手5T
今度は後手4に色々と読みきったおかげでおおむね予定通りの展開となった。 先のターンに多くドローしたことと大きいサイズのベルエンジェルを立てたことによりボード状況がフラットになり、大きく回復を見込めるハンドとなったため不利度合いが改善している。
このターンに取るべき行動は次のシャオ＋スケルトンレイダーと7Tの打点最大択を両立させることである。 さらに達成したい項目として最大限に回復する(次のターンは回復できないので出来ればボードに回復を残す)ことが考えられる。
7Tの打点最大択はスージー直接召喚+デッドスタンピード+進化+墓地20ケルヌンノスが手に見えている最大択である。 加えて山上のグリームニル、このターンの進化前に引く2枚目のスケルトンレイダーは打点として受けている。
これらを考慮するとこのターンの択はルナ人形奇跡2枚ドミネーターが基準択となりそうだ。 この時点で墓地は死門からベルエンジェルが出れば18、ゴシックリーパーが出れば20となっている。 18の場合はスージーの墓地が足りないので、2枚目はスケルトンレイダーは受けても打点が最大にならない可能性がある。 したがって、ドミネーターの捨て先はグリームニルを引いた場合のみケルヌンノス、それ以外はケルヌンノス以外の何かを捨てるのが適切だろう。
以上の前提からこのターンは奇跡を2枚打つところからスタートする以外は選択肢がなく、比較検討先が存在しない。
本記事で提案するメソッドは絞り込みを行うためのものであるので、このターンのように読み切れる場合は使わないのが基本となる。
後手6T～リーサル
ここまででこの試合で思考することは終わったので、蛇足になるが結末を載せておく。
結果的には相手が初手から持っているスケルトンレイダー+グリームニルの先7リーサルパターンを回避し、死門からはゴシックリーパーを召喚。 さらにグリームニルを引くことでしっかりと相手の回復を貫通して運良く勝利することができた。
おわりに
本記事では思考を簡略化するメソッドの1つとして、探索アルゴリズムと平均・分散を利用した選択肢の評価を例に挙げた。
具体的には
- 選択肢の絞り込みを最良優先探索で解くことを考える
- 現在地までのコストを状況判断、ヒューリスティック関数を選択肢の評価値とする
- 選択肢の評価値を正規分布に従う確率密度であると仮定し、パラメータを平均と分散の2つに減らす
という手順を踏むことで、脳内の選択肢の絞り込みの処理を
- 現状の有利/不利/フラットの状況判断をする
- 選択肢の平均と分散を予測し、適切な選択肢を抽出する
という非常に簡単な2工程に収める事ができた。
注意しておきたいのは、このメソッドはあくまで概算的かつ選択肢の絞り込みにのみ応用できるという点である。
当然だが、択の評価値が正規分布に従うというのは大胆な仮定であるし、そもそも評価値も平均値に圧倒的な差があれば分散など比較するまでもないことも多い。
今回のメソッドは多くの選択肢が存在するときにある程度まで絞り込んだり、微差の選択に対して根拠を与えることの助けになるだけであり、
展開を読み切れる場合はすべて選択肢を厳密に読み切ることが間違いなく勝利に一番近くなるだろう。
また今回は筆者がCS(Computer Science)の出身であるため、馴染みのある探索アルゴリズムの考え方を適応しただけであり、読者のみなさまにはぜひ自分と違う考え方で、より厳密またはより簡潔である選択肢の探索方法を発見・共有していただきたいと思う。
いずれにせよ現代のShadowverseは選択肢のすべてをいかなる場合でも検討出来るような簡単なゲームではなくなり、人が処理する以上は何かしらの簡略化が必要となる。 その手法として局所的だが非常に効果的なパターン化に対して、抽象的な本記事のフレームワークは様々な場面で少しだけ役に立つだろう。
両者を駆使して重要な思考に使う時間を0.1秒でも長くすることが、現代のShadowverse攻略の近道となれば幸いである。
おまけ
有利な状況であれば基本的にリスクを取るのは損にしかならない。 したがって、相手に自分が今有利な状況にあると錯覚させながら不利な状況に陥れると、相手は勝負手を取らずに緩やかに負けていくこととなる。
なかなか狙って出来ることではないが、筆者はこれが勝負事における最も確実な勝ち方だと考えている。
逆に、相手に今は不利だと認識させてしまうと相手がリスクを承知で勝負手を打たざるを得なくなるので、勝負手を勝負手だと気付かせない技術、みたいなものがあればそれは最も大切だと思う。
ということで
相手を追い詰めすぎると強すぎる択で返されるため、相手は追い詰め損
— Yua(Hiroya Shimono) (@as_your_real) 2019年1月27日
おしまい。
宣伝
明日はMiguruさんの『レート初ランクインしたお話＋情報のお話』と、 tdTomatoさんの記事です。
お楽しみに。
