囲碁ＡＩにおける革命「モンテカルロ木探索」とは何か？に参加した。 期待以上の面白さだった！
弱い弱いといわれていた囲碁AIだけど2006年頃から急に強いのが出始めて、今ではアマチュア最強と互角ぐらい、置石８個で１９路盤でプロに３戦中１勝した、とか。今まさにコンピュータ囲碁会に革命が起きている！
伊藤毅志「ゲーム情報学から見たコンピュータ囲碁」
- バベッジ：1840年、コンピュータができたらチェスもさせられるよ
- シャノン、チューリング、グリーンブラッドもなんやら
- 完全情報ゲームだから、解析し尽くせば先手後手どちらが必勝かわかる
- チェッカーは2007年に解けた
美添一樹「モンテカルロ木探索 理論編」
話が小気味よくてすごく面白かった！
- モンテカルロ法を使ったAIは昔(1993)からあった、けど弱かった
- 2006年ブレークスルー
- 勝ち負けの点差を最大にするんじゃなく、勝つ確率が高い手を選ぶ
- 勝てそうな手を調べる回数を増やす
- その手を調べた回数が少ないうちは、たまたま負けが続いただけかもしれないのでまだチャンスを与える。そうでなければ本当にダメな手なんだろうから調べる回数を減らす
- 証明が与えられているので、安心して使える
- 細く長い一本道の正解しかないような手順に弱い（シチョウとか）
- さまざまなタイプのゲームに対しても有効
- 麻雀とかトランプのような不確定、非完全情報のゲーム
- さめがめとかハーツのような一人ゲーム
- アマゾンズ、Lines of Action
- General Game Playing （その場で今までにないゲームのルールが与えられてそれをコンピュータで解く競技）でもかなりいい成績を出す
- モンテカルロ木探索を使った AI は、自分が優勢だととにかく安全に勝とうとするので、プレーヤー側からするとすごくつまらないゲームになる
- 逆に、コンピュータが負けてるとそのままやってもジリ貧なのが判るので、少しの望みしかなくても勝負手を仕掛けてくるようになる。それをことごとく返り討ちにして勝ったときはすごく楽しい。
- その辺のさじ加減で、エンターテイメントゲーム用の思考ルーチンとしても使えるんじゃないか
- Civilization の思考ルーチンを楽しいものにしてくれると嬉しい、という話
山下 宏「モンテカルロ木探索 実践編」
まじめな語り口調が好感持てた！
- モンテカルロ木探索といっても夢の手法じゃなくて、いろいろ組み合わせないと強くならないよ
- 3x3 のパターンの確率も考慮
- As Move As Fast
- 囲碁の場合、手順が多少前後しても最終的には変わらない？ので、打つ手順に関係なく全ての場所の評価関数を更新してみる（荒っぽいけど、それなりに動く）
- モンテカルロ法で囲碁、将棋 論文へのリンクあり
他
- 聞きたかったこと：ある局面でプレイアウトまでたくさん計算した結果は、次の自分の手のときに再利用するのか？
- 勝てそうな手を調べる回数を増やす、というのはＣＧのモンテカルロ法のレンダリングにおけるインポータンスサンプリングみたいなものなのかな？（インポータンスサンプリングが何かよくわかってないけど）
- もんしょの巣穴blog モンテカルロ木探索