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

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

[人工知能]革新AI囲碁ソフト『Crazy Stone』@モンテカルロ法

1 :名無し名人:2007/10/02(火) 20:34:08 ID:q6BMalXv
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/10/02(火) 20:35:02 ID:q6BMalXv
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万件の対局シミュレーションをランダムに実行した。
これまでのアルゴリズムとは異なり、モンテカルロ法のアプローチでは
非常に簡単に並行処理ができるので、
新世代プロセッサーのマルチコア構造を活用できる。



3 :名無し名人:2007/10/02(火) 20:35:32 ID:q6BMalXv
WN:Crazy Stoneはモンテカルロ法を採り入れたプログラムの
第1号ではありませんでしたが、囲碁ソフトのプログラマーの間で
流行となるほどの成功を収めました。
あなたのアプローチのどこが革新的だったのでしょうか?

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

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

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

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

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

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

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

4 :名無し:2007/10/02(火) 20:55:05 ID:cc5vqih8
>>1
>[日本語版注:KGSは『棋聖堂碁サーバー』の略。

KGSはKGS Go Serverの略じゃないの?

5 :名無し名人:2007/10/02(火) 22:13:19 ID:Htgxnw7g
GNUとかLAMEみたいなもんじゃね

6 :名無し名人:2007/10/02(火) 23:39:05 ID:OoAL5kOl
近い将来ソフトに負けないように、詰め碁、手筋がんばるか。。。

7 :名無し名人:2007/10/03(水) 00:28:02 ID:Wj3nCXqP
>>4
訳段階で虚偽情報を混ぜ込む・・・
何がしたいんだ

8 :名無し名人:2007/10/03(水) 01:10:46 ID:sAM2jiDL
>>4
> KGSはKGS Go Serverの略じゃないの?

Kiseido Go Server の略だよ。

9 :名無し名人:2007/10/03(水) 01:41:00 ID:hdCwv9Kg
>>8
今は違うよ。4は知ってて書いてるんだよ。
2chじゃそういう人よくいるから気をつけて

10 :名無し名人:2007/10/03(水) 01:47:51 ID:hdCwv9Kg
>>1
要するに、下手でも5万人集まって多数決で着手を決めれば
多少はましになる、って理解でいいのかな?

11 ::2007/10/03(水) 02:56:12 ID:6L2W1XL6
>>7>>4の指摘が正しいという意味だからな
http://ja.wikipedia.org/wiki/KGS

12 :名無し名人:2007/10/03(水) 03:06:13 ID:YqBQI+gb
多数決とはちょっと違うね。とにかくランダムに5万局最後まで打
つのが肝要で、あいまいなのは死石も抜いて
中国ルールでやれば最終局面の石数結果は簡単に判る。
変化の勝つか負けるかで勝率計算も自明。
ただ、むやみなランダムでなくパターンや
多少ヒューリスティックな要素を入れて絞っているので強くなる。
序盤はダメだが中盤以降は手筋がでたりそこそこ強い。
碁会所2,3級なら油断するとやられるよ。

13 :名無し名人:2007/10/04(木) 21:29:03 ID:ZlpASQAl
碁解除四段ですが何か

14 :名無し名人:2007/10/05(金) 01:39:56 ID:gxe5XXdA
>>10
5万人の秀才より、1人の天才のほうが激しく強い。
これは越えられない壁。

コンピュータがどんなに時間をかけて計算をしても天才の域には達しない。
そもそも思考の土俵が違いすぎる。

15 :名無し名人:2007/10/05(金) 02:53:44 ID:Bo6LKRsu
5万を50万にするとどれくらい棋力が上がるか興味あるな。
この方法ならコンピュータを並列化すればいくらでも棋力が上がるし。
まあ、ネット初段くらいが事実上の限界の気もする。

16 :名無し名人:2007/10/05(金) 11:53:38 ID:kyCiCWIA
ソフトって、石の連絡を正しく認識するのさえむつかしいような。
例えばケイマをでぎられても利き筋がシチョウあたりでシチョウに抱えられる場合とか。
状況の変化によっては利き筋が利かなくなって激しく振り変わったりするでしょ?
そういう認識をしっかりさせないで、ランダム対局5万局とか50万局とかさせても、ぜったいプロに勝てないと思うんだけどな。。。


17 :名無し名人:2007/10/05(金) 12:01:26 ID:Bo6LKRsu
そういうのをしっかりさせようと色々頑張ったけどあんまり強くならなかった。
モンテカルロ法を応用したらびっくりするほど強くなった。
低いレベルでの話だけどね。
(9路定先でプロに勝ったらしいけど)

18 :一歩:2007/10/05(金) 12:23:21 ID:243Bs6yK ?2BP(0)
>>1-3
までの記述、理論的にただしい。
 しかし、まだ大きな問題点が指摘できる。
  1. 如何にして「勝敗の確定」状態であると認識できるのか。
  2. 読み切りの確定状態になると、失敗の回避は不要になる。
  3. プログラムの主体は、失敗しない上げることになっているが
    形勢が有利な場合はいいけれ、不利に場合にはかえって「勝負手」が打てない


19 :一歩:2007/10/05(金) 12:30:05 ID:243Bs6yK ?2BP(0)
もう1つ、
 この方法は、10級の棋力の人また6段の棋力の人が、
  勝率をあげる手段でつまり、間違いを減らすことで勝率を上げている

  そのため、6級に人が、間違うことによって5級になるという
  人間の成長システムとは、まったく異質のものに思える。

  つまり、
   発展がない世界での、最善の効率を求める
  というように思える。

20 :一歩:2007/10/05(金) 12:40:57 ID:243Bs6yK ?2BP(0)
それを防ぐには...
 失敗の中で、最善の正解を見つけることが必要になる。
 しかし、これには、無駄を省くではなく
          無駄を検証することが必要になる。
  学問的には、無駄の検証ほど、無駄な時間はない。
 
 この矛盾を修正できれば、すばらしい理論的のに確かな発展が期待できそう。


21 :一歩:2007/10/05(金) 13:36:11 ID:243Bs6yK ?2BP(0)
>>14
囲碁の発展は、一人天才の発想でだけで生まれるものではありません。


22 :名無し名人:2007/10/05(金) 14:09:50 ID:JqIRRmnT
うん

23 :名無し名人:2007/10/05(金) 14:39:10 ID:gxe5XXdA
>>21
されど、1人の天才がいなければ発展は激しく遅れるのも然り

24 :名無し名人:2007/10/05(金) 23:54:32 ID:q8Fld3Uc
CrazyStoneに100万局に1局も勝てない日本囲碁ソフトはおよびでない

25 :名無し名人:2007/10/06(土) 00:45:23 ID:8dnZoo1B
もうソフトとかいらね
100目以上差が付くってなんだよカス杉
それにコンピュータの対局中の地合い評価・形成判断って明らかに変なときがあるし。
いや、死なんだろってところを勝手に死に石として数えてたり

26 :名無し名人:2007/10/06(土) 01:11:53 ID:SJiKLifJ
MOGOの9路やれ。

27 :名無し名人:2007/10/06(土) 02:17:52 ID:yVHLrsjo
関連スレ
ttp://game12.2ch.net/test/read.cgi/gamestones/1180110774/l50
ttp://game12.2ch.net/test/read.cgi/gamestones/1161215654/l50

28 :名無し名人:2007/10/20(土) 22:13:41 ID:mRATaQ0g
保守

29 :名無し名人:2007/11/18(日) 09:22:01 ID:RSJ8iHd6
モンテカルロシュミレーションを高速化するにはどうすればいいんですか

30 :名無し名人:2007/11/18(日) 14:59:19 ID:uZ7dUshM
速い CPU を使う,たくさん並列化する,実装を頑張る(bitboard とか)
RAVE を実装する,Progressive widening を実装する,
新しいアルゴリズムを考える

好きな方法を選べ

31 :名無し名人:2007/11/18(日) 15:43:42 ID:RSJ8iHd6
それ以前の段階でつまってますorz
黒白それぞれに可能手をリストアップしてやるのが一般的なのでしょうか?
あとあとビットボードで書いて並列化する予定なのですが・・・

32 :名無し名人:2007/11/19(月) 02:50:54 ID:T75o4YQH
>>29
一時的にでもメモリにアクセスしないこと。
高級言語を使わないこと、動作する環境にあわせたデータ処理を行うこと、
キャッシュメモリを乱すアクセスをしないこと、
メモリアクセスはアドレスに対してシーケンシャルに行うこと、
予測分岐ペナルティを受けないように回数の少ないループは展開して行うこと
プロセッサの得意とする支援機能を熟知し、プロセッサ専用の命令語で
最適化すること。

アルゴリズム自体を別なものにすることw

33 :名無し名人:2007/11/19(月) 02:59:52 ID:T75o4YQH
>>31
メモリを一時に使うような工程を伴なうデータ処理でメモリを扱う
中間処理を行わないこと。
全体の処理を行う前に、それらを求める中間情報や計算位置や検索などは
予め前計算して、重い主処理では参照以外の書き込みを一切しないこと。

複数のCPUでメモリを共有せずに分散できるアルゴリズムを考えること。


34 :名無し名人:2007/11/20(火) 01:41:00 ID:vHuzy7ra
>黒白それぞれに可能手をリストアップしてやるのが一般的なのでしょうか?
普通は空点のリストを持っておいて
合法手か否かは別にチェックする
ただ,Remi, Sylvain とも,高速化は最後にやればいいと言っている
それよりアルゴリズムの方がずっと重要だと
もっとも,二人とも実装は上手だからそう言えるのではあるが
初心者の場合は何度も作り直すつもりで気楽に作るのがいいと思う
まずはとにかく動くものを作ることが大事
一気に凄いものを作ろうなんて考えないこと

35 :名無し名人:2007/11/20(火) 07:16:21 ID:dqur8LVS
>>32,33
なんとなくですが処理の遅い箇所がみえてきました
ありがとうございます

>>34
はじめは黒白双方に可能手をリストで作成していたのですが
効率が悪そうなので空点リストで作っているところです
やはりそちらのほうがメジャーなのですね
ありがとうございます

36 :名無し名人:2007/11/23(金) 15:05:06 ID:5+jAodNG
>>35
作業をしないアルゴリズムほど早いものはない、
つまり可能手リストをその場で作るというのが高速化には不利。
容量を捨てるほど使って全てパターン化、ハッシュ作品で1発検索すれば
解決できるのでは?
九九の計算をするときに暗記しておけば早いのは当然の論理。
このデータを蓄えると莫大な量になる、これを解決するには
パターンを記録するのではなく、規則そのものを記録するしかない
のでしょうね。

37 :名無し名人:2007/12/02(日) 22:44:08 ID:BgwwMCd1
UEC杯が終わりました.参加プログラムは27,一日目は予選で5ラウンド
変形スイス式,2日目は16プログラムによる決勝トーナメントで,結果は:
優勝 Crazy Stone, 以下,勝也,MoGo,AyaMC, GGMC Go, caren,思考錯誤,
きのあ囲碁,RunGo,GNU_ark,迷い子,Boozer,martha,GOGATAKI,
囲碁っぴ,boon−ぶーん−,でした.
Crazy Stone は今日行われた KGS のトーナメントの Open, Formal の
両部門でも優勝し,一日で3つ勝つという快挙を達成しました.

38 :名無し名人:2007/12/03(月) 01:12:14 ID:RdzW0o9b
囲碁って感覚で打つ部分も多いから難しいだろうな。
俺は感覚しか使わないけど

39 :名無し名人:2007/12/03(月) 20:19:34 ID:V8w4U/8M
boonってもしかしてVIPPER?

40 :名無し名人:2007/12/03(月) 20:43:07 ID:OuGz95En
そうです

41 :名無し名人:2007/12/03(月) 20:49:47 ID:OuGz95En
でも囲碁のほうが好きです⊂( ^ω^)⊃

42 :名無し名人:2007/12/03(月) 23:30:38 ID:V8w4U/8M
そうなんだ、応援するぞ

43 :名無し名人:2007/12/22(土) 15:37:58 ID:hsRjSkzT
17日発売の週刊碁の12月24日号に第1回UEC杯の記事が19面全部使って載ってる
24日に次の号が出るから購入は早めに駅の売店で

44 :名無し名人:2007/12/28(金) 22:03:15 ID:jKJDMh50
おっぱいでかい女友達が身長たかいやつって顔でかいからきもいっていってたお


45 :名無し名人:2007/12/28(金) 22:03:49 ID:jKJDMh50
誤爆した 死にたい

46 :名無し名人:2007/12/28(金) 23:33:16 ID:BgLRodPe
あがってるから見てみればwww誤爆乙wwwwww

47 :名無し名人:2007/12/28(金) 23:39:27 ID:J3Avo7Gc
死んでくれ

48 :名無し名人:2008/01/08(火) 20:54:07 ID:S0enMp6j
全数計算すればそれで終わり

49 :名無し名人:2008/01/08(火) 21:33:28 ID:Ympfxz+l
まずは結果を記録するメモリの手配から頼む

50 :名無し名人:2008/01/27(日) 15:23:56 ID:j+skORBb
9路盤において中国ルールを用いた場合
コミが7.5のときと6.5のときの
先手と後手の勝率分かるかたいたら教えてください
分かるところだけでいいのでお願いします

51 :名無し名人:2008/01/27(日) 23:08:46 ID:KI86RF0i
ttp://computer-go.org/pipermail/computer-go/2007-April/009367.html

If some are interested by the results, I just did a test.
9x9 games, MoGo with 3k simulations per move against itself. Of course
this player is much weaker than the one playing on KGS, but at least
it enables me to make thousands games in some hours.

Here are the results (wins for black):
komi 6.5:
1943/3640 (53%)
komi 7.5
1754/3640 (48%)

Sylvain


52 :名無し名人:2008/01/27(日) 23:44:55 ID:j+skORBb
(-人-)どもです

53 :名無し名人:2008/02/11(月) 16:59:31 ID:Fyaug53C
確率で計算していれば100%負ける

54 :名無し名人:2008/03/03(月) 22:45:06 ID:rVFKlbBG
9路MOGO強え〜
白番で勝てね〜


55 :名無し名人:2008/03/07(金) 17:43:34 ID:9wyjY26/
mogo9路強いなあ

56 :名無し名人:2008/03/09(日) 13:33:46 ID:LxIQpPzZ
強い

57 :名無し名人:2008/03/10(月) 20:35:27 ID:m+Qjii25
13路のもごも侮れない。
9路よりは勝てるけど。

58 :名無し名人:2008/04/11(金) 14:19:43 ID:ZY1Xv+/4
初歩的な質問なんですがMoGoが実装しているRAVEってどういうものなんでしょうか
UCTの中で候補手を絞ったりする方法のことでしょうか?
論文が見つからないもので…

59 :名無し名人:2008/04/11(金) 14:20:15 ID:ZY1Xv+/4
あげ

60 :名無し名人:2008/04/11(金) 16:36:16 ID:0U1VY/5T
>>58
こらこらマルチポストは遺憾ぞな

61 :名無し名人:2008/05/04(日) 15:43:23 ID:1dN71nIv
七路コミ6.5で、私黒番必勝のパターンがありますね。
いろいろやってくるかと思ったら、パターンに嵌ってからの変化ばかり。


62 :名無し名人:2008/05/04(日) 21:36:36 ID:X58zhmfr
7路でコミ6.5目は小さいんじゃない? 7.5だとどう?

63 :名無し名人:2008/05/05(月) 17:20:48 ID:oHKi+MRT
コミ7.5で10回に1度くらい負ける。


64 :名無し名人:2008/05/06(火) 00:54:27 ID:a0zZ5Jnz
相手はMoGoですよね.4コア相手にそれならプロレベルでしょ.

65 :名無し名人:2008/05/06(火) 15:09:44 ID:xfjHWPR2
Crazy Stoneって、MoGoなの?
4コア?
誤爆?


66 :名無し名人:2008/05/06(火) 19:47:08 ID:E7s9nFyg
ググレカス(AA略

67 :名無し名人:2008/05/07(水) 09:13:20 ID:ni5AHZgJ
MoGoは7路には対応してないはず。GNU Go?

68 :名無し名人:2008/05/07(水) 23:35:34 ID:2V8nHRzv
>>61
7路盤は人間の研究によれば、黒9目勝ちという結果が出ている。
なのでコミ6目半とか7目半なら黒かなり有利だと思われる。

もちろんしらみつぶしで証明されたわけじゃないが、
コミ8目なら紛れなく黒が勝てると思う。


69 :名無し名人:2008/05/08(木) 12:22:09 ID:QZEgB9JR
まさに>>68
実際に証明はされてるのは5路までだが6路と7路はプロが出した値があったはず
ちなみに9目は中国ルールだったかな

70 :名無し名人:2008/05/08(木) 13:41:56 ID:wIxjqk5D
>>68,69
> 7路盤は人間の研究によれば、黒9目勝ちという結果が出ている。

面白そうな話ですね。
よろしければ出典を教えてください。

71 :名無し名人:2008/05/08(木) 14:04:42 ID:6HkPsIKA
ttp://olive.zero.ad.jp/qin/7ro/
ほい。日本ルールでも中国ルールでも一緒らしい。
ただし、なんかjavaに問題があってみられない。

72 :名無し名人:2008/05/09(金) 00:51:40 ID:/YRpw+Ut
手が白番で終わってるから日本ルールでも同じみたいですね

73 :名無し名人:2008/09/07(日) 21:07:04 ID:3k6KRIbl
hoshu

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

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

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)