俺主催囲碁プログラミングコンテスト

[1 デフォルトの名無しさん NG NG]

俺に勝てたら、賞金が出ます

[281 デフォルトの名無しさん NG NG]

別の隅を評価しながらの布石は、結構厄介だった。

[282 デフォルトの名無しさん NG NG]

>>281
それはかなり高度な部類に入るかと・・・。
実際、それを生かすだけの棋力を持つプログラムは存在しないと思われ。

[283 278 NG NG]

定石データベース＋αβ探索だけで囲碁を作って見て思ったんだけど、
人間の脳ってなんであんなにすごいんだ？

[284 デフォルトの名無しさん NG NG]

囲碁は特に画面認識とか、人間の脳に向いている作業が多いからね。
しかし、αβということはまともに探索してるの？
それはすごいね。

[285 デフォルトの名無しさん NG NG]

学習して、自ら改善するっていうプログラムじゃないんだよねぇ。
なら、実際に打ってみて足りない点を逐一カバーしていくってのが
いいと思うよ。
つーわけで、遊ばせてくださイ。ちゃんと報告するから。
　　　　　　　　　　　　よろしく。

[286 278 NG NG]

２ｃｈネラーだという事がばれると
なんか恥ずかしいのでそれは勘弁して>>285

それに、弱すぎてやっても意味ない。

αβに関してだけど、現状の評価関数だとほとんどやっても意味ないかも。
コンピューター同士で対戦させて
どのくらい読みが的中するのかを調べたところ
打つ場所の残りが１０箇所くらいになって
当たりだすくらい。

それに１９＊１９だと
最初の幅優先探索がえらく時間がかかる。

それをふまえて、自分がどうやっているのか
検証してみたんだけど・・・・

[287 デフォルトの名無しさん NG NG]

無料の囲碁のフレームワークってないですかねぇ。
ルールを組み込むのがすごく大変で。

[288 デフォルトの名無しさん NG NG]

ここを見てみたら。
http://www.inventivity.com/OpenGo/

[289 デフォルトの名無しさん NG NG]

>>288
ありがと。
これでAI作りに専念できそうです。

まずは探索から実装してみます。

[290 minikat NG NG]

ルールは狭義には、コウと自殺手判断ぐらい。厳密には終局計算を含む。
昔アップルIIの囲碁ソフトはウッテガエシが打てなかったよ。
返品しようとおもったがそれ以外なかった。
どのルールも１石の自殺手はできないがSSTルールやニュージーランドルール
は認めている。
日本ルールではセキは地にならないが、中国ルールではなる。
とにかく市販ソフトでもセキ判断は完全でないのでルールが完璧とは
いえないのでこちらまかせ。　
でもルール作りのハードルが高いならシチョウ、ゲタなんてもっと大変よ。
がんばってください。

[291 minikat NG NG]

＞＞どのルールも１石の自殺手はできないがSSTルールやニュージーランドルール
は認めている。
スマン。表現がおかしい。
多石の自殺手を認めているという意味。

[292 デフォルトの名無しさん NG NG]

ルールなんか 日本ルールに 決まってるだろ

[293 デフォルトの名無しさん NG NG]

とりあえず五路地盤のを作ってみたら？

[294 ニュージーラン土人 NG NG]

ジャップ消すゾ

[295 デフォルトの名無しさん NG NG]

もう少しにぎやかにならないかな。

[296 デフォルトの名無しさん NG NG]

着手生成アルゴリズムってどんなのがあるの？

[297 デフォルトの名無しさん NG NG]

パターンが楽なんじゃないの？
こんな形は１間で、これは2間、ケイマ、とか色々。

[298 デフォルトの名無しさん NG NG]

候補手列挙を学習する方法ってない？
例えば、パターンだったら
探索した結果良いものを集めてデータベース化していくと。

でも、パターンだとマッチングが大変じゃない？
ある点が候補としてあげられるかは
その点の付近のパターンを、データベースで比較しなくてはならない。
ハッシュを使えばいいのかな。

[299 デフォルトの名無しさん NG NG]

学習だったらプロ棋士の棋譜を使えばいいんじゃない？
たしか公開されてたはずだしね。

