[人工知能]"Crazy Stone"@モンテカルロ法

Brendan Borrell　2007年05月11日

その昔、人工知能(AI)マニアが関心を向けるゲームと言えば、
何と言ってもチェスだった。
しかし、チェスでは物足りなくなったマニアたちは、
次なる狙い目として「碁」を選んだ。
だが、なぜ碁なのだろう？

碁の起源はチェスより1000年以上古く、
碁における石の手数は宇宙に存在する原子の数よりも多いと言われる。
だが、さらに重要なのは、囲碁の場合、コンピュータープログラムが
人間の囲碁の名手に勝ったことが一度もないという点だ。

世界中で、熱心なコード開発者たちがコンピューター囲碁の
メーリングリスト上でプログラム開発の秘訣をやりとりし、
『KGSコンピューター囲碁トーナメント』
[日本語版注：KGSは『棋聖堂碁サーバー』の略。
神奈川県茅ヶ崎市にある棋聖堂が運営している]で、
毎月腕を競い合っている。

2005年には、フランスのリール大学に所属するコンピューター科学者、
Remi Coulom氏が提起した新戦略が、既存の手法に革命的な変化をもたらした。
Coulom氏のプログラム『Crazy Stone』は、
2006年5月から6月にかけてイタリアのトリノで開催された
第11回『コンピューター・オリンピアード』で、金メダルを獲得している。
Coulom氏は先ごろWired Newsの取材に応じ、
囲碁ソフト作成の難しさやCrazy Stoneの成功の秘密について語ってくれた。

[日本語版：ガリレオ-藤原聡美／長谷 睦]

WIRED NEWS 原文(English)
http://wiredvision.jp/news/200705/2007051121.html

Wired News(以下「WN」)：囲碁ソフトのプログラミングが
チェス用のソフトより難しい理由は？

Remi Coulom氏：碁では、[チェスのような形で]相手の石を取ることはない。
だから、黒が優勢なのか白が優勢なのか、盤面を見ただけでは判断できない。
勝ち残るためには、自分の石で2つの「目」
――相手に侵略されない空白の陣地――を囲む必要がある。

囲碁では、縦と横、19本の線が引かれた碁盤の上に石を置いていくわけだが、
それが生きた石になるか死んだ石になるかは、打った時点ではわからないので、
静的分析が非常に難しい。ここがチェス(あるいはチェッカー)と状況が違うところだ。
チェスならば、盤面を見て「わたしの方がポーンを1個多く持っている」と言えるのだが。

WN：「モンテカルロ法」とはどういうもので、どのように碁に応用されているのでしょう？

Coulom氏：モンテカルロという名前は、
カジノで有名なモナコの一地区にちなんでつけられたものだ。
碁の場合の基本的な考え方はこうだ。
次の一手の選択肢を評価するために、
まずは何千通りもの対局をランダムにシミュレーションする。
その上で、その手を打った場合、白よりも黒が勝利をおさめる傾向が強いとすれば、
その手が黒にとって有利だと判断できる。

WN：一般的な碁の対局では250手を要することを考えると、
それをシミュレートするには、非常に処理能力が高いコンピューターが必要なのでは？

Coulom氏：トリノのオリンピアードで使用したバージョンのCrazy Stoneでは、
CPUを4つ――米Advanced Micro Devices社製のデュアルコア・プロセッサー
『Opteron』(2.2 GHz)を2つ――搭載したマシンを使い、
1秒あたり約5万件の対局シミュレーションをランダムに実行した。
これまでのアルゴリズムとは異なり、モンテカルロ法のアプローチでは
非常に簡単に並行処理ができるので、
新世代プロセッサーのマルチコア構造を活用できる。

WN：Crazy Stoneはモンテカルロ法を採り入れたプログラムの
第1号ではありませんでしたが、囲碁ソフトのプログラマーの間で
流行となるほどの成功を収めました。
あなたのアプローチのどこが革新的だったのでしょうか？

Coulom氏：すべての対局をしらみつぶしにサンプリングすることは不可能なので、
モンテカルロ法のアルゴリズムでは、最良の一手を見つけられない場合もよくある。
たとえば、特定の一手を打った時の対局シミュレーションの結果が、
大半が負けで、1つだけ勝てるパターンがあったとする。
基本アルゴリズムは結果の平均値を取り、
そこに石を置くのはよくないと判断する。

