Criticality: a Monte-Carlo Heuristic for Go Programs

by Rémi Coulom. Invited talk at the University of Electro-Communications, Tokyo, Japan (January 2009).

English version


When applying Monte-Carlo tree search in a Go-playing program, a variety of playout statistics can be used to guide the search. All-moves-as-first value, average score, or average point owner, in addition to winning frequency, provide useful information for the search algorithm. Criticality is another Monte-Carlo heuristic that estimates how important it is to own a point in order to win playouts. It was used succesfully as a pattern feature in Crazy Stone.


クリティカリティ: 囲碁プログラム用のモンテカルロ・ヒューリスティック



モンテカルロ探索を使った囲碁プログラムは,プレイアウトから得られる種々の統計情報を探索に利用することができる.このような情報には,勝率の他に all-moves-as-first の値,平均スコア,ある点の平均オーナーなどがある.クリティカリティ(臨界)は,ある点を取ることがプレイアウト(複数)に勝つためにどの程度重要かを推定する,新しいモンテカルロ・ヒューリスティックである.これを Crazy Stone のパターン特徴の一つとして用いて良い結果を得た.