パターンマッチングの高速化はどうするんだろうね。
データベースをハッシュでまとめてしまえば高速で可能なような気もする。
完全一致から似ている形まで、とかなると難しそうだけど。

あと、単純なパターンだとうまくいかないかもね。
この石はシチョウで取られる、とか、ダメが２以上ある、とか
色々な情報をパターンの中に組み込む必要があるかも。
ここに打った場合の手順とかも。

[300 デフォルトの名無しさん NG NG]

データがあっても、アルゴリズムがないとね（藁

似ている物まで探してくるのは無理だと思うなぁ。
似ているの基準から定義しないとわからんけど。

>あと、単純なパターンだとうまくいかないかもね。
候補を列挙するだけだからいいんじゃない？
あとは、それを探索するだけ。

[301 minikat NG NG]

ハッシュよりも実プログラムでは２分木探索が速いという報告もありムヅ。
普通に照合するよりは何十倍か早いだろうけど。
パターンは骨格と肉付けがあり、２０年前の同級生で様子が違ってもある程度
認識できるのと似ている。黒、白、空点と、黒白空点どちらでもいいというのが厄介。
rotationで８種類、反転で１６種類ある。広さの問題もあるなあ。
人間は碁をやって入ればますます、パターン認識は早くなるが、機械は照合に
ドンドン時間が食われる。ここに根本的な問題ありだろ。
AI囲碁で２０００くらい。最初手入力してたらしいが途中からBITMAPにして
グラフィックエディターで入力したらしい。うまいね。

[302 デフォルトの名無しさん NG NG]

学習のアルゴリズムかぁ。
分からんね（ｗ
完全一致で出現した回数とかなら簡単だけど。

大量の棋譜から学習で楽をしよう、というのは誰もが誘われる麻薬みたいな
もの？だが実際は少数のパターンを人間が自分で判断して打ち込んだほうが
精度の高いものが出来そうな気もする。
何より、プログラムがその手をなぜ打ったかを推理できるからね。

[303 デフォルトの名無しさん NG NG]

>ハッシュよりも実プログラムでは２分木探索が速いという報告もありムヅ。
２分木にする時のキーとして、何を使うの？
それがハッシュコードなら
ハッシュテーブルの大きさによると思うよ。

似てる物を集めてくるのはちょっとつらいよね。

>だが実際は少数のパターンを人間が自分で判断して打ち込んだほうが
>精度の高いものが出来そうな気もする。
おそらくそうだと思う。
だから、外からのデータを与えるんじゃなくて
自分でデータを生成検証して、候補手を生成するアルゴリズムを
学習するようなものがいいね。

[304 デフォルトの名無しさん NG NG]

あらかじめ、全ての手を計算しておいて、データベース化しておく。
データベースの構築には、膨大な計算力とディスクスペースが必要なので、
SETIのように分散処理で解決。
データベースができた後は、最善手のみが打てる。

一度プロジェクト起こしてみては？
それなりに金になると思うぞ。
あと、首謀者は地位と名誉も得られる。

[305 デフォルトの名無しさん NG NG]

もし、それで碁の必勝法がみつかれば、歴史に名が残るね。
少ない資金で多大な効果が得られる、数少ないプロジェクト。
早い者勝ちだぞ。

[306 デフォルトの名無しさん NG NG]

相手が知ってたら意味ないじゃ〜ん

[307 デフォルトの名無しさん NG NG]

お前ら・・・囲碁の可能な局面の数は
3^19^2 = 10^230 にもなるんだぞっと。

[308 デフォルトの名無しさん NG NG]

完全解析したらゲーム自体消滅

[309 デフォルトの名無しさん NG NG]

3^19^2 ＝ 1350851717672992089 ≒ 10^18
1千万台(10^7台)のコンピュータを使えば、10^11回の演算で済む。
1台のコンピュータが1秒に3170回の演算が行えるとして、10年間。
現行の性能では難しいが、将来は可能になるかもしれない。
可能になった時点で、誰が先に演算を終えるか？
先に演算を始めた者に決まってる。

[310 デフォルトの名無しさん NG NG]

オセロならもっと早く演算が終了する。
早い者勝ちだぞ。
ゲームを消滅させろ。

[311 minikat NG NG]