Crazy Stoneは、この問題を回避できるようプログラミングされている。
1つの手から生じる一連の流れが他の手よりよいと気づけば、
シミュレーションの中でもその流れを重点的に取り上げる。

WN：KGSトーナメントの進行役を務めるNick Wedd氏のように、
モンテカルロ法を採り入れたプログラムの対局は、
見ていて退屈だと不満を述べる人もいるが、
それはなぜでしょう？

Coulom氏：モンテカルロ法によるプログラムは、
勝利の可能性を最大限にするもので、
大差で勝つことを目指していない。
相手よりはるかに有利な状況になると、
必ず安全最優先のモードに移るので、
攻め姿勢の対局に比べると、見ていて退屈だと感じるかもしれない。
見るにはつまらないかもしれないが、
ゲームで勝利をおさめるにはより効率のよいやり方だと思う。

WN：優れた囲碁ソフトの作者は、多くが自身も優秀な棋士だと聞くが、
あなた自身の囲碁の腕前は？

Coulom氏：最初の囲碁用プログラムを書く前には、
わたし自身も、世に出ている他のプログラムを打ち負かせるくらいには
強くなろうと心に決めていた。だが、
強い棋士であることが、強いプログラムを書くために重要だとは思わない。
そのことは、わたしがチェス用のプログラムを書いていた時からはっきりしていた。
わたしが作ったプログラムはわたしよりはるかに強かったからだ。

今出回っているプログラムの中には、
「定石」と呼ばれる、昔から最善とされている
決まった石の打ち方を用いるものがあるが、
わたしはこうした既存の知識をあらかじめコードに組み込むことは避けている。
無条件に定石を当てはめたために勝ちを逃すプログラムもあるのを知っているからだ。

目的への情報が拡散し収束しないのに１票。

で、結局「モンテカルロ」って食えるのか？

立てる板間違えた？

理系カテゴリーでも相手にされないな
まあ試してごらんｗ

階層構造のないモンテカルロなんて、ゴミと同じだろ。
条件反射で動くことしかできない脳のようなものｗ

アルゴリズムってのはそもそも条件反射の集積だろ。

>>10
人間は条件反射以上のことができる。いつまでたっても。ウリナラ思考なのか？
コピーではなく、創造できなければ猿レベルだと思わないか？

モンテカルロ法って乱数使ってるだけでしょ。
アルゴリズムに活気性はないように感じるが、
並列処理ができるという利点ではよい。
CPUをつければより強くなる。
他の分野にも適用できそうだね。

碁のアルゴリズムに統計が応用できると
わかったのが画期的だったんじゃないかな
生存のルールを定めてやれば、あとは自然に最適解に向かうという
なにやら自然界の遺伝アルゴリズムにも通じるものがある

>>11
日本語でおｋ

>>1
いい評価関数がなくても使えるのが画期的なモンテカルロ
でも囲碁と違って将棋は初段でもほぼ正確な形勢判断ができる
適当な評価関数作れる将棋じゃいらない子だよ

>>5-13
UCTアルゴリズムは学習が進むと徐々に前向きの枝刈りへ変化するよ
昔の知識で語ってる人がいっぱいいるよーな

>>15
暴走することができないアルゴリズムでは狭い論理集合の状態に収束して
しまい、学習は狭い論理でしか行われない。
つまり次元が違う読み合いが複雑化する戦いには学習は無意味になりえる。

学習した答えは相手の力量によって間違った答えになるからである。

>>16
まだ理想のコンピュータ囲碁のアルゴリズムが
どのくらいの規模の論理集合で表現できるのか誰も知らない
基準が存在しないのに狭いとかいっても何の説明にもならないよ
現に囲碁では強いプログラムがあるので今のところ有効なのは明らかだし
UCTを改良していってもし性能が伸び悩むようだったら
そのとき別のアルゴリズムを考えるのが現実的な方策でしょ

>>16
UCT/UCBの収束具合は自由に調整できるし
最終的に最善手に収束することが保証されているから
その心配は無用
それに学習って言っても毎回忘れちゃうオンライン学習だし

囲碁プログラムにはトポロジーが有効。

乱数を使う＝モンテカルロならば、別に目新しいことでもないな。
しらみつぶしができないから、次の１手をエイヤで決めてしまうような。

>>20
憶測で語ってないで論文嫁よ。せっかく加藤さんが翻訳してくれてるんだし。
ttp://www.geocities.jp/hideki_katoh/

>>21
どこがすごいのか全くわからん。
逝った香具師なら希望的な情報なら無条件で理解しているという話じゃないか？

