巡回セールスマン問題とアルファ碁の比較
１． 初めに
「ＡＩ（人工知能）は巡回セールスマン問題を解けるか？」ということを考えることが主要なテーマの１つである本ブログは、アルファ碁を例として巡回セールスマン問題との比較を行いたいと思います。
２． 階乗の概算値
巡回セールスマン問題についての詳細は、ネット上に数多の説明が載っているのでそちらをご覧ください。ここでは、結論として次のことだけを巡回セールスマン問題の説明とします。
「Ｎ！通りのケースからただ１つのケースを求める問題である。」
ここで、Ｎは点の数、！は階乗を意味します。
さて、上述の問題はとても単純で容易く解ける問題に見えますが、問題はＮ！が示す数の大きさにあるので、その数を見ていきたいと思います。
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つにしたいと思います。
