2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :名無し名人:2007/09/28(金) 10:26:04 ID:F7i/xrOP
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

2 :名無し名人:2007/09/28(金) 10:26:55 ID:F7i/xrOP
Wired News(以下「WN」):囲碁ソフトのプログラミングが
チェス用のソフトより難しい理由は?

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

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

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

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

3 :名無し名人:2007/09/28(金) 10:27:25 ID:F7i/xrOP
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つの手から生じる一連の流れが他の手よりよいと気づけば、
シミュレーションの中でもその流れを重点的に取り上げる。

4 :名無し名人:2007/09/28(金) 10:28:03 ID:F7i/xrOP
WN:KGSトーナメントの進行役を務めるNick Wedd氏のように、
モンテカルロ法を採り入れたプログラムの対局は、
見ていて退屈だと不満を述べる人もいるが、
それはなぜでしょう?

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

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

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

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


5 :名無し名人:2007/09/28(金) 15:06:33 ID:fIg3EiUk
目的への情報が拡散し収束しないのに1票。


6 :名無し名人:2007/09/28(金) 15:12:21 ID:qQpmJgZH
で、結局「モンテカルロ」って食えるのか?

7 :名無し名人:2007/09/28(金) 17:40:35 ID:7xkThOYd
立てる板間違えた?

8 :名無し名人:2007/09/29(土) 01:36:45 ID:DSm6HeCC
理系カテゴリーでも相手にされないな
まあ試してごらんw

9 :名無し名人:2007/09/30(日) 00:31:41 ID:7iIuVwn6
階層構造のないモンテカルロなんて、ゴミと同じだろ。
条件反射で動くことしかできない脳のようなものw

10 :名無し名人:2007/09/30(日) 01:09:39 ID:5YkuiTG1
アルゴリズムってのはそもそも条件反射の集積だろ。

11 :名無し名人:2007/10/01(月) 01:28:07 ID:Q2xt0Wn/
>>10
人間は条件反射以上のことができる。いつまでたっても。ウリナラ思考なのか?
コピーではなく、創造できなければ猿レベルだと思わないか?

12 :名無し名人:2007/10/01(月) 03:28:39 ID:VAoydR/c
モンテカルロ法って乱数使ってるだけでしょ。
アルゴリズムに活気性はないように感じるが、
並列処理ができるという利点ではよい。
CPUをつければより強くなる。
他の分野にも適用できそうだね。

13 :名無し名人:2007/10/01(月) 11:29:54 ID:kTS2CkZr
碁のアルゴリズムに統計が応用できると
わかったのが画期的だったんじゃないかな
生存のルールを定めてやれば、あとは自然に最適解に向かうという
なにやら自然界の遺伝アルゴリズムにも通じるものがある

14 :名無し名人:2007/10/02(火) 00:56:54 ID:MsBG4A8V
>>11
日本語でおk

15 :名無し名人:2007/10/02(火) 01:17:00 ID:28h/MbQo
>>1
いい評価関数がなくても使えるのが画期的なモンテカルロ
でも囲碁と違って将棋は初段でもほぼ正確な形勢判断ができる
適当な評価関数作れる将棋じゃいらない子だよ

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

16 :名無し名人:2007/10/02(火) 17:21:51 ID:ddUNToRb
>>15
暴走することができないアルゴリズムでは狭い論理集合の状態に収束して
しまい、学習は狭い論理でしか行われない。
つまり次元が違う読み合いが複雑化する戦いには学習は無意味になりえる。

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



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

18 :名無し名人:2007/10/03(水) 03:57:27 ID:6SC+aFjj
>>16
UCT/UCBの収束具合は自由に調整できるし
最終的に最善手に収束することが保証されているから
その心配は無用
それに学習って言っても毎回忘れちゃうオンライン学習だし

19 :名無し名人:2007/10/03(水) 21:04:38 ID:kY1xKQv6
囲碁プログラムにはトポロジーが有効。

20 :名無し名人:2007/10/03(水) 22:33:06 ID:cYHoExcp
乱数を使う=モンテカルロならば、別に目新しいことでもないな。
しらみつぶしができないから、次の1手をエイヤで決めてしまうような。

21 :名無し名人:2007/10/04(木) 02:22:23 ID:B7QerBJN
>>20
憶測で語ってないで論文嫁よ。せっかく加藤さんが翻訳してくれてるんだし。
ttp://www.geocities.jp/hideki_katoh/

22 :名無し名人:2007/10/04(木) 13:58:33 ID:rNNafD5o
>>21
どこがすごいのか全くわからん。
逝った香具師なら希望的な情報なら無条件で理解しているという話じゃないか?


23 :名無し名人:2007/10/04(木) 21:01:18 ID:HalEq+Lp
>どこがすごいのか全くわからん。
Coulom氏が誰もがダメだと信じていたモンテカルロ法の
欠点を回避する方法を発明したってとこがすごいんじゃないかと。
モンテカルロ法の欠点は指摘するのに、その発明には一切触れない人は
論文読んでないか理解できないんだと思うけど、違うのかな。

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

24 :名無し名人:2007/10/06(土) 00:25:38 ID:dQin5MoQ
>欠点を回避する方法を発明したってとこがすごいんじゃないかと。
そう思っただけじゃないのか?
そもそも誰かが検証できたわけ?
論文の閲覧数ではたいしたことはないようだけど

25 :名無し名人:2007/10/06(土) 07:15:56 ID:jtnBarod
>>24
> そう思っただけじゃないのか?
> そもそも誰かが検証できたわけ?
それ言い出したらきりないだろうw
あなたが検証して、問題が見つかったら公表すれば良いだけの話

26 :名無し名人:2007/10/07(日) 14:30:04 ID:1wuPXIFW
だれか普通の9x9将棋に適用よろしく。
ttp://ci.nii.ac.jp/naid/110006345248/

27 :名無し名人:2007/10/09(火) 04:46:11 ID:sjj9CHbA
しかし他力本願だなぁ

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



12 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)