Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2007-03-06 コンピュータ囲碁におけるモンテカルロ法

[][] コンピュータ囲碁におけるモンテカルロ法  コンピュータ囲碁におけるモンテカルロ法を含むブックマーク  コンピュータ囲碁におけるモンテカルロ法のブックマークコメント

コンピュータ囲碁の入門

コンピュータ囲碁GREAT―プログラムの作り方とネット対局の実際


オセロチェス将棋囲碁のようなゲームは終局状態は簡単に定義できる。「こういう形になればゲームセットである」と判定したり、その状態の先手の勝ち負けを判定するプログラムは簡単に書ける。


だけど、ゲームの途中でどちらが有利なのかを判断させるためには、適当な評価関数を用意しなければならない。これらのゲームに共通してそういう性質がある。


そのなかでもコンピュータ囲碁はそれらのプログラムのなかでも最も難しいとされている。うまい評価関数を作成すること自体が難しい。


将棋ならば駒を得しているかだとか、王のまわりは安全かだとか駒の働きはどうかだとかそういったパラメータを導入する。それらのパラメータは熟練したプレイヤ(人間)が経験的に知っているものであり、ゲーム終了の局面から何らかの方法で逆算したものではない。


序盤で王を囲っておかないと、終盤で相手に駒を渡したときに詰みやすいが、いまのコンピュータ将棋アルゴリズムでは序盤の局面において終盤付近まで読む(探索する)ことは不可能なので、評価関数に手心を加えてやる必要が出てくるのだ。


Mathematical Go: Chilling Gets the Last Point

だけど囲碁では手心を加えようにもどう加えていいのかお手上げに近いものがある。どの石が終盤に生きてくるのかを定式化するのはとても難しいからである。一方、モンテカルロ法をコンピュータ囲碁に応用するという手法がある。


現在の局面からでたらめに打っていき、終局させてみる。終局状態は簡単に判定できるから、9路盤ならばいまどきのパソコンなら秒間に1000万局ぐらい終局までシミュレーションしてみることが出来る。(と思う)


そのうえで、たくさん自分勝ちの終局状態があるところに着手する。たったこれだけのアルゴリズムであるが、これが結構強いのである。いままでの囲碁プログラムは何だったのだ、という感じだ。「たくさん優勢になる変化があれば優勢」というのは、この手のゲーム共通の性質だ。


たった一つの受けの好手があってその変化によって敗勢になることもあるので、なかなか難しいものがあるとは思うが、こんな単純な手法でそれなりの成果があがるというのは大変興味深い。

yaneuraoyaneurao 2007/03/05 01:41 コンピュータ将棋にも応用は利きそうではあるが、将棋の場合、駒得とか厚み、位(くらい)、駒の働き、王の堅さ、広さ、敵の攻めからの遠さなど定式化しやすいパラメータがほとんどなので、モンテカルロ法の出番は無いと思う。

yaneuraoyaneurao 2007/03/05 01:45 ある程度深く読めば、静止評価関数がちゃらんぽらんでもそれなりに効果があがるというのは、コンピュータ将棋にも言えていることである。よく「どれだけコンピュータ将棋の終盤がつよいと言えども序盤がよわよわなのでプロには勝てない」という見方があるが、探索量が増えるに従って序盤も自動的に強くなっているところを見ると、このままコンピュータが速くなれば序盤でもプロに勝てるのではないかと思う。

yaneuraoyaneurao 2007/03/05 06:36 オセロにもモンテカルロ法が応用できそうではあるが、オセロはいまどきのマシンだと序盤の定跡を抜けたところで終局まで読み切れるのでほとんど意味がないのではないかと思う。でもお手軽に実装できるので楽しそうではある。

yaneuraoyaneurao 2007/03/05 06:38 終局での勝ち負けが簡単に判定できて、かつ中盤での評価関数のチューンが大変難しいゲームはいっぱいあるので、それらのゲームで簡単な実装でそれなりの効果が出せるのは頼もしい。モンテカルロ万歳。

