一口にポーカーといってもさまざまな種類があるが、このほど、最も一般的な種類のポーカーである「テキサス・ホールデム」を基本的に完全に攻略したコンピューター・アルゴリズムが開発された。このアルゴリズムを作成しScienceに報告した¹アルバータ大学（カナダ・エドモントン）のコンピューター科学者Michael Bowlingらは、「公正にゲームを行うかぎり、どんな相手にも負けることはありません」と言う。

この手のプログラムでは、1997年に当時のチェス世界チャンピオンGarry Kasparovを負かしたIBM社のチェス専用コンピューター「ディープ・ブルー」が有名だが、今回のアルゴリズムはその一歩先を行くものだ。Bowlingらが開発したポーカー・プログラムは、あらゆる意味で無敵のポーカー・プレーヤーである。

これまでに解かれた人気ゲームは他にもいくつかある。例えば2007年には、今回の論文の共同執筆者であるNeil Burchも含む、同大学コンピューター科学科の研究チームが、「チェッカー（またはドラフツ）」というゲームを解いた²。

けれどもポーカーは、チェッカーよりも解くのが難しい。チェスやチェッカーは、プレーヤーがゲーム中に起こった出来事と現在の状況を完全に把握している「完全情報ゲーム」であるのに対し、ポーカーは、プレーヤーが相手の手札などを完全には把握できない「不完全情報ゲーム」だからだ。不完全情報ゲームは、オークションや交渉において最適な戦略を見いだすなどの実用的な問題を含むため、特に経済学者やゲーム理論研究者の関心が高い。

後悔と成長

Bowlingらが今回取り組んだのは最も一般的な「テキサス・ホールデム」という最もよく遊ばれているタイプで、ゲームは「ヘッズアップ（プレーヤーは2人だけ）」、「リミット（賭け金の額および賭け金を上げる回数を固定）」という設定である。このヘッズアップ・リミットホールデム（HULHE）がとり得る状態は3.16×10¹⁷種類あり、プレーヤーが意思決定を行う必要がある点（意思決定点）は3.19×10¹⁴個である。

Bowlingらは、経験から学習することができ、1500ゲーム以上をプレーすることによりチャンピオンレベルの技術を身につけられるアルゴリズムを設計した。アルゴリズムは最初のうちはランダムに意思決定を行い、続いて、それぞれの意思決定がうまくいかなかった度合いに応じて「後悔値」をつけることにより自らを改訂していった。この手続き（procedure）は反事実的後悔値最小化（counterfactual regret minimization）と呼ばれ、2006年から毎年開催されているコンピューター・ポーカー年次競技会でも広く用いられている。

Bowlingらはこの手続きを改良した。訓練を始めたばかりの頃にアルゴリズムが失敗と評価した意思決定を後で再評価できるようにしたのだ。

さらにBowlingらは、重要な改良をもう1つ行った。大量の情報の扱い方だ。戦略を立ててプレーに用いるために必要な情報量は、262テラバイトにもなる。これだけ膨大な量になるとディスクストレージが必要になるため、アクセス速度が遅くなる。Bowlingらは、このデータ量をより扱いやすいよう11テラバイトまで減らすデータ圧縮法を考案し、ディスクストレージの利用による計算時間の増加量を5％にとどめたのである。

マンチェスター大学（英国）のコンピューター科学者Jonathan Shapiroは、「素晴らしいのは、反事実的後悔値アルゴリズムだけではありません。彼らは他にも極めて巧妙な工夫をしているのです」と評価する。

はったりを利かせる

Bowlingらのアルゴリズムは戦略の一環として、プレーにある程度のブラフ（はったり）を取り入れることを学習した。ブラフは、ポーカーの要素の中でも極めて人間的・心理的なもののように思われるが、実はゲーム理論の一部であり、コンピューター・ポーカーにもよく取り入れられている。「ブラフはゲームの数学から出てきます。最善の結果を得るためにはブラフを何回用いるべきかを計算できるのです」とBowlingは言う。

もちろん、このアルゴリズムが全てのゲームに勝つことができると数学的に保証することはできない。ポーカーの勝敗には、どんな手札が配られるかという偶然の要素が大きく影響するからだ。けれどもBowlingらは、このアルゴリズムが長期的には常に勝つことを実証した。

Bowlingは、自分たちの手法は、実生活にも役立つ可能性があると考えている。例えば、投資ポートフォリオの管理など、不完全情報しか与えられずに意思決定をしなければならない場面だ。研究チームは現在、糖尿病の専門家との協力により、この手法を医療に関する意思決定に適用することに注目している。

翻訳：三枝小夜子、要約：編集部