おまいら最強の将棋プログラムしてみろよ part6

できたらよろこんでやる。
前スレ
おまいら最強の将棋プログラムしてみろよ part5
http://pc11.2ch.net/test/read.cgi/tech/1109307327/

過去スレ
おまいら最強の将棋プログラムしてみろよ part4
http://pc5.2ch.net/test/read.cgi/tech/1086678961/
おまいら最強の将棋プログラムしてみろよ part3
http://pc5.2ch.net/test/read.cgi/tech/1064984089/l50
おまいら最強の将棋プログラムしてみろよ part2
http://pc2.2ch.net/test/read.cgi/tech/1043246252/
おまえら最強の将棋プログラムしてみろよ！！
http://pc2.2ch.net/tech/kako/1004/10043/1004395614.html

関連スレ
▲コンピュータ将棋スレッド35▽
コンピューター将棋番外編5・アルゴリズム
http://game12.2ch.net/test/read.cgi/bgame/1175435755/
▲コンピュータ将棋スレッド35▽
http://game12.2ch.net/test/read.cgi/bgame/1170114501/

TCP/IP通信プロトコル（コンピュータ将棋協会）
http://www.computer-shogi.org/protocol/

アップローダ (Part3 929氏提供)
http://gm.a-ark.net/~shogi/clip/clip.cgi

CSAサーバ (Part3 773氏作、Part3 783氏提供)
アドレス wdoor.c.u-tokyo.ac.jp 4081
棋譜など http://wdoor.c.u-tokyo.ac.jp/shogi/LATEST/

MTD(F)
http://www.cs.vu.nl/~aske/mtdf.html
ゲーム木の探索問題
http://tt.sakura.ne.jp/~suzu/search_problem/index.html
反復深化
http://tt.sakura.ne.jp/~suzu/search_problem/i_deepening.html
最良優先探索
http://kyu.pobox.ne.jp/softcomputing/ai/ai3.html

遷移確率、激指
http://www.logos.t.u-tokyo.ac.jp/~gekisashi/algorithm/abstract.html
GNU shogi
http://www.cs.caltech.edu/~mvanier/hacking/gnushogi/gnushogi.html
福将棋
http://touch-mi.hp.infoseek.co.jp/csa2001/prog.htm

あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あ

ゴメンネ！　オレ必至すぎてゴメンネ！

ボナの最適化アルゴリズムが実は「強化学習」なんじゃないかなー？
と思い始める前に

森北出版の『強化学習』R. Sutton・A. Barto著
(原著：Reinforcement Learning: An Introduction)

をネット書店に注文していて、ちょうど今日届いたもんだから
ちょっと舞い上がっちゃっててね。 そうであってくれると嬉しいんだ。
（でも、もしそうなら既に実現されていて、ちょっとくやしいｗ）

強化学習って環境との相互作用から学習するというやつで
バックギャモンのそれは自分との対戦から学習していくという方式
ボナンザのは探索こそしているけれど、環境との相互作用とはいいにくい
だから、強化学習とは違うと思う。

どちらかというと統計的学習じゃないのかな

wikipediaのコンピュータ将棋の項を見ていて、
人工知能という単語が目に入った瞬間コーヒーふいた

なんで？>>9

まあ、昔から人工知能の課題とされて来たものは研究がある程度進展した
段階で必ず、もはや人工知能の課題とはみなされなくなって来た。

音声認識も自動翻訳も人間との（簡単な）会話もチェスも将棋も。
どれもまだ全然完全じゃないんだけどね。
（その昔、チェスを機械に指させる事はリッパな人工知能の課題だった）

つまり「人工知能」って言うのは見果てぬ夢に対して付けられる
看板であって具体的な課題、技術、手法の事じゃないんだよ。

なるほど

>>11の定義って一般的なの？
別にコンピュータチェスとか将棋とかが人工知能でも違和感ないのだけど
人工知能系の学会ではチェスや囲碁は研究されてないのかな

>どちらかというと統計的学習じゃないのかな
正解

パターン認識は流石に外れてるかな
ゲームはまだ人工知能に含まれてる
プランニングは十分人工知能だし（ゲームもプランニングの一種）

プランニングって何？
計画を立てること？

中学生でも知ってる単語だろうが

ごめん俺消防だから教えて

行動計画だったかな。
目標状態を得るための行動の組み合わせと順序を探索他で決定するやつ。

要するに巡回セールスマン問題とかナップザック問題とか言う奴だろ。
実用的にはLSIの配線とかにも利用されてるようだが。

研究者から見れば十分にAIの研究かも知らんが、素人目には
これがAI研究ですって言われてもなあ……ジミだ。

アルゴリズムが発見されると、人工知能の課題でなくなっちゃうんだよな。
機械的に手順を踏めば解決しちゃうから。

>>20
それは線形計画法で実用上解決された。
AIとみる人はいないでしょう。

NPCみたいに人間の代打扱いするのが人工知能
道具扱いすれば人工知能じゃなくなる、と考えちゃ駄目？

俺は人間も本当の知能ではなくて自動機械だと考える派だから
人工知能という物ができたならそれは人間を超えてないとダメ

>それは線形計画法で実用上解決された。
線形なものしか扱えませんが。

人工知能の定義として
人間の知能を構成するために必用な技術の総体
というのでどうでしょう？

問題が与えられた時に、
「人間はどうやって問題を解いているのだろう？」
と、人間と対比して考えるのが、
人工知能分野の特徴だと思いますが。

>人工知能系の学会ではチェスや囲碁は研究されてないのかな
難しいので直接扱う人はいません。
小手先の改良をしただけでは研究にはなりませんので。

どうでもいいけどお前らほんとに将棋プログラミングしてみてるのか？
ゲ作厨が流入しているだけにしか見えんのだが。

>>25
漏れはROMに近いが一応作ってるよ
先週のオープン戦には参加してきた

>人間と対比して考えるのが、
>人工知能分野の特徴だと思いますが。
素朴な考えだけど実際は違う
人工知能は「知的」な作業を機械化する技術を開発する分野
やり方が人間と似てる必要も無いし人間と対比させる必要もない
ニューロモルフィズムと言うのがあなたの考え方に近いけど少数派
人間がどうやってるかを考えるのは認知科学（とか神経科学）

>要するに巡回セールスマン問題とかナップザック問題とか言う奴だろ。
ぉぃぉぃ
もっと複雑なアプリが山ほどある
例えば介護/警備/レスキューロボットの行動計画とか
大規模な組み合わせ最適化問題は今でも十分AIの研究テーマ
連が木スマソ

３球体問題は解けるの？

>人工知能は「知的」な作業を機械化する技術を開発する分野
知的の定義は？

知的とは人間に出来てコンピュータには出来ない知的行為のこと。

それじゃ人工知能の研究の意味ないじゃんw

人間の脳も機会と同じく生体分子の形態で思考していると思うよ

>>31
循環論法乙。

>>29
物理の三体問題のこと？
人工知能とは全然違うと思うけど、いまだに、というか永久に厳密解を
得ることは不可能ですよ。

>知的の定義は？
お好きなようにどうぞ
だから人工知能の定義も人によって異なる

>人工知能は「知的」な作業を機械化する技術を開発する分野
じゃあ、これは妄言だね

お前が将棋プログラミングに全く興味がないのはわかったからあと10年ROMっとけ。

将棋だとアルファベータとモンテカルロってどっちが強いのだろう
今のところアルファベータが主流な感じだが

大差なし、同じようなもんだ

>>40
モンテカルロ法を用いた将棋24でレーティング2000以上のコンピュータ将棋ソフトを
是非教えていただきたい。

やだ

ボナンザが、裏で「遠隔操作」を行っていたことが判明。
これじゃ、一般人が勝てる訳がない・・・

http://news22.2ch.net/test/read.cgi/newsplus/1177353357

そりゃボナンザ違いでんがな。

マサルさんのボナンザを思い出した

おまいら、そろそろ最強の将棋プログラムとやらに
とっかかってくださいよ。

SK"2

人が切れ負けになるまで「本当に成らなくてよろしいですか？」ダイアログを出し続ける

>>46
とりあえず明日逝って来る

第17回世界コンピュータ将棋選手権 ライブ中継
http://live2.computer-shogi.org/wcsc17/live_s.html

>>7

強化学習と機械学習の差を強調して書くなら、こんな感じ。

最適（と思われる）行動が教示されるのが機械学習で、Bonanzaはこれ。
将棋で言うと最善手が教示される（実際にはプロが指した手＝最善手と見なしているが）。

過去の（≠直前の）行動に対して報酬が与えられるのが強化学習で、実現したソフトは（選手権参加ソフトが公開している情報を見る限りでは）まだ無い。
将棋で言うと勝ったから100点の報酬をあげる、とかそんな感じ。

まぁ、実際には他にも色々差があるわけですが。詳しい事は7氏の買った本に載ってます。

ちなみに私は構想中。来年の選手権はそれで出ます。

VIP擬人化将棋のWikiです。
http://wiki.livedoor.jp/vipshogi/d/FrontPage?wiki_id=48341
将棋の駒を女の子にして将棋が打てるプログラム、是非試してみてください。
http://shogi.vip2ch.com/dl.php?f=koma0360.zip

プログラム作りたい！　今からとりかかる。　まずは盤だ。　来年は遠いねー。

将棋の局面の良し悪しの判定ってどういうふうにやってるの？
コンピュータにまともな判定ができるとは思えないんだけど。

駒の損得とか駒の位置関係とか玉の堅さとか・・・

強化学習は機械学習と相反するものじゃないだろう
過去の最善手を参考にしながら局面のよしあしに点数をつけるんじゃないかな。
で、反意語は教師なし学習で、これはグループ化、クラス分けをしていくことによって条件判断していくものだったと思う

>51
説明してくれてアンガト。
まだ、あの本読み始めてないけど（英語なんでとっかかるのに気合が要る）ｗ。

でもナーンか、挑戦状を叩きつけられたような気がするのは気のせいでしょうか？
相手は私ではなく多分、他の将棋プログラムを開発している方々なんでしょうが。

あ、こっちは英語じゃなかったか。
最近買った別の本と混同しちまったｗ。

激指チームが悪事の限りを尽くしているスレはこちらです。
http://game12.2ch.net/test/read.cgi/bgame/1165706999/

結局は旅人の釣りであったか・・・

コンクリートの上で垂直式ブレンバスター。
さすがのジャイアンも・・・
旅人恐るべし。。

news : 革新的なAI囲碁プログラム『Crazy Stone』
http://wiredvision.jp/news/200705/2007051121.html

これは凄いな

なんかえらく古い話だと思ったら，原文は去年の9/16じゃないか
翻訳遅すぎ＞Wired
CrazyStoneの最新版は19路でもMoGoより強いかなってとこまで来てる
丁度その秘密を書いた論文が公開されたところ
内容は主にパターン等の自動学習
ttp://remi.coulom.free.fr/Amsterdam2007/

遅いって言うかWiredは最近までずっと休刊?してたわけだが

それは旬を外れた記事を載せる理由にはならんだろ

大学が休講になっちゃった。
暇だから将棋の続きやるか。

>67
早稲田ですか？

はしかで休講になったとこはいっぱいある

昨日の午後、突然休講になった大学はそんなに多く無いと思う。
まあ、どうでも良いけどさ。

激しく今更だけど、>>51の“機械学習”は“教師あり学習”の間違いでした。
勉強しなおしてきます。

GHI問題って、手数の少ない局面の得点は足し込まないようにすれば
不詰みを、詰みと間違える事はあっても逆はないはずだよね?
詰みが、判定できたら実際に指し進めて、ループしている部分があったら
その先が詰むかどうか調べればいいんじゃないの?

ちょっと作ってみようと思ったんだけど、やっぱりC言語がいいのかなあ。
できればC#で作りたいんだけど実行速度遅いんかなあ。

>>73
元々C#使いだったんだけど速度に不満が出てきてCに移植してみたら３倍違った。
C#は何かあれば例外投げてくれるからバグに気づきやすいんだけどね。特に配列関係とか。
今でも一部のコードではC#でバグが無いように作ってからCに移植ってのは時々やってる。

Cに移植(笑)

>74
ふーん、そういうやり方でうまく行くんなら俺もまずJavaで書いておいて
C++に"移植"すると言うやり方でやってみようかな。

うさぴょんの育ての親さんのJavaで作るコンピュータ将棋の本も出てる
事だし。

でもJAVAとかC#もJITコンパイラの進歩で思ったほど実行効率落ちないみたいだね。
http://homepage2.nifty.com/Fujimaki/download/Comparison/

この結果をそのまんま鵜呑みにするのも怖いけど、実際どうなんだろう。


あと、YSSのページにこんなこと書いてた。
＞ban[256] その位置にある駒の駒番号
＞Ｃ言語では、配列の添字に２のべき乗を使うと、内部計算がビットシフトで表現され高速化されるので、配列はすべて２のべき乗にするとよい。
http://www32.ocn.ne.jp/~yss/book.html
こんなテクニックは全然知らんかったわ。まだまだおれの知らない効率化の技もいっぱいあるんだろうな。
こんなふうに最善を尽くすと、やっぱりC言語との差はかなりあるんだろうか。
教えてエロい人

そういうのはほんとはコンパイラの仕事で、賢いコンパイラは
自分で工夫してくれる（べき）ものなんじゃないかと

むしろ、そういう工夫を人がしなきゃいけないというのは
Ｃの大変な点といっていいのでは

＞＞Ｃ言語では、配列の添字に２のべき乗を使うと、内部計算がビットシフトで表現され高速化されるので、配列はすべて２のべき乗にするとよい。
真っ白な鷽ですが。
x86系CPUのビットシフトが遅いのは有名な話だし、インデックス計算みたいに頻繁に出てくるコードは
コンパイラとしては腕の見せ所ですから素人が小手先で弄ったCコードよりもよっぽど効果のあるコードを出します。

まぁ、高速化の基本は実測にあるといっても過言ではありません。

>>77
実行時最適化ができるVM上での動作の方が速くなることも多いよ。
だからLLVM
ttp://llvm.org/
なんかが開発されてる。将棋プログラムのような分岐の多いプログラムなら
Cで書くよりも最終的には速くなるかもしれない。

ただJavaやC#で計算が遅くなるのは配列を使うとき。要素へのアクセス全てが
範囲内かどうかチェックするから行列計算とかが入ると絶対的に遅くなる。

＞Ｃ言語では、配列の添字に２のべき乗を使うと、内部計算がビットシフトで表現され高速化される

これは多次元配列だけだな。でも本当に効率化をしたいなら行単位でポインタを
指定するからあんまり意味のないテクニックだと思う。

その理屈だと別に２のべき乗にしてもあまり害はないよね？誤差程度のメモリを食うだけで。
デフォルトの名無しさんのいうこととYSSの作者の言うことがちがった場合、普通はYSS作者を信じるだろうから２のべき乗で行くのが懸命だね。
もしそんなことはないっていうのなら嘘ってソースを見せて欲しい。

あと、実測は高速化の手段じゃなくて確認じゃない？

>>81は>>79へのレスね。

>>80
ってことはJAVAやC#で書いて、Cで作ったDLLを呼び出すのでFA？

>>82
>>79は明らかに嘘か無知が入ってるな。
286の時代ならともかく、今手に入るx86 CPUのビットシフトは基本的に１クロックのはず。
例えばAthlonのデータシート
ttp://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/22007.pdf
とかね。

でも配列のサイズを２のべき乗にする意味はあんまりないよ。
キャッシュのヒット率を上げる方が小手先のテクニックより重要だから、うまく
プリフェッチを入れてくれる賢いコンパイラの方が効率の良いコードを履いてくれる。

前C#で配列の添え字チェックが入らないようにMarshalクラスを使って領域確保してから
配列のように使う改造をしたことはあるけどCには及ばなかった。
>>83
自分はそうしてる。
GUIはC#で評価関数のDLLはCで作ってる。

>>81
>>79じゃないけど、簡単に分かるよ
#include <stdio.h>
#define N 63
int main( int argc, char** argv ) {
　int A[N][N][64];
　int B[N][N][64];
　int i, j, k;
　int loop;
　for ( loop = 0; loop < 1000; loop ++ ) {
　　for ( i = 0; i < N; i++ ) {
　　　for ( j = 0; j < N; j++ ) {
　　　　for ( k = 0; k < 64; k++ ) A[ i ][ j ][ k ] = 1;B[ i ][ j ][ k ] = 2;
　　　}
　　}
　　for ( i = 0; i < N; i++ ) {
　　　for ( j = 0; j < N; j++ ) {
　　　　for ( k = 0; k < 64; k++ ) B[ i ][ j ][ k ] += A[ j ][ i ][ k ];
　　　}
　　}
　　for ( i = 0; i < N; i++ ) {
　　　for ( j = 0; j < N; j++ ) {
　　　　for ( k = 0; k < 64; k++ ) B[ j ][ i ][ k ] -= A[ i ][ j ][ k ];
　　　}
　　}
　}
　return 0;
}

>>81
YSSの作者が書いた時点と今では事情も違うだろうからねぇ。
>79を信用できないなら自分で実測してみるといいよ。
コンパイルオプションはgccならgcc -O3 -funroll-loops -msse、iccならicc -fastで。
>79は自分自身も「白い嘘」である「ビットシフトが遅い」を引き合いに出しているけれど。

で、「実測は高速化の手段」とは書いていないね。「高速化の基本は実測にある」と書いているけど。
私もそれには賛成。
今までの経験で高速化されるだろうと思ったコードが実際にはそうでなかったなんてことはざら。
「○○は高速化される」なんて書いてあってもそれを鵜呑みにしちゃダメ。

これGCCでコンパイルして実行するとNが64と63では計算回数分だけ63の方が速い。
昔気質の人の高速化手法は最近はコンパイラやCPUがやってくれちゃうからコードに書く
意味はあまりないよ。

>>85
>GUIはC#で評価関数のDLLはCで作ってる。
それ超危険。
マネージドコードとアンマネージドコードの切り替えはすごいオーバーヘッドがある。

>>89
じゃあ切り替え回数をなるべく少なくするように設計するべきか？
こりゃ設計するだけで一苦労だな。
やはり生産性は落ちるが何も考えずVCあたりで作るのが無難ってことか

>>89
そりゃ探索はC#、葉の評価はCみたいにアホな設計の場合でそ。

>>77
山下さんの勘違いがあって、全て２のべき乗にする意味はないでしょう。
１次元配列A[x]は*(A+x)で掛け算は出てきませんし。
２次元配列でも一番左側の添字は２のべき乗にする必要はありません。

>>88
これは失礼ながら全く見当違い。
２のべき乗にするかどうかという議論はあえて余分な領域を取るかどうかという話で、
計算回数が増えるわけではありません。

>>93
分かってますよ。
１．配列の先頭のアドレスが2^nになるとアドレスの計算が速くなるか
２．ポインタのアドレスがラインにヒットさせることを常に心がけるべきか
ってことが問題で、もう少し複雑にNを64にしても走査する範囲を63にすればいいだけです。
だから「計算回数分だけ」Nが63の方が速いと言っているので、見当違いはそちらでしょう。

と、分かりにくいかもしれないので追記。
もし配列の要素数を2^nにするのがよいのだとしたらNが64の方が計算回数が多くても
それを覆すほどの利点があって速くなるはず、あるいは一つの計算あたりのマシンタイムは
確実に速くなるはず、という前提で言っているので、計算回数あたりの時間が同じであった
という実験の結果から、配列の要素数をどうするかは目に見える違いにはならないという
結論を導いたので、私の意図を>>93には理解してもらえてないのだろうな、ということです。

>>95
「計算回数あたりの時間が同じであった」というのは元々は書いてありませんでしたが。
あと現在のまともなコンパイラーなら最適化によりあなたのプログラムでは配列へのアクセスに掛け算は発生しないと思います。
つまりA[i][j][k]へのアドレスの計算をいちいち
A+i*N*N+j*64+k
などとしなくてもfor (k=..)のループなら直前のアドレスをインクリメントするだけ、
for (j=..)でも64を足すだけでいいので。

将棋ではもっとランダムなアクセスになるのでこの実験では結局何も分かりません。

どうでもいいことですが
>>A+i*N*N+j*64+k
はA+i*N*64+j*64+kですね。
86の例では。

>>93
じゃあたとえばA[i][j][k]みたいな多次元配列なら、j，kは2のべき乗のほうがはやかったりするのですか？

>>98
>87

>>98
速いかどうかは環境によりますから実験してみるしかないでしょう。
私が書いたのはA[i][j][k]の場合ならiを２のべき乗にしてもシフトやかけ算と関係ない、というだけです。
まあiについてはわざわざ２のべき乗にしてもサイズが大きくなるだけ損だとは思います。

てかさ、そんな枝葉の事よりもっと重要な評価関数とか探索ルーチンとか考えてるの？ ＞ALL

探索ルーチンは多少悪くてもハードウェアの進歩でどうでもよくなる

問題は評価関数だよ
評価関数が悪ければいくら探索が速くても休むに似たりだ

じゃあ、良い評価関数とは何か？
それはプロの手を良いと感じ、ヘボの手を悪いと感じる評価関数
少なくとも、現状で手に入る簡単な指標としてはそうだ

つまりプロの棋譜を教師とする自己学習を本旨としたボナンザで
将棋プログラムは最終形を迎えたわけだ

もう将棋プログラムに費やして得るものは何もないよ
ボナンザで将棋プログラムは終わった

バカｷﾀｺﾚ!!

>>102
全然終わってないでしょう。
実際ボナンザはすぐ切れ筋に陥ってしまうようなまだまだ弱いプログラムだし。
自己学習というのも大きな誤解。
人間が決めたパラメータを最適化しているだけ。

>102
コンピュータ将棋ソフトを作ってる、あるいは作ろうとしている人間は
例え内心ではそういう事を思っていたとしても決して口にできないな。
口に出したら、じゃトッププロに勝てるものを作ってみせろと
言われるに決まっているから。

本気でそう思っていたら何も言わずに黙って手を引くしかないだろうが、
やっぱり本当にその手法で可能かどうか実地にやってみたくなるのが
人情ってもんだろ。

幕を引くのは自分でありたいって事だ。

逆に評価関数簡素化してパワーでプロ棋士を押し切るなんともｼｮﾎﾞｰﾝな結果になりそうな悪寒

>106
それは俺も心配。
ただ、シンプルだけどそこそこ正確な評価関数ってなんだろ？とは思うが。

>>107
敵玉が詰み = +1点
自玉が詰み = -1点
持将棋成立 = 0点
先手千日手 = 0点
後手千日手 = 0点

あとはパワーでｗ

>108
ごめん、俺には無理。

>72
ttp://www.fun.ac.jp/~kishi/pdf_file/kishi_mueller_is2004.pdf
# 久々に読んだけど書けるかな?

なあ、今からC＋＋やJavaで指し将棋ソフト作っても
あんまり変わり映えしなさそうだから、Lispで
書いてみようかと思うんだがオマイラどう思う？

Lispプログラミングを勉強がてらたがｗ。

つ http://hotwired.goo.ne.jp/news/technology/story/20060316301.html

間違えた ＿|￣|○
http://lyrical.bugyo.tk/

>>111
Lispではないけど関数型言語を使っているらしいチームが
5月の選手権には何度か参加登録してる
たしかOCamlだったか…
楽しみにしてると参加取り消しだったりした
実際に出場したことがあるかは不明

>>111
別に利用するプログラミング言語で変わり映えをつけようとしなくてもいいと思うが。
弱ければ単なる色物で終わってしまう。

>115
単なる色物にすらならない（ただの弱いソフト）よりはマシだろ？
それにあんまり良く分かってないが、アルゴリズム的にも面白い
事ができるかも知れん。Lispを相当深く理解して使えたらだけど。

弱けりゃ何で作っても一緒

