ゲームがAI研究の2つの学校の背後にある原動力になった方法

今日、世界は深層学習とニューラルネットワークに基づくAIによって嵐に巻き込まれています。ただし、Webサーフィンと運転ルートを管理するアルゴリズムの多くははるかに古く、1950年代から1990年代後半までAIの主なタイプであった「シンボリック」人工知能としても知られるいわゆる「古き良きAI」にルーツがあります。 ..。深い学習による象徴的なAIの影は、人工知能の歴史における2つの主要なマイルストーンによって示されます。それぞれのマイルストーンは、最高の人間プレーヤーに対するAIシステムの勝利に関連しています。





^{世界チャンピオンのGarryKasparovは1996年にIBMDeep Blueコンピューターを破りましたが、1997年に敗北し、4-2で敗れました。}



1997年にグランドマスターで世界チャンピオンのギャリーカスパロフにIBMディープブルーコンピューターが勝利したことは、月への着陸に匹敵する、テクノロジーの歴史における勝利の分水嶺と見なされています。彼女は、コンピューターが私たちに固有であると考えられていたもの、つまり思考^1で人間を打ち負かすことができることを示したようです。 DeepBlueコンピューターで使用されているシンボリックAIテクノロジーは、特に25、000年前に中国で発明されたgoのようなより複雑なゲームでは、現在では廃止されていると見なされています。しかし、2016年、世界ゴーチャンピオンのリーセドルはGoogleのDeepMind AlphaGoAIシステムに敗れました。研究者でベンチャーキャピタリストのLiKaifuは、このイベントを中国の「スプートニクモーメント」と呼んだ²：彼は、中国が米国に追いつき、おそらく米国を超えるために、AI研究に数十億ドルを投資するように促したのはこのためだと信じています。 AlphaGoの勝利は、現代のAI革命の中心にある新しいAIパラダイム（深層学習とニューラルネットワーク）の繁栄を示しています。



なぜチェスのようなゲームがAIの歴史の中でそれほど重要になったのですか？ハーバート・サイモン、アレン・ニューウェル、ジョン・マッカーシー、マーヴィン・ミンスキーなどの人工知能研究の先駆者たちは、アリストトルが基礎を築いた西洋哲学の伝統的なプリズムを通して人間の知能を見ました。カルテシアンの心と体の分裂に根ざした、この男性的でユーロ中心の知性の見方は、論理、数学、そして身体的、感情的、社会的、文化的な形の知性を犠牲にして問題を解決する能力など、脳のスキルを優先しました。彼らは、理由（つまりロジック）が人間と獣を区別する場合、インテリジェンスの基礎となるのはロジックであると信じていました。





ブレイズパスカルは哲学者であり数学者でした。1640年代に、彼は、徴税人である父親を助けるために追加を実行できる機械を発明しました。



BlaisePascalからGeorgeBoole、Bertrand Russellに至るまで、多くの西洋の哲学者や数学者は、思考自体と同等の計算/論理を作成するか、数学的に厳密に（より「正式に」）、または次のステップに進むか、それを機械化しようと努めてきました。パスカル自身がこの目的のために計算機を作りました、そしてこの西洋思想の衝動の集大成は20世紀のデジタルコンピュータの発明でした。 1950年代と1960年代のAI研究の先駆者たちは、ゲームを人間が問題を解決することによって知性を実証するための別の方法と見なしていました。 AIの研究者がプレイヤーのやり方をシミュレートできれば、このプロセスを自動化できます。経済学と軍事に適用されるゲーム理論と呼ばれる数学の分野は、数学者でありコンピューターのパイオニアであるジョン・フォン・ノイマンによって設立されました。コンピュータサイエンスで広く使用されている戦略とアルゴリズムの最適化を提供しました。 AIのパイオニアであるハーバートサイモンは、これらの理論をコンピューターサイエンスと経済学の両方に適用しました（彼はノーベル賞を受賞しました）。したがって、ゲームが現実世界の側面を真剣にモデル化できるという考えは、コンピューターサイエンスの初期の中心でした。特に、初期のコンピューターでは現実世界の複雑さをシミュレートすることが困難であったため、ゲームは単純化された「マイクロワールド」と見なされ、その制限とルールは1960年代に急速な進歩を可能にしたコンピューターによって十分に理解されていました。したがって、ゲームが現実世界の側面を真剣にモデル化できるという考えは、コンピューターサイエンスの初期の中心でした。特に、初期のコンピューターでは現実世界の複雑さをシミュレートすることが困難であったため、ゲームは単純化された「マイクロワールド」と見なされ、その制限とルールは1960年代に急速な進歩を可能にしたコンピューターによって十分に理解されていました。したがって、ゲームが現実世界の側面を真剣にモデル化できるという考えは、コンピューターサイエンスの初期の中心でした。特に、初期のコンピューターは現実世界の複雑さをシミュレートするのが困難であったため、ゲームは単純化された「マイクロワールド」と見なされ、その制限とルールは1960年代に急速な進歩を可能にしたコンピューターによって十分に理解されていました。





