【G検定】③ 第２章 人口知能をめぐる動向（１）探索・推論 ・・・「『宇宙の水素原子』を数えたほうがマシな世界」
２－１．探索・推論
「『宇宙の水素原子』を数えたほうがマシな世界」
あなたは「宇宙の水素原子が何個あるか？」ご存じでしょうか？
『10の80乗』だそうです。
「へぇ～」じゃなくて、続きがあります。
あなたは「囲碁の打ち手が何パターンあるか？」ご存じでしょうか？
『10の360乗』だそうです。
「えっ？はぁ？」じゃないですか？いや、衝撃的。
『ハチワンダイバー』という将棋棋士のマンガがあるんですが、主人公が「ダイブ！」ゆうて、将棋盤の中の『宇宙』に潜るという…（何ってるかわからんと思いますが）この将棋の打ち手パターンも『10の220乗』だそうです。当時は「またまた。大げさな。。」と思ってましたが、トンデモナイ。宇宙の水素原子、何回数えたらええねん。。棋士の世界が『宇宙規模』というのも納得です。
さて、先の章（【G検定】②）で「2015年 AlphaGOがプロ棋士に勝利」と紹介しましたが、これがトンデモナイ事というのが伝わりましたでしょうか？
ド文系脳で考えた場合「打ち手の全パターンを記憶して、勝つパターン選んだらええやん」とか簡単に言いそうな話ですが、理系脳の方からすれば「そりゃそーなんですがそんな簡単な話じゃないっちゅうねん！」という話。こういう構図・・・社会のそこら中にありそうですよね？AI開発の依頼事とかする時など特に。理系脳方々を無駄に疲弊させたりしないようにしたいものです。。自戒。
そんな宇宙規模の「探索・推論」を行う技術を、ギュッと数行に凝縮したカンペノートはこちら。まずは「こんな考え方で進化したのか～」程度でご確認を。
**********
２-１「探索、推論」
①迷路（探索木）
１）幅優先探索（左・右）・・・〇最短距離で解答・×メモリ不足あり得る
２）深さ優先探索（左・右）・・・〇メモリ軽い・×メチャクチャ時間かかるかも
分岐点のパターンを樹形図にして、それを幅で左優先（S→A→B→…）で探索したのが「幅・左優先探索」…言葉の通り。「深さ・右優先探索」だったら（S→B→A→…）となるだけ。
②ハノイの塔
１・２・３のリングをP・Q・Rの塔に移動させていった時のパターンを探索
③ロボットの行動計画（プランニング）
STRIPSは３つのステータス（前提・行動・結果）のパターンを探索してプランニング。
SHRDLUは空間上に「積み木」を配置し、それをロボットに指示（言語）出した時にロボットが可否を判断し、返答を返して実行するプログラム。→後に自然会話研究の「CYC（サイク）プロジェクト」へつながる
④オンボードゲーム
オセロ（10**60）<チェス（10**120）<将棋（10**220）<囲碁（10**360）
※10**60・・・「10の60乗」という意味
「網羅できるわけない！」→「そうだ『探索木』+『コスト』で負担減らそう」
・コスト…状態が「有利」か「不利か」の「スコア」を経験則からストックし、「次のスコア」を推論して、探索をできるだけ減らす。コスパ良い探索行うための概念。
・MIN-MAX法（+αβ法）…自分の手は「有利に」（それ以外を切る＝αカット）、相手の手は「（自分にとって）不利に」（それ以外を切る＝βカット）
・モンテカルロ法…完全ランダムで手を打ち、プレイアウト（勝ち負けつける）まで行う。その結果のパターンから最良のものを選ぶ。要するに力業。（パターン多すぎると使える方法ではない。。）
・「AlphaGO」はDNN（ディープニューラルネットワーク）とMCTS（モンテカルロ木探索）を用いて棋士に勝利
**********
個々の単語の詳細は、こちらのHPが親切丁寧なのでご参照を。
ここで特に重要（試験出る）なのは下記3点
１）①迷路の「幅・深さ」「左・右」優先のルールを理解する
２）オセロ～囲碁の難易度順番（パターン数までは覚えなくてもOK）
３）MIN-MAX法（+αβ法）の考え方。
探索の優先ルールはホント言葉通り『幅』なら1段目・2段目・3段目を『左優先』ならこっち向き『→』で調べる。だけ。『深さ』なら縦の経路をたどって、一番深いところまで行ったら、1個手前戻ってまた縦の経路をたどる。だけ。言葉が指す通り。でもなぜか混乱するので、自分で探索木を手で追ってみるのがオススメです。そのうえで「何でメモリを食うのか？」を考えてみるとわかりやすいかも。幅探索だったら探索した分は全部記憶しておかないとダメですもんね。深さ探索なら一旦最後まで探索し終えたのち、それが解でないなら忘れていけるメリットがあります。これはどちらが優劣という話ではなく、例えば作るプログラムが、スマホに載せるものなら、少ないメモリしかないので、時間かかっても深さ探索方法をチョイスせざるを得ない…というような話。
オセロ～囲碁は、間のチェス・将棋が特に問われるポイントですが、「チェスは1997年に『ディープブルー』byIBMが勝った。囲碁は2016年『AlphaGO』が勝った」という話を覚えておけば大丈夫かと。チェスと囲碁で20年近くかかったんすね…囲碁スゴ。。
MIN-MAX法とαβ法は、このサイトが有難いです。【G検定】Mini-Max法とαβ法～具体例でわかりやすい解説を試みてみた～ (pictblog.com)
ピクトの思考録・・・平成生まれでこの知識量？スゲー人が居るもんだわ。。ド文系で営業しかしたこと無い私からしたら「天才」にしか見えん。こういう人がゴロゴロしてる世界なんだから恐ろしい。。何で世に出てないのか？出てるのかな？先のAIZINもスゴイサイト。あんな解りやすく書かれてるサイト、あまりお見かけしない。
そういう「解りやすい」説明をしてくれる人やサイトだけを「探索・推論」出来るプログラムを是非作ってみたい。「解りやすさ」の定義が人によって異なるので難しそうだが、いつかチャレンジしてみたいものです。
