コンピューター将棋番外編5・アルゴリズム

コンピュータ将棋のアルゴリズムをめぐる疑問・質問・議論はこちらでどうぞ。

＜最近の話題＞
1.ボナンザのアルゴリズムは本当に全幅探索なのか？
2.プログラムに一定深さまで完全探索させて意味があるか？
3.静的評価関数の不完全さをどうやって補うか？
4.ニューラルネットorGA等を利用した革新的手法は有り得るか？

＜旧スレ＞
コンピューター将棋番外編・旅人議論
http://game.2ch.net/test/read.cgi/bgame/1058629287/
コンピューター将棋番外編2・進歩に懐疑的な人たち
http://game6.2ch.net/test/read.cgi/bgame/1061102154/
コンピューター将棋番外編3・進歩に懐疑的な人たち
http://game9.2ch.net/test/read.cgi/bgame/1085592538/
コンピューター将棋番外編4・オルターナティブ
http://game9.2ch.net/test/read.cgi/bgame/1091717838/

＜本スレ＞
コンピュータ将棋スレッド35
http://game12.2ch.net/test/read.cgi/bgame/1170114501/
<お仲間スレ>
ボナンザ Bonanza　専用スレ　9手目
http://game12.2ch.net/test/read.cgi/bgame/1175159947/
おまいら最強の将棋プログラムしてみろよ part5
http://pc11.2ch.net/test/read.cgi/tech/1109307327/

特２なし

３ざん既出

誰も書いてくれないので私がボナスレを読んで考えた事をちょこっと書きます。

命題１：完全な静的評価関数を持てればソフトは一手先を読むだけで良い。

命題２：任意の局面から最終局面まで完全探索できれば評価関数は不要である。
　　　　勝ち、負け、引き分けの評価がゲーム木の末端やノードにラベル付け
　　　　されるだけである。