Wolfgang von KempelenのTurokチェスマシンは、中に隠された生きているプレーヤーによって制御されています。



特にチェスは、歴史的に西洋における知的活動の頂点と見なされてきました。それは論理と戦略に関連した知的ゲームでした。スタートレックのスポック氏のことを考えてみてください3Dチェスで人間のプレイヤーを倒します。 18世紀でさえ、ヨーロッパのエリートはチェスをすることができる機械のアイデアに魅了されました。 Wolfgang von Kempelenは、オーストリア皇后マリアテレサのために作られたチェスマシンである「MechanicalTurk」で有名になり、ベンジャミンフランクリンとナポレオンを破りました。その後、「Turk」は偽物であり、ライブプレーヤーがその中に隠れていたことが判明しました。それにもかかわらず、彼はエドガー・アラン・ポーとチャールズ・バベッジの想像力をかき立てました。インテリジェンスの指標としてのチェスへの関心は、20世紀に計算理論を打ち立てた数学者、アランチューリング、クロードシャノン、ジョンフォンノイマン、ノーバートウィーナー、そしてもちろん、AIハーバートサイモン、アレンニューウェル、ジョンマッカーシーの先駆者にまで及びました。特に、NewellとSimonは、チェスをAIのモデルチャレンジと見なしました。彼らの好ましい解決策に最適です：検索。





1947 .





MIT Bell Labs () 1950 , . MIT ( ). (. 1950 ).





, , 1980 .

検索とは何ですか？チェスをプレイするときにどのように使用できますか？ AIのコンテキストでは、検索はGoogleを使用してWeb上のテキストを検索することを意味しません（ただし、Web検索エンジンはAIのコンテキストで検索の概念を使用できます）。 AIでは、検索とは、問題の考えられる解決策をたどる際の試行錯誤のプロセスを指します。検索は、「シンボリック」AIとしても知られる古典的なAIの基本的な方法の1つです。このような方法では、代数的問題の解決など、シンボルのリストを操作する必要があるためです。定理の証明、パズルの解決、ゲーム、迷路の解決など、あらゆる種類の問題解決プロセスには、最初に何を試すかを決定することが含まれます。これらの選択肢は、分岐決定ツリーとしてモデル化できます。





.

-. , , - «».



迷路から抜け出す方法を探すロボットマウスを作成する必要があるとしましょう（おおよそ1950年にClaude Shannonが行ったこと）。彼女が4つのドアのある交差点にぶつかった場合、彼女は右、前、左に移動できますが、戻ることは禁じられています。これにより、3つの選択肢があります。コンピュータ科学者は、マウスの「分岐係数」は3であると言うでしょう。迷路を通り抜ける（解決する）ようにコンピュータをプログラムする最も簡単な方法は、各オプションまたは分岐を順番にチェックすることです。これはブルートフォースサーチと呼ばれます。すべてのバリエーションをテストします。ただし、もちろん、マウスは、最初の交差点で他のすべてのオプションをチェックするために戻る機会が与えられる前に、もう1つの交差点に移動します。彼女が新しい交差点に到達するたびにマウスはさらに3つの新しいパスから選択できます。戻って別のパスを試す前に、マウスが詳細に検索できる交差点の数を設定できます。





