Translated by Nobukazu Kato
(掲載日 2021/06/16)
はじめに
アルゴリズムという言葉は秘儀のようなオーラを感じさせます。ソフトウェアエンジニアがデータを集めたり、検索結果を並べたり、動画をおすすめするときに唱えるような魔法です。
しかし実際は、多くのコンピューターサイエンスの専門用語がそうであるように、アルゴリズムとは聞きなれないだけでシンプルな概念を表す用語です。アルゴリズムとは、意思決定をシステマチックに行うための方法のこと。みなさんも料理をするときにレシピを見たり、進む道を決めるときに地図を使ったりしますよね。これもアルゴリズムを使っている例です。
ただ、コンピューターサイエンスのアルゴリズムはその優劣を証明することができます。レシピはどれが最高のレシピか証明する方法はないですし、そもそもその証明に意味もありません(一人一人味覚が違うわけですから)。
しかし、マージソートやいかなるn-log-nソートアルゴリズムが明確に最善であると証明することはできます。どのアルゴリズムが、なぜベストなのかがわかるのです。形式的なアルゴリズムは現実世界の意思決定の背景にはない明快さがあります。
マジックや人生全般の意思決定の質を上げようとアルゴリズムにインスピレーションを求めた結果、意思決定のプロセスに一定の明快さが伴うようになりました。εグリーディ法による探索を使った考え方についてはプレイヤーズツアー・ファイナルのレポートで言及しました。この記事では、私の経験上、有用だと思ったそのほかのアルゴリズムをご紹介しましょう。
最悪を想定する
最先端のゲームAIでさえも利用しているのが、ミニマックス法と呼ばれる基本的な意思決定アルゴリズムです。ミニマックス法では、対戦相手の行動を推測したり、可能性がもっとも高い一手を明確にしようとするのではなく、相手が意思決定するたびに自分にとって最悪の結果になると想定します。シンプルではありますが、効果的で汎用性のあるアルゴリズムです。
このフレームワークはマジックのあらゆる状況で有用ですが、なかでも有効なのは戦闘です。お互いにクリーチャーを5体ずつ並べている状況において、自軍全員がリーサルの攻撃に向かった場合に起こり得るパターンを全て把握するのはほぼ不可能です。ダブルブロックやトリプルブロックを度外視してシングルブロックを考えただけでも120通りあります。
ここでブラフや相手の癖に思考を巡らせるのではなく、相手が自分の手札を完全に知っているという前提のもとで最悪の結果は何かを考えます。もし自分が何らかのコンバットトリックを持っていたら、相手はそれを把握していて、完璧にそれをケアしてきます。
最悪のシナリオがそう悪くないと思えば、そこで思考を止め、自信を持って攻撃に向かえるでしょう。結果として起こることは事前に想定したよりも悪いことはないのですから。最悪のシナリオが受け入れがたいものであるならば、言うまでもなく自軍をおとなしくさせておくべきです。
攻撃宣言後、相手が想定した最悪のシナリオ以外の行動をとってきた場合は立ち止まってその理由を考えます。相手は把握しているはずのコンバットトリックに引っかかりにきた？相手は除去を持っているのか、それともここでコンバットトリックを消費させることで後々もっと上手い使わせ方をさせないようにしたいのだろうか？
もちろん実際には相手がそのコンバットトリックを読めていないこともあるでしょうし、ただ単にケアしている余裕がないこともあるでしょう。ですから、この理屈のまま行き過ぎた考えをしてはいけません。ただ、相手が上手いほど、最善でないプレイの裏には何かあります。また、最悪のシナリオを事前に想定しているからこそ、その裏を読むべき状況だとすぐに気づけるのです。
最悪のシナリオを想定することに慣れてくれば、ちょっとした未来予知をしている気持ちになります。強いプレイヤーはその予想通りに行動してくるでしょうし、全軍突撃ではなくクリーチャーの数を減らしたら何が起きるかも考えられるようになります。相手が自分にどうブロックして欲しいと思っているのかを理解できるようになると、そのブロックが自分にとって都合の良いものだった場合、相手にはその戦闘で勝つための何かを握っているのだと推測がつくでしょう。
誤差逆伝播法
現代ゲームAIの成功の裏にはもうひとつのアルゴリズムがあります。それはモンテカルロ木探索、通称MCTSです。MCTSの基本コンセプトは、コンピューターが数ある手からランダムに行動を選び、ゲームの終 局まで導いていくこと。
このプロセスを何千、何百万回と繰り返してゲーム木を作成し、そこから最善のプレイを見つけ出します。MCTSはニューラルネットワークや行動空間の縮小、深さの制限など改良が重ねられていますが、AlphaGoまでのAIはこのモンテカルロ木探索を使用しています。
もちろん、何千回とゲームをシミュレーションするのはコンピューターにしかない強みです。とはいえ、MCTSは重要で実践的な考え方を示唆してくれます。つまり、ゲームの終局を想像し、そこから逆算して行動することです。
これをマジックで言い換えるなら、このターンや次のターン、あるいは4ターン後に起きることを予想するのではなく、自分が勝っているとすればどのようなゲーム状況になっているかを把握するのです。もしかしたらそのためには特定のキーカードを引かなくてはならないのかもしれませんし、相手のミスを待たなくてはならないかもしれません。そうだとしても、鮮明に描いたゲーム状況を目指してプレイすることが大切なのです。
ここでひとつ私が好きな言葉を引用してみましょう。第二次世界大戦時に陸軍大将であったジョージパットンの言葉です。
来週まで完璧な計画を待つぐらいなら、及第点の計画を強引にでも今すぐ実行したほうが良い
言うまでもありませんが、ノープランに成功の見込みはありません。この考え方を実践すれば、完璧な計画、つまり一番勝てる確率が高いゲームの終局を選び取ることはできないでしょう。しかし、プランを持ち、そのプランに沿って行動していくことで、何が上手くいき、何が上手くいかないのか、良いプランと悪いプランを分けるものは何なのかがわかるようになってきます。
これを継続していけば、良いプランと悪いプランを直観的に見分けられるようになるでしょう。そして同時に、たとえ実行しているのが悪いプランだったとしても、目の前のターンのことばかりを考えているよりかは断然実りがあるのだとわかるようになるはずです。
水道
どんなゲームであれ、ゲーム状況を数学的に評価するには何らかの評価関数が必要になります。ほとんどのゲームは簡単な評価関数で問題ないでしょう。ゲームに勝ったら1、負けたら0というように。
しかし、チェス・囲碁・マジックのように複雑なゲームの場合、もっと高度にする必要があります。たとえばAlphaGoは盤面状況を評価できるように学習させたニューラルネットワーク。初期のAlphaGoはMCTSを20手分まで適用し、導かれるゲーム状況をニューラルネットワークへと受け渡し、結果のゲーム木に対してミニマックス法を使います。
複雑なゲームでは、ゲーム状況の有利不利を判断するのはほぼ直観です。ニューラルネットワークでさえもその直観をアルゴリズムによって形式化しようとしています。ですが、マジックには観測可能な指標がいくつかありますね。たとえば、競技マジックに最初の一歩を踏み入れたとき、「カードアドバンテージこそが最強で、ライフはリソースの1つに過ぎない」と教わります。
このような経験則は新規プレイヤーにとっては確かに便利なものでしょうが、私はこの考えが嫌いです。マジックで勝てるのは、相手のライフを0にしたからであって、相手よりも《予言》を多く撃ったからではないですよね。
では私がどう考えているかと言えば、マナ・カード・ライフ・ターンの4点で捉えています。《闇の腹心》を《稲妻》で除去すると、1マナ分の得をして、カード・ライフ・ターンの点では等価交換しています。これはかなり美味しい交換ですね。
では、《悲しげなセルキー》に《稲妻》を撃つ場合はどうでしょう。こちらは2マナ分の得をしますが、相手が1枚分カードを得をする。そのほかは等価です。この交換がどちらにとって美味しいのかはマナとカードのどちらがリソースとして重要なのかによるでしょう。いずれにしても、リソースの交換と言えます。
この4つの指標のなかで、ほとんどの場合で最重要なのはマナです。だからこそ1マナの呪文は強いんですよね。1ターン目に《貴族の教主》を出すと、《はらわた撃ち》や《溶岩の投げ矢》のような例外はありますが、除去されてマナを損することはあり得ません。逆に言うと、《稲妻》は最低でもマナの等価交換が保証されており、美味しい交換になることも頻繁にあります。
カードとマナの価値は状況に大きく左右されますが、《自然の怒りのタイタン、ウーロ》《表現の反復》《夢の巣のルールス》などがあるご時世ですから、カードが重要な要素になることは稀です。仮にカードやライフの重要性が高い状況だったとしても、たいていは積極的にそれらをマナのために交換していくべきでしょう。
ターンは最低でもカード1枚と5マナ以上に相当し、圧倒的に希少価値の高いリソースです。ただ、ターンを得られる状況はほとんどありません。完全な1ターン分を得られる状況、たとえばクリーチャーの攻撃回数を増やしてクロックを1ターン分縮めたり、コンバットトリックを使って即刻ゲームに勝ったりできる状況であれば、通常はその選択肢を取るべきでしょう。
このほかにも「キーカード」という知っておくと便利な概念があります。ここでいう「キーカード」とは、特定のマッチアップにおいて繰り返しアドバンテージを発生させるものであり、なおかつ除去しづらいものを指します。
ひとつ例を挙げると、《地下世界の人脈》は先ほどの指標に照らせばプレイアブルなカードではありません。カード1枚に4マナとライフ1点を払い、カード2枚に5マナとライフ2点を払い……と続きます。カード4枚目まではかなり割に合わない交換ですね。
ですが、マジックには4枚分のカードを発生させるカードはそうありません。ましてや、かつての黒単信心ミラーでは《地下世界の人脈》は絶対に破壊できないカード。そしてそのミラーマッチはゲーム速度が遅く、リソース勝負であり、ライフがものを言うことはほとんどありませんでした。もしこういったキーカードを破壊できれば、みなさんが得をすることになります。
ここで紹介した考え方は、マジックのゲーム状況を評価するには決して万能なものではありませんが、何かしらのヒントを得ていただけたらと思います。私の評価システムを使うにしろ、みなさんの独自の評価システムを使うにしろ、何らかのシステムは必要だと覚えておいてください。
魚はほかにもたくさんいる
みなさんは従業員を1人雇うとします。応募してきたのは100名であり、1人ずつ面接を行います。各面接を終えたら、その時点で雇用するかどうか決めなくてはなりません。採用を見送れば、あとから遡ってその人を採用する、ということはできないとします。しかし、誰かを採用するなら、その時点でそれ以降の面接は打ち切り。募集していた枠は埋まります。まだ面接していなかった応募者のなかにもっと優秀な人材がいた可能性もあります。さて、どうやって採用する人を決めれば良いでしょうか？
政治的に批判もあった古くに生まれたこの状況設定は「秘書問題」としてよく知られています。この問題には絶対的に正しい解法があることがわかっていますが、その解法は最高の1人を選べる保証をするものではありません。応募者100名がいる場合は、最初の37名と面接を行い、一切採用を決めることなく、最高の1人をメモだけしておきます。そして37人目以降の面接で、メモしておいた最高の1人を上回る人が出てくればその時点で採用を決めるのです。
応募者全体100名のなかでの最高の人材が最初の37名のなかにいたり、採用決定後のなかにいたりする可能性がありますので、この戦略に従った場合、その最高の1人を選べる確率は37%になります。
当然ですが、現実の世界ではこんな硬直した条件で面接を行うことはなく、もっと柔軟に行えます。たとえば、応募者全員と面接をして、全員から話を聞いた後で最高の1人に採用通知を送る、といった具合に。あるいは第一候補の人材が入社できなくなった場合、一度採用を見送った第二候補がまだ採用を受け入れてくれるパターンもあるでしょう。そうであるにしても、この秘書問題は捨てるには惜しい洞察をいくつか与えてくれます。
まず、選択肢となる候補がどれだけあるのか明確にし、それらのパフォーマンスを追うことに価値があることを示唆しています。たとえば、大会に向けてデッキを選んでいるのであれば、メタゲームにどれだけのデッキがあるのかをまず明確にします。
そしてプレイアブルなデッキが20個あるとわかったとしましょう。このとき、最適な戦略はまずデッキを選ぶことを考えずに7～8個目までデッキを回すことです。これよりも前にデッキ選択を確定させてしまえば、停止するのが早過ぎる可能性があります。仮に初期の段階であるデッキが成功を収めていたとしても、その後の候補デッキにさらに良いものが潜んでいた可能性があるのです。
次に、数学的に最適な戦略であっても、最高の候補を選べる確率は37%しかないということです。人生とは予想外な要素が無数にあるものであり、ベストデッキを見つけられないことはよくあります。テスト段階における成功とは、十分な数のデッキを回してその結果を適正に評価することであって、ベストデッキを見つけることではないのです。
最後に、最終的な判断を下すときはそれまでの経験に照らして慎重に判断することです。私はよくデッキを過大評価してしまいます。なぜこういったミスをするのかというと、その直前に使っていたデッキがあまりにもひどかったから。しかしデッキのパフォーマンスを測る上で比較対象にすべきは、その直前に試したデッキではなく、それまでに試したデッキのなかで最高のデッキでしょう。
おわりに
アルゴリズムを整数のリストのなかから過半数の要素を見つけることだと例えることがありますが、これは上手い例えだなと思います。そのリストには確かに過半数の要素が存在する、つまりひとつの数字がリストの過半数を占めているとします。ここで分割統治法を使ってリストをグループに分け、確実な答えを得ることもできますが、この方法だと実行時間がO(n log(n))より短くなることはありません。
しかし仮にリストからランダムに要素を選び、それが過半数の要素かどうかをチェックするだけであれば、実行時間は平均してO(n)になり、圧倒的に短縮されます。過半数の要素はリスト全体の半数以上に当たるわけですからね。一発目の選択でそれを当てられないのは不運でしかありません。
専門用語を多く並べてしまいましたが、要するにここで言いたいのは、ランダムに数字を選んで実行するといったごくごくシンプルな方法がときには最適解であるということです。もっとも、人というのはつい物事を深く考えすぎてしまうものですけどね。私もついつい考えすぎてしまいます。しかし、それとは反対のアプローチを採り、複雑さを手放したときに何らかの発見があるかもしれない。この記事を通じてそんな思いを少しでも持ってもらえたらと思います。
ゲームプレイのアルゴリズムについてもっと詳しく知りたい方は、一般的なゲームAIに関するスタンフォード大学の講義ノートをこちらから、AlphaGoの論文をこちらからご覧いただけます。
アレン・ウー(Twitter)