fkmfkm 2007/03/05 08:44 囲碁の場合、PS3×10台ぐらいのクラスタでシミュレートしてやると格段に強くなる感じなのでしょうか??

yaneuraoyaneurao 2007/03/05 09:00 台数に対してどれくらい強くなるのかは知らないけども(´ω`)
数が増えると安定度が増すだけで、そんなに強くならない気もする。

とりすがりとりすがり 2007/03/05 10:20 モンテカルロって美味しそうだよね(*´・ω・)(・ω・`*)ネー

yaneuraoyaneurao 2007/03/05 10:22 モンテ甘露ならとても甘そうだ。

取り縋り取り縋り 2007/03/05 10:42 モンテカルロで法で「当たりが出そうな所を重点的に狙う」ってな話がそういえば最近あったですよhttp://www.itmedia.co.jp/news/articles/0702/22/news054.html

yaneuraoyaneurao 2007/03/05 11:27 はい、実はその記事に触発されて今日のエントリを書きました。その記事のソフトウェアの方法は、おそらくモンテカルロするときに「当たりになっている石は30%の確率でつなぐ」などの統計情報をもとに、(この場合なら)30%の確率でつなぐ手を選ぶんではないですかね。

コンピュータ将棋だと激指が、そういう表層的な確率を利用して探索してますので、そんなに画期的な手法ではないと思います。モンテカルロ法はいくらでもその手の工夫の余地はありますね。

yaneuraoyaneurao 2007/03/05 18:16 しかし、↑*2の IT mediaの記事は、知らない人にはさっぱりわからないような書き方がしてありますね。「なんでスロットマシンに例えるんや(´ω`)」とか思いました。

ダンカンダンカン 2007/03/05 18:23 モンテカルロ法ってコマ大っぽくていいよね。

yaneuraoyaneurao 2007/03/05 18:24 うむうむ。(探索の)量は質を創り出す。

HYHY 2007/03/05 23:17 ↑スロットマシンに例えたのは,モンテカルロという名前がカジノの町からとられたからじゃないでしょうか.モンテカルロ法の重点的サンプリングは他の分野でもやってますね.レンダラとか.

yaneuraoyaneurao 2007/03/06 00:02 ↑素晴らしい洞察

GusGus 2007/03/06 21:35 通りすがりですが、
http://zaphod.aml.sztaki.hu/papers/ecml06.pdf
ITmediaの記事のねたはたぶんこの論文だと思います。
スロットマシン云々は、multiarmed bandit problemというものを指しているんだと思います。私もよくわかってません、すみません

yaneuraoyaneurao 2007/03/07 00:28 情報ありがとうございます。のちほど読んでみます。

yaneuraoyaneurao 2007/03/07 08:30 http://www.weddslist.com/kgs/past/24/

3月4日のコンピュータ囲碁の大会において19路盤で、モンテカルロ法を採用したプログラムが優勝しました。追い風になるかも。

yaneuraoyaneurao 2007/03/07 08:39 追記。IT mediaの記事にあるプログラムは上記の優勝したMoGoを指しているのだと思われます。

あと加藤さんがMoGoの論文(RR-6062.pdf)を訳されてたので紹介。
http://www.geocities.jp/hideki_katoh/RR-6062-v3-jp.pdf

yaneuraoyaneurao 2007/03/07 13:19 モンテカルロ囲碁はGPGPU向きと思うのだけど誰ぞ実装しないか。> GPGPUで

sunasuna 2007/03/07 17:40 ここでMoGoの存在を知って、実際の対局を見てみましたがまだまだ弱いという印象を受けました。わけのわからない手が他のぼっとに比べて多すぎなので、演算能力がアップしてもこの方式で本当に強くなるのかな?
それでも、結構勝ててるのが不思議ですが。

yaneuraoyaneurao 2007/03/07 17:49 19路盤では3〜5級ぐらいなんですかね。少し改善したらじきに初段ぐらいにはなりそうですけど。

トラックバック - http://d.hatena.ne.jp/yaneurao/20070306
 | 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06