クロードシャノンは迷路の中で彼の電気マウスを動かします（1952年頃）。



これは検索深度と呼ばれ、ゲームのコンテキストでは「先読み」です。ご覧のとおり、マウスで検索する必要のあるパスの数は非常に急速に増加します。たとえば、3（分岐係数）のように、意思決定ツリーを事前にチェックする回数だけそれ自体が乗算されます。言い換えれば、問題は指数関数的に増大しています。AI業界では、これは「コンビナトリアル爆発」問題と呼ばれることがよくあります。

初期の理論におけるチェス盤

同様の方法をチェスでも使用できます。各プレーヤーの動きで、最大38の可能な動きを選択できます。つまり、チェスの問題の分岐係数は38です。これらの38の動きの中で最良のものを選択するには、定量的な方法を使用して、あるチェスの位置が別の位置に与える相対的な利点を評価します。これを「スコアリング機能」といいます。平均的なチェスゲームは、42点の移動を取り、2人の選手があるので、このニーズは、私たちに約38与える、2倍される⁸⁴ -宇宙の星の数よりも多くを。 AIの歴史の初期段階でさえ、チェスやその他のタスクのブルートフォース検索によるそのような検索は、当時の機器では機能しないことが明らかになりました。オプションが多すぎて、コンピューターが弱すぎます。クロードシャノンは、アルゴリズムを最初に使用した人の1人でした。minimax "コンピュータチェスプログラム（このアルゴリズムは今でもほとんどのチェスプログラムの基礎です）で、ゲームでの人間の知識と経験のおかげで、多くの枝を見なくてもすぐに切断できることに気づきました。ハーバートサイモンとアレンニューウェルは「ヒューリスティック」を使用することを提案しました。人間が問題を解決するときに部分的に使用する大まかなルールは、ほとんどの場合機能しますが、常に発生するとは限りません。ヒューリスティックは、コンピューターにプログラムできる人間の知識の一種です。

チェス

Chessの決定ツリーには、tic-tac-toeよりもはるかに多くのブランチがあります。チェスゲームの変異体の数は10にほぼ等しいと計算された¹²⁰以上の宇宙における原子の数よりも、。

有界先読み

ブランチの数が非常に多いため、チェスプログラムは検索ツリーを有限の深さまでしか見ることができません。そうしないと、検索は永遠に続きます。



チェスで役立つことが証明されているそのようなヒューリスティックの1つは、「アルファ-ベータカットオフ」です。"。これは、いずれかの動きが敵によって簡単に打ち消されるとプログラムが判断した場合、同じ動きを打ち消すことができる他の方法を探す必要がないことを意味します。このパスに沿ったそれ以上の検索は無視して、この枝全体をツリーから切り離すことができます。これにより、分岐係数を38から6に、場合によっては3に大幅に減らすことができます。さらに、当時のコンピューターの制限を考えると、ほとんどのプログラムは4手先しか見ることができませんでした。は、1959年から1962年頃に、MITの学生であるAlan KotokによってJohnMcCarthyの指導の下で作成されました。Kotoka-McCarthyプログラムでは、アルファベータクリッピングを使用しました。





, IBM 7090 . , - . 1967 , , 3-1 .

1959 MIT , . , , . . 1962 .



NewellとSimonは、チェスなどのすべてのAIの問題は、ヒューリスティックと組み合わせた検索、つまり「ヒューリスティック検索」によって解決できると考えていました。ヒューリスティック検索は、ニューウェルとサイモンの初期のブレークスルーである論理理論家と一般問題解決者の背後にある中心的なアイデアであり、人間と機械の両方のインテリジェンスはシンボルの単純な操作、つまり基本的な構成要素にあるという彼らの理論の重要な柱になりました。数学と言語。この「物理的シンボルシステム」仮説は、1950年代の開始から2000年代初頭まで、シンボリック人工知能プロジェクト全体の基礎となった前提となりました。コンピュータと人間の「脳」の同等性を仮定したこの理論は、認知心理学において非常に影響力を持つようになりました。その後、サイバーパンクのジャンルの作品のおかげで人気のある文化になりました。そこでは、人々は自分の頭脳をインターネットにアップロードしたり、チップに置き換えたりすることができました。