>>２分木にする時のキーとして、何を使うの？
パターンをbit化すればいいのと違うかな？
>>ハッシュテーブルの大きさによると思うよ。
そうだね。やって見ないとわからない。ハッシュの計算や衝突の際の探索も時間がかかるし。
でも２，３千のパターンではアマ初段には間に合わない。
瀬越の手筋辞典や官子譜見たらとんでもない筋やパターンがでている。
NHK囲碁の解説聞いていても「これは筋ですねえ」といわれても、知らない、わからない
のが結構多い。筋の定義もムズだが、パターンとも共通性があるし。
コスミ自体は１種類しかないが、周りの状況でヨセからワタリ等等役目はゴマンと
ある。要するにパターンは目的を入れないと絵に描いたモチ。

[312 デフォルトの名無しさん NG NG]

分散処理で計算する方法は考えたんだけどさ、
黒（自分）が最善手を常に打つとして、
白（敵）が最善かどうかわからない手を打つとすると
19*19では
(19*19-1)*(19*19-3)*(19*19-5)....となる。

これを300*300*300......(19*19-100)
と近似しても激しい値になる。
コレをどこへ保存すればいいのだろうか？
地球上のコンピューターをすべて集めてきても
保存できない。

>3^19^2 ＝ 1350851717672992089 ≒ 10^18
コレ間違ってるよ。
3^(19*19) > 2^400
log10 2^10=3
log10 2^400 =120
まあ120桁はあるな。

[313 デフォルトの名無しさん NG NG]

爺さんの楽しみが無くなるなあ〜

[314 デフォルトの名無しさん NG NG]

賞金 １００円
みんな ガンバレ〜〜

[315 デフォルトの名無しさん NG NG]

>>311
候補手といっても、いろいろなレベルがあると思う。
例えば、どの手を選んでも悪手にはならない
候補手の列挙から
どの手を選んでも良い手であるような
候補手の列挙から・・・

あるいは攻撃的な手だけを列挙できるようになるのも
有効だし
守備的な手だけを列挙できるようになるのも有効だね。

候補手が列挙できたら、あとは探索するのみ。

[316 デフォルトの名無しさん NG NG]

今考えてるのは
精度の粗い候補手列挙システム
（つまり、悪手は切り捨てるけど良手は絶対に切り捨ててはいけない。
判定不能の物は残す）
と
高機能なαβサーチの組み合わせでの
アルゴリズムを作ろうと思ってる。

候補手列挙は、やっぱり周辺パターンのデータベースしか
ないのかな。

候補手列挙で一つ思いついたのは、
応手作成アルゴリズム。
相手の手を、どんな手なのか予測分類して
（２つに分類するなら、攻撃的か守備的か）
候補手を列挙する。

まあ、まだアイディアを練ってる段階だけど

[317 デフォルトの名無しさん NG NG]

絶妙手をも切り落とさないシステムだと大変かもね。
そういう手は弱いレベルには悪手だから。
プログラムの棋力にふさわしい普通の手が10手から20手程度抽出できれば
十分じゃないかな。

囲碁はまだそれほど深く読めないので（シチョウは除いて）
探索手法自体の重要性は低いと思われ。

やはり最大の難関は評価関数かと。
地の判定から、石の連絡、強弱、空間の支配力、
この辺を適当に数値化しないといけないからね。

[318 デフォルトの名無しさん NG NG]

