開閉ボタン
ユーザーメニュー
ユーザーメニューコンテンツ
ログイン

  • 会員限定
  • 2021/03/05

「全幅探索」「選択的探索」とは?チェス・囲碁・将棋に使われるAI技術の秘密

連載:図でわかる3分間AIキソ講座

人工知能(AI)の性能向上が一般に広く知られるようになったきっかけの1つはゲームにおける進歩でしょう。囲碁で人間に勝ったAlphaGoアルファ碁をはじめ、チェス、将棋、クイズと、さまざまなゲームでAIが人間に勝利するようになり、注目されるようになりました。こうしたゲームにおけるAIの進歩について、特に重要だった出来事や技術を解説していきます。

フリーライター 三津村直貴

フリーライター 三津村直貴

合同会社Noteip代表。ライター。米国の大学でコンピューターサイエンスを専攻し、卒業後は国内の一部上場企業でIT関連製品の企画・マーケティングなどに従事。退職後はライターとして書籍や記事の執筆、WEBコンテンツの制作に関わっている。人工知能の他に科学・IT・軍事・医療関連のトピックを扱っており、研究機関・大学における研究支援活動も行っている。著書『近未来のコア・テクノロジー(翔泳社)』『図解これだけは知っておきたいAIビジネス入門(成美堂)』、執筆協力『マンガでわかる人工知能(池田書店)』など。

画像
1997年、IBMの開発したチェス専用のコンピューター「ディープ・ブルー(Deep Blue)」が、当時のチェスの世界チャンピオンに勝利。この時、用いられていた技術は「全幅探索(ぜんぷくたんさく)」でした(後ほど詳しく説明します)


チェスで人間に勝利したAI技術:「全幅探索」

 最初に本格的な知能ゲームでAIが人間を破ったのはチェスのAIでした。

 1960年代にアマチュアを破り、1980 年代後半にはチェス専用のAIである「ディープ・ソート(Deep Thought)」がトップクラスのプロ(グランドマスター)を倒すまでになりました。そして1997年になるとIBMの「ディープ・ブルー(Deep Blue)」が、当時のチェスの世界チャンピオンであったガルリ・カスパロフ氏を倒すことになります。

 この一戦は「AIが人間を超えた瞬間」として、世界中に報道されました。このときディープ・ブルーでは、主に「全幅探索(ぜんぷくたんさく)」という可能性のある局面を片っ端から計算・検討するといったアプローチが用いられました。圧倒的な計算能力に物を言わせて勝利するという、ある意味プログラムらしいテクニックです。

 ただ、この手法は手数の多い、将棋や囲碁などのゲームでは探索しきれず、人間に勝てるレベルには達していませんでした。

将棋・囲碁に使われたAI技術:「選択的探索」

 将棋や囲碁のAIでは、全幅探索のような強引な手法が使えなかったため、当初は「選択的探索」という、局面ごとに次の手を絞り込みながら探索する手法を用いていました。しかし、人間が設定する「絞り込み方」次第で性能が変動してしまうため、この手法を用いたAIは、安定した能力を発揮できませんでした。

画像
局面ごとに次の手を絞り込みながら探索する「選択的探索」と呼ばれる手法

 ところが、将棋ソフトの「ボナンザ(Bonanza)」が全幅探索で大きな成果を挙げることに成功します。

 ボナンザは普通に全幅探索するのではなく、機械学習を用いて局面を評価する能力を向上させる仕組みを備えていました。全幅探索によりすべての局面を計算しきれなかったとしても、局面を正しく評価する能力さえあれば、どの手が優勢になるのか判断できるようになります。さらに、囲碁の世界でも、機械学習と確率論を組み合わせたような手法が取り入れられ、急速に実力を伸ばしていきました。

 その後、「ディープラーニング」と呼ばれるアプローチが登場し、機械学習の性能が飛躍的に進歩すると、さまざまな対戦ソフトウェアが登場し、トップレベルの将棋や囲碁のプレイヤーがAIに敗れるようになりました。チェス、将棋、囲碁において「AIに勝つのは人間でも難しい」という認識は、すでに各業界で共通のものになっています。

「完全情報ゲーム」と「不完全情報ゲーム」

 高い計算能力による「探索」と機械学習を用いた「局面評価」を使った手法は非常に強力ですが、これだけで戦えるのは「完全情報ゲーム」と呼ばれるすべての手順が見えている不確定要素のないゲームの場合だけです。

 一方で、相手の手札が分からないポーカーや麻雀、一部のテレビゲームのような不確定要素の存在するゲームは「不完全情報ゲーム」と呼ばれており、探索や評価を行おうにも不確定要素の影響で運の要素に振り回され、探索と評価だけでは勝てません。

 また、私たちが日々行っている活動も、それぞれの目的を達成するゲームの一種だと考えれば、仕事、スポーツ、料理など、その活動のほとんどが体調や思惑、素材や部品の品質といったコントロールできない“不確定要素”に満ちている不完全情報ゲームと言えます。こうしたゲームで有効な判断ができなければ、AIは人間の代わりにはなりません。

【次ページ】「不完全情報ゲーム」でもAIが勝利、凄すぎるその手法とは

お勧め記事

AI・人工知能・機械学習 ジャンルのトピックス

AI・人工知能・機械学習 ジャンルのIT導入支援情報

ビジネス+IT 会員登録で、会員限定コンテンツやメルマガを購読可能、スペシャルセミナーにもご招待!