ICOTの囲碁はESPっていう逐次論理型言語を使ってたみたいねー
http://www.icot.or.jp/ARCHIVE/Museum/IFS/abst/052-J.html
EPSってwikipediaによるとPrologにオブジェクト指向を取り入れたものらしいけど

>弱けりゃ何で作っても一緒
　強くないと、何か言っても説得力無いしねｗ
　強い＝優れたアルゴリズム

>>111
>Lispで書いてみようかと思うんだがオマイラどう思う？
　LISPでどういうやり方でやるかわからんけど、
　探索より知識の積み重ねで指そうと考えてるなら、


　ここのHIT将棋が取り組んでいる
http://homepage1.nifty.com/ta_ito/HIT/top.htm
　ここの研究室は、プロ棋士がどういう風に手を絞っているからを調べてて、

　はじめから２，３手に絞って、その先を確認して指すタイプとか、
　10手とかたくさんの手を検討して指すタイプとか、
　けっこういろいろなタイプに分かれるらしい。
http://www.webspace-jp.com/~mozu/mozuiro/moromoro/ninchi.html

Freisinn :: 一挙公開
http://yashiromann.sakura.ne.jp/diary/blosxom.cgi/tron/btron/20060831bappl.htm

MPLAYER
　MPEG動画プレーヤーです。MPEG-1 および MPEG-2 に対応しています。

レコードエディタ
　任意のレコードを編集できる高機能なバイナリエディタです。

SmartPoint
　プレゼンテーション用のツールです。

アプリケーション一覧/登録/更新
　BTRONアプリケーションの登録作業を柔軟かつ楽に行うためのツール群です。

データボックス編集
　データボックスレコードをグラフィカルに編集するためのアプリケーションです。

>120
誤爆かあるいはただの宣伝かい？

プロ棋士に勝つ方法

1.詰めろアルゴリズムを詰める。
2.必死アルゴリズムを詰める。
3.終盤の速度計算をする。
4.定跡データベースを詰める。
5.乱戦模様に誘導する。
6.NECのSX-8iを借りる。

モデルはタイガーウッズ。序盤即終盤。

「詰める」を「詰みを読み切る」と思って意味がわからんかった

>122
SX-8iってベクトル機だよ？
今主流のコンピュータ将棋が高速に動くとは思えないが？

あと、マルチポストうぜぇ。

>122
それから、「乱戦模様」の「定跡」を作ろうって言ってる？
がんばってね。

>122はあちこちにマルチポストしてる愉快犯だから相手にしないように。

http://c-au.2ch.net/test/-/mass/1183191945/i#b
http://c-au.2ch.net/test/-/soc/1152718893/i

必至だなｗ

既に詰んでますｗ

>122はPonanzaというソフトの作者の保本さんです。

チェッカーは解かれたそうだ。
http://en.wikipedia.org/wiki/Draughts
http://www.nature.com/news/2007/070716/full/070716-13.html
http://www.nikkei.co.jp/news/shakai/20070720STXKE037619072007.html
駒取り合う「チェッカー」を完全解明・カナダの研究チーム
【ワシントン19日共同】市松模様の盤上で黒と赤などの丸い駒を斜めに動かし、
相手の駒を飛び越して取り合うゲーム「チェッカー」を完全解明したと、
カナダ・アルバータ大の研究チームが米科学誌サイエンス（電子版）に19日発表した。
平均50台のコンピューターを18年動かし続けて得た結論は、最善手で差し続ければ必ず引き分けになるというもの。
決して負けない対戦ソフトが可能になったが、より複雑なチェスや将棋の完全解明にはかなり時間がかかりそうだ。
チームはチェッカーの世界チャンピオンに勝つプログラムを作る目的で、1989年にチェッカーの解明に着手。
全部で５兆の１億倍通りもある駒の置き方を踏まえてシミュレーションを繰り返した結果、
お互いにミスをしなければ相手の駒が取れなくなる「引き分け」に終わることを突き止めた。(07:00)

俺今日>>131のニュースを読んで思ったんだけど、将棋は完全解析できないけど人間相手なら無敵という物なら作れるんじゃ？
自然淘汰を取り入れた自己進化するアルゴリズム同士をスーパーコンピューターで戦わせまくれば人間より強い定石を見つけるんじゃないかな？

>132
将棋はチェスやチェッカーと違って終盤でなかなか手の広さが収束しないんだよ。
もちろん取った駒を盤上の好きなところに打てるからだが。

おかげで終了局面からさかのぼって局面をデータベース化するのがとてつもなく難しい。
終盤データベースなしに学習させたところでそれは解全体のほんの一部の実戦例から
学習させる事になるので正しい学習をする（正しい定跡を発見する）かどうか怪しい。

>>131
そんなのは昔から解明されていた。しかし誰も認めなかっただけの話だよ
その記事も当てにならない、科学的に示すには論理的仮説と多面的な反証
があってこそ科学として認められる、その解明とは単なる思い込みの域
にすぎない。つまり１０手先を読んで模擬して解明したのと１８年かけて
解明した悟ったという差にしかすぎないわけだ。

>>134
なにに反応したのか、当たり前のこと並べて楽しいのか？
んな常識的なこといってもつまらんだけ。
コンピュータ将棋が最強なんて考えている乙君が沸いてきそうだ。

>>134
では三色問題も解かれてないと主張するのですね？

>>135-136
あんまりいじめてやるな。134が哀れだろ。

>>132
中学生さんですか？

計算機の速度を考慮する場合と、計算機の速度を度外視する場合は別に考えてね

>>139
誰に対しての発言？
意味がよく分からん。

132に一言いいたかったんじゃね

>>132
>自然淘汰を取り入れた自己進化するアルゴリズム同士をスーパーコンピューターで戦わせまくれば
　まさにGAで対戦させて強い奴を進化させるって話じゃまいか。
　中学生ですか？　は言い過ぎだよ。

　次みたいに名大の人が昔オセロでやってみてる
http://www.phys.cs.is.nagoya-u.ac.jp/~watanabe/swarm/garev.html

>暫定王者にのみ勝てる弱者が現れ、再び戦国の世に戻ってしまうのだ
　なかなか示唆に富んだ結果が得られている。

将棋でやるとなると相当なマシンパワーが必要だな
アルゴリズムを進化させるアルゴリズムも作るのも大変そうだ

>>143
最初は歩だけしか動かせないアルゴリズムや角だけを狂ったように使うアルゴリズムが出てきて面白そうｗ
でも普通の対局できるレベルになるまで何千万世代もかかるだろうね。

いや、進化させるっていうかたまに突然変異を混ぜればいいのか
それが環境に対してダメな進化（退化）だったら淘汰されるだけか

>>142
スパコン同士を戦わせたら何百億円もかかるから採算絶対にあわない。
実現困難な"夢"と非現実的な"夢物語"の間には大きな違いがあるよ。
132はリアルに中学生かもorz

>>142
その結果って公知じゃないのか？
その研究はせいぜい学部生の宿題レポのレベルだし

>146
最近はスパコンを無料で貸してくれるところがあるよ、大学で。
地球シミュレータも有償だが借りられるし、そんなに高くはない。
まあ、ベクター計算機をこういう用途には使いづらいだろうが、
超並列スカラー型なら結構使えるんじゃないかな？

何百億円もかけたら自分で好きなタイプを作れてしまうな。

>146
これは非現実的の範疇には入らないと思うが。
「採算」の事を考えてる時点で現実的じゃん。
非現実的ってのはもっと、今後どんだけ科学が発展しても無理！ってものの事を言わないか？

んなこたーない
>>146のでも非現実的といえる

最強のとか言ってる時点で現実的じゃないような気もするけど。
理論的な最強を目指しているのか？現時点での暫定的な最強を作りたいのか？
前提が定まっていないような

>>151
自分は当面目指すのは後者だと思ってる

人間破ったらそれでいいんだ
まずはコンピュータの頂点を目指す

>>142
リンク先を見た。オマオレ、と思った。
俺も中高生の頃こんな感じで大学入ってから忙しくて中断
した口。でもこの人の学習手法はGAに成ってない。
交差と突然変異が無きゃ駄目だし、実際問題として
純粋な弱肉強食だと、変な局所最適にすぐ陥ってしまう
ので、ヘボい遺伝子も少し残さないといけない。
その加減が難しいんだけど。

>>151
上のチェッカーにも有るように「全探索」してしまえば
間違いなく最強だろ。
NP完全問題の全探索は絶望的に大変だが、チェッカーや
6x6オセロくらいまでなら実現してる。ガンガレ。

>154
「ガンガレ」って誰に言ってるのか知らんが、将棋の全探索は無理だろう？
いくらなんでも現状では。

量子コンピュータが実現するとか、ものすごい理論でも発明？されない限り。

全探索というゴールが存在するという事実は重要じゃないか？
あとはそれにどこまで近付けるか、あるいは到達するか

>>155
量子コンピュータができれば、将棋の必勝解を一瞬で計算できます。
時間など不要です。
なぜなら量子コンピュータは手順という概念を組み立てる方法では計算しないからです。

将棋というルールを因数分解して必勝という答えを導きだす。
その計算された手順を取り出す（現状は取り出せない）。
量子演算は無限の並列計算ですから無限の計算ができることになります。

みなさんも量子コンピュータを応援しましょう。

応援なんかよりアルゴリズム考えろよ

>>157
量子コンピューターでもNP問題を解くのは難しいって何かで読んだ、
チェスなら>>157に書いてあるように完全解析できるだろうけど将棋はどうなんだろう？
そもそも将棋は全探索できる数学的証明がないと分からん。

>>159
チェスは無限に続くかもしれんが、将棋は同一局面3回出たら引き分け

順番からいって次はオセロだろう
いやまぁ自分は量子コンピュータのことよくわかってないんだけどね

単純にいって、駒は8種類で成りを加えて、14通り
合計40枚だが、それを考慮しないことにして
高々配置可能な種類は15の81乗程度

敵味方を忘れた　将棋の可能な配置パターンは29の81乗以下
それすべてに、勝ち負けを設定すれば将棋は完全に溶けた

配置可能なパターンはそれだけでも
次の手番がどっちかとか何回目に出た局面かで勝ち負け引き分け変わるでしょ。

>>164
素人考えだけど、手番はともかく、何回目に出た局面かは
必要ないんじゃないかな？だって最強のもの同士が闘っているのだから、
その局面が出た瞬間に、これは無限ループ＝千日手と解るはずだから。

んぁ〜、あつはなついなぁ〜

手番は2通りしか無いんだし、2通り作ればいいだけだな。

>>165
そういえばそうだった

>>163
それだと一秒間に一兆パターン調べても終わらないいんだがw
何で今更そんな議論を

>>166
そういえばそうだった

>>160
チェスにも同じルールがあるよ、次に完全解析されるゲームはダイヤモンドゲームじゃ無いかと予想
最後まで解けないのは囲碁。

同じ局面が３回というのはルールだろうけど、それを記録できなければ
無限に終わらない罠。記録できてこそ３回一致を判定できる罠。

>>171
囲碁はもう解けてるだろ
先手必勝

>>173
あれ、囲碁って先手の6目（7目？）勝ちって解明されたんだっけか？
教えてクンですまん。

>>174
囲碁も将棋同様に解かれてないよ。
囲碁は人間モンテカルロ法で先手有利のような結果が出てるだけで。
ちなみにオセロでも同様な方法だったら後手有利のような結果が出る。
しかしちゃんと最善'候補'のゲーム木を構築したら引き分けの可能性が高いという結果が出る。

オセロって完璧に全手解明されてなかったっけ？

>>176
オセロ（通常は８ｘ８の事）もまだ解明されてないよ
６ｘ６盤は解かれてるけど

>>177
そうでしたか

8x8は解明したと力説する奴は結構いるんだけどな。
ぽえむ君だから仕方が無いんだけど、

>165の意見は強烈だなぁｗ。

一目、局面を見ただけで千日手（無限ループ）だと分かる？
今まで何回、同じ局面が出てきたか記憶しないで？
最強の者同士が戦ってるってどこから来た仮定？

例え将棋の神様であっても、これまでに現れた局面を
記憶しない限りループにはまってるかどうかは分からんだろ？

久々に笑わせてもらったよ。

>>180
おまえ変だ
完全に勝敗が決まっていたら、勝ちか負けか千日手しかない

>>180
勘違いしてるバカ

>181
意味不明！

全ての局面と試合結果の組データを構築する場合
局面・・・駒の配置と手番の情報だけが必要
結果・・・その局面から全探索した結果（勝ち・負け・千日手）だけが必要

>184
同じ形の局面でもそれが何回目の出現かを区別しないで
どうやって千日手だと判定するんだ？？？

もしかして特定の形をした局面が千日手になるか
ならないかはその形から自動的に決まると思ってる？

>>185
勝ちでも負けでもない局面はあいこだろが

>>185
だからそれは別の問題なんだって。
そっちの話題に関してはもちろん思ってないよ。

それよりお前ら開発してるのか？

>>180は、こっちで完全無視されたやつじゃないのか?
http://game12.2ch.net/test/read.cgi/bgame/1184085334/


解析中と解析後の区別がついてないから始末が悪い。

>>188
スレは見てるけど最近将棋の開発はしてないなー
ちょっと前は高速化のためにSSE2の勉強やってたけどどんなところに使えるかな

だから特定の局面の勝ち、負け、引き分けを
正確に判定するためにはその局面に至る手順で
区別して扱わない限りそもそも不可能なんだよ。

言葉だけで説明するのは非常に難しいので、
後は"GHI問題"でググるなどして自分で勉強してくれ。

ちなみに特定の局面から全探索する場合、
そこから先の局面は手順により区別されている。
ところが探索の開始局面にその区別がなかったとすると
情報は蓄えられずにどんどん失われて行く。

>>191
おめー頭悪いな

>>180, >>185
どんな探索をしていっても、自分が勝った局面に、どちら側がどう工夫しても
持って行けない局面は、探索ツリーの中で閉じたループ状の構造となる。
ループ状の構造であれば、、局面の数は莫大とはいえ有限なので、
それを辿っていくと同じ局面が必ず繰り返されるので、千日手。
言いたかったのは上記のことで、ツリーの構造を議論するのに、
時系列で追う発想はもはや必要はない、ってこと。

>>191
＞ところが探索の開始局面にその区別がなかったとすると
＞情報は蓄えられずにどんどん失われて行く。
この部分の解説希望
失われて行く情報とは？

>>194
191は頭悪いよ
詰め将棋を解く(勝敗を決定)する事と、
すでに決定されている事の区別が出来ていない

千日手が決定している局面は、そこに至る手順に関係なく千日手なんだよ

>>165で言っている事と>>196は同じ事だ


>最強のもの同士が闘っているのだから、
>その局面が出た瞬間に、これは無限ループ＝千日手と解るはずだから

つまり

1) 探索ツリーを作る段階での議論
2) すでに完成した探索ツリーの構造の議論

がゴッチャになっているのかな？

その点では、>>191 氏にもミスはあるように思うが、
でも「GHI問題」ってのが 1)ではあるんだね
ちょっとググって勉強してみるよ 情報サンクス

>193
千日手になるのは単純な見て分かるループだけじゃない。
大きな流れの中で同一の節（局面）を4回通過するだけで起きる。
千日手にならない手順と容易には区別できない。
局面だけで区別するとゲーム木はツリー構造ではなく
メッシュ構造になるので辿りかたが全く決まらない。
そこら中がループしていて、
ループしていないところとの区別は存在しないんだよ。

>>199
将棋の完全解析は不可能、を主張しているということでOK?

>>199
手順は関係ない
勝ちと負けと引き分けしか無いのだから、局面が与えられればそれは決定するんだよ
探索によって結果が変わるなら、その探索が間違っているだけだ

勝敗が決定する局面では、次の指し手は一つに絞られる

千日手の局面では、一つに絞られないから、確かにメッシュ構造になるんだろう
でも、ループでもメッシュでも、ノードの数は有限だから、やはり千日手は千日手

確かにループになるって書いたのは間違いだったけど、
最初の議題「何度目の局面の情報は必要か」っていう点では、同じ結論になるんじゃないかな？

>200 >201
違う、違う。
その局面に至る手順により区別して（別の物として）
扱わない限り、その局面が勝ち負けか引き分けかを
決定できないと言ってるんだよ。
つまり局面をその現れる順番で展開したゲーム木を作れば良い。

手順に関係なく局面が与えられれば勝ち、負け、引き分けが
決定するはずと言うのが単なる思いこみなんだよ。

>>203は釣りですから無視しましょう

>>201
局面pがあって、その子供がc1,c2のみで、ともにXの負けの(一手詰みの)局面とする。
GHIがない場合、後退解析では
　　c1, c2の局面がXの負けとわかる->c1,c2だけを子供に持つ局面pはXの負けとわかる
だけど、もしGHIがあったら、pに来た時点で経路によっては4回目の同一局面になって、
引き分けになるかもしれない。
連続王手の千日手になってXの勝ちになるかもしれない。
だから、pの局面は結局勝ち負けが一意に定まらないというわけ。

それでも完全解析は理論的には可能で、要するに局面数Nだったのが、
ある局面に至るまでの経由局面を全て考慮しなくてはならないと言う意味で、
最悪の記憶量がO(N!)になるというだけでしょ。
ずいぶん爆発的に増えちゃうとはいえ、どちらの場合にせよ天文学的な局面数なので、
まぁそんなにまじめに考えてもしかたないと思うけど。

>>203
> その局面に至る手順により区別して（別の物として）
> 扱わない限り、その局面が勝ち負けか引き分けかを
> 決定できないと言ってるんだよ。
「区別が必要」という仮定で、手順により区別して
勝ち負けか引き分けかを決定したとするよね?
そうすると完全解析済みになるよね?
後は完全解析済みの結果を参照するだけでよいよね？
再解析の必要は無いよね?
その局面は参照するだけで、勝ち負けか引き分けか決定してるよね？

これは、あなたの主張する「区別が必要」と矛盾するよね?
この矛盾は、仮定が間違っていいたためであり、「区別の不要」
ということになる。
証明終わり。

これ背理法っていうんだけど、問題ある?

>>205
よーく言いたいこと解った！！サンクス！！
後退解析だけでは駄目なんだね　経路が必要なんだね
で、結局、局面だけでは判断できない･･･ってことか
ちょい目から鱗が落ちたよ 漏れの勉強不足を痛感した

例えば、勝ちと判別されている局面があったとして
勝つ手順がわかっていたとしても、
既にその局面が3回現れていたとしたらそこへは指せない
と言うことなんだろ???しかし、この場合、1回目で勝っている

>>207
局面だけ決着しているって
おまえも頭が悪いやつの仲間入りか???
GHI問題というのは、探索の中で現れるだけで実際に指した手ではないんだぞ
一回目で、勝ち負けが決していたら2度目は無いダロが

>>206 氏の意見は、O(N!)とO(N)がゴッチャになっていて、
「局面へ至る手順により区別」と「局面による区別」がすり替わっているように思う
その点において、>>203 氏の意見の方が正しそう

O(N!)からO(N)への射影は、一意には決まらないのじゃないか？
>>205 氏は、それをもって「決定できない」と言っているのだと思うよ。

>206
問題があります。
なぜなら勝ち、負け、引き分けが決定するのは飽くまでそこに至る手順により
区別された局面であり、その区別を外して形だけで同一視した局面は
一般的には決定不能だからです。

GHIとか言ってるやつは、よく聞け!!!

勝ち負け引き分けが分かっていたら、同じ局面は2度現れない
よく考えろ!!

>>210
確認。
完全解析の定義は「すべての局面の勝ち負けか引き分けかを決定すること」。
認識は、あってる?


「局面へ至る手順により区別」して、完全解析する。
完全解析後に、「局面による区別」し、参照する。
問題あるなら何行目か具体的に指摘してくれるか?

>>211
完全解析の定義は?
で、完全解析はできるのできないの？

同じ局面が現れるならそれは千日手である、という点が抜けていた

手順に関係なく完全解析は出来るよ
勝ち負けが決している局面は1度しか訪れないし、2度訪れるなら千日手
ただこれだけだ

二人零和有限確定完全情報ゲームは、
ゲーム理論で扱われるゲームの分類のひとつである
チェス・オセロ・石取りゲーム・囲連星・連珠・五目並べ・三目並べなどが該当し、
偶然に左右されない読みの深さを競う。

概要
これに分類されるゲームの特徴は、理論上は完全な先読みが可能であり、
双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か
引き分けかが決まるという点である。

Wikipedia

>213
分からないかな？
局面の形だけで区別したのでは答えが複数あるんだよ。
どういう手順によりその局面に至ったかにより異なる答えが。

>>213 氏の言う「完全解析」がもし可能であるとすると、O(N!)→O(N)への射影が可能
しかし、後退解析を使って「完全解析」するのは、GHI問題があるために不可能

どうやって「完全解析」するかの、方法論、つまりアルゴリズムの問題を除けば、
確かに>>208, >>209 氏の言うことにも一理あるようで、「完全解析」出来るのかも知れない
もし「完全解析」が可能であるとすれば、>>213 氏に漏れは同意　ここまでが漏れの今の認識

少なくとも、後退解析が持つ問題点と、完全解析が可能かどうかは、分けて議論すべき感じだね

>>218
そんなことは聞いていない。
(1)完全解析の定義はあってるかどうか。
(2)>>206の何行目が間違い。
を

(1)Yes or No
(2)X行目
と簡潔に答えてくれ。

>>208の言う通りだろう

千日手を回避して勝ちがあるなら初めからその手にすればいいし
回避しても価値がないならそのまま千日手を狙うのが最善

>>218の言いたいのはこういうことかな

　現在の局面がある

　この局面からは勝ち筋があるが
　勝ち筋の途中である局面Aを通過する

　よって、局面Aが「すでに3回登場しているのか」
　「そうではないのか」によって違いが生じる

でもその場合局面Aから現在の局面になるのだから
結果は千日手なのだよな

>212
千日手になるためには同じ局面が"4回"現れる必要があるぞ。
2回目が現れたらその途端に千日手になるわけじゃない。

千日手のパラドックス

>>223
頭を使え!!!

>>223
イメージ的に、対局で、詰めろが回避できないと諦めた段階で投了するか、
詰まされるまで指し続けるかの違いかな。

>>209, 212
スマン、「で、結局、局面だけでは判断できない･･･ってことか」は、
後退解析の途中で現れる局面についての話題ってことに読み直してくれ。

しかし完全解析って、後退解析以外にそもそも定義できなそうだから、
正しくは後退解析の実行手順の問題と言い換えるべきか？　これで正しい？

>222
うん、つまりはそういう事。
すでに以前、局面Aを3回通過してれぱ頑張っても千日手にしかならないが、
そうでなければ（2回あるいは1回通過）勝ち筋があるというわけ。

そして局面Aから現在の局面に来たとしても、必ずしもそこに戻るとは限らない。

>>223
神同士が対局してるものとして、
同じ局面が現れる（2回目）って事は、仮に千日手ルールが無ければ3、4、5・・・回目も必ず現れるよね？
んで千日手ルールがあった場合、2回目が現れた時点でその局面は千日手（4回目）なのと同じでしょ？

なんだかプログラマというより数学板みたいな感じですね

>>230
そう。

>>180は、最初こっちでやってて、逃げ出したみたい。
「将棋って数学に似てるの？」
http://game12.2ch.net/test/read.cgi/bgame/1136526660/

こっちでも完全無視。
http://game12.2ch.net/test/read.cgi/bgame/1184085334/

で、ここで叩かれていると。

>>228
ちょっと待って、整理させてくれ

その「戻らない」場合っていうのを
盤面はもちろんなくていいから例示してくれないか


局面Aから現在の局面に来た過程では、
相手方の協力があったから来たわけだよな

つまりこの千日手含みの手順に入ったからには
相手としても「回避すれば負ける」という事情が
あったわけで、するとやはり千日手が結果の気が
するのだけど