>>317
俺は(中盤の）評価関数の作成が無理だと思うんだよね。
評価関数の作成が将棋と同程度の難しさなら、
現状のルールベースの候補手生成アルゴリズムと組み合わせれば
きっと将棋と同程度の強さになってると思うんだ。
探索空間の広さが同程度になると思うから。

囲碁は、終盤に近づくほど評価関数が正確な値を示すようになってくる(気がする）が
序盤では定石に頼らないとまったく打てない（はず）。
それは定石データベースを持たない囲碁プログラムを作れば
おのずとわかると思う。
という事は、評価関数の精度をあげるには深く読んでみる事が
一つの方法であると思う。

そこで、いかに有効な手を深く読むかが重要だと思う。
評価関数が曖昧と仮定している以上、αβサーチは使えない。
じゃあ、どうするかというと、深く読む。
どうやって幅を絞るかというと・・・
アイディアはあるけど今は暖め中という事で。

>そういう手は弱いレベルには悪手だから。
絶対評価と相対評価がメチャクチャになってるかもね。
人間にとって一見悪手にみえるが良い手である手を妙手という？から
それがコンピューターにとって妙手かといえば、違うと思う。
目指すは”最強”なのでｗ

[319 minikat NG NG]

例えば、１０年くらい前の棋道で趙治勲の読みの内容に関するする連載があったが、
プロでも驚くところまで読んでいる。多分、プロの頭には過去の膨大な筋や
パターンと、ものすごい読む力が備わっている。全部の可能着手数なんて考える必要ないんだ。
反面、故岩本九段のようにパラパラ打って碁にする棋風もあるが。それは一言で言えば、バランス。
理論でもいいから趙さんの読みの深さまで深化できるアルゴリズムでなければ
先の見通しは暗い。
評価関数でいえば、人間は盤面計算や評価を毎着手やっていないでしょ。
一段落したところでやる。それまでは手順をつくすか、ある死活なら死活に集中する。
その意味でプログラムは人間を徹底的に模倣し、攻めあいや終盤計算等の得意分野で人間を追い越さ
なければいつまでたっても初心者レベル。と思う。
それから今のプログラムはエントロピーが低い。着手に多様性がないからプログラムは
かならずこう来るんだ。とか読まれてしまう。ノゾキにいつもツグぐようなものやね。
プロでも道策にケイマにカケられて安井家はいつも下うけでこなされる。
道策の深読みと多様性についていけない。この２点をどう表現するか。

[320 デフォルトの名無しさん NG NG]

多様性に関しては学習なのかな。
負けたゲームから何かを学ぶ。
少なくても、相手が同じ事をしてきたら
それに対して何か別の策をこうじるようにならないと。
まあ、それができるなら
永遠とコンピューター同士で学習すると
最強になってしまうんだけど。

[321 デフォルトの名無しさん NG NG]

深く読むかぁ。
何手ぐらい読めば妥当なんだろうね。
>>319さんの言うように当然の手順、というのを抽出できれば
それに沿って読みさえすれば5手、10手、20手先の局面でも
正確に読めそうな気もする。

この場合、地合でなく、戦いを重視したプログラム、ということになるのかな。

[322 デフォルトの名無しさん NG NG]

実際に人間は何手くらい読んでるのかな？

俺は囲碁初心者だけど
ぱっとみで候補が５くらいあがって
そして７手先くらいは読んでるね。

確かに、読みっていうのは
そこへ打っても大丈夫かといった
チェックをしているような気がする。
つまり、感覚だけである種の最善手がはじき出されている。

[323 デフォルトの名無しさん NG NG]

>この場合、地合でなく、戦いを重視したプログラム、ということになるのかな。
それは、当然の手順＝最適な手順がなんなのかによりそう。

[324 デフォルトの名無しさん NG NG]

将棋や囲碁では、状態をイメージ（画像）として捕らえるような作業を
人間は行っているだろうね。陣形とか、血合とか。

以前ちょっと考えたことがあるのが、上記の考えを元に、
盤面を白黒で２分割、４分割・・・１６分割くらいして、
（分割はそれぞれが優勢な部分を中心とする）
そのそれぞれのブロックで、細かい判定を行うというもの。

でも、すでに他の人が同じような研究を行っていたという罠。

[325 デフォルトの名無しさん NG NG]

>>324
白黒で・・・ってどういう意味ですか？

これだけだと実装の仕方だけでもいろいろあると思うから
他の人が研究してようが問題ないのでは？

たとえば、優勢な部分を判定するアルゴリズムが大きく効いてそうだし
細かい判定で何を判定するのかによっても全然違うものが
でき上がると思うよ。
俺には作れなさそうだ。

[326 デフォルトの名無しさん NG NG]

いい加減な事を書くなよ

[327 名無しさんに接続中… NG NG]

囲碁の場合、アバウトなイメージだから難しい。
将棋の場合は、駒がぶつかったら「取る」ことを考えるし
王手をかけられたら「避ける」しかないので必然の手がある
囲碁の場合は１マスぐらいずらして打っても構わないので
これをプログラミングするのは難しいだろうな

[328 デフォルトの名無しさん NG NG]

学習といえば、ニューラルネット使った奴が
けっこういい成績残したね。
俺にはｻﾊﾟｰﾘなんですが。

[329 デフォルトの名無しさん NG NG]

どこかに論文があったと思うよ。

あった。ここ。
http://www.markus-enzenberger.de/compgo.html

[330 デフォルトの名無しさん NG NG]

とうとう7行に収まったようです。
http://pc3.2ch.net/test/read.cgi/tech/1033143528/530

[331 NG NG]

コンクール・コンテスト総合掲示板
http://jbbs.shitaraba.com/music/3054/

[332 1 NG NG]

結局、俺に勝てる囲碁プログラムを作れた奴はいないのか。
２ｃｈってバカばっか。

[333 デフォルトの名無しさん NG NG]

>>332
結局、自分に勝てる囲碁プログラムを作れた1はいないのか。
2chってバカばっか。

[334 デフォルトの名無しさん NG NG]

厳しい事言うね。
プログラムの中でも囲碁は難しいほうだよ。
日本中探し回っても、囲碁の思考の部分をプログラムできる人は
数えるほどしかいないと思うけど。

[335 デフォルトの名無しさん NG NG]

だいたいまだ３００レスじゃねーか。

[336 デフォルトの名無しさん NG NG]

囲碁の評価関数の話をしませんか？

思うに、評価関数自体で再帰的に探索するような仕組みを作れば
いいような気がする。
石の死活はこの石を殺すには先にこの石を殺して、その前に・・・と
延々続いていくので、この部分を上手に再帰的に処理できれば
石の死活に関してはかなり強くなるのでは。

とか書いてみる。もちろんアイデアだけで実現できてません。

[337 デフォルトの名無しさん NG NG]

>>336
提案してるのは「再帰」なわけ？
ぶっちゃけ、君相当レベル低いかも。
MiniMaxとか知ってる？
木構造＝再帰で処理できる
再帰的に処理できる事のメリットはコーディングが容易なだけだけど。

評価関数の話で一つ問題を提起すれば
状況に応じて評価関数を切り替えるという方法は
一般的な方法だけれど、
では、状況というものをどう定義するか。
つまり、どういう状況に振り分けるか。
序盤、中盤、終盤に分ける方法が一番短絡的かもしれない。
他にもコウの時は別の評価関数を用意できるかもしれない。
評価関数の中身は別として、
どれくらいの状況に分けられるのか？
振り分けるアルゴリズムがあるかどうかはまた別の問題だと思う。
まあ、囲碁に限った話ではないんだが。

[338 デフォルトの名無しさん NG NG]

再帰という言葉を覚えたから使ってみたかったんだろ。

[339 デフォルトの名無しさん NG NG]

盤の端っこでの死活の問題はさ、強い人ほど先を読まずに形を暗記して
うってるんですよ。
というわけで、死活はデータベースを作ればよろしい。

[340 デフォルトの名無しさん NG NG]

今なら１０万件くらいは余裕で処理できそうだから・・・
log3 100000 =10
よって3*3の範囲なら全部覚えられる。
マス目の数＊0.477=必要なレコードの桁数
１６マスなら7桁、つまり１００万レコードだ。

[341 デフォルトの名無しさん NG NG]

>>340
とりあえず、死活１００選とかそういう本をざっと眺めてみる
ことをお勧めする。

[342 デフォルトの名無しさん NG NG]

>>341
たしかに、すべてのパターンは必要にならないけど
相手が常に最善を打ってくるとは限らないので
340に出てる数字と大差ないというか。
一マス増やしただけで、桁数が0.5桁増えるというのは
恐ろしい事だよ。

まあ、実際のプログラムでは
眼形データベースと演繹的な処理で判定するわけだけど。
詰め碁がデータベースでできたら、学会誌には出てこないよ。

[343 デフォルトの名無しさん NG NG]

書き逃げ？

[344 デフォルトの名無しさん NG NG]

HSP イイ!!

[345 デフォルトの名無しさん NG NG]

あきらめたとか？

[346 デフォルトの名無しさん NG NG]

盤のはしっこのデータベースつっても３＊３じゃ正直狭すぎでわ？
5目中手ですら３＊４の大きさは必要だし。
外側の石の状態とかも必要と思われ（安全、攻め合いになってる、とか）

[347 デフォルトの名無しさん NG NG]

>1に勝ったら賞金が出力されるロジックが必要なんだと思ってた・・

[348 デフォルトの名無しさん NG NG]

うにゅ

[349 デフォルトの名無しさん NG NG]

完全読みすれば死活の判定はできそうだけど

[350 デフォルトの名無しさん NG NG]

2*2でも、完全読みをするのはめちゃくちゃ時間がかかる

[351 デフォルトの名無しさん NG NG]

3x3が何とかなるレベル。
４は、今のPCだと辛すぎる。
５以上は間に睡眠や人生をはさまないと無理。

[352 デフォルトの名無しさん NG NG]

5x5は解かれた、と情報が流れていたけど？

[353 minikat NG NG]

解いた見たいですね。
確か結果は、白全滅。

[354 デフォルトの名無しさん NG NG]

それは完全読みじゃなくて、
ヒューリスティックを使ってるんじゃなかったっけ？

[355 デフォルトの名無しさん NG NG]

10/21のメールから。
天元に打って黒25目勝ち。
4時間で解いたとか書いてるな。

Yesterday my program solved 5x5 Go starting with the first move in the
centre. As was expected it is a win for the first player with 25 points
(the whole board belongs to black).

I used an iterative deepening Alpha-beta search (PVS) with:
- Transposition tables (2-deep replacement scheme, 2 x 2^24 entries)
- Enhanced transposition cut-offs
- Symmetry lookups in the Transposition table
- 2 killer moves
- History heuristic
- Benson's algorithm for unconditional live (extended with unconditional
territory)
- Heuristic evaluation for positions that are not fixed by benson

The solution was found at 22 ply deep (23 for the empty
board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)

The main reason why my search was able to solve 5x5 is Benson's
algorithm which reduced the depth where a proven full-board-win is
detected by at least 6 plies (compared to by old implementation which
had to play many things out).

Only the simple (japanese) ko-rule was used, so the result is
independent of any superko-rule. This does not mean that super-ko is
irrelevant, just that from the empty 5x5 board there is a forced line
that avoids all long cycles.

[356 デフォルトの名無しさん NG NG]

This does not mean that super-ko is
irrelevant, just that from the empty 5x5 board there is a forced line
that avoids all long cycles.
誰かここ訳して

As was expected
って書いてあるから、完全読みではないんだよね？

[357 デフォルトの名無しさん NG NG]

>>356
日本ルールの単純なコウだけを考えていて、３コウとか長生とかの無限手順は
考慮していない、ってことでしょ。

３コウとかを軽視したわけではなく、5x5の盤では３コウとかになるのを
防ぐ強制的な手が存在するから、ということかな。

[358 デフォルトの名無しさん NG NG]

>>356
As was expected
それは、予期していた通り、という意味だと思う。
完全読みしてるんじゃないかな。

[359 鬼池田 ◆uADIuuYAIU NG NG]

拙訳です。用語、意味で間違ってたら直してください。

　昨日、私のプログラムは初手天元の手から５路盤を解決しました。
予想通り、先番２５目勝ち（全盤面が黒に属す）

反復アルファーベータ探索（ＰＶＳ）を使用して：
-移項テーブル（２手先置換計画、 2 x 2^24 候補手）
-改良置換枝狩り
-対称置き換えテーブル
-２キラームーブ
-ヒューリスティック
-無条件生きのベンソンのアルゴリズム（無条件地に拡張された）
-ベンソンのアルゴリズムに用意されていない盤面のヒューリスティック評価

２２手の深さで解答が見つかったが（空の盤からは２３手）
（探索ノード数４，４７２，０００、ペンティアム４の２Ｇｈｚで４時間）

私の探索が５路盤を解決できた主たる理由は、ベンソンのアルゴリズムが、少なくとも
６手必要なと思われる証明すべき全面勝ちの深さを、減らしてくれるからです。
（多くのことをやらねばならない従来の方法に比べて）

日本の単純コウルールだけを使用したので、結果はいかなるスパーコウルール（使用条件）
からも独立していると考える。これはスーパーコウルールが不適切という意味ではなく
すべての長い循環を避けるための、5路盤に限定された結果です。

[360 デフォルトの名無しさん NG NG]

>>359
グッジョブ
でも、完全読みかどうはうよくわからないね。

[361 デフォルトの名無しさん NG NG]

>>360
そうとは書いてないから完全読でしょう。
でなければ解いたとは言わないだろうし。

[362 鬼池田 ◆uADIuuYAIU NG NG]

すまん　探索ノード数は０が３つ足りません。（間違い）

[363 デフォルトの名無しさん NG NG]

これの意味がわからないと、完全読みかどうかもよくわからないね。

-移項テーブル（２手先置換計画、 2 x 2^24 候補手）
-改良置換枝狩り
-対称置き換えテーブル
-２キラームーブ
-ヒューリスティック
-無条件生きのベンソンのアルゴリズム（無条件地に拡張された）
-ベンソンのアルゴリズムに用意されていない盤面のヒューリスティック評価

で、俺は囲碁プログラミングに少しは詳しいつもりだったけど
一つもわからないよ。
誰か、ここら辺の説明が書いてある論文でも本でもＷＥＢでも
なんでもいいので教えてください。

[364 デフォルトの名無しさん NG NG]

6x6のオセロが解けたぐらいだから6x6までは
囲碁も解かれそうな気がするがどうよ？

[365 デフォルトの名無しさん NG NG]

>>363
-移項テーブル（２手先置換計画、 2 x 2^24 候補手）
ハッシュ表のことですな。1677万局面記憶可能。（おそらく）2手以上の探索結果のみを保存
-改良置換枝狩り
ハッシュ表で
-対称置き換えテーブル
ハッシュを見る場合に、局面の対称性も同時にチェック
-２キラームーブ
ある局面で有力な手があった場合、その手を兄弟局面でも先に試す。これを2手まで。
-ヒューリスティック
History ヒューリスティック。例えば、(2,2)に置いて場合の最善手が(2,3)だった場合、
その場所での回数を記憶しておき、他の局面での手の生成で先にそれを読む。
-無条件生きのベンソンのアルゴリズム（無条件地に拡張された）
ダメを詰めまくっても取られないので、この石は活き、という判定条件
-ベンソンのアルゴリズムに用意されていない盤面のヒューリスティック評価
適当に無条件活きの条件をでっちあげた、ということでしょう。
ベンソンのアルゴリズムはあまりに低レベルな判定をしているから。

[366 デフォルトの名無しさん NG NG]

だいたいチェスで開発された技法なのでコンピュータチェス関係の
本を読むといいよ。
Webだとこことか。
http://www.xs4all.nl/~verhelst/chess/programming.html

[367 デフォルトの名無しさん NG NG]

お勧めの本は下とか。
残念ながら囲碁はいいのがないね。

コンピュータチェス―世界チャンピオンへの挑戦 Information & Computing
http://www.amazon.co.jp/exec/obidos/ASIN/4781907237/
コンピュータ将棋の進歩１，２，３
http://www.amazon.co.jp/exec/obidos/ASIN/432002799X/
http://www.amazon.co.jp/exec/obidos/ASIN/4320028929/
http://www.amazon.co.jp/exec/obidos/ASIN/4320029569/
ゲームプログラミング
http://www.amazon.co.jp/exec/obidos/ASIN/4320028988/

[368 デフォルトの名無しさん NG NG]

お勧めはしないけど、立ち読みは勧める囲碁の本

コンピュータ囲碁GREAT―プログラムの作り方とネット対局の実際
http://www.amazon.co.jp/exec/obidos/ASIN/4434009354/
囲碁の算法―ヨセの研究
http://shopping.yahoo.co.jp/shop?d=jb&id=19409155

[369 鬼池田 ◆uADIuuYAIU NG NG]

完全読みの定義だけど
　いかなる局面からも結果がわかる意味.　と我思う。
　全ては読めん、よって皆頭を悩ます
　DataBase作っているようなので、完全読みといっていいと思う。

Ｔｒａｎｓｐｏsiｔｏｎ　Ｔａｂｌｅ　でハッシュと呼んでないのは
最善手やスコアーや深さを含んだ複合的なものだからだろう。

*David LevyのGamesmanshipはお勧め（将棋もあるでよ）

[370 デフォルトの名無しさん NG NG]

少年漫画のヒカルの碁スレで量子コンピュータが話題、とのこと。
http://corn.2ch.net/test/read.cgi/ymag/1036302320/

[371 デフォルトの名無しさん NG NG]

何×何路までだったら読み切れるのだろう？
５×５路までかな？

[372 デフォルトの名無しさん NG NG]

6x6ぐらいまでは読みきれるんじゃないか？
とかてきとーな事を書いてみる。

９路が読み切れたらすごいだろうけど。
完璧なコミが分かるし（ｗ

[373 デフォルトの名無しさん NG NG]

>>371
4x4は日本の清　愼一さん（囲碁プログラム勝也の作者）が最初にコンピュータで
完全読みをした。これが2000年のこと。

5x5は、今年、完全読みがされた。
>>365
では、
>-ベンソンのアルゴリズムに用意されていない盤面のヒューリスティック評価
>適当に無条件活きの条件をでっちあげた、ということでしょう。
>ベンソンのアルゴリズムはあまりに低レベルな判定をしているから。
と言っているみたいだが、無条件活きの条件をでっちあげているのではなく、
この先、どう指せば活きになりやすそうか？という判定に用いているように
読めた。（英語力が足りんので間違ってたらスマソ）
つまり、いい加減なことはせずに、きっちり最後まで読みきった、ということ。

さて、論文を見る感じでは、4x4は実はかなり力技(＾＾;で解いたようだが、
5x5は、やはりずいぶん工夫をしてやっと解けたということのようだ。

単純に考えて、6x6は、36*35*34*33*32*31*30*29*28*27*26倍、5x5よりも
難しいので、（実際には対称形があるのでもっと減るけど）すぐに完全読み
されるとは思えない。

…もっとも、この程度なら時間の問題かな。

[374 鬼池田 ◆uADIuuYAIU NG NG]

中山典之プロの古い著作より。
岩波新書　囲碁の世界　１９８６年初印刷

コンピュータ碁や五路盤について言及している。
Ｐ１９８より抜粋

ところで、２５の階乗は．．．２６ケタと言う長いものとなったが、
．．．
　ただし、コンピュータ君は、油汗をながしてでもこの程度のことは
読みきるだろうが、人間さまというのは偉いもの（？）で、もし、あなたが幸いにして
アマチュア初段くらいの力があれば．．．．．。

　黒１の手で、右上の図に示したように天元（盤の中央）に打ち、黒が２４目勝にな
ることをタッタの１秒で読み切れるであろう。こうしてみると、われわれも頭の中にも
のすごく高度なコンピュータを持っているとも言えそうである。


　そうですね中山先生。でも、ゆっくりですけど進歩してます。
長生きして待っててください。

[375 鬼池田 ◆uADIuuYAIU NG NG]

中山典之プロの古い著作より。
岩波新書　囲碁の世界　１９８６年初印刷

コンピュータ碁や五路盤について言及している。
Ｐ１９８より抜粋

ところで、２５の階乗は．．．２６ケタと言う長いものとなったが、
．．．
　ただし、コンピュータ君は、油汗をながしてでもこの程度のことは
読みきるだろうが、人間さまというのは偉いもの（？）で、もし、あなたが幸いにして
アマチュア初段くらいの力があれば．．．．．。

　黒１の手で、右上の図に示したように天元（盤の中央）に打ち、黒が２４目勝にな
ることをタッタの１秒で読み切れるであろう。こうしてみると、われわれも頭の中にも
のすごく高度なコンピュータを持っているとも言えそうである。


　そうですね中山先生。でも、ゆっくりですけど進歩してます。

[376 デフォルトの名無しさん NG NG]

ベンソンのアルゴリズムについての解説ってありますか？

[377 デフォルトの名無しさん NG NG]

>>376
ここ。
http://www.fides.dti.ne.jp/~oka-t/benson-algorithm.html

[378 デフォルトの名無しさん NG NG]

質問。
読み切れたら正当なコミがいくつか解るんですか？
たとえば、4×4路と5×5路はコミいくつが適正とか解ってるんでしょうか？

[379 デフォルトの名無しさん NG NG]

>>378
４路盤のコミは１５目で、５路盤のコミは２４目が適正です。

[380 デフォルトの名無しさん NG NG]

>>379
4路盤は引き分けです。

[381 デフォルトの名無しさん NG NG]

1路盤のコミは?