コンピュータ囲碁が強くなっているらしい
「情報処理」2008年6月号（Vol.49 No.6 通巻520号）p.686に掲載された「モンテカルロ木探索−コンピュータ囲碁に革命を起こした新手法」と題する記事のアブストラクトから。
囲碁は，主なボードゲームの中でコンピュータの挑戦を拒み続けてきた唯一のゲームである．囲碁の難しさは良い評価関数を作ることが困難であるということに起因していた．
しかし2006年にコンピュータ囲碁の世界にまったく新しいアルゴリズムがもたらされた．評価関数が不要という画期的な探索アルゴリズム，通称，モンテカルロ木探索と呼ばれるものである．登場から2年あまりで9路盤ではプロ棋士を破るほどの強さを獲得した．そのアルゴリズムの性質や理論的背景について述べ，今後の展望を探る．
モンテカルロ法とは何か、ご存知ない方はWikipediaをどうぞ。
これを円周率（の近似値）計算に応用したのが「ビュフォンの針」という手法。
本題に戻って記事本文モンテカルロ木探索アルゴリズムを要約すると、こんな感じ。（私の解釈であることに注意）
- 囲碁は、評価関数の作成が非常に難しいゲームである。
- しかし、終局した時点の勝敗ならば容易に判定できる。
- そこで、ある局面が有利か不利かを判定するのに評価関数を用いるのではなく、その局面から適当にランダムに打つ（モンテカルロ法）仮想プレイヤー同士で終局まで対戦させ（プレイアウト）、勝敗を判定し探索木を構築する。
- プレイアウトを繰り返しながら探索木を成長させる。 その際に有望だった手筋により多くのプレイアウト（≒思考時間）を割り当てる。
- さらに一定の閾値を超えたら、その手を展開（≒定石化）し、プレイアウトを開始する節点を一段深くする。
特に最後の2点がキモで、これはミニマックス戦略におけるαβ枝刈りという手法に近いものがある。
このアルゴリズムがGNU Goや市販囲碁ソフトに組み込まれると面白い（かも）。