うーん、どこで話が噛み合わなくなってるか何となく分かってきた。
皆さんは将棋の神様同士が双方最善を尽くす場合の棋譜を考えてるよね。
だから千日手になるのを避けるために特定の局面を通らない事もあると仮定している。
そう考えるとその時点での局面の形から指し手が一意に定まると（少なくとも結果は同じ）。

私はルール上許される全ての局面に勝ち、負け、引き分けのラベルを貼る事を考えている。

そうすると後退解析するしか方法がなくて、すると>205が書いているように
GHI問題を考慮する必要が出てくる。

で、漏れはGHI問題についてググって以下のPDFに辿り着いた
ここの2ページ目だけ読めば、GHI問題については理解した（つもり）
ttp://www.fun.ac.jp/~kishi/pdf_file/kishimoto_gpw2004_paper.pdf

これって詰め将棋のように、手順に基づいて探索ツリー作製していったとき、
サイクル手順に出てくる局面を、「無闇に」不詰として、ハッシュ表に登録することから生じる問題みたい
この「無闇に」ってところが重要で、ホントは2ページ目の局面Aは詰む局面

したがって「完全解析」の是非や、それに何回目の局面の情報が必要か、といった問題じゃなく、
あくまでも探索アルゴリズムの問題だね。最初の議論と、GHI問題の関係は、微妙だよ？

>>231
なるほど、横からだが把握した

この板IDないしな

>>233　釣りはやめろ

>>233
勝ち、負け、引き分けのラベルを貼る＝神同士の対局

>>234
ひとまずその2ページ目は見た
言いたいことはわからないでもないが
それは探索の実装の問題ではないかね

ハッシュが誤作動するとかいう問題と
結論がどうであるかということとは関係ない
もっといいアルゴリズムに替えたらいいだけ

この例でいえばEは「千日手」が結論なわけで
何も不明解さはないだろう

連続王手の千日手はまた別にして。

>>238は間違えた。「先手勝ち」な。

悪い、いろいろ間違えた。
>>238で俺が言いたかったことは>>234が言ってたな。

>233
GHI問題は、必ずしも「後退解析」（←これって勝ち筋から手を逆算していくことですよね？）の問題じゃないみたい

手順を追ってツリーを構築していく際に、ある経路では、千日手のように”みえる”局面が、
別の局面では勝ち筋に必要な局面ということ　もちろん探索の途中で、うっかり千日手と
登録してしまったところに問題があるのであって、本当は、当然詰む局面

そもそも局面をハッシュしなければ、こういった問題は生じない
ハッシュするにしても、なんらかの形で辿った経路を情報として残せば、問題ない
また、図1で最初にA→Cと探索すれば、最初からこんな問題は生じない

とりあえずGUI問題について語るには、上のPDFの2ページ目を読もうよ
さっきから漏れも色々考えているのだが　この論文の2ページ目以上に、簡単にGHI問題を説明するのは無理ぽ

>237
初手からの神同士の対局と任意、それも手順を含めた
任意の局面からのそれをごっちゃにしてない？

>>242
解析中と解析後はちゃんと区別しろよな
解析後に同一局面が出てくるなら引き分け、そうでなければ同一局面は出てこない

>>242
してないよ

神様同士の対局というのは、完全なる「次の一手」マシンのことだろ

完全なる「次の一手」マシンというのは、どんな局面を与えられても
勝ち筋があればそれを指し、なければ千日手に持ちこめる順を指し、
それもなければ何か指すというようなものだと思う

このようなマシンを作成することと、すべての局面の勝ち負けがわかる
完全な一覧表を作ることは等価だよ

マシン作成→与えられた局面からマシンに一人将棋をさせる→その勝ち負け

一覧表作成→有効手の中から、移行後の局面が「勝ち」であるものを
（なければ「千日手」を）さがす→それが次の一手

現時点での漏れの結論

1) 完全な後退解析が出来れば、
局面だけで勝ち・負け・千日手が解る（→完全解析）

2) 現実のアルゴリズム（これは後退解析でない）で
ツリー構造を作るには、ハッシュ表を使うことが多い

3) むやみにループする局面を千日手としてハッシュ表に登録していくと、
本来の勝ち筋を千日手と間違える問題が生じる(GHI問題)

4) 上記問題を回避するには、ハッシュ表に、千日手と判断するに
至った経路を登録して、局面だけでなく経路を区別する必要がある

5) 4)の事情があるために、「局面だけでは勝ち負けは決まらない」という
誤解が生じている

うん、それだ
今>>246がいいこと言った

それじゃあ任意の局面が与えられてそこから次の一手を決定する時、
そこまでどんな局面(経路)を辿って来たかについてどんな仮定を置いて
決めるんだい？

どんな経路を辿って来たとしても同じだと言うんならその根拠は？

「後退解析」をよくわかってないんだけど何かいい資料無い？

ひとり何役やってるの？
まあ、役者不足、ってやつだよね。

最低３〜４人は居そうだけど

>>248
次の一手問題なら経緯は調べないだろが
勝ち負けの判定ならその局面へくる前に勝敗か引き分けが決まっている

>>248
いや別に

その「完全なる次の一手全集」を見ながら
バカみたいに指していくだけでいい

もしその局面からは千日手が最善なのであれば
全集には千日手になる手が書いてある
それを指せば、もし一回目や二回目なら
また同じ局面に戻ってくるわけだし
三回目なら、千日手になる

>>251
俺、俺より賢い奴、俺と同じくらいの奴、変なことを言う奴
の少なくとも４人はいると俺は思ってる

あと、見てる奴や１レスくらいしかしてない奴が多数

>>248
不完全な指し手が指したところから、勝敗を判定するなら
千日手は考慮しなければならない
データベースは使えない

>>248
すでに>>206で、「区別の不要」と証明されているんじゃないの？
否定できるなら、してみれば？
まず、>>220の形式で答えるのかな。

>>256
横からだけど、ちょっと待って

棋譜は有限だから、「指し手履歴込みの局面」も有限
それらをすべて列挙して勝ち負けを調べればよい

で、「同じ局面でも、指し手履歴の内容によって結論が異なる」
という現象はあるのかないのか

そこが本当の焦点なんじゃないのかと思う

>>254
>>185-248辺りでどのレスが誰？
自分のレスがどんな奴だと思われてるかちょっと気になる

>>257
「同じ局面でも、指し手履歴の内容によって結論が異なる」 と「区別の必要」の違いは?

とにかく、他にどんな問題があっても、単純に>>206を否定できなければ
「区別の不要」という結論は覆らないでしょう。

>256
区別が不要だといったいどこで証明されているんだ？
206の主張はトートロジーだよ。
区別が不要だから不要だと言ってるに過ぎない。

>246の1も未証明な仮定だと思うぞ。

>>259
えー俺は釣られてるのかな
それとも俺がバカなのか

> その局面は参照するだけで、勝ち負けか引き分けか決定してるよね？

具体的にはここだろう

今は「区別の必要がある」という仮定で話をしているのだろ？
そして、手順を区別した上で勝ち負け表を作ったのだろ？

つまり、同じ局面でも手順が違うものは別物として勝ち負けを
判定したのだろ？

それを整理して、局面だけから勝ち負けがわかるようにするのだろ？

でも、その整理ができるという保証がないよ
「区別の必要がある」という仮定のもとでは

つまり、区別ありの表から区別なしの表を作るときに、
もし区別ありの表において、ひとつの局面が
手順によって勝ちだったり負けだったり結論が異なっていたら、
区別なしの表にまとめることはできないじゃないか

そして、「区別の必要がある」という仮定はまさに
手順によって結論が異なるかもしれないという意味だ

だからこれは「他の問題」なんかじゃなくて本質的な問題だよ

>>261
あ、先に言われた
同意

あー、ようやく分かってくれる人が居た。

>>261
> つまり、区別ありの表から区別なしの表を作るときに、
「区別ありの表」とか、「区別なしの表」なんていらない。
単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
完全解析とは、その一つの表を埋めて、完成させること。
解析後は、「局面情報と手番」から「結果」を参照するだけ。


>でも、その整理ができるという保証がないよ
後で整理する作業は発生しない。
全く問題にならない。
よって、>>206の否定にはならない。

反論をお待ちしています。

>>264
おまいさん釣りだろう
議論ごっこなら付き合わないぞ

> 「区別ありの表」とか、「区別なしの表」なんていらない。
> 単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
> 完全解析とは、その一つの表を埋めて、完成させること。

> 全く問題にならない。

これらは>>206の論証の結果として得られるものだろう
それを論証の過程で使うのは「結論先取の詭弁」という詭弁

>>264
＞「区別が必要」という仮定で、手順により区別して
＞勝ち負けか引き分けかを決定したとするよね?

＞「区別ありの表」とか、「区別なしの表」なんていらない。
まず仮定をぶち壊してるけどこれOKなの？

>>261
おまえが言っているのは、完全解析が不可能、ということじゃないか?
完全解析は「すべての局面の勝ち負けか引き分けかを決定すること」。
つまり、表を正しく完成させるということだぞ？

>264
「完全解析とは、そのひとつの表を埋めて、完成させる事」
と言うそれが可能だと言う保証がどこにも無いんだよ。

後で整理する作業が必要ないと言うならそれを作る手順は？

>>266
> ＞区別ありの表」とか、「区別なしの表」なんていらない。
> まず仮定をぶち壊してるけどこれOKなの？
言葉が、足りませんでしたか。
完全解析時の作業用の表は、たくさん必要です。

完全解析を行った結果出力として、
>単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
という表があればよい。
ということです。
完全解析ができるということは、この表を得ることができるということです。

反論をお待ちしています。

>>267
いや、いま問題になっているのはそうじゃないよ

将棋のルールは、一見、局面（駒の配置と手番）だけでは
勝ち負けが確定しないように見えるじゃんか
同じ手でも千日手になる場合とそうでない場合があるからね

つまり、将棋において状態とは、駒の配置と手番だけではなくて
「局面の出現回数の履歴」も含めたものでなければならない

そう考えられるわけだよ。素朴には。


でも、もちろん感覚的には、そんなことはなくて、履歴などなくても
局面（駒の配置と手番）だけで判断がつくように思える

その感覚が正しいかどうかがいま問題になっているのだよ
将棋というゲームの状態変数として「駒の配置と手番」だけで
十分なのかどうかと

ルールを素朴に読んだだけでは、不十分に思えてしまうわけで

>>269
>>270

>>268
「将棋の完全解析は不可能」を主張しているわけだ。
これが不可能なら確かに>>206は成り立たないね。

でも、基本的に>>217にもある通り「可能」が、共通認識なんだけど。

つまり、あなたが「将棋の完全解析は不可能」を証明できなければ、
>>206を否定する必要がある。

がんばってくれ。

あはは。千日手模様。
>>268、>>270、>>271の最善手は、「千日手」に持ち込むことか。

>>272
横からだけどおまいさんの言う「完全解析」っていうのは
あくまで「駒の配置と手番」だけを状態変数としたものだろう

たとえば、三山崩しにおいて、ルールを読んだだけでは
状態変数として「１の山の個数」「２の山の個数」「３の山の個数」
という３つの状態変数が必要に思える

でも実際にはこんなにいらなくて、それらのXORだけあれば
勝ち負けが判定できる

このように状態変数を減らすことが、将棋でもできるかどうか
それが論点だよ

>267 >269
完全解析の定義を勝手に自己流に狭く定義しないでくれ。
その定義での完全解析ができるという保証は無いだろ？

実際に可能なのは手順込みの局面にラベルを貼る事。

>>270
完全解析の定義と、それが可能かどうかを、まず、答えてください。
ここの立場をはっきりしないとお話にならない。
いいですか？
はっきり明記してくださいよ？

>>272
＞二人零和有限確定完全情報ゲーム
「完全情報」ってのは手順の情報も含むんだが
君はこの情報を欠落させても欠落させない場合と等価な事を証明する必要がある

>>273
レッテル貼りの詭弁

>>272
共通認識というか定理だろう

将棋のルールは駒の配置と手番とそれらの履歴とで
記述されているわけだから、当然「区別ありの表」は
作れるわけだよ

そこから「履歴」を消してもWell-Definedになる、
というのは自明なことではないと思うよ

>>277
>>206

>>279
そのアンカじゃループしてるよ
何か別の事言ってよ

>>274
>>259

>206の言ってる事はずっと以前からループしてるんだよ。
区別は必要ないから区別しなくて良いってずーっと。

>>259
>>261

あー、疲れた。
この議論だけで徹夜しちまったよ。

反論が無くなったようだしとりあえず寝るか
何かあればまた今夜にでも参加するよ
みんなお疲れ

>>284
俺もだ
土曜出勤なのにな

>>276に長レスを書いてたんだけどバカらしくなってきた

ああやって「これにレスできないとバカだ」みたいな言い方をするのは
釣り師が一般人を議論に引きずり込むときの常套手段なんだよなあ

>>278、>>280
>>276
よろしく。

>>276
可能

あ、定義もか
誰か出してなかったっけ

>>248、>>278、>>280
>>269にも回答よろ。

皆さん、お疲れさま。
付き合ってくれてアリガトン。

「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ

自分も寝る
おやすみ

なんか急に伸びすぎﾜﾛﾀｗｗｗｗ

俺は松原先生の本を昔図書館で何冊か読んだ程度で
ゲームの数学は全然わからないからあれだけど
記号や用語などもたぶんでたらめ

状態変数X1、X2、…、Xnはそれぞれ
有限集合A1、A2、…、Anに値をとる変数として

直積A := A1×A2×…×Anの要素 X = (X1, X2, …, Xn) を
このゲームの状態という

Aから、Aの部分集合全体P(A)への写像 M がある（可能な着手）

Aから集合R:={勝ち, 負け, 引き分け, それ以外}への写像Vがある

Aの元X0があり、これを初期状態という

k手からなる手順Fとは、Aのk乗の元 ( X1, X2, …, Xk ) であって
　X1 は M(X0) の元
　Xi は M(X[i-1]) の元　（i = 1, 2, …）
をみたすもの

Aの元Xが到達可能であるとは、あるkが存在して、Xk=Xとなる
k手からなる手順が存在すること

到達可能な元の全体からなるAの部分集合をA'とする

ゲームが添え数づけ可能とは、A'からN以下の自然数への写像
Sがあって、すべてのA'の元XとすべてのM(X)の元Yとに対して
　S(X0) = 0
　S(Y) = S(X) + 1
となること

以下添え数づけ可能なゲームを考える
将棋は「局面の出現回数の総和」で添え数づけ可能

k手からなる手順が終わる手順であるとはV(Xk)が勝ち、負け、
引き分けのいずれかであること

あるKが存在して、k>Kのときk手からなる手順は存在しない

完全解析WとはA'からRへの写像で次をみたすもの

　V(X) が勝ち、負け、引き分けのいずれかのときは
　W(X) = V(X)

　S(X)が偶数で、かつ、集合M(X)のSによる値域S(M(X))が
　勝ち、負け、引き分けだけからなるとき、それが
　　　・勝ちを含むならば、W(X)は勝ち
　　　・勝ちを含まず引き分けを含むならば、W(X)は引き分け
　　　・それ以外はW(X)は負け

　S(X)が奇数で、かつ、集合M(X)のSによる値域S(M(X))が
　勝ち、負け、引き分けだけからなるとき、それが
　　　・負けを含むならば、W(X)は負け
　　　・負けを含まず引き分けを含むならば、W(X)は引き分け
　　　・それ以外はW(X)は勝ち

次が成り立つとき完全解析が存在する（十分）

　A'の元Xについて、Xは次のいずれかを満たす
　　　・M(X)は空ではない
　　　・V(X)は勝ち、負け、引き分けのいずれか

証明はS(X)の有限性による

>>206はごちゃごちゃ言いすぎ。
完全解析を「すべての局面の勝ち負けか引き分けかを決定すること」と
手順を含まずに定義したんだから、解析後に手順が関係ないのは、自明。
この定義で、解析後に手順がどうのと文句つけるのがアホ。

>>292のように、
>「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
と定義に、手順を入れれば、解析後も手順も関係するが、こんな定義初めて見たよ。

>>295, >>296 打ち込みサンクス！！

それによると、A'は履歴を含んでいるわけではないのだから、
やっぱり「完全解析」の定義は、局面だけであって、履歴は関係ないんだね

上の議論は、将棋固有のルールを反映したものではないけれど、
将棋もまた上の数学の枠内でのものなのでしょう

「M(X)は空ではない」ってのは、例えば両方ともパスするしかないような
状況はありえないって事だよね？更に勝ち・負け・引き分け以外の
終わり方は、将棋ではあり得ないから、やっぱり将棋は局面だけで、結論がでているんだ

途中まで人間が指して、そのあと最強ソフトが指すならデータベースは使えないってことだろ
千日手があるから・・・

全局面をNとしたとき、その局面が何回現れたかを記録した
0から3までの数字列N個分を保持していなければならない

最終的には4のN乗程度の状態を保持しなければ、途中差しは出来ないって事だ

>>297
いやいや、>>292などは既存の常識に疑義を言ってるのだから、
「初めて見る」は非難にはならないよ

>>298
数式に惑わされたらだめだろ
>>295-296は何も新しいこと言ってないぞ

そしてさりげに>>295のAは履歴も含んでるよ
Sは手数とか言ってるしな
履歴を持ってないとVが千日手を判定できない

最後の条件は、勝敗未定ならば有効な手がある
ということ
たとえばもしルールでステールメイトを負けにするのを
忘れていたりすると、
M(X)が空（有効な手がない）で、しかも
勝ち負け引き分けのいずれでもない
という状況が発生するね

>>295, >>296 の論法で完全解析が可能であるというには、
駒の配置に加えて「この局面が何回目か」というパラメータも
ノードの状態変数として加える必要があるということ。
完全な履歴は必要ないが、何回目かは必要となる
これが「局面の出現回数の総和で添え数字づけ可能」の意味と理解した。

だとすると、途中で人間×２からコンピュータ×２に交代するとして、
全ての局面の出現回数を保持していなくても「この局面は何回目です」と
だけ伝えればいいんでないかい？後は事前に完全解析された結果に基づいて、
最強ソフトが「先手の勝ちです」「後手の勝ちです」「引き分けです」
とだけ伝えてオシマイになるはず。少なくとも十分条件としては。

>>301
勝ち負けの決まっている手順の途中に千日手が現れる可能性有り

>>299
将棋というゲームの正しいイメージはこうかもしれないな

N個のマスと、それらをつなぐ線があり
マスのうちいくつかは赤か青に塗ってある

二人が交互にマスに石を置いていく

一つのマスには３個まで石を置ける
４個目の石を置いたら引き分けで終了

赤のマスに石を置いたら先手の勝ち
青のマスに石を置いたら後手の勝ち

ただし直前に相手が置いたマスから
線でつながっているいマスにしか置けない

>>300
だいぶ問題が絞られてきたね。

確かに、Aが履歴を含むのかどうかで、話は全く変わってくる。
Aに出てくるnって何だ？漏れはX1, X2が、例えば各駒の場所の様な変数で、
nが駒やボードに対応するものかと思った。で、その直積であるAは
履歴を含んでいないな、と。それだと千日手の判定が出来ないから、
少なくとも、「この局面が何回目か」という情報をAnとして加えてやれば、
完全解析の対象になる、という意味だと理解したんだが。

そしてある局面が何度でてくるかという情報は、手順から
考えれば何通りでもありそうなものだが、完全解析の対象としてみた場合、
最善の選択をして射影していくのだから、S(X)が決まってくるのかなと
思ったのだけど？

突き詰めると、やっぱり
> 将棋は「局面の出現回数の総和」で添え数づけ可能
のところが漏れには解らない。

うーん、難しいね、Anの意味とS(X)の意味、もし良かったら教えて

>>302
人間が指す以上、必ずしも最善手の連続ではないから、
それまでの履歴に、「完全解析」では出てこない履歴があって、
以後の手順に千日手をもたらす可能性がある。
そのため事前に用意した「完全解析」のテーブルが必ずしも
使えなくなる、でいい？

だとすると、これって結局、GHIの問題とほとんど同じだね
GHIの場合は、探索アルゴリズムが完全でないことに起因、
人間からコンピュータに替わる場合は、それまでの履歴が最善手でないこと
（勝ち負けを見落として、無駄な経路を辿っている）ことが原因
しかしこれらが、将棋の完全解析の可能性を排除するものではない

って、これでいいのかな？

>>304
今から出かけるから手早いけどごめん

X1、…、Xnが駒の場所などの変数で、
A1、…、Anがその値集合

たとえばX1は「先手玉の場所」で
A1は{「1一」、「1二」、…、「9九」}
みたいな感じ

それで、「同一局面４回」のルールを記述するために
（立会人に見せて「引き分けですね」と言ってもらうために）
局面の出現回数も、X1、…、Xnの中で持ってなきゃいけない

俺もおまいさんと多分だいたい同じ考えだよ

でも全部の局面の出現回数を持たなきゃいけないと思ってる

問題図までを指すのは神ならぬ人間なのだから、
神様に言わせれば変な手などもあるはず

そこから神様が引き継いだとして
勝つつもりで指してたら、途中で「その局面は４回目ですよ」
といわれて引き分けになっちゃうかもしれない

そんなわけでXnの中にはすべての（膨大な数の）局面に対して
その出現回数をあらわす変数が含まれてる
ことを俺は想定してた

>>306の続き

S(X)は「今の状況までの初手からの手数」で、
どうせ有限なのだからそんなの持ち出さなくてもいいのだけど
議論を簡単にするために出してみた

千日手がある以上、無限に多くの手数は指せない
だから手数の多いものから逆にさかのぼって
2000手以上は解明済み…　1000手以上は解明済み…
などとすることができる


>>305
たとえば簡単な状況で、自玉は必至、相手玉には
３種類の詰みが見えてるとする

ここで、もしその詰み手順の途中の局面が
３回出現済みだったら、自分は相手玉を詰めれない

だから千日手引き分けになる

もちろんそうでなければ勝ちになる
これは履歴が結論に影響を与えてるんじゃないかな

>>306
なるほど「局面の出現回数の総和」って「全ての(膨大な数の)局面に対してその出現回数」
っていう意味にも読めるね。確かにこれを全て保持したとしても、局面の数が有限であり、
千日手ルールで頭が押さえられているから、それを状態変数とみたてても、取る値は
高々有限集合になって、>>295 の条件を満たす

人間から神様に交代する場合は、確かに全部保持している必要があるだろうね。
先にも書いたように、勝ちの見落としがあるから、GHI問題と同じ現象が生じる。

で、問題なのは「将棋が完全解析されるには、状態変数として、その局面の出現回数だけで
良いのか、それとも全ての局面についての出現回数が必要なのか？」ってところに絞られてきた。
>>296 氏がさらりと書いた、『将棋は「局面の出現回数の総和」で添え数づけ可能』って
いう命題、この証明を載せた文献とかが解れば、それ見てはっきりするんだが

今から出かけるってことだけど、また暇な時に相手してね、サンクス

ところで、完全解析って、すべての局面の「勝ち」「負け」「引き分け」の
他に、「何回間違うと状態が変わるか」って情報いらないの？

対局は、必ず「詰み」まで指すものする。

神Aと神Bが対局して、神Aが先手。先手必勝と分かっている場合、神Aは単に「勝ち」を
選んでいけばいいが、「負け」しか選べない神Bはどんな情報を基にたくさんの「負け」の
中から手を選ぶのかな？

また、形勢差がついている局面から「人間vs神」が指し継ぎ、神が神が判断して形勢不利側を持つ。
このとき神は、差を詰めなければいけない訳だが、どんな情報を基に手を選ぶのかな？

よく考えたら、その局面の出現回数だけ保持していたとすると、
状態が遷移したとき、次の状態が何回目かなんて解りっこない

したがって、あるノードの千日手判定はできるが、そこから一つ前の手順に
後退解析することすら不可能になってしまう。なぜなら、ノードは
その局面の出現回数しか保持していないため、