すなわち、評価関数と先読みはCPU時間を奪い合う背反な関係にある。
したがって凝った(=計算時間を必要とする）評価関数はそれにより
大幅な前向き枝狩りが有効になるほど正確な、読み抜けを起こさない
ものでないと価値が無い。

よって現状ではボナンザのような全幅探索を基本にしたソフトの方が有望である。

しかし、もし将棋を完全探索したゲーム木が入手できたとすると
末端には「勝ち」「負け」「引き分け」の三通りしかないが、
途中のノードには単なる三種類のラベルではなくそれぞれ点数を
付ける事もできなくは無いと考える。

例えば、ある局面から「勝ち」に至る手の広さ（多さ）、近さに応じて
高い点数を付け、逆に「負け」に至る手の広さ、近さに応じて低い
（マイナスに大きい）点数を付ける。

そのような確定的な評価値は存在するが、正確な値は不可知であると考え
将棋を決定論的ゲームというよりは確率的ゲームとみなして、その未知の
評価値を統計的（ベイズ推定のよう？）に推定すると言う考え方は
できないだろうか？

>>4
> よって現状ではボナンザのような全幅探索を基本にしたソフトの方が有望である。

ボナンザの作者の保木さん自身、全幅が有望かどうかはコンピュータチェスの世界でも
結論が出ていないと言っているのでそれは違う。

>>5
> 評価値を統計的（ベイズ推定のよう？）に推定する

現状のコンピュータ将棋でやっている終端ノードでの静止評価でも点数をつけて
やってるわけだけど、それとはなにが異なるの？

「全幅探索」と「全幅探索ベース」の境界が、いまいちハッキリしない。

全幅検索っていうと、ホントに全部の手をバカ正直に数え上げて・・・って感じかな
全幅検索ベースっていうのは初めて聞いたけど、返ってくる結果が全幅検索のそれと同じもの、ということでいいの？

前にちょっと出てた話だけど、αβとかって、「結果としては全幅検索と同じ回答を得られる」ものなんだよね
確かに評価値で枝刈りしてるから「それ全幅じゃないぢゃん」って誤解されちゃうのはわかるんだけど
全幅検索っていうのはあくまでも探索の方法であって、最終的な目的は「その中でどれがいい手か？」を探すこと

全幅検索の場合は、全部の手を調べてその全部の手に点数をつけて、最後にそれらの点数を比較して一番いい点数を指し手とする
αβの場合は、調べた手の点数をその場で調べることで枝刈りをするから、いくつか枝刈りができる

αβは「全部の指し手をきちんと読む」わけではないけど、「結果として出てくる回答は全幅検索の結果と同じものがでてくる」っていうことだね

・・・うん、話が違うねorz

αβは全幅検索だよ。
MINMAXのことを全幅検索って言ってるんだろうけど、どっちも全幅。
αβの場合は最善手以外の手については、最善手より劣るということしか分からないけど
MINMAXだと最善手以外の全ての手の評価値も正確に分かるってところが違う。

評価関数が正しけりゃ全幅検索にもなるけど、
だいたい評価関数が正しけりゃ検索する必要などない

なんかゲーム理論の適用方法が根本的に間違ってるから
オバカな勘違いつー奴

一人で考えたこと垂れ流してないで
専門書嫁
先人に敬意を払え

>>9
αβは「後ろ向き枝刈り」とでも言った方がいいんじゃないの？
全幅ではないけど、全幅と同じ結果が出る、という方法でしょ

>>10
わからないかなぁ・・・
全幅でも最後は評価関数を使って指し手を決めてるでしょ
だから全幅とαβとの違いに評価関数の正確性はある意味無関係だよ
・・・違う話をしたいのかもしんないけど

>>12
評価関数が最善手と評価する手を互いに指しても、評価値が上下するでしょ
５手先読みにｍｉｎｉｍａｘ使おうとしても、その間に評価値が上下してるでしょ
最善手指し続けたら評価値は、先手勝ちか後手勝ちか、どちらかに収束していかないとｍｉｎｉｍａｘ使えないんだよ

君は、将棋プログラマーが全て解った上で、仕方なくやむなく、現状にあるマシな方法をとっている事を、
勝手に、完璧な方策をとっていると善意で？勘違いしてるだけ

ｍｉｎｉｍａｘの説明に使われる絵の枝に割り振られてる数字の大きさが進行方向で常に減り続けずに、
上下しながら減ってるんだよ
下手をすると５手先で却って増えているかもしれない

MINMAXを何か勘違いしてるようだけど、
MINMAXってのはただ単に5手先の評価値を、読み始めた局面まで持ち上げる方法のこと。
だから1手進めてまた5手読みしたら、評価値が上下するのは当たり前。
ただ1手進めてから次に4手読みをしたら、当然その前の評価値と正負を逆にした点数が帰ってくる。
あるいは2手進めてから3手読みしたら2手前に5手読みしたときと同じ評価値が帰ってくる。

その疑問は私にもあるんだよね。
現状の指し将棋プログラムは何手か先を読んだ末端の評価値を確定的な値だと
仮定し、MinMax法ではそのまま上のノードの評価値として持ち上げて行く。
αβカットはそれをより効率良く行い、同じ結論を得る手法なわけだ。

しかし良く考えると数手先を読んだ末端のノード（葉）の評価値は
ある種の推定値なわけだ（本当の値は不明）。だから末端の値を比較して
そのまま持ち上げる手法では途中のノード（同じノード）の値が
何手先までを読んで評価するかでガクガク変わっているのかも知れない。

>>14
> MINMAXってのはただ単に5手先の評価値を、読み始めた局面まで持ち上げる方法のこと。

それバツ
MINMAXは得点の定められた選択ゲームに於ける選択戦略の一手段

これを将棋プラグラムの先読みに適応している時点で大きな勘違い
妥協でやむなく採用されている現状を、勝手に完璧な方策をとっていると君が勘違いしている

> だから1手進めてまた5手読みしたら、評価値が上下するのは当たり前。
じゃなく、互いに最善手を指した５手の間に評価値が上下するのが現状
ｍｉｎｉｍａｘを無理に適応して手を選んでも、切り捨てられた手の評価値がその後に高くなることが頻繁に有り得る

そうでないなら評価関数は完全に信頼でき先読みの必要はない
初手から評価値が最大値の手だけ指していれば必勝

[続き]
値が変わるだけなら良いが大小の順序関係が途中で変わっていると
間違った枝狩りをして間違った指し手を選んでいる可能性があるのでは
無いだろうか？(5手前に読んだ時はカットしてしまっていた指し手が、
同じ手数まで来て、改めて5手先まで読んだら実は最善だった。
しかし実際にはもう、別の指し手を選んでいる）

というわけで、上に書いたような有利な局面に至る手の広さ、近さなどを
考慮した重み付けをしながら末端からノードの評価値を計算していけば
ある程度、評価値のブレを抑えられるのでは無いかとちょっと思っている。

ただし、そうすると当然αβカットは不可能になり完全探索（有りうる
すべての指し手の探索と評価）が必要になると思う。

>>14
> ただ1手進めてから次に4手読みをしたら、当然その前の評価値と正負を逆にした点数が帰ってくる。
> あるいは2手進めてから3手読みしたら2手前に5手読みしたときと同じ評価値が帰ってくる。

５手読んだら、最善手を選んだ場合は、その５手の間に評価値が上がり続けなければ(下がり続けなければ)ｍｉｎｉｍａｘは適用できないよ

> 切り捨てられた手の評価値がその後に高くなることが頻繁に有り得る

こんなの当たり前だろって言ってるの、最後まで読みきってないんだから。
何を言いたいのか分からない。
全部読みきれないから途中で打ち切ってMINMAXを適用してるだけで。

それとこれの意味が完全に分からない。
> ５手読んだら、最善手を選んだ場合は、その５手の間に評価値が上がり続けなければ

>>19
じゃあ３手読みで考えてみて
互いに最善手を選んだ場合に評価値が上下したらｍｉｎｍａｘ適応できないのが解りやすいから

最善手を選び続けて評価値が上がり続ければ(下がり続ければ)評価関数は完璧だから、先読み不要だし

ttp://www.youtube.com/watch?v=ct1fk8GFubA
改めて、酷いな

> 間違った枝狩りをして間違った指し手を選んでいる

この枝狩りってのはアルファベータの後ろ向き枝狩りのことだと思うけど、
結局途中で枝狩りしようがしまいが同じ手が選択されるから、どのみちその間違いは避けられない。

それとは別に、先読みの信頼性を上げるために途中のノードの点数も考慮する方法もある。
その途中のノードの点数というのは下から上げられてきた点数ではなく、
その場で1手読みなりして求めた評価値で。

>>20
理解できないからもういいです。

>22
「途中のノードの点数も考慮する方法がある」事を教えてくれてありがと。
いずれにしろ、上に書いた愚直な探索をして評価値を決める方法は自分で
プログラミングしてみて効果があるか無いかやってみたいと思ってるんだ。

将棋プログラムをまだ、書いた事無いから本当にやれるかどうか
分からんけど。

それとはちょっと違う話だが、これからの将棋プログラムは機械的な
強さを求めるよりもっと人間的な指し手を指せる方向に向かうべき
なんじゃないかなと思ってるんだ。いろんな理由で。

「言うは安く行うは難し」の典型だけども。

何でミニマックスなんて使用できるの？

ソフトはソフトっぽい手を指すしかないんじゃないの

>>8
亀で申し訳ないけど、レスありがとう。
チェスでは「全幅探索」が主流として表現されているけど、
実際には、いろいろな前向き枝刈りが実装されている。
それを「全幅探索」といっていいのかどうかが疑問だったんですよ。

つまりは「全幅」が何を指しているのか、と考えたんだけど、
「ある局面において、参照もしくは参考にすべきデータが無い時、合法手全て探索する」
（実際には後ろ向き枝刈りで全て探索することはないと思うけど）
ということになるのかな？

>>9
またバカ ｷﾀｺﾚ!!

ミニマックス法という言葉がダメなのかな？

ミニマックスアルゴリズム(Minimax algorithm)？
ミニマックス探索(Minimax search)？

素朴な疑問なんだが、
例えば、相手の手番から考えて、ｍｉｎｉｍａｘ原法で相手のｍａｘ手(１手目)を予想して、その中でのｍｉｎｉ(２手目)を選んで、、
その時点で切り捨てられた枝が、３手目に最善局面になってることは普通にあると思うけど

最善手を選び続けても評価関数の評価値が上下する現状ではｍｉｎｉｍａｘはダメじゃないの？
もっとも、最善手を選び続けて評価値が一方向に増加(減少)するなら先読み不要で、現局面で最善手選択してれば無敵だし

自分の手番から考えても同じね
２手目の相手のｍａｘ手を予想して、それをｍｉｎｉにする１手目を選んで、、
選ばなかった枝が３手目に最善局面になるのは普通にあるんじゃない？

Minimaxとαβは結果は一緒
評価関数が正しい事が（本来は）大前提
実際は誤差が多いから強くならない
だからボナの評価関数の自動作成が有効だったわけだ
また，評価関数がある程度良くてCPUが速ければ
ヒューリスティクスによる（ある意味いい加減な）前向き枝刈りは
やらない方がいいんじゃないかしらむ

将棋プログラム作者が、全てわかった上(評価関数の不完全さにより読み漏れ多し)で、現状ではやむなく、枝刈り採用してるのに、
「αβは全幅だよ」とか言い切るから混乱が生じる

評価関数が完全なら、αβは全幅と同じ出力をするけど、
評価関数が完全なら、先読み自体が不要になる

評価関数の精度に関係なく出力は同じ。(ゲーム木探索の文脈では)
ただこの人の場合ミニマックスというのを完全な局面評価ができるか
最後まで読みきって用いる手法だと定義しているようだから
そう定義すると違った結果になるね。

もしかしたら「全幅」というのを全深さという意味で使っているのかな？
そうだとしたら確かにαβは「全幅」ではないね。

>>33

＞＞30の例は？
ｍｉｎｉｍａｘ２回適用して３手目まで読んでも完全に読み漏れ
３手目まで全幅検索すれば、もちろん読み漏れなし

>>35
よくわからないから簡単なゲーム木を書いて画像でも上げてほしい。
何が読み漏れであって、何が読み漏れでないとかが分からない。

こことか、どうでしょう。
【コンピュータ将棋の基礎】
ttp://homepage2.nifty.com/kakinoki_y/kiso.htm

>>35
minimaxを２回適用？

>>29-30もどうかと思うけど、都度一手読みになっていて、
且つ１手進めると「後戻りが出来ないという状況」になっている気が。

探索におけるminmaxは各節ごとに下を見て、単に最小値or最大値を選択する方法。
ttp://en.wikipedia.org/wiki/Minimax
リンク先のページのExample(中段付近)の図で説明。

深さ４に辿り着いて初めて４手読みとして評価値を得ることができる。
図中の○□内の値は、全て深さ４（最下段）から上に伝播されたもの。
深さ３の各節では、自分に繋がっている深さ４の各節で得られた値の最小値を選択、
深さ２の各節では、自分に繋がっている深さ３の各節で得られた値の最大値を選択、
深さ１の各節では、自分に繋がっている深さ２の各節で得られた値の最小値を選択、
深さ０では、自分に繋がっている深さ１の各節で得られた値の最大値を選択、

深さ０の -7 はそうやって取捨選択を繰り返されて深さ４から伝播された値。
ここでようやく最善手順が決定され、深さ０における最善手が青矢印（右方向）になる。

深さ４で得られる評価値がゲームにとって最善かどうかは問わない。
あくまで、深さ４で得られる評価値を最小値or最大値で取捨選択して深さ０に伝えていくだけ。
深さ４で得られる評価値の信頼性が上がれば、
探索における最善手順がゲームにおける最善手順に近づく。

俺の勘違いがあった
ｍｉｎｉｍａｘは２手ペアで読む手法と思っていた、学生時代に読んだ原著ではそうなっていた
５手読みの場合はｍｉｎｉｍａｘを何回か適用するとの勘違い
５手分丸ごとｍｉｎｉｍａｘを適用するのね

ゴメンね、原著の最初の例題が、相手と同時にカードを出して、その組み合わせで得点が決まるゲームだった。

βカットなんて当たり前すぎて探索法の進歩なんて今後はないだろうよ
結局は評価関数の精度が全てだよ

>>32
誰も「αβは全幅だよ」とは言ってないと思うぞ

「αβで返ってくる最善手候補（そのソフトが考えた最善手）と全幅で返ってくる最善手候補は同じ」
というのとそれとは話が違う

>>34
全深さ、というよりは全はば、かなw
まさに全幅

要するに、その局面で考えられる指し手を「必ずすべて」検索するのが全幅検索
αβは、枝刈りをしても全幅と同じだけの効果が必ず得られる検索（節約）方法

でいいんだよね

ボナスレにも書いたけど、みんなうさ本くらい読もうよ・・・orz

>>42
前向き枝狩りをしないことを全幅探索って言うんだけど

ここ参照
http://www32.ocn.ne.jp/~yss/csa0307.txt
ちなみにYSSの作者さんのページ

>>29
全幅とαβの違い、ってのを論ずるときには、評価関数が正しいかどうかって言うのはあんまり関係ないよ

>例えば、相手の手番から考えて、ｍｉｎｉｍａｘ原法で相手のｍａｘ手(１手目)を予想して、その中でのｍｉｎｉ(２手目)を選んで、、
>その時点で切り捨てられた枝が、３手目に最善局面になってることは普通にあると思うけど

っていうケースはもちろんあるよ。いっぱいあるw

けど、それはαβ「だから」読み逃す、ってわけじゃない
全幅検索をしてても、同じ評価関数を使ってる以上その手は最善手だと判断できない

切り捨てられた、という表現だから誤解を持っちゃうのかもしんないけど
αβで言う「切り捨て」「枝刈り」って言うのは
全幅検索をしたとしてもこの枝（指し手）は候補に選ばれることはない、だから読む必要がない、っていう意味の切り捨てなのね
人間が考えるような、この手は損だから先を読むのをやめよう、っていう意味の「切り捨て」じゃないの
そこを混同しちゃいけない

>>44
「後ろ向き枝刈り」をしてる、ってことかなw
あくまでも個人的な感想だけど、やっぱ「全幅」っていうのは全く枝刈りしないで全部読む、みたいな感じで使いたい

山下さんは
全幅＝前向き枝刈りをしない
αβとかはだから全幅に入る

私
全幅＝前向き枝刈りも後ろ向き枝刈りもしない
αβとかはだから全幅に入らない

という感じかなぁ

言葉のイメージの問題なんで、私の感覚は間違ってるのかもしんない
全譜君のヘルプを見ると「全幅探索 full-width search」ってあるしなぁ・・・

当然後ろ向き枝狩りはしてるよcraftyは
というかαβを使わないプログラムなんて存在しないはず
同じ時間で倍の深さまで読めるのだから

それと全幅探索の間の探索のことをbrute force、
前向き枝狩りが入る読みはselective searchともいうと思った確か

ルートから何手かはbrute force、そこから先はselective searchってのがよくある方法だと思う

おまいら何言ってんだよ
ミニマックスで全幅検索するときに、αβなんて知らないし聞いたこともなくとも、普通は誰でも同様に行うだろ
単に誰かがαβって命名しただけで、全幅検索と同値だよ

それはさすがにないw

深さ10までの全分岐を探索するのと、カットするのでは結果は変わるだろ

αβは普通に使ってるよ
詰将棋なんかやってるときでも、ある局面まで読んでそこで相手がある手を指したとき
こちらが相手を詰ませられないことが分かったときに
その局面で相手の残りの別の手なんて考え出さないでしょ

MinMax法とαβカットと全幅探索の話だけでここまで議論が長くなるとは。
こりゃ確かに他のスレでやると敬遠される（嫌がられる）だろうな。

ここでは皆、遠慮しないでやってね。(言われなくてもやってるようだがｗ）

それが全て同じものなのに違うと思ってる人が
後から後から出てくるから延々とループしつづける

ま、そのうちどこかに議論が収束するだろう（と期待します）。

ところで皆さんは保木さんのボナンザに関する講演資料のスライド、読んだ？

http://ebiomiya.exblog.jp/6025019/

http://www.geocities.jp/bonanza_shogi/gpw2006.pdf

すごく興味深いね。

静的評価関数の調整を一体どうやって機械学習させているんだろうと思ったら
人間が実際にある局面で指した一手一手を正解として学習させているようで。
ボナンザはニューラルネットではないけれど既に、かなりの程度まで自動で？
将棋の局面評価を統計学習するマシンになっていると思う。

つまり、そのように人間（プロ棋士）の指し手をなるべく真似するように
調整されているから「次の一手問題」で正解率が何パーセント上がったと
言うような事が上達（能力向上）のバロメータになるんだろうね。

初めから人間の指し方なんか無視してアルゴリズムを作っているなら
「次の一手問題」が当たろうが当たるまいが関係ないだろうから。

なんだ、ボザンナの学習は糞だな、永久に人間に勝てないじゃん

おまいには勝てるんだからいいじゃんw

今にして思えばかなり前、どっかのスレで私が「うさぴょんの育ての親」さんに
言ってみた

「将棋の完全ゲーム木は作れなくとも、今まで指されたあらゆる（プロ棋士の？）
棋譜をすべてひとつにくっつけてゲーム木として表現し、その上をプログラムが
行ったり来たりしながら評価関数の最適化を行う」

と言う提案とほぼ等価な事を既に？実現してたわけだね、ボナンザは。
（その時ボナンザあったっけ？）

その時「うさぴょんの育ての親」さんの答えはそんなに長時間PCを
振り回したら電気代と騒音で家の方にとても許してもらえそうもない
と言うものだったと思う。

まあ、静的評価関数の最適化をしようと思ったら誰が考えても、現状
いちばん手近で信頼できそうなのはプロ棋士の棋譜にある指し手だよね。

なんか、ここまで来たら後はもう機械学習にどんな理論的枠組みおよび
テクニックを使うのか、どうやってハードウェア・アクセラレーションするか
あるいは多数のCPUまたはネットワークに分散したPC上で効率よく実行するか等
の勝負になりそうだね。

最適制御理論だろうがニューラルネットだろうが強化学習だろうが
統計的学習マシンなのは一緒（だと思う）。

根本的に違うやり方を取るとしたら、人間（プロ棋士）の指し手を正解と
する事自体をやめるしかないが今のところそれでうまく行きそうな方法は
無いよなあ？

>>59
実際ボナの時は3ヶ月かかったとか言ってなかったっけ？

棋譜には通常、敗着手があるんだが、
それも含めて最善手局面としてパラメータ係数を学習調整しているのか？

中盤の指手で少しでも人間に近づいて、終盤の読み合いで人間側の読み抜けがあればPC勝てると

静的評価関数の最適化ってのがイメージできないんですけど
どういう意味があるんですか？

たぶんパラメータがイッパイあって
A：駒得、実際はズット細かく分れてると思う
B：手番
C：玉形
D：角道が通っている
その他、もろもろ１００個以上

評価値 = aA^2+bA+cB^2+dB+eA･7B+kC^3+lC^2+mC+nA･D+････
とかで、パラメータ、a,b,c,d,e,f,,,,,の値を理想に近づけて行く

>>64
評価関数のパラメーターを１００個にしてあの計算速度が出るのが不思議

Bonanzaの評価パラメータは10000個以上じゃなかったかな。
線形和パラメータの最適化にPCで3ヶ月かかったもんを
ニューラルネットで似たような事やろうとしたら最適化にどれほど
コストが掛かることやら。

なんだ線形和なのか、
相手が飛車持ってるときには陣形低い方が良いとか評価できるのか？

>>67
そういう組み合わせの評価項目を追加するなら線形和のままでもそれなりに行けるかもしれんけどね。

>66　>68
ボナの評価関数ってパラメータの線形和なのか？
単なる線形和じゃ評価関数として何の役にも立たないんじゃないか
と言う先入観（偏見？）があるんだが。

私がニューラルネットを少しかじったくらいしか知らないせいかね？

>>55 を読んだ限りは線形和だと思ったのだが、
間違っているようなら指摘してもらえるとありがたい。

>70
6ページ目の「最終的な目的関数の表式」
J(P0,...,ν)= ……　と言う奴が結局最小化したい評価関数（？）なわけだろ。

で、その中にl(P,ν)と言う項の線形和が有るが、これは

　　　ξ(Pm,ν):minimax探索の評価値

と呼ばれる形式不明の関数に対してさらにT(x)と言う明らかな非線形関数を
適用してから、それらの総和を取っているように見えるのだが。

誰か良く分かってる人、分かりやすく教えてくれないかなあ？

評価関数がなぜパラメータの単純な線形和じゃダメなのかようやく思い出した
（気がする）。

もしもそれが線形和で F(X1,X2,..XN)=A1(X1-B1)+A2(X2-B2)+……+AN(XN-BN)
と言うような形式をしていたとするとそれ（評価関数値）を最大（あるいは最小）
にするにはそれぞれのパラメータを単にその条件（局面）で許される範囲の
一方の端に振れば良いだけになってしまう。

答えはいちいち試行錯誤で値を代入し結果を計算してさらに他の値と比較する
（つまり手を探索する）までもなく自明であり、またあるパラメータ値は
ある程度大きい方が良いが大きすぎてもまたいけないというような
「中庸」の必要性が全く表現できなくなってしまう。

と言うような理由だったと思う。

weigtを|a|+|b|+|c|+・・・=1
a*a+b*b+c*c+・・・=1にしろ

１次関数ですこまで行くなら、PCも人間もたいしたことないって事？
神様からは程遠い
神様が指したら１局に２０手位の羽生マジック飛び出しそう
もちろん、人間の感覚では鬼手･想定外って事で、神様にしたら当然の最善手

と言うか１次関数で表現できるような問題なら、制約条件は多少ややこしくても
とっくに前向きの計算だけで解ける、試行錯誤なんか必要ない規模の問題だと思う。

で、（多分）将棋はそれほど簡単に解ける問題じゃないんだよ。

>>74
難しいことを考えつくからすごい、というんであれば、PCの将棋は評価されないよね・・・

例えば羽生マジックでもこないだの△３九龍でもいいけど
読みがもっと深ければ、現在のボナ*程度の*評価関数でもその手に気づくかもしれない
指されてみればなるほどね、というわけで、10数手先にはその手が好手だという理由がもっとわかりやすくなるだろうから
まぁ、かもしれない、なんだけどねw

人間とか神様？がすごいのは、その嗅覚というか、先を予見する力であって
（もちろん違う側面もあるんだろうけど、それはちょっと脇へ置いといて）
PCはそんな力を身につけようというわけじゃない

「遠い先」を力任せに読むことで、それを「近い将来」にすることができる
で、「近い将来」であれば、そんなに正確な評価関数でなくても、かなり正しい評価ができる
判りやすく優劣のついている局面だろうからね。たとえて言えば、ボナ先手優勢5000とかw

PCが目指してるのはそういう強さ
そうじゃない、そんなんじゃない強さがいい、なんて人もいっぱいいるけど
PCらしい強さ、PCにしかできない強さというのはそういう強さ

>74
もしかしたら誤解されてるかも知れないので私の理解（考え）を書いておくと
人間が指す将棋も現在のコンピュータ将棋が指す将棋も評価関数が線形（一次）
関数で済むような簡単な手法で指し手を決めているわけじゃないと言う事だよ。

もし関数表現するなら多価（多変数）で高次の非常に複雑な関数の最大値
（or最小値）を与えるパラメータを探索している事になる（と思う）。

つまり人間も現在のコンピュータ将棋もすごく難しい計算？をしているのだが
それでも将棋の神様には遥か遠く及ばない（のだろう）。

中盤と終盤で別の関数使えば、共に１次でも全体的には線形じゃないわけで
その場合は局面進行を評価する別の関数も必要になるよな

100個の変数で２次関数なら100*99/2=4950個もの二次の項が出て大変そう。

100*100/2 じゃないのか？？

101*100/2じゃない？

>79 には二次の項って書いてあるぞ

適当に書いたんだけど二次の項って何？

変数がX、Ｙ、の時

aX^2、aY^2、aXY、が２次の項だろ
aは任意の係数ね

a,b,cはweight、x,y,zは変化する数値
一次式　ax + by + cz + ・・・

二次式
a(0)xx + b(0)xy + c(0)xz + ・・・
a(1)yy + b(1)yz + ・・・
a(2)zz + ・・・

3変数ならば　3　+　2　+　1個のwightが出てくる
n変数ならば　n + ・・・ + 3　+　2　+　1個のwightが出てくる

n(n+1)/2が正解

線形とはそういう意味か？
調整したいのは高次元係数空間の係数であって係数の一次式で表すというものだと思ってた。


最小自乗法の線形・非線形の意味とは違う考え方なんだね。

>>81でよかったのか

間違えた

n(n+1)/2 + n (プラス一次の項)

>>88
そこまで数えて何故にゼロ次の項を数えない

n(n+1)/2 + n + 1(プラス ゼロ次の項)

ﾎﾞﾅﾝｻﾞの評価関数で係数はたくさんあるけど変数の値域はほとんど0または1じゃない？
0と1は何乗しても変わらないからほとんどの2次以上の係数は無意味では？

変数Ｈ：持ち駒の歩の枚数

０枚　Ｈ＝０
１枚　Ｈ＝３
２枚　Ｈ＝４
３枚　Ｈ＝５
４枚以上　Ｈ＝６

とかじゃね？

>>89
ゼロ次の項は先手番と後手番の評価で相殺されるはず。

>>92
うん、序盤から終盤、終局まで同一の評価関数で済めばゼロ次項は考慮外だよね。

>>93
ん？
序盤、終盤、終局を違う評価関数でやってもそれぞれのゼロ次項は考慮外では？

>>91
ﾎﾞﾅﾝｻﾞの場合は
０枚　Ｈ＝０
１枚　Ｈ＝h1
２枚　Ｈ＝h2
３枚　Ｈ＝h3
…
ていう風に係数を分けていたと思う。
これは歩の枚数に関して各評価値を通る高次の関数を表わしているとは言えまいか？

あ、私がずれた事を書いてることに気が付いた(´･ω･｀)ｼｮﾎﾞｰﾝ

ボナンザのアルゴリズムって局面を静的評価関数で数値化して次の局面への最善手？を全幅検索してるの？（ここからよく分からん。）

でも静的評価関数のベクトル？（特徴空間　Q値みたいなもの？としたらある局面における最善手の評価値の集合）を求めるにはパラメータが多すぎるので
機械学習させましたと。　　その後最適制御を用いてってあるけど、どうみても実際の手とボナンザの手との誤差を最小にしてるようにしか思えない…
よく分からない…　　後は目的関数に高速条件と化学習を防ぐ項を加えて、誤差が最小になるベクトルを6万局面回して学習させ、
特徴空間を作った。かなぁ？　
ようするに学習によって6万局面での最適手の集合を学習させ、全幅検索で運用したら強かったってことかな
正直分かりません。（＞＜）　特に最初の一行が間違ってたらグダグダなんで、もしそうなら教えて

いい加減、手筋おぼえさせろよ

若干、スレの主旨から外れるかもしれないが、
評価関数を検討する上で関連があると思うので、プロ棋士の感覚について書かれている本を紹介。

[読みの技法]
　ある局面について、羽生、佐藤、森内の三者が自分の読み筋を解説する本。
　非常にハイレベルな内容。プロ棋士の読みの深さや広さを知って驚いた。

[森内俊之の戦いの絶対感覚]
[佐藤康光の戦いの絶対感覚]
[羽生善治の戦いの絶対感覚]
[谷川浩司の戦いの絶対感覚]

　絶対感覚シリーズ。読みの技法の各個人版。
　これも非常にハイレベル。レベルが高すぎて付いていくのは難しい。

[注釈 康光戦記]
　佐藤康光の自戦記。この本もプロ棋士の凄さを垣間見ることが出来る本。
　対久保戦の玉頭戦が一番面白かったが、対藤井戦の「将棋を創っていく感覚」や、
　対谷川戦の超ハイレベルな終盤戦も面白かった。
　また対羽生戦（佐藤負け）の羽生完勝譜は圧巻。

[上達するヒント]
　羽生が書いたアマ初段〜二段ぐらいが対象。
　大局観を養うことを目的としている本で、将棋の考え方が書かれている。
　この本を読んで初めて、羽生がとてつもなく強いことを実感した。

[羽生善治の終盤術(1) 攻めをつなぐ本]
　終盤の考え方が次の一手形式で書かれた本。これまた非常にハイレベル。
　羽生マジックの何たるかもおぼろげながら知ることができる。
　決して「5手目に有利になる鬼手」ではないと思った。
　そもそもマジックではないのだが、あえていうなら「局面のテーマに沿った手」か。

ボナの評価関数は，各特徴ベクトル自体が非線型性を持っているので
全体としては非線型．学習させる都合で最終的な形は線型和を使ってる．
もう一つ特徴的なのは，評価関数の最適化と探索アルゴリズムが無関係でないこと．
両者を組み合わせた探索の結果がプロの棋譜と（できるだけ）一致するように
係数を調整してる．これまでの評価関数の自動学習と異なるのはこの点．
運動制御（軌道＝探索経路）の最適化というのはこういう意味．

探索アルゴリズムは関係ないんじゃないの？
１手読み＋静止探索で一致するようにしてるんでしょ

違う．本人と話したから間違いない

具体的なやり方は？

つーかあのpdfに書いてある方法では今はやってないってこと？

いや，あの pdf の発表の時(GPW)そう言ってた
読み違えてるんじゃね？

，とか．とかの特徴的な句読点の使い方は・・・・・・

>>105 当たり！ｗ
>>103 補足　これ書くの二度目だと思うけど
９頁の左下の玉頭の歩の重みがゼロになってるのが探索アルゴリズムの影響だと言ってた

玉の１つ上の敵の歩だよね
王手がかかっている局面は末端にならないとかじゃないん？
よくわからんけど

スマソ　詳しい話は忘れた

>>99
で、どれが一番ハイレベルなの？
一冊だけ読んでみたいんだが

>>109
あえて一冊に限定するなら「読みの技法」。

なぜ地平線効果の単語が出てこないんだ？

>111
どういう意味？
ボナがどうやって地平線効果を解消しようとしてるか知りたいって事？

ホシュ

ま、いちおう言っとくけど、
a+bx+cx^2+dx^3... (1)
も線形と呼ぶ。
なぜなら、
入力は
x=(1,x,x^2,x^3...)
というベクトルであらわせて、
係数ベクトルを
w=(a,b,c....)とすれば
(1)はxとwの内積で表現できる。
だから、線形と呼ぶ。

ボナンザの場合、
x^2とかそういうのはなくて、なんらかの特徴量が入力ベクトルになる。
例えば、(3,4)に飛車がいたら1いなければ0
みたいなね。
だから、この特徴量の選び方がとても重要になってくる。
無限個の特徴量を作っていいなら、
全てのパターンを記憶できるので、
最適戦略を表現できる。
ただし、その分だけ学習データが必要になる。

ノイズを除去するためにも、自由度（パラメータ数）の２倍程度は
学習データが必要かもね。

あと、線形モデルの場合、いわゆる最小2乗法と同じで
最適なパラメータは一発で出るけど、
ボナンザの場合、学習データから直接評価値が求まらないから、
ごちゃごちゃしてる。

それじゃ

>>97
だいたいそんな感じ。
特に間違ったことは言ってない。
制御とか関係ないよ。

>制御とか関係ないよ。
全然分かってないな
例えば、腕を動かす時最終位置だけでなく途中も最適にするのが運動制御
Bonanzaは探索の途中の経路も含めて学習するために制御理論を使ってる
保木氏がこれまでの評価関数の学習方式に納得できずに自ら考案した
これまでの学習方式とは基本的な考え方から違ってる

>探索の途中の経路
棋譜にそんなデータないのにどうやって学習してるの？

>114
関数が線形である（線形和である）と言うためには普通、係数ベクトルと
掛け合わされる方のベクトルが全て一次独立である（互いに従属でない）
と言う条件が必要だと思うが。つまりは基底ベクトルの線形和と言う事で
あり、そのベクトルで張られる超空間内の超平面で表現できると言う事。

そういう制約が全く無しにパラメータ（ベクトル）がどんな高次で
かつ互いに複雑な相関が有っても良いのならそれが例え、どんな関数で
あっても（見かけ上）線形和で表せるのは当たり前だと思うが。

しかし、通常そういう場合には最小二乗法とか線形計画法とかの
分かりやすい解法は使えないと思われる。

>>118
関数が線形であるというのは、
例えば、f(x+y)=f(x)+f(y)。
関数モデルが線形というのは、
f(x;w)+f(x;z)=f(x;w+z)
ということ。wとzは係数。

xとx^2は基底関数として独立だよ。

>どんな関数であっても（見かけ上）線形和で表せるのは当たり前だと思うが。
例えば、マクローリン展開とか、フーリエ級数展開ね。
だけど、有限個の項で近似する場合、誤差がでてしまう。
その誤差を最小にしようというのが、最小２乗法。

最小２乗法は、例えば勾配法などを使って解くことができるけれど、
線形モデルの場合は、1回の行列計算で解析解が求まる。

関数近似じゃないけれど、
2次計画法を使って係数を求めるサポートベクターというのもある。

機械学習では、基底関数と係数を同時にデータから決めるということをやっていて、
そういうのではEMアルゴリズムがよく使われる。

どれも、誤差関数を最小化するための、最適化アルゴリズム。
線形計画法も最適化アルゴリズムだけれど、学習に使われることはあまりない。

参考書としてelement of statistical learningがおすすめ。

>>116
>例えば、腕を動かす時最終位置だけでなく途中も最適にするのが運動制御
>Bonanzaは探索の途中の経路も含めて学習するために制御理論を使ってる
学習データとして、
局面:p
手:m
の組み合わせの集合{(p,m)}が与えられてるわけだよね。
これはつまりオススメ合法手の集合です、と。
今、評価関数f(p,m)を簡単に作る方法を考えたい。
学習データに含まれているp,mに対して、
f(p,m)=1
それ以外でf(p,m)=0
となるような関数を作ることを考えれば、
経路も同時に最適化される。
これが普通の機械学習だと思うのだけれど、
これに対してボナンザはどこが新しいの？

>120
自分で（評価関数の）学習をやってみりゃ分かる
>f(p,m)=1
>それ以外でf(p,m)=0
なんてやり方じゃうまく行かないから

あ忘れてた
>となるような関数を作ることを考えれば、
>経路も同時に最適化される。
>これが普通の機械学習だと思うのだけれど
全然違う

>>121
全然うまくいかない理由は？
ゲーム木探索をしない場合は、俺が書いた
「普通の機械学習法」の方が上手くいくよ。

例のスライドの
ξ(p_m,v):minmax評価
を
f(p,m;v):ただの局面評価
だと思えば、Jの最小化は最小2乗法もどき。
(pが局面、mが手,vがパラメータ)

Tの形が階段関数の場合、
「棋譜で指された手よりも良く判断してしまった合法手の数」
の最小化をすることが明記されてる。
それから、Tを1次関数にすれば、最小2乗法と一致する。
学習データに含まれるものをf(p,m)=1とし、
学習データに含まれないものをf(p,m)=0とすることと、
正規化項をつけることは等価。

ξ(p_m,v):minmax評価
は解析的な関数じゃないので、最適化しにくいけどね。
スライドによると、なんらかの近似をしてる。
（次の局面の評価値か？）

>>122
何と何が違う？
上記したものは、「普通の機械学習」だけど。

ここまで書いて思ったんだけど、
普通に機械学習すれば
ボナンザより強いプログラムできるんじゃね？

ξっていう、minmax評価値の方をあえて最適にしようとしてるけど、
次の局面の評価値f(x,m)を近似として使ってるなら、
ダイレクトにf(x,m)を学習するのとほとんど変わらない。

あとは学習データをどれだけ用意できるかと、
どのような特徴量の線形和を考えるかが肝ってことかも。

ボナの学習最適化の手法には数十万の棋譜が必要みたいだね。
プロの棋譜だけで学習すればいのにという話に、それでは棋譜の数が全然たりない
という話があった。江戸時代の棋譜を使ったのもとにかく大量の棋譜が必要
だったからかと。

>>125
ボナって大量の棋譜をつかって平均化したわりには
個性的な将棋を指すよねｗ

>全然うまくいかない理由は？
それが分かればとっくに強いソフトができてるはずだろ。
長い間多くの人が評価関数の学習に取り組んでものにならなかったという歴史がある。
だから保木さんの手法が革新的なの。

>>127
そりゃ説明になってないんじゃね？

>>125
スライドにはプロ3万局と、将棋クラブ3万局、と書いてあるけど。
学習データの量と強さは直結するから、多ければ多い程いい。

>>127
>長い間多くの人が評価関数の学習に取り組んでものにならなかったという歴史がある。
線形モデルを使った例があるなら、ソースキボンヌ

上記したとおり、ボナンザのやり方と、
通常のやり方に大きな差はない。

>>128
解説して損した気分だ。数式を読む力もないみたいだね、彼には。

昔の学習は自分自身同士を延々と戦わせて評価関数を調整するという感じじゃなかった？
人間の高段者の棋譜をもとに評価関数を作ったのってボナンザ以前にあったっけ。

>>130
お前は一体何を言っているんだ。
初期のころの柿木将棋ですらプロの棋譜から駒の価値を求めているんだが？

この人はボナンザと同じことしてるね。
http://d.hatena.ne.jp/mkomiya/20070401/p2

激指も、棋譜情報を活かすとかやってたっぽいけど。

ちゃんと学習してる人は、いないっぽいな。

>>131
ソース

>>133
1985年当時の「マイコン」(←これが雑誌名)
と「コンピュータ将棋」 サイエンス社, 1990

Bonanzaの新しい点の一つは学習対象のパラメータが万を越えること
今までにはこんなむちゃくちゃな数を用意したものはなかった

穴熊で一手一手で受けがなくなるパターンとか
一手稼げるパターンをデータベースに出来ないものだろうか。

>>134
そのソースはたどれないな。
まあ、DeepBlueにも学習機能はあったらしいけど、
どこまで「まとも」かは・・・。
まあ、過去についてぐだぐだ言っても意味ないので
この辺で打ち切りますか。

機械学習のアルゴリズムが統計の専門家以外でも使えるように
整備されてきたのは2000年前後だと思うので、
ボナンザ出現のタイミングは妥当と言えば妥当かも。

>>137
>>まあ、DeepBlueにも学習機能はあったらしいけど、
あったらしいけどって・・・いやありますよ確定事項で。
チェスでは評価関数は自動学習が当たり前。

終盤は駒が減って組み合わせが減り、かつDB化もなされている。
なので終盤については評価値を正確に求められ評価関数の適切な学習が可能だった。
そこで終盤の評価関数を定め、次にこれを使って中盤の評価関数を学習し・・・
というやり方で逆にたどる事で世界チャンピオンを超えるレベルに到達している。

将棋ではそんな手法は当然使えないのでこれまでは人間が評価関数を作っていた訳。

>>126
そんなもんだろ。平均化といっても、かなりの広範囲に渡ったものを独自の視点で解釈したわけだし。

>139
「解釈」はしてないと思う、少なくとも保木さん自身は。
そういう人間（開発者）の好みが入らないのがボナのみそだと思われ。
自動学習してるうちにその学習によって出来上がった評価関数が
勝手に解釈し始めたと言う可能性はあると思うが。

>>138
チェスでは当たり前なのか。
まあ、発想は当たり前なので、
まともなアルゴリズム=線形回帰＋最小２乗が使われているかが問題かな。

>終盤は駒が減って組み合わせが減り、かつDB化もなされている。
>なので終盤については評価値を正確に求められ評価関数の適切な学習が可能だった。
>そこで終盤の評価関数を定め、次にこれを使って中盤の評価関数を学習し・・・
なるほどね。
将棋は王をとった/とられた瞬間の評価値しかわかんないからねぇ。
そういう意味で、チェスに比べて、将棋の方が
評価関数の学習が重要になるわけね。

俺も学習する将棋作ってみようかな。
でも、時間も棋譜もないなぁ。

書いててフト疑問に思ったんだが、ボナはプロの棋譜中に現われる特定の
局面の指し手に対して何らかの重み付けを与えて学習させてるんだろうか？

例えばより高段者の指し手に対して重み付けを高くするとか、考慮時間の
長い対局ほど高くするとか。

あるいは同一局面について複数の指し手が出てくる場合は単に頻度のみで
選んでるのか？

うまい事重み付けしないとボナの評価関数は平均的なプロ棋士の
棋力を（原理的に）上回れなくなりそうな気がする。
それでも、この学習された評価関数の汎化能力は非常に驚異的だと思うが。

>142
棋譜に関しては「棋譜」「データベース」で検索すればWebのあちこちに
転がってると思うが。そういう方法ではなく真正面からプロ棋士の棋譜を
（対価を支払って？）入手する方法があるのかどうか俺は知らない。

将棋の定跡データベースだったら、以前日本将棋連盟の新潟支部か
どこかが（有償で？）配布してたと思うがまだやってるのかなあ？

棚瀬将棋、柿木将棋がボナと同じ学習させたらしいと
どこかのブログにかいてあった。

将棋年鑑をスキャン＆ＯＣＲ

>145
そういう話は良く聞くけど、どこまで本当かなあ？
ボナ流の評価関数を使うと言う事は今までの人間（作者）が評価関数を考えて
与えるやり方を一度捨ててしまわないと不徹底なものになる。

今まで苦労して作ってきた自分のそう簡単に捨てられるものかねえ？
また、今更ボナと全く同じような学習をして同じような手を指すソフトを
発表しても意味無いだろうし。評価関数のパラメータ選びに工夫の余地は
あるかも知れないが。

書いてて、またまたフト思ったが途中（一定深さ）まではボナ流儀の
全幅探索と評価関数で押し切っておいて、しっかり考え込みたい（怖い）
局面まで来たら人間（プログラマー）が考えた評価関数で大幅に前向き
枝狩りしながら、さらに深く読むと言うやり方はあるかも知れんな。

ボナ自身、竜王と対決したバージョンには全幅探索した局面から、
さらに深く前向き枝狩りしながら読む手法を付け加えていたそうだし。

どうやってさらに深く読みたい局面だと判定するのかは知らんけど。

>>147
CSAの一月例会で柿木さんが発表してる。議事録の一部を貼ると
>・保木さんの成果に倣い、玉との位置関係による駒の価値の自動学習を行った。
>　・参考: GPW2006「局面評価の学習を目指した探索結果の最適制御」
>　保木邦仁(http://www.computer-shogi.org/gpw/gpw11.html)
>　・綺麗に学習できることが確かめられた。

>>149
GJ!!
キレイに学習ってなんだよって突っ込みは当然あったんだよねwww

>>148
>ボナ流の評価関数を使うと言う事は今までの人間（作者）が評価関数を考えて
>与えるやり方を一度捨ててしまわないと不徹底なものになる。
人間の書いた評価関数をデータ（棋譜）で修正することはできるけど、
大量にデータがある場合は、そんなことする意味は全くない。
ハンドコーディングの評価関数はなるべく使わない方がいいだろうね。


>>143
その指摘は正しい。
ボナの中の人もきっと悩んでると思う。
実際には、勝った側の手筋が+1、負けた側の手筋が-1みたいなことになってるはず。
でも、高段者同士なら、+1と+0.9とかが本来の重みになる。
そういう意味で、今は人間の指し手を学習して、
探索で稼いでる面が大きいと思う。

はぁ、また半可通か

>151
何となく気持ちは分からないでもないが、おかしいと思うところがあれば
具体的に指摘してもらえると有り難い。スレもにぎわうしｗ。

多少、カドが立つかも知れんが他人に分かるように書いてるうちに
自分の考えが整理されてくると言う事（利益）もあるよ。

だれか、このスレで今まで議論してきた議題と争点を整理してもらえないか？
議事メモ的なものがあると、ありがたいのだか。

結論が出ているか、出ていないか、はっきりするし。

議論なんかで結論が出るわけないじゃん

結論を出すのは鉄則だって。結論があやふやで終わったら、議論の意味がないから。

まあ、結論保留なら、それはそれで、そう書かれていればいいよ。
ポイントはステイタスをはっきりさせるってところに尽きるわけね。

>>119 の f(x;w) ってどういうもの？

横からスマソ
　>> ID:H2QsQun4 がバカな事だけは解った。

そうだね。

いや、別に議論したくて、ましてやそこから何らかの結論を導き出したくて
このスレを立てたわけではないんだが。

これは社会学とか政治などの話じゃないので議論しての結論より証拠が一番。
そういう意味じゃ自然科学に近いと思う。議論の論点を整理するのは皆に
分かりやすくて良いかも知れないが、それを書く人が相当良く分かってないと
的ハズレになりかねないからねえ？

私は自分の疑問を口にでき、自分の知りたい事を遠慮なく質問する事ができる
（あるいは勝手に答えを誰かが書いてくれる）ようにスレを立てました。

後は各自、興味があれば自分で調べるなり試しにプログラムを作るなりして
みれば良いかと（エエ、純粋に利己的な動機からですｗ）。

最近このスレに住み着いてる俺ｗ
疑問にならなんでも答えるお。

f(x,w)は
x=(x_1, x_2, x_3...x_N)
w=(w_1, w_2, w_3...x_N)
というベクトルを考えていて、
線形モデルは
f(x,w)=Σw_i×x_i
ということ。
ここでxというのは局面の情報で
例えば、x_1は(1,1)に歩があるかないか、みたいな感じ。
どうやってデータからwを決めるかについては、参考書を読んでみて。
理解するのは簡単じゃないから、説明しても無意味だと思うので。

例えば
データ学習アルゴリズム　渡辺澄夫
これは絶対買った方がいい。
英語が読めるなら
element of...
も買うべき。

>だれか、このスレで今まで議論してきた議題と争点を整理してもらえないか？
>>1-1000

自分でやれよアフォウ！！

マジレスすると
全部答えてやるから、疑問を全て箇条書きにしてこい！！

>>163
ボナンザは中盤で何手先まで読んでるの？
５手先？
ボナンザ同士を対戦させて評価関数の優劣評価が逆転するのは何故？
互いに５手読んで最善手指して、５手以内に優劣評価が何故に逆転するの？

>161
ヘッヘッヘ！　それで全部じゃないんだな。
このスレの議論は「ボナンザ Bonanza　専用スレ　8手目」後半（600辺り）
http://game12.2ch.net/test/read.cgi/bgame/1168758137/
からの話の流れをそのまま引き継いでいる。

このスレだけ読んでも話の流れは完全には分からないんだな。

>163
そう慌てなさんなって。アナタにはいろいろ教えてもらって感謝している。
ただ正しい質問を投げるためにはこちらも相当、問題を理解していないと
不可能なんだと言う事を配慮してもらえるとアリガタイ。
（要はユックリ付き合って欲しいと言う事ダナ）

>ボナンザは中盤で何手先まで読んでるの？
設定による

>ボナンザ同士を対戦させて評価関数の優劣評価が逆転するのは何故？
評価関数が間違ってるから

>互いに５手読んで最善手指して、５手以内に優劣評価が何故に逆転するの？
評価関数が間違ってるから

>164
ボナンザ同士（かつ同じバージョン）を対戦させて本当にそんな事起きる？
もし起きるとすると両者の評価関数または探索の深さがどこかで異なって
いない限り有り得ない気がする。

先手後手の立場が違えば時間の使い方の関係なんかでそういう事も起こり得る
のかなあ？

君、やってみた？

>>166
同一の評価関数(完璧ではないのは当然)で最善手を指して、その同一の評価関数の評価が５手以内に逆転するのは何故？

>>168
ベルマン方程式を満たしてないから

>>167 ID:U7iYhmSo さんは ＯＫ

>> ID:F20F8f3n さんは、
> マジレスすると
> 全部答えてやるから、疑問を全て箇条書きにしてこい！！
とか書いてたけど、やっぱりアフォウ

試してゴメンネ。

>>160 Thx

>> マジレスすると
>> 全部答えてやるから、疑問を全て箇条書きにしてこい！！

保木さんチャートの読み方を教えてくれ

http://www.geocities.jp/bonanza_shogi/gpw2006.pdf

・beta cut ていうのは αβ と同じ?
・futility pruning とは?
・Bitboard? Aspiration search? PV search? 0.5手延長？
再帰的反復深化？SEE? stand pad?
・通常探索と静止探索ってどう違うの？
・拘束条件？ペナルティー？

わからない理由も書いてくれたら、真剣に答えるお

>>172
理由も何も用語を知らないからな
>>168
それは局面が進んで５手前より読みが深くなったから

>>172
google未満のことは答えないお

>173
オイオイ！　>168は >164で
「ボナンザ同士を対戦させて評価関数の優劣評価が逆転するのは何故？」
と書いてある。こっちの方が問題だろう？

対戦相手がボナ自身でないなら（極端な話、渡辺竜王など）相手の読みが
ボナを上回れば、評価関数の優劣評価が逆転するのは幾らでも起こり得る話だ。

>>173
> >>168
> それは局面が進んで５手前より読みが深くなったから

うん、それが正解と思う。

>171
これだけは私も回答できる。

・beta cut ていうのは αβ と同じ? 答え：同じ

こないだ、「おまいら最強の将棋プログラムしてみろよ part5」スレで
質問して(No.956)答えをもらったので間違いない。

ttp://pc11.2ch.net/test/read.cgi/tech/1109307327/

じゃ勘で書くから訂正してくれ

・beta cut --> αβ. 最善手 a0 に対して他の手 a1...an を読むときは a0 の
ときより点を悪くするような相手の応手 b1...bn があること以外は読まなくてよい
・futility pruning --> 相手の悪手っぽい手(評価が明らかに落ちる手)は読まない
・Aspiration search? --> search window を制限して読みを絞る？わからん
・反復深化--> iterative deepening. 時間の許す限り読みの深さをあげていく
・Bitboard --> データ構造

まだよくわからない用語

・0.5手延長？ SEE? stand pad?
・通常探索と静止探索ってどう違うの？
・拘束条件？ペナルティー？

>174
こういう専門用語の意味が解説されてる参考文献をいくつかリストに挙げて
あげたら？英語の文献しかないかも知れんが。

俺も助かる（ソレガホンネｗ）。

>>168 >>175
評価関数っていうのは局面に対して定義されるわけだけど
画面に出てくる値っていうのは読みを入れて計算するわけだよ

いま５０手目なら例えば５５手目まで双方が最善手を指した局面の評価関数の値を表示している

５５手目まで進んだら今度は６０手目の局面の値になるんだから結果が違って当然

>180
いや、それは前提として分かってるって。ただし >168は

「"同一の評価関数"で最善手を指して、その"同一の評価関数の評価"が５手以内に逆転するのは何故？」
と書いてるわけだ。つまりボナならボナの同じバージョン同士と言う事だろう。
その条件下で互いに指してるうちに途中で評価値が本当に逆転するとしたら
（先手有利、後手不利 -> 先手不利、後手有利あるいはその逆）
その理由はもう少し微妙（込み入った話）だろう。

どういう状況かいまいち理解できない。

先手が5手読み→最善手がAで評価値+10→そのAを指す
後手が5手読み→最善手がBで評価値-7→Bを指す
先手が5手読み→最善手がCで評価値+2→Cを指す
後手が5手読み→最善手がDで評価値+4→Dを指す
先手が5手読み→最善手がEで評価値-6→Eを指す

このケースを5手以内に逆転してるって言ってるの？

>>181 そうだろうか？

本当にお互いに最善手しか指してなくても

評価関数(５５手目局面) ≠ 評価関数(６０手目局面)

はありえるでしょ。評価関数というのは間違っているわけだから

>182
ウン、多分そう言う意味だと思う（と私は解釈している）。

ただし、そういう事が>164 ID:NwAohz5r の言う通り、ボナの同一
バージョン同士を戦わせて本当に起こるのかどうか疑ってもいる。

実際に実験しないで思い込みかヒッカケで書いたんじゃないかなー？と。

これだったら起こるのかどうかじゃなくて
起こらない方が不思議なくらい当然なことなんだけど。
これが理解できないなら話にならないような。

>183
評価関数は間違っている（完全じゃない）のは当然としても
先手と後手双方が同じその「間違った評価関数」を使って
同じ手数だけ先読みしたら読み筋が互いに一致するんじゃないか？

それなのに評価値が途中で逆転するとはどういう事だろう？

先手・後手は互いに自分の手番に来た時に一手ずつ深く先を読んで行く
わけだから水平線効果が起きるような指し手があれば起こり得るかな？

いや一致しないから。
次の読みを4手読みに減らしたら評価値と読み筋も一致するけど。

>>185
でもこれくらいも説明できないってのも…

もう一回別の言い方で説明するぞ

・理想的な評価関数は理想の最善手を指すかぎり値が変化しないのが正しい
・ボナの評価関数はボナが思う最善手を指しているかぎり値が変化しないべきだとも思う

でも現実の評価関数ではそのどちらの性質も成り立たないんだよ

現実の評価関数っていうのは持ち駒の数とか駒の位置関係で適当に決めてるだけ
なんだから手数が進めばほとんどランダムに値が変わっちゃうわけ

当然値の＋−が変わっちゃうこともありうるんだけれど…どうわかった？

>187 >188
原理的には確かにそうだと思うが、ボナの指し手同士がそんなに頻繁に
読み筋が食い違うほど評価関数が不正確かねえ？

実際には一局の中でも一回あるかないかくらいの見つけるのも大変な現象なんじゃ
なかろうか？そんな事、実験して追跡してみた事無いから分からないけど。

さてぼちぼちいいかな
>>152
半可通って言葉の意味を辞書で調べてみろ
それで俺の言いたいことは分かるはずだ
話はそれからだ
今まで何度も相手してきたが
お前には他人の言葉を真剣に聞こうという態度が見られん
学習に関しては本をたくさん読んで勉強しているようだが
それを実際の応用に適用してアルゴリズムさらにプログラムにするという
産みの苦しみを知らん奴が保木さんの成果を貶めるのには我慢がならん

ところで渡辺戦の終盤の一手一手が見えない問題っていうのは
どう解決すればいいのか結論は出てる？

・評価関数で一手一手局面を判断→難しそう
・枝刈り読みで最後まで読む→時間がかかりそう

ということで今までの手法じゃ難しそうだと思うんだが…どうだろう

詰みまで読めなくても「一手一手局面である」ことだけを判断して
それを評価に入れるというようにはできないのだろうか？

>190
エー、おれの事？
自分が「半可通」なのは認めるがおれは保木さんの事をこれまで貶した
つもりは無い。むしろ非常に尊敬している。ボナの事を良く知らなかった
何ヶ月も前なら不遜な事を言ってしまっていたかも知れないが。

誰か他の人の発言とゴッチャにされとるようだな。
でもそれが誰かを言うとそれもまたカドが立つので言わないけど。

保木さんの学習方式を「普通」と言ってたのはお前さんじゃなかったか？
もしそうなら確かに俺がごっちゃにしてたことになる
言葉の使い方が似てるから同一人物だと思ってしまった
謝罪する

>193
いや、全然別人。大体、俺は「普通」の学習方式がどんなものか良く知らない。
（だから知りたいと思っている。それとボナの方式の違いも）

だが、俺は（多分）君がターゲットにしている人も結構、尊敬してるんだよね。
いろいろ参考文献とか有用な情報を教えてくれるし。

>191
「一手一手局面」って「この指し手を放っておいたら次で詰ますぞ」と言う
「詰めろ」の局面だと言う事だよね。つまり相手に手番を渡さない。

それを評価関数で別に評価する事も出来なくは無いんじゃないかなあ？

必至や詰みの速度争いを正確に評価するのは難しそうだけど。

>>195
> それを評価関数で別に評価する事も出来なくは無いんじゃないかなあ？

読みを入れないで局面だけ見て詰めろってわかるものなの？

そもそもあのボナの判断ミスはどっから来たんだろうな

・詰みは読めなかった
・評価関数的には味方の玉形＞＞＞＞＞＞＞敵の玉形

ということであの結果っていうことでいいの？

>196
ウーン、確かに一手は読んでそこから詰み探索ルーチンを呼び出さないと
気づきようが無いか。でも放っておくと次に相手に王手を掛けられてしまう
事は分かるよね。それでも最低二手は読んでるわけか。

これは申し訳ないことをした。改めてごめん _(o)_

>>194宛てね

>>195
>「一手一手局面」って「この指し手を放っておいたら次で詰ますぞ」と言う
>「詰めろ」の局面だと言う事だよね。つまり相手に手番を渡さない。

一手受けて詰めろを外してもまた次の一手で詰めろがかかる

最終的な受けなしまでは読めなくても
「詰めろが切れない」感じを評価に入れられないかなと思った

>198
いえいえ、そんなお気に為さらずに。

>200
ウーン、「詰めろが切れない」事に気づくためには「詰めろ探索専用」
ルーチンが必要な気もする。で、最初に詰めろ（放っておけば王手）が
掛かった時にそれを呼び出すと。

CPU時間がそれに相当、食われそうな気もするな。

知っている範囲でまとめてみます

minimax．．．-法， -アルゴリズム，-原理， -戦略
αβ．．．．-法，-アルゴリズム，-刈り(pruning)
などと呼ばれています．

「全幅探索」はαβ法を用いないピュアなminimaxアルゴリズムだけを指すんだ！と主張される先生もいらっしゃいますが，minimax評価値をαβ法で求める方法を含めて「全幅」と呼ぶのが普通かとおもいます．

αβを用いると倍の深さまで読める，というのは時折見かける表現ですが，

合法手の数が全ての局面で同じであり，評価の順序が神がかり的で常に一番良いものを先にすることができ，局面の展開(指し手の生成や局面の更新)に係る時間を無視することができるならば，
という条件が付きます．

>>203
さすがに空気を読まないと・・・

英語読めないと思うけど、英語でよければ
http://digilander.libero.it/mizarchessengine/papers.htm
wikipediaのalpha betaを読むとか。

まあ、
英語読めない&&馬鹿
だと話にならないので、どっちかを改善してから来なさい

>204
キミキミ、またそんなカドが立つような事を。
カドが立つ事を平気で言うのも空気が読めない部類に入ると思うぞ。

>>202
minimax 探索は敵玉詰み(+∞),自玉詰み(-∞) それが
わからなければ読めるところまででの最終局面の評価値を返す

でいま

▲１手目▽２手目▲３手目▽４手目…

と互いの最善手を読んだときに▽２手目▽４手目... が全て受けの手で
かわりに他の攻めの手を指せば▽玉の詰みがすぐ見えるような状況の場合は
最終局面の評価値を大幅に上方修正するようなことをすればいいんじゃないかと…

>それを実際の応用に適用してアルゴリズムさらにプログラムにするという
>産みの苦しみを知らん奴が保木さんの成果を貶めるのには我慢がならん
そんなの知らないってｗｗｗ

普通の機械学習と違うんだったら
どこが違うか指摘すりゃいいじゃん。
できれば、違いによって生じるメリットも加えてくれ。
できないなら、「同じ」でいいだろ？

「違う」と思い込みたいだけなら、自分の中で閉じててくれ。

んじゃ、さっきの発言取り消し

>初心者君
まず、
minmax探索の定義
を書いてみてくれ

>204
あ、参考文献がたくさん載ってるページ挙げてくれてアンガト！

>>208

- minimax 探索は木の上の探索
* 木のノードが局面
* 木の枝が手

- 木のノード n には深さが奇数(自手番)か偶数(相手番)かに応じて
以下のような評価値 v(n) が定義される
* v(n) = max{v(m) | m は n の子ノード } (ｎ が自手番ノードのとき)
* v(n) = min{v(m) | m は n の子ノード } (ｎ が相手番ノードのとき)
* v(n) = f(n) (n が読みの深さを超えたとき、 f は評価関数)

ルートの子ノードの中で最大の評価値を持つものを返す手を捜すのが minmax 探索

それコピペだろーがｗｗ
自分の頭で理解して、自分の言葉で書こう
何がポイントなのさ？

>>211
コピペじゃねーし
定義書けっていうから書いただけだろ
ポイントは互いに最善手を指した何手後かの評価関数の値を返すってだけ

それより>>206にコメントがほしい
詰みしか最終判断(+∞,-∞) の基準がなくていいのか
１０手連続で王手がきても大丈夫かもしれないが
５手連続で詰めろかけられたらほぼ終わってるのが将棋じゃないかと思うんだが

>>212
つ 水平線効果

コンピュータ君は無駄な手を探すのは得意だよ。
自分が負けそうになると無駄な王手を連続して指すのは良くあるでしょ。
無駄な詰めろを探して勝ちだと思うようになって駄目だと思う。

王手と違って詰めろが悪手ってそんなになくない？

>>214
駒をただ捨てしての詰めろとか。

詰めろ = 相手が"何もしなければ"詰み なので
悪手の詰めろは結構あるでしょう。

王手より詰めろの方が悪手が少ないと見積もる根拠は？

>>215
どんな場合？▽５１玉▽３段目飛車に▲金を持って持ち駒を
ひとつひとつ３段目に打っていってだめとかまああるかもしれないが…

話を渡辺ボナンザ戦に戻して
じゃあどうやったら２４歩で何手かあとに一手一手になるのを判断して回避できたと思う？

たとえば、相手は矢倉、こちらは敵陣2段目に飛車、持ち駒に金
3一金でも4二金でも詰めろ。でもまあ、金を取られてぜんぜん駄目

あと、5手連続の詰めろがあることを確認するには
詰め将棋探索のコストが相当高くなると思う。

>話を渡辺ボナンザ戦に戻して
そんな話をしていたつもりはないのだが。

「探索深さを十分深くして一手一手を判定させる」
「精度の高い評価関数を作って一手一手を判定させる」
というのがひどいが間違ってはいない回答。
具体的にどうやるかは知らん。

ボナンザの学習ってのを（相）穴熊の場合だけ別にやったらどうなの？

小宮日記
http://d.hatena.ne.jp/mkomiya/200704

難しかったが、断片的に分かった部分だけでも面白かった。

緊迫の一手 人工知能 VS 渡辺竜王　を地上波で再放送してほしいなー
ところで、この番組見た人いるかい？

>204 空気読まなくてすみません
URLにのっているαβは正しいのですが疑似コードとしては冗長な感じがします．
http://uguisu.skr.jp/othello/6-1.html
のNegamax探索法にのっているコードがシンプルで本質をついていると思います．

>208 >210さんが書かれているとおりです
min番では最小評価値を返しますが「最良のもの」の意味で「最大」と
書かれているのだと思います．

再度空気読まなくてすみませんでした

ＢＳでやってた運命の一手で一旦▲２七香車と打てば先手優勢ってプロが解説していた局面の手がなぜ
コンピュータソフトには読めないのでしょうか？
ほとんどのソフトがあの局面を考えさせると▲２四歩と打って自分が優勢だと考えているのはなぜなんだろう？
なにか読みづらい盲点というかそういうものがあるのでしょうか？
それとも単に読みの深さが足りないだけでもっと深く読めればあの手が発見できるのでしょうか？
△３九龍と飛車を切ってくる手をなぜか読みに入ってないんだよなあ。検討とかさせても・・・
何か重大な手を見落としてる事がソフトにはたまにある。

>150
＞実際には、勝った側の手筋が+1、負けた側の手筋が-1みたいなことになってるはず。
それニューラルとかの強化学習でやってるのと勘違いしてなくね？

ボナの学習は、最終結果から逆算というより、棋譜の全てが「次の１手」問題として
「それらしい手」を良いと思うような評価関数を作ってるんだと思うが

>222
一手一手を適切に扱えていないからだと思います．

そもそも一手一手を認識できないからじゃないのかな
一手一手ってどう定義するんだろう

>>222
＞△３九龍と飛車を切ってくる手をなぜか読みに入ってないんだよなあ。

△３九龍は駒損だからじゃなかろうか。△３九龍として先手玉が詰むわけでもないし。

>225
一手一手=受け方がどうやっても詰めろ，王手が続く
ですかね
対竜王戦の39龍以下は7手とか11手の詰めろが混じっているので見た目以上に大変そうです．

>>227
そうなると必死と変わらないような。
詰みはともかく、必死はそんなに強くないそうなので
何かブレークスルーがないと難しいってことかな。

>227
>そうなると必死と変わらないような。
そうか・・・必死問題と同じかも知れません・・・勘違い？

>それニューラルとかの強化学習でやってるのと勘違いしてなくね？
「ニューラルとかの強化学習」の意味がよくわからない。
ニューラルネットと、強化学習は完全に違う概念。
ニューラルネットは非線形モデルであって、
上の方に書いたのは線形モデルの話。
ボナンザは線形モデル。
だから、ニューラルネットのシンプルなものを使っている・・・
と言えば、当たらずとも遠からず。


>棋譜の全てが「次の１手」問題として
>「それらしい手」を良いと思うような評価関数を作ってるんだと思うが
f(それらしい手)＝１
f(それ以外)＝−１
「それらしい手」の定義：与えられた棋譜で買った時の手
実際にそうやっているかはわからないが、
ＰＤＦのＴの形による。
シグモイドを使う意味はない。

基本的には探索の深さが十分に増えれば解決する問題だろうね。
数十年待っていいのなら、それだけでもプロに勝てるような希ガス。

一手透きはパス手との絡みで、ヒューリスティックに危険度を求めてから
閾値を越えたら一部のＣＰＵを分配して専用ルーチンで確認とかそんな
方法はないのかな。

今の並列探索ってホモジニアスな方法のみっぽいのかな？
終盤なんかは複数ＣＰＵにそれぞれ別の仕事をさせてもいいよね？

ゲーム木探索というのは、
末端ノードの評価関数が与えられた時、
minmax探索の結果を求めるという問題。
この問題に対するアプローチは
厳密解法
近似解法
という二つに分類される。
厳密解法というのはminmax探索と同じ答えを与えることが保証されていることを意味する。
厳密解法の代表例はαβね。

だけど、厳密解法は深さに対して指数的な時間がかかるため、
近似解法が研究されている、と。
近似解放というのはある「仮定」をいれたもとで定式化されると思うのだけれど、
どんな仮定があるのか知ってる人がいたら、教えてエロい人。

>数十年待っていいのなら、それだけでもプロに勝てるような希ガス。
どう考えても探索だけで勝つのは無理だろｗ

long a=0;
while(true)prina(log(a++))

とかやってみな。
表示されるのは、
2手しか分岐しないゲームをminmaxした時の、読んだ深さね。

なんなら1万台でやったバージョンとして
while(true){
a+=10000
prina(log(a))
}
もやってみれば？

>>233だけど、logの底は２にしてくれ。
あるいは分岐数eとか。
普通に間違えた。

>>232を考えてるのは
末端ノードの評価関数は、
現実には多少なりとも誤差が含まれているので、
どうせminmaxのヒューリスティックを考えるなら、
ちゃんとした仮定をいれて、問題を定式化しなおした方が
きれいなアルゴリズムができるんじゃないかと思った。

>>233
現状でも結構いい線いってるけど、プロに勝つためには
10手以上増えないと駄目なのか、3手ぐらいでもいいのか。
というのがわからん以上、どっちとも言えないのでは？

ところで、GPW招待講演時のPDFをみると
Bonanzaでは枝刈りの効果で1局面では2.23手を読むだけらしい
計算速度も数年で倍になることを考えると
数十年で探索深さが10増えることになるわけだ。
これならいけると、個人的には思うわけだが。

ところでprina はタイプミス？

>231
並列探索には鉱脈がたくさんありそうですが，
成果を上げるのに時間がかかりそうですし
皆さんあまり乗り気でないのかもしれません

>235
探索延長なしでやろうとすると終盤でも10手じゃ足りない気がします．
序中盤でプロが「自信がない」「味がいい」「含み」「指せそう」
等の理由で選ぶ指し手を超えるにはもう少し必要な気がします．

あとあまりに深さが増えてくると手の生成や局面の更新にかかる
コストもばかにならなくなってくる気がします．．．

ボナンザの静的評価関数のデータベースと探索技法について、ソフト開発者の方にお尋ねします。
問題となる現局面の特徴次元空間の配列と、近接度の高いヒルベルト曲線群上の各点を選び出し、
評価関数を自動生成するには、データベースがあらかじめ探索によってプロットされていなければならないように思います。
すなわちプロ棋士の棋譜を近似的に最善応手列とみなすことにより、その終端局面から十分狭い領域で評価値の変分が最小となる特徴に着目し、
直接的に求まるのは「応手による各評価要素の適正な交換レート」であるように思います。
評価要素の交換レートが求まると、ここから評価要素の値の係数が求まり、評価要素の値×係数の総和（線形和）を取ると、局面の評価値が求まります。
しかしこれは単なる評価値で、探索によって得られたものではなく、かなりの誤差を含んでいると思われます。
たとえば瞬間的に銀得でも、次の相手の手番で駒損を回復されるような場合があり、１手ごとに評価値はがくがくと上下することが考えられます。
そこでminmax法による探索を行い、評価値の変動が安定化する十分な深さまで探索する必要があると思います（水平線効果の除去）
ある深さまで探索しても安定化しない場合や最善手と次善手の差が僅かであるような場合には、探索延長が必要かと思われます。
安定化すると、その終端ノードの値を返すことにより、局面の評価値が確定すると思います。（この値をプロット）
次に探索の幅についてですが、これは手の信頼度に直結しており、近接度の一定領域内に存在する参考応手列のハミング距離、データ数、分散の大きさ、棋力などによって総合的に判断されているものと推測します。
上記の交換レートの最確値と手の信頼度の計算には、最小自乗法などの統計的手法が用いられているものと思います。
以上、その辺の書き込みだけ見て、あとは想像で書いているので、とんでもなく勘違いしているかもしれませんが、この理解で良いのでしょうか？

>237
数学畑でないものでわからない言葉がたくさんありすぎです・・・勉強不足ですねorz

＞評価値の変分が最小となる・・・
ちょっと疑問です．指し手によって変分が最大となるように最適化するんじゃなかったかと思います．

後半は探索時の話でしょうか？
minimaxと水平線効果の除去，安定な評価値と探索延長はそれぞれつながらないような気がします．

探索の幅は深さのことでしょうか？
深さなら反復深化をやっていると思うので与えられた時間しだいではないかと．

手の信頼度という言葉は初めて耳にします．
その辺の書き込みというのがどのへんにあるのか教えていただけますか？

あの、私が質問してるのですけど（笑）

＞＞評価値の変分が最小となる・・・
＞ちょっと疑問です．指し手によって変分が最大となるように最適化するんじゃなかったかと思います．

最善応手列の特徴→形勢の揺らぎが最小→変分が最小・・・という意味で書きました。


＞探索の幅は深さのことでしょうか？

枝刈りによって残す幅の意味です。ボナンザも枝刈りしていると聞きました。


＞手の信頼度という言葉は初めて耳にします．

近接度が低い、分散が大きい、データ不足、棋力が低いといったケースでは参考応手列の信頼度は低くなるかと思います。


＞その辺の書き込みというのがどのへんにあるのか教えていただけますか？

本スレと「おまいら最強の将棋プログラムしてみろよpart5」のスレです。dat落ちしてますが。

取り敢えず回答ありがとうございます。160の人が権威者のようなので、この方に訊いてみたいと思うのですが。

アルゴリズムより定跡いれたら？

>>235
>現状でも結構いい線いってるけど、プロに勝つためには
>10手以上増えないと駄目なのか、3手ぐらいでもいいのか。
>というのがわからん以上、どっちとも言えないのでは？
まあそうかも。

>計算速度も数年で倍になることを考えると
>数十年で探索深さが10増えることになるわけだ。
>これならいけると、個人的には思うわけだが。
近似的な枝刈りで良ければそうかもね。
でも、厳密解を考えると、倍なんてカスだよね。

>>231
>並列探索には鉱脈がたくさんありそうですが，
>成果を上げるのに時間がかかりそうですし
>皆さんあまり乗り気でないのかもしれません
確かにみんなやってないねぇ。
minmax探索の効果があるのかどうかもよくわからない改良をするくらいなら
ゲーム木の展開なんて簡単に並列化できるんだから、
そういうことに力を注いだ方がいい気もする。
ちなみに、東大が100台くらい使ってやってたけど、
あんま意味なかったぽいね。
やっぱりNP困難なので、計算力じゃ意味ないかも？
100台が1万台になったらまた違うのかもだけど。

>あとあまりに深さが増えてくると手の生成や局面の更新にかかる
>コストもばかにならなくなってくる気がします．．
そんなのどうでもいいよ。

ソフト開発者じゃないけど

>>237
PDFをベースにすると間違いは一個もない。

ただ、俺の意見だと
>たとえば瞬間的に銀得でも、次の相手の手番で駒損を回復されるような場合があり、１手ごとに評価値はがくがくと上下することが考えられます。
これは間違ってると思う。

>しかしこれは単なる評価値で、探索によって得られたものではなく、かなりの誤差を含んでいると思われます。
探索しても得られるのは単なる評価関数に基づくminmax探索（の近似）なので、
かなりの誤差を含んでいる。

>たとえば瞬間的に銀得でも、次の相手の手番で駒損を回復されるような場合があり、１手ごとに評価値はがくがくと上下することが考えられます。
1万次元の評価関数なんだから、そんなことは起こらないと思う。（勘）

ただ、評価値の安定度に基づいてなんかするなら、そこは確かにポジティブな効果が期待できる。
でも、それと評価関数の学習はやはり別物だと思う。
つまり、棋譜からの学習以外のものを、学習に突っ込んでしまうと
純粋な棋譜からの情報抽出ができない。
言い換えるならば、
安定度の評価は情報抽出後にやっても遅くはないし、同じ結果を与える。

そういうわけで
minmax探索後の結果を与える評価関数（のしかも近似）を補正するというのは意味がない
と思いますよ。

>次に探索の幅についてですが、これは手の信頼度に直結しており、
>近接度の一定領域内に存在する参考応手列のハミング距離、
>データ数、分散の大きさ、
>棋力などによって総合的に判断されているものと推測します。

PDFに出てくる関数Tのことかな？
さすがにデータ数や棋力や分散などを考えるのはめんどくさいので
やっていない気がする。
シグモイドを勘でチューニングしたんじゃないかな。
俺は線形でいいと思うんだけどね（正則化項がついてるからね）。

>>242
バカになんないんだったらどうでもよくないだろw

>>245
馬鹿になんないけど、そこを考えてもどうしようもないだろ？

>236
というより、マルチコア化が最近になって急速に進んできたからいろんな意味で準備不足なのかも。
これもインテルの熱湯バース党アーキテクチャが大コケしたおかげだけど。

メニーコア化して、1ソケットあたり10コア以上が叩き込まれるようになったらwktk

>>241
>でも、厳密解を考えると、倍なんてカスだよね。
誰も厳密解をどうこうしようとはしてないでしょ。

>>243
>>たとえば瞬間的に銀得でも、次の相手の手番で駒損を回復されるような場合があり、１手ごとに評価値はがくがくと上下することが考えられます。
>1万次元の評価関数なんだから、そんなことは起こらないと思う。（勘）
いや、評価値の上下は起こるよ。
普通は静止探索（駒を取る手だけを探索とか）でもってこれを解決している。
つーかボナンザ限定の話なの？ 1万次元て。

>>248
>>1万次元の評価関数なんだから、そんなことは起こらないと思う。（勘）
>いや、評価値の上下は起こるよ。
>普通は静止探索（駒を取る手だけを探索とか）でもってこれを解決している。

それを聞いて安心しました。ボナンザという連想記憶モデルの他分野への応用が楽しみですね。

>誰も厳密解をどうこうしようとはしてないでしょ。
だったら、並列化より近似方法を考えた方が生産的かも。
もちろん、並列化によって性能はあがるけど、
k^n台にした時効果はnしかない。

>いや、評価値の上下は起こるよ。
>普通は静止探索（駒を取る手だけを探索とか）でもってこれを解決している。
俺が書いたことをほとんど読まないで書いてるでしょ。
学習データの近傍で上下は起こらないってことを言ってるんだが。

そりゃ、学習データがないところで揺れることはあるけど、
それと学習は関係ない。

静止探索というか、評価関数の不確からしさを見積もって、
それに応じて読みの深さを増やすことは、
評価関数によらず効果があるよ。
逆にそういうものを学習データの近傍でつぶしてしまったら、
分散の情報などを取りこぼすことにつながる。

そもそも探索した場合まで考えてしまうと、
近似的にしか学習できないので、かなりの改悪だと思う。

>>245
バカになんないんだったらそういう方法はとらないって選択肢が出てこないか？

ずーっと前の話で申し訳ないけど、いいかな？

>>203
>「全幅探索」はαβ法を用いないピュアなminimaxアルゴリズムだけを指すんだ！と主張される先生もいらっしゃいますが
>minimax評価値をαβ法で求める方法を含めて「全幅」と呼ぶのが普通かとおもいます．

これ、どうも気にかかるんだよね

実際の現場でそういう表現を用いるってのはよく判る。実際、αβを使えば同じ（ような）結果minmaxより早く得られるわけだし

ただ、学術的というかw　入門書的というか、そういう「minmaxやαβってなんなのかお勉強しましょう」というレベルの話であれば
そこはやっぱりminmaxとαβは分けて考えるべきだと思う
勝ち負けをどう求めるかというminmaxという手法があり、更にそれを効率よく行うαβがあり、そもそも前向きに枝狩しよう、という考え方もあり、っていう風に

なので、>>203の物言いはなんかすごく引っかかる。言い方悪いけど、知らない人を馬鹿にしてるみたいで（203の人ごめん）


・・・チラ裏ですまんw

>>252
オマエがバカなだけだろ ｗ
野球の試合でもリードしているチームは９回裏の攻撃しないんだよ

>>252
お前が出てくるとレベルが著しく下がるから引っ込んでろと正直言いたい
言わないけど

>254
言ってるじゃないか（事実上）ｗ。
まあ気持ちは分かるが、本人も「チラシの裏」だと言ってる事だし。

正直ｽﾏﾝｶｯﾀ

>>252
まず、将棋のようなゲームにはゲーム木というのが存在する。
これを全探索すれば必勝（利得最大）手筋が発見できる（存在すれば）。
これをminmax探索という。

>>253
が書いているとおり、もはや探索する意味がないような筋が、
最適値の上限と下限から決定できる。
従って全てを探索する必要はなくなり、αβが使える。

ただ、この枠組みと現実が大きく乖離する点がある。
それは、どんな高速化をしたところで、
end gameまで読み切ることはできないとうこと。

この時点で、minmax探索というのは基本的には崩れさる。
この打開策として、とりあえずの評価関数、というものをいれる方法が行われている。
言い換えれば、途中でゲーム木の展開を諦めて、
「minmax探索の推定値」を挿入している、と言える。

この推定値がかなり間違っているのであれば、どんなに深く読んでも無意味なのだ。
現実的なゲーム木探索では、
「ゲームが進めば進むほど、推定値の精度があがる」
という仮定をいれている。
もしこの仮定が誤っていれば、どんなに探索を高速化したところで無意味であるが、
実験的、経験的に確かめられている。

>252
「同じ（ような）結果」じゃなくて、完全に同じ結果が保証されてるんだよ。
変な小細工しなければ。だから、練習用に純粋なminmaxで組みましたって
わざわざ言わない限り、αβだというのが暗黙の了解だろ？

>257
そういう事を言ってるんじゃないと思う。252はもっと瑣末な枝葉レベルのくだらんことに拘ってるだけ。
ああ、枝葉といってもツリーの探索の話ではなくてだな……

minimaxの改良で「手の広さ」って
評価の対象にならないのだろうか

一手一手の問題もそうじゃないか？

つまりいまの評価関数って局面局面の駒の位置関係だけだろ
もっと手の流れの点を重視すれば読みを省けると思うんだよ

打った駒が立ち往生とか強要されて後手引くとか
３９や３８に受けに打たされた金銀を弱い駒と順次交換されるとかは
なんとなくよくない流れだろ

そこらへんあまり読みをいれずにね
前の指した手との繋がりの観点から評価関数で学習しておくと…
もっと強くなるだろうな

駒に相性を設定してそれと盤上の位置で点数つけちゃうとか。
同じ位置関係でもだいぶ意味が違ってくる。
とんでもない方向に判断ミスする可能性もあるが。
そんなに処理に時間食うわけでもないから面白いと思うんだけどな。
人間がやってるのもせいぜいそんな感じだし。
あと駒じゃなくてマスの方に点数振るのも面白い。

>>260,261
強くなるだとか面白いと思うなら自分でコード書いてみりゃいいじゃん。
そんなコードぐらいすぐに書けるんだし。

そしたら自分が馬鹿なこと言ってるなってすぐにわかりそうなもんだけど。

>>258
うーん、だから、

>だから、練習用に純粋なminmaxで組みましたって
>わざわざ言わない限り、αβだというのが暗黙の了解だろ？
　　　　　　　　　　　　　　　　　　　　　　　　　　~~~~~~~~~~~~~~~~~
これが>>252で言っている「実際の現場でそういう表現を用いる」話で、それを否定してるわけじゃないのよ
ただ、本でおべんきょしましょうね、というレベルの話であったら、それを分けて話しても別に問題ないし
むしろそこをきちんと分けた方が（ちゃんと枝狩してるんだよというのが判るという点でも）いいと思う

それを、「こんなもんそう表現するに決まってる。分けるなんて論外」とまで言っちゃうのはどーよ？
……という部分に引っかかっていたわけよ
瑣末な枝葉レベルのくだらんことに見えるかもしんないけど、入門者レベルの人がそういうの見たらいい気持ちしないよ？



……なにやってんだろもう千葉行かなきゃいけないのにw

最善解を求める全幅探索だよ
全幅探索を単純なアルゴリズムを加えて行うのがminimax
も少しだけアルゴリズムを加えて全幅探索を行うのがαβ

昔の人がminimaxとかαβとか名前を付けただけで、当り前の全幅探索

昔のソフトって全幅探索だったんでしょ？

ボナンザはそれを可能にする正確な評価関数を作り上げたのが
もっとも画期的なことなんだと思う。

>263
だから、もまえが事情を承知の上でくだらんことに拘っているのは解っている。
それゆえ、漏れは「もまえが事情を承知の上でくだらんことに拘っている」と言っている。

相互理解はもう十分に出来ていると思うが？

>>263
実際の現場レベルでも、本でおべんきょレベルでも
minmaxもαβも全幅探索で何の問題もない。
αβは全幅探索じゃないとかの表現をいちいち区別してたら
初心者レベルでもかえって混乱するだけ。

>>252 は、全幅探索として minimax 迄なら許せるが αβ 迄は許せないというトラウマの持ち主。
いったい、何が彼をそうさせたのだろうか？
いかなる幼児体験があったのであろうか？

>>239
手の信頼度つまり点の偏差というのは結構大事なポイントだろうな
minimax では平均点を最大化する解しか捜さないが…

・それぞれの評価は低くて全く違った(攻めと受けとか)
いくつかの手をさせるような手の広い局面であれば
後でその局面になって読みを入れたときには実は平均以上の手が
見つかるかもしれない

・逆に評価が高くても手が狭ければ, 読みを入れたら点ががた落ち
したときに回復のしようがない。実際に渡辺戦の３９竜の数手後
いきなり +400 → -400 という変動をしたわけだけれど…

この前者のような手ってのはいわゆる手堅い手だよな
こういうのがさせるようになるとソフトも強くなるな

難解な局面で、ほとんど全ての手が優勢（劣勢）になるけど、ただ一つの正解手を指せば大逆転って時に、
えいやと勝負手を放てるようになったらwktk

勝負手っていうのは「ただひとつの正解手」じゃなくて難解な局面において
相手に正しく応手されると却って自分が悪くなるが、相手はごく狭い範囲の
正解を多分見つけられないだろうと見込して放つ手の事だと思うが。

つまり「勝負手」というのは通常「正解手」じゃないんだけど、
君はどういう意味で言ってるの？

ごめん、君がなぜ勝負手を正解手と勘違いしてると思うのか解らん

「ただ一つの正解手を指せば大逆転」って所だね。
勝負手を放つような局面では正解だけれども、どれもジリ貧って手はいっぱい
あるだろ？それに対して勝負手ってのはそんなに選択肢が多くないよな、普通。

元々、優勢な方が「ただ一つの正解手」を指すと言う話なら「大逆転」てのが
良く分からん。

相手がただ一つの正解手を指せなければ大逆転って時にえいやとその勝負手を放てるようになったら

これなら意味は分かる。

>>267
俺は
minmax探索の全探索
minmax探索の厳密解法
minmax探索の近似解法
と分けるのが好き、というか工学ならこう分けるのが普通のような。

まあ、どうでもいいか。

あ、そういう意味か。なるほどね、了解！

いや、俺は270じゃないから。
俺はこうなら分かるってのを書いただけで。

いや、まあ俺もそういう意図での発言なら納得できると思って。
別人なのは分かってるけど。

>>275
全幅探索と言われたときには全探索のことではなく
ある局面で指せる全可能手を対象にした最善手探索と定義するべき。
全幅探索でも探索しない手があることに触れたいなら、全幅探索でないとは言わずに
αβ探索におけるαカット、βカット、negamaxでのβカットなどで説明するべき
αβが全幅探索でないは、たまにそういうことを言う変わり者がいるという
豆知識程度以外では触れるべきではない。
用語を統一しないと、あれ？αβって全幅探索じゃないんですよね？とか言い出す
馬鹿が現れるので困る。

これが結論。

----
全幅探索 ≠ minimax

全幅探索 ⊃ minmax
全幅探索 ⊃ α-β

>>280
全幅探索 ⊃ minimax ⊃ α-β
　
全幅探索→ゲーム木の探索だけじゃない一般の用語、枝狩り探索の反語
minimax→ゲーム木の探索のこと
α-β→アルゴリズム

いずれにしろ用語なんて記号にすぎなくて
そんなの統一しなくてもいくらでも理解とか議論はできるけどな

低レベルの叩きあい

それを口に出した時点で同レベ（ｒｙ

>>281-282
その説明はウソだろ…
あと用語の統一は基本中の基本だろう。考え方がむちゃくちゃ。

>>284
数学っていうのは記号じゃなくて概念を扱っているんであって
解釈が曖昧になりそうな記号や用語は定義を与えて使えばいいだけ
用語の使いかたなんて趣味の問題でまったく本質と関係ないよ

衝撃的な発言だ・・・

コミュニケーションっていうのは記号じゃなくて概念を扱っているんであって
解釈が曖昧になりそうな記号や用語は定義を与えて使えばいいんだけど
用語の使いかたなんて趣味の問題でまったく本質と関係ないよって思ってると
まったく話が通じないんだよね。
さて、自分の井戸に戻ろう。

>全幅探索と言われたときには全探索のことではなく
>ある局面で指せる全可能手を対象にした最善手探索と定義するべき。
いや、俺はそもそも前幅探索という言葉が好きじゃないから
使わない方がいいと思うけどね。
minmax探索の厳密解法
minmax探索の近似解放
の２つがあれば、分野外の人が迷うことは何もない。
まあ、たかが用語の定義の問題だけど。

人間同士がコミュニケーションする際に記号でやり取りせずにダイレクトに
概念を伝え合うなんて事はできないだろう？どこまで行ったって記号の
やり取りしかできない（記号の意味を説明する方法もまた記号）のだから
用語の定義がお互いにずれているという状況は本質的な困難を生む。
（言葉も文字も数式も数字もグラフも全ては記号）

いわゆる記号論着地問題という奴だな。

それを真剣に考えると人間同士がなぜ曲りなりにもコミュニケーション
できている（ように見える）のか、むしろそっちの方が不思議な話
なんだよな。

ゴメン、「記号"論"着地問題」じゃなくて「記号着地問題」が正しい表現だった。

>>288
だから、全幅探索と言われたときには>>279の定義でいいだろう。
厳密解法か近似解法かは、minimaxとαβの原理を説明するときに使えばいい。
オレは将棋プログラミングで、厳密解法と近似解法の区別が必要なケースはほとんどないと思うが。

あ、>>291は勘違いしていた、すまん。
しかし全幅探索と言われたときは、αβも含めるで統一して問題ないと思う。

>>288 「好きじゃない」って要は自分でも趣味の問題だって認めてるだろ

まあ解釈がわかれる用語は使わない方がいいっていうのはその通り

全幅探索がどうこう言ってる奴は相手にするなよ
しかもそいつはそれ以上の話は一切できないんだから

相手にするなと言うなら、オレはこれからもαβを全幅探索と呼び続ける。
だいたい数々の論文でもそう書かれていて、既に定着している用語を
>>252のような考えで変更するのは問題がある。
もちろん>>252の考えで、厳密解法、近似解法を使うのは構わない。
しかしそれはほとんど初心者に説明するレベルでしか使われないのであって
例えば全幅探索でこれだけの深さを読みましたと言うところを、厳密解法で
とか言い直していたらかえって伝わらない。

>>296
いや逆逆
>>252のこと
それにαβは近似でもなんでもないし

>294
解釈が分かれる用語は「私はこれから、この場でこういう意味で使う」と
前置きをしてから使えば（あるいは後で注釈を付ける）何の問題も無いと
思うんだが。

そういう意味で用語の問題は本質的でないと言うのはその通りだと思うが
現実にはどの用語が人により、あるいは分野により解釈が分かれるのか
事前にはなかなか分からない上に皆、それぞれ（自分の専門分野では）
「普通の解釈はこうだ」と言うこだわりがあってなかなか捨てられない
から話が面倒くさくなる。

まあともかく用語の定義の話じゃなく内容を議論して欲しいとは思うよ。
だが、多分必要不可欠なコストなんだろう（用語の定義で議論が起こるのは）。

ええっと、>>279の補足になると思うが、指し手決定には、
(1)検索する木を作る。
(2)作った木を辿る。
の作業が必要。
で、「全幅検索」とは、(1)を合法手すべてに対して行うこと。
(2)ですべての枝葉を辿ることではない。
よって、ここで、(2)の手法であるminimaxとかαβとかの話は、ナンセンス。
なんか、ここら辺がごっちゃになっていると思われ。

>>296の
>オレはこれからもαβを全幅探索と呼び続ける。
は、(1)をすべての合法手に対し行っていなければ、間違い、というか、関係ない話。

で、どう？

>>299
> 「全幅検索」とは、(1)を合法手すべてに対して行うこと。

これ一般的な見解？

>これ一般的な見解？
と、私は思っている。

という答えでいい？
どこか引っかかる？
要は「読み抜けがない」ってことでしょ？
「すべて」でなければ、枝狩りしたことになる。
けど、「自明で安全な枝狩り」は、「全幅」に含めるかもしれないし。
「合法手すべて」の定義は？
という質問？

ところで
１秒何万手って読むらしいけれども、
同じCPU・違うプログラムでこの何万手に差は当然出るの？
出るとしたら何の差？
手数が少なくてもリカバー可能？

>>301
木を作ることを指して「探索」というのが理解できなかった。
合法手を生成するだけなら探索してねーじゃんと思った。それで一般的？と聞いてみた。

>>302
設計やコードの組み方次第で無茶苦茶に差が出る。自分の経験上。
将棋のプログラムは組んだことないけど。

リカバー可能かどうかは将棋の将棋のプログラムを組んでいる人よろしく。

> 「全幅検索」とは、(1)を合法手すべてに対して行うこと。

そうそう、これを見ていて気になったのがもう一つあった。

「全幅検索」は全ての合法手の木を作るのが必須なんだとすると、メモリをバカ食いするなぁと思ったよ。
「αβでカットするのって局面の評価だけなのか。
それじゃCPUは節約できてもメモリは節約できんな。ヘンなの」と思った。

オレあんまり分かってないんで、的外れかも。すみません。

>>300
それが一般的だが、そうじゃない定義をする人もたまにいる。
そんなの無視すりゃいい話なんだが、>>252がそんな瑣末な問題に
こだわってしまったのがそもそもの間違い。

>>302
手の生成速度、探索速度、評価関数の速度などで大きく差が出る。
1秒間で1万手読めるプログラムと、千手しか読めないプラグラムが
あるとしても、千手以内に最善手が発見できれば1万手読めるプログラム
と同等の強さになれるので、速いから必ずしも強いとは限らない。

>>304
普通のプログラムでは、探索した木は探索が終われば破棄され
次の木を探索するので、たいしたメモリは喰わない。

>>303
>木を作ることを指して「探索」というのが理解できなかった。
そういうことか。
実際は、
(3)局面に点数をつける。
というのがあって、(1)(2)(3)は、実装者にもよるだろうが、多分、同じタイミングで
実行されることになるので、これらにはっきりした境界をつけるのが難しい。
私も「全幅検索」と書くか、単に「全幅」と書くか、悩んだよ。


>「全幅検索」は全ての合法手の木を作るのが必須なんだとすると、メモリをバカ食いするなぁと思ったよ。
実際は、「作っておく」わけではなく、「作りながら」になることが多いので、(2)を、深さ優先でやるか
幅優先でやるかによっても違うけど、そんなにバカ食いにはならないと思う。
で、深さ優先と幅優先とαβのいい所取りが、反復深化法になるのかな。

>>302
>出るとしたら何の差？
>手数が少なくてもリカバー可能？
実装テクニックもあるけど、(1)(2)(3)のどこで頑張るか、でしょう。
(3)で頑張れば、(2)が犠牲になる。
実際問題として、コンピュータはプロに勝てていないし、プロが１秒何万手も
読んでるとは思えないし、そう考えれば、手数の問題ではないと思う。

私も、手数の少ない方向の方針で、来年は、大会出場しようかなと思っている。
とかいう人が時期的に増えそう。

将棋の総局面数は10＾200　ぐらいのようなので、
仮に一秒間に1億局面読めるPCを一年間フル稼働しても
1億 * 60 * 60 * 24 * 365 = 3.1536 × 10^15　局面しか読めない。

よってコンピューターが全幅検索のみで将棋を解くことは不可能。
かりに10億局面/secよめても10＾16になるのみ・・・

で、いいよね。コンピューター将棋素人ですが。

いや間違ってる
手段によらず将棋を解くことは不可能

つ二人零和有限確定完全情報ゲーム

速度以前にそれだけの局面の情報を格納しておける記憶媒体がないわけで

メモリはそんないらないだろ
速さが足りてるなら
読みきろうとして葉に達するまで、1億手もあれば十分なんじゃないか？

チェスのディープブルーが１億手/sec　らしいので、全然足りないのだと思う。
（人間に勝つという目的では足りているといえるかもしれないが）

１億手/sec　になれば、今より強くなるとは思うが、何手先まで深く読めるようになるのだろう。。

あー「宇宙に存在する全原子の数より多い局面」なんで。
現在の技術の延長では何をどうやっても読みきり不可能。

量子コンピュータみたいのの更に凄い奴が考案されて、
二人零和有限確定完全情報ゲームならなんでも一瞬で
解けるとかそういうＳＦみたいな展開にならないとあかんだろう

と、なるとやはりマシーンパワーをどうこうよりも、
評価関数・アルゴリズムをいじるほうに重さがあるということで、
それはプログラマーにとっては面白いのかな？

>>311の1億手ってのは1秒に何手読めるかではなく
初手から1億手以内にゲームが終わるだろうって意味

深さ優先で効率を考慮しないで探索するなら
必要な記憶域は読み進める手の深さの分だけ

だからいかに分岐が多くても速さの問題を克服できるなら
メモリは問題にならないだろうって話

全幅探索の性能を上げるためには、底を如何にして小さくするかってところがポイントになると
思っているんだが（合ってる？）、理論的にはどこまで小さく出来る可能性があるのかな？

ホキさんのスライドによると、
　Minimax法＋beta cut＋null move pruning や hasu cut＋Futility pruning = 1/4 * (2.23)^n
とある。

これ、もっと頑張ると2^nオーダーを切ることも可能？
1.5^nオーダーぐらいで探索できるようになったら、かなり面白いと面白いと思っているんだけれども。
ぜんぜん分かっていなくてすみません。

面白いが二つあるな…誤記失礼。

>316

>これ、もっと頑張ると2^nオーダーを切ることも可能？

上位ソフトは実質的に合法手2ぐらいの探索になってるんじゃないかと思います．
風のうわさで激指でも換算してみるとそのぐらいだと聞いたので．

全幅の話をぶり返します．すみません．

葉局面で評価する直前に静止探索をやる方がほとんどだと思いますが（ボナンザもそうだったと思いますが）静止探索をやると全幅探索とは言えなくなると思うのです．
そのへんはどうなんでしょう．

ＹＳＳのエキシビション見て思った
アルゴリズムより定跡いれるほうが先だと・・・

>>315
読み進める手の深さってのが、最後まで読み切るなら天文学的数になるんじゃない
1局面に平均40手あったとすると、40^手数
1億なんてたった5手で越えちゃう

>316
底が2.23から1.5に減ると探索量は約2/3桁に減るな。
15手先まで読むとして2.23^15=16万。1.5^n=16万の時、nは29手先になる見込みか。
わりと激指の二十数手先まで読めるってのに符合するかも。

>>321
そうじゃなくて直線的に読み進めて終局までにかかる手数のこと

誰かプログラムが分かって説明がうまい人お願い

>>322
> 底が2.23から1.5に減ると探索量は約2/3桁に減るな。

将棋の棋力の低い奴はよく勘違いしてるんだけど、
底は読みが深くなるとどんどん小さな値になるんだよ。

「15手先で悪くなるから、その手を選択することはあり得ない」だとか。

俺の予想では30手先まで読むなら、底は2を切るぐらいにはなると思うよ。

全幅探索でも実際にはすべての手は読んでいない。
すべての手は読んでいないのに、すべての手を読むアルゴリズムと
同等の解が得られる点がαβ探索のマジック。
探索ゲーム木全体がいくら巨大だろうと、実際にメモリを喰うのは
現在探索中の枝だけ。
将棋プログラムでメモリを喰うのは、探索した局面の最善手や評価値
などを記憶しておく、ハッシュ表とか局面表とか呼ばれる部分。
ハッシュ表は事前に大きさを決めておくので、ゲーム木が巨大だから
メモリを喰うという訳でもない。

>>319
意味がいまいちわからないが、普通全幅探索といったら静止探索の
アルゴリズムとは無関係。
葉局面で静止探索するのは、実際に駒の取り合いをしてみて、評価関数の
精度を上げるため。
探索の途中で静止探索をやるのは、静止探索の結果で良さそうな順に
手を並び替えるため。
最善手が先に見つかれば、残りの手は読まない。

木の最大深さって言ったほうが分かりやすいかな

>>310で読み切るには局面の情報を格納しておく記憶媒体が必要だと書かれたけど
それは必要ないってことを書いたわけ

でも実際は読み切れないわけだけど

>>324
> 俺の予想では30手先まで読むなら、底は2を切るぐらいにはなると思うよ。

それをどういう枝刈り手法で実現するの？

>324
いや、いいたいことは解るつもりだ。

局面の数が多くなると、より駄目な局面がガンガン増える（枝狩りの効率があがる）

でおけだろ？結局同じ事を言ってる希ガスなのだが

>315
毎回、一手指す毎に深さ優先探索して最善手を求めるわけか。
で、当然ゲーム木の末端（葉）の評価値は
”勝ち””負け””引き分け（千日手）”の三通りのみで
それに対してMinMax法（αβカット）を適用すると。

そうすれば確かに途中で覚えておくべき局面数は多分1000局面も
無いだろうが、（計算量的に）スゲー贅沢な方法だなｗ。

一手指すごとに候補手が平均9手あるとして（合法手80手の平方根）
一局に掛かる手数が平均120手なら9^120。計算するの面倒くさいから
10^120探索が必要と仮定するなら最後まで読み切りながら指すためには
これを一手指す毎に毎回繰り返すと。スゲーｗ！

なるほど
つまり相手が最善手以外の手を指したら読み直しってことでOK？
>>307が完全解明の話だったから、そういうの含めて解く話だと想定してたよ。

よく意味が分からないけど、普通に将棋で探索と言ったら深さ優先探索なんだけど
幅優先探索は読み進めるのにメモリが必要だから
その対比であえて深さ優先って書いただけで

minmaxとかアルファベータももちろん深さ優先探索

>330
以前に探索した局面（ゲーム木）とその評価値を覚えて置かないで済む
ためにはそうするしかないよな。

で、覚えておこうとするにはこの宇宙にあるどんな記憶装置を使っても
容量が足りないと言う制約があると。

まあ、実際には読み直しを減らす工夫はいろいろ有りそうだが、
（今のところ）どうやってもまず計算速度が足らないｗ。

>331
そうだね。深さ優先探索するのと以前に探索した結果を一々覚えていない
（基本的に毎回読み直す、ハッシュ表に格納しておくとかの特別の工夫は
別にして）と言う方式は現在の将棋ソフトのやり方そのままだよね。

ゲーム木の末端まで読むかどうかと言う規模（徹底度）の違いだけだ。

>325

「普通全幅探索といったら静止探索とは無関係」というのは認識しているんですけども，
なぜ無関係と言われるのかが今ひとつ腑に落ちなくて・・・

そもそも評価関数を信頼できないから探索をやるわけで，
それはroot局面だろうが葉局面だろうが変わらないと思うのですけれど，
駒の取り合い探索は評価関数の一部だから全幅探索か選択的探索かには
関係ないと言われるのはごまかされているような気がするのです．

オーダリングのときに静止探索をやるのは特に気にしてません．
（ボナンザはやってましたっけ？）

>334
「終盤に近いほど評価関数の精度が良い」のであれば、探索の深さは性能に直結するね。
この仮定が受け入れられるかどうかという問題じゃないか

終盤になったら、一手指すごとに、全幅探索とは別に、他のパソコンで
詰め将棋ルーチンと「詰めろ探索専用」ルーチンを使えば
少なくとも今よりは強くなるんじゃないでしょうか？

うっかり次スレ立てずに1000踏んでしまった……こっちで告知

▲コンピュータ将棋スレッド41▽
http://game12.2ch.net/test/read.cgi/bgame/1178460754/l50

>>334
静止探索の性質について。

例えば、飛車の取り合いを行っている途中、
葉局面が相手の飛車を取り自分の飛車が当たりになっている（次に取られてしまう）場合、
その局面を単純に評価しようとすると、こっちは飛車の丸得だと評価してしまいます。
このように、葉局面は重大な取り合いの途中であった場合、正しい局面判定が出来ません。

そこで、評価を正しく行うための補助として、静止探索(取り合い探索)を行うことで
評価する局面を安定させることができます。
ここでポイントなのは、静止探索は「探索」と言っておきながら、その役割は
「局面を安定させる」というために行われる点です。

ここまでおっけ？？

>335
言葉が足りなかったかもしれません．
rootでみた評価関数の値と10手先読みしたときの評価値ならば
後者のほうが信頼できそうだと言いたかったのです

>338
とりあえずOKです

>337　Thanks！
なんか、いきなり宣伝に使われてるようだがｗ。

正直>>339が何を言いたいのか分からなくなってきた
結局何が聞きたかったの？？

>341
静止探索を使うのに全幅っていうのはおかしくないですか？
と．

>342
駒を取る手（or 取られる手）のみ評価するから"全幅"とは言えないんじゃ
ないかと言う事ね。でも「局面の評価値を安定させる」ためにのみ行われる
本当の探索ではない「探索」だと言う事には納得したんでしょ？

>343
本当の探索と局面を安定させるための探索の違いはプログラマが区別しているだけのものだと思うのです．

全幅探索+静止探索の組み合わせは，
一定の深さまで全幅+そこから選択的に探索（適宜探索延長）
と同じ挙動になるのではないかと．

もし一定の深さ=1だとしたらそんなプログラムは全幅とは呼べませんよね？

>344
でも一定深さまで読んだゲーム木の末端（葉）を正確に評価するために
静止探索を入れたからと言って全くの"選択的探索”とも言えない。
途中局面を評価し、前向き枝狩りしてそこからさらに狭く深く
読もうとしてるわけじゃないので。

>一定の深さまで全幅+そこから選択的に探索（適宜探索延長）
>と同じ挙動になるのではないかと．

確かにその通りだと思うが、なら後はそれをどう呼ぶかと言う問題だよね。
結局はプログラマの意思（実は何をやりたかったのか）を名前に付けるのが
ふさわしいと言う事になるのでは？

>>344
確かに厳密にいったらそうですね
「全幅探索型」の探索であって、
「完全全幅探索」ではありません
そういえば王手延長もしてるはずだし

まぁでも、全幅探索か選択的探索かといわれると、
間違いなく「全幅探索」だと思います

>>344
×探索：全幅探索＋静止探索 / 評価：評価関数
○探索：全幅探索 / 評価：静止探索＋評価関数

駒の取り合いなどが起こりうる局面の場合、評価値の変動が大きい。
その変動を評価関数内で取り除くルーチンを作って処理してもいいが、
取る手や成る手など変動が大きいとわかっている手に絞って
探索（局面展開）する形をとることで、同等の処理に置き換えている。
つまり、既探索ルーチンが利用できるということ。
また、評価値の変動が大きそうな手が他にも考えられる場合、
専用ルーチンを作らなくても、そういった指し手を
静止探索の候補に追加するだけでいい。

＞結局はプログラマの意思（実は何をやりたかったのか）を名前に付けるのが
＞ふさわしいと言う事になるのでは？

妙に納得しました．
確かにそうかもしれません．

Bonanza製作者の保木さんが参考にしたチェスの論文のタイトルと雑誌名をお教え願います。

私の考えた方法でボナンザが強くなるか質問です。

ボナンザは大量の棋譜を解析して評価関数の
精度を上げていると思うのですが、
この棋譜の量及び質が上がれば評価関数も上がるとすると、
PFLOPS級のスーパーコンピューター上で
質の高いそして大量の棋譜を作れば
良いのではないかと思うのですがこれは間違い？

どうやって質の高い棋譜をつくるの？

>>350
良い鶏を作るためには良い卵が必要だぞ

終盤になったら、一手指すごとに、全幅探索とは別に、他のパソコンで
詰め将棋ルーチンと「詰めろ探索専用」ルーチンを使えば
少なくとも今よりは強くなるんじゃないでしょうか？

PFLOPS級のスーパーコンピューターでボナンザを起動すると、
通常のPC上で起動した場合よりも深く手を検索(少なくとも5手以上深く)でき、
強くなるので、PFLOPS級のスーパーコンピューター下で
ボナンザ同士で対戦すれば質の高い棋譜ができると思うのですが･･･。

>>353
なるほど、ハイブリッドにするわけですね？
そうすれば殆どの人はボナンザに勝てなくなるかも
しれませんね。

人類が勝てなくなるには必勝法が解析可能になるまで待たなければ
なりませんが･･･。2040年頃のトップクラスのスーパーコンピューター
ならば必勝法解析に一年もかからないかもしれません。

>>354
エキジビションの加藤-ＹＳＳご覧になりましたか？

例えば、後手が７五で歩交換した後の、▲７六歩　なんて手は
プロ棋士なら絶対に指さない手ですが、全幅探索で５手程度深く
読めるようになったからといって、これが疑問手だという事が
果たして分るようになると思いますか？

>>356
すみません…私は将棋の事は殆ど分からないレベルですが、
『５手程度深く読んでもプロには勝てない』と言う事は分かりました。
しかし、『５手程度深く 読めるようになったからといって』
ともおっしゃっておられるので、CPUを10万台以上程度搭載している、
PFLOPS級のスーパーコンピューターならば20〜30手深く読み、
力尽くで質の高い棋譜を量産可能かもしれません…。

汎用京速計算機を使えば日本国内で可能かもしれません。

PFLOPS級のスーパーコンピュータ上で将棋ソフトを走らせても速くはなりません。
何故なのかを理解するにはスーパーコンピュータが一体どんな物で
普通のPCとどこが違うのか知る必要がありますが。

また必勝法を解析で知るのは今日の原理を使用したコンピュータでは事実上不可能です。

>357
終盤の詰むや詰まざるやといった局面、中盤で駒を激しく取り合う戦もたけなわな状況、
では数手の差で勝ちが見えることもある。だからこそ、今のコンピュータ将棋は終盤が
強くなってきた。

コンピュータは序盤が徹底的に弱いんだ。素人には優劣の判断がつかないような微妙な局面
で数十手先を見据えた一手をどう処理するかさっぱり解らない。

>>358
PFLOPS級のスーパーコンピューターであっても
一つのCPUに一つの棋譜を数ヶ月かけて考えさせれば
CPUの数の分だけ質の高い棋譜が大量に数ヶ月間で
生産できると思っていたのですが、
そうでは無いのですか？

>>359
その序盤の強さは定石の質と量で
決まると思いますが、
人が定石をつくるように、
その過程を機械上で再現し、
機械的に定石を量産する事は不可能でしょうか？

質問ばかりですみません。

追記

>>359
大局観を機械に理解させるのが難しいように、
優劣の判断がつかないような微妙な局面
で数十手先を見据えた一手は機械には難しいかもしれません。
それでも、プロの思考方法を科学的に解析し、
大局観の定義を浮き彫りにして行く作業は必要だと思います。
膨大な費用と大人数のプロ棋士の全面的な協力が必要だと思います。

>360
自己学習、自己複製的なアルゴリズムは、アイディアとしてはそんなに珍しいものではないですが、
将棋のような複雑なゲームで実現させようというのは、現在のところ思考実験の域を出ないように思います。
まして、定跡（将棋の場合はこちらの字を使ったほうが違和感がありません）を創造するというのは
とんでもなく高いハードルです。
一度、定跡データベースを外して将棋ソフトを走らせてみてください。滅茶苦茶しますよ（笑）
序盤に関しては、将棋だろうとチェスだろうと、人間の過去の研究と経験則に
全面的に依存しているのが現実です。今の時代に現実世界に存在する最高のコンピュータ「程度」の
能力では、定跡の創造などというのは夢物語ではないでしょうか。

早い話、コンピュータだけで作る棋譜の質など（ソフト開発に利用するには）たかが知れていますし、
現実に用意できる量も、将棋の複雑さに比べたらたいしたことは無いということです。

>361
膨大な費用と大人数のプロ棋士の協力、勿論それがあるに越したことは無いのですが（苦笑
でも、現在のソフト開発者は、それ「なし」にここまで将棋ソフトを強くしましたし、
将来に関してもある程度自信を持っているようにも見受けられます。

現時点ではコンピューターvs人間　というよりかは
プログラマーvs棋士　の知恵比べ。って感じかな。
だからこそアルゴリズムに重要性があり、おもしろい。
単純にコンピューターの総当り思考で人間に勝つのは、ほぼ不可能。
これは、将棋の総局面数が指数関数的に増えるのに対し、いくらマシンパワーが向上しても
比例関数的な伸びしかない。。から。でok？

プロ棋士棋譜使って評価関数鍛えてるのに
自分の評価関数で自分を鍛えるのは不毛ではないか

５手余分に読めるコンピュータ使えるのなら、それで対戦すれば良いではないか？

あと１０年でプロに追いつく？
笑わせるぜ！

>362
たぶん、「プログラミングの能力を必要としない」評価関数のチューニングが可能になると随分変わってくると思う。
局面の良し悪しを判定するだけで、あとは細かい調整を自動でやってくれるような仕組みにすれば、序盤定跡の
進歩に対して追随していくだけで相当なものになるのじゃないかと。

それは兎も角、一切定跡を入れてないＣＯＭが二枚落ちで４筋の位を取れるようになったらプロに楽勝しそうな希ガス

>363
マシンパワーというか、半導体の集積度は指数関数的に上がっているが

プログラム一定で、コンピュータを競い合う大会も、たまにはあってもいいと思う。
会場に持込むのは難しいかもしれないが、ネットなら比較的簡単だと思う。
ＮＡＳＡや、大学、研究所などの参戦があればおもしろいと思う。

将棋で評価関数の自動学習が難しいのは単なる組み合わせの数の多さよりも、
終盤になっても駒数が減らず局面の組み合わせが収束しないというのが最大の原因。

チェスでもオセロでも終盤になるにしたがって収束するので終盤付近では力技の読みだけでも
人間よりはるかに正確に手の良し悪しを判定出来る。
なのでそれを利用して終盤の正確な評価関数を自動学習出来る。

するとそれを利用してそこから少し手前の評価関数を学習し、さらに手前・・・と繰り返す事
で中盤〜序盤の評価関数を終盤から逆に辿って調整出来る。
これによって人間を超える強さを実現した。

しかし将棋では終盤でも局面が収束しないので、序盤〜中盤の評価関数をまともに
自動学習させる方法が全く存在しない。
ボナンザはそこで発想を切り替えて、人間(プロ棋士)と出来るだけ同じ手を指すこと
を目標として自動学習させているわけ。

碁は収束するのに大変ですね

>>369
碁はチェスや将棋とは全く違うアプローチが取られているよ。
チェスや将棋のような探索型のプログラムがそもそも全く通用しないので。

単純に数が多いとかそういう違いではなく、根本的に異なるゲームですよ。

>>362
たしかに、膨大な予算を組み、超一流の人材を大量に投入して、
その目的を達成しても、『当たり前じゃん』程度の感動しか
得られないかもしれません。
もっとも、今現在はその『当たり前』な事も出来ませんが･･･。

もし、『当たり前』に出来るようにするためには、
2007年時点で最高のコンピューター(PFLOPS級)ではとても非力で、
PFLOPS級のさらに数億倍〜数兆倍のスーパーコンピューターが
必要かもしれませんね。

1990年 NEC SX-3/44R 23GFLOPS
1997年 Intel ASCI Red/9152 1TFLOPS
2002年 NEC 地球シミュレータ 35TFLOPS
2005年 IBM Blue Gene/L 280TFLOPS
2010年 汎用京速計算機 10PFLOPS(予定)

↑のように、スーパーコンピューターの性能は
10年で100倍以上のペースで性能が向上しているので、
あと40年程度待てば出来るかもしれません。

>>963
私の考えている方法は
cpu開発者+プログラマー+棋士vs棋士
かもしれません。
総当り思考で人間に勝つマシンの登場は
後40年以上待たなければならないと思いました。

>>964
コンピューターで大量生産した場合の棋譜の質を高めるのは相当
のマシンスペック(現在の数億倍以上)が必要だと思いました。
直接PFLOPS級のスーパーコンピューターがプロ棋士と対戦すれば、
現在でも勝つ可能性はあるかもしれません。

今の所の私の考えは、繰り返しになりますが、
PFLOPS級のスーパーコンピューター上では
私の考えたボナンザ強化方法はスペック不足で、
さらに数億倍〜数兆倍のスーパーコンピューターの登場を
待たなければならないと言う所です。
登場まで40年以上待つ忍耐力が必要ですが･･･。
この考えは間違いでしょうか？

将棋専用Linuxディストリってあってもいいと思う
ボナ　柿木win　２４対戦　がはじめから入っていて
将棋ＤＢの全てをコントロールする
名前は　えーと　Chesix とか

自分が指した棋譜に指し手を近づけるように評価関数をチューニングする意味が
どれぐらいあるのか素朴に疑問。どうなんでしょうね、この辺？

ところで浮動小数点演算にこだわるのは何故か。

Linuxのwineでボナ動かしてるけどbook.binの
定跡読んでくれなくて、いきなり思考始めてしまうね

>375
自家中毒

>>375
通常のPC上でプログラムが作る棋譜より、さらに深く手が読める状態で
指した時に出来る棋譜の方が質が高く、さらにその棋譜が
プロ棋士並みならばその棋譜を解析し、評価関数の精度を高め、
結果として強い将棋ソフトになるのではないか？
と思い、ここで質問をさして頂いております。

もっとも、『さらに深く手が読めるようになった』だけで
プロ棋士並みの棋譜を作れるようにするためには
今のスーパーコンピューターの数億〜数兆倍の演算能力が必要と思いますが･･･。

浮動小数点演算表記を使っていた理由は、世界一速いスーパーコンピューターは
将棋を演算する上でも良い影響を及ぼすと勝手に思っていたからです。
先ほど検索してみたところ、
http://www32.ocn.ne.jp/~yss/bench.htmlにて

『囲碁や将棋のプログラムは基本的に整数演算しか行いません。
そこで、より速く動かすためには、整数演算能力の高いCPUを選びましょう。
浮動小数点演算能力が高くても効果はないです。』

と書いてあり、今後は整数演算能力を重視したいと思います。
ディープ・ブルーもチェス専用VLSIプロセッサを512個追加して作られたのですから、
予算があれば、将棋に適したCPUを新たに作り、それを使って
将棋ソフト専用スーパーコンピューターを作れば良いと思います。

度々の長文すみません。

マシンが早くなった時の差し手は、要は思考時間を増やした時の差し手と
変わらない。
探索速度は並列度の平方根に比例するとのYSSの作者さんの談を元に計算
すると現在最高レベルのスパコンでも探索速度はPCの70倍程。

では仮に1手70分の時間を与えた時に、プロが1手60秒で指す手に迫れるか？
と言うと、これは簡単に実験出来る訳で・・・
まあ程遠いと。

>>379
確かに思考時間を増やした時の指し手と
変わりませんが、一つのCPUに一つの棋譜を
200日かけて作らせれば、例えば100手の棋譜なら、
一手48時間かけて読めます。
10万個のCPUがあれば200日後には一手2880分思考時間をかけた
棋譜が10万個出来ると思うのですが･･･。

最も、この一手2880分でも不十分で、
2040年まで待ち、現在のスーパーコンピューターより
数億〜数兆倍速いスーパーコンピューターの登場によって、
少なくとも、現在のPCが一手を190年かけて思考時間を増やした時の差し手と
同じ結果が出来た時には、プロ棋士並みの棋譜が作れるのではないかと
思っています。

それでは寝ますのでまた明日。

俺の経験上、
レーティング2000同士の対局棋譜から学習させるのと
レーティング3000同士の対局棋譜から学習させるのとで
学習結果にそんな大差があるとは思えないのだが。

どちらかと言えば、最初に手作業で選出した特徴要素が何であるかというのと
どれくらいの深さまで読むのか、探索手法は何かというのでほぼ決まるんだが。

どうしてID:+uuKyFVHみたいに自分でコードすら書かずに
適当なことばかり言うのか信じられない。

そもそもボナは、評価関数を学習するために人間の棋譜使ってるわけで。
ボナ自身で作った棋譜に、それ以上の精度を持った評価関数を獲得できるとは思えませんが。

むしろボナに実装されてない評価要素の追加や吟味が必要だと思います。

>>382
> ボナ自身で作った棋譜に、それ以上の精度を持った評価関数を獲得できるとは思えませんが。

少しでもコードを自分で書けばそんな滅茶苦茶な意見は出てこないと思うんだが。

プロ棋士ですら終盤で30秒将棋だとコンピュータに敵わない(特に即詰があるとき)のだから、
そんなへたれ棋譜から学習させるぐらいなら終盤だけでもコンピュータ対コンピュータ
(時間は30秒では なくもっと与えれば良い)の棋譜から学習させたほうが
よっぽどマシに決まってるだろ。

>>383
同意

たとえば、現在の局面の評価値よりも数手の深さで探索した評価値の方が正確なので、
後者の値を教師信号として学習を行うことができる

>>368
が非常にわかりやすいね。ありがとう

つまり序・中盤はプロの真似をして差を離されない様に踏ん張る、終盤はこっちのもの！
ということか。

>>383
はっきり言うと、コンピュータも終盤は穴だらけです
「プロ≦コンピュータ」が確定しているのは、
詰みが絡んだときのみだと言えます
逆に速度計算は糞みたいなものだし、
プロは「一手数十分」で十分終盤も吟味された将棋も大量にあります

それはさておき、
bonanzaはたしか、「詰みを見つけたら学習しない」という上で、
一手読み＋静止探索での学習でしたよね
この学習では、「一手＋静止探索後の局面」を比較した場合、
将棋の神様が見て「その中で最も良い局面」になる手が
指されている棋譜が必要なのであって、
強い棋譜が必要なのではありません
もちろん、強い棋譜はその傾向にあるとは思います
ただ、その性質上、ただ十数手先をしらみつぶしにいい加減に読んだコンピュータの棋譜より、
より一手後の局面を大切にするプロの棋譜のほうがふさわしいのではないでしょうか

という意味で、やっても意味は・・と思ったわけです
以上、長文失礼しました。

>>381
http://www.logos.t.u-tokyo.ac.jp/~yokoyama/study/miwa_gpw2005.pdf
に書かれてる、評価要素の作り方は自動化されている部分が多いと思いますが、
この方向性で質の高い評価要素の作成が可能でしょうか？

>どうしてID:+uuKyFVHみたいに自分でコードすら書かずに
>適当なことばかり言うのか信じられない。

私はプログラマーではないので、コードを書けません。
テレビでコンピュータ将棋の事を知り、
興味を持ち、ここで質問をさして頂いております。
御不快な思いをさせてしまい、誠に申し訳ございません。

>>387
この論文を解釈する限り、
これは詰み将棋の話で、かなり限定的な評価要素で何とかなるので有効に働いたようです
一方で、通常の将棋の場合は、より大局的な評価要素が必要となり、
自動化では上手くいかないことも多いのではないのでしょうか

>>386
私は、今のPCが読める手数よりさらに何手深く読めば、
プロ並み棋譜が作れるか？と言う疑問に突き当たっています。

もしかしたら今のPCより、さらに十数手読めばプロ並み棋譜が
出きるかも知れませんし、今のPCより百手以上深く読まなければ
プロ並み棋譜が出来ない可能性もあるかも知れません。

>>388
やはり、自動化は難しいのですね。
コンピュータの詰み将棋の強さは
その単純さから来ている所もあると思います。

>389
「プロ並みの棋譜」とか実態の無い言葉で議論とかしないほうがいいよ。
何を持ってプロ並みとかそうじゃないとか定義づけるの？

つーか、仮にマシンパワーの進化や開発者（人間）の手による評価関数の調整で、
プロにも勝ちうるソフトが将来誕生して、よりレベルの高い棋譜を作ることができるようになったとしても、
そこから、自己学習、評価関数の自動調整による自己強化を実用化できるかどうかは
全然別のアルゴリズム作りからはじめなきゃいけないことで、それは単に強い将棋ソフトを作るよりも
ずっと困難な仕事になるっつーのは自明のことだと思うんだけど。

単に
「コンピュータ単独で完成度の高い棋譜を作ることが出来て」
「それに自己学習の手法を組み合わせれば」
爆発的に強くなるはずだ、みたいな思いつきで仰っているとしか思えない。
どうやって自己学習をさせることが出来るのか、というのが議論すべき点なのに、
それは出来はずだ、という根拠の無い前提で語られても…

>>390

>何を持ってプロ並みとかそうじゃないとか定義づけるの？
プロ棋士に5割以上の確率で勝つソフトが出力する棋譜がプロ並の棋譜、
プロ棋士に5割以下の確率で勝つソフトが出力する棋譜がプロ以下の棋譜と思います。

厳密には棋譜の強さの定義づけには数値化する必要があると思いますが、
私の考えた方法を言いますと、必勝手が分かった場合に指す手と、
分かって無い場合に指す手に『差』が有りますが、
その『差』が狭ければ狭いほど強い棋譜と言えると思います。
プロ棋士の棋譜はどれくらいの『差』があるのか
私には分かりませんが･･･。もし棋譜の強さが数値化出来る時には
必勝手も解析済みの時と思います。


>どうやって自己学習をさせることが出来るのか、というのが議論すべき点なのに

質問ばかりですみませんが、
ボナンザはプロ棋士の棋譜から評価関数を調整し、
強くなるのであれば、『棋譜の強さ＝ボナンザの強さ』になり、
強い棋譜さえ大量にあれば現在のボナンザでも
強くなると思うのですが、これは間違いでしょうか？

>>391

>プロ棋士に5割以上の確率で勝つソフトが出力する棋譜がプロ並の棋譜、
>プロ棋士に5割以下の確率で勝つソフトが出力する棋譜がプロ以下の棋譜と思います。

これは間違いです。
例えプロに5割の確率で勝てるソフトがあったとして、
しかしそれの自己対戦で得られる棋譜は、必ずしもレベルの高い棋譜ではありません

また、必勝手とおっしゃっていますが、そもそも必勝手とは何でしょうか？
それは「局面に対する最善手」でしょうか？
最善手にもいろいろあり、「勝ちやすい手」という意味でも「駒を得する手」という意味でも使われます。
例えば「局面を難しくするが、相手の大駒を取って有利な局面」と
「局面を分かりやすくするが、それほど有利ではない局面」ではどちらがベストな選択かは一概に言えません
あなたのおっしゃる必勝手。それが存在するという保証はどこにもないのです

>ボナンザはプロ棋士の棋譜から評価関数を調整し、
>強くなるのであれば、『棋譜の強さ＝ボナンザの強さ』になり、
>強い棋譜さえ大量にあれば現在のボナンザでも
>強くなると思うのですが、これは間違いでしょうか？

これについては>>386の下に私の意見を書きましたので、良かったら目を通してください

では

バカにバカがマジレスしている構図に付いてどう思いますか？

山下さんの文章によると、棚瀬将棋も激指も新しいやり方を試みているようで、
来年も楽しみだね。

>>932

>自己対戦で得られる棋譜は、必ずしもレベルの高い棋譜ではありません

なるほど、ここに私の考えの間違いがあるわけですね。
皆様にお手数をおかけしてすみませんでした。
私の考えを達成するためには必勝法
の解析完了によって、完璧な評価関数を作るしかないようです。

>必勝手とおっしゃっていますが、そもそも必勝手とは何でしょうか？

必勝手ではなく、必勝法でした。誤解を招き、すみませんでした。
私の言っている必勝法とは、
http://journal.mycom.co.jp/news/2003/09/05/09.html
↑に書いてある通り、絶対に負けない方法です。
将棋は10の220乗通りの検証が必要です。
http://www.suken.co.jp/subject/jyoho/inet/inet05/inet05-1.pdf
↑では1秒間に数十万手読むPCが解析すると、500億年かかるとされています。
私の考えた解析方法は、唯一、コンピュータ技術の向上に期待する事です。
例えば、スーパーコンピューターの能力は10年で100倍以上、上がっています。
50年後には今の100億倍早いスーパーコンピューターが
現れる可能性がありますので、これならば、必勝法が分かるかもしれません。

>395
「語り」たいのなら、コンピュータ将棋の本でも読んでからの方がいいし、
「質問」したいなら、もう少し質問らしくしたほうがいい。

自動学習とは単に問題に対する最適化手法に過ぎない訳で人間の学習と混同してる時点で勘違いが甚だしい。
>>たとえば、現在の局面の評価値よりも数手の深さで探索した評価値の方が正確なので、
>>後者の値を教師信号として学習を行うことができる

例えばこれを実装すればどうなるか、当然読みを深くしても評価値が変化しない方向に収束するので
結果、「どんな盤面でも同一点と評価する」という酷い評価関数が出来上がってしまう。

自動学習させる場合、最適化の目的は何か？何を持って良し悪しを判定するか？
入力から出力を導く関数をどのような構造にするか？それに合わせてどのような最適化手法を導入するか？
またその最適化手法を適用して学習が収束するのか？得られた解の信頼性は？

これらを正しく理解し、検討し、設計しなければならない。
それを分からない人がCPUだけ早くしても、まさに猫に小判。

>>396
質問は私の考えた方法(>>350)でボナンザが
強くなるかどうかでした。
皆様のお答えによって、自己対戦によって
強くなるのは現時点では非現実的なアプローチ(>>392)だと
結論が出ました(>>395)ので、ここで一応質問は終わります。

皆様、勉強不足な私の質問に、真摯なお答えを頂き、誠に有難うございました。

なお参考までオセロの場合にどうやって自動学習するか？
それをもう少し詳しく説明してしまうとぶっちゃけ全探索ですｗ

つまり過去の数万-数十万のある程度進行した盤面のデータがあります。
これを有志の方が膨大な時間をかけて全探索(αβだけどね)を行い、
双方最終手まで最善手を指した場合に、何点差となったかを評価値としたデータを作成したのです。

これが一般に公開されているので今では誰でも自動学習にトライ出来ます。
これは何せ、本物の最善手ですのでこれ以上ない正確な評価値です。

でも将棋ではそんな訳にいかないのは上のほうで説明したとおり。
なお最後に、
>>1秒間に数十万手読むPCが解析すると、500億年
これで解析出来る手は50万手×500億年としておよそ10の24乗通りです。
10の220乗通り計算するには
500億年×1兆×1兆×1兆×1兆×1兆×1兆×1兆×1兆×1兆×1兆×1兆×1兆×1万年
ほど見ておいて下さいｗ

羽生なら羽生の棋譜だけ学習させて、羽生そっくりの思考作れないの？
完全にコピーできたら、１００年後のトップ棋士とバーチャル羽生が戦えるんだからすごいよ

>>400
10万局ほどのデータが必要として、
1日10局の奴隷労働させても約30年ですか・・・・

哀れ羽生。

>>400
探索法は学習できるわけではないし、いまのコンピュータは人間のような超並列処理に向かないし、
特徴要素の抽出は人間が手作業でやってんだし、せいぜい静止評価関数がほんのわずかだけ
羽生っぽくなるだけでね？

100億倍早いマシーンなどで必勝法などわかるはずもない・・・
10^200という数字のすさまじさは>>399　がわかりやすいね。

>>400
それの大山さんﾊﾞｰｼﾞｮﾝ激指がやってたよ。何年か前に発表したやつ。
正解率は微妙らしいけど。
今回の選手権にはそれを本格的に取り入れているらしい。

ネタですけど。
251 ：名無し名人：2007/04/29(日) 14:23:18 ID:6FI+6n6K
「東大将棋夢想転生」
棚瀬将棋の学習機能を使って、伝説の名棋士の棋風を再現。
学習させた６万局の棋譜の中から、指定した棋士の指し手の重み付けを１０倍にして、棋風をシュミレートしたソフト。
大山・中原・谷川・羽生はもとより、坂田三吉や天野宗歩などコンピュータが作り出したバーチャルな棋士との対戦が楽しめる。
弓月城太郎の「神秘体験」とセット販売の予定。

253 ：251：2007/04/30(月) 19:53:38 ID:Ol/v/vbB
弓月城太郎の「神秘体験」はどうせ売れ残るから、「東大将棋夢想転生」のオマケでいいです。。

旅人＝ちわわ　必死だな

何億手読もうが
変な手読んだら
一緒

普通に人間の限界点付近に達したら
普通に人間に負けなくなるよ

>>399
http://journal.mycom.co.jp/news/2002/12/19/12.html
↑のように、スーパーコンピューターが5年で27倍性能が向上すると仮定した場合、
800年後には10の220乗通りの検証も1年で出来るようになり、
必勝法が分かると思います。

ヒント：10の220乗はこの世の原子数より多い

>>410
探索ってのは、探索したすべての局面をメモリに保持するわけではないから、無問題

>411
でも保存しないと一手分しか覚えていないから、次の一手を指すためにはまた一年間探索だよｗ。

>411
でも保存しないと一手分しか覚えていないから、次の一手を指すためにはまた一年間探索だよｗ。

ア、二重カキコしちまった。スマソ！

それに最近のスーパーコンピュータの性能向上はもっぱら
並列性向上によるものだから5年で27倍もの性能向上が
800年も続くとすると（27^130か）
キャッシュメモリーなどのCPU内ローカルメモリーだけで
全宇宙の原子数を軽く越えそうな気がするｗ。

10^80くらいだっけ？　全宇宙の原子数。

別のやり方で計算力の理論的極限を見積もるなら、
宇宙の推定年齢（4.3×10^17秒)÷プランク時間(5.391×10^-44)=8＊10^60

掛ける

(観測可能な範囲にある)全宇宙の原子数10^80で
約8×10^140となるな。

8×10^60はCPUの速度＊計算に与えられる時間の極限、
10^80は並列性の理論的極限とみなして。

と言うわけで将棋の必勝法を見つけるにはやはり量子コンピュータが必須と思われ。

あー「プランク時間」て何？と言う人は
物理学の教科書か百科事典(Wikiなど)を参照してね。

量子コンピュータについては以下のNTTのページが分かりやすいかも。
http://www.ntt.co.jp/news/news04/0409/040909.html

これじゃ
何年経ってもﾌﾟﾛには勝てないね
安心安心

将棋ソフト「ボナンザ」は人間の手で操作

２０日午前１０時ごろの会見で、大和証券スタッフ数名の内部告発により、
最強将棋ソフト「ボナンザ」を人為的に負けさせたという事実が発覚した。
３月２１日に東京・品川プリンスホテルで行われた渡辺明竜王（２２）と
最強将棋ソフト「ボナンザ」の特別対局で、ボナンザ優勢の終盤戦を迎え、
１００手目の渡辺竜王の王手に対し、ボナンザの長考を装って画面を一時
中断し、将棋関係者と相談した末に▲２八同馬が正着であるのを▲同銀に
訂正させたという。
主催者側は事件の大筋を認め「渡辺竜王とは長期契約をしていたため、
初対局で負けては困ると判断した。ファンの方には申し訳ないと思っている」
と謝罪している。（朝日新聞）

関連スレ：【ボナ】ソフトに勝てない将棋界に未来はあるのか？【最強】
http://game12.2ch.net/test/read.cgi/bgame/1174024683/l50

人間トップが将棋のパーフェクトプレーヤーに限りなく近い強さを持ってるなら
コンピュータが勝てるのは相当先になりそうだけど

>420
単に「将棋の神」と言えば？

Yss-ｃomputer　ソフト　Ｒ２７４４
24名人　ookuwa氏　　　Ｒ２６９１
24竜王　gerard氏 　Ｒ２６９４
24達人syunaidar氏 　Ｒ２６８５

ソフトは既に２４名人、竜王、達人をも越えてるね。

対人間に関してはボナが１番だね

俺も勝率が１番悪いね、ボナが

>>416
私も、将棋の必勝法を見つけるには、量子コンピュータのような
革新的な技術が確立されなければ不可能だと思います。
もっとも、量子コンピュータの登場には後数十年待たねばなりませんから、
まだまだコンピューターは名人には勝てませんが･･･。

量子コンピュータについて私も調べてみました。

量子コンピュータ，夢の正体
http://itpro.nikkeibp.co.jp/free/NC/TOKU2/20030804/1/

3者間の量子テレポーテーション実験に成功（基礎研究最前線）
http://www.jst.go.jp/kisoken/seika/zensen/09furusawa/index.html

【レポート】量子コンピュータとは(1) - 暗号を短時間で破る超高速性能の秘密
http://journal.mycom.co.jp/news/2003/01/01/05.html

ただ、必勝法を知ってしまうと、将棋が面白くなくなるかも･･･。

>424
心配するには及びません。
必勝法は多分、人間が覚えきれるような単純なルールで表現できる可能性は低いと思われます。
下手をするとどんなコンピュータでも覚えきれないほどの情報量であり、
一手ごとに当該局面から終局まで読み直すしか最善手を指す方法が無いのかも知れません。

つまり必勝法は存在するが、情報の圧縮がほとんど効かないと言う
本質的に複雑な問題であるという可能性があり得ます。

あ、その場合でももちろん先手と後手が双方最善を尽くした
場合の勝敗およびその時の棋譜は得られると思いますが、
（そのパターンすら膨大な数である可能性もあります）
それと誰を相手にしても負けないと言う意味での必勝法は
また全然別問題のはずですから。

>424
必勝法の解明と対プロ勝利との間には何の関係も無いのだけれど。
人間ごときに勝つのに必勝法なぞいらんよ？
まあ今のところは人間ごときにまるで歯がたたないんだけどさ。

なあ、前からちょっと悩んでるんだが先手必勝あるいは後手必勝の
（双方最善を尽くすと引き分けかも知れないけど）結論が出た場合、
最善手ってどう定義すべきかね？

例えば先手必勝であれば後手がどう指しても必ず先手の勝ちに至る筋は
それこそ山のように有りそうだし。

やはり勝つ側はなるべく短い手数で勝つ指し手、負ける側はなるべく
長い手数で負けに至る筋を選んでそれを”最善手”とすべきだろうか？
それでも同じ長さのものが無数に出て来そうな気はするが。

結論が引き分け（千日手）だったら長い方が良いのか短い方が良いのか？
その場合どっちでも同じかね？

詰め将棋と同じで最長手数の応手を敗北側の最善手とするんじゃまいか

>>428に関連してだが、
香を打っても飛車を打っても相手玉が詰む場合、
どちらを打つ方が自然かな？

詰将棋の場合は高い価値のほうで指す
雑兵よりも位の高いサムライに討ち取らせるのがいいんだとw

>423

半年ほど前に奨励会の方に伺った話ですが，ボナンザよりも激指のほうが筋がよいとのことでした．筋がよいことが最重要ではないかもしれませんが．

人間より異質の手を指して強い方が価値がありそうだが

24トップのソフトは大体激指だから対人間一番は激指っぽいな
レートの伸び率からＡＩ将棋の可能性もあるが

この手の方法論って盤面の展開そのもの（駒の配置）を対象にしているけど、
視点を対局者の思考ルーチンや内部状態にも向けた研究ってあるの？

要は相手の棋風を考慮した読みということね。
相手モデル探索といって、簡単にいえば自分と相手の二回評価関数を呼ぶことになる。
読み手を半分にしても効果があるかどうかということだね

http://ci.nii.ac.jp/naid/110002872077/

思考ルーチンを公開する作者がいるのか???

つ うさぴょん

>>424
量子コンピュータを勘違いしていないか？
あれはプログラム可能型のノイマン式コンピュータではない。
つまりソフトウエアで動く仕組みが存在しない。
つまり量子コンピュータではゲームもできないし、インターネットで
ブラウザで楽しむこともできない。
現状は因数分解の類のアルゴリズムしか発見されていない。

>439
君もちょこちょこ勘違いしてると思うが？
もうちょっと調べてから書いた方が良いと思うよ。
本質的に間違ってるとは言えないけど。

>>440
知ったか乙
日本語でおｋ

＞441
そう思っておけば？
それじゃ進歩ないけど。

将棋思考プログラム(ボナンザプロトコル版,ソース付)
ttp://mucho.girly.jp/cgi/shogiup/src/up0011.zip

なにこれ？？

>>443
ダウンロードしてreadme.txtを読みましたが、
ボナンザと同じプロトコルを採用したオリジナルの思考ルーチンみたい。
せっかくなんでソースを読んでみます。

ソース読んでみました。
マイボナって標準入力で手をやりとりするんですね。

プログラムが短くてシンプルですね。
静止探索はやってないとありますが、末端だけ駒損手を生成しないので少しやってる感じかも

評価関数は駒得だけなんですね。
あとは、ハッシュとNullMove（パスしてnullWindow探索してもベータ超えるようなら、何をやってもベータカットが置きそうなんで、探索せずにベータカットしていいんじゃね？）をやられると速くなると思います……

>445
「ボナンザ　Bonanza 専用スレ 9手目」にそれをアップした人が書き込んでるよ。
あっちが本スレかな？

掲示板で読みの深さと最善手の更新確率の話が出たが，
深さを軸にとるのはどうなんだろう。同じ1手深く読むとは言っても、
2手から3手は1.5倍深くなり、3手から4手は1.333倍しか深くないという風に考える事もできる。

もちろん、一手深くしていくごとに評価する局面の数の増えっぷりはアレだが

>>447　YSSの掲示板のことですね。
なるほど。同じ1手深く読む場合でも
深いところほど、全体での深さの増え方が減ってるってことか……。

あの議論は、
山下さんはある程度深いところでは90%ぐらいはルートの手が変わらないから
並列探索してもいいんじゃね？

保木さんはルートに有力手が複数あるときはルートの並列探索はやめたほうがいい

ってことかな？

そもそも有力手が複数ある場合はなぜルートで並列探索しない方がいいんだろ？
むしろ有力手が複数ある場合こそ並列探索した方がいい気もするけど。

有力手が複数あると、同期処理が面倒ってことらしい？

変なのが連投してるな。なんだありゃ

人工無脳じゃね？ｗｗ
それらしい単語が並んでるだけで・・

今見たらそうでもなかった。失礼

tss -> 初心者 だと思うが、さて・・・

848 名前：☆いまさらだが、BTRONの体験版☆[age] 投稿日：2007/06/06(水) 10:42:04

1B/V3体験版のご案内
http://www.personal-media.co.jp/tron/1bv3_taiken.html
ftp://ftp.personal-media.co.jp/pub/1b/p971212.exe

1BV3体験版
http://tat.soga.in/btron/modules/bwiki/index.php?OS%2F1BV3%C2%CE%B8%B3%C8%C7
「超漢字」を体験させてほしい
http://homepage1.nifty.com/isdknit/_tqFOnLE.html

DeepBlueは、アドバンスドチェス。

つまり、インチキ。

だから、わざと保存しなかった。

しったか乙

知ったかと言うより、根拠のない言いがかりかと。
DeepBlueが一試合ごとにパラメータ調整して、差し方が毎回変わった事に
カスパロフが幻惑された事を指しているならそう言えるかも試練が。

>>455
カスパロフサイドが負け惜しみで言っているだけ。
上場企業のIBMがたかだチェスごときにばれたら大変なことになる陰謀に手を染めるわけがない。

YSSの中の人がいう”推定高速化”って何のことだろう。
評価局面数が高速化度そのものではないのだろうか

>>459
並列化による勝率の上昇から推測した高速化の度合い。
例えば４スレッドの並列で４倍のnpsを実現しても、実際は少し無駄な探索が生じるので、
４倍の時間を与えたほどには勝率が上昇しない。

仮に「評価関数の呼出回数」という基準で並列化度が１００％だとしても
そもそも無駄な評価関数呼出を行っているから性能向上という観点で
評価すると必ずしも高速化しているとはいえない。

という理解でいいかな。そして、

並列化によって向上した勝率と同じだけの勝率となるような、
単一ＣＰＵでの高速化による勝率を算出して、これを「推定高速化」
と呼ぶことにした。

ってことでおｋ？

仮にαβも無しの素のminmaxであれば、並列度がそのまま速度向上になるが、
枝狩りを行っている場合、並列化で割り振るタスクが本来読まずにすむ（刈られる運命にある）
枝であるために空振りに終わる事があるっていう感じか。

これからさき更にコアが増えていくと混沌としそうだ。一番楽なのはやっぱりヘテロ処理なのか

指し手生成(とその順位付け)だけを並列化すれば無駄は少ない

指し手生成(　0手先読み　)、一手先読み・・・と近い部分から順次読んでいけばcpuも休まない
しかし、過去のインターネット先読みの例からいうと大したことがないか?
複数cpuだから効果あるか?

投稿者：初心者とIPが一致しました。（編集済）

プロに勝つ方法
1.詰めろアルゴリズムを詰める。
2.必死アルゴリズムを詰める。
3.終盤の速度計算をする。
4.定跡データベースを詰める。
5.NECのSX-8iを借りて、序盤即終盤にする。

モデルはタイガーウッズ。

>>368
将棋でも、終盤から序盤、序盤から終盤の往復学習は有効だよ。

>465
2.と3. とりわけ3.が難しそうだな。

>466
往復学習ってどういうデータを元に行わせるの？
人間が指した実戦の棋譜？それとも計算機自身に読ませて作るの？

>>456-458
アメリカはリアル陰謀の国。

ツカレルなーｗ

1番あたりを将棋が強い人に聞いてみたいんだが、
詰めろは今の将棋ソフトでも判る。
問題は、詰めろを相手が回避しても詰めろがかかって、
それ回避しても詰めろがかかってみたいな、
竜王ボナ戦みたいな終盤

詰め将棋は王手が続く限り読み続けるので深くても読めるが、
連続詰めろは、手が多くてそれも難しいと思われる
このへんが解決されれば、ずいぶん終盤力が上がると思う。

このへんの感覚は人間は、読みで解決？　それとも大局観？

コンピュータの場合連続詰めろの検索は３手でもかなり厳しいのが実情。
人間は経験の蓄積から並列的にデータを引っ張り出してきている感じなので、
コンピュータの最も苦手な分野とも言える。

24で2200程度の人間の話だけど
寄せで詰めろはあんま読んでない

もちろん微妙な詰みの場合はキッチリ読むけど
どっちかというと「まずこの形は詰めろ」とか「おんなじ筋で詰みだから詰めろ」とか
形や読みの再利用をすることによってかなり実質的な読みを減らしてる

>>472
なるへそ
人間だから詰めろ連続を読み切れてるってわけでも無さそうだね。
詰め将棋についても、プロ棋士が単純な見落としした例もあるし、

詰めも詰めろも、
局面の部分的なパターン認識を再利用してるかも人間。

Freisinn :: 一挙公開
http://yashiromann.sakura.ne.jp/diary/blosxom.cgi/tron/btron/20060831bappl.htm

MPLAYER
　MPEG動画プレーヤーです。MPEG-1 および MPEG-2 に対応しています。

レコードエディタ
　任意のレコードを編集できる高機能なバイナリエディタです。

SmartPoint
　プレゼンテーション用のツールです。

アプリケーション一覧/登録/更新
　BTRONアプリケーションの登録作業を柔軟かつ楽に行うためのツール群です。

データボックス編集
　データボックスレコードをグラフィカルに編集するためのアプリケーションです。

プロ棋士に勝つ方法

1.詰めろアルゴリズムを詰める。
2.必死アルゴリズムを詰める。
3.終盤の速度計算をする。
4.定跡データベースを詰める。
5.乱戦模様に誘導する。
6.NECのSX-8iを借りる。

モデルはタイガーウッズ。序盤即終盤。

いまだに全数手を計算できるなんて、トンデモな発想している奴がいるとはｗ

888 名前：名無し名人[sage] 投稿日：2007/07/16(月) 09:25:31 ID:3txnVwiF
ｗを付けるやつはその時点で痛いが
文章の内容自体も痛いという傾向がある

なあ、将棋の必勝法を見つけるには完全ゲーム木を作って
その上を探索するしかないと言う雰囲気に何となくなってるが
それは証明された事じゃないよな？

全通りの差し手を探索しなくても必勝法が見つかる可能性も
まだ、わずかながらあると思う。

＞478
全探索をしないで発見した「必勝法」が本当に必勝法かどうか
どうやって調べるのですかw

>479
理論で押さえ込むんだよ。
つまり実際には探索しないで探索したのと実質的に等価な情報を得る。
ある種の情報圧縮だな。αβカットだってそうだろ？

実際に可能だと言ってるんじゃないよ。
可能かも知れないと言うだけ。
直感的には不可能っぽいがこれまた
（不可能だと言う証明も）難しいと思う。

αβとかは評価値がアナログだから枝を刈る価値があるけど
必勝かどうかは勝ちか負けのデジタルだから評価値で刈るってのはできないんじゃないの？

勝ち1引き分け0負け-1を割り当ててルートで(-1,1)で呼べばいいだけじゃん
むしろこっちのほうが早く終わるぞ
読みきれるゲームなら

方がもなにも、必勝法を探すにはそうするしかないよねぇ

チェッカーが解明されたようだが、
まさに>>480が言うような手法じゃないか？

いくら18年かけたといえ、巨大な探索木をすべて読めるわけないし、
結局、
相手がどういう手を指そうと、こちらが最善手を指し続ければ
負けないことが証明できればいいわけだった。

>482
評価関数の値を優勢なら１。劣勢なら-1と扱って探索するのはありかもしれん

Endgameのデータベースを基にしてるようだが＜チェッカー

>>485
そのEndGameデータベースは、
長い時間をかけて、
DFPN+という詰め探索（ある種の情報圧縮）を使って
作られたようだよ。

将棋の場合、終盤が収束しないので終盤データベースを作れないのが……
オセロ、囲碁でも終盤DBは聞かないな。
手は減ると思うが、局面パターンは膨大だからかな？

チェスが特殊（延々続く）なんじゃない？
囲碁も九路なら作れそうだけど読んだ方が速いしオセロもそう
十九路は流石に無理だろうし

「スパコン、無料で貸します」東大など８大学、民間に
http://www.asahi.com/national/update/0724/TKY200707240535.html

よしこれでがんばってくれ

>>487

>囲碁も九路なら作れそうだけど読んだ方が速いしオセロもそう
　モンテカルロは並列化してもリニアに近く効率が出るみたいなので、

>>488が言うように、超並列のスパコンで、やったら

　9路なら超並列計算で、プロに勝てるのもう作れるじゃないか？
　実際はUCTが並列計算でどのくらい効率が出るかよく知らんけど。
　スパコンTOP500とかだと数万プロセッサとかあるんで。
　東工大のTSUBAMEとかいいんでないかい。
　　
　オセロは、終盤はそうとう深く読めるし、
　実際探索してるのは中盤の数手だよね？　そのへんがくっつけば、
　完全解明になると言えるのかな？

>実際はUCTが並列計算でどのくらい効率が出るかよく知らんけど。
MC部を並列化するとUCT部が本来の動作と微妙に変わるから
余り並列度を高くすると妙な動作をする可能性がある
それにMC部だけ超並列にしてもUCT部(の処理速度)がボトルネックになってしまう
UCT部そのものの並列化はまだ上手くいってないようだ

>UCT部そのものの並列化はまだ上手くいってないようだ
　解説THX!
　UCTほど性能が無くても並列性が良いアルゴリズムを考えるのもいいかもねー。
　なんにせよあと3年くらい経ったら、将棋より囲碁の方がプロに近づいている気がする。

それはないｗ

九路なら３年でプロに近づいている可能性もなくはないと思う

>>491
同意

本人乙

みんなで激指を買って遊ぼうよね♪（　＾ω＾）

激指 定跡道場

商品紹介
2005年世界コンピュータ将棋選手権で全勝優勝を飾った「激指」のシリーズ最新作。
序盤戦術を体系立てて学習できるモードを搭載、最強の思考エンジンに加えて学習補助機能が充実しました。
定跡講座は所司和晴七段が全面協力、プロ将棋の最先端を無理なく身につけることが出来ます。

q

B-TRONの体験版・・・(超漢字のご先祖)

1B/V3体験版のご案内
http://www.personal-media.co.jp/tron/1bv3_taiken.html
ftp://ftp.personal-media.co.jp/pub/1b/p971212.exe

1BV3体験版
http://tat.soga.in/btron/modules/bwiki/index.php?OS%2F1BV3%C2%CE%B8%B3%C8%C7
「超漢字」を体験させてほしい
http://homepage1.nifty.com/isdknit/_tqFOnLE.html

オープンギャラリー:1B/V3の環境
http://www.ne.jp/asahi/open/gallery/1bv3/1bv3.htm

オープンギャラリー：プラットフォームコーナ
http://www.ne.jp/asahi/open/gallery/platform.htm

ｺﾝﾋﾟｭｰﾀ囲碁ってさ途中まで真似碁で打ってさ、終盤に形が決まってからﾌﾘｰ打ちすりゃ、そのへんのおっちゃんには勝てるんじゃない？

勝てるかもしれんが意味がねえ

でもそんなの関係ねえ

誰か評価関数における評価項目をうまいことまとめてもらえませんかorz

「コンピュータ将棋の進歩」１〜５嫁

駒割
大駒の安全度
王の安全度
位取り
脅威

お前らアホかｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ネット将棋なんてのはな、ソフトで指そうが何しようがOKなんだよｗｗｗｗｗｗｗｗｗ
なぜならな、ネット将棋ってのは、いかに相手を叩きのめして優越感を味わうかが重要だからだｗｗｗｗ
それを競うゲームなんだよｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
そのためには何をやってもいいんですぅ〜〜〜〜ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
自分の力？？？正々堂々？？？？？
馬鹿じゃねーの？？？？？？？？？ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
俺様は今後もソフトを使ってどんどんお前らをブッ殺してやるぜｗｗｗｗｗｗｗ
悔しいねぇｗｗｗｗｗｗｗｗｗ俺みたいなクソ野郎に負けちゃって悔しいねぇｗｗｗｗｗｗｗｗｗ
お前らカスどもの屍の上で勝ち誇る俺様を見て、悔し涙でも流しているといいさｗｗｗｗｗｗｗｗｗｗ
ぎゃっはｈっはははははははははははｈｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
あっひゃっひゃっひゃはｙはやｈっひゃははっやはひゃっはｈｙ「ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
笑が止まらねーぜええうぇえええええええうぇええええええええｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
殺せ殺せえええええええええええええええｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ネット将棋ってのはな、心を殺しあうゲームなんだあああああああああああｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
殺してやるぜええええええええええｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
死ねシネシネ死ねえええええええええええええええええええええええええええええええええええ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

ヘタな煽りだなﾌﾟ

と言うかスレ汚しのコピペやめれ。

しかし駒数が規定より多い変則対局は出来ないソフト多いよな。

王飛角香は座標記録して特例処理のほうが都合いいこともあるだろうけど、
他の駒も駄目なんだよな。

お前らアホかｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ネット将棋なんてのはな、ソフトで指そうが何しようがOKなんだよｗｗｗｗｗｗｗｗｗ
なぜならな、ネット将棋ってのは、いかに相手を叩きのめして優越感を味わうかが重要だからだｗｗｗｗ
それを競うゲームなんだよｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
そのためには何をやってもいいんですぅ〜〜〜〜ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
自分の力？？？正々堂々？？？？？
馬鹿じゃねーの？？？？？？？？？ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
俺様は今後もソフトを使ってどんどんお前らをブッ殺してやるぜｗｗｗｗｗｗｗ
悔しいねぇｗｗｗｗｗｗｗｗｗ俺みたいなクソ野郎に負けちゃって悔しいねぇｗｗｗｗｗｗｗｗｗ
お前らカスどもの屍の上で勝ち誇る俺様を見て、悔し涙でも流しているといいさｗｗｗｗｗｗｗｗｗｗ
ぎゃっはｈっはははははははははははｈｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
あっひゃっひゃっひゃはｙはやｈっひゃははっやはひゃっはｈｙ「ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
笑が止まらねーぜええうぇえええええええうぇええええええええｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
殺せ殺せえええええええええええええええｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ネット将棋ってのはな、心を殺しあうゲームなんだあああああああああああｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
殺してやるぜええええええええええｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
死ねシネシネ死ねえええええええええええええええええええええええええええええええええええ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

恥ずかしい人を見つけました