見出し画像

人工知能をめぐる動向

t endoh

探索木

探索木とは、要するに場合分けです。場合分けを続けていけば、いつか目的の条件に合致するものが出現するという考え方を基礎にしています。コンピュータは単純な作業が得意なので、いくらでも場合分けを行い、いつしか正解にたどり着 くわけです。

コンピュータは単純な作業が得意なため、探索木を使って様々な場合分けを行い、最終的に目的の条件に合致する解を見つけることができます。

探索アルゴリズムの種類

探索木に対して効率的に探索を行う方法には主に2つのアルゴリズムがあります。それらは幅優先探索と深さ優先探索です。

幅優先探索 (Breadth-First Search)

幅優先探索は、探索木の各要素（ノード）を出発点に近い順に検索するアルゴリズムです。この方法では、最短距離でゴールにたどり着く解を必ず見つけることができます。

例:

      A
     / \
    B   C
   / \ / \
  D  E F  G

幅優先探索では、上記の探索木に対して次の順序でノードを探索します: A, B, C, D, E, F, G

利点: 最短距離でゴールにたどり着く解を見つけることができます。

欠点: 探索の途中で立ち寄ったノードをすべて記憶しておかなければならないため、複雑な迷路になるとメモリ不足で処理を続行できなくなる可能性があります。

深さ優先探索 (Depth-First Search)

深さ優先探索は、探索木の各要素（ノード）を出発点から最も深い部分まで検索し、それから戻って次の最も深い部分を検索するアルゴリズムです。

例:

      A
     / \
    B   C
   / \ / \
  D  E F  G

深さ優先探索では、上記の探索木に対して次の順序でノードを探索します: A, B, D, E, C, F, G

利点: メモリ効率が良いため、より大規模な問題に対処できます。

欠点: 最短距離でゴールにたどり着く解を見つけることが保証されていません。また、解が見つからない場合や探索木が無限に広がる場合には、探索が終わらないことがあります。

決定木のまとめ

探索木は、問題の解決策や選択肢を表現するためのデータ構造で、コンピュータは探索木を用いて効率的に問題を解決することができます。幅優先探索と深さ優先探索は、探索木に対する代表的な探索アルゴリズムです。
幅優先探索は、最短距離でゴールにたどり着く解を見つけることができますが、メモリ効率が悪いという欠点があります。一方、深さ優先探索は、メモリ効率が良いものの、最短距離でゴールにたどり着く解が見つかることが保証されていません。どちらのアルゴリズムを選択するかは、問題の性質や要件に応じて適切に判断する必要があります。


深さ優先探索

深さ優先探索は、探索木を用いて問題を解決する際の一般的なアルゴリズムです。このアルゴリズムでは、あるノードから進める限り進んで行き止まりになったら一つ手前のノードに戻って探索を続けるという方法を繰り返します。

概要

深さ優先探索は、メモリ効率が良いという利点があります。探索が行き止まりになれば、一つ手前のノードに戻って探索を再開するため、メモリはあまり必要ありません。しかし、解が見つかったとしても、それが最短距離でゴールにたどり着く解であるとは限りません。また、運次第で探索が速く終わることもあれば、時間がかかることもあります。

例

例として、迷路の問題を考えてみましょう。幅優先探索では、ゴールにたどり着くのに11ステップかかります。一方で、深さ優先探索では、13ステップでゴールにたどり着くことが分かります。

一長一短

深さ優先探索と幅優先探索は、それぞれ長所と短所があります。実際の問題解決では、これら2つの良い点を組み合わせた方法や、特殊なケースに限って速く探索できる方法が求められることが多いです。そのため、深さ優先探索や幅優先探索の研究は古くから行われており、現在も続いています。

深さ優先探索まとめ

深さ優先探索は、探索木に対する一般的な探索アルゴリズムで、メモリ効率が良いという利点があります。しかし、最短距離でゴールにたどり着く解が見つかることが保証されていないため、問題の性質や要件に応じて適切なアルゴリズムを選択する必要があります。

ハノイの塔

ハノイの塔は古典的なパズルであり、探索木を用いて解くことができます。このパズルでは、3本のポールがあり、最初はすべて左側のポールに大きさの異なる複数の円盤が小さいものが上になるように順に積み重ねられています。円盤は一回に一枚ずつ別のポールに移動させることができますが、小さな円盤の上に大きな円盤を乗せることはできません。すべての円盤を右端のポールに移動できればパズルの完成です。

コンピュータに解かせるための準備

このパズルをコンピュータに解かせるためには、まずコンピュータが理解できる形式に問題を変換する必要があります。円盤に小さいものから順番に1、2、3と番号を振り、3本のポールの位置は左からP、Q、Rと名前を付けておきます。

ハノイの塔の状態の表現

ハノイの塔の状態は、3つの円盤がどのポールに置かれているのか、その位置を順番に並べることで表現できます。たとえば、すべての円盤がPの位置にある状態は(P,P,P)と表現できます。また、(P,R,Q)と表現された状態は、1番目の円盤がPの位置に、2番目の円盤の位置がRの位置に、3番目の円盤がQの位置にある状態を表しています。