局面A(1回目) → 局面B(4回目) → 千日手で引き分け

といったツリー構造があれば、

局面A(1回目) → 局面B(1回目)
局面A(1回目) → 局面B(2回目)
局面A(1回目) → 局面B(3回目)

というツリー構造も必ず存在するわけだから。したがって、全ての局面に
ついての出現回数がないと、そもそも完全解析の際に千日手に至る
手順を落としていくことが全く不可能になってしまう。

結論は「棋譜としての履歴は必要ないが、全ての局面についての
出現回数を保持する必要がある」ってことになりそうだ。

(つづき)
でも全ての局面について出現回数を保持するのは、理論的には簡単であっても、
現実的にはまず不可能。で、結局は順番はともかくどういった局面がこれまでに
出てきたか、その回数と共に保持していくことになる（これは実装上の問題であって、
理論的には全ての局面についての出現回数保持と同じ）。

最後の問題は、なぜ全ての局面の出現回数を保持しておけば、
将棋が添え数づけ可能になるかってことだ。>>296 の後半にある
「次が成り立つとき･･･」以下を証明なしに受け入れるとしても、
ここが争点として残る。でないと「以下添え数づけ可能なゲームを考える」
という前提から崩れてしまう

松原先生の本には、この辺の理論は載っているのかな？

>309
それを考慮するためには同じ「勝ち」「負け」「引き分け」の結論でも
どんな結果が「勝ち」 or 「負け」側にとってより良いとされる手なのか
その価値基準を事前に定義しておく必要があるよ。

つまり「勝ち」「負け」が既に分かっている局面で、形勢差はどう定義
されるべきなのか？

>>309
うーん完全解析の立場からいえば、その時は神様が「負けました」って
頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
したがってその問題は、完全解析の枠内では無いと思うぞ
実際のプログラムを作る場合には、非常に重要になるには違いないが

余談だけど、プロ棋士も、負けのときに形を作って投げるよね

>>313
> うーん完全解析の立場からいえば、その時は神様が「負けました」って
> 頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
これって、笑い話だよね？
結果は分かっているから「いきなり投了」ということで、実際は、指せば指せるよね？
指せないとなると、それはそれで変。

>>309
囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？

>>315
>囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
相手玉を詰ませば勝ち。

>315
詰め将棋に準じて考えれば勝つ側はなるべく短い手数で勝つ手を選び
負ける側はなるべく長い手数で負ける手を選ぶべきなのだろうが、
結論が引き分けの時は？？？

また手数が同じならすべての手順は価値が同じなのか？

私には良く分からない。

>>314
笑い話かどうかともかく、相手のミスをどれだけ仮定するかは、実際の将棋対極では
非常に重要な要素に思うぞ、プログラム開発に限らず。いわゆるハメ手ってやつね。
相手がヘボなら、ハメ手を使って早々に対極を終わらせるだろうし、相手が上手ければ
ハメ手を見透かされて逆に咎められるだろうから、そんな手は使わないだろう。

ハメ手は、素人相手の、相手のミスを前提とした手法だが、プロでも形勢が悪いときは
それに近いことをするようだ。たとえば米長さんの本に、状況がこちらに不利であると、
ギャンブルっぽい手をあえて選ぶと書いてあった。

神はどう相手にミスを期待して、手を選ぶのか。
神が神でいられるのは、初期局面だけなのだろうか・・・

子ノードの勝ち手順の多寡かなぁ・・・
でも手順は少なくても簡明な勝ちもあるだろうし・・・

そうか
この議論は>>162-163に対する>>164のレスから始まってるのか

>321
そう。そして私が>165の意見に対してキツイ事を書いて
これだけ燃え上がってしまった。

今思えば、彼が考えていた前提（神様同士が初手から対局したと仮定）が
分からなかったとは言え、失礼な書き方をしてしまった。

>165さん　
今更ですが済みません。ゴメンナサイ！

>>317
昔、ちょっとGAをやったとき、生き残り戦略はそんな感じにしてた。
引き分けの時、手数が同じ時は、駒得している手数が長いほうが有利としてた。

くどいようだけど、最後に一言だけ言わせて。

既存のゲームの理論を用いて、将棋の完全解析可能性を証明するには、
将棋が添え数づけ可能であることを示す必要があるのだろう。そして局面に、
全ての局面についての出現回数を保持すれば、それが添え数づけ可能になるようだ

しかし、それは「将棋が完全解析可能か」という命題には答えても、
我々が議論してきた問題とは微妙にずれているような気がする。
我々は「将棋を完全解析するのに、局面の出現回数（＝履歴）を保持する必要があるのか？」
という問題を議論してきたはず。これは「将棋は完全解析可能か？」とは違う。

「局面だけで完全解析が出来るか？」という命題は、>>296の理論にもとづいて
行おうとする限りにおいては、千日手の判定ができないため>>300 氏の言っている理由により
証明出来ない。しかしこれは、他の理論で証明することまでも不可能であると言っている訳ではない。

もし局面だけで完全解析が可能だとすると、少なくとも出現回数付きの完全解析から、
一意に射影できるはず。なぜなら後者は前者に情報を追加したものだから。
もし前者で完全解析が可能であるなら、追加した情報（＝局面の出現回数）は
余分な情報であって、後から射影作業によって取り除ける。

（つづき）
とりあえず「局面の出現回数つきのノードで考えると、完全解析が可能」を認めるとしようや。
上の「局面の出現回数」は、そのノードの出現回数だけではなくて、全ての局面の出現回数ね。
ここで、次の問題を考えてみる。

（＊）出現回数つきの状態で考えて、完全解析した状態ツリーを得たとする
このツリーに含まれる状態のうち、出現回数の項目だけ違っていて駒の配置が
同じものは、同じ結果（勝敗および千日手）がマークされているのか？

ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、
千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは
前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの
状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、
回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、
出現回数の情報から明らか。

（つづき）
何が言いたいかというと…

状態図にループ構造があると、数学的に完全解析の存在の証明が非常に難しそうだ。
で、状態変数に、全ての局面についての出現回数を保持するのは、そのループ構造を
千日手に至るまでの手順で展開し（添え数づけ可能にし）、数学で知られている
既存の完全解析の理論に乗っけるための便宜的な手法に過ぎないんじゃないかと。

もし（＊）が満たされれば、勝ち負けの情報を一意に保ったまま、折りたたんで、
局面だけの完全解析に移行できるように思うのさ。折りたたむと、当然ツリーから
ネットワーク構造（ループ含む）となる。

この段階で「局面だけだと、途中の千日手を経由しているかも」と議論するのは不要。
なぜなら、もともと出現回数つきのツリーから折りたたんでいるんで、先に述べた
理由から、考える必要がない。そして勝ち負けがつく局面（ノード）以外は、全て千日手の
局面のはず。当然、千日手の局面は千日手の局面で、閉じたネットワークを作る。
勝ち負けが決定したノードが千日手に繋がってないんだから。もはや勝敗・千日手とも
出現回数の差異によって、その間のツリー・ネットワークの交叉が変化しないのは明らか。
これはあくまでも、（＊）の前提が満たされた場合の話ね。

でだ、（＊）の問題について、誰か解るヤシはおらんか？これが鍵になる気がする。
何らかの簡単な論理で言及できそうにも思うのだが？

>>324-326

(*)については「出現回数の項目だけ違っていて駒の配置が同じもので、
結果が異なることはある」でしょ。

それも「しばしば経験する」からこそ、みんな困っていて、
transposition tableにやむを得ず経路を入れなくちゃいけないわけで。

>>327
きっとプロの方すね、了解しました
これで漏れの中では解決
サンクス！！

>>327
それGHI問題じゃないの？

>>327
反例を棋譜で示せる？

>>329
GHI問題だよ。

GHI問題は「駒の配置が同じなのに、経路によってその局面の
勝ち負けのラベル付けを変えなければならないことがある」ということだよ。
まさに325の(*)の話でしょ。

325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。

>>331
だとすると、GHI問題は、必ずしも探索アルゴリズムの問題とは限らなくて、
完全な探索を行ったとしても、局面から以前の局面の出現回数を取り除いたことに
起因して起こる、より本質的な問題だということになるのですね

上の方に出てきたPDFの説明では、この辺りがハッキリしない
それとも、そういった問題を総称して「GHI問題」っていうのが普通なんですか？

>>331
＞ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、
＞千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは
＞前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの
＞状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、
＞回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、
＞出現回数の情報から明らか。
ここ読んだ？
ここが間違ってるの？

>>333
漏れが意図したのは、探索アルゴリズムの問題による、見かけ状のGHI問題
PDFの2ページ目での説明では、こっちがメインだった
>>332 で書いたように、 完全な探索を行った上でもGHIが生じるのであれば
そっちのGHIは>>325 で書いたGHIには含まれないと解釈してくれ。
少なくとも、漏れが書いた意図としてはそう。

>>330
岸本さんに言えば出てくるかもしれないとは思うけど、自分では持ってないなぁ。
例えば234の論文の図3「続詰むや詰まざるや」42番が、
GHIを考えなければ間違えちゃうわけだから、
その証明木の中のどこかに(*)が満たされない部分があるということでしょ。

>>332
何かの探索アルゴリズムに起因した問題ではないよ。
「同一駒割の局面が必ずしも同じ局面としては扱えない」という問題の総称が
GHI問題、ということでしょう。

(*)の反例は>>307の後半？

自分も状態変数には出現回数が必要だと思ってるけど
不要だっていう意見の人まだ居る？

>>324
すまん。

命題：「○○は△△△である」
→真 or 偽

の形で整理してくれないか？
問題がいくつあるのか、結論がなんなのか、結論の出ているもの、出ていないものがよく分からん。

>>337
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回目ではない、というのは、
前提条件を崩しているので議論の余地はないのでは？

>>339
一見すると、千日手のループであっても、入る場所が異なると
千日手と判定を下すタイミングが異なってくる。
したがって、ある手順では千日手のループの一部であっても、
別の手順で別の入り口から入ると、それが勝ち筋に必要な手順の一部となる。
いままでの議論を注意ぶかく読んで、 >>234 のPDFを見たらたぶん
そういう結論に至ると思うぞ。

>>339
あと、「最善を尽くす」ために、今すべての状態遷移についての
ツリーを作ろうとしていることも忘れないでくれ　ツリーの一本一本は
必ずしも「最善」に絞られて作製しなくてはならないわけではない

簡単のため将棋ではなく、>>234 のPDFの図1で考える
二度同じ局面が出てきた場合に千日手(引き分け)とするルールを考える
まず最初に、すべての局面の出現回数を含めたツリーを考えるとし、
その出現順序をABCDEFGHの順にならべて、カギ括弧の中に書くとする

あるツリーでは、以下の手順で千日手(今は2手だけど)が成立する

手順1) A[10000000]→B[11000000]→E[11001000]→H[11001001]→E[11002001]

H[11001001]はE[11002001]しか行き先がない。E[11002001]は千日手だから、
後退解析によりH[11001001]は千日手だ。しかし以下のツリーを考えると、

手順2) A[10000000]→C[10100000]→F[10100100]→H[10100101]→E[10101101]→G[10101111]

H[10100101]は明らかに勝ち筋に必要な局面だ。

もしカギ括弧をとっぱらったとすると、手順1)では千日手としか結論づけられない局面Hが、
手順2)では勝ち筋の一部。

したがってGHIがある限り、カギ括弧付きのツリーから、カギ括弧なしへのツリーは、
一意に射影できない。重複した写像のなかから、与えられた局面に対する正解
を選び出すには、結局、なんらかの方法でカギ括弧と同じ情報をツリー検索に
加えないと駄目。これがGHI問題の本質だと漏れは理解している。

>>340>>341>>342は、頭がおかしいんだろ
探索した手と、指された手が区別できていない

どんな指し手にも対応できるように、
すべてを検索してしまえって話をしているのだから、
区別する必要はないように思うぞ？それとも釣りかな？

>>340
じゃあ、言い方を変えます。
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回しかないのは明らかなので、
完全解析後のテーブルとしては、すべての局面(手番込み)の
「先手勝ち」「後手勝ち」「引き分け」の状態のみ持てばよいのでは？
ということです。

>自分も状態変数には出現回数が必要だと思ってるけど
当然のことながら、完全解析中のテーブルとしては必要です。
あなたの書き方は、「どのテーブルに、状態変数が必要か」が、あいまいです。

>>343
探索で考える手順と、実際に指される手順を区別しないと、
千日手の発生状況が異なるから、意味がないっていいたいのか？
それは「カギ括弧無しには一意に射影できない」といっているのと同じだぞ

もちろん実際に指される手順は、括弧付き（括弧の情報を含む）なんだよ。

「括弧無しで議論して、手順1)での探索から、手順2)のHまで千日手と結論づけてはいけない」

といっているんだよ。
おまいさんは、カギ括弧無しで考えていて、手順1)を「探索した手」と呼び、
手順2)を「指された手」と言っているように思うんだが？

>>346は完全な釣りですから・・・相手にするのはやめましょうね

俺は門外漢なんで申し訳ないが

>>331の
325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。

というのがサッパリわからない

ここで言うaとかbとかってそれぞれ同じ局面なんでしょ？
なんで勝ち負けが変わったりするの？

>345
>そもそも「双方が最善を尽くす」という前提があるので、
>「引き分け」でない局面の出現が一回しかないのは明らかなので、

この『「引き分け」でない局面』でいうところの、「局面」は、
今までの全ての局面の出現回数を、情報として持っている？持っていない？
漏れの説明もあいまいだったかも知れんが、そちらの質問もまた漏れには
あいまいにうつってる。悪いが、言葉を補ってくれ。

>>349
完全解析後のテーブルとしては、持っていません。
ただし、対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。

>>348
同一局面が4回現れると引き分けで指し直しになる
引き分けにあえて持ち込むか、勝ちを狙うかという違いが出てくる

途中から、人間→CPUに切り替える場合のみ局面の回数が必要
はじめからCPUなら同一局面はあり得ない(単に手を延長するだけでしかないため)

>>351
>>339

>>352
>>339
「人間→CPU」は、対局上「双方が最善を尽くす」ではない。

そもそも千日手で引き分けは王手とか詰み回避の時しか成立しないじゃなかったか？
何の意味も無い議論をしてるようにしか見えないのだけど。

まあ、完全解析自体が計算量的に不可能なんだから
千日手を巧いこと処理して、1万倍の速度で解析したところで
全然意味ないし、始めから机上の空論なわけですよ。

机上の空論もなかなか楽しいもんだぜ？

http://ja.wikipedia.org/wiki/%E5%8D%83%E6%97%A5%E6%89%8B
千日手のルールって結構最近出来たものなんだね

>>180は、「例え将棋の神様であっても」といってる
理論と現実の区別もついてなかったのか・・・
妙に納得

因みに地球上の全ての原子に1ビットづつ記録しても、
全ての局面を記憶することはできないし
かと言って量子コンピューターで将棋ができる時代の遥か以前に
名人は負けてるでしょうし。彼は何が言いたかったんでしょうね

>>351
24でR2300ていどのヘタレの意見だから的外れかもしれないけど


同一局面が出てきた場合、そこで千日手か打開かの選択が生まれるってのは
対局中よくある話なんで理解できる

ただ、331は引き分け（千日手）or勝ち（打開）じゃなくって
負けor勝ちというふうになってる

そこが理解できない

>>361
連続王手の千日手なら引き分けじゃなくて負けになるよ。

>>362
するどいね。ただ>361 の意見にも一理あって、
>351 に、引き分けも加えるべきだろうね

それと「最後の審判」っていう詰め将棋の問題があるようだ
現在の将棋のルールには不備があって、
必ずしも勝ち・負け・千日手で閉じるわけではない

打ち歩詰めのルールは、やや特例的なものだから、
仮に全部探索したところで、このルールを適用すると、
一部の状態ノードの勝ち負けが重複してしまう

現状の詰め将棋のプログラムに「最後の審判」食わせたら、
ただしく「不定です」って答えるのかな？

後手が王手を防ぐために打つあい駒の歩が逆王手になっている。
先手がそれを取って王手をすると千日手になってしまい先手は取れない。
しかしその局面は先手が歩を取れないと、先手玉は歩打ちで詰んでる。

個人的な意見だけど、詰め将棋としては歩詰みで、対戦としては後手の勝ちでいいんじゃない?
同一局面が2回しか出ていないなら王手を外せるんだから

>>364
打ち歩詰めで後手の負け

作者の作意では、歩の合駒が出来ないから(打ち歩詰め)後手の負けって事らしいね

>>366
先手の方から、同一局面への王手を外せるんだから
先手が繰り返す方が悪い

>>366
麻雀でいう形式テンパイを認めるっていうやつと同じだ
盤面をみただけでは打ち歩詰めではないのだからOKにしようぜ!

>>366
これ嫁　
千日手の定義より、打ち歩詰めの定義の方が優先されている
歩で王手する手は、ルールによれば、打ち歩詰めの規定には当てはまらない
しかし、歩を取る4度目の王手は千日手の規定に当てはまる　後手の勝ちだ


「特に決められた禁手事項」
(将棋世界平成5年1月号付録の'93年版 将棋ルールブック)

３．打ち歩詰
持駒の歩を打って王手をした局面で
王手を解除することが不可能な状態になる時、その歩を打つ手

５．連続王手の千日手
一局中同一局面の最初と４回目の局面の間の
一方の指し手が王手の連続であった時、
王手をした側にとって４回目が出現したときの局面。

将棋のルールってこんなに複雑だったんだね

最初から完璧に考え抜かれて作られたルールじゃないから
想定外な状況に対処するために後付けルールを足して複雑になって来ている訳か

まるでこれは

まるでこれは・・・何？

続きはWEBで

　　　〃∩ ∧＿∧
　　　⊂⌒（ 　・ω・）　　はいはいわろすわろす
　　　　 ｀ヽ_っ⌒/⌒ｃ 　　　　
　　　　　　　 ⌒ ⌒

>>350
ああ、やっと言いたいことが解った。
お互いが最善手を尽くせば、同一局面は二度あらわれないってのが
間違いだと思うぞ。それだと千日手に陥る局面というのはそもそも存在しない。

実際には、千日手ルールを無視した最善手だと千日手になってしまう局面が、
詰め将棋にあって今それを議論している。そして千日手は避けないといけないから、
それを効率よくコンピュータで処理する方法はどうかって話。

初期局面からの完全解析は当然無理だが、これは詰め将棋の問題を内包するし、
詰め将棋を適切に解く技術は、将棋のプログラム開発に必要

千日手になるタイミング云々の話は、そうしたことは当然わかっているものとして、
答えたんだよ

どういった解釈が正しいかについては、議論があるだろうが、
いずれにせよプログラム開発の段階では、各ノードの結論として、
「先手勝ち」「後手勝ち」「千日手」に加え、「先手打ち歩詰め」と
「後手打ち歩詰め」を考慮しないと駄目だろうね。

>359-360

私のこの問題に関する（このスレでの）これまでの発言は

>180 >183 >185 >191 >199 >203 >211 >218 >223 >228 >233
>242 >248 >260 >263 >268 >275 >282 >284 >291 >312 >317
>322

言いたい事はこれがほぼ全てなのでそこから判断してください。

ちなみに「例え将棋の神様であっても……分からない」と言う意味は
人間、あるいは何も考えてないプレーヤー（機械を含む）が指した
将棋を途中から将棋の神様が引き継いだとしたら、それまでに
どの局面が何回現われたかと言う情報なしに指し継いだのでは
最善手が何か決められないし、千日手かどうかの判断もできない
と言う事です。

なぜなら、元々の話題が将棋の神様同士が対局した場合に現われる
局面だけではなく、理論上考えられるあらゆる局面に対して「勝ち」
「負け」「引き分け」の結論を出そうと言う話なのでそういうふうに
解釈したと言う事です。

もひとつ追加すると、さっきも言ったが、「引き分け」の局面かどうかは、
その千日手ループにいつ突入したかで替わってくる。千日手判定が下る瞬間が違うんだから。
出現回数を保持していない局面のみの情報では、それが「引き分け」かどうか解らない

だから、

>「引き分け」でない局面の出現が一回しかないのは明らかなので、
> 完全解析後のテーブルとしては、すべての局面(手番込み)の

上記の「『引き分け』ではい局面」の、「局面」には出現回数を含ませる必要があって、
それなしには「引き分け」かどうか解らず、そして出現回数によって結果が違っているから、
出現回数の情報を単純にとっぱらうことは出来ない

おまいさんの言っている「解析中のテーブル」を「括弧付きのテーブル」、
「解析後のテーブル」を「括弧なしのテーブル」と読み替えて、>>340, 342 を見てくれ

それと>350で

1)「完全解析後のテーブルとしては持っていません」
2) 「ただし対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。 」

棋譜の情報を保持していれば、出現回数が解るので、1)と2)は両立しないよ
もし仮に2)が実際の対局を想定していっているのであっても、
参照先である「完全解析後のテーブル」が、1)によって情報を失っているので、
付き合わせることは出来ない。ないのと一緒だ

>>180は釣りか、解析後と解析中は判っていない

>378

あんまし気にしない方がいいと思うよ、ここ2chだし
ちなみに量子コンピュータ関係で言うとね、まるで量子コンピュータが完成すれば
今コンピュータで扱っている問題がすべて並列に瞬間的に解けるとする
言説がまかり通っているけど、それは勉強不足

量子コンピュータでは、解きたい問題ごとにアルゴリズムを考える必要がある
自分の知る限り、Shor, Grover以外に、パッとする実用的な話はないのが現状
量子コンピュータで、例えば3x3オセロでも解くアルゴリムを作ったら
そりゃ後世に名を残す、いい仕事になると思う

だから仮に量子コンピュータデバイスが実現したとしても、
それを使って将棋を解くアルゴリズムが見つからない状況になると思うぞ
将棋は人間が作ったゲームだから、問題設定が非常に複雑だ

ついでに今、私の頭の中で整理されている（つもりの）イメージを
お話しますと局面と指し手の組の集合が3種類あります。
（細かく分けると4種類）

O(1):将棋の神様同士がお互いに最善手を指し合った場合の集合

O(2):将棋の神様が勝てる側（先手必勝なら先手、後手必勝なら後手）を
　　 持って相手があらゆる手を指して来た場合に対応して勝つ手の集合。

　　 結論が引き分けなら相手があらゆる手を指して来た場合に
悪くとも引き分けに持ち込む（相手がミスをすれば勝つ）手の集合。
　　　
O(3):ルール上許されるあらゆる手で初期局面からたどり着ける局面
　　 及び指し手の集合（局面は指し手によりメッシュ状に連結される）

明らかにO(2)はO(3)の真部分集合であり、O(1)はO(2)の真部分集合です。
さらに

O(3)':ルール上許されるあらゆる手で初期局面からたどり着ける局面
　　 をそこに至る手順で区別したもの及びそこからの指し手の集合
　　　（局面と指し手は木構造で表現できる）

これまでこのスレで問題となっているのは「勝ち」「負け」「引き分け」の
区別を局面にラベル付けするにはO(3)の中で話しが閉じるのか、あるいは
O(3)'の集合に移行しなければならないのかと言う事ですよね。

私はGHI問題が存在するために局面を探索する途中のみならず、
その結果を保持するためにもO(3)'の集合上で表現しなければならない
（でなければ必要な情報が欠落する）と考えているわけです。

可能な局面数　Nにたいし、3回訪れた、0-2回訪れたという情報を持っていれば完全に解ける

2のN乗局面調べればいい

>381
いえ、私はほとんどたった一人の人を相手に話をしているつもりなのです。
それは将棋板の「将棋って数学に似てるの？」スレ

http://game12.2ch.net/test/read.cgi/bgame/1136526660/

で私とずっと議論を戦わせてた人（276)。この人に納得してもらいたい。
ちなみに私はそのスレで281の発言をした者です。