>どこがすごいのか全くわからん。
Coulom氏が誰もがダメだと信じていたモンテカルロ法の
欠点を回避する方法を発明したってとこがすごいんじゃないかと。
モンテカルロ法の欠点は指摘するのに、その発明には一切触れない人は
論文読んでないか理解できないんだと思うけど、違うのかな。

次の１手は、最終的に現在の最良の手を変更する可能性が最も高い手を
統計的に推定してそれを選択する。
まだ一度も選んだことのない手に関しては推定ができないので、
事前にありそうなパターン関して統計をとってレートをつけておき
レートの高い手ほど高確率で選択するようにする。
そこで初めて乱数が出てくる。
エイヤとかそんな適当じゃないよ。あとは論文読んで。

>欠点を回避する方法を発明したってとこがすごいんじゃないかと。
そう思っただけじゃないのか？
そもそも誰かが検証できたわけ？
論文の閲覧数ではたいしたことはないようだけど

>>24
> そう思っただけじゃないのか？
> そもそも誰かが検証できたわけ？
それ言い出したらきりないだろうｗ
あなたが検証して、問題が見つかったら公表すれば良いだけの話

だれか普通の9x9将棋に適用よろしく。
ttp://ci.nii.ac.jp/naid/110006345248/

しかし他力本願だなぁ

オマエがやれ、証明しろ、定義しろ、んなことはない。
なってほしい。教科書を読め、論文を読め、検証しろ。

　

しかし他力本願だなぁ

オマエがやれ、証明しろ、定義しろ、んなことはない。
なってほしい。教科書を読め、論文を読め、検証しろ。

あ

読んでみたけど、これって将棋・チェスより囲碁・オセロの方に向いてるっぽいね。

ゲームでの勝負とは

１．理屈と理屈の勝負（未決定勝負なら確立の問題）
２．心と心の読み合いの勝負（負けへの恐怖心で相手の行動を縛る）
３．相手の思考論理規則（つまり特徴の観察）

だいたいこの３つで勝負が決まる。
単純なゲームほど２と３が重要となり。
ルールや仕組みが複雑なゲームほど１が重要となる。
コンピュータが行うアルゴリズムは１でしかない。
相手が究極に論理的であれば、行動を縛るのは容易で疑うことなく
その場で計算できる最善手（最も確立の高いもの）しか選ばない。
どちらでも等価と判断される場合に行う行動は癖や特徴として現れる、
その判断基準の特徴の域で相手の行動は本来の確立が５０％、５０％な
物と判断されても、１００％その行動になると予測されてしまう。
ルールや仕組みでは予想できない選択部分は等価としか判断できない。
過去で勝ったパターンで学習すれば行動が読まれてしまう。次も同じ
判断をするだろうという確立のアンバランスである。
つまり最初にだした２や３は１が完璧なほど予測するのが安易になる。
例え等価部分の判定をランダムにしてもランダムという特徴を読まれて
しまえば擬似乱数の一様の特徴（どの数も確立が一定になりやすい）からの
確立分析でランダムすら予測可能である。

確率

過去律

アカギて誰？

確率で計算していれば１００％負ける

age

 コンピュータが囲碁でプロの棋士に勝利（ただし９路）
ttp://slashdot.jp/article.pl?sid=08/03/28/0611252

機械の判断とは、１度やった成功は２度目も繰り返す。

これほど合理的な判断はない、しかし、２度目も同じだと判断することが
負けに繋がることすら判断できないのが機械の愚かさである。
２度目はわざと踏ませた地雷なのに。

人間ならば２度目の負けは疑うものだろう、しかし機械は疑わない
何故なら理屈だけでうごいているからだ

達人になればなるほど合理的すぎることこそ相手の力量を判断し
危険な雰囲気を感じ取れる。この体験からくる感覚は機械には無い機能である。
何故なら機械には恐怖心というものが存在しないからだ。
必然的に勝利しかありえない理屈なら考えずに選ぶだろう。
高性能が故に１００歩先まで読めても２００歩先は読めない。
小さい勝利が、大きな負けの落とし穴に誘導するための布石になっていること
すら理解できない。何故なら機械には心がないから。
それは１００％読みきったときにしか確実に機能しない近似値にすぎないから。
偶然が巨大なサイクルでバランスを保とうと確率を歪ませていることに
気がつかない。それは目の前の合理性しか掴めない単純な仕組みだから。