DeepStack

DeepStack（ディープスタック）は、2人用ポーカー、特にヘッズアップ・ノーリミット・テキサス・ホールデムをプレイするために設計された人工知能プログラムである。本作は、このゲームにおいて人間のプロを凌駕した最初のコンピュータプログラムである。

背景 ポーカーは学術界における重要なベンチマークゲームであり、最悪の敵に対する最適戦略を見出すために膨大な研究が行われてきた。

チェスのような完全情報ゲームでは、数十年前に人間のプロが追い越されたが、不完全情報ゲームはより複雑な再帰的推論を必要とする。

以前の一般的なアプローチは、主に抽象化を用いてゲームを簡略化することに依存していた。しかし、不完全情報ゲームにおける抽象化は、しばしば付け入る隙の大きい戦略を生み出す。 代わりに、DeepStackはニューラルネットワークの使用や継続的再解決（continual resolving）といったいくつかのアルゴリズムの革新を利用している。

本プログラムは、カレル大学、チェコ工科大学、アルバータ大学の国際チームによって開発された。

アルゴリズム プログラムの中核は、特定のカードの組み合わせの価値を決定するためのニューラルネットワークの使用にある。

ネットワークは少数のゲーム状態のみで学習され、学習中には見られなかった状況へと一般化するために使用される。

本プログラムは、ニューラルネットワークを用いた探索と継続的再解決を使用し、各ステップで見出された戦略が前のステップで使用された戦略と一貫していることを保証する。

探索手順では、反実仮想後悔最小化（CFR）を用いて先読みツリーの戦略を反復的に更新し、ニューラルネットワークを末端ノードの評価に使用する。

末端ノードの評価では、ある一定の深さ以降の計算を高速な近似推定に置き換えることで、ゲームの残り全体についての推論を回避している。

2016年のプロプレイヤーとのトーナメント 2016年12月に完了した研究において、DeepStackは4万4,000ハンドのポーカーをプレイし、11人のプロポーカープレイヤーを破った。全ゲームを通じて、DeepStackは100ハンドあたり49ビッグブラインド（bb/100）を獲得し（常にフォールドした場合は75 bb/100の損失となる）、ゼロから4標準偏差以上の差をつけた。これにより、ヘッズアップ・ノーリミット・テキサス・ホールデムにおいてプロプレイヤーを破った最初のコンピュータプログラムとなった。

競合アプローチ DeepStackと同時期に、カーネギーメロン大学の研究グループから、Libratus（リブラトゥス）と呼ばれる競合アプローチが発表された。2017年1月11日から31日にかけて、Libratusは4人のトップクラスの人間ポーカープレイヤーとのトーナメントに投入された。そのアルゴリズムもScience誌に掲載された。Libratusは末端ノードの評価にニューラルネットワークを使用していない。専門家は、DeepStackが行ったようなニューラルネットワークを用いた学習の方がより汎用的であると主張しており、実際に他の不完全情報ゲームへと一般化するその後の研究でも利用されている。

ポーカーコミュニティによる反応 456ハンドをプレイしたアイルランドのプロポーカープレイヤーであるダラ・オカーニーは、DeepStackがゲーム理論に基づいた、一部の人間プレイヤーが使用するスタイルに似たスタイルでプレイしたと述べた。

脚注

関連項目 Cepheus Claudico Libratus Polaris (ポーカーAI) Pluribus (ポーカーAI)