() , -, Logic Theorist, General Problem Solver NSS ( --). JOHNNIAC RAND.



コンピューターはより高速になり、RichardGreenblattやHansBerlinerなどの経験豊富なチェスプレーヤーであるコンピューター科学者が独自のチェスプログラムを作成しました。彼らは、最初のチェスプログラム（Kotokによって書かれたものなど）のプレイが非常に悪いことを発見し、ライブプレーヤーがどのようにゲームにアプローチするかについての独自の知識をプログラムに追加しました。この知識は、ピースの位置の推定、オープニングムーブとエンドゲームのデータベース、および競技場のパターンの認識を改善するための追加のヒューリスティックの形を取りました。しかし、時間の経過とともに、より高速なコンピューターや特殊な機器で実行されるチェスプログラムは、大量の人間の知識が組み込まれているプログラムよりもパフォーマンスが優れていることが明らかになりました。これは、完璧なヒューリスティックがなく、すべての状況を説明できるわけではないために発生しました。プレイヤーがほとんどの人が悪い動きだと思うようなことをしようとしているために、巧妙な動きが生じることがあります。ほとんどのヒューリスティックは、それ以上検索せずにそのような動きを遮断します。つまり、人間の知識を使用するプログラムがそのような動きをすることは決してありません。





ハンス・ベルリナー（背景）、マレー・キャンベル（左）、およびネバダ州リノで開催された第20回ACMコンピューターチェス選手権でのフェン・シオン・シュー。 1位は、HiTech（Berlinerのチーム）とDeep Thought（CampbellとXuのチーム）の2つのチームによって共有されました。どちらもカーネギーメロン大学を代表していました。 Deep Thoughtチームの3人のメンバー（CampbellとXuを含む）は、後にIBMに雇われてDeepBlueを作成しました。



コンピューターの速度が上がるにつれ、6、7、8ムーブというより深く先を見据えることができ、4ムーブだけ先を予測していたプログラムを簡単に打ち負かすことができました。 「反復深化検索」と呼ばれる、より効率的な検索アルゴリズムが発見されました。彼は、最も有望に見えるパスに沿って検索の深さを徐々に増やすことができました。 Chess4.5で最初に使用されました。³ DavidSlateとLarryAtkins-1976年のヒューマンチェストーナメントで優勝した最初のプログラム。メモリ容量の増加により、プログラムは以前にレビューした位置を保持できるようになり、必要な検索の量がさらに削減されました。これらの革新（アルファベータプルーニング、反復深化、検証済みの位置の保存、オープニングとエンドゲームのデータベース）はすべて、コンピューターチェストーナメントのチェスプログラムの開発者によって自由に交換されたため、標準的な手法になりました。





1977年、Ken Thompson（Unixオペレーティングシステムの共同発明者としてよく知られています）とBellLaboratoriesのJoeCondonが、特殊なチェスマシンであるBelleを設計しました。ベルの専用チェス機器とエンドゲームデータベースは、コンピューターチェスに革命をもたらしました。





Belle 13- . Belle , Cray Blitz. 1970 1994 (Association for Computing Machinery, ACM) .





1980- Belle, Bell Labs, . Belle CHAOS WCCC 1980 , , . Belle CHAOS .





Belle Chess 4.0 4- (WCCC), - 1983 . : , . : Chess . Cray Blitz, Bebe.



