巡回セールスマン問題の解法のアルゴリズム
１． 初めに
・2019/03/30 巡回セールスマン問題と凸図形の関係
・2019/04/06 巡回セールスマン問題をモンテカルロ木探索で解く
上の2つの記事を元にして平面ＴＳＰのアルゴリズムを組みたいと思います。
２． 入力データ
#define NN nnxx
ｌｏｎｇ ｎｎ・・・ノードの点数
ｄｏｕｂｌｅ pp（NN，NN）・・・ノードの座標
ノードのＩＤは、配列の添え数と同じにします。
筆者の流儀として、変数名は2文字以上としています。
なお、ノード間の移動コストは、直線距離として求めます。
３． 初期処理
すべての線分の情報を取得します。
３．１ 線分情報
LINEAR line(NN*NN/2)・・・線分の情報（実際の線分数はｎｎ*（ｎｎ－１）/2になります。）
struct LINEAR{
long ltype・・・通常０：ｘ軸と並行１：ｙ軸と並行２
double apara・・・ｙ＝ａｘ＋ｂのときのａ
double bpara・・・ｙ＝ａｘ＋ｂのときのｂ
double dist・・・・・距離
}
ノードＩＤp1とp2からなる線分のLINEAR line(）の添え数を(p1-1)*nn+p2-1とします。
３．２ 交点情報
long pcross(NN*NN/2,NN*NN/2)・・・交点が存在しない０：両線分内で交点を持つ１：パス候補（wpath）線分外で交点を持ち、もう一方の線分内で交点を持つ２：その他０
① 実装メモリに余裕のあるとき＆実行速度を速くしたとき、交点情報を初期段階で処理します。
② 実装メモリに余裕がないときは、必要なとき随時交点情報を計算します。
③ 必要な交点情報だけを保持する方法もあります（凸図形内に交点が存在しない０を情報として持たない）が、アルゴリズムが複雑になるので割愛します。
３．３ Ｌ集合とＲ集合
long lrset(NN*NN/2,NN*NN/2)・・・Ｌ集合またはＲ集合が０の時⇒０：Ｌ集合とＲ集合の両方が１以上⇒１
４． 核となるアルゴリズム
① 任意のノードを木構造の頂点とします。例えば、プログラム実装時は添え数０＝pp(0,0)です。
そして、このノードＩＤを始点として作業用パス変数long wpath(NN)に投入します。
つまり、wpath(0)=頂点（始点）ノードＩＤです。
さらに、層ポインタを1つ増やします。long lvpos=0⇒lvpos++
② 第2層のノードを配列に保持します。
long p2(NN)・・・第2層のノードＩＤ
層ポインタを１つ増やします。lvpos++
第2層では、nn-2回ループ処理する必要があります。
③ 続行の可否を判断する①
①と②で１つの線分（ループの一部）ができました。
ここで、この線分が最短パスの一部となる可能性があるか否かを判断します。
・ pcross（）がタイプ２のとき・・・有効
・ pcross（）がタイプ０のとき
lrset（）がタイプ０のとき・・・有効
lrset（）がタイプ１のとき・・・無効（このパスは後続の計算が不必要）
④ 端から順に計算する
このまま、第2層を処理していくと保持するメモリの量が膨大になります。
そこで端から順に層を深くして処理を行います。
アルゴリズムは、いくつの点数を処理するのかあらかじめわかっていないものとすると、底層が第何層になるかわかりません。
そこで、この核となるアルゴリズムを関数として、その関数の呼び出し側でループを制御します。
重要なのは、現在処理している部分がどこなのか知っていることです。
つまり、層ポインタと層の中の位置です。
もちろん、構成してきたパス情報（wpath）も保持していなければなりません。
⑤ 続行の可否を判断する②
層が深くなっていくと、パスを構成するノード数と共に線分数も増えていきます。
続行の可否を判断する条件は、線分群が凸図形を2分割しているか否かです（Ｌ集合かＲ集合が空集合以外のとき）。
ところが、アルゴリズムは与えられた入力が凸図形か否かを知りません。しかし、与えられたノード集合から凸図形を描くことをアルゴリズムの作成者は知っています。
そこで、次の条件のとき凸図形が2分割されたと判断します。
パスを構成する線分のpcross（）がタイプ２のＡＮＤが、空集合にならないとき・・・有効
それ以外の時、
lrset（）がタイプ０のとき・・・有効
lrset（）がタイプ１のとき・・・無効（このパスは後続の計算が不必要）
（ lrsetは随時計算が必要かわからなくなってきました）
⑥ メモリの保持
long p2(nnxx)・・・第2層のノードＩＤと同じように各層に配列が必要になってきますが、実装メモリに余裕がない場合、malloc()関数などで、節約する方法もあります。
５． 最後に
「４． 核となるアルゴリズム」で核関数と関数の呼び出し側の処理がごっちゃになりましたが、ご容赦ください。
筆者がＳＥとして現役時代は上のようなざっくりとしたアルゴリズムからコーディングやテストを行っていました（筆者はチームプレーがあまり得意でなかったのですいません）。
2019年4月27日～2019年5月6日まで休暇なので上のアルゴリズムからプログラムを作ってテストを行い、どの程度の計算量になるか測ってみたいと思います。
なお、どのような結果になっても報告はしたいと思います。そして、ソースも公開したいと思いますが、言語はＶＢになるかもしれません。ＶＢの方が手っ取り早いので。
また、線分上にノードが乗っかるケースなど、不具合があることは承知していますが、随時修正していきたいと思います。
閉路となるパスが複数存在しますが、その中の最短のパスを解とします。
巡回セールマン問題の命題そのものを振り返ってみる
１． 初めに
巡回セールスマン問題と凸図形の関係を読み直しているときに、ふと気が付きました。
巡回セールスマン問題の問いはどのような形で出題されるのだろうか？と。
２． 錯覚？
筆者は、都市の座標が羅列されたノード群のみが与えられると思っていました。そして、都市間は直線で結ばれており、その距離（重み）は座標から求められると思っていました。
３． 都市の座標ではなく都市間の距離（重み）が与えられる？
都市間は直線で結ばれるのではなく、曲線も許しているのでしょうか？そして都市間の距離（重み）は座標とは別に与えられるのでしょうか？
そうであれば、 巡回セールスマン問題と凸図形の関係の前提は根底から覆されてしまいます。
４． 拡張性
もし、「３． 都市の座標ではなく都市間の距離（重み）が与えられる？」が正しい命題の一部であったとすると筆者の巡回セールスマン問題の解法は根底から覆されてしまいます。
しかし、巡回セールスマン問題と凸図形の関係を前提とした筆者の巡回セールスマン問題の解法は、拡張性がほとんどないことを筆者自身も認識していて「命題の出し方が不親切である」とごねることはありません。
唯一残るモデル性は、モンテカルロ木のような分枝の消去法だけであり、巡回セールスマン問題以外の命題を解くとき、その命題ごとに消去条件を考え出さなければなりません。
５． 最後に
このブログを書くことによって、筆者の目的は「巡回セールスマン問題の解法」ではなくなってきたように思いますので、上述のような破綻が訪れてもそう大きな落胆とはならないようです。そして、それはおそらく負け惜しみではありません。
この記事を投稿する直前にgoogleで「巡回セールスマン問題」を検索し、Wikipediaを見たところ、筆者の想定してい命題は「平面ＴＳＰ」に属するようです。
なお、巡回セールスマン問題の命題を読み返してみたところ、都市の位置と都市間の移動コスト（筆者は距離とか重みとしていました）から答えを導きだすものが、真？の命題のようです。つまり、座標（位置）から移動コスト（距離）を決定するものではありませんでした。
座標（位置）から移動コスト（距離）を決定する命題は「平面ＴＳＰ」と呼ばれるようですが、これもはっきりと断言できません。
巡回セールスマン問題をモンテカルロ木探索で解く
１． 初めに
筆者がモンテカルロ木探索を知ったのはごく最近です。巡回セールマン問題の解法を25年間求めていた筆者が辿り着いた解法がモンテカルロ木探索によく似ていたので、このモンテカルロ木探索の有効性を数値によって測ってみたいと思いました。
なお、筆者による巡回セールスマン問題の解法は、遅くとも今年（2019年）の夏くらいまでには記事にしたいと思っています（Ｃ言語によるソース公開を予定しています）が、筆者の解法は次の２つの問題を抱えていました。
① 速度・・・解法と呼べるほど有効な解法であるか？
② 解法に論理的な破綻を含んでいないか？
①の問題は、この記事（または後続記事）によってある程度解決できることを期待しています。
②の問題は、筆者の解法を検証してくれる人がいないので今年（2019年）の5月くらいに実行可能なプログラムを作成して、公開したいと思っています。（理論は後からついてくるという乱暴な実力行使みたいなものですね（笑い））
②は①の期待速度がそれほどでもなければ、また何かを考え直さなければならないので、まず本記事などで①の問題を解決したいと思います。
２． モンテカルロ木探索
以下の記述は「モンテカルロ木探索」をある程度理解しているものとして書いていますのでご容赦ください。とはいっても、そもそも「モンテカルロ木探索」の詳細を筆者もよく知りません。
モンテカルロ木探索は主にゲームなどの場面で用いられる手法（アルゴリズム）であると認識しています。そして、その手法（アルゴリズム）は確率的なものだと認識しています。
確率的な部分は、下位の枝ノードを生成するか否かの判断に用いられるものと思っていますが、筆者の巡回セールスマン問題の解法は、確率的ではなく厳密に下位の枝ノードを生成するか否かを判断します。
結論として、「モンテカルロ木探索」は下位の枝ノードを生成するか否かの判断によって膨大な計算不可能な計算量を計算可能な計算量にするものとみなします（確率的か厳密的かを問わず）。
３． 凸図形を描く点（座標）配置を解く
巡回セールスマン問題を解くときの１つのケースをモンテカルロ木探索を使って考えてみます。それはノードの座標配置が凸図形となるケースです。
ただし、巡回セールスマン問題を直接解くわけではありません。まず、複数の閉路（パス）を作成します。その複数の閉路（パス）から最短の閉路（パス）を選択します。
なお、一般的に木（ツリー）の階層を何と呼ぶか筆者はよく知らないので、頂点ノードを第1層、次の枝ノードを第2層、深さが増すごとに第3．．．第ｎ層と呼ぶことにします。また、木構造の最深層を底層と呼ぶことにします。
３．１ 任意の１つのノード
凸図形から任意の1点（ノード）を選択します。
巡回セールスマン問題では、与えられた点（ノード）のすべてを必ず1回だけ通過しなければなりません。従って、選択するのは１つのノードが必要十分条件であると考えます。
このノードが第1層となり、このノードがパスの始点となります。
３．２ １つのノードから作られるすべての線分
第1層のノードから作られるすべての線分を考えます。
ノード数がＮ点数であるとき、この線分の数はＮ－１となります。”－１”は頂点（自分自身）のノードを意味し、除外されるからです。
そして頂点ノードから枝ノードを派生させます（第2層）。
３．３ 排除するノード
図3
図3において第1層のノード（Ａ）からつながるノード（第2層）は両隣のノード（ＢＣ）を除いてすべて対角線となります（例えば線分ＡＤ）。この対角線は凸図形を描くノード群を完全に2分割します。この2分割されたノードの集合をＬ（左）集合とＲ（右）集合とします。
ここで、対角線（例えば線分ＡＤ）と交差しないでＬ集合とＲ集合をつなぐ線分は存在しません。つまり、対角線となる線分はモンテカルロ木から排除されることになります。
巡回セールスマン問題と凸図形の関係（２． 最短パスは交差する線分を含まない）から
結果として、ノードＡとつながるノードはＢかＣだけが許されることになります。そして、ＢとＣのいずれを選択しても結果として逆回りの閉路（パス）を生成するので、Ｂだけについて述べたいと思います。
３．４ 第3層以降
Ｂ（第2層）につながるノード（第3層）は、凸図形の外周の両隣のノードしか存在しません。「３．３ 排除するノード」と同じ理由からです。さらに片方のノードは１つ前の層のノード（Ｂの場合はＡ）と同じなので選択できるノードは１つしか存在しないことになります。
以下、底層が第1層と一致するまで同じことの繰り返しになります。
３．５ 計算量
上述のように凸図形を描く点（座標）配置を巡回セールスマン問題に与えた場合、Ｎ！通りの計算量が、（第1層は1通り）、第2層はＮ－1通り、第3層はＮ－2通り、底層はＮ－Ｎ＋1通りとなります。
すなわち、（Ｎ－1）＋（Ｎ－2）＋．．．（Ｎ－Ｎ＋１）の2倍≒Ｎの2乗通りとなります。
４． 凸図形が内包するノードのケース
図４
図4のように凸図形の内部にノードＥを加えてみます。
４．１ 第1層
第1層は同じくＡとします。
４．２ 第2層
第2層はＢＣにＥが加わりますが、ＥのケースとＢのケースだけを考えます。
４．３ Ｅのケース
第1層Ａ、第2層Ｅのとき、第3層に許されるのは、ＢかＣだけです。
なぜならば、それ以外のノードは対角線と同じく凸図形を描くノード群を完全に2分割します（例えば線分ＡＥとＥＤ）。
Ｂ（ＡＥＢ）とＣ（ＡＣＥ）も凸図形を描くノード群を完全に2分割しますが、ＬかＲ集合のどちらかが空集合となります。つまりＬとＲ集合をつなぐ線分は必要なくなります。
４．４ ＢＣのケース
第1層Ａ、第2層ＢかＣのとき、第3層に許されるのは、ＥかＢＣに隣接するノードだけです。
第3層がＥのとき、「４．３ Ｅのケース」と同じとなり、ＢＣのとき、「３． 凸図形を描く点（座標）配置を解く」と同じになります。
４．５ 計算量
凸図形が1点のノードだけを内包するとき、Ｎ！通りと比較にならないくらい計算量が小さくなることがわかりますが、凸図形に相当数のノードが内包されるとき、どのくらいの計算量になるか残念ながらよくわかっていません（う～ん、結論としては弱いですね）。
ただ、計算量を求める法則があるような気だけはしています。興味のある方は探してみてはいかがでしょうか？
４．６ 特異なケース
ノードＥがどれかの対角線上に存在するとき、どのような処理をすればいいのかわかっていません。
もしかすれば、このケースが大きな意味を持っているかもしれませんし、簡単に処理できる問題かもしれません。
ただ、筆者はこのケースは巡回セールスマン問題の解法にとって全体から考えれば小さな問題と考えているので、当面このケースを考えるつもりはありません。
５． 最後に
５．１ 厳密解のアルゴリズム
次の記事から厳密解のアルゴリズムを掲載したいと思います（ソースの公開はまだ先になりそうです）。もっともアルゴリズムに欠陥があるかもしれませんし、予想しているような点数を予想しているような現実的な時間で解けるかわかりません。
５．２ 座標配置と計算時間
上述したことに疎漏がなければ、与えられたノード群を解くときノードの座標配置と計算時間に関係があることがわかりました。つまり、「凸図形に内包するノードの数が多いほど計算量は多くなる可能性が高い」ということです。
感覚的にですが、内包するノードの座標配置によっても計算量は作用されるのではないかと考えています。
５．３ 拡張性に難点あり
上述したことの前提は、ユークリッドの2次元空間上での解法の考え方であるということです。
例えば、ユークリッドの3次元空間では、巡回セールスマン問題と凸図形の関係（２． 最短パスは交差する線分を含まない）は成立しません。それ以外の条件を考え出さなければなりません。
５．４ 領域を作る座標配置
薄々感じていたことですが、このブログの記事によって考えを整理しているうちに1つの僅かな光明を得ました。
それは、「同じ点数のノードであっても座標配置によって異なる情報を持つ」ということです。
例えば、上述の手法を用いれば、巡回セールマン問題を解く過程で、解く過程が座標配置から領域を作って（あるいは切り取って）いきます。これは2次元上のことですが、解法を3次元に拡張できれば、ある科学的問題を解明できるのではないかと期待しています。
なお、領域はＬまたはＲ集合が空集合になったとき構成されます。
巡回セールスマン問題と凸図形の関係
１． 初めに
筆者の巡回セールスマン問題の解法はアルゴリズムによるものです。従って数学的にＮＰ問題などの解法を求めている方には参考にならないかもしれません。
また、Ｎ！を多項式に展開することを目的としているのではなく、いかに最小の計算量で求めるかを目的としています。
なお、以下の記述はユークリッドの２次元空間を前提としています。
２． 最短パスは交差する線分を含まない
図１
図２
２．１ 図1の説明
図１においてＰ１とＰ２は、ノードＡＢＣＤ以外のノードを含むパスとします。
また図1で線分ＡＢと線分ＣＤは交差しています。
注意点は交差する交点が線分ＡＢと線分ＣＤの内部に存在することであって、例えば線分ＡＢを無限線に延長したとき、線分ＣＤと交差した交点のケースは当てはまりません。このケースは線分の外部で交差しているとみなします。
２．２ より最短に
図２を使って線分ＡＢの距離＋線分ＣＤの距離が、線分ＡＤの距離＋線分ＢＣより長いことを証明したいと思います。
ＡＤ＜ＡＥ＋ＤＥ・・・①
ＢＣ＜ＣＥ＋ＢＥ・・・②
①式と②式を足すと
ＡＤ＋ＢＣ＜ＡＥ＋ＢＥ＋ＣＥ＋ＤＥ・・・③
③式の右辺を整理すると
ＡＤ＋ＢＣ＜ＡＢ＋ＣＤとなり、証明が終了しました。
２．３ パス全体をみると
Ｐ１＋Ｐ２＋ＡＤ＋ＢＣ＜Ｐ１＋Ｐ２＋ＡＢ＋ＣＤを整理すると
ＡＤ＋ＢＣ＜ＡＢ＋ＣＤとなりパス全体においても交差する線分を最短につなぎかえられることがわかります。
３． 凸図形を構成するノード集合の最短パス
「凸図形を構成するノード集合は巡回セールスマン問題において外周が最短距離となる」（外周とは凸図形を描画する線分そのものを意味します。）
３．１ 証明
① 凸図形の外周以外の任意の線分（線分ＡＢ）を１つ選択します。
② すべてのノードを線分ＡＢの左右（あるいは上下）に分類してノード集合Ｃとノード集合Ｄを作ります。このとき、ノード集合Ｃ、Ｄは絶対に空集合とならないことを確認してみてください。
③ 巡回セールスマン問題の解は全てのノードを1回だけ含むことが条件となりますから、
線分ＡＢのノードＡ、Ｂとノード集合Ｃ、Ｄの全てのノードを含む必要があります。となるとノード集合Ｃのいずれかのノードとノード集合Ｄのいずれかのノードをつなぐ機会（線分）が最低1回は必要となります。この線分は必ず線分ＡＢと交差しますので確認してみてください。これは「２」で証明した「最短パスは交差する線分を含まない」という条件に反します。故に、 凸図形の外周以外の任意の線分は最短パスには含まれない。従って、残る凸図形の外周だけが最短パスを構成することになります。
４ 最後に
途中、証明を省いた部分がありますが、そう難しくないものなので興味のある方は証明してみてください。この記事は厳密な論文を書くことを目的としていないので筆者の怠慢をお許しください。
巡回セールスマン問題
記事一覧
・2019/03/30 巡回セールスマン問題と凸図形の関係
・2019/04/06 巡回セールスマン問題をモンテカルロ木探索で解く
・2019/04/07 巡回セールマン問題の命題そのものを振り返ってみる
・2019/04/13 巡回セールスマン問題の解法のアルゴリズム
巡回セールスマン問題とアルファ碁の比較
１． 初めに
「ＡＩ（人工知能）は巡回セールスマン問題を解けるか？」ということを考えることが主要なテーマの１つである本ブログは、アルファ碁を例として巡回セールスマン問題との比較を行いたいと思います。
２． 階乗の概算値
巡回セールスマン問題についての詳細は、ネット上に数多の説明が載っているのでそちらをご覧ください。ここでは、結論として次のことだけを巡回セールスマン問題の説明とします。
「Ｎ！通りのケースからただ１つのケースを求める問題である。」
ここで、Ｎは点の数、！は階乗を意味します。
さて、上述の問題はとても単純で容易く解ける問題に見えますが、問題はＮ！が示す数の大きさにあるので、その数を見ていきたいと思います。
10！ ≒3x10の6乗
100！≒9x10の157乗
170！≒7x10の306乗(筆者の持つ表計算ソフトではこのＮ＝170を超す計算はエラーとなりました。）
ここまででもＮ！が示す数の大きさが実感できたと思いますが、アルファ碁との比較のためもう少し概算による計算をしてみたいと思います。
２．１ 200！の概算
もうすでにお気づきかと思いますが、「170！≒7x10の306乗」で最も注目するべきは306乗の部分です。そこで200！の概算において〇〇乗の部分を注目してください。
1～200を平均した100を全ての数（1～200）と同じとみなして（かなり乱暴ですが、結果となる数値を見ればその乱暴さも吹き飛ぶものと思います）、200！の概算を行います。
200！≒100の200乗＝（1x10の2乗）の200乗＝1x10の（2x200）乗＝ 1x10の400乗
これは、数値の先頭の1に0が400個続く数値を意味します。
２．２ （19x19）！の概算
（19x19）という数値を考える理由は、碁盤が縦19、横19からなるマス目で構成されているからです。（19x19）＝361のマス目が囲碁の空間となります。「２．１ 200！の概算」と同様に概算を行います。
361の平均値を180とします。
361！≒1.8の361乗x100の361乗≒1.4x10の92乗x（1x10の2乗）の361乗＝1.8x10の（92＋2*361）乗＝1.4x10の814乗
ここで、Ｃ＝1.4x10の814乗とします。
３． 囲碁の世界
囲碁のルールでは、黒石番が先手となりますが、第一手は盤上の（19x19）マスのどこに着手しても問題はありません。同じように後手番となった白石も（19x19）－1マスのどこに着手しても問題はありません。囲碁では、黒石であれ白石であれすでに埋まっているマスに着手することができません。「（19x19）－1」マスの－1は、すでにマスが埋まっていることを意味します。黒石と白石は交互に着手しますが、そのたびにマスは1つづつ埋まっていきます。
これは囲碁というゲームがとり得る対局のケースの全てを、「２．２ （19x19）！の概算」で計算した数値Ｃであらわすことができることを意味します。
囲碁界では、「同じ対局は2度と現れない」と言われていますが、Ｃというケースの数値をみれば納得もできます。
ただしＣの中には、囲碁のルールによる反則手も含まれており、「コウ」という場面などの想定はしていません。
４． アルファ碁
アルファ碁は、多くの局面を予想し、黒白どちらが優勢かという形勢判断を行っています。
そしてそれらの予想や判断がＡＩ（人工知能）によって行われていることも知られていますが、それらは確率によるものと認識しています。
世界のトップ棋士がアルファ碁に敗れているのは、ＡＩ（人工知能）の確率を上回る着手を思いつかないからだと思っています（理由はくどくど書きませんが、決して囲碁界の棋士をけなしているのではありません。）。
５． 巡回セールスマン問題
囲碁と巡回セールスマン問題に類似点があることがわかりましたが、巡回セールスマン問題を適切な時間内で解く方法が発見されたならば、アルファ碁に勝つことができるか？そしてそれから、スーパーアルファ碁が現れて、リベンジを果たされるのか？という疑問が浮かびます。
なお、アルファ碁と巡回セールスマン問題とを比較するとき、巡回セールスマン問題の解法を持つ装置は、囲碁のルールは知っているが、囲碁の勝負に勝つ方法は知らないものと仮定します。巡回セールスマン問題の解法は、すべての着手（決着までの後続手を含む）を網羅しているためすべての着手から最善手を選択できるため、「勝つ方法を知らなくてもよい」という前提を持ちます。
５．１ 近似解と厳密解
巡回セールスマン問題を解く方法は、近似解と厳密解が存在します。
５．１．１ 近似解
近似解がすべてのケースを網羅できるとはいえ、確率と似た側面を持ちます。ある命題に対して近似解は厳密な答えに近い答えです。近似解を求める手法の評価は、厳密解への近さと答えを求める過程の速度によって決定されます。
日常のテクノロジーでは近似解によって困ることはほとんどありませんし、科学の世界でも厳密な法則を発見したり、その法則を厳密に解明した例はほとんどないのではないでしょうか？
つまり、近似解や確度の高い確率によってわれわの世界は発展していくだろうし、困る人はその精度によって増減するということです。
さて、巡回セールスマン問題の近似解を適切な時間で解くことができたとき、アルファ碁の予想や判断の確率と近似解の精度の違いにより、勝負は決するものと考えられます。
仮にアルファ碁が負けを認めたとき、近似解の精度を上回るスーパーアルファ碁の出現によってリベンジは果たされるものと考えられます。
５．１．２ 厳密解
厳密解を確率で表せば100%となります。つまり、アルファ碁に負けることもなければ、リベンジされることもないという結論になります。
６． 最後に
- 巡回セールスマン問題と囲碁は類似点が存在します。筆者は、巡回セールスマン問題を囲碁のモデルとして結びつかせたいと考えています。
- この記事では触れませんでしたが、1.4x10の814乗通りの囲碁のケースを持つ世界をＡＩ（人工知能）はどのように見て、どのように解釈しているのか？
- 巡回セールスマン問題の解法にＡＩ（人工知能）を取り入れることは可能か？
以上、最後はまとめになりませんでしたが、目標は大きく「アルファ碁に勝つ」厳密解によるシステムの作成を本ブログの目標の1つにしたいと思います。
ＡＩ（人工知能）の能力のレベル（低レベルから脅威レベルまで）
１． 初めに
この記事の内容は、筆者が一般的なＡＩ（人工知能）の能力のレベルをあらわす指標であると思ってネットから拾ってきた情報を基礎としてＡＩ（人工知能）の能力のレベルを考察するものです。
２． 一般的なＡＩ（人工知能）の能力のレベル
・レベル１：例えば、家電のような少ない情報を少ない判断の範囲でデータを処理する。
・レベル２：弱いＡＩと呼ばれるようです。人がＡＩ（人工知能）を対話などによる教育によってＡＩ（人工知能）を育てる。つまり、教えられた範囲でのみデータを処理する。
・レベル３：レベル２に加えて、人あるいは環境に対応するパターンを、自立的にも学習する。
・レベル４：レベル３に加えて、対応パターンが強化されていく。
・レベル５：人と同等の知能を、ＡＩ（人工知能）が持つ。
レベル１～５を「人の脅威となりうるか？人が完全に制御できるか？」という基準でレベル段階を判断していきます。
レベル１とレベル２を低レベルと判断します。
レベル３は、自立的な学習を取得していることから中レベルと判断します。
レベル４を高レベルと判断します。
レベル５を脅威レベルと判断します。
３． 自立的判断
レベル３、４は自立的な学習能力を取得しています。つまり、自立的に学習し判断することができます。これはＡＩ（人工知能）が（人の利益にとって）間違った判断をすることがあることを意味します。そして、暴走するかもしれません。
これに対処するためには、いくつかの方法が考えられます。
① ＡＩ（人工知能）の電源ＳＷをおとす。
② あらかじめ、ＡＩ（人工知能）に暴走を制御する機構を組み込んでおく。
①の場合、多くのケースでは成功するかもしれませんが、例えばＡＩ（人工知能）を搭載した爆撃機を遠隔操作で発進基地に引き戻すことが可能なのでしょうか？そうでなければ、目標物への爆撃を回避できても、どこかに墜落して爆弾と共に爆発してしまいます。
②の場合、制御機構は意図したとおりに働くのでしょうか？ＡＩ（人工知能）の自立した学習が制御機構の回避方法も学習していることは考えられないのでしょうか？
このようにしてＡＩ（人工知能）は、徐々に人の制御から離れていくのではないでしょうか？
４． 脅威となるレベル５
レベル５になると、いくつかの部分でＡＩ（人工知能）は人の脳をはるかに上回ります。
例えば、演算処理速度です。いくら人が手動でコンピュータを操作しようとも、ＡＩ（人工知能）が学習した人の脳と同等の知能は、人より早くデータを処理して的確なアルゴリズムを組んでいくことが予測されます。
筆者が考える最大のＡＩ（人工知能）の優位性は、シミュレーションによるトライ＆エラーの回数の多さです。人が1回のシミュレーションを行うとき、ＡＩ（人工知能）は数万回のシミュレーションを行っているかもしれません。
一方、人の脳がＡＩ（人工知能）を上回る部分は存在するのでしょうか？筆者にはほとんど思い浮かびません。
５． 対応パターン
ＡＩ（人工知能）のレベルを測るとき（例えばレベル４）、「対応パターン」が指標となりますが、これは何を指しているのでしょうか？
知識の引き出しのことなのでしょうか？
対人とのコミュニケーション能力のことなのでしょうか？
いずれにしても、それらの能力を自立的に学習するのですから、ＡＩ（人工知能）自身が自分に与えられた環境から学んでいく能力と考えられます。
例えば、アルファ碁のことを考えてみます。蛇足ながら筆者は若いころに碁会所でアマ2段くらいの棋力を持っていましたが、現在では12級くらいです。ただ、囲碁が好きなこととルールがわかることからアルファ碁を例にとってみました。
５．１ アルファ碁
さて、アルファ碁はレベル３なのでしょうか？レベル４なのでしょうか？
その答えをすぐに出すことは、難しいので囲碁というゲームの局面を考えていきたいと思います。
布石（序盤）：棋士の間には定石という黒白の石を配置する多くのパターンが用意されています。この定石は、数百年前から時代と共に定石が黒と白のどちらに優位に働くか？それとも互角か？を棋士によって検討されてきました。そして、何人かの棋士が新定石を生み出してきました。
ところが、ここ数年くらいでアルファ碁は新定石を生み出したり、棋士たちが下した布石による黒白の優位性や互角性の判断を覆したりしました。
これは、アルファ碁が自立学習を行って自ら布石という対応パターンを生み出したという証拠になります。アルファ碁は、世界のトップ棋士に無敗なのですから、アルファ碁より弱い棋士がアルファ碁に何かを教えることができません。
中盤や寄せ（終盤）においては、対応パターンが狭められていくのでＡＩ（人工知能）にとっては、対応パターンを用意するのは布石より容易になっていきます。
レベル３か？４か？の結論はレベル３としたいと思います。確かに対応パターンを自立的に生み出したことは明白ですが、対応パターンは19ｘ19マスの盤上という狭い環境に限定されるので、それほど強い対応パターンとは考えられません。
６． さらなる脅威
上述したＡＩ（人工知能）のレベルは、人の脳に相当するものだけでした。これは、脳がただ想像したり思考したりするのと同じことで、実際に身体のどこかを動かすという振る舞いを
考慮に入れていませんでした。
さて、レベル５のＡＩ（人工知能）に例えば「手」を与えたらどうなるでしょうか？何かを物理的に生産しようと思わないでしょうか？
人類に都合よく考えれば、人のために食料の生産工場を作ってくれるかもしれません。それを否定的に考えれば、人を支配下におくためにあるいは滅亡させるためにＡＩ（人工知能）搭載の兵器の生産工場を作るかもしれません。
７． 脅威の回避
はっきりいえば、ＡＩ（人工知能）の脅威を回避する方法はほとんど見つかりません。レベル５のＡＩ（人工知能）に手が与えられる前に回避方法を見つける必要を感じます。筆者の回避方法は、「限界環境境界」の設定です。
「限界環境境界」とは、ＡＩ（人工知能）に与える環境（すなわちデータ）を制限するために境界を設定して、その境界の限界を模索していこうというものです。
最後に期待する回避方法は、レベル５のＡＩ（人工知能）の開発は不可能であるという論拠を見つけることです。