で、>359-360及びこのスレの>206他はその人の発言なんじゃないかな？と
もし違っていたらゴメンナサイ、誤ります。

>>384よ、
可能な局面(N個とする)　ごとに、3回訪れたかどうかの情報を持ち、かつ
局面データがあれば完全にとけているんだ 意味わかるか?
これ以上のことはないだろが　どこが不満だ?
道筋は全く関係ない

まずは、初手からならば局面だけ持っていればいいことは判っているのか??

>385
私も解析対象の局面に至る手順の情報全てを保持しなければならないとは
思ってません。ある程度（かなり？）、圧縮は効くでしょう。
ただ、実際に解析する際の手順としてはO(3)'上でゲーム木を展開するのが
いちばんシンプルで分かりやすいと思います。探索すべき局面は増えますが。

また初手から神プレーヤー同士が対戦するならば純粋な局面情報のみ保持
すれば良い、即ちO(1)上の結果にGHI問題が発生しないのは分かります。
まだ、いまいち良く分からないのはO(2)上の結果もそうなのか？　
こちらの結果も経路により区別する必要は無いのか？と言う事です。

>>378
ごめんね。

>>359は、>>355-357に対して、>>180をみれば「理論」の
話をしているのは分かるのに、「理論」だからこそ、
みんな付き合っているのに、「実行不可能」とか言い出すから、
いまさらそんなことを言うやつが出てくるのか、といった
意味合いの発言でした。
>>180に言ったわけではないです。

>妙に納得
は、
>>170と同じようなニュアンス。

ちなみに
> 人間、あるいは何も考えてないプレーヤー（機械を含む）が指した
> 将棋を途中から将棋の神様が引き継いだとしたら、それまでに
> どの局面が何回現われたかと言う情報なしに指し継いだのでは
この情報とやらは、棋譜で十分では?
それと、無責任なことはするなよ?
と思わなくもないのですが。

>387
ああ、そういう意味でしたか。それはこちらこそ失礼致しました。

引き継ぐべき情報はもちろん棋譜で十分ですね。
無責任な行為かも知れませんが、任意の局面に結論を出すためには
そのような仮定が必要になると思います。

>>388
またまた、ごめん。

>それと、無責任なことはするなよ?
は、>>378に言ったのではなく、話の内容で、対局を引き継ぐのに
「千日手になるかならないかの瀬戸際で交代するなよ。せめて二回目の
局面で交代してやれよ。」と言う意味でした。

他の人もそう思ったかな?

>>388
ちなみに
> 引き継ぐべき情報はもちろん棋譜で十分ですね。
とのことですので、>>379と意見が異なると言うことですよね?

>>379は、まったく、困ったもんですよね。

>>378さん(>>379さんもかな)

>>217を、もう一度よく読んでみてください。
よく読むとわかると思うのですが、初期局面の駒配置については、
何の言及もされていないのです。
これは、「初期局面として、任意の局面を指定可能」という事でしょう。
上での議論は、「理論上考えられるあらゆる局面」を十分含んでいるので
心配しないでください。

将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ？
当然そんなことは出来ないし意味が無いから勝敗に関係の有る部分だけ解析すればいいだけであって、
人間相手に最強を目指すなら同じ局面が何度来ようがその時に可能なベストの手を打ち続ければいいはず、
結果的にそれが千日手になっても将棋のルールに不備がある部分に達しても負けはしない。

うん
それが何か？

>>381
その通りで、量子コンピュータが実現すれば既存のコンピュータで難しい問題が
なんでも一瞬で解けるようになると思っている人間がいるから困る。
量子アルゴリズムがあって初めて高速な計算が可能になる。
ゲーム木の探索なんて量子アルゴリズムとは相容れないだろう。

>>376、>>379
あなたは、>>345、>>350の内容を全然理解していないことがわかりました。
基本的に、話の発端である>>165と同じことを言っているんですよ？

あと、詰め将棋のルールと、指し将棋のルールが違うことを知っていますか？
ルールが違えば、検索方針も違うんですけど?

>>180の方は、
>引き継ぐべき情報はもちろん棋譜で十分ですね。
と納得したようですが、あなたは理解できましたか?

>>394
>量子アルゴリズムがあって初めて高速な計算が可能になる。
高速な計算とは言わないだろ、手順を経て組み立てる計算なら高速であるが
局所的な超同時な仕組みでは計算しているというより状態の合成をしている
に過ぎないよな。
そもそも計算は「計って」、「数を算する」ことであて量子コンでは
計ってもないし、数も扱っていない。
量子コンピュータで致命的なものはソフトウエア、つまりプログラムの
仕組みが存在しないことだよな。
超同時演算にソフトウエアが存在したら、それが足を引っ張り
早いどころか亀速度になるｗ

量子コンピュータが学者の間で注目されないのは、ハードウエアとして
存在しなければいけないという前提があるからだろ。
電子回路な計算機で、ソフトウエアなしの計算機では利用価値などない。
「ソフトウエア」がどれだけ重要な発明であるか理解しておいたほうがいい。

>>392
>将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ？
「巡廻セールスマン問題」で完全解析を行ったというような話と同じだよな。
最適解だと証明したようなことを言う奴はいるが、結局は抜けが発生する。

類似問題を全数を判断せずに証明したと言い張るＤＱＮがいるが、
科学では仮説と実証だけでは、科学ではない。
仮説→実証→複数の反証で多面的に検証できなければ証明したことにはならない。
原理を解明したとか信じるヴァカも多いよな。まさしく宗教の域。

>>396
禿げしく胴衣

>>396
別にソフトウエア無でも超高速なデータベースとして機能すれば十分だろ
大体、計算機という翻訳語が変で、コンピューターは演算する機械だよ
つまり状態の合成をしているだけなんだがw

>>396
量子コンピューターに対してどんだけ無学なんだよ、中学生か？

何の指摘にもなってないよ

量子デバイスでだって量子ゲートは設計できる。
即ちチューリングマシンが構成できるし、メモリーだって作れるので
原理的に現代のノイマン型コンピュータで可能な事はなんでもできる。
ただ量子エンタングルメントを利用した長いキュービットによる
超並列演算をしないと、現代のコンピュータより圧倒的には
速くならないと言うだけで。