ソフトウェアの進歩にもかかわらず、1970年代のコンピューターの速度の向上に伴い、チェスプログラムはソフトウェアの革新なしに自動的に改善されました。 1980年代までに、コンピューターチェスの進歩の主な要因は、検索を高速化するためのハードウェアの使用でした。それらは、AIの課題ではなく、コンピューター設計の課題になっています。 1997年、ディープブルーは、20年前のチェスプログラムとほぼ同じプログラミング手法を使用していました。しかし、彼は主に多くの特殊な並列プロセッサを備えた高速コンピュータであったため、Kasparovを打ち負かすことができました。ある意味で、コンピューターの速度が上がるにつれて、チェスプログラムのインテリジェント性は低下しました。





Deep Thought I, 1988 . Deep Thought, — , Deep Blue.





Deep Blue.





IBM Deep Blue ( , , , , . . ).





1997 Deep Blue (-).



1980年代には、AI研究の主要なトピックとしての深度優先検索はすでに衰退していました。1960年代から、スタンフォードのEd Feigenbaumなどの研究者は、いわゆる「エキスパートシステム」を作成しました。このシステムでは、大量の人間のエキスパート知識がif-thenルールの形でAIプログラムに注ぎ込まれました。最初のヒューリスティックプログラムの場合と同様に、これらのルールはソフトウェアコードにプログラムされましたが、ヒューリスティックシステムとは異なり、「ナレッジベース」はプログラムの論理部分（「推論マシン」）から分離されていました。フェイゲンバウムと他の専門家システムの支持者は、「知識は力である」と主張した。言い換えれば、彼らは、大規模な知識ベースが複雑な推論の欠如を補うと信じていました：知識が多いほど、検索が少なくなり、逆もまた同様です。

檻の中の虎：知識ベースシステムの適用、エドワード・フェイゲンバウムによる講演、1993年

AAAI-17でのAIの歴史に関する議論：エキスパートシステム、2017年

1980年代に、専門家システムが多くの商業企業を生み出しました。このすべての活動は、当時は別の方向に展開されていたチェスプログラムにほとんど影響を与えませんでした。特殊な機器の助けを借りてブルートフォース検索に戻りました。このタイプの主要なチェスマシンは、KenThompsonのBelleof Bell Labsと、2つの別々のCarnegie Mellon Universityプロジェクトでした。HansBerlinerのHiTechとFengXiong Xu、およびMurrayCampbellのDeepThoughtで、後にIBMのDeepBlueに進化しました。つまり、マシンがカスパロフを打ち負かすまでに、チェスプログラムは、優れた広告を提供したものの、AI研究の一般的な分野との関連性を実質的に失っていました。



しかし、さらに厄介なのは、1990年代初頭までにニューウェルとサイモンの物理的なシンボル仮説に基づいたシンボリックAIプロジェクトへの攻撃でした。彼の批評家、特に哲学者のヒューバート・ドレイファスは、1960年代に象徴的なAIのプロジェクトに疑問を呈し始め、脳と体の分離の哲学的な仮定は正しくなく時代遅れであると主張しました。マーティン・ハイデガーのような20世紀の哲学者は、人間の思考は、身体的経験と主題の直接の文化的環境から切り離すことはできないと主張しました。



AIの研究者は、ドレイファスの批判に非常に鋭敏に反応しました（彼自身は特に外交的ではありませんでしたが）。AIの分野の主要な当局は、ドレイファスの作品を発表したときにジャーナルを脅かしました。チェスがあまり得意ではなかったドレイファスがリチャード・グリーンブラットのマックハックチェスプログラムに敗れたとき、彼らは栄光を放った。しかし、チェスプログラムの成功は、ドレイファスの批判が間違っていたことを証明しませんでした。実際、ディープブルーのようなチェスプログラムがブルートフォース検索を使用したという事実は、それらがより大きな汎用AIプロジェクトで特別な役割を果たしていないことを意味しました。カスパロフの雷のような敗北のドラマは、マシーンズ・オーバー・マンの勝利のマイルストーンとして歓迎されましたが、実際には、1人のチェスプレーヤーに対するディープブルーのエンジニアの勝利でした。そして、ディープブルーの作成者は主張しませんでした彼らのコンピューターはインテリジェントだった。彼らは言った：もし建物で火事が始まったら、カスパロフは逃げるのに十分賢く、車はその場にとどまるだろう。以前はAIのパイオニアであるジョンマッカーシーはチェスをAIの主な目標と考えていましたが、ディープブルーの勝利後、人間の知性を模倣する方法に関する単一の新しい理論を開発できなかったという事実についてチェスを批判しました。





