不完全情報ゲームのポーカーで人間を倒したAI「Libratus」が採っていた戦略が論文で公開される

ポーカーは手札の情報がすべて公開されていないため「不完全情報ゲーム」だと言われており、人工知能(AI)が人間を打ち負かすのは難しいと考えられてきました。しかし、2017年1月にカーネギー・メロン大学の開発したAI「Libratus」はこの難題を見事にクリアし、人間のプレイヤー相手にポーカーで完勝することに成功しました。そのLibratusを開発した研究者が、どのような戦略をLibratusが採ったのかに関する論文を公開しました。

Superhuman AI for heads-up no-limit poker: Libratus beats top professionals | Science
http://science.sciencemag.org/content/early/2017/12/15/science.aao1733.full

Inner workings of victorious AI revealed by researchers: Libratus AI defeated top pros in 20 days of poker play -- ScienceDaily
https://www.sciencedaily.com/releases/2017/12/171218091001.htm

CMU team publishes paper on how their poker-playing AI beat the best humans | TribLIVE
http://triblive.com/business/technology/13087657-74/cmu-team-publishes-paper-on-how-their-poker-playing-ai-beat-the-best

囲碁や将棋と違い、カードゲームの「ポーカー」では相手の手札が公開されていない不完全な応報の中での戦いを強いられる「不完全情報ゲーム」であるため、ポーカーは一般的に最良の手を探し出すアルゴリズムの開発が難しいゲームとして知られています。そのため、AIの進化の尺度を示すものとしてポーカーは機能してきたという側面があり、人間のプロプレイヤーを破るという快挙をカーネギー・メロン大学で開発されたAI「Libratus」が成し遂げたことは、AI開発の歴史的偉業だとたたえられています。

人工知能と4人のプロとのポーカー対決は人工知能が完全勝利 - GIGAZINE

カーネギー・メロン大学のトーマス・サンドルム博士たちが、歴史的偉業から約11カ月たった2017年12月15日に、いかにしてポーカーで人間に打ち勝ったのかというLibratusの戦術について科学誌Scienceで論文を発表しました。

論文によると、Libratusが採った戦略は大きく3つのアプローチに分かれていました。まず最初のアプローチである第1のモジュールは、「ゲームの抽象化」と呼ばれる作業を行います。テキサス・ホールデムのポーカーでは、ゲームは「10の161乗」という膨大な数の分岐点が現れます。これは全宇宙の物質の数よりも多いというとてつもない数で、これらすべてを計算することは最新のコンピューターでもとうてい不可能です。そこで、より計算がやりやすいようにLibratusの第1モジュールではゲームを抽象化する作業を最初に行うそうです。例えば、「フラッシュ」という手はキングハイフラッシュやクイーンハイフラッシュなど複数の種類がありますが、これらをすべて同じ1つの手と考えるグループ化によって、考える手を少なくするのだとのこと。同様に、賭け金が100ドルの場合と101ドルの場合とで大きな違いがないことから、これらもグループ化して単純化されます。なお、この第1段階で行われる抽象化は、後のラウンドのための粗い戦略形成を行うため「blueprint(青写真)戦略」と名付けられています。

ゲームが後半に入ると、Libratusの第2モジュールはそれまでの小さな攻防(サブゲーム)でどのようにプレイしたかという情報から、より細かな戦略を立てることを始めます。最終盤に近づくまでに、Libratusはゲームがどのように進展してきたかに基づいて、第2段階の戦略をより洗練させていくとのこと。ポーカーではブラフなどを駆使して相手を揺さぶりますが、相手である人間のプレーヤーが抽象化されていない動きをするたびに、第2モジュールはサブゲームとして扱い計算し、別のモデルを組み立て戦略に組み込むという作業を行うそうです。

最終の第3モジュールは「自己改良」の工程で、青写真戦略をより強化します。ここで青写真戦略で抽象化するのに欠けていた「枝」を埋めるのだとのこと。しかし、この作業はすべて計算するには量が膨大すぎるため、人間の実際の行動を活用して、計算を単純化するそうです。「AIは機械学習を使って相手の戦略のミスを見つけて、それを利用する」のだとサンドルム博士は第3モジュールでの働きを説明しています。この青写真戦略における潜在的な穴を検出するために、相手の賭け金を分析しているそうです。

論文で解説されている内容は素人が理解するにはあまりにも難解ですが、3つの段階を経るというLibratusの戦略によって得られた結果は以下のグラフの通り。Libratus(赤色)は終始チップを失うことなく、中盤以降はグラフがほぼ直線を描くように一方的にチップを奪い続け、4人の人間のプロプレイヤーを完膚なきまでに打ち負かしています。