17/05/10 09:58:58.76 nXQAoWxu.net
>>268 関連
ちょっと古いが
URLﾘﾝｸ(alcuin.hatenablog.com)
2013-12-30 ボードゲームの思考アルゴリズムの入門 Thinking out loud id:alcuin
(抜粋)
社内の技術系Adventカレンダー向けに何か書けと言われ、とりあえずボードゲームの思考ルーチンについて書いてみたり。
せっかくなので、存在を忘れかけていたBlogメンテの意味も込めてこちらで公開。
オセロ、チェス、将棋、囲碁の探索問題としての「難しさ」
オセロは、90年代の後半に、日本人チャンピオンの中島さんとPCが対決をし、6対0で人間が完敗してしまいました。
チェスもまた、1996年にDeepBlueという計算機クラスタにより、人間に一応勝ちました。
将棋も、2013年になり、人間に勝つ兆し(事実上勝っている?)が出てきました。
各ボードゲームの局面数をざっくり推定をすると、以下のようになります。 (10の360乗というのは、0が360個ということです、念のため。)
オセロ : 10の56乗
チェス : 10の120乗
将棋 : 10の220乗
囲碁 : 10の360乗
非常に膨大な探索空間です。 探索をするという観点では、仮にコンピュータが10倍速になったとしても、せいぜいさらに数手先まで深読みが出来る程度の違いしか無かったりします。
そういう意味では、コンピュータの「早さ」の進歩も大事ながらも、適切な評価関数であったり、棋譜のデータを取り入れたりといった試みの方が大事だったりもします。
ちなみに、現在、最もホットな領域の1つが「囲碁」です。 上記の局面数を比較すると、囲碁だけが桁違いです。
これは、19×19と盤が広く、好きなところに置けるので局面数も広いことが理由で、また探索をする上でも、評価関数が非常に難しい(たった一手によって形成が逆転をしたりと安定せず、また形成の判定に地というパターン認識が求められるためスコア化が極めて行いにくい)ということが主な理由です。
そのため、ちょっと前までは、今までのゲーム木探索というアプローチとノイマン型計算機である限り、囲碁プログラムは人間には勝てないと言う研究者もいました。
しかし最近になり、確率的なアプローチでプレーをする「モンテカルロ囲碁」という方法が出現し、突如、囲碁のレベルが上がりました。