探索木の作成

ハノイの塔は、探索木を使って表現できます。各ノードはパズルの状態を表し、エッジはルールに従った円盤の移動を示します。探索木を使ってすべての円盤を右端のポールに移動するパスを見つけることができます。

最短パスの選択

ハノイの塔の最短解は、すべての円盤を最小回数で右端のポールに移動させる方法です。探索木を用いて複数のパスを見つけることができますが、最短で移動させるには右端のパスを選択すればよいことが分かります。

ロボツトの行動計画

ロボットの行動計画は、探索を利用して作成できる技術で、プランニングと呼ばれています。古くから研究されており、ロボットやその他の環境要素を考慮して、あらゆる状態における行動計画を立てることができます。

探索空間

ロボット、部屋、ゴミなどを含む環境を一つの状態とし、状態間の遷移をロボットの行動とみなすことで、探索空間を構成します。これにより、ロボットが取り得る行動とその結果を表現し、最適な行動計画を立てることができます。

STRIPS

プランニングの研究では、前提条件、行動、結果という3つの組み合わせで記述するSTRIPS (Stanford Research Institute Problem Solver) が有名です。これにより、任意の状態に至る行動計画を効率的に立てることができます。

積み木の世界とSHRDLU

プランニングの研究には、積み木の世界を完全に実現する研究も行われました。SHRDLUは1968年から1970年にかけてテリー・ウィノグラードによって開発されたシステムで、英語による指示を受け付け、コンピュータ画面に描かれる「積み木の世界」に存在する様々な物体を動かすことができました。

この限定された世界では、自然な会話を通じてロボットとコミュニケーションが可能でした。この成果は後にCycプロジェクトにも引き継がれていきました。

テリー・ウィノグラードはその後、ヒューマン・コンピュータ・インタフェース（HCI）という研究分野に移り、Googleの創業者の1人、ラリー・ペイジを育てました。

ボードゲームと人工知能

ボードゲームの歴史的な出来事

2016年3月9日、囲碁の世界でトップレベルの実力者である韓国のプロ棋士に、DeepMind社が開発した人工知能の囲碁プログラムAlphaGoが4勝1敗と大きく勝ち越した歴史的な事件が起こりました。これにより、囲碁のような複雑なボードゲームでもAIが人間のトッププレイヤーに勝利する可能性が示されました。

ボードゲームの探索の基本

ボードゲームをコンピュータで解く基本は探索です。しかし、ボードゲームでは組み合わせの数が非常に多いため、すべての組み合わせを探索することは現実的には不可能です。そこで、効率的な探索方法が求められます。

コストとヒューリスティックな知識

効率的な探索を実現するために、コストの概念が導入されます。コストは、例えば時間や費用など、ある経路や交通手段を使った場合にかかる負担を表します。コストを計算することで、探索を短縮できます。

ヒューリスティックな知識は、探索を効率化するのに有効な経験的な知識を指します。多くの人工知能で扱う問題では、組み合わせの数が大きすぎて網羅的な探索では解決できないため、ヒューリスティックな知識の利用が重要になります。

対戦型ボードゲームの探索木

対戦型ボードゲームでは、相手がいるため、自分と相手が交互に手を指す探索木を作成する必要があります。各ノードはその時点でのゲーム盤の状態を表し、効率的に最良の手を探索できるように、それぞれの状態が自分にとって有利か不利かを示すスコア（コスト）を情報として保持させます。ゲーム盤の状態のスコア（コスト）の計算方法は事前に決めておき、駒の数や位置関係を元に計算するようにします。
AIの進歩は、近年急速に進んでおり、複雑なゲームでも人間のトッププレイヤーに対抗できるようになってきています。AlphaGoの勝利は、その象徴的な出来事であり、今後もボードゲームの分野で人工知能の研究がさらに進むことが期待されています。

人工知能と将棋・チェス

囲碁だけでなく、他のボードゲームでも人工知能が人間のプレイヤーに対抗できるようになっています。将棋やチェスでは、既にコンピュータが人間のトッププロと互角以上の実力を持っており、これらのゲームでも人工知能の進化が示されています。

ボードゲームと人工知能の今後

ボードゲームにおける人工知能の進化は、人間の思考や判断力を模倣し、さらには超越する可能性を示しています。ボードゲームは、論理的な思考や戦術的な判断が求められるため、人工知能の研究において重要な役割を果たしています。

今後は、ボードゲームだけでなく、さまざまな分野で人工知能が活躍することが期待されています。例えば、医療や金融、自動運転など、人間の専門家の判断力や知識が必要とされる分野で、人工知能がより効率的な解決策を提案することが可能になるでしょう。

また、人工知能がボードゲームで培ったヒューリスティックな知識や探索手法を、他の分野に応用することで、新たな発見や技術革新が生まれることが期待されています。ボードゲームの世界での人工知能の進化は、今後も私たちの暮らしに大きな影響を与え続けることでしょう。

ボードゲームの探索とMinMax法