メディアは、世界のチェスチャンピオンであるギャリー・カスパロフと特殊なスーパーコンピューターであるIBMディープブルーとの間の1997年のリプレイを、人と機械の戦いとして描写しました。ニュースウィークの表紙で、彼女は「脳の最後の防衛線」と呼ばれていました。このような見方は、コンピューターの能力を誇張し、マシン自体を構築する人々の労力を最小限に抑えました。



1990年代初頭までに、研究者たちはドレイファスの批判を真剣に受け止め始め、ロドニーブルックスロボット^4のように、体を強調するものなど、新しい種類のAIを考案し始めました。、または感情を扱うもの。この記事の後半で説明するように、2000年代には、機械学習と呼ばれるまったく異なるAIの伝統が象徴的なAIに取って代わり始めました。機械学習は、顔の認識や人間の会話の理解など、シンボリックAIが人間よりも優れたタスクを実行することはできません。同じことが、マシンがヒューリスティック検索と競合してプレイできないゲーム、つまりgoにも当てはまりました。



ただし、検索は主要なAI手法としての優れた機能を失っていますが、コンピューターサイエンスの幅広い分野での有用性を失ったことはありません。最適かつ効率的な問題解決のための検索アルゴリズムの改善において、大きな進歩が見られました。この手法は非常に基本的であるため、決定ツリーの作成と検索は非常に広く行われています。それを使用するすべてのプログラムをリストすることはほとんど不可能です。



検索は、データベースに対するクエリの実行からWebの検索まで、情報を取得するあらゆるタスクで役割を果たします。Shakeyロボット用に最初に発明された*検索アルゴリズムSRIは、自律車両ルーティングおよびGPSアプリケーションに広く使用されています。そして今日でも、機械学習を使用してゲームをプレイするAIプログラムは、それらの最も興味深いコンポーネントではなくなったとしても、さまざまなタイプの検索を使用します。ただし、「人工インテリジェンス」と見なされていた他の手法と同様に、最新の検索は、通常のプログラムほどインテリジェントではない、単なる別の基本的なコンピューター手法と見なされます。これは、AI開発の歴史的なパターンを示しています。標準的かつ自動になると、人々はそれを「インテリジェンス」とは見なしなくなります。以前、「AI」について話したとき、それらはおそらく検索を意味していました。今日「AI」と呼ばれる場合、それは通常、シンボリックAIの後継である機械学習を指すことを意味します。



この記事の第2部では、人工知能における機械学習革命、深層学習と検索およびシンボリックAIの違いの深さ、DeepMindのAlphaGoが深層学習を使用してWorldGoチャンピオンのLeeSedolを倒した方法について説明します。

ノート

1. Nathan Ensmenger、「チェスは人工知能のドロソフィラですか？アルゴリズムの社会史」、社会科学研究42、no。 1（2012年2月）：22、https：//doi.org/10.1177/0306312711424596。



2. Kai-Fu Lee、AI超大国：中国、シリコンバレー、および新世界秩序。（ボストン;ニューヨーク：ホートンミフリンハーコート、2019）、1-5。



3. Stuart J.RussellおよびPeterNorvig 、Artificial Intelligence：A Modern Approach、第3版、Prentice Hall Series in Artificial Intelligence（Upper Saddle River、NJ：Pentice Hall、2010）、110。4。RodneyA



. Brooks、「象はチェスをしません」ロボティクスと自律システム、自律エージェントの設計、6、いいえ。1（1990年6月1日）：3-15、https：//doi.org/10.1016/S0921-8890（05）80025-9。

---

広告

LinuxまたはWindowsでインスタントアクティベーションを備えたサーバー が機能する必要がある場合は、間違いなく私たちのところに来てください-サーバーは支払い後1分で機能する準備ができています！