長いエンタングルメントしたキュービットの列で
特殊用途の専用アキュムレータ(と専用アルゴリズム用特殊ハードウェア）を
構成して今のノイマン型コンビュータアーキテクチャの一部として
埋め込む事も出来るんじゃないかな？
周りのノイマン型の部分は既存のデバイスでも量子デバイスでも良いだろうし。

いずれにしろ、まだろくに存在していないものを
あれが出来てこれが出来ないと言うのは早計じゃないか？
アルゴリズムが無ければキュービットアキュムレータが働かない
（超並列演算が出来ない）のはその通りだろうが。

>即ちチューリングマシンが構成できるし、メモリーだって作れるので
それではチューリングマシンであって、量子コンピュータではないだろ
頭変になったのか？

量子チューリングマシンと言うのが定式化されている。

>>404
あたま悪そうだな。チューリングマシンの手順式手法に戻るのなら
従来技術に激しく勝てず、量子の意味すらなくなる。
手順式は手順を超える演算はできないんだよ。

量子チューリングマシンでは量子コンピュータが得意とする因数分解が
出来なくなるｗ
これでは古典的コンピュータの因数分解専用の演算回路に下った
たんなる量子トランジスタレベルだろう。

仕組みを手順通り行うという概念の壁が越えられないからこそ
古典的コンピュータには性能の限界があることすら知らないようだなｗ

>405
量子チューリングマシンは古典的（決定論的）チューリングマシンとは
その動作原理自体が異なる。
決定論的チューリングマシンのアルゴリズムは量子チューリングマシン上では
（そのままでは）使えないだろうが、むしろ使う必要が無いとも言える。


参考：
http://results.atr.jp/atrj/ATRJ_25/08/main.html

>>406
あたま悪いな。論理手順が存在する限る原理が異なろうが
手順を省略できないわけだ。手順が省略できなければ順番に実行する
以外ありえないわけ。勉強になった？

>>406
そもそもチューリングマシンは命令語を受け取りそれを手順どおり実行する
タイプだろ。電送時間が存在しれば遅延する。
これでは古典的コンピュータが速度を上げられない理由と同じで
電送経路があるかぎり従来技術にはコスト的についてこれない。
つまり永久に開発されない。

量子チューリングマシンは古典的チューリングマシンが持つ能力を
全て保持しながら、なおかつ量子コンピュータ固有の機能も持っている。

量子ゲートに与えるデータ次第でどちらの働き方もできる。

量子チューリングマシンは計算可能性と言う点で
古典的チューリングマシンと全く同等であるが、
問題によっては（まさに）桁違いの計算能力を発揮する。

どうでもいいけど将棋の話題しない？

振れるようなネタはないのだけど。

うーん、難しいな。
Lispで将棋ブログラミングしたいと思っててまだ始めてないし。

と言うか、Schemeで書くべきかCommon Lispで
始めるべきかで早くも悩んでるしw。

非決定的チューリングマシンの話は出ないのか？
これが量子チューリングマシンで実現できればメチャ嬉しいのだが

量子コンピューターが出来る前に光子コンピューターの方が早く出来るでしょ。

量子コンピュータでチューリングマシンはできる、しかし現状の性能には
激しく達し得ないというのでＦＡ。
まあマヌケ君はできないことを誇張するのが得意だから、またデンパするんだろう

http://www.geocities.jp/rysyy913/kakinokijyoseki.html
URLに「宮本定跡が激指５に使われている」とありますが、本当でしょうか。
事実なら「激指６」ではどうなっているのでしょうか。
なるべく詳しい事情を知りたく思います。

>414
誰が正しいかでは無くて真実は何なのかを知ろうとする方が有益だぞ。

スレ違いかどうか気づける能力を持つ方が重要だ。

最近はスレ違い、スレ違いとやたらうるさい人が居るな。
まるで縦割行政が好きな役人か自分の専門分野にコモッテル蛸壷学者だ。
そういう考え方からは学際領域にある分野が発展する事は決してあり得ない。

とは言うものの量子コンピュータ及び分子コンピュータや
光コンピュータなどに関するスレを新たに立てた方が
良いかとも思ったが、どの板に立てたら良いのか良く分からん。

それとも既にどこかにあるのかな？

量子コンピュータ　3qubit
http://science6.2ch.net/test/read.cgi/sci/1171629018/

過疎ってるな

>>418
お前がスレ違いだろ。別に学問を発展させようなんて思ってない

>>418
お前こそ将棋のプログラマじゃないだろ

>420 Thanks

物理板か。
しかも寂れていると言うか荒れているようだな。

計算理論やアルゴリズム論、計算量理論から見た
量子コンピュータ　スレがあっても良い気もするな。

量子コンピュータなんてやっている奴は約１名の２ｃｈ中毒ニート以外
いないだろ。

量子コンピュータまず量子縺れ状態のシュミレーションから、かなり高度な量子力学の知識が必要。
どちらにしても量子コンピューターシュミレーターってあるらしいけど一般公開して無いだろ、動かすのにたぶんスパコン必須？

みんなで激指を買って遊ぼうよね♪（　＾ω＾）

激指 定跡道場

商品紹介
2005年世界コンピュータ将棋選手権で全勝優勝を飾った「激指」のシリーズ最新作。
序盤戦術を体系立てて学習できるモードを搭載、最強の思考エンジンに加えて学習補助機能が充実しました。
定跡講座は所司和晴七段が全面協力、プロ将棋の最先端を無理なく身につけることが出来ます。

コピペうぜぇ氏ね

量子信者はカエレ！

町はずれの教会をシルクのような霧雨が包んでいます。
傘も差さずにレンガの階段にもたれていると
遠い町明かりがいくつも輝いては滲んで行きます。
あの人はガードレールをのりこえて空の向こうに何を見たかったのでしょうか。
あの人が星になったなんて嘘ですよね？

ポエムはポエム板でおｋ

>>429
我々は重要な事を見逃していたようだ、

このポエムの中に封印された古代の将棋の英知が詰まっているのだよ！！(AA略)

だから量子コン厨は物理板で爺でもしておけ。
スレ違いだよ、キミのような量子ウンコは

>429
リョウコ信者w
最近の厨はググって出てこないと何も調べられないのか

夏厨の季節

>>429 これかｗｗ ttp://jp.youtube.com/watch?v=_QV7UrAW5vU

うはぁ、なんという音程……

量子って、武豊の嫁？

銀星将棋おもろいな。思考タイプに強引、慎重なんてのがあって
強引にすると思考レベル最低でも強引に攻め込んでくる。
ずっとこういうの待ってたんだよな。重みのさじ加減弄るだけで
技術的にはなんも難しくないのになぜ今までなかったのかが不思議なくらいだ。
全AIにこのオプションをつけてくれ。

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

ほ

しゅ、しゅって言いたい訳じゃないんだからねっ！

ぬは、書かれちまったw

ダリか初心者にも分かるように
評価関数における評価項目のつけ方まとめてもらえませんか

>>443
・駒割
・王将8近傍の敵・味方の利きの数
・王将との相対位置による評価
って感じの情報でいいのか？

玉の安全度を考えるをON/OFFで自己対戦すると２７勝３敗だった。
終盤は駒得より完全に玉の安全度だね。

>>444
>>445
ありがとうございます。
評価項目の全体的な全体的な優先順位や
細かい設定などはありますか？

優先順位ってのは評価項目の重みの事？
序盤は駒得や囲いが重要だけど、終盤は王将の安全度の方が重要だろうし・・・
大雑把な方針としては、試行錯誤して最適な重み・設定を見つけるか、学習で何とかするかの二択じゃないかな。
自分の棋力とかコンピュータ将棋にかけれる時間と相談しながら決めてくれい。

>>447
分かりました！がんばります！！

ほ

し　ひゅうま

あ

そ

こ

ほ

あたぁ！

[人工知能]革新AI囲碁ｿﾌﾄ『Crazy Stone』@ﾓﾝﾃｶﾙﾛ法
http://game12.2ch.net/test/read.cgi/gamestones/1191324848/
[人工知能]"Crazy Stone"@モンテカルロ法
http://game12.2ch.net/test/read.cgi/bgame/1190942764/

> これまでのアルゴリズムとは異なり、モンテカルロ法のアプローチでは
> 非常に簡単に並行処理ができるので、
> 新世代プロセッサーのマルチコア構造を活用できる。

モンテカルロ法自体は並列化しやすいだろうが、
それとともに使われて成果を上げているUCT（だっけ？）
とか言う探索アルゴリズムは並列化しにくいらしいよ。

ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ

今このスレを読んだ。「完全解析」について。

チェッカーや6x6オセロで言う「全探索」や「完全解明」は
ゲーム開始時の局面から始めた場合の話だよね。
合法な任意の局面からというのは解かれていない。
でも、このスレを見てきたところ、
将棋では任意の局面からの場合を考える人が結構いる。
任意の局面から始められるものとして詰将棋があるからかな。

何だか文化の違いのようなものを感じたので感想を書いた。
チラ裏ですまん。

ゲーム理論はどうも胡散臭い。
見直してその有効範囲を確認する必要がある。

>>461
バカですか？

しっ
触れるな

ﾜﾗﾀw

>>463-465はツンデレ

おまえは最近ツンデレという言葉を知ったばかりの初心者

確かに。
俺もツンデレとは違うとおもた。

ttp://minerva.cs.uec.ac.jp/~uec55/
誰か出る？

>>469
準備期間短すぎ

５５将棋って以前権利をめぐってもめてなかった？

あれどうなったんだろう？

よく判らんが、これが発案者のサイトかな?
http://www.geocities.co.jp/Playtown-Spade/8662/
電通大ではまったく無視しているようだけど。
http://minerva.cs.uec.ac.jp/~uec55/

>472
無視してるのか、一応話しは通してあるのか見ただけじゃ分からんだろ？

>>473
普通話を通すと言うことは、断り書きを入れる方向で落ち着くもんだ。
断り書きもなしに無条件に許可するようならば、森田将棋に噛み付く筈も無かろう。

ゲームのルールはアイデアだから
ルールの記述文をぱくらない限り問題ないよ

こんなんめっけ
ttp://524.teacup.com/yss/bbs?M=ORM&CID=1088&BD=3&CH=5

マジですか？！って感じだねえ、ほんとならやばくて手が出せないっつうか出したくないｗ

ココはひとつチャネラーで新しいミニ将棋ルールー作ろうぜ

７七将棋とか…
駒の種類も本将棋と変わんない。けどちょっと大きいかな。

　　 ７　　　 ６　　　 ５　　　 ４　　　 ３　　　 ２　　　 １
┌──┬──┬──┬──┬──┬──┬──┐
│▽桂│▽飛│▽銀│▽玉│▽金│▽角│▽香│一
├──┼──┼──┼──┼──┼──┼──┤
│▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│二
├──┼──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│三
├──┼──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│四
├──┼──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│五
├──┼──┼──┼──┼──┼──┼──┤
│▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│六
├──┼──┼──┼──┼──┼──┼──┤
│▲香│▲角│▲金│▲玉│▲銀│▲飛│▲桂│七
└──┴──┴──┴──┴──┴──┴──┘

全駒総動員の方向で、一度も動かさない駒とかを無くしたいね。
で７七将棋のルール案を。

１．相手陣は「三段分」
　※桂馬の成・不成の選択を残したい

２．味方玉が相手陣の一段目に到達すれば、相手玉を詰まさなくても「勝ち」
　※参考：トライルール

３．千日手はどんな場合でも４回目の同一局面を出現させたほうが「負け」にしたいけど、
　棋譜をきちんと取らないと判断しづらいから難しいかな

　　 ４　　　 ３　　　 ２　　　 １
┌──┬──┬──┬──┐
│▽香│▽桂│▽王│▽銀│一
├──┼──┼──┼──┤
│▽歩│▽歩│▽歩│▽銀│二
├──┼──┼──┼──┤
│＿＿│＿＿│＿＿│▽歩│三
├──┼──┼──┼──┤
│▲歩│＿＿│＿＿│＿＿│四
├──┼──┼──┼──┤
│▲銀│▲歩│▲歩│▲歩│五
├──┼──┼──┼──┤
│▲銀│▲玉│▲桂│▲香│六
└──┴──┴──┴──┘

これどうよ、評価よろしく

>>479
大駒がないのと、銀があって金がないのが気になった。

>>480
大ゴマは盤面が狭いのでこの際無くていいだろうという判断
金は、ほしけりゃ敵陣に乗り込んでひとはた揚げて帰って来いということでゲーム性を面白くするためわざと無くしました

駒の動きは本将棋と同じじゃなくてもいい？例えば八方桂とか。

４４将棋はさすがに簡単すぎるんじゃねーか？
たぶんすぐ解明されそう。

４６だった orz

>>483
解明されたら告ぎ考えるから是非解明してくれ

将棋板から拾ってきた
あっちにはこいつの対局スレがあるぞ


　　　６　　　５　　　４　　　３　　　　２　　　１
┌──┬──┬──┬──┬──┬──┐
│▽飛│▽桂│▽銀│▽王│▽金│▽角│ 一　
├──┼──┼──┼──┼──┼──┤ 　　　
│▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│ 二
├──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│ 三
├──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿｜ 四
├──┼──┼──┼──┼──┼──┤
│▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│ 五
├──┼──┼──┼──┼──┼──┤
│▲角│▲金│▲玉│▲銀│▲桂│▲飛│ 六
└──┴──┴──┴──┴──┴──┘

ああ？おお？

知障のふりで「将棋界の○○」「ああ？」という言い回しを使う奴には要注意だ。

>>486
香車がいないのはさびしいな。

むしろ大駒がいらないんじゃね
どうせ盤面は狭いんだし

代わりに酔象を入れようや
裏は太子で

　　　６　　　５　　　４　　　３　　　　２　　　１
┌──┬──┬──┬──┬──┬──┐
│▽銀│▽金│▽象│▽王│▽金│▽銀│ 一　
├──┼──┼──┼──┼──┼──┤ 　　　
│▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│ 二
├──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿│ 三
├──┼──┼──┼──┼──┼──┤
│＿＿│＿＿│＿＿│＿＿│＿＿│＿＿｜ 四
├──┼──┼──┼──┼──┼──┤
│▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│ 五
├──┼──┼──┼──┼──┼──┤
│▲銀│▲金│▲玉│▲象│▲金│▲銀│ 六
└──┴──┴──┴──┴──┴──┘

金玉象はまずいんじゃないか？ エロ的な意味で。

ここも糞スレになったな

フェイクができないアルゴリズムなんて、負けるのは当たり前。
勝負というのは先の読み合いで、決定されたものではないだろ。

つまり先が読めないからこそ勝負なわけであって、
相手の行動を予測し、相手に勝つのではなく相手に負けてもらうのが筋ってものさ。

眼力の無いやつは空気読めないから計算、つまり理屈だけで勝とうとする
理屈だけな奴ほど勝つのは楽なことを知っていた方がいい。
理屈な行動は、相手からは完全に予測される行動だからだ。
勝ち手を譲れば、１００％の確率で勝ち手を奪うのが理屈というもの。
それがフェイクだと気がつかなければ相手の負けは決まる。

日本語でおｋ

＞492
とっくの昔から糞スレだボケ。

完全情報ゲームでフェイクとか言ってもな。

>>493
いや、言ってる事はよくわからんがとにかく麻雀やポーカーのスレじゃないからここ

493じゃないが、例えば自王は放置すれば20手詰めと言う場合

１、放置すれば相手王に必死を掛けられる。
　　相手が詰みに気付かなければ勝ち。
２、受けると長引くがジリ貧。

こういう場合コンピューターだと2を選んだり、
持ち駒使い果たすまで王手掛けたりすることが多いわな。

com同士だと意味ないだろうけど、人間同士だと1が有効なことが有る。

>498
それを実現するには自分の読みと相手の読み及び評価関数を区別して扱う
「相手モデル探索」が必須だな。

で相手が人間かコンピューターか、どれくらいの棋力かに応じて使い分ける。

圧倒的に強ければ、相手は関係ない　強ければそもそも20手詰めの局面へは進まない

おれも>>500と同意見。
結局、相手の思考を予測するってのは、自分の思考に自信が無い時の小手先の対策なんじゃね？

>>498-499
相手のアルゴリズムを読んだとしても、その相手はこっちを騙すためにわざと気付かないふりをして
弱く見せかけているのかもしれないぞ
相手を見て判断するのは対人戦での面白さを出すには重要なとこではあるけどさ

>500-501
人間のトッププロにはなかなか勝てない（全体的な実力では上回れない）
からこそ、そういう戦略に価値があるのでは？

例えばコンピュータ将棋は詰みのある局面でそれを発見するのが
やたら速いが、相手（人間）もそうだと仮定していたらその利点は
あまりうまく生かせずに>498の挙げたような状況に陥るかも知れない。
詰みを正確に速く見つける能力がむしろ弱みになってしまう。

>502
特定の相手の指し方を事前にじっくり研究していたらどうかな？
たとえば対渡辺竜王を想定して。

ディープブルーも実はカスパロフの指し手を事前にたっぷり研究して
相手の指し方のモデルを持ってたと言う話だし。

>>503
個人的には、そういう方向性が好きなのだが、
こと「プロに勝つ」という目的においては、>>500が正しいと思う。
というか>>503の方法でプロに勝つには、とてつもないプログラム技術と
ハードウエア能力が必要になって現実的でない。

プロに勝つというのは、ほっといても100年後には達成できるけど、
楽しめる、指導してくれる、というコンピュータ将棋が今後の課題やね。

>504
その考えが甘いとしたら。

つまりコンピュータが人間のトッププロより圧倒的に強くなると言う事は
相手がどんな指し手で来てもそれに対して正しく応手できると言う事だが
将棋と言うゲームがそう御しやすいもので無いとしたら厄介だぞ。

その可能性は多いにある……と俺は思う。

それよりは対戦相手のモデルを持っておいて相手の思考の癖（隙）を突いて
序盤からジワジワ優位を築いて行く方がまだ望みがありそうに思える。
確かにセコイ方法だけどなｗ。

>>505
確かに俺の考えが絶対に正しいとは言えないが、
相手モデルとかでプロに勝てるなどというのは
とんでもなく甘い考えだと思う。

>>505がセコイ方法だとは全く思わない。
実現できたら本当に素晴らしいが、実現が難しすぎる。

{41, 85, 45, 12, 02, 77,　・・・} 　(これがひとつのデータです)　という可変長データが複数あるとします
これらを効率よくメモリに記録するにはどうしたらいいですか?

場所まちがえました　すみません

あんまりセコクない対人戦略だと、
短時間の勝負ほどコンピュータ有利であることを考えて
時間攻めがいいんじゃないかな？

極端な例だと、80台パソコンを連結して並列に先読みさせる。
可能な相手の指し手が80ある局面なら、人間の思考時間に全部考えて、
ほぼノータイムで指すこともできるはず。
そうされると持ち時間2時間でも、正味1時間位に感じるんじゃないかと。

あるいは、"少しよくなるけど局面を単純化する手"より
"よくもわるくもならないけど局面を複雑化する手"を優先する方針にする。
そうすると選択肢が多くなり、人間側の読み筋から外れる率が高くなる。

人間の場合かなり前から現在の局面のことを考えているので、
先読みを空振りさせた場合の負担は、コンピュータよりずっと重いはず。
一から考え直すことになって、かなり苦しくなるじゃないかな。

竜王と対戦したボナンザも、予測読みが当たればノータイムで指した。
また、ボナンザは人間なら早期に枝刈りしてしまう手を指すこともあったので
読みを空振りさせるという点でもそれなりにできていた。
80台のパソコンというリソースがあるなら、普通にやらせても強くなるから
下手な小細工では意味がないということになると思う。

いや、、アイデアを否定してばかりであれだが、
実際そういうアイデア自体は貴重だし、生かしていくべきだと思う。
ただ、それはすごく難しい（だからこそ素晴らしい）と言いたかった。

相手の指しやすい手から調べるのはかなり有効な手法だよ　プロの棋譜、定跡を使うのはその為
個人に限定してもよい

>>510
持ち時間１時間として
コンピューターが３回に１回ノータイムでも、１時間つかいきれば
人間側の思考時間は、自分の持ち時間と合わせて２時間ある
コンピューターが全部ノータイムの超早指すると
人間側の思考時間は、自分の持ち時間の１時間しかない
読みを空振りさせる回数が３回位増えると
１回あたり数分位とられるから１０分くらい損する
ぜんぜん違うと思うんですが‥

結局、８０台を良い手を捜すためにつかっても、２割位しか
最前手が変わらないなら、時間攻めで人間が間違うのに
かけた方がお得なように思うわけで

実際、複数台での並列先読みや、局面の複雑度を測ったりするのは、
相手の指し手の傾向をつかむより遥かに容易じゃない？
自分のプログラムはまだ弱いのでそんな段階ではないけど。
誰か人柱にならないかなあ。

台数が80倍になると、一般的に思考時間を9倍にしたくらいの強さになる。
つまり、思考時間：1分、強さ：1台9分相当を選択するか、
思考時間：0分、強さ：1台1分相当を選択するかという問題になる。
（人間が常に同じ時間を消費するという前提）

コンピュータよりも人間の方が持ち時間の価値が高いことを利用するわけだ。
悪い手は切り捨てて愚直に80手読まないようにするなどの工夫もできる。
そうなると普通の予測読みとの境界がぼやけてくる。
俺は、通常の予測読みがいいと思う。俺も実測してないのでこれしか言えない。

あの自演犬やってないと言い張ればいいと思ってるな
バレてないと思ってるのは自分だけだぞｗ

ああ？おお？

ボナンザVS勝負脳―最強将棋ソフトは人間を超えるか
http://www.amazon.co.jp/dp/4047101079/

将棋のプログラム作っている人の開発環境が気になります。
VC6++っていうのは古いでしょうか？

将棋ならコンパイラやIDEは関係ないと思うが、
VC2005EEがある今、VC6を使う理由がない。

VC++6は軽い

VC++6ってインテリセンスのだいぶ貧弱だったような

まぁ、x64がコンパイルの出来ないでいいならVC++6でいいんじゃね。

>>518-521
みなさんどうもありがとうございます。
VC++6でもよさそうですね。

VC++6はバグが多くて嫌

つーか、>518を読んでどうしてそういう結論になるのか判らん。
まぁ、VS6の正規ユーザで尚且つ時代遅れのPCを使っているというなら止めないが。

VC6は2004にバージョンアップ版が出ている
新しいVistaつかうより、バージョンアップされたXPの方がいいということもある

仕事じゃなければ好きなのを使えばどれでもいいさ

VC6なぜか人気あるが自分の経験から言うとあまり印象よくないな。
特に付属のSTLかなりバグがあってひどかった。

今となってはかなり古いコンパイラだから
テンプレートのサポートが微妙だったりするけど
自分の使い方では２００３よりもよかったよ
インストール早いし、起動軽いし

STLはSTLPORTいれて使うもんだと思ってる。

そんな私も２００５に移行しましたが。

VC6の怖いとこは
一見するとコンパイル通って正常に動作しているようでも
ﾄﾝﾃﾞﾓな解釈をコンパイラがしている箇所があったはず。

std::cout << typeid(1.0F==1.0F).name() << std::endl;
std::cout << typeid(1==1).name() << std::endl;

仕事だからVC6とかいう発想は
無責任もいいとこ。

まともなコンパイラの機能テストをしていれば
Noob以外はそのような発想はしないでしょう。

ぼ、Borland C++ Builderは？　いいの？

USIプロトコルの info コマンドって、minmax探索に偏ってるね。
MC+UCTだと info string ばっかになりそう。
もうちょっと融通利かせないとUSIプロトコル使う意味なす…

>>531
setifnomenuコマンドなんてのが必要かもね。

setinfomenuだった。

info pvで「最後のモンテカルロシミュレーションの手順」でも送ってやればいいんじゃね。
GUIがちゃんと対応出来るかどうかは知らん。

最強じゃなくてもいいからだれか大局将棋実装しておくれｗ

やるからには最強を目指す！
ところで大局将棋ってナニ？

ttp://taikyokushogi.hp.infoseek.co.jp/tkintro.html

ttp://www.chushogi-renmei.com/images2/taikyoku-s.jpg
やる気しねえｗ

ごめん、やっぱムリ。
てか、駒の動かし方全部把握してるヤツ居るのか、これ？

仮に把握できたとしても、動かす気になれねぇ。

ttp://taikyokushogi.hp.infoseek.co.jp/tkpieces.html
>>537のサイトに駒の説明があるけど

ページなげえｗ

http://game14.2ch.net/test/read.cgi/bgame/1163033955/
最長テンプレだと聞いた。

スレを立てるたびに貼る必要はあるのか…
最長の地位を保つための儀式なのか…

こんなのランダムに動かしてれば人間の方が飽きて投了するだろｗ

大局将棋はゲーム性が低いな

ゲームと言うより占いの儀式みたいなものだったって聞いたような気がした(うろ覚え)。

>>537
テレビ番組で、プロ棋士同士が対局してたな
駒の動かし方は本を見ながら確認してたｗ
１日では勝負がつかず、３日くらいかけていたと思った

トリビアだな

森羅万象棋作ろうぜ

「バーサーカーソウル！」

市販の将棋強すぎだろ。なんか将棋もプログラミングもやる気ﾅｸﾅﾀ・・・

おまいが弱いだけ

前回のGA見てみろ。やる気沸くぞ。

もっとこのスレ盛りageようぜ

【訃報】チェス元世界王者、ボビー・フィッシャーさん死去　６４歳
http://mamono.2ch.net/test/read.cgi/newsplus/1200665136/

C言語でやってる人いる？
C++の方がいいのかな？

C++の方がいい
部分的にC言語やアセンブラも使える

スレッド使ってますか？

使ってますがなにか？

もう、ブルージーンで最強のチェスプログラムできちゃったので将棋プログラムは興味ないわ

門外漢がよーいうわ

作ってる人近況報告してよ

強化学習してる。死にそう。

いちから作り直してる。

>>564
ばかやろう、俺なんてマイナスからの出発だぞ。

>>565
なんだよ、マイナスってｗ

以下、マジレス。
おとといのUSIエンジンの登場でモチベーションがかなり上昇した。
弱くても、勝てなくても、笑われても、それでもいいからとにかく形にすることに決めたよ。

>>566
ランダムざしに負けるのがマイナスじゃね？

俺も強化学習やってる
俺よりは強いんだが・・・

パソコンぶっ壊れたから修理するところから。
あと、部屋が汚くてどこに本があるか分からないから掃除するところから。

>>567
負けそうだから怖い。

>>568
出現頻度の低いパラメータって学習が遅くね？
なんか対策考えないとなぁ。

>>570
自分は出現頻度が低いパラメータは保持したまま
別のパラメータが変わるような局面に分岐させたりしてる
ちなみに効果の程は測ってないけど

7五玉で投了

>>571
なるほど、賢いなぁ。
俺は猿だから対局数でごまかそうかなっと。

れさライブラリ使ってる人いる？

あの！　Delphiで将棋作るとC++より速度遅いですか？

ボーランド製品ならどう速度だろ

あの！　Delphiで将棋作るとVisual C++より速度遅いですか？

最適化や個人の技術によるが同程度ならVCの勝ち

あの！　Delphiでインラインアセンブラだけで将棋作るとC++より速度遅いですか？

並列化のことで何年か前にYSS掲示板で議論になってましたけど

すごく初歩的な話なんですがrootでsplit(分割)する／しないってのは
どういう意味だったんでしょうか？

最初の深さ1だけは読んで、そのそれぞれの（1手読みの）手を並列化するのが
「rootでsplitする」でいいのかな？

しない、ってのはどういうことなんでしょう？

YSS掲示板で訊いた方がいいんじゃね？

あまりに初歩的すぎかなとおもって・・・

真面目に質問すれば大丈夫

あ，ここより将棋板の方が人（実際に作ってる人）が多いから
そっちでもいい alternative だったか，開発者用のスレがある

32bitパソコンを使ってますがintでなくcharを使うと
メモリの節約にはなるが速度は遅くなるのですか？

メモリアクセスが減るから速くなるケースもあるかもしれません。
要は、一概には言えないのでテストケースを充分絞って実験してみることです。

char や　floatが遅いというのはデマ
キャッストに時間がかかるというのはデマ

へぇ〜今調べて自己解決しますたと言うところだったんですが
一概に言えないのですか。へぇ〜

そりゃそうだろ。メモリ2GB程度のパソコンごときで1G件のデータを扱おうとしたら
charじゃないとswapしまくりで遅くてしゃぁない。

将棋では1Gも使わないでしょう。
ところでYSSの人は配列は2のべき乗にすると速くなると言ってますが
みなさんそうしてるのですか？

それはデマ　スワップが発生しないように最低限の確保が速い

へぇ〜デマばっかりなんですね。
今のパソコンと将棋ソフトでスワップはないと思いますが。
でもそう言うには相応の理由があると思いますが、
実際に実験してないけど理論的には速いはず、というところでしょうか。

512や1024ならスワップ起こるよ
OS、ほかのプログラムが動いているとハッシュテーブルがメモリ外に出ることがある
するととても弱くなる
たとえばボナンザで実験するとわかる

>>580
rootでA,B,Cと候補手があるとして
BやCの評価値の評価値を並列に探索して求める場合はrootでsplit。
Bの評価値が確定してからCを探索する場合はrootではsplitしていない。

>592
デマというか、ハードウェアとかコンパイラに依存するので時代によって……

>>594
ありがとうございます

>BやCの評価値の評価値を並列に探索して求める場合はrootでsplit。

というのは直観的に理解できそうです
rootでとりあえず指し手を列挙してみて
おらこれとこれとこれがあるから行ってこいやぁ、みたいなw

でも
>Bの評価値が確定してからCを探索する場合はrootではsplitしていない。

というのがよくわかりません
この場合、どこで並列処理（並列化）をしているのでしょうか？

Bにも子供たちが…

てことは……

深さ0（？　現局面のこと）で指し手を列挙して
おのおのの指し手について並列するのがrootでsplit

深さ0で指し手を列挙したあとその指し手の1つをまず取り出して
そこからの指し手（深さ1以下の指し手）について並列するのがrootでないsplit

ってことですか？

実際の方法論としては
たとえば候補手が50個並んでいて
CPU1が候補手aを、CPU2が候補手bを読んでいって
先に終わったほうが候補手cを読む……という「仕組み」自体はいっしょで
それをrootでやるかそうでないかだけが違う（というかYSS議論では違ってた）
ということでしょうか？

>>598
深さ0で指し手がA0、B0、C0と3つあるとすると、今のプログラムは
A0の手を調べるのに全体の50%の時間を使ってしまいます。
そこで、A0の探索が終わった後に、B0、C0の2つの手を並列に探索します。
その方がA0の探索の結果を使えるので効率がいいためです。

A0の手の下にはA01、A02、A03の3つの手があるとすると、
A01の手を調べるのにこれまた50%の時間がかかります。
そこで、A01の探索が終わった後にA02、A03の探索を並列に行います。

こうやって延々続いていきます。
深さ0でも並列に探索するのが「rootでsplit」で
深さ0でのみ並列に探索しないのが「rootでsplitしない」です。
「rootでsplitしない」場合でも深さ1、深さ2、、、、ではsplitします。

並列化ド素人の自分だが
Aspiration searchの真ん中の値で二分すれば
単純に二倍速くなりそうという感じは受ける。
ちょっと試せないので分からないけど。

ボナンザも歩の交換値２つぶんでAspiration searchをやってるらしいので。。

やっぱり問題はその次からの一回の探索を分ける方法だねえ。

>>599
なるほど・・・
ありがとうございました

>>600
お前コンピュータ将棋もど素人だろ。
ウィンドウを２分割すれば探索ノードもキレイに２分割できると思ってる？

逆に他の手法はきれいに二分割できるの？やろうとしてるの？

ただのPVS使ってるが少なくとも600のやり方よりは効率がいい。
ついでに書くと、MTD(f)の探索木みれば600がいかに効率悪いかわかる。
まぁ、俺は選手権の対局より強化学習の方を高速化したいから、並列探索は手抜きだがな。

書き忘れてた。>>604のPVSはPV Splittingの方。

あーなるほど、2つほど勘違いしてた。
600をやって他もできると思ってたら、できないねえ。
ノード数が二分できないのではなく、ノードが二分できないのか。
同じ局面を二回作ってるから二で割って一と。

そーゆー事だ。

>>599に補足すると、「rootでsplitする」場合だと、B0とC0を並列に探索するのでB0,C0の評価値が求まるまでの時間は長くなる。
「rootでsplitしない」場合だと、B0の子ノードOR孫ノードORもっと先のノードで並列化するので、B0の評価値は「rootでsplitする」場合より速くも止まる。
んで、仮にA0の評価値＜B0の評価値だと、B0の探索終了時に「B0は（最善手ではないかもしれないが）少なくともA0よりは良い」と分かる。
なんで、「rootでsplitしない」場合は、「仮の最善手」が速く決まる可能性が高い（YSSの掲示板だと「見切り発車」とか表現してた）から、思考時間に制限がある場合にちょっとお得、と。

すまん、二行目の「も止まる」は「求まる」だった。
死んできます。

まあ、そんなに簡単なら話にも出てこないか。
でも並列化ってイメージしにくいような気がする。
頭を両手で同時に洗うのは並列化？

もちろんそうだが，タスクの分割が自明な例だな

例えばフライを揚げる時、衣付ける人と揚げる人の二人でやる事あるだろ？
そういうのが並列処理。

その例えは誤解の元

>>612
それはCPUのパイプラインだ。
並列処理なら、フライパンを二つ用意しなきゃ。

もっとも、将棋の場合は揚げなくてもいいものがあるから、
二つ用意しても倍は速くならないのだ。

>613
どういう点が…と聞いてみようと考えたら分かった。
>612の例えは「並列処理」と言うより「パイプライン処理」だ。

あ、先に言われてしまったｗ。

パイプライン処理も並列処理みたいなもんでしょ。
依存関係があっても適用できるわけだし

そういう細粒度の並列処理を
ソフトウェアでうまく書く方法ってある？

手の生成→並べ替え→手を打つ
　　　　　手の生成→並べ替え→手を打つ
　　　　　　　　　　手の生成→並べ替え→手を打つ

手を打たないと、次の手の生成ができないから無理か　orz

>パイプライン処理も並列処理みたいなもんでしょ。
ぷぎゃー

いや、言いたいことはわかるよ

>617
普通のPCハードウェア（CPU）じゃ無理だね。
パイプライン処理（それも将棋専用の）が可能なCPUじゃないと。

だから「A級リーグ指し手1号」と言う名前で専用プロセッサを
FPGA使って開発してる人が居るわけで。

パイプラインによるオーバーラップさせた処理は並列処理の一種

マルチコア環境ではハードでなきゃ無理ということはないと思う
例えばPS3/Cellにはそういう形（パイプライン）の並列処理の枠組みが用意されてる
もちろんアルゴリズムは自分で考えるのだが

>622
へー、CellB.E.(SPU?)にそんな仕組みがあるの？
単なるSIMD演算器がさらに8個並列で存在するだけかと思ってた。

個々のSPU内の演算器を自分好みのパイプラインに仕立てられるのか？

>622
もしそういう機能が本当にあれば非常に興味深い（使ってみたい）ので
どのドキュメントに載っていてどんな名前で呼ばれている機能か教えてくれ。

「Cell Broadband Engine アーキテクチャ」Ver1.01 (by ソニー）
をざっと眺めてみたが見つけられなかった。

>622
もしかしてSIMD演算機能あるいはSPUを仮想化してマルチスレッド
ソフトウェアを走らせる機能を（ハードウェア）パイプライン機能と
混同してない？

普通の（IntelやAMDのx86)CPUもある種のパイプライン（スーパースカラー）
機能はあるけどプログラマが意識的（明示的）に操れるわけじゃないし。

622じゃないけど、

PS3のCellで囲碁をパイプラインってこんなの？
http://www.geocities.jp/hideki_katoh/publications/gpw2007/gpw07-private.pdf

αβ探索じゃなくて、モンテカルロならパイプライン可能かもな
要はスレッド間の同期をとるだけじゃん

>>625 スーパースカラーはパイプラインじゃないよ

フェッチ→デコード→演算→レジスタ書き出し
　　　　　フェッチ→デコード→演算→レジスタ書き出し
　　　　　　　　　　フェッチ→デコード→演算→レジスタ書き出し
　　　　　　　　　　　　　　　フェッチ→デコード→演算→レジスタ書き出し

こういうのがパイプライン。
スーパースカラは複数の命令を同時に実行できる機能

スレッド間同期とパイプライン処理は違うでしょ？

>627
スーパースカラー＝パイプラインじゃないけど、現在主流のCPUで言う
「スーパースカラー」はパイプライン処理が前提なんだけど。

すなわち複数命令を（同時実行できるものは）同時発行しておいて
さらにそれらをパイプライン化された処理装置に叩き込む。

詳細はWiki等を参照してくれ。

どの命令が並列処理できないかコンパイル時点で分かるよね？

>630
??? 何が言いたいの？
コンパイラに並列化を任せて明示的に(機械語レベルで）複数命令を
並列実行するならVLIWアーキテクチャだね。Itaniumみたいな。

ちなみに普通の（VLIWでない）CPUはコンパイラが並列処理可能な
命令を見つけたとしてもそれをマシン(CPU)に伝える手段が無い。

さらにちなみにベクタープロセッサ(ベクター型CPU）はひとつの
演算処理（たいていは積和算）そのものを複数のステージに細切れに
分けてパイプライン処理する。したがって同じタイプの演算命令が
次々と間を空けずに来る事が前提。

なのでベクター（行列）の処理に向くと言うか、それにしか向かない。

およよ，思いっきり勘違いされた
>マルチコア環境ではハードでなきゃ無理ということはないと思う
と書いた時点でソフトの枠組みの話をしてることが分かると思ったのだが
分かり難くてスマソ

>634
いいたいことは分かった。
スレッド同士のバケツリレー的なことを API でサポートしてるってことね。きっとイベントキューとかメッセージボックスとか使うんでしょ。
って >622の文脈であの書き方じゃわかるわけねーよ！

俺は使ったことがないが，API より上のレベル，
フレームワークが提供されていると聞いている
>じゃわかるわけねーよ！
読み直してみると確かに分かり難い．改めてすまんかった

やっぱりソフトウェア（開発ツール）レベルでパイプライン（的）
処理をサポートする枠組みがあると言う事だったのか。

>634を読んでしばらく考えてようやく意味が分かったよ。

確かにCellのSPUならマルチスレッド（マルチコア処理）で
パイプライン（的）処理をする仕組みを作りやすいかも知れないな。
キャッシュなしのローカルストレージのみで動くから
インストラクションの実行時間を確実に見積もれる。

そういう話を聞くと>617が書いてるようなパイプライン処理を
Cell(PS3)上で実現できないか、ちょっと考えてみたくなるな。
タスクをそれぞれ均等な実行時間を持つステージに分割できるか、
通信オーバーヘッドがどれくらいあるかが問題だけど。

概要レベルだが
ttp://research.cesa.or.jp/pdf/shiryo6-2-2.pdf
にCellの並列化のPipelineモデルとかStreamingモデル等の話が載ってる
（日本IBMの東京基礎研の人の講演）

>>638 THX 勉強になった

>>626 のPDFを見ても、cellってMBOXでSPUが通信できる仕組みみたいだねえ

ハードのパイプラインはクロック同期と思うが、
ソフトでも負荷の無い同期方法ってないもんか？
Stramingモデルってのが面白かった

>負荷の無い
ってどういう意味？
libspe2 には mbox と signal しか用意されてないけど
自分で作るのもあり

>>639
ハードウェアのクロック同期だって負荷があるだろ。
1クロックよりずっと短い処理だってクロック同期を待たなければならないんだから。
それでもCISCの頃よりは計算資源のアクティブ率は上がった。
ソフト側も同様にプロセッサの稼働率を上げていけばよい。

保守

4/6(日)開催予定のオープン戦案内メールをもらった。
しかしソフトはまだ全然出来ていない。
将棋を指す骨組みと通信部分だけくらいは何とかその日までに
完成させて一回は通信対戦テストをしておきたいのだが。

このままじゃ、ぶっつけ本番になってしまいそうだ。

オープン戦に間に合わなければ、
wdoorでテストしておけば？
CSAの対局サーバーとは細かい違いはあるようだが……

がんばれ

あげ

てなかった

ボナンザについて解説してるサイトがあったら教えてください＞＜

>>647
作者のサイトの　GPW 2006 発表資料　には目を通した？
あの説明で何かわからないことある？

>>648
見てなかったです．
読んでみます．
サンクスです．

>648
あれ読んでも具体的に何と何を入力パラメータとして
選んだのか今一良く分からないんだよね。

各駒種に対してその位置（升目）ごとに重み付けしていって、
それを2個以上の駒の位置関係にまで広げていったら、
あっと言う間にパラメータは1万個どころか百万個以上に
なりそうだし、学習を進めると結局、棋譜に現れたもしくは
探索済みの特定の局面に評価値を与えるだけになりそうな気が。

つまり一般化能力なんか全く無さそうな気がするんだが、
私が何か勘違いしてるのかね？
コンピュータ将棋に詳しくないために。

>>650
その論文読んでないけど、テレビでやってたやつ見た限りだと
その発想そのままだと思う。

ボナンザの初期バージョンでは数手先まで読むように拡張してみたところ
うまく読み取れない局面があることがわかった。

そこで、ある程度（？）評価の悪い枝についても読むようにしたところ
かなりよくなった。

完全に総当りじゃなくて、ある程度評価がいい手の中でも
多少悪いぐらいでは枝狩をしない
また、相手の手版のときに、多少悪いぐらいの手をさしてくることを
考慮して読んでおくことで、時間を有効に使う

一般的にどうこうするっていうのではなくて
特定の場合に愚直な実装して、枝狩りの閾値さげたら
割とうまくいきました　っていう感じだと思う。
他の検索系のやつもそうだけど
この手の総当りが必要そうなものについて、愚直に実装して
動かしてみたら案外うまくったってのが、最近の傾向じゃないかな
人間があーだこーだ考えるよりPCに考えさせたほうが
早いっていう。

だから一般化というより、ある特定のルールのときに
CPU時間を有効に使えるように変えてみたら
アルゴリズムは今までとほとんど同じだけど
勝率があがりました　って思ってるけどこれも違うかな？
あくまで素人の意見なんですが。

>>650
> それを2個以上の駒の位置関係にまで広げていったら、

広げない。

将棋は、自玉、敵玉に対する位置関係は重要だが、それ以外の2駒の相対的な位置関係は
あまり重要なゲームではないからだ。

例えば以下の記事が参考になるだろう。
http://d.hatena.ne.jp/yaneurao/20080406

ただし、銀の退路が歩で遮られていないかだとか、歩越しになっていないかだとかは重要なので、
Bonanzaでもそこは考慮に入れていたはず。

あり？　良く考えてみると二駒の絶対位置関係の
全ての組み合わせにそれぞれ点数を付与して
行ったとしても、二駒のペアは自由に選べるわけだから
特定の局面に対して点数を付けて行くのとは違うな。
汎化能力はあるか、俺が勘違いしてたわ。

それにしてもパラメータ数が膨れ上がると言う謎は残るな。
愚直にやると駒のペア×位置（マス目）×位置（マス目）で
40×39÷2×83×83で500万以上にもなるか？

>652
なるほど、サンクス！
もうちょっと考えてみよう。

>>654教授か研究者の方？

>655
いえ、違います。
ただ単にコンピュータ将棋に関心があって
（できれば自分でも作りたいと思ってる）
ボナンザメソッドに興味を持った
一介のアマチュアです。

最善手を求めるときって、引き分けがある場合はちょっと工夫が必要なのかな？
反復進化で求めると思うんだけど、その時未知の局面が現れた場合、引き分けの値との関係が難しい。
負け＜引き分け＜未知＜勝ちという図式になると思うんだけど、未知の局面の値は相手から見ても引き分けより
大きくなければならないので、単純に符号を変えるという普通の方法が使えないわけですが
何か一般的な手法があるのかなと思って聞いて見た次第です。

>>657
未知の局面て何よ？

未探索で評価値がわからないなら探索して決めればいいじゃん。
終端ノードなら、静止評価すればいいじゃん。

そんなの反復深化とも引き分けともなんも関係ないよ。

えっと、負け＜引き分け＜未知＜勝ちから分かる通り
未探索の局面を全て調べる必要がないわけですが、深さを制限しないで調べるのが一般的でしょうかね。

>>659
> えっと、負け＜引き分け＜未知＜勝ちから分かる通り

何が言いたいのかさっぱりわからんよ。

基本的なことを確認するが、あんたは普通のαβや反復深化は理解していて
自分でそのプログラムぐらいはすぐに書けるんだろな？

あんたの言う「未知」って何よ？置換表に登録されていないの意味か？

そしてその「引き分け」っていうのは、なによ？

評価したい局面で引き分けにする指し手が見つかっているのか、
それとも「引き分け」というのが存在する将棋みたいなゲームでの
一般的な探索メソッドについて話しているのかどっちなのよ。

>>653
例えば相対位置を使ったり

上の方にあった千日手関係の話？

で将棋に関するGHI問題の話の結論はどうなったの？

>>663
このスレでは >>234 の論文以上の進展はないと俺は理解している。

>663-64
結論は既に出てると思うが？
GHI問題と言うのは証明アルゴリズムの不完全性などに起因するのではなくて、
千日手などのそこまでの指し手に依存して勝ち負け（引き分け含む）が決まる
タイプのルールを持つゲーム（将棋、チェスなど）には必然的に生じる問題。

即ち、ある局面からの勝ち、負け、引き分けを厳密に判定するにはその局面に
至るまでの経路（指し手の履歴）も考慮する必要があると言う良く考えれば
ごく当たり前の話に過ぎない。

上のアンカーは >663-664 の書き間違い。

>657の言う「未知」と言うのは千日手になるかも知れないが初手からの
完全な履歴は残してないので厳密に考えると「千日手になるかどうか不明」
になると言う話なのかな？

しかし「相手から見ても引き分けより大きくなければならない」と言うのが
良く分からんな。不明な局面の場合「悪くても引分け（千日手）」に持ち込める
と言う保証なんか無いわけだから。不利な状況から千日手に持ち込もうとしても
出来ないかも知れない。

うさ将棋本に局面で乱数xorを用いるhash(zobrist hashのことだろう)を、乱数ではなく
もう少しいい方法があるらしいことが書いてあるのだが、誰か情報求む。

与えられた数列集合の要素同士のxorを何回かとるときに
なるべく衝突しないような数列を数学的に決定する方法があるのか、
それとも衝突しにくい組み合わせを事前にrandomで選んだ数列集合のうち
良いものを探してみましょう、程度の話なのかどちらなのだ？

その本のは知らないけど、以前読んだ何かのプログラムのソースでは
個々の乱数を生成したら立ってるビットの数はチェックしていたな。
うろ覚えだけど16±5くらいの範囲に収まってるかってのだったかなぁ。
この範囲に無ければ再生成。

ボナンザでいくつか質問があるんだけど，
・静的評価関数はminimax探索で利用されるんだよな？
・最適化の数値的手法１のスライドの関数f(p,ν）って何？

人工知能は学部で多少勉強した程度で将棋プログラムの経験もないんでとんちんかんなこと
聞いてるかもしれないけど，教えてください

>>669
ああ、なるほど。1のビットの数はチェックしたほうが良さそうだね。

他の乱数とのハミング距離が小さいのは捨てる
というのもあった（時間掛かるけど最初だけだからOK）

>>672
ああ、それもいいね。

>670
良く嫁。同じスライドの下に式があるだろう＞f()

序盤、中盤、終盤はどのように判定したらいいんですか?
50手で終盤の事もあるし、200手で中盤の事もあるので手数とは関係ないと思います
考えられるのは、玉の危険度で測るのがいいと思いますが定番のやり方ってありますか?

>>668
数学的な方法って無いと思いますよ　
自分でやってみた方法は、プロの 棋譜を読み込んで衝突が起こりにくい乱数を決めておくって方法です
実際に起こりえない局面で衝突が起こらなくても意味がないので

読み無しで、玉が詰みそうかどうかを判定する方法がわかれば良いのですが

>>677
> 玉が詰みそうかどうかを判定
これを読みって定義するんじゃないか？

危険度を数値化(危険度の評価関数)するって事ですよ
詰みそうならば詰め将棋を読んで、詰まないことが局面だけから判断できるなら詰め将棋をしなくて済みます
玉の逃げ道の多さが危険度に関係ありそうですけど、穴熊だとうごける所は0なのに堅いです
どのように危険度を判定するといいですか

それこそ開発者各々の know-how の部分だろ．
まずは定番の「コンピュータ将棋の進歩」シリーズを読む．
続いてゲームプログラミングワークショップの予稿集を読む．
CSA に入ってトーナメントに参加し，他の開発者から色々教わる．
本格的な議論は将棋板のコンピュータ将棋関係のスレッドで

将棋板には人いません

>>675
成駒の数とか敵陣にいる駒の数、あとは王将と攻め駒の距離とかかな。
適当に考えただけだから、実装して上手くいくかどうかはわからんが。

>679
この辺で聞くと役に立つアドバイスがもらえるかも知れないよ。
GA将!!!さん運営の「コンピュータ将棋等の掲示板＠入門編」
http://www4.rocketbbs.com/741/comsyogi.html

あるいは超有名なYSSの山下さんところの
「コンピュータ将棋や囲碁の掲示板」
http://524.teacup.com/yss/bbs

最近、掲示板@入門偏は話題が無くて止まってるからちょうど良いかも。
ちなみにダブルポストすると注意されるから気を付けてね。

サンクス

>679
ちなみに「うさぴょん本」にちょっとだけ書いてあるのを紹介すると

・玉の危険度
「玉の周囲に敵の利きがどの程度あるか、敵の駒がどの程度の距離に迫っているか」

結局、自陣(自玉周囲）にどの程度敵方の駒が利いているかが判定のキモだと思うな。
自陣に利いていても、玉ではない味方の駒で敵の駒の利きを受け止めているんなら
まだ固いと判断できるし、何にも無い空間にバシバシ利いているんなら（裸玉）、
もう詰められる寸前だろうし。

固さと玉の逃げ道の広さは当然、矛盾するところがあるので難しいところだけど。

しかし、玉の危険度と、通常の評価関数の二つがあると、どちらを優先したらいいのか混乱しますね
統合した評価関数が出来れば一番良いのですが

プロの棋譜で、2回以上現れる局面で必然手のない局面は、互角であると思います。
これを基準にして評価関数を調整するといいと思うのですが…
しかし、問題があり、2手以上出てくる中盤までしか調整が出来ません。
プロが指した手が最も得点が高くなるように調整すれば全局面に対応出来ますが
例えば、10手読みを入れた結果だとすると、評価値の値を間違えることになります。
しかし、何手読んだのか知ることは出来ず、常に一手読みとして学習したら駄目でしょうか?

>686
？？？　そりゃ、両方をひとつの評価関数として統合しないと。
と言うか、玉の危険度も通常は評価関数の一部だよ。
いろんなパラメータを重み付けして足して行くわけだ。

だから手動で調整するとバランスを取るのに四苦八苦するわけだが。

>>688
序盤か、終盤か、は通常の評価関数では知ることは出来ないと思います。　
互角であっても終盤である事があります。
終盤であることを知るにはどちらかの玉が危険であると知ることが必要と思います。
そのため、玉の危険度と通常の評価関数がないと終盤がわかりません。

先手の得点A、後手の得点Bに対して、評価関数をA/(A+B)とするならば
MAX(A,B)の値によって終盤判定が行えると思います。

>689
（通常の評価関数の一部としての）玉の危険度と
局面の進行度（終盤度）を計るための玉の危険度の話が
ゴッチャになっているね。（私が誤解したのかも知れない）

後者は例えば
序盤度×パラメータA＋中盤度×パラメータB＋終盤度×パラメータC
と言うような重み付け係数として組み込む事になると思う。

玉の危険度は終盤度（進行度）と通常の（有利不利を見る）
評価関数の一部としての両方に表れて良いと思うけど、
進行度の方はあまり凝った評価はしなくて良いんじゃ無いかな？

お互いの陣地に成り込んだ駒の数とか持ち駒の数くらいで。
飽くまで私見ですが。

5対5でも、8対2でも、最善手を指せば駒交換などの後、数手以内なら状勢は変わらないはずですね。
ボナンザはその前後で評価値が変わらないとして学習しているって事ですか。
何手先の局面と評価が一致するのかが重要ですが。

>>691
玉の危険度を正確に評価することは重要と思います。
正確に判定できれば、終盤用の指し手がさせますし、詰め将棋を調べず高速に危険度が求まります。

>>692の続きですが、評価値が保たれている局面を把握する方法は、既に知られているんですか?
ネットで見る限りでは、駒交換だけ進める様な感じと思いますが…　
しかし、それでは飛車・角・香の利きが良く利いているなどの情報は失われます。

例えば、銀は取られて、と金が作れて互角になったり、
桂は取られるけど、飛車がいい位置に移動できて互角になったりすると思います。
あとお互いに飛・角がいい位置に移動して互角になることもあります。
静止探索では、飛車が好位置に移動することも考慮しますか?

>>693
> 正確に判定できれば、終盤用の指し手がさせますし、
> 詰め将棋を調べず高速に危険度が求まります。

あんた、ほんとに将棋弱いんだな。

少しでも将棋が指せるなら、持ち歩の一歩の違いだけで
詰む/詰まないが変わることなんてしょっちゅうあることは
わかりそうなものなのに。

結局、ここからもわかるように
単純な関数で正確に評価することは出来ない。

詰め将棋なんて、静止評価に比べれば終端ノードの評価に
計算量を要しないので、詰む可能性が高そうな局面は全部調べればいいじゃん。

>>694
> 静止探索では、飛車が好位置に移動することも考慮しますか?

したければすればいいし、したくなければしなければいい。

その手の評価関数を副作用なしに書くことは非常に難しいので
シンプルな評価関数にして先読みできる量を増やしたほうが
棋力は向上すると思うがな。

例えば、三手後に詰みそうな局面が出てきたとします。
先手と後手の指し手が20通りずつあって、そのうち正解手は一手だけとして
その400通りの全てで詰め将棋を0.5秒つかったらそれだけで3分以上かかります。

静止探索でググると「　関連検索: bonanza 静止探索　」というのが出てきます。
みなさん bonanzaの 静止探索に注目してるんですね…

>>696
評価関数を書くのではなく、評価関数を自動で調整する為に静止探索をつかうんです。
プロの指し手は最善だとすると、静止の局面から、次の静止の局面への評価値に変化はないと仮定できると思います。
2つの局面で評価値が変化しないようにパラメータを決めるんです。
そのため静止局面が正しく判定出来ないと弱くなります。

野暮な突っ込みだけど
＞その400通りの全てで詰め将棋を0.5秒つかったらそれだけで3分以上かかります
0.5秒は遅すぎです。正確な時間は分からないけど１ミリ秒でも
遅いと思います。

>>697
> 例えば、三手後に詰みそうな局面が出てきたとします。

だから「三手後に詰みそう」だとどうやって正確に判定すんの？

言っとくけど王の近傍だけでは判定できないし、敵王の近傍に
自駒がたくさん利いていても、その利きによって打歩詰めになるかも
知れない。利いてりゃいいってもんでもない。

正確に判定したければ、実際に3手読むほうがよっぽど速い。

> 先手と後手の指し手が20通りずつあって、そのうち正解手は一手だけとして

即詰に関しては平均合法手は20もない。6,7ぐらい。

> その400通りの全てで詰め将棋を0.5秒つかったらそれだけで3分以上かかります。

日本語が意味不明なんだが、3手読むのに要する時間は1ms以下だと思うのだが。
一体、何の話をしてるんだ？

>>698
> 評価関数を書くのではなく、評価関数を自動で調整する為に静止探索をつかうんです。
「評価関数を自動で調整する為に静止探索をつかう」なら
その「静止探索」で使うための評価関数がいるだろ。

> プロの指し手は最善だとすると、静止の局面から、
> 次の静止の局面への評価値に変化はないと仮定できると思います。

できない。少なくとも投了の数手前には形勢はどちらかに大きく傾いてる。

あんた本当にプログラム1行でも書けるのか？
プログラムの書けないキチガイの戯言ならこれ以上付き合わないぞ。

>>701

> あんた本当にプログラム1行でも書けるのか？

今頃気づくなよｗ
どう考えても最初から素人の妄言だろ

>>701
中・終盤で2対8でもいいんです。
双方が最善を指したならば数手以内なら2対8が保たれるはずです。
例えば、いったん飛車がとられるけど、金と桂を取り返せて
初めの静止局面から、次の静止局面の評価はほぼ等しくなるはずです。
プロがミスをしないものとします。

>>700
ルートでは詰みはないけれど、探索中の3手後に詰みそうな局面が現れたとします。
このとき、全てに対して詰め将棋を計算するのは効率は悪いって事ですよ。
だから、局面から危険度が求まれば、詰め将棋をしなくて良い場合がでてくるかもしれないってことです。

ボナンザの場合、基本は一手後と評価値の変化はないものとして、駒交換が起こる場合は進めた局面と比較するって事でしょう。

>>703-705
あんたがプログラムが一行も書けない
掲示板をsageることすら知らない
日本語がままならないキチガイだって
ことはよくわかった。

プログラムが書けないなら、プログラムの勉強から先にやりなよ。
あんたが小・中学生ならいまからでも遅くはないだろう。

え、痴呆、知的障碍でなければプログラミングなんて
いつからだって間に合うでしょう。。

>>707
もちろんその通りなのだが、703の場合は日本語の勉強とかインターネットを使う勉強とか
たくさん他に勉強しないといけないことがあるように思ったんでな。

こいつはリバーシ１くさいな

いや30過ぎてからでは難しいと思うぞ＜プログラミング

どうなんだろうな
一種の芸術技能だと考えると確かに30越えはきつそうだが…

すみません、詰め将棋のプログラムつくっているんですけれども、
無駄合いの判断でつまっています。なにかいい考え方はありますでしょうか？

>>712
「コンピュータ将棋の進歩」の1を読んだらどうだ？

>712
うさ親さんの「コンピュータ将棋のアルゴリズム」にも解決法が
示されているよ。「王手を掛けた駒で合い駒を取り、その合い駒を
玉方にすぐに返した時にそれでも詰むならばそれは無駄合いである」
と言う考え方らしい。

「柿木のアルゴリズム」と呼ばれるのだそうな。

玉側の利きが無くて玉の周囲で無い駒はりは無駄合いの確率が高い。
まとめると、引きつけておいて、その駒が取れて逃れられるケース以外は無駄合いらしいということ。

http://homepage.mac.com/junichi_takada/wcsc18/

アマチャンピオンがAIに負けたようだな

山下BBSで初心者が完全スルーされててワロタ

皆さんに教えてください。　思考部分の将棋ソフトを作ろうと考えていますが。
GUIに「ＣＳＡ将棋」を使うか「将棋所」を使ったほうがいいか考えています。
他に何か良さそうな物が有れば教えてください。
行く行くはコンピュータ将棋選手権に出たいと考えています。

どちらでもいい。思考本体さえ出来れば入れ替え簡単

了解しました。では、サービスがよい「将棋所」で作ります。ありがとうございました。

将棋所ってはじめて知った。USI対応のGUIなんてあったんだ。
俺も将棋プログラムしてみようかな…

>>718
こいつ？

2回目以降の探索の確率は 投稿者：初心者 投稿日：2008年 5月 7日(水)03時15分22秒 　 　編集済
2回目以降の探索の確率は、どうやって決めますか?
１回目の探索で、たとえば、王手やそれをかわす手、飛車取りやそれをかわす手などは
高い確率にするのは当然と思いますが、2回目は得点に応じて確率を割り振りますか?
しかし、得点比率で割り振ると飛車が逃げる手が10通りあってどれもがほぼ同点だと
重要な手なのに、割り振る値は小さくなってしまいます。
かわす場合は特別で、一手であるかの様に扱うとかわしてすぐに取られてしまう手にも
高確率を与えてしまう事になります。
あと初期の確率は、完全に無視して、得点だけにするかどうかもはっきりしません。

かわす手はその時点で、一番高い一手のみを採用して、あとは無いものとして扱って
確率を分配すれば良さそうですね。その手を使って不利にならなければそのままで良いし
無視したほかの手より得点が下がればそちらを採用すればいいので。

将棋所のLaramieとか序盤がめっちゃくちゃで萎える・・・
そのくせ駒がぶつかると強くなる　将棋の勉強にちっともならない

CPUで勉強しようとする頭がオカシイんだよ＾＾たまには外でなよ＞＜

逆に考えるんだ。
序盤なんてどうでもいいんだと

yaneuraoの宣伝ブログの裏側はこうなっています。
http://www.pressblog.jp/static/pressblog.aspx
yaneuraoのブログを訪問したり、コメントしたりすると、原稿料がアップする仕組みです。

原稿料の算定基準が掲載されていないな

>>727
キチガイ帰れ

727は
http://d.hatena.ne.jp/yaneurao/20080510
弓月とか言うキチガイの模様。

集客力のあるブロガーほど報酬が高いのは当たり前

731は弓月とか言う知能障害者っぽいな
http://d.hatena.ne.jp/yaneurao/20080509

ここのところ屋根裏は毎朝宣伝こいてるな

集団ストーカー激指＆やねうらおはもはや有名

弓月とか言うキチガイは、あの天下のやねうらお様に遊んでもらえて幸せだな。

>>733-734
お前はお前用のキチガイスレに帰れ
http://love6.2ch.net/test/read.cgi/sf/1177547691/

>>736
この弓月とか言う精神障害者用のスレは、こっちじゃね？
http://science6.2ch.net/test/read.cgi/sci/1165122111/

以上、集団ストーカーの実演でした。

>>738
お前は、半角入力すら出来ない知能障害者

なるほど。
--
727 名前：デフォルトの名無しさん[ＳＡＧＥ] 投稿日：2008/05/20(火) 13:34:56
yaneuraoの宣伝ブログの裏側はこうなっています。
http://www.pressblog.jp/static/pressblog.aspx
yaneuraoのブログを訪問したり、コメントしたりすると、原稿料がアップする仕組みです。

731 名前：デフォルトの名無しさん[ＳＡＧＥ] 投稿日：2008/05/20(火) 14:46:03
集客力のあるブロガーほど報酬が高いのは当たり前

733 名前：デフォルトの名無しさん[ＳＡＧＥ] 投稿日：2008/05/20(火) 14:57:35
ここのところ屋根裏は毎朝宣伝こいてるな

734 名前：デフォルトの名無しさん[ＳＡＧＥ] 投稿日：2008/05/20(火) 14:59:45
集団ストーカー激指＆やねうらおはもはや有名

738 名前：デフォルトの名無しさん[ＳＡＧＥ] 投稿日：2008/05/20(火) 17:54:45
以上、集団ストーカーの実演でした。
--
判りやすいと言うかなんと言うか……

やねうらおは明日も宣伝をこく。きっとこく。

全角の人以外に空欄はいないので（略）

>>741
お前激しくスレ違いだから以下の精神病患者スレに移動願う。。
http://love6.2ch.net/test/read.cgi/sf/1177547691/
http://science6.2ch.net/test/read.cgi/sci/1165122111/

なんだこいつ・・・きめえ・・・

詰め将棋を研究して数学的になぜ詰めるのかが分かればその延長線上に最強プログラムがあると思うよー
あとチェスでいうオープニングの研究もしたほうがいいと思うよー

詰め将棋は既に十分に強いんです

ki2　書式の質問です。
▲７六歩 △３四歩 ▲２六歩 △４四歩 ▲２五歩 △３三角
▲４八銀 △４二飛 ▲６八玉 △３二銀 ▲７八玉 △７二銀
▲５六歩 △４三銀 ▲５八金右 △９四歩 ▲９六歩 △６二玉
▲５七銀 △６四歩 ▲３六歩 △７一玉 ▲８六歩 △５二金左
▲８七玉 △７四歩 ▲７八銀 △８四歩 ▲３八飛 △３二飛
▲６六歩 △５四歩 ▲６七金 △６三金 ▲６八銀 △８二玉
▲７七銀右 △４五歩 ▲７九角 △５五歩 ▲３七桂 △５四銀
▲５五歩 △同　角 ▲５六金 △４四角 ▲５八飛 △２六角
▲４五金 △５三歩 ▲５四金 △同　歩 ▲４三銀 △３三飛
▲５四銀成 △同　金 ▲同　飛 △３七角成 ▲４六角 △３六馬
▲４四飛 △４三歩 ▲６四角 △７三銀打 ▲４六飛 △６三馬
▲４二角成 △５二金打 ▲３三馬 △同　桂 ▲３一飛 △２五桂
▲３四飛成 △３七角 ▲５四金 △６二馬 ▲２五龍 △５三歩
▲５五金 △１九角成 ▲６五桂 △４六馬 ▲同　歩 △５七飛
▲５八歩 △１七飛成 ▲３三角 △６七香 ▲５九金 △６八歩
▲１八歩 △３七龍 ▲１五角成 △３九龍 ▲４八馬 △１九龍
▲３七馬 △３九龍 ▲４八馬 △同　龍 ▲同　金 △６九歩成
▲６七銀 △７九と ▲２九龍 △８九と ▲同　龍 △５四歩
▲７三桂成 △同　馬 ▲６五金 △５三桂 ▲５四金 △５五桂
▲７八銀 △２七角 ▲５三金 △同　金 ▲６五桂 △５四角成
▲５七金 △６四馬上 ▲５六香 △６三金 ▲８八玉 △７三桂打
▲２一飛 △６五桂 ▲同　歩 △同馬右 ▲６六銀打 △６四桂
この棋譜において最後の行の△同馬右です。これは△同馬直と書くのが正しいと思うのですが。
柿崎将棋では正しく処理されています。何故なのでしょう?
右と書いて右に無ければすぐ下を探すというのが正しいのですか?
ちなみに直と書き直しても正しく処理されました。

自己レス。同じような記述を複数見つけ、これが正しいと理解しました。　お騒がせしました。

>>745
色々考えた結果、最強はデータベースっぽいアプローチなのかなと思った。

chessは序盤と終盤がデータベースで済むんだが……

将棋は中盤に入ると毎回、一度も過去に出ていない局面が毎回大量に出てくるので、
100TBぐらいでは全然歯が立たないみたいなんだよな
データベースに全部収まるとカッコイイんだが

要は、ある局面を評価できればいいだけなので、
データベースとしてデータを持っておくことに意味があるわけではない……

チェスの終盤は、ポーン2個vsポーン2個くらいの状況でも
普通のコンピュータで完全に読みきることは出来ないくらい難しい。
データベースがあると終盤をかなり上手く指すようになるけど
思考力は人間の半分以下

ネタ提供？　2ch棋譜の内40433件の分析したデータ
＊：先手の勝ち数：後手の勝ち数：＊：＊：戦型
1:739:626:0:0:その他の戦型
2:1282:1131:0:0:横歩取り
3:1994:1785:0:0:中飛車
4:4975:4259:0:0:矢倉
5:4208:3825:0:0:四間飛車
6:1647:1608:0:0:相掛かり
7:516:378:0:0:角交換腰掛銀
8:37:33:0:0:袖飛車
9:928:749:0:0:向飛車
10:1699:1679:0:0:三間飛車
11:646:617:0:0:相振飛車
12:114:121:0:0:右四間飛車
13:847:754:0:0:角換わり
14:737:822:0:0:ひねり飛車
15:40:43:0:0:筋違角
16:123:81:0:0:右玉
17:297:227:0:0:陽動振飛車
18:56:38:0:0:５筋位取り
19:139:144:0:0:角交換その他
20:50:60:0:0:角換わり棒銀
21:34:17:0:0:角換わり拒否
22:18:13:0:0:風車
23:38:20:0:0:棒銀
24:29:23:0:0:タテ歩取り
25:93:98:0:0:雁木

＊：先手の勝ち数：後手の勝ち数：＊：＊：棋戦
1:968:881:0:0:王位戦
2:5715:5183:0:0:順位戦
3:837:764:0:0:ＮＨＫ杯
4:1525:1229:0:0:竜王戦
5:146:128:0:0:日本シリーズ
6:228:196:0:0:朝日オープン
7:1438:1385:0:0:その他の棋戦
8:788:680:0:0:棋王戦
9:71:65:0:0:達人戦
10:1503:1308:0:0:棋聖戦
11:741:745:0:0:銀河戦
12:133:107:0:0:レディースオープン
13:865:820:0:0:王座戦
14:653:540:0:0:新人王戦
15:269:212:0:0:名人戦
16:40:43:0:0:朝日アマ名人戦
17:249:230:0:0:勝ち抜き戦
18:127:125:0:0:女流王将戦
19:102:99:0:0:倉敷藤花
20:490:434:0:0:早指戦
21:1122:943:0:0:王将戦
22:116:108:0:0:女流王位戦
23:212:203:0:0:女流名人戦
24:73:80:0:0:近将カップ
25:130:96:0:0:三段リーグ
26:101:104:0:0:早指新鋭戦
27:10:9:0:0:中学生名人戦
28:20:28:0:0:アマ王将戦
29:10:21:0:0:赤旗名人戦
30:59:53:0:0:全日アマ名人戦

30:59:53:0:0:全日アマ名人戦
31:13:22:0:0:平成最強戦
32:31:25:0:0:グランドチャンピオン
33:55:63:0:0:鹿島杯
34:25:30:0:0:アマ竜王戦
35:604:538:0:0:全日プロ
36:28:22:0:0:レーティング選手権
37:2:4:0:0:学生王将戦
38:12:20:0:0:小学生名人戦
39:19:15:0:0:学生名人戦
40:11:13:0:0:女流アマ名人戦
41:13:25:0:0:ＩＢＭ杯
42:177:170:0:0:天王戦
43:95:84:0:0:若獅子戦
44:411:333:0:0:名将戦
45:430:309:0:0:十段戦
46:48:41:0:0:若駒戦
47:76:94:0:0:連盟杯戦
48:19:16:0:0:名棋戦
49:100:100:0:0:奨励会
50:43:53:0:0:最強者決定戦
51:27:16:0:0:古豪新鋭戦
52:82:87:0:0:九段戦
53:19:44:0:0:東京新聞杯
54:36:40:0:0:支部対抗戦
55:4:1:0:0:学生女流名人戦

56:1:0:0:0:新春お好み対局
57:1:0:0:0:細：九段設定戦
58:8:10:0:0:アマ女王戦
59:10:7:0:0:育成会
60:47:61:0:0:都名人戦
61:8:4:0:0:高校竜王戦
62:1:3:0:0:その他の棋戦　　　　　
63:28:18:0:0:大和証券杯
64:1:0:0:0:ＮＨＫ杯　　　　　　
65:0:2:0:0:順位戦　　　　　　　
66:38:30:0:0:朝日杯
67:22:31:0:0:マイナビ
68:0:1:0:0:倉敷藤花戦

＊：先手で勝ち数：先手で負け数：後手で勝ち数：後手で負け数：名前
1:585:178:491:253:羽生善治
2:644:304:539:378:谷川浩司
3:187:180:155:208:島　　朗
4:119:87:122:108:三浦弘行
5:105:88:83:95:畠山成幸
6:258:130:229:176:郷田真隆
7:216:163:203:206:南　芳一
8:90:62:82:77:真田圭一
9:128:92:132:105:中田宏樹
10:341:156:272:202:森内俊之
11:260:103:237:180:丸山忠久
12:208:125:180:150:藤井　猛
13:533:332:468:370:中原　誠
14:363:173:307:224:佐藤康光
15:57:41:62:44:松尾　歩
16:102:83:93:105:日浦市郎
17:97:96:98:69:畠山　鎮
18:179:121:150:143:阿部　隆
19:108:57:115:56:渡辺　明
20:155:104:155:115:中川大輔
21:39:57:29:59:伊藤博文
22:226:205:189:243:桐山清澄
23:169:110:153:130:先崎　学
24:84:58:69:82:北浜健介
25:94:44:96:55:山崎隆之
26:67:85:56:100:前田祐司
27:184:206:145:204:青野照市
28:68:52:58:61:石橋幸緒
29:49:52:53:55:矢内理絵子
30:59:39:53:46:近藤正和
以下省略

>>752みて思ったんだけど将棋の戦型って曖昧だよな
四間飛車だけだと先後どちらが振ったか分からないし、角換わりだけやたらと分類されてたり
もっとスマートに記述する方法はないの？

定跡データベースの樹形図で葉の数が均等になるようにすればよい

DNAの解析を各自のコンピュータで分析した結果をあつめて
実現しようっていうのがあったとおもうけど
それと似たように分散している計算力をあつめて全ての局面を評価するってできない？

分散処理は既に行われてるが全ては無理

将棋も囲碁もその場が今どちらが有利かなんて人によって考えが違うに決まってる

だから色んな人工頭脳をもった将棋プログラムを作ればいいと思う

俺には無理だけど

ログも読まず低レベルながらに頑張って口出ししては消えていく
そういう輩が時々現れるよね

９ｘ９の盤面に8種類のコマが自分と相手の分あって、あとは空だから
81**(8*2+1) で、ルールの制約があるからこれよりもっと少ないと思う
http://www.google.co.jp/search?hl=ja&rlz=1T4GFRD_ja___JP238&q=81**%288*2%2B1%29&btnG=%E6%A4%9C%E7%B4%A2&lr=

それまでの手がどうであってもルール上許される配置のどれかになる
でルール上許される全ての局面に評価値をつける

勝敗が微妙な局面もあるけど、そこから
自分の勝ちの局面に少ない手で到達できるとか
相手の打ち方によらず確実に勝ち局面に到達できる手とか
があるほど評価値を高くするって案はどう？

>>763
成りがあるから81**29か
http://www.google.co.jp/search?hl=ja&rlz=1T4GFRD_ja___JP238&q=81**29&lr=

で特定局面から持ち駒も含めて別の局面へ遷移する手を考える
つまり各局面間の遷移に分割して解析する

>>764
ちがうわ 29**81かｗ
81C40 * 29**40 でもいいか？

81C40 * 29^40 = 6.65363027 × 10^81
http://www.google.co.jp/search?hl=ja&q=%2881+choose+40%29*29%5E40&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=

このスレの過去スレを読みたいのです。どこかで見れますか?
又は、持っている方UPお願いいたします。

つ　http://usapyon.dip.jp/shogi/computer/index.htm

ありがとうございます。

どういたしまして

仮にすべての局面を評価できるとしたら、投了直前の局面をすべて生成して勝ち負けつけて
開始局面に向かって戻っていくだけだから、連続的な評価値なんて不要

>>771
戻して行く？
どこで手駒を使ったかまで遡れるのか？

>764
（現在の）局面状態だけを見て各局面への遷移を分類するのは難しい。
あちこちにループが発生する。詳しくはこのスレを頭から良く読んでね。

>771と>772が想定している「全ての局面」の意味が違うようだな。
つまり、その局面に至る経路情報を含めて分類してるのか、
経路情報は捨てているのか？

将棋でこういうデータ調べてる人っているの？
http://www9.atwiki.jp/othello/pages/27.html

>775
居ないんじゃないかな？
オセロや囲碁と違って将棋は終盤がなかなか収束しない。
終局図が何通りあるのかも良く分からんし。

>>771
投了局面から「詰めろ？」を遡ることで
投了局面より前の局面の勝敗を決定できるのは確かだと思う

だけど更に遡ると、遡ったのとは違う経路で将棋が進んで
違う結果の局面になることがあると思う
一手で形勢逆転するような手があると思う

>>773
ループは枝刈りするとか対策は考えられるんじゃないかな

目標の中間局面に到達するまでの手の経路は
手数が多くても少なくても勝敗には関係ないよね
最短でなくて遠回りしてもいい

さしてるうちに、最初目標としていた中間局面じゃなくて
自分に有利な別の中間局面に変えてもいいし

・ルール上可能な局面（駒の配置図）はそれぞれがネットワーク状に「手」で繋がる
・局面のサブセットにだけ勝敗の評価が決まっているものがある
・局面の遷移がかなり限定されていれば（詰めろみたいに）勝敗の評価を決められる
・そのほかの局面は手によって評価が変わる
って感じのイメージを持ってる

上の方で議論になっているけど
将棋の「局面」を見て形勢を判断するためには
単なる盤上や駒台の様子だけではなく
その局面に至るまでの経緯も必要

極端な話、たとえば指しかけを引き継いだとして
「この盤面は敵玉に詰みがあるぞ！」と思っても
それは千日手の４回目かもしれないとかそういうこと

>777-778
末端局面から遡って勝ち、負け、引き分け（千日手）で
確定的にラベル付けするだけじゃなく、
途中局面に中間的な評価値を付けようって事？
おもしろい考え方だが、一体どうやって？

末端局面からさかのぼるのなら途中も当然
「勝ち」か「負け」か「引き分け」になるだろうって

>>779
> それは千日手の４回目かもしれないとかそういうこと

(現在の技術で可能かどうかは知らんが)データベースを引くのだから、現在の局面に
至るまでに詰みがある局面を逃しているはずはないと仮定できるだろう。

だから、連続王手の千日手のことは考慮しなくて良いと思う。

>>779
ソフトが「この盤面は敵玉に詰みがあるぞ！」と思って指したら。
システムから千日手で引き分けと言われるだけで。その事にソフトは何の関係が無いわけ。
それを操作した人間が、あちゃ〜〜前に勝ってたのか、と思うだけ。
それに何の問題があるのか?

引き継ぐ前の事を意識する必要は無い。

>781
もちろん、そうなんだが >777-778が何か面白いアイデア持ってないかな？と。
例えば勝ちに至る経路の広さや近さで評価値を付けるとか。

なんかminmax法も分かってない奴がいるな

>>786
いや、「神ならぬ人間がその盤面を引き継いだとして
どれほど勝ちやすいか」っていう評価値じゃね？

>>782
自分についてはそういう仮定を置くのもアリかもしれないけど
少なくとも相手のことについてはまずいだろう

「うむ、俺が勝つにはこの手しかない！
　でも相手にこう王手されるとまずいな…
　しかたない。勝ちはあきらめて千日手に持ち込むか…」

というようなケースってあるじゃんか

ところがこの相手の王手が千日手の４回目かもしれない

>>788
与えられた局面が勝ちか負けかを判定するデータベースを構築する話をしているんだろ？

相手がポカして相手が勝てる局面を(その勝ちのための指し手を連続王手の千日手で)負けの状態に
してようが、それはデータベース構築には何の関係もないことだろ。

引き継いだ前の人間の意識を、引き継いだソフトは考慮する必要は無い。
もし考慮して欲しいなら、その旨のインターフェースを作るべき。
しかしその人間の目的を読み取る機能は、最強の将棋ソフト作るより遥かに
困難な人工知能が必要。

いや、なんかおまいら話が変な方向へ
ひとまず>>165-395あたりは読んでくれ

>789
実はそのデータベースを構築する事そのものが、その局面に至る経路を考慮する事を要請する。
さもないと探索あるいは末端局面からの遡りが止まらなくなる。

良く考えてみないと分かりにくい事だが、なぜ千日手のルールがあるのかを考えてみよう。

>>789
「それは関係ないことだから関係ないのである。」
では説明になってないぽ

だからさ、一連の流れのある局面が、他の流れのある局面と同じと言う事は無いのかと、言う事だろ。

流れとか「局面」とか、意味のあいまいな言葉を無定義で使うなよ

隣の将棋盤の駒の配置と持ち駒の数や種類が、その隣の違う対局の数時間前のときの全く同じ将棋盤の駒の配置と持ち駒の数や種類がある手において、同一だったと言う事は無いのかと言ってる。

>795
「流れ」と言うのはある局面から別の局面に至る経路の事だよ、多分。
>794じゃないけど。

で、違う経路から見かけ上同一の局面に至る事は
それこそ幾らでもあるし、ループする事もある。

評価値として
勝ち、負け、千日手、勝ちか千日手、負けか千日手
を定義すれば局面評価DBを作る点では問題無くない？

>>798
問題ないかどうかは、どういう目的で作るのかによるけど

そもそもそのような評価が、駒配置だけを見て可能か
ということに対して懐疑的なんだと思うよ

今の指し将棋プログラムは現状の局面状態（駒割と駒の配置）だけで持って、
盤面を評価してるように見えるから　>789のように勘違いする人も居るんだよね。
ところがその評価はかなり荒い近似に過ぎないから通用するのであって、
厳密に確定局面から遡って評価しようとするとそこに至る経路情報が必須になる。

詰め将棋プログラムは確実に経路情報を考慮してるし、しないと答えを間違う。
いわゆるGHI問題。

経路情報は局面間を結ぶ有向線として持てると思う
勝ち負けの決まる局面は確かに存在する
これらの情報で中間局面をどう評価するかだけど
相手の手が何であっても勝ち局面に遷移できる局面は勝ちたが
相手の手によって勝ち千日手負けのいずれも有りうる局面もあると思う
そんな局面は勝ちやすさで評価する
勝ちやすさは例えば勝ち評価値の局面への距離とかで決める
そんな単純じゃないと思うけどね

>>800
俺はコンピュータ将棋の開発者で、GHI問題はもちろん知っている。
GHI問題を正しく理解していないのはお前のほうだろ。

詰みのあるすべての局面の集合から逆算してんだぜ？
GHI問題なんか起こるわけないだろ。

ただしそこに至るまでに同一局面が3回以上出てきていないという条件が必要だが。
(連続王手の千日手を発生させないため)

>>802
>ただしそこに至るまでに同一局面が3回以上出てきていないという条件が必要だが。

おいおいw

>>803
お前、頭おかしいんじゃねーの？

> 俺はコンピュータ将棋の開発者で、

権威づけか

>>805
実際に作ってもない/作れない/作ったことがない奴に言われたくないね。

作ってるのに理屈がわかってないんだとしたら
そっちの方がよっぽど問題のような…

そんなに俺様の言うことを聞けって言いたいなら
コードの断片でもうｐしてからにしろよ

できないならおとなしく名無しに戻っとけ

>>807
理屈がわかってないのはお前。

お前はGHI問題が何故発生するのかわかっていない。

>俺はコンピュータ将棋の開発者
イタイ奴が来たなｗｗｗ

頭おかしんじゃね？

>807
詰め将棋解法プログラムのような答えが
厳密に求められる問題に取り組まないと
開発者と言えども勘違いする可能性はあるな。

>>810
お前もGHI問題が何故発生するのか理解できていない。

>>808
いや俺は横から茶々を入れてるだけで
何も言ってないんだけどな

自分以外（正確には自分に異論をいう奴）を全部
一人の人間だと思っちゃうっていうのは
ありがちなことなんだけどかっこよくはないよ

GHI問題については>>191あたりから始まって
>>234とかの議論でさんざんがいしゅつなんだけど
もちろんそのへんはログ読んだ上でのレスだよな？

しかも「お前はわかっていない」とかじゃなくてさ、
だったらちょっと簡単にでいいから説明してみろよ
ほら

経路君のソフト楽しみにしてます＾＾

>>812
詰み局面から逆算するんだぜ。GHI問題なんか起こらないよ。
GHI問題が起きるのは、探索中の循環を即、不詰めと判定するからだ。

GHI問題でよく話題になる図を勝ちの局面であるIから逆算して行くとわかる。

お前ら、シャープの亀山工場で液晶を組み立ててる工員が
みんな液晶の仕組みを理解してるだなんて思ってないだろ？
そういうことだよ

>814
どのように逆算するの？
つまりその逆算する時に経路情報を考慮するの？しないの？

>>814
あー詰み局面から逆算していく話が続いてたのか

その場合で、局面というのは駒配置だけじゃなくて
局面の出現回数も持たなきゃいけないよな

そうしないと、千日手になるはずの手順は
永遠に「勝ち」とも「負け」とも塗られないことになる

ような気がするんだが

○→○→○→○→○
　 　 　 　 ↑　 　 　 ↓
　 　 　 　 ○←○←○

こういうループだけじゃなくて

○→○→○→○→○
↑　 　 　 ↓
○←○←○

こういうループもあるよな

>>816
経路情報を考慮しないし、する必要はない。
ただし循環は検出する必要がある。

具体的に書くと

Iが勝ちとわかっている局面。よって、直前のGも勝ち。その直前のEも勝ち。
Eに至る手順はB,K。Bは相手の手番なのでDを選択されて負け。よってBは負け。(勝ち局面の集合にBは含めない。)
Kは勝ち。たどって、Jも勝ち。Hも勝ち。Hに至るのはE,F。

Eは自分の手番だし、勝ちだとわかっている局面。よって、Eのほうの探索はここで打ち切り。
残るはF。Fは勝ち。その直前のCも勝ち。その直前のAの局面は自分の手番なのでCを選んで勝ち。

よってAは勝ちの局面。GHI問題なんか発生していないし正しくAの局面の勝ちを判定できている。

ちなみに>>789は意地悪だから図を書いてくれないけど
>>234のPDFを参照な

>>818
　　　　 　 　./ﾆＹﾆヽ
　r､r.rヽ. 　/ （0)(0）ヽ
r |_,|_,|_,|／　 ⌒｀´⌒　＼　　　で？っていう
|_,|_,|_,|_,|　, -）　　　　（-、.|　　　
|_,|_,|_人　(^ iヽ＿＿ ノ　l |
|　)　　 ヽﾉ　|　 `ー'´ 　 ／
|　　`".｀´ 　ﾉ
　　　入＿ノ
　＼＿／
　　 ／
　 /

>>817
> あー詰み局面から逆算していく話が続いてたのか

続いているも何も、最初から最後まで、詰み局面をデータベース化しよう、という話なのだが。

具体的には、これだ。
http://d.hatena.ne.jp/KZR/20080531/p1

>>820
すまない。俺は意地悪なんじゃなくて図とか苦手なんだ。ほら…わかるだろ。

>>817
> その場合で、局面というのは駒配置だけじゃなくて
> 局面の出現回数も持たなきゃいけないよな

「局面の出現回数」は持たなくてもいい。

>802で書いたが
「ただしそこ(判定したい局面)に至るまでに同一局面が3回以上出てきていないという条件が必要」だが、
これを前提条件とできるなら「局面の出現回数」のデータベースへの記録は不要。

ただし、勝ち/負け/引き分けとラベリングされた局面はすべて記録(データベース上に保持)していることが前提。

>>882
あれ、与えられた局面が勝ちか負けかを判定するデータベース
つまり必勝定跡を構築する話をしているんだと思ってたんだが

そして、その「局面」というのが駒配置だけでよいのか、それとも
駒配置の出現回数も持っていなきゃならないのかだと思ったが

経路という言い方をするからGHI問題と絡んでいるように見えて
いろいろみんな混乱したるんじゃないかな


それで、仮に、駒配置だけで勝ち負けが決まるのだとしたら
もちろん「この局面は千日手」というラベルを貼られる
局面（駒配置）もあると思うのだけど、
詰み局面（駒配置）からたどっていったとき
千日手のラベルを貼る機会というのはどういうとき？

あと、終盤のデータベース化については >822 以外にも

http://d.hatena.ne.jp/mkomiya/20080601/1212289142
http://d.hatena.ne.jp/yaneurao/20080602

このへんも参考にしてくれ。

>>825
> あれ、与えられた局面が勝ちか負けかを判定するデータベース
> つまり必勝定跡を構築する話をしているんだと思ってたんだが

その過程で引き分けデータベースも出来るだろ。

> そして、その「局面」というのが駒配置だけでよいのか、それとも
> 駒配置の出現回数も持っていなきゃならないのかだと思ったが

俺の言う　局面　とは　盤上の駒配置・手番。その局面の出現回数は関係ない。

>>824
あー、その条件があればたぶんそうだよな
でも前に進むなら、ループしたら「千日手」、でいいと思うけど
後ろに戻っているのだから難しい気が

まあ、どうせ局面（駒配置）の数は有限なのだから
全部調べて「勝ち」にも「負け」にもならなかったものは千日手
でいいのかもしれないけど

>>825
> 詰み局面（駒配置）からたどっていったとき
> 千日手のラベルを貼る機会というのはどういうとき？

いま、 A,Bが未ラベルとする。Aは自分の手番、Bは相手の手番とする。
このとき A→B→A のような循環を発見した。

AからB以外に行く手は負けとする。
BからA以外に行く手は勝ち(＝相手の負け)とする。

このとき自分にとっても相手にとっても千日手を選択するのが最善だからA,Bの局面の最善は引き分け。

このように未ラベルの局面同士の循環を発見して、この循環がお互いの最善であるときこれらの局面を
引き分けのリストに追加する。

825はどうも勘違いしているようだが、このA,Bの局面の「出現回数」を記録しておいてもこの循環の検出の役には立たない。