ボードゲームにおいて、最適な戦略を立てるためには、さまざまな手を試行し、相手の反応に応じて最善の手を選ぶことが重要です。そのため、MinMax法やαβ法などの探索手法が非常に役立ちます。本記事では、ボードゲームの探索とMinMax法について詳しく解説します。

MinMax法とは？

MinMax法は、ボードゲームにおいて戦略を立てるための手法です。基本的な考え方は、自分が指すときにはスコアが最大（つまり自分が有利）になるように手を打ち、相手が指すときにはスコアが最小（つまり相手が有利＝自分が不利）になるように手を打つということを前提に戦略を立てます。これにより、自分が打つべき最適な手が決定されます。

MinMax法の例

例えば、ゲームの状態を三手先まで先読みした場合のMinMax法を考えてみましょう。まず、三手先のゲーム盤の状態のスコアをすべて求めます。そして、現時点まで遡って各ノードのスコアを決定することで、最終的に現時点で自分が打つべき手が確定します。

αβ法とは？

MinMax法による探索をできるだけ減らすために、αβ法という手法が用いられます。αβ法は、探索する必要のない枝を切り落としてしまうことで、探索量を減らす工夫を行います。

αカットは、最大のスコアを選択する過程でスコアが小さいノードが出現したら、その時点でそのノードを探索対象から外してしまうことです。一方、βカットは、スコアが最小のものを選ぶ過程で、すでに出現したスコアよりも大きいノードが現れた時点で、その先につながるノードの探索をやめてしまうことです。

モンテカルロ法

コンピュータの処理能力が飛躍的に向上したことで、囲碁や将棋 ソフト は近年 とても強くなっています。たとえば、第2回電王戦 に登場した
「GPS 将棋」は東京大学 にある670台のコンピュータ と接続して、
1秒間に3億手を読むといわれていたそうです。
しかしながら、どんなに工夫しても囲碁クラスのポードゲームになると、
探索するノード数 は膨大です。深く探索すればするほど望ましい結果を得 られますが、特にゲームの序盤はコンピュータのメモリや探索時間をいくら費やしても、また、どんなに効率よく探索しても全ての手を読み切ることはできません。ところが、ゲーム後半になると、碁石が打てる場所は 限られて くるため、コンピュータが ます ます有利になってい きます。
特に最終局面ではコンピュータはまずミスをしないため、人間がコンピュータ との対戦で勝つには序盤から中盤でいかに戦うかが重要にな ります。 しかしそれでも、旧来 の方式では、人間のプロレベルの棋士にコンピュータが勝つのは難しい状況で した。19×19の 囲碁 (19路盤)ではなく、 9×9の囲碁 (9路盤)ですらコンピュータが人間のアマチュア初段に勝つのは難しかったのです。9×9の囲碁の場合は、組み合わせの数はチェスよ り少ないので、コンピュータが人間に勝つのが難しいのは、探索しなければならない組み合わせの数が多いということだけでなく、ゲーム盤のスコア (コスト評価)に問題があるようだ とい うことが分かって きました。ある意味、このスコアがゲームの強さを決めるわけですから非常に重要になりますが、典型的な旧来の方式では、過去の膨大な戦歴を元に局面のスコア (コスト評価)を人間が決めていたのです。モンテカルロ法 とい う手法では、グームがある局面まで進んだら、あら か じめ決められた方法でゲームの局面のスコアを評価するとい う方法を完全に放棄してしまいます。その代わ り、どのようにスコアを評価するか というと、コンピュータが2人の仮想的なプレーヤーを演じて、完全 にランダムに手を指し続ける方法でゲームをシミュレーションし、とにか く終局させてしまうのです。このようにゲームを終局させることをプレイアウ トと呼びます。ある局面からプレイアウ トを複数回実行すると、どの方法が 一番勝率が高いか計算できるので、ゲームのスコアを評価できるのです。 ゲーム後半 は碁石が置ける場所が限定されるので、1秒間に数億手を読むことができるコンピュータであれば、ある局面から後のグームをランダ ムに指 してシミュレーションすることは実にたやすい作業です。モンテカルロ法の登場により、人間がスコアの付 け方を考えるよりも、とにかく数多く打つて最良のものを選ぶ という評価方法の方が優れていることが分かり、9× 9の 囲碁では人間のプロ棋士 とほぼ同じレベルになりました。 しかし19× 19の 囲碁では、やはり人間のプロ棋士 には全 く歯が立たな い状況が続 きました。モンテカルロ法 は素晴 らしい発明ですが、人間の思考方法 とは違ってブルー トフォース (力任せ)で押し切る方法なので、探索しなければならない組み合わせの数が増えると、立ち行かなくなるからです。 AlphaGoが 19× 19の 囲碁で人間のプロ棋士 に勝利したことがいかに画期的なことだったか分かるでしょう。その勝利の戦略はこれまでの方法とはまったく異なるものでした。AlphaGoは プルートフォース (力任せ)の 戦略ではな く、デ ィープラーニングの技術 を使って人間の思考方法 をコンピュータで実現し、人間のプロ棋士に勝利 したのです

この記事が気に入ったらサポートをしてみませんか？