Darkside(リンクエラー修正しました)

2016年03月14日の記事

2016年3月14日(月) 21:31

前夜の状況

 ボードゲームをプレイする場合、任意の局面において合法着手が幾つかあり、それを何手が進行させると勝負が着く。考慮する場合の数は掛け算で増えるため、爆発的に大きくなる。将棋で10の220乗、囲碁で10の360乗、と流布されている。そのため、三目並べのような単純なものを除いては、人間はもちろんコンピューターにも計算できないほど考慮数が増えてしまう。
 そこで必然的に、ボードゲームでは2つの手法が使われる。

1)合法着手の全部ではなく、一部だけを読み進める。
 明らかに悪い着手は、最初から考慮しない。

2)決着が着くまで読み進めるのではなく、途中で読みを打ち切る。
 途中の局面で優劣を判断する。

 これにより、考慮数を減らすことができる。
 しかし、すべての場合を調べている訳じゃないので、読み抜けが発生する。
 人間は1)が抜群にうまい。読める数は非常に少ないが、1)で僅かな合法着手しか考慮しないため、2)でかなり先まで読むことができる。
 初期の人工知能は、人間が1)を行う際のノウハウをプログラムに組み込んだ。まさしく、人間の知能を模倣した。人工知能というわけだ。

 だが、人間の1)は単純な規則で記述できるようなものではなく、1)の巧みさにおいて人工知能は人知に圧倒的に劣っていた。

 そこで1)を放棄し、高速演算というコンピューターの利点を活かし、ひたすら力技で先読みする手法が隆盛を極めた。人間がどんなに1)が上手でも、理論上は読み抜けの可能性をゼロにできない。一方コンピューターは全部読んでいるのだから、読み抜けがない。これでは人間は勝てない。
 こうして強い人工知能はできたが、1)での勝負を捨てたプログラムを人工知能と呼ぶことは邪道ではないかという考えは常に存在した。また、囲碁のように合法着手の多いボードゲームでは、場合の数が増え過ぎて、このアプローチが無理だった。人工知能に1)での勝負を強いるのが、囲碁なのだ。

 ところが、人工知能研究は、また逃げてしまった。
 AlphaGo の登場する前も、対局囲碁ソフトは相当に強くなっていた。最強の人間にはボロ負けするが、普通のアマチュアでソフトに勝てる者は1%とか2%しか居なくなっていたのではなかろうか。その意味では、市販ソフトとしては十分に強くなっていた。
 なぜ実用的な強さのソフトが製作できたかと言えば、2)の方でブレイクスルーがあったためである。すなわち、勝負が決着するまで先読みを進める、モンテカルロ法だ。

 モンテカルロ法は要するにランダム法で、ランダム着手で終局まで打ち進める。それを数多く行って、勝つ確率の高い手を選ぶ。
 そんなのうまく行かないだろうというのはその通りで、うまく行かない。だが、完全なランダムではなく少しでも良さそうな手を選ぶとマシになる。あれこれ改良を加えたところ、それなりに強いソフトが出来た。
 しかしそれでも、プロ棋士に対抗できるような強さは得られず、棋力向上も頭打ち。1)も放棄したまま。
 以上が、AlphaGo 登場前夜の状況である。

written by higashino [ネット・PC] [この記事のURL] [コメントを書く] [コメント(0)] [TB(0)]

この記事へのトラックバックPingURL
Darkside(リンクエラー修正しました)

Generated by MySketch GE 1.4.1

Remodelling origin is MySketch 2.7.4