おまいら最強の将棋プログラムしてみろよ part6
あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あー面倒くさい。あー面倒くさい。 あ
ゴメンネ! オレ必至すぎてゴメンネ! ボナの最適化アルゴリズムが実は「強化学習」なんじゃないかなー? と思い始める前に 森北出版の『強化学習』R. Sutton・A. Barto著 (原著:Reinforcement Learning: An Introduction) をネット書店に注文していて、ちょうど今日届いたもんだから ちょっと舞い上がっちゃっててね。 そうであってくれると嬉しいんだ。 (でも、もしそうなら既に実現されていて、ちょっとくやしいw)
強化学習って環境との相互作用から学習するというやつで バックギャモンのそれは自分との対戦から学習していくという方式 ボナンザのは探索こそしているけれど、環境との相互作用とはいいにくい だから、強化学習とは違うと思う。 どちらかというと統計的学習じゃないのかな
wikipediaのコンピュータ将棋の項を見ていて、 人工知能という単語が目に入った瞬間コーヒーふいた
まあ、昔から人工知能の課題とされて来たものは研究がある程度進展した 段階で必ず、もはや人工知能の課題とはみなされなくなって来た。 音声認識も自動翻訳も人間との(簡単な)会話もチェスも将棋も。 どれもまだ全然完全じゃないんだけどね。 (その昔、チェスを機械に指させる事はリッパな人工知能の課題だった) つまり「人工知能」って言うのは見果てぬ夢に対して付けられる 看板であって具体的な課題、技術、手法の事じゃないんだよ。
なるほど
>>11 の定義って一般的なの?
別にコンピュータチェスとか将棋とかが人工知能でも違和感ないのだけど
人工知能系の学会ではチェスや囲碁は研究されてないのかな
14 :
デフォルトの名無しさん :2007/04/08(日) 16:09:08
>どちらかというと統計的学習じゃないのかな 正解
パターン認識は流石に外れてるかな ゲームはまだ人工知能に含まれてる プランニングは十分人工知能だし(ゲームもプランニングの一種)
プランニングって何? 計画を立てること?
中学生でも知ってる単語だろうが
ごめん俺消防だから教えて
行動計画だったかな。 目標状態を得るための行動の組み合わせと順序を探索他で決定するやつ。
要するに巡回セールスマン問題とかナップザック問題とか言う奴だろ。 実用的にはLSIの配線とかにも利用されてるようだが。 研究者から見れば十分にAIの研究かも知らんが、素人目には これがAI研究ですって言われてもなあ……ジミだ。
アルゴリズムが発見されると、人工知能の課題でなくなっちゃうんだよな。
機械的に手順を踏めば解決しちゃうから。
>>20 それは線形計画法で実用上解決された。
AIとみる人はいないでしょう。
NPCみたいに人間の代打扱いするのが人工知能 道具扱いすれば人工知能じゃなくなる、と考えちゃ駄目?
俺は人間も本当の知能ではなくて自動機械だと考える派だから 人工知能という物ができたならそれは人間を超えてないとダメ
>それは線形計画法で実用上解決された。 線形なものしか扱えませんが。 人工知能の定義として 人間の知能を構成するために必用な技術の総体 というのでどうでしょう? 問題が与えられた時に、 「人間はどうやって問題を解いているのだろう?」 と、人間と対比して考えるのが、 人工知能分野の特徴だと思いますが。 >人工知能系の学会ではチェスや囲碁は研究されてないのかな 難しいので直接扱う人はいません。 小手先の改良をしただけでは研究にはなりませんので。
どうでもいいけどお前らほんとに将棋プログラミングしてみてるのか? ゲ作厨が流入しているだけにしか見えんのだが。
26 :
デフォルトの名無しさん :2007/04/12(木) 21:46:16
>>25 漏れはROMに近いが一応作ってるよ
先週のオープン戦には参加してきた
>人間と対比して考えるのが、 >人工知能分野の特徴だと思いますが。 素朴な考えだけど実際は違う 人工知能は「知的」な作業を機械化する技術を開発する分野 やり方が人間と似てる必要も無いし人間と対比させる必要もない ニューロモルフィズムと言うのがあなたの考え方に近いけど少数派 人間がどうやってるかを考えるのは認知科学(とか神経科学)
>要するに巡回セールスマン問題とかナップザック問題とか言う奴だろ。 ぉぃぉぃ もっと複雑なアプリが山ほどある 例えば介護/警備/レスキューロボットの行動計画とか 大規模な組み合わせ最適化問題は今でも十分AIの研究テーマ 連が木スマソ
3球体問題は解けるの?
30 :
デフォルトの名無しさん :2007/04/13(金) 15:41:20
>人工知能は「知的」な作業を機械化する技術を開発する分野 知的の定義は?
知的とは人間に出来てコンピュータには出来ない知的行為のこと。
それじゃ人工知能の研究の意味ないじゃんw
人間の脳も機会と同じく生体分子の形態で思考していると思うよ
>>29 物理の三体問題のこと?
人工知能とは全然違うと思うけど、いまだに、というか永久に厳密解を
得ることは不可能ですよ。
>知的の定義は? お好きなようにどうぞ だから人工知能の定義も人によって異なる
37 :
デフォルトの名無しさん :2007/04/20(金) 13:54:43
>人工知能は「知的」な作業を機械化する技術を開発する分野 じゃあ、これは妄言だね
お前が将棋プログラミングに全く興味がないのはわかったからあと10年ROMっとけ。
将棋だとアルファベータとモンテカルロってどっちが強いのだろう 今のところアルファベータが主流な感じだが
大差なし、同じようなもんだ
>>40 モンテカルロ法を用いた将棋24でレーティング2000以上のコンピュータ将棋ソフトを
是非教えていただきたい。
やだ
そりゃボナンザ違いでんがな。
マサルさんのボナンザを思い出した
46 :
デフォルトの名無しさん :2007/04/30(月) 15:37:14
おまいら、そろそろ最強の将棋プログラムとやらに とっかかってくださいよ。
SK"2
人が切れ負けになるまで「本当に成らなくてよろしいですか?」ダイアログを出し続ける
49 :
デフォルトの名無しさん :2007/05/02(水) 19:50:54
51 :
デフォルトの名無しさん :2007/05/03(木) 21:17:55
>>7 強化学習と機械学習の差を強調して書くなら、こんな感じ。
最適(と思われる)行動が教示されるのが機械学習で、Bonanzaはこれ。
将棋で言うと最善手が教示される(実際にはプロが指した手=最善手と見なしているが)。
過去の(≠直前の)行動に対して報酬が与えられるのが強化学習で、実現したソフトは(選手権参加ソフトが公開している情報を見る限りでは)まだ無い。
将棋で言うと勝ったから100点の報酬をあげる、とかそんな感じ。
まぁ、実際には他にも色々差があるわけですが。詳しい事は7氏の買った本に載ってます。
ちなみに私は構想中。来年の選手権はそれで出ます。
52 :
デフォルトの名無しさん :2007/05/03(木) 23:45:39
53 :
デフォルトの名無しさん :2007/05/04(金) 13:57:44
プログラム作りたい! 今からとりかかる。 まずは盤だ。 来年は遠いねー。
54 :
デフォルトの名無しさん :2007/05/04(金) 22:36:48
将棋の局面の良し悪しの判定ってどういうふうにやってるの? コンピュータにまともな判定ができるとは思えないんだけど。
駒の損得とか駒の位置関係とか玉の堅さとか・・・
強化学習は機械学習と相反するものじゃないだろう 過去の最善手を参考にしながら局面のよしあしに点数をつけるんじゃないかな。 で、反意語は教師なし学習で、これはグループ化、クラス分けをしていくことによって条件判断していくものだったと思う
57 :
7 :2007/05/05(土) 00:23:33
>51 説明してくれてアンガト。 まだ、あの本読み始めてないけど(英語なんでとっかかるのに気合が要る)w。 でもナーンか、挑戦状を叩きつけられたような気がするのは気のせいでしょうか? 相手は私ではなく多分、他の将棋プログラムを開発している方々なんでしょうが。
58 :
7 :2007/05/05(土) 00:25:26
あ、こっちは英語じゃなかったか。 最近買った別の本と混同しちまったw。
59 :
デフォルトの名無しさん :2007/05/09(水) 11:19:00
結局は旅人の釣りであったか・・・
コンクリートの上で垂直式ブレンバスター。 さすがのジャイアンも・・・ 旅人恐るべし。。
これは凄いな
遅いって言うかWiredは最近までずっと休刊?してたわけだが
それは旬を外れた記事を載せる理由にはならんだろ
大学が休講になっちゃった。 暇だから将棋の続きやるか。
>67 早稲田ですか?
はしかで休講になったとこはいっぱいある
昨日の午後、突然休講になった大学はそんなに多く無いと思う。 まあ、どうでも良いけどさ。
71 :
51 :2007/05/22(火) 20:37:31
激しく今更だけど、
>>51 の“機械学習”は“教師あり学習”の間違いでした。
勉強しなおしてきます。
72 :
リバーシ1 :2007/06/07(木) 18:41:55
GHI問題って、手数の少ない局面の得点は足し込まないようにすれば 不詰みを、詰みと間違える事はあっても逆はないはずだよね? 詰みが、判定できたら実際に指し進めて、ループしている部分があったら その先が詰むかどうか調べればいいんじゃないの?
ちょっと作ってみようと思ったんだけど、やっぱりC言語がいいのかなあ。 できればC#で作りたいんだけど実行速度遅いんかなあ。
>>73 元々C#使いだったんだけど速度に不満が出てきてCに移植してみたら3倍違った。
C#は何かあれば例外投げてくれるからバグに気づきやすいんだけどね。特に配列関係とか。
今でも一部のコードではC#でバグが無いように作ってからCに移植ってのは時々やってる。
Cに移植(笑)
>74 ふーん、そういうやり方でうまく行くんなら俺もまずJavaで書いておいて C++に"移植"すると言うやり方でやってみようかな。 うさぴょんの育ての親さんのJavaで作るコンピュータ将棋の本も出てる 事だし。
そういうのはほんとはコンパイラの仕事で、賢いコンパイラは 自分で工夫してくれる(べき)ものなんじゃないかと むしろ、そういう工夫を人がしなきゃいけないというのは Cの大変な点といっていいのでは
>>C言語では、配列の添字に2のべき乗を使うと、内部計算がビットシフトで表現され高速化されるので、配列はすべて2のべき乗にするとよい。 真っ白な鷽ですが。 x86系CPUのビットシフトが遅いのは有名な話だし、インデックス計算みたいに頻繁に出てくるコードは コンパイラとしては腕の見せ所ですから素人が小手先で弄ったCコードよりもよっぽど効果のあるコードを出します。 まぁ、高速化の基本は実測にあるといっても過言ではありません。
>>77 実行時最適化ができるVM上での動作の方が速くなることも多いよ。
だからLLVM
ttp://llvm.org/ なんかが開発されてる。将棋プログラムのような分岐の多いプログラムなら
Cで書くよりも最終的には速くなるかもしれない。
ただJavaやC#で計算が遅くなるのは配列を使うとき。要素へのアクセス全てが
範囲内かどうかチェックするから行列計算とかが入ると絶対的に遅くなる。
>C言語では、配列の添字に2のべき乗を使うと、内部計算がビットシフトで表現され高速化される
これは多次元配列だけだな。でも本当に効率化をしたいなら行単位でポインタを
指定するからあんまり意味のないテクニックだと思う。
その理屈だと別に2のべき乗にしてもあまり害はないよね?誤差程度のメモリを食うだけで。 デフォルトの名無しさんのいうこととYSSの作者の言うことがちがった場合、普通はYSS作者を信じるだろうから2のべき乗で行くのが懸命だね。 もしそんなことはないっていうのなら嘘ってソースを見せて欲しい。 あと、実測は高速化の手段じゃなくて確認じゃない?
82 :
81 :2007/06/09(土) 01:44:47
>>80 ってことはJAVAやC#で書いて、Cで作ったDLLを呼び出すのでFA?
前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みたいにアホな設計の場合でそ。
92 :
デフォルトの名無しさん :2007/06/10(日) 11:54:54
>>77 山下さんの勘違いがあって、全て2のべき乗にする意味はないでしょう。
1次元配列A[x]は*(A+x)で掛け算は出てきませんし。
2次元配列でも一番左側の添字は2のべき乗にする必要はありません。
93 :
デフォルトの名無しさん :2007/06/10(日) 12:05:05
>>88 これは失礼ながら全く見当違い。
2のべき乗にするかどうかという議論はあえて余分な領域を取るかどうかという話で、
計算回数が増えるわけではありません。
>>93 分かってますよ。
1.配列の先頭のアドレスが2^nになるとアドレスの計算が速くなるか
2.ポインタのアドレスがラインにヒットさせることを常に心がけるべきか
ってことが問題で、もう少し複雑にNを64にしても走査する範囲を63にすればいいだけです。
だから「計算回数分だけ」Nが63の方が速いと言っているので、見当違いはそちらでしょう。
95 :
94 :2007/06/10(日) 14:42:37
と、分かりにくいかもしれないので追記。
もし配列の要素数を2^nにするのがよいのだとしたらNが64の方が計算回数が多くても
それを覆すほどの利点があって速くなるはず、あるいは一つの計算あたりのマシンタイムは
確実に速くなるはず、という前提で言っているので、計算回数あたりの時間が同じであった
という実験の結果から、配列の要素数をどうするかは目に見える違いにはならないという
結論を導いたので、私の意図を
>>93 には理解してもらえてないのだろうな、ということです。
96 :
92,93 :2007/06/10(日) 15:42:44
>>95 「計算回数あたりの時間が同じであった」というのは元々は書いてありませんでしたが。
あと現在のまともなコンパイラーなら最適化によりあなたのプログラムでは配列へのアクセスに掛け算は発生しないと思います。
つまりA[i][j][k]へのアドレスの計算をいちいち
A+i*N*N+j*64+k
などとしなくてもfor (k=..)のループなら直前のアドレスをインクリメントするだけ、
for (j=..)でも64を足すだけでいいので。
将棋ではもっとランダムなアクセスになるのでこの実験では結局何も分かりません。
97 :
92,93 :2007/06/10(日) 15:49:06
どうでもいいことですが >>A+i*N*N+j*64+k はA+i*N*64+j*64+kですね。 86の例では。
>>93 じゃあたとえばA[i][j][k]みたいな多次元配列なら、j,kは2のべき乗のほうがはやかったりするのですか?
100 :
92,93 :2007/06/10(日) 23:42:53
>>98 速いかどうかは環境によりますから実験してみるしかないでしょう。
私が書いたのはA[i][j][k]の場合ならiを2のべき乗にしてもシフトやかけ算と関係ない、というだけです。
まあiについてはわざわざ2のべき乗にしてもサイズが大きくなるだけ損だとは思います。
101 :
デフォルトの名無しさん :2007/06/26(火) 21:09:07
てかさ、そんな枝葉の事よりもっと重要な評価関数とか探索ルーチンとか考えてるの? >ALL
探索ルーチンは多少悪くてもハードウェアの進歩でどうでもよくなる 問題は評価関数だよ 評価関数が悪ければいくら探索が速くても休むに似たりだ じゃあ、良い評価関数とは何か? それはプロの手を良いと感じ、ヘボの手を悪いと感じる評価関数 少なくとも、現状で手に入る簡単な指標としてはそうだ つまりプロの棋譜を教師とする自己学習を本旨としたボナンザで 将棋プログラムは最終形を迎えたわけだ もう将棋プログラムに費やして得るものは何もないよ ボナンザで将棋プログラムは終わった
バカキタコレ!!
104 :
デフォルトの名無しさん :2007/06/27(水) 01:55:09
>>102 全然終わってないでしょう。
実際ボナンザはすぐ切れ筋に陥ってしまうようなまだまだ弱いプログラムだし。
自己学習というのも大きな誤解。
人間が決めたパラメータを最適化しているだけ。
>102 コンピュータ将棋ソフトを作ってる、あるいは作ろうとしている人間は 例え内心ではそういう事を思っていたとしても決して口にできないな。 口に出したら、じゃトッププロに勝てるものを作ってみせろと 言われるに決まっているから。 本気でそう思っていたら何も言わずに黙って手を引くしかないだろうが、 やっぱり本当にその手法で可能かどうか実地にやってみたくなるのが 人情ってもんだろ。 幕を引くのは自分でありたいって事だ。
逆に評価関数簡素化してパワーでプロ棋士を押し切るなんともショボーンな結果になりそうな悪寒
107 :
デフォルトの名無しさん :2007/06/28(木) 10:36:05
>106 それは俺も心配。 ただ、シンプルだけどそこそこ正確な評価関数ってなんだろ?とは思うが。
>>107 敵玉が詰み = +1点
自玉が詰み = -1点
持将棋成立 = 0点
先手千日手 = 0点
後手千日手 = 0点
あとはパワーでw
109 :
デフォルトの名無しさん :2007/06/29(金) 19:19:40
>108 ごめん、俺には無理。
なあ、今からC++やJavaで指し将棋ソフト作っても あんまり変わり映えしなさそうだから、Lispで 書いてみようかと思うんだがオマイラどう思う? Lispプログラミングを勉強がてらたがw。
112 :
デフォルトの名無しさん :2007/07/07(土) 17:49:43
113 :
112 :2007/07/07(土) 19:40:36
>>111 Lispではないけど関数型言語を使っているらしいチームが
5月の選手権には何度か参加登録してる
たしかOCamlだったか…
楽しみにしてると参加取り消しだったりした
実際に出場したことがあるかは不明
115 :
デフォルトの名無しさん :2007/07/08(日) 22:28:36
>>111 別に利用するプログラミング言語で変わり映えをつけようとしなくてもいいと思うが。
弱ければ単なる色物で終わってしまう。
116 :
111 :2007/07/08(日) 23:13:18
>115 単なる色物にすらならない(ただの弱いソフト)よりはマシだろ? それにあんまり良く分かってないが、アルゴリズム的にも面白い 事ができるかも知れん。Lispを相当深く理解して使えたらだけど。
弱けりゃ何で作っても一緒
>120 誤爆かあるいはただの宣伝かい?
122 :
デフォルトの名無しさん :2007/07/15(日) 23:15:41
プロ棋士に勝つ方法 1.詰めろアルゴリズムを詰める。 2.必死アルゴリズムを詰める。 3.終盤の速度計算をする。 4.定跡データベースを詰める。 5.乱戦模様に誘導する。 6.NECのSX-8iを借りる。 モデルはタイガーウッズ。序盤即終盤。
「詰める」を「詰みを読み切る」と思って意味がわからんかった
124 :
デフォルトの名無しさん :2007/07/16(月) 13:11:18
>122 SX-8iってベクトル機だよ? 今主流のコンピュータ将棋が高速に動くとは思えないが? あと、マルチポストうぜぇ。
125 :
デフォルトの名無しさん :2007/07/16(月) 13:12:22
>122 それから、「乱戦模様」の「定跡」を作ろうって言ってる? がんばってね。
>122はあちこちにマルチポストしてる愉快犯だから相手にしないように。
127 :
デフォルトの名無しさん :2007/07/16(月) 20:22:02
必至だなw
129 :
デフォルトの名無しさん :2007/07/17(火) 17:46:58
既に詰んでますw
>122はPonanzaというソフトの作者の保本さんです。
俺今日
>>131 のニュースを読んで思ったんだけど、将棋は完全解析できないけど人間相手なら無敵という物なら作れるんじゃ?
自然淘汰を取り入れた自己進化するアルゴリズム同士をスーパーコンピューターで戦わせまくれば人間より強い定石を見つけるんじゃないかな?
>132 将棋はチェスやチェッカーと違って終盤でなかなか手の広さが収束しないんだよ。 もちろん取った駒を盤上の好きなところに打てるからだが。 おかげで終了局面からさかのぼって局面をデータベース化するのがとてつもなく難しい。 終盤データベースなしに学習させたところでそれは解全体のほんの一部の実戦例から 学習させる事になるので正しい学習をする(正しい定跡を発見する)かどうか怪しい。
>>131 そんなのは昔から解明されていた。しかし誰も認めなかっただけの話だよ
その記事も当てにならない、科学的に示すには論理的仮説と多面的な反証
があってこそ科学として認められる、その解明とは単なる思い込みの域
にすぎない。つまり10手先を読んで模擬して解明したのと18年かけて
解明した悟ったという差にしかすぎないわけだ。
>>134 なにに反応したのか、当たり前のこと並べて楽しいのか?
んな常識的なこといってもつまらんだけ。
コンピュータ将棋が最強なんて考えている乙君が沸いてきそうだ。
>>134 では三色問題も解かれてないと主張するのですね?
137 :
デフォルトの名無しさん :2007/07/24(火) 21:17:16
計算機の速度を考慮する場合と、計算機の速度を度外視する場合は別に考えてね
140 :
デフォルトの名無しさん :2007/07/24(火) 22:40:01
>>139 誰に対しての発言?
意味がよく分からん。
132に一言いいたかったんじゃね
将棋でやるとなると相当なマシンパワーが必要だな アルゴリズムを進化させるアルゴリズムも作るのも大変そうだ
>>143 最初は歩だけしか動かせないアルゴリズムや角だけを狂ったように使うアルゴリズムが出てきて面白そうw
でも普通の対局できるレベルになるまで何千万世代もかかるだろうね。
いや、進化させるっていうかたまに突然変異を混ぜればいいのか それが環境に対してダメな進化(退化)だったら淘汰されるだけか
>>142 スパコン同士を戦わせたら何百億円もかかるから採算絶対にあわない。
実現困難な"夢"と非現実的な"夢物語"の間には大きな違いがあるよ。
132はリアルに中学生かもorz
>>142 その結果って公知じゃないのか?
その研究はせいぜい学部生の宿題レポのレベルだし
>146 最近はスパコンを無料で貸してくれるところがあるよ、大学で。 地球シミュレータも有償だが借りられるし、そんなに高くはない。 まあ、ベクター計算機をこういう用途には使いづらいだろうが、 超並列スカラー型なら結構使えるんじゃないかな? 何百億円もかけたら自分で好きなタイプを作れてしまうな。
>146 これは非現実的の範疇には入らないと思うが。 「採算」の事を考えてる時点で現実的じゃん。 非現実的ってのはもっと、今後どんだけ科学が発展しても無理!ってものの事を言わないか?
最強のとか言ってる時点で現実的じゃないような気もするけど。 理論的な最強を目指しているのか?現時点での暫定的な最強を作りたいのか? 前提が定まっていないような
153 :
デフォルトの名無しさん :2007/07/27(金) 00:00:00
人間破ったらそれでいいんだ まずはコンピュータの頂点を目指す
154 :
デフォルトの名無しさん :2007/07/27(金) 02:13:59
>>142 リンク先を見た。オマオレ、と思った。
俺も中高生の頃こんな感じで大学入ってから忙しくて中断
した口。でもこの人の学習手法はGAに成ってない。
交差と突然変異が無きゃ駄目だし、実際問題として
純粋な弱肉強食だと、変な局所最適にすぐ陥ってしまう
ので、ヘボい遺伝子も少し残さないといけない。
その加減が難しいんだけど。
>>151 上のチェッカーにも有るように「全探索」してしまえば
間違いなく最強だろ。
NP完全問題の全探索は絶望的に大変だが、チェッカーや
6x6オセロくらいまでなら実現してる。ガンガレ。
>154 「ガンガレ」って誰に言ってるのか知らんが、将棋の全探索は無理だろう? いくらなんでも現状では。 量子コンピュータが実現するとか、ものすごい理論でも発明?されない限り。
全探索というゴールが存在するという事実は重要じゃないか? あとはそれにどこまで近付けるか、あるいは到達するか
157 :
デフォルトの名無しさん :2007/07/27(金) 12:45:10
>>155 量子コンピュータができれば、将棋の必勝解を一瞬で計算できます。
時間など不要です。
なぜなら量子コンピュータは手順という概念を組み立てる方法では計算しないからです。
将棋というルールを因数分解して必勝という答えを導きだす。
その計算された手順を取り出す(現状は取り出せない)。
量子演算は無限の並列計算ですから無限の計算ができることになります。
みなさんも量子コンピュータを応援しましょう。
応援なんかよりアルゴリズム考えろよ
>>157 量子コンピューターでもNP問題を解くのは難しいって何かで読んだ、
チェスなら
>>157 に書いてあるように完全解析できるだろうけど将棋はどうなんだろう?
そもそも将棋は全探索できる数学的証明がないと分からん。
160 :
デフォルトの名無しさん :2007/07/27(金) 13:36:26
>>159 チェスは無限に続くかもしれんが、将棋は同一局面3回出たら引き分け
順番からいって次はオセロだろう いやまぁ自分は量子コンピュータのことよくわかってないんだけどね
162 :
デフォルトの名無しさん :2007/07/27(金) 13:39:56
単純にいって、駒は8種類で成りを加えて、14通り 合計40枚だが、それを考慮しないことにして 高々配置可能な種類は15の81乗程度
163 :
デフォルトの名無しさん :2007/07/27(金) 13:41:40
敵味方を忘れた 将棋の可能な配置パターンは29の81乗以下 それすべてに、勝ち負けを設定すれば将棋は完全に溶けた
配置可能なパターンはそれだけでも 次の手番がどっちかとか何回目に出た局面かで勝ち負け引き分け変わるでしょ。
>>164 素人考えだけど、手番はともかく、何回目に出た局面かは
必要ないんじゃないかな?だって最強のもの同士が闘っているのだから、
その局面が出た瞬間に、これは無限ループ=千日手と解るはずだから。
んぁ〜、あつはなついなぁ〜
手番は2通りしか無いんだし、2通り作ればいいだけだな。
>>163 それだと一秒間に一兆パターン調べても終わらないいんだがw
何で今更そんな議論を
>>160 チェスにも同じルールがあるよ、次に完全解析されるゲームはダイヤモンドゲームじゃ無いかと予想
最後まで解けないのは囲碁。
同じ局面が3回というのはルールだろうけど、それを記録できなければ 無限に終わらない罠。記録できてこそ3回一致を判定できる罠。
174 :
デフォルトの名無しさん :2007/07/27(金) 22:13:05
>>173 あれ、囲碁って先手の6目(7目?)勝ちって解明されたんだっけか?
教えてクンですまん。
>>174 囲碁も将棋同様に解かれてないよ。
囲碁は人間モンテカルロ法で先手有利のような結果が出てるだけで。
ちなみにオセロでも同様な方法だったら後手有利のような結果が出る。
しかしちゃんと最善'候補'のゲーム木を構築したら引き分けの可能性が高いという結果が出る。
オセロって完璧に全手解明されてなかったっけ?
>>176 オセロ(通常は8x8の事)もまだ解明されてないよ
6x6盤は解かれてるけど
8x8は解明したと力説する奴は結構いるんだけどな。 ぽえむ君だから仕方が無いんだけど、
>165の意見は強烈だなぁw。 一目、局面を見ただけで千日手(無限ループ)だと分かる? 今まで何回、同じ局面が出てきたか記憶しないで? 最強の者同士が戦ってるってどこから来た仮定? 例え将棋の神様であっても、これまでに現れた局面を 記憶しない限りループにはまってるかどうかは分からんだろ? 久々に笑わせてもらったよ。
>>180 おまえ変だ
完全に勝敗が決まっていたら、勝ちか負けか千日手しかない
>181 意味不明!
全ての局面と試合結果の組データを構築する場合 局面・・・駒の配置と手番の情報だけが必要 結果・・・その局面から全探索した結果(勝ち・負け・千日手)だけが必要
>184 同じ形の局面でもそれが何回目の出現かを区別しないで どうやって千日手だと判定するんだ??? もしかして特定の形をした局面が千日手になるか ならないかはその形から自動的に決まると思ってる?
>>185 勝ちでも負けでもない局面はあいこだろが
>>185 だからそれは別の問題なんだって。
そっちの話題に関してはもちろん思ってないよ。
188 :
デフォルトの名無しさん :2007/07/28(土) 01:35:13
それよりお前ら開発してるのか?
>>188 スレは見てるけど最近将棋の開発はしてないなー
ちょっと前は高速化のためにSSE2の勉強やってたけどどんなところに使えるかな
だから特定の局面の勝ち、負け、引き分けを 正確に判定するためにはその局面に至る手順で 区別して扱わない限りそもそも不可能なんだよ。 言葉だけで説明するのは非常に難しいので、 後は"GHI問題"でググるなどして自分で勉強してくれ。 ちなみに特定の局面から全探索する場合、 そこから先の局面は手順により区別されている。 ところが探索の開始局面にその区別がなかったとすると 情報は蓄えられずにどんどん失われて行く。
>>180 ,
>>185 どんな探索をしていっても、自分が勝った局面に、どちら側がどう工夫しても
持って行けない局面は、探索ツリーの中で閉じたループ状の構造となる。
ループ状の構造であれば、、局面の数は莫大とはいえ有限なので、
それを辿っていくと同じ局面が必ず繰り返されるので、千日手。
言いたかったのは上記のことで、ツリーの構造を議論するのに、
時系列で追う発想はもはや必要はない、ってこと。
>>191 >ところが探索の開始局面にその区別がなかったとすると
>情報は蓄えられずにどんどん失われて行く。
この部分の解説希望
失われて行く情報とは?
>>194 191は頭悪いよ
詰め将棋を解く(勝敗を決定)する事と、
すでに決定されている事の区別が出来ていない
千日手が決定している局面は、そこに至る手順に関係なく千日手なんだよ
197 :
デフォルトの名無しさん :2007/07/28(土) 02:07:06
>>165 で言っている事と
>>196 は同じ事だ
>最強のもの同士が闘っているのだから、
>その局面が出た瞬間に、これは無限ループ=千日手と解るはずだから
つまり
1) 探索ツリーを作る段階での議論
2) すでに完成した探索ツリーの構造の議論
がゴッチャになっているのかな?
その点では、
>>191 氏にもミスはあるように思うが、
でも「GHI問題」ってのが 1)ではあるんだね
ちょっとググって勉強してみるよ 情報サンクス
>193 千日手になるのは単純な見て分かるループだけじゃない。 大きな流れの中で同一の節(局面)を4回通過するだけで起きる。 千日手にならない手順と容易には区別できない。 局面だけで区別するとゲーム木はツリー構造ではなく メッシュ構造になるので辿りかたが全く決まらない。 そこら中がループしていて、 ループしていないところとの区別は存在しないんだよ。
>>199 将棋の完全解析は不可能、を主張しているということでOK?
201 :
デフォルトの名無しさん :2007/07/28(土) 02:23:33
>>199 手順は関係ない
勝ちと負けと引き分けしか無いのだから、局面が与えられればそれは決定するんだよ
探索によって結果が変わるなら、その探索が間違っているだけだ
勝敗が決定する局面では、次の指し手は一つに絞られる 千日手の局面では、一つに絞られないから、確かにメッシュ構造になるんだろう でも、ループでもメッシュでも、ノードの数は有限だから、やはり千日手は千日手 確かにループになるって書いたのは間違いだったけど、 最初の議題「何度目の局面の情報は必要か」っていう点では、同じ結論になるんじゃないかな?
>200 >201 違う、違う。 その局面に至る手順により区別して(別の物として) 扱わない限り、その局面が勝ち負けか引き分けかを 決定できないと言ってるんだよ。 つまり局面をその現れる順番で展開したゲーム木を作れば良い。 手順に関係なく局面が与えられれば勝ち、負け、引き分けが 決定するはずと言うのが単なる思いこみなんだよ。
>>201 局面pがあって、その子供がc1,c2のみで、ともにXの負けの(一手詰みの)局面とする。
GHIがない場合、後退解析では
c1, c2の局面がXの負けとわかる->c1,c2だけを子供に持つ局面pはXの負けとわかる
だけど、もしGHIがあったら、pに来た時点で経路によっては4回目の同一局面になって、
引き分けになるかもしれない。
連続王手の千日手になってXの勝ちになるかもしれない。
だから、pの局面は結局勝ち負けが一意に定まらないというわけ。
それでも完全解析は理論的には可能で、要するに局面数Nだったのが、
ある局面に至るまでの経由局面を全て考慮しなくてはならないと言う意味で、
最悪の記憶量がO(N!)になるというだけでしょ。
ずいぶん爆発的に増えちゃうとはいえ、どちらの場合にせよ天文学的な局面数なので、
まぁそんなにまじめに考えてもしかたないと思うけど。
>>203 > その局面に至る手順により区別して(別の物として)
> 扱わない限り、その局面が勝ち負けか引き分けかを
> 決定できないと言ってるんだよ。
「区別が必要」という仮定で、手順により区別して
勝ち負けか引き分けかを決定したとするよね?
そうすると完全解析済みになるよね?
後は完全解析済みの結果を参照するだけでよいよね?
再解析の必要は無いよね?
その局面は参照するだけで、勝ち負けか引き分けか決定してるよね?
これは、あなたの主張する「区別が必要」と矛盾するよね?
この矛盾は、仮定が間違っていいたためであり、「区別の不要」
ということになる。
証明終わり。
これ背理法っていうんだけど、問題ある?
>>205 よーく言いたいこと解った!!サンクス!!
後退解析だけでは駄目なんだね 経路が必要なんだね
で、結局、局面だけでは判断できない・・・ってことか
ちょい目から鱗が落ちたよ 漏れの勉強不足を痛感した
208 :
デフォルトの名無しさん :2007/07/28(土) 03:05:35
例えば、勝ちと判別されている局面があったとして 勝つ手順がわかっていたとしても、 既にその局面が3回現れていたとしたらそこへは指せない と言うことなんだろ???しかし、この場合、1回目で勝っている
>>207 局面だけ決着しているって
おまえも頭が悪いやつの仲間入りか???
GHI問題というのは、探索の中で現れるだけで実際に指した手ではないんだぞ
一回目で、勝ち負けが決していたら2度目は無いダロが
>>206 氏の意見は、O(N!)とO(N)がゴッチャになっていて、
「局面へ至る手順により区別」と「局面による区別」がすり替わっているように思う
その点において、
>>203 氏の意見の方が正しそう
O(N!)からO(N)への射影は、一意には決まらないのじゃないか?
>>205 氏は、それをもって「決定できない」と言っているのだと思うよ。
>206 問題があります。 なぜなら勝ち、負け、引き分けが決定するのは飽くまでそこに至る手順により 区別された局面であり、その区別を外して形だけで同一視した局面は 一般的には決定不能だからです。
212 :
デフォルトの名無しさん :2007/07/28(土) 03:14:01
GHIとか言ってるやつは、よく聞け!!! 勝ち負け引き分けが分かっていたら、同じ局面は2度現れない よく考えろ!!
>>210 確認。
完全解析の定義は「すべての局面の勝ち負けか引き分けかを決定すること」。
認識は、あってる?
「局面へ至る手順により区別」して、完全解析する。
完全解析後に、「局面による区別」し、参照する。
問題あるなら何行目か具体的に指摘してくれるか?
>>211 完全解析の定義は?
で、完全解析はできるのできないの?
215 :
212 :2007/07/28(土) 03:22:26
同じ局面が現れるならそれは千日手である、という点が抜けていた
216 :
212 :2007/07/28(土) 03:24:29
手順に関係なく完全解析は出来るよ 勝ち負けが決している局面は1度しか訪れないし、2度訪れるなら千日手 ただこれだけだ
217 :
212 これ嫁 :2007/07/28(土) 03:28:03
二人零和有限確定完全情報ゲームは、 ゲーム理論で扱われるゲームの分類のひとつである チェス・オセロ・石取りゲーム・囲連星・連珠・五目並べ・三目並べなどが該当し、 偶然に左右されない読みの深さを競う。 概要 これに分類されるゲームの特徴は、理論上は完全な先読みが可能であり、 双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か 引き分けかが決まるという点である。 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回目が現れたらその途端に千日手になるわけじゃない。
千日手のパラドックス
225 :
212 :2007/07/28(土) 03:37:52
>>223 イメージ的に、対局で、詰めろが回避できないと諦めた段階で投了するか、
詰まされるまで指し続けるかの違いかな。
>>209 , 212
スマン、「で、結局、局面だけでは判断できない・・・ってことか」は、
後退解析の途中で現れる局面についての話題ってことに読み直してくれ。
しかし完全解析って、後退解析以外にそもそも定義できなそうだから、
正しくは後退解析の実行手順の問題と言い換えるべきか? これで正しい?
>222 うん、つまりはそういう事。 すでに以前、局面Aを3回通過してれぱ頑張っても千日手にしかならないが、 そうでなければ(2回あるいは1回通過)勝ち筋があるというわけ。 そして局面Aから現在の局面に来たとしても、必ずしもそこに戻るとは限らない。
>>223 神同士が対局してるものとして、
同じ局面が現れる(2回目)って事は、仮に千日手ルールが無ければ3、4、5・・・回目も必ず現れるよね?
んで千日手ルールがあった場合、2回目が現れた時点でその局面は千日手(4回目)なのと同じでしょ?
なんだかプログラマというより数学板みたいな感じですね
>>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 勝ち、負け、引き分けのラベルを貼る=神同士の対局
>>234 ひとまずその2ページ目は見た
言いたいことはわからないでもないが
それは探索の実装の問題ではないかね
ハッシュが誤作動するとかいう問題と
結論がどうであるかということとは関係ない
もっといいアルゴリズムに替えたらいいだけ
この例でいえばEは「千日手」が結論なわけで
何も不明解さはないだろう
連続王手の千日手はまた別にして。
>233 GHI問題は、必ずしも「後退解析」(←これって勝ち筋から手を逆算していくことですよね?)の問題じゃないみたい 手順を追ってツリーを構築していく際に、ある経路では、千日手のように”みえる”局面が、 別の局面では勝ち筋に必要な局面ということ もちろん探索の途中で、うっかり千日手と 登録してしまったところに問題があるのであって、本当は、当然詰む局面 そもそも局面をハッシュしなければ、こういった問題は生じない ハッシュするにしても、なんらかの形で辿った経路を情報として残せば、問題ない また、図1で最初にA→Cと探索すれば、最初からこんな問題は生じない とりあえずGUI問題について語るには、上のPDFの2ページ目を読もうよ さっきから漏れも色々考えているのだが この論文の2ページ目以上に、簡単にGHI問題を説明するのは無理ぽ
>237 初手からの神同士の対局と任意、それも手順を含めた 任意の局面からのそれをごっちゃにしてない?
243 :
デフォルトの名無しさん :2007/07/28(土) 05:00:06
>>242 解析中と解析後はちゃんと区別しろよな
解析後に同一局面が出てくるなら引き分け、そうでなければ同一局面は出てこない
神様同士の対局というのは、完全なる「次の一手」マシンのことだろ 完全なる「次の一手」マシンというのは、どんな局面を与えられても 勝ち筋があればそれを指し、なければ千日手に持ちこめる順を指し、 それもなければ何か指すというようなものだと思う このようなマシンを作成することと、すべての局面の勝ち負けがわかる 完全な一覧表を作ることは等価だよ マシン作成→与えられた局面からマシンに一人将棋をさせる→その勝ち負け 一覧表作成→有効手の中から、移行後の局面が「勝ち」であるものを (なければ「千日手」を)さがす→それが次の一手
現時点での漏れの結論 1) 完全な後退解析が出来れば、 局面だけで勝ち・負け・千日手が解る(→完全解析) 2) 現実のアルゴリズム(これは後退解析でない)で ツリー構造を作るには、ハッシュ表を使うことが多い 3) むやみにループする局面を千日手としてハッシュ表に登録していくと、 本来の勝ち筋を千日手と間違える問題が生じる(GHI問題) 4) 上記問題を回避するには、ハッシュ表に、千日手と判断するに 至った経路を登録して、局面だけでなく経路を区別する必要がある 5) 4)の事情があるために、「局面だけでは勝ち負けは決まらない」という 誤解が生じている
それじゃあ任意の局面が与えられてそこから次の一手を決定する時、 そこまでどんな局面(経路)を辿って来たかについてどんな仮定を置いて 決めるんだい? どんな経路を辿って来たとしても同じだと言うんならその根拠は?
「後退解析」をよくわかってないんだけど何かいい資料無い?
ひとり何役やってるの? まあ、役者不足、ってやつだよね。
最低3〜4人は居そうだけど
252 :
デフォルトの名無しさん :2007/07/28(土) 05:22:22
>>248 次の一手問題なら経緯は調べないだろが
勝ち負けの判定ならその局面へくる前に勝敗か引き分けが決まっている
>>248 いや別に
その「完全なる次の一手全集」を見ながら
バカみたいに指していくだけでいい
もしその局面からは千日手が最善なのであれば
全集には千日手になる手が書いてある
それを指せば、もし一回目や二回目なら
また同じ局面に戻ってくるわけだし
三回目なら、千日手になる
>>251 俺、俺より賢い奴、俺と同じくらいの奴、変なことを言う奴
の少なくとも4人はいると俺は思ってる
あと、見てる奴や1レスくらいしかしてない奴が多数
255 :
デフォルトの名無しさん :2007/07/28(土) 05:26:32
>>248 不完全な指し手が指したところから、勝敗を判定するなら
千日手は考慮しなければならない
データベースは使えない
>>256 横からだけど、ちょっと待って
棋譜は有限だから、「指し手履歴込みの局面」も有限
それらをすべて列挙して勝ち負けを調べればよい
で、「同じ局面でも、指し手履歴の内容によって結論が異なる」
という現象はあるのかないのか
そこが本当の焦点なんじゃないのかと思う
>>257 「同じ局面でも、指し手履歴の内容によって結論が異なる」 と「区別の必要」の違いは?
とにかく、他にどんな問題があっても、単純に
>>206 を否定できなければ
「区別の不要」という結論は覆らないでしょう。
260 :
248 :2007/07/28(土) 05:45:24
>256 区別が不要だといったいどこで証明されているんだ? 206の主張はトートロジーだよ。 区別が不要だから不要だと言ってるに過ぎない。 >246の1も未証明な仮定だと思うぞ。
>>259 えー俺は釣られてるのかな
それとも俺がバカなのか
> その局面は参照するだけで、勝ち負けか引き分けか決定してるよね?
具体的にはここだろう
今は「区別の必要がある」という仮定で話をしているのだろ?
そして、手順を区別した上で勝ち負け表を作ったのだろ?
つまり、同じ局面でも手順が違うものは別物として勝ち負けを
判定したのだろ?
それを整理して、局面だけから勝ち負けがわかるようにするのだろ?
でも、その整理ができるという保証がないよ
「区別の必要がある」という仮定のもとでは
つまり、区別ありの表から区別なしの表を作るときに、
もし区別ありの表において、ひとつの局面が
手順によって勝ちだったり負けだったり結論が異なっていたら、
区別なしの表にまとめることはできないじゃないか
そして、「区別の必要がある」という仮定はまさに
手順によって結論が異なるかもしれないという意味だ
だからこれは「他の問題」なんかじゃなくて本質的な問題だよ
263 :
248 :2007/07/28(土) 05:58:14
あー、ようやく分かってくれる人が居た。
>>261 > つまり、区別ありの表から区別なしの表を作るときに、
「区別ありの表」とか、「区別なしの表」なんていらない。
単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
完全解析とは、その一つの表を埋めて、完成させること。
解析後は、「局面情報と手番」から「結果」を参照するだけ。
>でも、その整理ができるという保証がないよ
後で整理する作業は発生しない。
全く問題にならない。
よって、
>>206 の否定にはならない。
反論をお待ちしています。
>>264 おまいさん釣りだろう
議論ごっこなら付き合わないぞ
> 「区別ありの表」とか、「区別なしの表」なんていらない。
> 単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
> 完全解析とは、その一つの表を埋めて、完成させること。
> 全く問題にならない。
これらは
>>206 の論証の結果として得られるものだろう
それを論証の過程で使うのは「結論先取の詭弁」という詭弁
>>264 >「区別が必要」という仮定で、手順により区別して
>勝ち負けか引き分けかを決定したとするよね?
>「区別ありの表」とか、「区別なしの表」なんていらない。
まず仮定をぶち壊してるけどこれOKなの?
>>261 おまえが言っているのは、完全解析が不可能、ということじゃないか?
完全解析は「すべての局面の勝ち負けか引き分けかを決定すること」。
つまり、表を正しく完成させるということだぞ?
>264 「完全解析とは、そのひとつの表を埋めて、完成させる事」 と言うそれが可能だと言う保証がどこにも無いんだよ。 後で整理する作業が必要ないと言うならそれを作る手順は?
>>266 > >区別ありの表」とか、「区別なしの表」なんていらない。
> まず仮定をぶち壊してるけどこれOKなの?
言葉が、足りませんでしたか。
完全解析時の作業用の表は、たくさん必要です。
完全解析を行った結果出力として、
>単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
という表があればよい。
ということです。
完全解析ができるということは、この表を得ることができるということです。
反論をお待ちしています。
>>267 いや、いま問題になっているのはそうじゃないよ
将棋のルールは、一見、局面(駒の配置と手番)だけでは
勝ち負けが確定しないように見えるじゃんか
同じ手でも千日手になる場合とそうでない場合があるからね
つまり、将棋において状態とは、駒の配置と手番だけではなくて
「局面の出現回数の履歴」も含めたものでなければならない
そう考えられるわけだよ。素朴には。
でも、もちろん感覚的には、そんなことはなくて、履歴などなくても
局面(駒の配置と手番)だけで判断がつくように思える
その感覚が正しいかどうかがいま問題になっているのだよ
将棋というゲームの状態変数として「駒の配置と手番」だけで
十分なのかどうかと
ルールを素朴に読んだだけでは、不十分に思えてしまうわけで
>>268 「将棋の完全解析は不可能」を主張しているわけだ。
これが不可能なら確かに
>>206 は成り立たないね。
でも、基本的に
>>217 にもある通り「可能」が、共通認識なんだけど。
つまり、あなたが「将棋の完全解析は不可能」を証明できなければ、
>>206 を否定する必要がある。
がんばってくれ。
>>272 横からだけどおまいさんの言う「完全解析」っていうのは
あくまで「駒の配置と手番」だけを状態変数としたものだろう
たとえば、三山崩しにおいて、ルールを読んだだけでは
状態変数として「1の山の個数」「2の山の個数」「3の山の個数」
という3つの状態変数が必要に思える
でも実際にはこんなにいらなくて、それらのXORだけあれば
勝ち負けが判定できる
このように状態変数を減らすことが、将棋でもできるかどうか
それが論点だよ
275 :
248 :2007/07/28(土) 06:29:04
>267 >269 完全解析の定義を勝手に自己流に狭く定義しないでくれ。 その定義での完全解析ができるという保証は無いだろ? 実際に可能なのは手順込みの局面にラベルを貼る事。
>>270 完全解析の定義と、それが可能かどうかを、まず、答えてください。
ここの立場をはっきりしないとお話にならない。
いいですか?
はっきり明記してくださいよ?
>>272 >二人零和有限確定完全情報ゲーム
「完全情報」ってのは手順の情報も含むんだが
君はこの情報を欠落させても欠落させない場合と等価な事を証明する必要がある
>>273 レッテル貼りの詭弁
>>272 共通認識というか定理だろう
将棋のルールは駒の配置と手番とそれらの履歴とで
記述されているわけだから、当然「区別ありの表」は
作れるわけだよ
そこから「履歴」を消してもWell-Definedになる、
というのは自明なことではないと思うよ
>>279 そのアンカじゃループしてるよ
何か別の事言ってよ
282 :
248 :2007/07/28(土) 06:50:04
>206の言ってる事はずっと以前からループしてるんだよ。 区別は必要ないから区別しなくて良いってずーっと。
284 :
248 :2007/07/28(土) 06:55:40
あー、疲れた。 この議論だけで徹夜しちまったよ。
反論が無くなったようだしとりあえず寝るか 何かあればまた今夜にでも参加するよ みんなお疲れ
>>284 俺もだ
土曜出勤なのにな
>>276 に長レスを書いてたんだけどバカらしくなってきた
ああやって「これにレスできないとバカだ」みたいな言い方をするのは
釣り師が一般人を議論に引きずり込むときの常套手段なんだよなあ
あ、定義もか 誰か出してなかったっけ
291 :
248 :2007/07/28(土) 07:05:31
皆さん、お疲れさま。 付き合ってくれてアリガトン。
「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
自分も寝る おやすみ
なんか急に伸びすぎワロタwwww
俺は松原先生の本を昔図書館で何冊か読んだ程度で ゲームの数学は全然わからないからあれだけど 記号や用語などもたぶんでたらめ 状態変数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 の論法で完全解析が可能であるというには、
駒の配置に加えて「この局面が何回目か」というパラメータも
ノードの状態変数として加える必要があるということ。
完全な履歴は必要ないが、何回目かは必要となる
これが「局面の出現回数の総和で添え数字づけ可能」の意味と理解した。
だとすると、途中で人間×2からコンピュータ×2に交代するとして、
全ての局面の出現回数を保持していなくても「この局面は何回目です」と
だけ伝えればいいんでないかい?後は事前に完全解析された結果に基づいて、
最強ソフトが「先手の勝ちです」「後手の勝ちです」「引き分けです」
とだけ伝えてオシマイになるはず。少なくとも十分条件としては。
302 :
デフォルトの名無しさん :2007/07/28(土) 11:47:24
>>301 勝ち負けの決まっている手順の途中に千日手が現れる可能性有り
>>299 将棋というゲームの正しいイメージはこうかもしれないな
N個のマスと、それらをつなぐ線があり
マスのうちいくつかは赤か青に塗ってある
二人が交互にマスに石を置いていく
一つのマスには3個まで石を置ける
4個目の石を置いたら引き分けで終了
赤のマスに石を置いたら先手の勝ち
青のマスに石を置いたら後手の勝ち
ただし直前に相手が置いたマスから
線でつながっているいマスにしか置けない
>>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九」}
みたいな感じ
それで、「同一局面4回」のルールを記述するために
(立会人に見せて「引き分けですね」と言ってもらうために)
局面の出現回数も、X1、…、Xnの中で持ってなきゃいけない
俺もおまいさんと多分だいたい同じ考えだよ
でも全部の局面の出現回数を持たなきゃいけないと思ってる
問題図までを指すのは神ならぬ人間なのだから、
神様に言わせれば変な手などもあるはず
そこから神様が引き継いだとして
勝つつもりで指してたら、途中で「その局面は4回目ですよ」
といわれて引き分けになっちゃうかもしれない
そんなわけでXnの中にはすべての(膨大な数の)局面に対して
その出現回数をあらわす変数が含まれてる
ことを俺は想定してた
>>306 の続き
S(X)は「今の状況までの初手からの手数」で、
どうせ有限なのだからそんなの持ち出さなくてもいいのだけど
議論を簡単にするために出してみた
千日手がある以上、無限に多くの手数は指せない
だから手数の多いものから逆にさかのぼって
2000手以上は解明済み… 1000手以上は解明済み…
などとすることができる
>>305 たとえば簡単な状況で、自玉は必至、相手玉には
3種類の詰みが見えてるとする
ここで、もしその詰み手順の途中の局面が
3回出現済みだったら、自分は相手玉を詰めれない
だから千日手引き分けになる
もちろんそうでなければ勝ちになる
これは履歴が結論に影響を与えてるんじゃないかな
>>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 >囲碁やオセロなどは目数や石数によって勝ち(負け)の価値が決められるけど、将棋は?
相手玉を詰ませば勝ち。
317 :
312 :2007/07/28(土) 13:42:14
>315 詰め将棋に準じて考えれば勝つ側はなるべく短い手数で勝つ手を選び 負ける側はなるべく長い手数で負ける手を選ぶべきなのだろうが、 結論が引き分けの時は??? また手数が同じならすべての手順は価値が同じなのか? 私には良く分からない。
>>314 笑い話かどうかともかく、相手のミスをどれだけ仮定するかは、実際の将棋対極では
非常に重要な要素に思うぞ、プログラム開発に限らず。いわゆるハメ手ってやつね。
相手がヘボなら、ハメ手を使って早々に対極を終わらせるだろうし、相手が上手ければ
ハメ手を見透かされて逆に咎められるだろうから、そんな手は使わないだろう。
ハメ手は、素人相手の、相手のミスを前提とした手法だが、プロでも形勢が悪いときは
それに近いことをするようだ。たとえば米長さんの本に、状況がこちらに不利であると、
ギャンブルっぽい手をあえて選ぶと書いてあった。
神はどう相手にミスを期待して、手を選ぶのか。 神が神でいられるのは、初期局面だけなのだろうか・・・
子ノードの勝ち手順の多寡かなぁ・・・ でも手順は少なくても簡明な勝ちもあるだろうし・・・
322 :
180 :2007/07/28(土) 14:27:08
>321 そう。そして私が>165の意見に対してキツイ事を書いて これだけ燃え上がってしまった。 今思えば、彼が考えていた前提(神様同士が初手から対局したと仮定)が 分からなかったとは言え、失礼な書き方をしてしまった。 >165さん 今更ですが済みません。ゴメンナサイ!
>>317 昔、ちょっとGAをやったとき、生き残り戦略はそんな感じにしてた。
引き分けの時、手数が同じ時は、駒得している手数が長いほうが有利としてた。
くどいようだけど、最後に一言だけ言わせて。
既存のゲームの理論を用いて、将棋の完全解析可能性を証明するには、
将棋が添え数づけ可能であることを示す必要があるのだろう。そして局面に、
全ての局面についての出現回数を保持すれば、それが添え数づけ可能になるようだ
しかし、それは「将棋が完全解析可能か」という命題には答えても、
我々が議論してきた問題とは微妙にずれているような気がする。
我々は「将棋を完全解析するのに、局面の出現回数(=履歴)を保持する必要があるのか?」
という問題を議論してきたはず。これは「将棋は完全解析可能か?」とは違う。
「局面だけで完全解析が出来るか?」という命題は、
>>296 の理論にもとづいて
行おうとする限りにおいては、千日手の判定ができないため
>>300 氏の言っている理由により
証明出来ない。しかしこれは、他の理論で証明することまでも不可能であると言っている訳ではない。
もし局面だけで完全解析が可能だとすると、少なくとも出現回数付きの完全解析から、
一意に射影できるはず。なぜなら後者は前者に情報を追加したものだから。
もし前者で完全解析が可能であるなら、追加した情報(=局面の出現回数)は
余分な情報であって、後から射影作業によって取り除ける。
(つづき) とりあえず「局面の出現回数つきのノードで考えると、完全解析が可能」を認めるとしようや。 上の「局面の出現回数」は、そのノードの出現回数だけではなくて、全ての局面の出現回数ね。 ここで、次の問題を考えてみる。 (*)出現回数つきの状態で考えて、完全解析した状態ツリーを得たとする このツリーに含まれる状態のうち、出現回数の項目だけ違っていて駒の配置が 同じものは、同じ結果(勝敗および千日手)がマークされているのか? ここで、人間の勝ち筋見落としやGHI問題、また「その局面に至る途中で、 千日手の局面を経由した恐れがある」というツッコミは、不要。ミスなしは 前提であるし、「GHI」や「途中の千日手」といった問題は、出現回数つきの 状態ツリーではそもそも存在しえない。なぜなら、今議論の出発点としているのは、 回数まで出現回数まで含んだノードなんだから、「途中で千日手」を経由していないのは、 出現回数の情報から明らか。
(つづき) 何が言いたいかというと… 状態図にループ構造があると、数学的に完全解析の存在の証明が非常に難しそうだ。 で、状態変数に、全ての局面についての出現回数を保持するのは、そのループ構造を 千日手に至るまでの手順で展開し(添え数づけ可能にし)、数学で知られている 既存の完全解析の理論に乗っけるための便宜的な手法に過ぎないんじゃないかと。 もし(*)が満たされれば、勝ち負けの情報を一意に保ったまま、折りたたんで、 局面だけの完全解析に移行できるように思うのさ。折りたたむと、当然ツリーから ネットワーク構造(ループ含む)となる。 この段階で「局面だけだと、途中の千日手を経由しているかも」と議論するのは不要。 なぜなら、もともと出現回数つきのツリーから折りたたんでいるんで、先に述べた 理由から、考える必要がない。そして勝ち負けがつく局面(ノード)以外は、全て千日手の 局面のはず。当然、千日手の局面は千日手の局面で、閉じたネットワークを作る。 勝ち負けが決定したノードが千日手に繋がってないんだから。もはや勝敗・千日手とも 出現回数の差異によって、その間のツリー・ネットワークの交叉が変化しないのは明らか。 これはあくまでも、(*)の前提が満たされた場合の話ね。 でだ、(*)の問題について、誰か解るヤシはおらんか?これが鍵になる気がする。 何らかの簡単な論理で言及できそうにも思うのだが?
>>324-326 (*)については「出現回数の項目だけ違っていて駒の配置が同じもので、
結果が異なることはある」でしょ。
それも「しばしば経験する」からこそ、みんな困っていて、
transposition tableにやむを得ず経路を入れなくちゃいけないわけで。
>>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問題、ということでしょう。
336 :
デフォルトの名無しさん :2007/07/28(土) 17:45:14
自分も状態変数には出現回数が必要だと思ってるけど 不要だっていう意見の人まだ居る?
>>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問題の本質だと漏れは理解している。
343 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 10:16:58
どんな指し手にも対応できるように、 すべてを検索してしまえって話をしているのだから、 区別する必要はないように思うぞ?それとも釣りかな?
>>340 じゃあ、言い方を変えます。
そもそも「双方が最善を尽くす」という前提があるので、
「引き分け」でない局面の出現が一回しかないのは明らかなので、
完全解析後のテーブルとしては、すべての局面(手番込み)の
「先手勝ち」「後手勝ち」「引き分け」の状態のみ持てばよいのでは?
ということです。
>自分も状態変数には出現回数が必要だと思ってるけど
当然のことながら、完全解析中のテーブルとしては必要です。
あなたの書き方は、「どのテーブルに、状態変数が必要か」が、あいまいです。
>>343 探索で考える手順と、実際に指される手順を区別しないと、
千日手の発生状況が異なるから、意味がないっていいたいのか?
それは「カギ括弧無しには一意に射影できない」といっているのと同じだぞ
もちろん実際に指される手順は、括弧付き(括弧の情報を含む)なんだよ。
「括弧無しで議論して、手順1)での探索から、手順2)のHまで千日手と結論づけてはいけない」
といっているんだよ。
おまいさんは、カギ括弧無しで考えていて、手順1)を「探索した手」と呼び、
手順2)を「指された手」と言っているように思うんだが?
347 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 11:03:51
>>346 は完全な釣りですから・・・相手にするのはやめましょうね
俺は門外漢なんで申し訳ないが
>>331 の
325が議論していた数え上げ方の言葉で説明するなら、
「aの局面が3回出現している状態でのbの局面は負けだが、
aが2回しか出現していない状態でのbの局面は勝ち」ということがしばしば起きる、
というのがGHI問題。
というのがサッパリわからない
ここで言うaとかbとかってそれぞれ同じ局面なんでしょ?
なんで勝ち負けが変わったりするの?
>345 >そもそも「双方が最善を尽くす」という前提があるので、 >「引き分け」でない局面の出現が一回しかないのは明らかなので、 この『「引き分け」でない局面』でいうところの、「局面」は、 今までの全ての局面の出現回数を、情報として持っている?持っていない? 漏れの説明もあいまいだったかも知れんが、そちらの質問もまた漏れには あいまいにうつってる。悪いが、言葉を補ってくれ。
>>349 完全解析後のテーブルとしては、持っていません。
ただし、対局である以上「棋譜」が生成されているので、
棋譜を見れば、その対局での「局面」の出現回数は分かります。
351 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 11:14:08
>>348 同一局面が4回現れると引き分けで指し直しになる
引き分けにあえて持ち込むか、勝ちを狙うかという違いが出てくる
352 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 11:16:29
途中から、人間→CPUに切り替える場合のみ局面の回数が必要 はじめからCPUなら同一局面はあり得ない(単に手を延長するだけでしかないため)
そもそも千日手で引き分けは王手とか詰み回避の時しか成立しないじゃなかったか? 何の意味も無い議論をしてるようにしか見えないのだけど。
まあ、完全解析自体が計算量的に不可能なんだから 千日手を巧いこと処理して、1万倍の速度で解析したところで 全然意味ないし、始めから机上の空論なわけですよ。
机上の空論もなかなか楽しいもんだぜ?
>>180 は、「例え将棋の神様であっても」といってる
理論と現実の区別もついてなかったのか・・・
妙に納得
因みに地球上の全ての原子に1ビットづつ記録しても、 全ての局面を記憶することはできないし かと言って量子コンピューターで将棋ができる時代の遥か以前に 名人は負けてるでしょうし。彼は何が言いたかったんでしょうね
>>351 24でR2300ていどのヘタレの意見だから的外れかもしれないけど
同一局面が出てきた場合、そこで千日手か打開かの選択が生まれるってのは
対局中よくある話なんで理解できる
ただ、331は引き分け(千日手)or勝ち(打開)じゃなくって
負けor勝ちというふうになってる
そこが理解できない
>>361 連続王手の千日手なら引き分けじゃなくて負けになるよ。
>>362 するどいね。ただ>361 の意見にも一理あって、
>351 に、引き分けも加えるべきだろうね
それと「最後の審判」っていう詰め将棋の問題があるようだ
現在の将棋のルールには不備があって、
必ずしも勝ち・負け・千日手で閉じるわけではない
打ち歩詰めのルールは、やや特例的なものだから、
仮に全部探索したところで、このルールを適用すると、
一部の状態ノードの勝ち負けが重複してしまう
現状の詰め将棋のプログラムに「最後の審判」食わせたら、
ただしく「不定です」って答えるのかな?
364 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 19:28:20
後手が王手を防ぐために打つあい駒の歩が逆王手になっている。 先手がそれを取って王手をすると千日手になってしまい先手は取れない。 しかしその局面は先手が歩を取れないと、先手玉は歩打ちで詰んでる。
365 :
364 :2007/07/29(日) 19:30:41
個人的な意見だけど、詰め将棋としては歩詰みで、対戦としては後手の勝ちでいいんじゃない? 同一局面が2回しか出ていないなら王手を外せるんだから
367 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 19:33:47
作者の作意では、歩の合駒が出来ないから(打ち歩詰め)後手の負けって事らしいね
368 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 19:35:59
>>366 先手の方から、同一局面への王手を外せるんだから
先手が繰り返す方が悪い
369 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 19:45:37
>>366 麻雀でいう形式テンパイを認めるっていうやつと同じだ
盤面をみただけでは打ち歩詰めではないのだからOKにしようぜ!
370 :
名無しさん@そうだ選挙に行こう :2007/07/29(日) 20:17:17
>>366 これ嫁
千日手の定義より、打ち歩詰めの定義の方が優先されている
歩で王手する手は、ルールによれば、打ち歩詰めの規定には当てはまらない
しかし、歩を取る4度目の王手は千日手の規定に当てはまる 後手の勝ちだ
「特に決められた禁手事項」
(将棋世界平成5年1月号付録の'93年版 将棋ルールブック)
3.打ち歩詰
持駒の歩を打って王手をした局面で
王手を解除することが不可能な状態になる時、その歩を打つ手
5.連続王手の千日手
一局中同一局面の最初と4回目の局面の間の
一方の指し手が王手の連続であった時、
王手をした側にとって4回目が出現したときの局面。
将棋のルールってこんなに複雑だったんだね
最初から完璧に考え抜かれて作られたルールじゃないから 想定外な状況に対処するために後付けルールを足して複雑になって来ている訳か まるでこれは
まるでこれは・・・何?
続きはWEBで
〃∩ ∧_∧ ⊂⌒( ・ω・) はいはいわろすわろす `ヽ_っ⌒/⌒c ⌒ ⌒
>>350 ああ、やっと言いたいことが解った。
お互いが最善手を尽くせば、同一局面は二度あらわれないってのが
間違いだと思うぞ。それだと千日手に陥る局面というのはそもそも存在しない。
実際には、千日手ルールを無視した最善手だと千日手になってしまう局面が、
詰め将棋にあって今それを議論している。そして千日手は避けないといけないから、
それを効率よくコンピュータで処理する方法はどうかって話。
初期局面からの完全解析は当然無理だが、これは詰め将棋の問題を内包するし、
詰め将棋を適切に解く技術は、将棋のプログラム開発に必要
千日手になるタイミング云々の話は、そうしたことは当然わかっているものとして、
答えたんだよ
どういった解釈が正しいかについては、議論があるだろうが、 いずれにせよプログラム開発の段階では、各ノードの結論として、 「先手勝ち」「後手勝ち」「千日手」に加え、「先手打ち歩詰め」と 「後手打ち歩詰め」を考慮しないと駄目だろうね。
378 :
180 :2007/07/30(月) 02:34:52
>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)によって情報を失っているので、
付き合わせることは出来ない。ないのと一緒だ
380 :
デフォルトの名無しさん :2007/07/30(月) 02:51:14
>378 あんまし気にしない方がいいと思うよ、ここ2chだし ちなみに量子コンピュータ関係で言うとね、まるで量子コンピュータが完成すれば 今コンピュータで扱っている問題がすべて並列に瞬間的に解けるとする 言説がまかり通っているけど、それは勉強不足 量子コンピュータでは、解きたい問題ごとにアルゴリズムを考える必要がある 自分の知る限り、Shor, Grover以外に、パッとする実用的な話はないのが現状 量子コンピュータで、例えば3x3オセロでも解くアルゴリムを作ったら そりゃ後世に名を残す、いい仕事になると思う だから仮に量子コンピュータデバイスが実現したとしても、 それを使って将棋を解くアルゴリズムが見つからない状況になると思うぞ 将棋は人間が作ったゲームだから、問題設定が非常に複雑だ
382 :
180 :2007/07/30(月) 03:10:50
ついでに今、私の頭の中で整理されている(つもりの)イメージを お話しますと局面と指し手の組の集合が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)'の集合上で表現しなければならない (でなければ必要な情報が欠落する)と考えているわけです。
383 :
デフォルトの名無しさん :2007/07/30(月) 03:26:02
可能な局面数 Nにたいし、3回訪れた、0-2回訪れたという情報を持っていれば完全に解ける 2のN乗局面調べればいい
384 :
180 :2007/07/30(月) 03:31:22
385 :
デフォルトの名無しさん :2007/07/30(月) 03:44:29
>>384 よ、
可能な局面(N個とする) ごとに、3回訪れたかどうかの情報を持ち、かつ
局面データがあれば完全にとけているんだ 意味わかるか?
これ以上のことはないだろが どこが不満だ?
道筋は全く関係ない
まずは、初手からならば局面だけ持っていればいいことは判っているのか??
>385 私も解析対象の局面に至る手順の情報全てを保持しなければならないとは 思ってません。ある程度(かなり?)、圧縮は効くでしょう。 ただ、実際に解析する際の手順としてはO(3)'上でゲーム木を展開するのが いちばんシンプルで分かりやすいと思います。探索すべき局面は増えますが。 また初手から神プレーヤー同士が対戦するならば純粋な局面情報のみ保持 すれば良い、即ちO(1)上の結果にGHI問題が発生しないのは分かります。 まだ、いまいち良く分からないのはO(2)上の結果もそうなのか? こちらの結果も経路により区別する必要は無いのか?と言う事です。
>>378 ごめんね。
>>359 は、
>>355-357 に対して、
>>180 をみれば「理論」の
話をしているのは分かるのに、「理論」だからこそ、
みんな付き合っているのに、「実行不可能」とか言い出すから、
いまさらそんなことを言うやつが出てくるのか、といった
意味合いの発言でした。
>>180 に言ったわけではないです。
>妙に納得
は、
>>170 と同じようなニュアンス。
ちなみに
> 人間、あるいは何も考えてないプレーヤー(機械を含む)が指した
> 将棋を途中から将棋の神様が引き継いだとしたら、それまでに
> どの局面が何回現われたかと言う情報なしに指し継いだのでは
この情報とやらは、棋譜で十分では?
それと、無責任なことはするなよ?
と思わなくもないのですが。
388 :
378 :2007/07/30(月) 04:25:19
>387 ああ、そういう意味でしたか。それはこちらこそ失礼致しました。 引き継ぐべき情報はもちろん棋譜で十分ですね。 無責任な行為かも知れませんが、任意の局面に結論を出すためには そのような仮定が必要になると思います。
>>388 またまた、ごめん。
>それと、無責任なことはするなよ?
は、
>>378 に言ったのではなく、話の内容で、対局を引き継ぐのに
「千日手になるかならないかの瀬戸際で交代するなよ。せめて二回目の
局面で交代してやれよ。」と言う意味でした。
他の人もそう思ったかな?
>>388 ちなみに
> 引き継ぐべき情報はもちろん棋譜で十分ですね。
とのことですので、
>>379 と意見が異なると言うことですよね?
>>379 は、まったく、困ったもんですよね。
>>378 さん(
>>379 さんもかな)
>>217 を、もう一度よく読んでみてください。
よく読むとわかると思うのですが、初期局面の駒配置については、
何の言及もされていないのです。
これは、「初期局面として、任意の局面を指定可能」という事でしょう。
上での議論は、「理論上考えられるあらゆる局面」を十分含んでいるので
心配しないでください。
将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ? 当然そんなことは出来ないし意味が無いから勝敗に関係の有る部分だけ解析すればいいだけであって、 人間相手に最強を目指すなら同じ局面が何度来ようがその時に可能なベストの手を打ち続ければいいはず、 結果的にそれが千日手になっても将棋のルールに不備がある部分に達しても負けはしない。
うん それが何か?
394 :
デフォルトの名無しさん :2007/07/30(月) 18:44:34
>>381 その通りで、量子コンピュータが実現すれば既存のコンピュータで難しい問題が
なんでも一瞬で解けるようになると思っている人間がいるから困る。
量子アルゴリズムがあって初めて高速な計算が可能になる。
ゲーム木の探索なんて量子アルゴリズムとは相容れないだろう。
>>376 、
>>379 あなたは、
>>345 、
>>350 の内容を全然理解していないことがわかりました。
基本的に、話の発端である
>>165 と同じことを言っているんですよ?
あと、詰め将棋のルールと、指し将棋のルールが違うことを知っていますか?
ルールが違えば、検索方針も違うんですけど?
>>180 の方は、
>引き継ぐべき情報はもちろん棋譜で十分ですね。
と納得したようですが、あなたは理解できましたか?
396 :
デフォルトの名無しさん :2007/08/02(木) 14:41:33
>>394 >量子アルゴリズムがあって初めて高速な計算が可能になる。
高速な計算とは言わないだろ、手順を経て組み立てる計算なら高速であるが
局所的な超同時な仕組みでは計算しているというより状態の合成をしている
に過ぎないよな。
そもそも計算は「計って」、「数を算する」ことであて量子コンでは
計ってもないし、数も扱っていない。
量子コンピュータで致命的なものはソフトウエア、つまりプログラムの
仕組みが存在しないことだよな。
超同時演算にソフトウエアが存在したら、それが足を引っ張り
早いどころか亀速度になるw
量子コンピュータが学者の間で注目されないのは、ハードウエアとして
存在しなければいけないという前提があるからだろ。
電子回路な計算機で、ソフトウエアなしの計算機では利用価値などない。
「ソフトウエア」がどれだけ重要な発明であるか理解しておいたほうがいい。
>>392 >将棋の完全解析って言うのは初手から終局までのすべての手筋を網羅した地図を作ることだろ?
「巡廻セールスマン問題」で完全解析を行ったというような話と同じだよな。
最適解だと証明したようなことを言う奴はいるが、結局は抜けが発生する。
類似問題を全数を判断せずに証明したと言い張るDQNがいるが、
科学では仮説と実証だけでは、科学ではない。
仮説→実証→複数の反証で多面的に検証できなければ証明したことにはならない。
原理を解明したとか信じるヴァカも多いよな。まさしく宗教の域。
>>396 別にソフトウエア無でも超高速なデータベースとして機能すれば十分だろ
大体、計算機という翻訳語が変で、コンピューターは演算する機械だよ
つまり状態の合成をしているだけなんだがw
>>396 量子コンピューターに対してどんだけ無学なんだよ、中学生か?
何の指摘にもなってないよ
量子デバイスでだって量子ゲートは設計できる。 即ちチューリングマシンが構成できるし、メモリーだって作れるので 原理的に現代のノイマン型コンピュータで可能な事はなんでもできる。 ただ量子エンタングルメントを利用した長いキュービットによる 超並列演算をしないと、現代のコンピュータより圧倒的には 速くならないと言うだけで。 長いエンタングルメントしたキュービットの列で 特殊用途の専用アキュムレータ(と専用アルゴリズム用特殊ハードウェア)を 構成して今のノイマン型コンビュータアーキテクチャの一部として 埋め込む事も出来るんじゃないかな? 周りのノイマン型の部分は既存のデバイスでも量子デバイスでも良いだろうし。 いずれにしろ、まだろくに存在していないものを あれが出来てこれが出来ないと言うのは早計じゃないか? アルゴリズムが無ければキュービットアキュムレータが働かない (超並列演算が出来ない)のはその通りだろうが。
>即ちチューリングマシンが構成できるし、メモリーだって作れるので それではチューリングマシンであって、量子コンピュータではないだろ 頭変になったのか?
量子チューリングマシンと言うのが定式化されている。
>>404 あたま悪そうだな。チューリングマシンの手順式手法に戻るのなら
従来技術に激しく勝てず、量子の意味すらなくなる。
手順式は手順を超える演算はできないんだよ。
量子チューリングマシンでは量子コンピュータが得意とする因数分解が
出来なくなるw
これでは古典的コンピュータの因数分解専用の演算回路に下った
たんなる量子トランジスタレベルだろう。
仕組みを手順通り行うという概念の壁が越えられないからこそ
古典的コンピュータには性能の限界があることすら知らないようだなw
>>406 あたま悪いな。論理手順が存在する限る原理が異なろうが
手順を省略できないわけだ。手順が省略できなければ順番に実行する
以外ありえないわけ。勉強になった?
>>406 そもそもチューリングマシンは命令語を受け取りそれを手順どおり実行する
タイプだろ。電送時間が存在しれば遅延する。
これでは古典的コンピュータが速度を上げられない理由と同じで
電送経路があるかぎり従来技術にはコスト的についてこれない。
つまり永久に開発されない。
量子チューリングマシンは古典的チューリングマシンが持つ能力を 全て保持しながら、なおかつ量子コンピュータ固有の機能も持っている。 量子ゲートに与えるデータ次第でどちらの働き方もできる。 量子チューリングマシンは計算可能性と言う点で 古典的チューリングマシンと全く同等であるが、 問題によっては(まさに)桁違いの計算能力を発揮する。
どうでもいいけど将棋の話題しない? 振れるようなネタはないのだけど。
うーん、難しいな。 Lispで将棋ブログラミングしたいと思っててまだ始めてないし。 と言うか、Schemeで書くべきかCommon Lispで 始めるべきかで早くも悩んでるしw。
非決定的チューリングマシンの話は出ないのか? これが量子チューリングマシンで実現できればメチャ嬉しいのだが
量子コンピューターが出来る前に光子コンピューターの方が早く出来るでしょ。
量子コンピュータでチューリングマシンはできる、しかし現状の性能には 激しく達し得ないというのでFA。 まあマヌケ君はできないことを誇張するのが得意だから、またデンパするんだろう
415 :
宮本 :2007/08/08(水) 17:37:03
>414 誰が正しいかでは無くて真実は何なのかを知ろうとする方が有益だぞ。
スレ違いかどうか気づける能力を持つ方が重要だ。
最近はスレ違い、スレ違いとやたらうるさい人が居るな。 まるで縦割行政が好きな役人か自分の専門分野にコモッテル蛸壷学者だ。 そういう考え方からは学際領域にある分野が発展する事は決してあり得ない。
とは言うものの量子コンピュータ及び分子コンピュータや 光コンピュータなどに関するスレを新たに立てた方が 良いかとも思ったが、どの板に立てたら良いのか良く分からん。 それとも既にどこかにあるのかな?
>>418 お前がスレ違いだろ。別に学問を発展させようなんて思ってない
>420 Thanks 物理板か。 しかも寂れていると言うか荒れているようだな。 計算理論やアルゴリズム論、計算量理論から見た 量子コンピュータ スレがあっても良い気もするな。
量子コンピュータなんてやっている奴は約1名の2ch中毒ニート以外 いないだろ。
量子コンピュータまず量子縺れ状態のシュミレーションから、かなり高度な量子力学の知識が必要。 どちらにしても量子コンピューターシュミレーターってあるらしいけど一般公開して無いだろ、動かすのにたぶんスパコン必須?
みんなで激指を買って遊ぼうよね♪( ^ω^) 激指 定跡道場 商品紹介 2005年世界コンピュータ将棋選手権で全勝優勝を飾った「激指」のシリーズ最新作。 序盤戦術を体系立てて学習できるモードを搭載、最強の思考エンジンに加えて学習補助機能が充実しました。 定跡講座は所司和晴七段が全面協力、プロ将棋の最先端を無理なく身につけることが出来ます。
コピペうぜぇ氏ね
428 :
デフォルトの名無しさん :2007/08/12(日) 13:28:16
量子信者はカエレ!
町はずれの教会をシルクのような霧雨が包んでいます。 傘も差さずにレンガの階段にもたれていると 遠い町明かりがいくつも輝いては滲んで行きます。 あの人はガードレールをのりこえて空の向こうに何を見たかったのでしょうか。 あの人が星になったなんて嘘ですよね?
ポエムはポエム板でおk
>>429 我々は重要な事を見逃していたようだ、
このポエムの中に封印された古代の将棋の英知が詰まっているのだよ!!(AA略)
だから量子コン厨は物理板で爺でもしておけ。 スレ違いだよ、キミのような量子ウンコは
>429 リョウコ信者w 最近の厨はググって出てこないと何も調べられないのか
夏厨の季節
うはぁ、なんという音程……
437 :
デフォルトの名無しさん :2007/09/10(月) 08:35:42
量子って、武豊の嫁?
銀星将棋おもろいな。思考タイプに強引、慎重なんてのがあって 強引にすると思考レベル最低でも強引に攻め込んでくる。 ずっとこういうの待ってたんだよな。重みのさじ加減弄るだけで 技術的にはなんも難しくないのになぜ今までなかったのかが不思議なくらいだ。 全AIにこのオプションをつけてくれ。
439 :
デフォルトの名無しさん :2007/09/14(金) 17:19:50
440 :
デフォルトの名無しさん :2007/09/18(火) 10:52:04
ほ
441 :
デフォルトの名無しさん :2007/09/18(火) 18:49:11
しゅ、しゅって言いたい訳じゃないんだからねっ!
442 :
デフォルトの名無しさん :2007/09/19(水) 10:05:02
ぬは、書かれちまったw
443 :
デフォルトの名無しさん :2007/09/19(水) 17:25:23
ダリか初心者にも分かるように 評価関数における評価項目のつけ方まとめてもらえませんか
444 :
デフォルトの名無しさん :2007/09/19(水) 19:32:30
>>443 ・駒割
・王将8近傍の敵・味方の利きの数
・王将との相対位置による評価
って感じの情報でいいのか?
玉の安全度を考えるをON/OFFで自己対戦すると27勝3敗だった。 終盤は駒得より完全に玉の安全度だね。
446 :
デフォルトの名無しさん :2007/09/19(水) 20:44:00
>>444 >>445 ありがとうございます。
評価項目の全体的な全体的な優先順位や
細かい設定などはありますか?
447 :
デフォルトの名無しさん :2007/09/19(水) 20:58:55
優先順位ってのは評価項目の重みの事? 序盤は駒得や囲いが重要だけど、終盤は王将の安全度の方が重要だろうし・・・ 大雑把な方針としては、試行錯誤して最適な重み・設定を見つけるか、学習で何とかするかの二択じゃないかな。 自分の棋力とかコンピュータ将棋にかけれる時間と相談しながら決めてくれい。
448 :
デフォルトの名無しさん :2007/09/19(水) 21:34:35
449 :
デフォルトの名無しさん :2007/09/25(火) 12:35:31
ほ
し ひゅうま
あ
そ
こ
455 :
デフォルトの名無しさん :2007/10/01(月) 11:07:00
ほ
456 :
デフォルトの名無しさん :2007/10/01(月) 19:46:05
あたぁ!
> これまでのアルゴリズムとは異なり、モンテカルロ法のアプローチでは > 非常に簡単に並行処理ができるので、 > 新世代プロセッサーのマルチコア構造を活用できる。
モンテカルロ法自体は並列化しやすいだろうが、 それとともに使われて成果を上げているUCT(だっけ?) とか言う探索アルゴリズムは並列化しにくいらしいよ。
ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ
今このスレを読んだ。「完全解析」について。 チェッカーや6x6オセロで言う「全探索」や「完全解明」は ゲーム開始時の局面から始めた場合の話だよね。 合法な任意の局面からというのは解かれていない。 でも、このスレを見てきたところ、 将棋では任意の局面からの場合を考える人が結構いる。 任意の局面から始められるものとして詰将棋があるからかな。 何だか文化の違いのようなものを感じたので感想を書いた。 チラ裏ですまん。
ゲーム理論はどうも胡散臭い。 見直してその有効範囲を確認する必要がある。
しっ 触れるな
ワラタw
466 :
デフォルトの名無しさん :2007/10/10(水) 22:04:46
おまえは最近ツンデレという言葉を知ったばかりの初心者
確かに。 俺もツンデレとは違うとおもた。
55将棋って以前権利をめぐってもめてなかった? あれどうなったんだろう?
>472 無視してるのか、一応話しは通してあるのか見ただけじゃ分からんだろ?
>>473 普通話を通すと言うことは、断り書きを入れる方向で落ち着くもんだ。
断り書きもなしに無条件に許可するようならば、森田将棋に噛み付く筈も無かろう。
ゲームのルールはアイデアだから ルールの記述文をぱくらない限り問題ないよ
7七将棋とか… 駒の種類も本将棋と変わんない。けどちょっと大きいかな。 7 6 5 4 3 2 1 ┌──┬──┬──┬──┬──┬──┬──┐ │▽桂│▽飛│▽銀│▽玉│▽金│▽角│▽香│一 ├──┼──┼──┼──┼──┼──┼──┤ │▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│二 ├──┼──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__│__│三 ├──┼──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__│__│四 ├──┼──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__│__│五 ├──┼──┼──┼──┼──┼──┼──┤ │▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│六 ├──┼──┼──┼──┼──┼──┼──┤ │▲香│▲角│▲金│▲玉│▲銀│▲飛│▲桂│七 └──┴──┴──┴──┴──┴──┴──┘
478 :
477 :2007/10/13(土) 17:51:08
全駒総動員の方向で、一度も動かさない駒とかを無くしたいね。 で7七将棋のルール案を。 1.相手陣は「三段分」 ※桂馬の成・不成の選択を残したい 2.味方玉が相手陣の一段目に到達すれば、相手玉を詰まさなくても「勝ち」 ※参考:トライルール 3.千日手はどんな場合でも4回目の同一局面を出現させたほうが「負け」にしたいけど、 棋譜をきちんと取らないと判断しづらいから難しいかな
4 3 2 1 ┌──┬──┬──┬──┐ │▽香│▽桂│▽王│▽銀│一 ├──┼──┼──┼──┤ │▽歩│▽歩│▽歩│▽銀│二 ├──┼──┼──┼──┤ │__│__│__│▽歩│三 ├──┼──┼──┼──┤ │▲歩│__│__│__│四 ├──┼──┼──┼──┤ │▲銀│▲歩│▲歩│▲歩│五 ├──┼──┼──┼──┤ │▲銀│▲玉│▲桂│▲香│六 └──┴──┴──┴──┘ これどうよ、評価よろしく
>>479 大駒がないのと、銀があって金がないのが気になった。
>>480 大ゴマは盤面が狭いのでこの際無くていいだろうという判断
金は、ほしけりゃ敵陣に乗り込んでひとはた揚げて帰って来いということでゲーム性を面白くするためわざと無くしました
駒の動きは本将棋と同じじゃなくてもいい?例えば八方桂とか。
44将棋はさすがに簡単すぎるんじゃねーか? たぶんすぐ解明されそう。
46だった orz
>>483 解明されたら告ぎ考えるから是非解明してくれ
将棋板から拾ってきた あっちにはこいつの対局スレがあるぞ 6 5 4 3 2 1 ┌──┬──┬──┬──┬──┬──┐ │▽飛│▽桂│▽銀│▽王│▽金│▽角│ 一 ├──┼──┼──┼──┼──┼──┤ │▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│ 二 ├──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__│ 三 ├──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__| 四 ├──┼──┼──┼──┼──┼──┤ │▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│ 五 ├──┼──┼──┼──┼──┼──┤ │▲角│▲金│▲玉│▲銀│▲桂│▲飛│ 六 └──┴──┴──┴──┴──┴──┘
ああ?おお?
知障のふりで「将棋界の○○」「ああ?」という言い回しを使う奴には要注意だ。
489 :
デフォルトの名無しさん :2007/10/16(火) 23:25:27
むしろ大駒がいらないんじゃね どうせ盤面は狭いんだし 代わりに酔象を入れようや 裏は太子で 6 5 4 3 2 1 ┌──┬──┬──┬──┬──┬──┐ │▽銀│▽金│▽象│▽王│▽金│▽銀│ 一 ├──┼──┼──┼──┼──┼──┤ │▽歩│▽歩│▽歩│▽歩│▽歩│▽歩│ 二 ├──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__│ 三 ├──┼──┼──┼──┼──┼──┤ │__│__│__│__│__│__| 四 ├──┼──┼──┼──┼──┼──┤ │▲歩│▲歩│▲歩│▲歩│▲歩│▲歩│ 五 ├──┼──┼──┼──┼──┼──┤ │▲銀│▲金│▲玉│▲象│▲金│▲銀│ 六 └──┴──┴──┴──┴──┴──┘
491 :
デフォルトの名無しさん :2007/10/21(日) 23:05:06
金玉象はまずいんじゃないか? エロ的な意味で。
ここも糞スレになったな
フェイクができないアルゴリズムなんて、負けるのは当たり前。 勝負というのは先の読み合いで、決定されたものではないだろ。 つまり先が読めないからこそ勝負なわけであって、 相手の行動を予測し、相手に勝つのではなく相手に負けてもらうのが筋ってものさ。 眼力の無いやつは空気読めないから計算、つまり理屈だけで勝とうとする 理屈だけな奴ほど勝つのは楽なことを知っていた方がいい。 理屈な行動は、相手からは完全に予測される行動だからだ。 勝ち手を譲れば、100%の確率で勝ち手を奪うのが理屈というもの。 それがフェイクだと気がつかなければ相手の負けは決まる。
日本語でおk
>492 とっくの昔から糞スレだボケ。
完全情報ゲームでフェイクとか言ってもな。
>>493 いや、言ってる事はよくわからんがとにかく麻雀やポーカーのスレじゃないからここ
493じゃないが、例えば自王は放置すれば20手詰めと言う場合 1、放置すれば相手王に必死を掛けられる。 相手が詰みに気付かなければ勝ち。 2、受けると長引くがジリ貧。 こういう場合コンピューターだと2を選んだり、 持ち駒使い果たすまで王手掛けたりすることが多いわな。 com同士だと意味ないだろうけど、人間同士だと1が有効なことが有る。
>498 それを実現するには自分の読みと相手の読み及び評価関数を区別して扱う 「相手モデル探索」が必須だな。 で相手が人間かコンピューターか、どれくらいの棋力かに応じて使い分ける。
500 :
デフォルトの名無しさん :2007/10/22(月) 22:38:02
圧倒的に強ければ、相手は関係ない 強ければそもそも20手詰めの局面へは進まない
おれも
>>500 と同意見。
結局、相手の思考を予測するってのは、自分の思考に自信が無い時の小手先の対策なんじゃね?
>>498-499 相手のアルゴリズムを読んだとしても、その相手はこっちを騙すためにわざと気付かないふりをして
弱く見せかけているのかもしれないぞ
相手を見て判断するのは対人戦での面白さを出すには重要なとこではあるけどさ
>500-501 人間のトッププロにはなかなか勝てない(全体的な実力では上回れない) からこそ、そういう戦略に価値があるのでは? 例えばコンピュータ将棋は詰みのある局面でそれを発見するのが やたら速いが、相手(人間)もそうだと仮定していたらその利点は あまりうまく生かせずに>498の挙げたような状況に陥るかも知れない。 詰みを正確に速く見つける能力がむしろ弱みになってしまう。 >502 特定の相手の指し方を事前にじっくり研究していたらどうかな? たとえば対渡辺竜王を想定して。 ディープブルーも実はカスパロフの指し手を事前にたっぷり研究して 相手の指し方のモデルを持ってたと言う話だし。
>>503 個人的には、そういう方向性が好きなのだが、
こと「プロに勝つ」という目的においては、
>>500 が正しいと思う。
というか
>>503 の方法でプロに勝つには、とてつもないプログラム技術と
ハードウエア能力が必要になって現実的でない。
プロに勝つというのは、ほっといても100年後には達成できるけど、
楽しめる、指導してくれる、というコンピュータ将棋が今後の課題やね。
>504 その考えが甘いとしたら。 つまりコンピュータが人間のトッププロより圧倒的に強くなると言う事は 相手がどんな指し手で来てもそれに対して正しく応手できると言う事だが 将棋と言うゲームがそう御しやすいもので無いとしたら厄介だぞ。 その可能性は多いにある……と俺は思う。 それよりは対戦相手のモデルを持っておいて相手の思考の癖(隙)を突いて 序盤からジワジワ優位を築いて行く方がまだ望みがありそうに思える。 確かにセコイ方法だけどなw。
>>505 確かに俺の考えが絶対に正しいとは言えないが、
相手モデルとかでプロに勝てるなどというのは
とんでもなく甘い考えだと思う。
>>505 がセコイ方法だとは全く思わない。
実現できたら本当に素晴らしいが、実現が難しすぎる。
507 :
デフォルトの名無しさん :2007/10/23(火) 02:07:42
{41, 85, 45, 12, 02, 77, ・・・} (これがひとつのデータです) という可変長データが複数あるとします これらを効率よくメモリに記録するにはどうしたらいいですか?
508 :
デフォルトの名無しさん :2007/10/23(火) 02:08:36
場所まちがえました すみません
あんまりセコクない対人戦略だと、 短時間の勝負ほどコンピュータ有利であることを考えて 時間攻めがいいんじゃないかな? 極端な例だと、80台パソコンを連結して並列に先読みさせる。 可能な相手の指し手が80ある局面なら、人間の思考時間に全部考えて、 ほぼノータイムで指すこともできるはず。 そうされると持ち時間2時間でも、正味1時間位に感じるんじゃないかと。 あるいは、"少しよくなるけど局面を単純化する手"より "よくもわるくもならないけど局面を複雑化する手"を優先する方針にする。 そうすると選択肢が多くなり、人間側の読み筋から外れる率が高くなる。 人間の場合かなり前から現在の局面のことを考えているので、 先読みを空振りさせた場合の負担は、コンピュータよりずっと重いはず。 一から考え直すことになって、かなり苦しくなるじゃないかな。
竜王と対戦したボナンザも、予測読みが当たればノータイムで指した。 また、ボナンザは人間なら早期に枝刈りしてしまう手を指すこともあったので 読みを空振りさせるという点でもそれなりにできていた。 80台のパソコンというリソースがあるなら、普通にやらせても強くなるから 下手な小細工では意味がないということになると思う。 いや、、アイデアを否定してばかりであれだが、 実際そういうアイデア自体は貴重だし、生かしていくべきだと思う。 ただ、それはすごく難しい(だからこそ素晴らしい)と言いたかった。
511 :
デフォルトの名無しさん :2007/10/23(火) 10:27:47
相手の指しやすい手から調べるのはかなり有効な手法だよ プロの棋譜、定跡を使うのはその為 個人に限定してもよい
>>510 持ち時間1時間として
コンピューターが3回に1回ノータイムでも、1時間つかいきれば
人間側の思考時間は、自分の持ち時間と合わせて2時間ある
コンピューターが全部ノータイムの超早指すると
人間側の思考時間は、自分の持ち時間の1時間しかない
読みを空振りさせる回数が3回位増えると
1回あたり数分位とられるから10分くらい損する
ぜんぜん違うと思うんですが‥
結局、80台を良い手を捜すためにつかっても、2割位しか
最前手が変わらないなら、時間攻めで人間が間違うのに
かけた方がお得なように思うわけで
実際、複数台での並列先読みや、局面の複雑度を測ったりするのは、
相手の指し手の傾向をつかむより遥かに容易じゃない?
自分のプログラムはまだ弱いのでそんな段階ではないけど。
誰か人柱にならないかなあ。
台数が80倍になると、一般的に思考時間を9倍にしたくらいの強さになる。 つまり、思考時間:1分、強さ:1台9分相当を選択するか、 思考時間:0分、強さ:1台1分相当を選択するかという問題になる。 (人間が常に同じ時間を消費するという前提) コンピュータよりも人間の方が持ち時間の価値が高いことを利用するわけだ。 悪い手は切り捨てて愚直に80手読まないようにするなどの工夫もできる。 そうなると普通の予測読みとの境界がぼやけてくる。 俺は、通常の予測読みがいいと思う。俺も実測してないのでこれしか言えない。
あの自演犬やってないと言い張ればいいと思ってるな バレてないと思ってるのは自分だけだぞw
ああ?おお?
将棋のプログラム作っている人の開発環境が気になります。 VC6++っていうのは古いでしょうか?
将棋ならコンパイラやIDEは関係ないと思うが、 VC2005EEがある今、VC6を使う理由がない。
519 :
デフォルトの名無しさん :2007/12/04(火) 08:33:00
VC++6は軽い
VC++6ってインテリセンスのだいぶ貧弱だったような
まぁ、x64がコンパイルの出来ないでいいならVC++6でいいんじゃね。
VC++6はバグが多くて嫌
つーか、>518を読んでどうしてそういう結論になるのか判らん。 まぁ、VS6の正規ユーザで尚且つ時代遅れのPCを使っているというなら止めないが。
525 :
デフォルトの名無しさん :2007/12/07(金) 00:45:10
VC6は2004にバージョンアップ版が出ている 新しいVistaつかうより、バージョンアップされたXPの方がいいということもある
仕事じゃなければ好きなのを使えばどれでもいいさ
VC6なぜか人気あるが自分の経験から言うとあまり印象よくないな。 特に付属のSTLかなりバグがあってひどかった。
今となってはかなり古いコンパイラだから テンプレートのサポートが微妙だったりするけど 自分の使い方では2003よりもよかったよ インストール早いし、起動軽いし STLはSTLPORTいれて使うもんだと思ってる。 そんな私も2005に移行しましたが。
529 :
デフォルトの名無しさん :2007/12/14(金) 14:21:23
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がちゃんと対応出来るかどうかは知らん。
最強じゃなくてもいいからだれか大局将棋実装しておくれw
やるからには最強を目指す! ところで大局将棋ってナニ?
ごめん、やっぱムリ。 てか、駒の動かし方全部把握してるヤツ居るのか、これ?
仮に把握できたとしても、動かす気になれねぇ。
スレを立てるたびに貼る必要はあるのか… 最長の地位を保つための儀式なのか…
こんなのランダムに動かしてれば人間の方が飽きて投了するだろw
大局将棋はゲーム性が低いな
ゲームと言うより占いの儀式みたいなものだったって聞いたような気がした(うろ覚え)。
>>537 テレビ番組で、プロ棋士同士が対局してたな
駒の動かし方は本を見ながら確認してたw
1日では勝負がつかず、3日くらいかけていたと思った
トリビアだな
森羅万象棋作ろうぜ
「バーサーカーソウル!」
市販の将棋強すぎだろ。なんか将棋もプログラミングもやる気ナクナタ・・・
おまいが弱いだけ
前回のGA見てみろ。やる気沸くぞ。
554 :
デフォルトの名無しさん :2008/01/17(木) 07:02:17
もっとこのスレ盛りageようぜ
C言語でやってる人いる? C++の方がいいのかな?
557 :
デフォルトの名無しさん :2008/01/20(日) 14:56:43
C++の方がいい 部分的にC言語やアセンブラも使える
558 :
デフォルトの名無しさん :2008/01/27(日) 14:07:14
スレッド使ってますか?
559 :
デフォルトの名無しさん :2008/01/28(月) 16:28:29
使ってますがなにか?
もう、ブルージーンで最強のチェスプログラムできちゃったので将棋プログラムは興味ないわ
門外漢がよーいうわ
作ってる人近況報告してよ
強化学習してる。死にそう。
いちから作り直してる。
565 :
563 :2008/01/28(月) 21:01:55
>>564 ばかやろう、俺なんてマイナスからの出発だぞ。
566 :
564 :2008/01/28(月) 21:16:24
>>565 なんだよ、マイナスってw
以下、マジレス。
おとといのUSIエンジンの登場でモチベーションがかなり上昇した。
弱くても、勝てなくても、笑われても、それでもいいからとにかく形にすることに決めたよ。
>>566 ランダムざしに負けるのがマイナスじゃね?
俺も強化学習やってる 俺よりは強いんだが・・・
569 :
563 :2008/01/28(月) 23:20:41
パソコンぶっ壊れたから修理するところから。
あと、部屋が汚くてどこに本があるか分からないから掃除するところから。
>>567 負けそうだから怖い。
>>568 出現頻度の低いパラメータって学習が遅くね?
なんか対策考えないとなぁ。
>>570 自分は出現頻度が低いパラメータは保持したまま
別のパラメータが変わるような局面に分岐させたりしてる
ちなみに効果の程は測ってないけど
7五玉で投了
>>571 なるほど、賢いなぁ。
俺は猿だから対局数でごまかそうかなっと。
れさライブラリ使ってる人いる?
あの! Delphiで将棋作るとC++より速度遅いですか?
576 :
デフォルトの名無しさん :2008/02/07(木) 16:07:46
ボーランド製品ならどう速度だろ
あの! Delphiで将棋作るとVisual C++より速度遅いですか?
578 :
デフォルトの名無しさん :2008/02/07(木) 16:16:26
最適化や個人の技術によるが同程度ならVCの勝ち
579 :
デフォルトの名無しさん :2008/02/09(土) 21:48:35
あの! Delphiでインラインアセンブラだけで将棋作るとC++より速度遅いですか?
並列化のことで何年か前にYSS掲示板で議論になってましたけど すごく初歩的な話なんですがrootでsplit(分割)する/しないってのは どういう意味だったんでしょうか? 最初の深さ1だけは読んで、そのそれぞれの(1手読みの)手を並列化するのが 「rootでsplitする」でいいのかな? しない、ってのはどういうことなんでしょう?
YSS掲示板で訊いた方がいいんじゃね?
あまりに初歩的すぎかなとおもって・・・
真面目に質問すれば大丈夫
あ,ここより将棋板の方が人(実際に作ってる人)が多いから そっちでもいい alternative だったか,開発者用のスレがある
32bitパソコンを使ってますがintでなくcharを使うと メモリの節約にはなるが速度は遅くなるのですか?
メモリアクセスが減るから速くなるケースもあるかもしれません。 要は、一概には言えないのでテストケースを充分絞って実験してみることです。
587 :
デフォルトの名無しさん :2008/02/11(月) 14:21:17
char や floatが遅いというのはデマ キャッストに時間がかかるというのはデマ
へぇ〜今調べて自己解決しますたと言うところだったんですが 一概に言えないのですか。へぇ〜
そりゃそうだろ。メモリ2GB程度のパソコンごときで1G件のデータを扱おうとしたら charじゃないとswapしまくりで遅くてしゃぁない。
将棋では1Gも使わないでしょう。 ところでYSSの人は配列は2のべき乗にすると速くなると言ってますが みなさんそうしてるのですか?
591 :
デフォルトの名無しさん :2008/02/11(月) 15:22:57
それはデマ スワップが発生しないように最低限の確保が速い
へぇ〜デマばっかりなんですね。 今のパソコンと将棋ソフトでスワップはないと思いますが。 でもそう言うには相応の理由があると思いますが、 実際に実験してないけど理論的には速いはず、というところでしょうか。
593 :
デフォルトの名無しさん :2008/02/11(月) 16:07:36
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の真ん中の値で二分すれば 単純に二倍速くなりそうという感じは受ける。 ちょっと試せないので分からないけど。 ボナンザも歩の交換値2つぶんでAspiration searchをやってるらしいので。。 やっぱり問題はその次からの一回の探索を分ける方法だねえ。
>>599 なるほど・・・
ありがとうございました
>>600 お前コンピュータ将棋もど素人だろ。
ウィンドウを2分割すれば探索ノードもキレイに2分割できると思ってる?
逆に他の手法はきれいに二分割できるの?やろうとしてるの?
ただの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の例えは「並列処理」と言うより「パイプライン処理」だ。
616 :
615 :2008/02/13(水) 19:54:54
あ、先に言われてしまったw。
パイプライン処理も並列処理みたいなもんでしょ。 依存関係があっても適用できるわけだし そういう細粒度の並列処理を ソフトウェアでうまく書く方法ってある? 手の生成→並べ替え→手を打つ 手の生成→並べ替え→手を打つ 手の生成→並べ替え→手を打つ 手を打たないと、次の手の生成ができないから無理か orz
>パイプライン処理も並列処理みたいなもんでしょ。 ぷぎゃー
いや、言いたいことはわかるよ
>617 普通のPCハードウェア(CPU)じゃ無理だね。 パイプライン処理(それも将棋専用の)が可能なCPUじゃないと。 だから「A級リーグ指し手1号」と言う名前で専用プロセッサを FPGA使って開発してる人が居るわけで。
パイプラインによるオーバーラップさせた処理は並列処理の一種
マルチコア環境ではハードでなきゃ無理ということはないと思う 例えばPS3/Cellにはそういう形(パイプライン)の並列処理の枠組みが用意されてる もちろんアルゴリズムは自分で考えるのだが
>622 へー、CellB.E.(SPU?)にそんな仕組みがあるの? 単なるSIMD演算器がさらに8個並列で存在するだけかと思ってた。 個々のSPU内の演算器を自分好みのパイプラインに仕立てられるのか?
624 :
623 :2008/02/14(木) 19:37:44
>622 もしそういう機能が本当にあれば非常に興味深い(使ってみたい)ので どのドキュメントに載っていてどんな名前で呼ばれている機能か教えてくれ。 「Cell Broadband Engine アーキテクチャ」Ver1.01 (by ソニー) をざっと眺めてみたが見つけられなかった。
625 :
623 :2008/02/14(木) 20:06:15
>622 もしかしてSIMD演算機能あるいはSPUを仮想化してマルチスレッド ソフトウェアを走らせる機能を(ハードウェア)パイプライン機能と 混同してない? 普通の(IntelやAMDのx86)CPUもある種のパイプライン(スーパースカラー) 機能はあるけどプログラマが意識的(明示的)に操れるわけじゃないし。
>>625 スーパースカラーはパイプラインじゃないよ
フェッチ→デコード→演算→レジスタ書き出し
フェッチ→デコード→演算→レジスタ書き出し
フェッチ→デコード→演算→レジスタ書き出し
フェッチ→デコード→演算→レジスタ書き出し
こういうのがパイプライン。
スーパースカラは複数の命令を同時に実行できる機能
628 :
623 :2008/02/14(木) 21:20:17
スレッド間同期とパイプライン処理は違うでしょ?
629 :
623 :2008/02/14(木) 21:27:37
>627 スーパースカラー=パイプラインじゃないけど、現在主流のCPUで言う 「スーパースカラー」はパイプライン処理が前提なんだけど。 すなわち複数命令を(同時実行できるものは)同時発行しておいて さらにそれらをパイプライン化された処理装置に叩き込む。 詳細はWiki等を参照してくれ。
どの命令が並列処理できないかコンパイル時点で分かるよね?
631 :
623 :2008/02/14(木) 21:34:30
>630 ??? 何が言いたいの? コンパイラに並列化を任せて明示的に(機械語レベルで)複数命令を 並列実行するならVLIWアーキテクチャだね。Itaniumみたいな。
ちなみに普通の(VLIWでない)CPUはコンパイラが並列処理可能な 命令を見つけたとしてもそれをマシン(CPU)に伝える手段が無い。
さらにちなみにベクタープロセッサ(ベクター型CPU)はひとつの 演算処理(たいていは積和算)そのものを複数のステージに細切れに 分けてパイプライン処理する。したがって同じタイプの演算命令が 次々と間を空けずに来る事が前提。 なのでベクター(行列)の処理に向くと言うか、それにしか向かない。
634 :
622 :2008/02/15(金) 02:16:07
およよ,思いっきり勘違いされた >マルチコア環境ではハードでなきゃ無理ということはないと思う と書いた時点でソフトの枠組みの話をしてることが分かると思ったのだが 分かり難くてスマソ
>634 いいたいことは分かった。 スレッド同士のバケツリレー的なことを API でサポートしてるってことね。きっとイベントキューとかメッセージボックスとか使うんでしょ。 って >622の文脈であの書き方じゃわかるわけねーよ!
俺は使ったことがないが,API より上のレベル, フレームワークが提供されていると聞いている >じゃわかるわけねーよ! 読み直してみると確かに分かり難い.改めてすまんかった
637 :
623 :2008/02/15(金) 22:45:43
やっぱりソフトウェア(開発ツール)レベルでパイプライン(的) 処理をサポートする枠組みがあると言う事だったのか。 >634を読んでしばらく考えてようやく意味が分かったよ。 確かにCellのSPUならマルチスレッド(マルチコア処理)で パイプライン(的)処理をする仕組みを作りやすいかも知れないな。 キャッシュなしのローカルストレージのみで動くから インストラクションの実行時間を確実に見積もれる。 そういう話を聞くと>617が書いてるようなパイプライン処理を Cell(PS3)上で実現できないか、ちょっと考えてみたくなるな。 タスクをそれぞれ均等な実行時間を持つステージに分割できるか、 通信オーバーヘッドがどれくらいあるかが問題だけど。
>>638 THX 勉強になった
>>626 のPDFを見ても、cellってMBOXでSPUが通信できる仕組みみたいだねえ
ハードのパイプラインはクロック同期と思うが、
ソフトでも負荷の無い同期方法ってないもんか?
Stramingモデルってのが面白かった
>負荷の無い ってどういう意味? libspe2 には mbox と signal しか用意されてないけど 自分で作るのもあり
>>639 ハードウェアのクロック同期だって負荷があるだろ。
1クロックよりずっと短い処理だってクロック同期を待たなければならないんだから。
それでもCISCの頃よりは計算資源のアクティブ率は上がった。
ソフト側も同様にプロセッサの稼働率を上げていけばよい。
642 :
デフォルトの名無しさん :2008/03/18(火) 10:22:07
保守
4/6(日)開催予定のオープン戦案内メールをもらった。 しかしソフトはまだ全然出来ていない。 将棋を指す骨組みと通信部分だけくらいは何とかその日までに 完成させて一回は通信対戦テストをしておきたいのだが。 このままじゃ、ぶっつけ本番になってしまいそうだ。
オープン戦に間に合わなければ、 wdoorでテストしておけば? CSAの対局サーバーとは細かい違いはあるようだが…… がんばれ
あげ
646 :
デフォルトの名無しさん :2008/03/23(日) 13:05:40
てなかった
647 :
デフォルトの名無しさん :2008/03/23(日) 15:10:42
ボナンザについて解説してるサイトがあったら教えてください><
>>647 作者のサイトの GPW 2006 発表資料 には目を通した?
あの説明で何かわからないことある?
649 :
647 :2008/03/23(日) 17:44:26
>>648 見てなかったです.
読んでみます.
サンクスです.
>648 あれ読んでも具体的に何と何を入力パラメータとして 選んだのか今一良く分からないんだよね。 各駒種に対してその位置(升目)ごとに重み付けしていって、 それを2個以上の駒の位置関係にまで広げていったら、 あっと言う間にパラメータは1万個どころか百万個以上に なりそうだし、学習を進めると結局、棋譜に現れたもしくは 探索済みの特定の局面に評価値を与えるだけになりそうな気が。 つまり一般化能力なんか全く無さそうな気がするんだが、 私が何か勘違いしてるのかね? コンピュータ将棋に詳しくないために。
>>650 その論文読んでないけど、テレビでやってたやつ見た限りだと
その発想そのままだと思う。
ボナンザの初期バージョンでは数手先まで読むように拡張してみたところ
うまく読み取れない局面があることがわかった。
そこで、ある程度(?)評価の悪い枝についても読むようにしたところ
かなりよくなった。
完全に総当りじゃなくて、ある程度評価がいい手の中でも
多少悪いぐらいでは枝狩をしない
また、相手の手版のときに、多少悪いぐらいの手をさしてくることを
考慮して読んでおくことで、時間を有効に使う
一般的にどうこうするっていうのではなくて
特定の場合に愚直な実装して、枝狩りの閾値さげたら
割とうまくいきました っていう感じだと思う。
他の検索系のやつもそうだけど
この手の総当りが必要そうなものについて、愚直に実装して
動かしてみたら案外うまくったってのが、最近の傾向じゃないかな
人間があーだこーだ考えるよりPCに考えさせたほうが
早いっていう。
だから一般化というより、ある特定のルールのときに
CPU時間を有効に使えるように変えてみたら
アルゴリズムは今までとほとんど同じだけど
勝率があがりました って思ってるけどこれも違うかな?
あくまで素人の意見なんですが。
>>650 > それを2個以上の駒の位置関係にまで広げていったら、
広げない。
将棋は、自玉、敵玉に対する位置関係は重要だが、それ以外の2駒の相対的な位置関係は
あまり重要なゲームではないからだ。
例えば以下の記事が参考になるだろう。
http://d.hatena.ne.jp/yaneurao/20080406 ただし、銀の退路が歩で遮られていないかだとか、歩越しになっていないかだとかは重要なので、
Bonanzaでもそこは考慮に入れていたはず。
653 :
650 :2008/04/11(金) 01:30:39
あり? 良く考えてみると二駒の絶対位置関係の 全ての組み合わせにそれぞれ点数を付与して 行ったとしても、二駒のペアは自由に選べるわけだから 特定の局面に対して点数を付けて行くのとは違うな。 汎化能力はあるか、俺が勘違いしてたわ。 それにしてもパラメータ数が膨れ上がると言う謎は残るな。 愚直にやると駒のペア×位置(マス目)×位置(マス目)で 40×39÷2×83×83で500万以上にもなるか?
>652 なるほど、サンクス! もうちょっと考えてみよう。
655 :
デフォルトの名無しさん :2008/04/11(金) 01:39:58
656 :
654 :2008/04/11(金) 01:52:32
>655 いえ、違います。 ただ単にコンピュータ将棋に関心があって (できれば自分でも作りたいと思ってる) ボナンザメソッドに興味を持った 一介のアマチュアです。
最善手を求めるときって、引き分けがある場合はちょっと工夫が必要なのかな? 反復進化で求めると思うんだけど、その時未知の局面が現れた場合、引き分けの値との関係が難しい。 負け<引き分け<未知<勝ちという図式になると思うんだけど、未知の局面の値は相手から見ても引き分けより 大きくなければならないので、単純に符号を変えるという普通の方法が使えないわけですが 何か一般的な手法があるのかなと思って聞いて見た次第です。
>>657 未知の局面て何よ?
未探索で評価値がわからないなら探索して決めればいいじゃん。
終端ノードなら、静止評価すればいいじゃん。
そんなの反復深化とも引き分けともなんも関係ないよ。
えっと、負け<引き分け<未知<勝ちから分かる通り 未探索の局面を全て調べる必要がないわけですが、深さを制限しないで調べるのが一般的でしょうかね。
>>659 > えっと、負け<引き分け<未知<勝ちから分かる通り
何が言いたいのかさっぱりわからんよ。
基本的なことを確認するが、あんたは普通のαβや反復深化は理解していて
自分でそのプログラムぐらいはすぐに書けるんだろな?
あんたの言う「未知」って何よ?置換表に登録されていないの意味か?
そしてその「引き分け」っていうのは、なによ?
評価したい局面で引き分けにする指し手が見つかっているのか、
それとも「引き分け」というのが存在する将棋みたいなゲームでの
一般的な探索メソッドについて話しているのかどっちなのよ。
上の方にあった千日手関係の話?
で将棋に関するGHI問題の話の結論はどうなったの?
>663-64 結論は既に出てると思うが? GHI問題と言うのは証明アルゴリズムの不完全性などに起因するのではなくて、 千日手などのそこまでの指し手に依存して勝ち負け(引き分け含む)が決まる タイプのルールを持つゲーム(将棋、チェスなど)には必然的に生じる問題。 即ち、ある局面からの勝ち、負け、引き分けを厳密に判定するにはその局面に 至るまでの経路(指し手の履歴)も考慮する必要があると言う良く考えれば ごく当たり前の話に過ぎない。
上のアンカーは >663-664 の書き間違い。
>657の言う「未知」と言うのは千日手になるかも知れないが初手からの 完全な履歴は残してないので厳密に考えると「千日手になるかどうか不明」 になると言う話なのかな? しかし「相手から見ても引き分けより大きくなければならない」と言うのが 良く分からんな。不明な局面の場合「悪くても引分け(千日手)」に持ち込める と言う保証なんか無いわけだから。不利な状況から千日手に持ち込もうとしても 出来ないかも知れない。
うさ将棋本に局面で乱数xorを用いるhash(zobrist hashのことだろう)を、乱数ではなく もう少しいい方法があるらしいことが書いてあるのだが、誰か情報求む。 与えられた数列集合の要素同士のxorを何回かとるときに なるべく衝突しないような数列を数学的に決定する方法があるのか、 それとも衝突しにくい組み合わせを事前にrandomで選んだ数列集合のうち 良いものを探してみましょう、程度の話なのかどちらなのだ?
その本のは知らないけど、以前読んだ何かのプログラムのソースでは 個々の乱数を生成したら立ってるビットの数はチェックしていたな。 うろ覚えだけど16±5くらいの範囲に収まってるかってのだったかなぁ。 この範囲に無ければ再生成。
670 :
デフォルトの名無しさん :2008/04/13(日) 16:32:31
ボナンザでいくつか質問があるんだけど, ・静的評価関数はminimax探索で利用されるんだよな? ・最適化の数値的手法1のスライドの関数f(p,ν)って何? 人工知能は学部で多少勉強した程度で将棋プログラムの経験もないんでとんちんかんなこと 聞いてるかもしれないけど,教えてください
>>669 ああ、なるほど。1のビットの数はチェックしたほうが良さそうだね。
他の乱数とのハミング距離が小さいのは捨てる というのもあった(時間掛かるけど最初だけだからOK)
>670 良く嫁。同じスライドの下に式があるだろう>f()
675 :
デフォルトの名無しさん :2008/04/17(木) 20:19:52
序盤、中盤、終盤はどのように判定したらいいんですか? 50手で終盤の事もあるし、200手で中盤の事もあるので手数とは関係ないと思います 考えられるのは、玉の危険度で測るのがいいと思いますが定番のやり方ってありますか?
676 :
デフォルトの名無しさん :2008/04/17(木) 20:23:10
>>668 数学的な方法って無いと思いますよ
自分でやってみた方法は、プロの 棋譜を読み込んで衝突が起こりにくい乱数を決めておくって方法です
実際に起こりえない局面で衝突が起こらなくても意味がないので
677 :
675 :2008/04/17(木) 20:27:40
読み無しで、玉が詰みそうかどうかを判定する方法がわかれば良いのですが
>>677 > 玉が詰みそうかどうかを判定
これを読みって定義するんじゃないか?
679 :
675 :2008/04/17(木) 21:31:52
危険度を数値化(危険度の評価関数)するって事ですよ 詰みそうならば詰め将棋を読んで、詰まないことが局面だけから判断できるなら詰め将棋をしなくて済みます 玉の逃げ道の多さが危険度に関係ありそうですけど、穴熊だとうごける所は0なのに堅いです どのように危険度を判定するといいですか
それこそ開発者各々の know-how の部分だろ. まずは定番の「コンピュータ将棋の進歩」シリーズを読む. 続いてゲームプログラミングワークショップの予稿集を読む. CSA に入ってトーナメントに参加し,他の開発者から色々教わる. 本格的な議論は将棋板のコンピュータ将棋関係のスレッドで
681 :
デフォルトの名無しさん :2008/04/17(木) 22:19:20
将棋板には人いません
>>675 成駒の数とか敵陣にいる駒の数、あとは王将と攻め駒の距離とかかな。
適当に考えただけだから、実装して上手くいくかどうかはわからんが。
684 :
デフォルトの名無しさん :2008/04/17(木) 23:05:52
サンクス
>679 ちなみに「うさぴょん本」にちょっとだけ書いてあるのを紹介すると ・玉の危険度 「玉の周囲に敵の利きがどの程度あるか、敵の駒がどの程度の距離に迫っているか」 結局、自陣(自玉周囲)にどの程度敵方の駒が利いているかが判定のキモだと思うな。 自陣に利いていても、玉ではない味方の駒で敵の駒の利きを受け止めているんなら まだ固いと判断できるし、何にも無い空間にバシバシ利いているんなら(裸玉)、 もう詰められる寸前だろうし。 固さと玉の逃げ道の広さは当然、矛盾するところがあるので難しいところだけど。
686 :
デフォルトの名無しさん :2008/04/18(金) 00:04:17
しかし、玉の危険度と、通常の評価関数の二つがあると、どちらを優先したらいいのか混乱しますね 統合した評価関数が出来れば一番良いのですが
687 :
デフォルトの名無しさん :2008/04/18(金) 00:49:07
プロの棋譜で、2回以上現れる局面で必然手のない局面は、互角であると思います。 これを基準にして評価関数を調整するといいと思うのですが… しかし、問題があり、2手以上出てくる中盤までしか調整が出来ません。 プロが指した手が最も得点が高くなるように調整すれば全局面に対応出来ますが 例えば、10手読みを入れた結果だとすると、評価値の値を間違えることになります。 しかし、何手読んだのか知ることは出来ず、常に一手読みとして学習したら駄目でしょうか?
>686 ??? そりゃ、両方をひとつの評価関数として統合しないと。 と言うか、玉の危険度も通常は評価関数の一部だよ。 いろんなパラメータを重み付けして足して行くわけだ。 だから手動で調整するとバランスを取るのに四苦八苦するわけだが。
689 :
デフォルトの名無しさん :2008/04/18(金) 01:06:48
>>688 序盤か、終盤か、は通常の評価関数では知ることは出来ないと思います。
互角であっても終盤である事があります。
終盤であることを知るにはどちらかの玉が危険であると知ることが必要と思います。
そのため、玉の危険度と通常の評価関数がないと終盤がわかりません。
690 :
689 :2008/04/18(金) 01:20:20
先手の得点A、後手の得点Bに対して、評価関数をA/(A+B)とするならば MAX(A,B)の値によって終盤判定が行えると思います。
>689 (通常の評価関数の一部としての)玉の危険度と 局面の進行度(終盤度)を計るための玉の危険度の話が ゴッチャになっているね。(私が誤解したのかも知れない) 後者は例えば 序盤度×パラメータA+中盤度×パラメータB+終盤度×パラメータC と言うような重み付け係数として組み込む事になると思う。 玉の危険度は終盤度(進行度)と通常の(有利不利を見る) 評価関数の一部としての両方に表れて良いと思うけど、 進行度の方はあまり凝った評価はしなくて良いんじゃ無いかな? お互いの陣地に成り込んだ駒の数とか持ち駒の数くらいで。 飽くまで私見ですが。
692 :
デフォルトの名無しさん :2008/04/18(金) 01:51:46
5対5でも、8対2でも、最善手を指せば駒交換などの後、数手以内なら状勢は変わらないはずですね。 ボナンザはその前後で評価値が変わらないとして学習しているって事ですか。 何手先の局面と評価が一致するのかが重要ですが。
693 :
デフォルトの名無しさん :2008/04/18(金) 02:15:05
>>691 玉の危険度を正確に評価することは重要と思います。
正確に判定できれば、終盤用の指し手がさせますし、詰め将棋を調べず高速に危険度が求まります。
>>692 の続きですが、評価値が保たれている局面を把握する方法は、既に知られているんですか?
ネットで見る限りでは、駒交換だけ進める様な感じと思いますが…
しかし、それでは飛車・角・香の利きが良く利いているなどの情報は失われます。
694 :
693 :2008/04/18(金) 02:26:04
例えば、銀は取られて、と金が作れて互角になったり、 桂は取られるけど、飛車がいい位置に移動できて互角になったりすると思います。 あとお互いに飛・角がいい位置に移動して互角になることもあります。 静止探索では、飛車が好位置に移動することも考慮しますか?
>>693 > 正確に判定できれば、終盤用の指し手がさせますし、
> 詰め将棋を調べず高速に危険度が求まります。
あんた、ほんとに将棋弱いんだな。
少しでも将棋が指せるなら、持ち歩の一歩の違いだけで
詰む/詰まないが変わることなんてしょっちゅうあることは
わかりそうなものなのに。
結局、ここからもわかるように
単純な関数で正確に評価することは出来ない。
詰め将棋なんて、静止評価に比べれば終端ノードの評価に
計算量を要しないので、詰む可能性が高そうな局面は全部調べればいいじゃん。
>>694 > 静止探索では、飛車が好位置に移動することも考慮しますか?
したければすればいいし、したくなければしなければいい。
その手の評価関数を副作用なしに書くことは非常に難しいので
シンプルな評価関数にして先読みできる量を増やしたほうが
棋力は向上すると思うがな。
697 :
デフォルトの名無しさん :2008/04/18(金) 11:05:35
例えば、三手後に詰みそうな局面が出てきたとします。 先手と後手の指し手が20通りずつあって、そのうち正解手は一手だけとして その400通りの全てで詰め将棋を0.5秒つかったらそれだけで3分以上かかります。 静止探索でググると「 関連検索: bonanza 静止探索 」というのが出てきます。 みなさん bonanzaの 静止探索に注目してるんですね…
698 :
デフォルトの名無しさん :2008/04/18(金) 11:25:43
>>696 評価関数を書くのではなく、評価関数を自動で調整する為に静止探索をつかうんです。
プロの指し手は最善だとすると、静止の局面から、次の静止の局面への評価値に変化はないと仮定できると思います。
2つの局面で評価値が変化しないようにパラメータを決めるんです。
そのため静止局面が正しく判定出来ないと弱くなります。
野暮な突っ込みだけど >その400通りの全てで詰め将棋を0.5秒つかったらそれだけで3分以上かかります 0.5秒は遅すぎです。正確な時間は分からないけど1ミリ秒でも 遅いと思います。
>>697 > 例えば、三手後に詰みそうな局面が出てきたとします。
だから「三手後に詰みそう」だとどうやって正確に判定すんの?
言っとくけど王の近傍だけでは判定できないし、敵王の近傍に
自駒がたくさん利いていても、その利きによって打歩詰めになるかも
知れない。利いてりゃいいってもんでもない。
正確に判定したければ、実際に3手読むほうがよっぽど速い。
> 先手と後手の指し手が20通りずつあって、そのうち正解手は一手だけとして
即詰に関しては平均合法手は20もない。6,7ぐらい。
> その400通りの全てで詰め将棋を0.5秒つかったらそれだけで3分以上かかります。
日本語が意味不明なんだが、3手読むのに要する時間は1ms以下だと思うのだが。
一体、何の話をしてるんだ?
>>698 > 評価関数を書くのではなく、評価関数を自動で調整する為に静止探索をつかうんです。
「評価関数を自動で調整する為に静止探索をつかう」なら
その「静止探索」で使うための評価関数がいるだろ。
> プロの指し手は最善だとすると、静止の局面から、
> 次の静止の局面への評価値に変化はないと仮定できると思います。
できない。少なくとも投了の数手前には形勢はどちらかに大きく傾いてる。
あんた本当にプログラム1行でも書けるのか?
プログラムの書けないキチガイの戯言ならこれ以上付き合わないぞ。
>>701 > あんた本当にプログラム1行でも書けるのか?
今頃気づくなよw
どう考えても最初から素人の妄言だろ
703 :
デフォルトの名無しさん :2008/04/18(金) 13:42:36
>>701 中・終盤で2対8でもいいんです。
双方が最善を指したならば数手以内なら2対8が保たれるはずです。
例えば、いったん飛車がとられるけど、金と桂を取り返せて
初めの静止局面から、次の静止局面の評価はほぼ等しくなるはずです。
プロがミスをしないものとします。
704 :
デフォルトの名無しさん :2008/04/18(金) 13:46:39
>>700 ルートでは詰みはないけれど、探索中の3手後に詰みそうな局面が現れたとします。
このとき、全てに対して詰め将棋を計算するのは効率は悪いって事ですよ。
だから、局面から危険度が求まれば、詰め将棋をしなくて良い場合がでてくるかもしれないってことです。
705 :
703 :2008/04/18(金) 13:48:52
ボナンザの場合、基本は一手後と評価値の変化はないものとして、駒交換が起こる場合は進めた局面と比較するって事でしょう。
>>703-705 あんたがプログラムが一行も書けない
掲示板をsageることすら知らない
日本語がままならないキチガイだって
ことはよくわかった。
プログラムが書けないなら、プログラムの勉強から先にやりなよ。
あんたが小・中学生ならいまからでも遅くはないだろう。
え、痴呆、知的障碍でなければプログラミングなんて いつからだって間に合うでしょう。。
>>707 もちろんその通りなのだが、703の場合は日本語の勉強とかインターネットを使う勉強とか
たくさん他に勉強しないといけないことがあるように思ったんでな。
こいつはリバーシ1くさいな
いや30過ぎてからでは難しいと思うぞ<プログラミング
どうなんだろうな 一種の芸術技能だと考えると確かに30越えはきつそうだが…
すみません、詰め将棋のプログラムつくっているんですけれども、 無駄合いの判断でつまっています。なにかいい考え方はありますでしょうか?
>>712 「コンピュータ将棋の進歩」の1を読んだらどうだ?
>712 うさ親さんの「コンピュータ将棋のアルゴリズム」にも解決法が 示されているよ。「王手を掛けた駒で合い駒を取り、その合い駒を 玉方にすぐに返した時にそれでも詰むならばそれは無駄合いである」 と言う考え方らしい。 「柿木のアルゴリズム」と呼ばれるのだそうな。
玉側の利きが無くて玉の周囲で無い駒はりは無駄合いの確率が高い。 まとめると、引きつけておいて、その駒が取れて逃れられるケース以外は無駄合いらしいということ。
716 :
デフォルトの名無しさん :2008/05/03(土) 14:34:10
アマチャンピオンがAIに負けたようだな
山下BBSで初心者が完全スルーされててワロタ
皆さんに教えてください。 思考部分の将棋ソフトを作ろうと考えていますが。 GUIに「CSA将棋」を使うか「将棋所」を使ったほうがいいか考えています。 他に何か良さそうな物が有れば教えてください。 行く行くはコンピュータ将棋選手権に出たいと考えています。
どちらでもいい。思考本体さえ出来れば入れ替え簡単
了解しました。では、サービスがよい「将棋所」で作ります。ありがとうございました。
将棋所ってはじめて知った。USI対応のGUIなんてあったんだ。 俺も将棋プログラムしてみようかな…
>>718 こいつ?
2回目以降の探索の確率は 投稿者:初心者 投稿日:2008年 5月 7日(水)03時15分22秒 編集済
2回目以降の探索の確率は、どうやって決めますか?
1回目の探索で、たとえば、王手やそれをかわす手、飛車取りやそれをかわす手などは
高い確率にするのは当然と思いますが、2回目は得点に応じて確率を割り振りますか?
しかし、得点比率で割り振ると飛車が逃げる手が10通りあってどれもがほぼ同点だと
重要な手なのに、割り振る値は小さくなってしまいます。
かわす場合は特別で、一手であるかの様に扱うとかわしてすぐに取られてしまう手にも
高確率を与えてしまう事になります。
あと初期の確率は、完全に無視して、得点だけにするかどうかもはっきりしません。
かわす手はその時点で、一番高い一手のみを採用して、あとは無いものとして扱って
確率を分配すれば良さそうですね。その手を使って不利にならなければそのままで良いし
無視したほかの手より得点が下がればそちらを採用すればいいので。
将棋所のLaramieとか序盤がめっちゃくちゃで萎える・・・ そのくせ駒がぶつかると強くなる 将棋の勉強にちっともならない
CPUで勉強しようとする頭がオカシイんだよ^^たまには外でなよ><
逆に考えるんだ。 序盤なんてどうでもいいんだと
原稿料の算定基準が掲載されていないな
集客力のあるブロガーほど報酬が高いのは当たり前
ここのところ屋根裏は毎朝宣伝こいてるな
集団ストーカー激指&やねうらおはもはや有名
弓月とか言うキチガイは、あの天下のやねうらお様に遊んでもらえて幸せだな。
以上、集団ストーカーの実演でした。
>>738 お前は、半角入力すら出来ない知能障害者
なるほど。
--
727 名前:デフォルトの名無しさん[SAGE] 投稿日:2008/05/20(火) 13:34:56
yaneuraoの宣伝ブログの裏側はこうなっています。
http://www.pressblog.jp/static/pressblog.aspx yaneuraoのブログを訪問したり、コメントしたりすると、原稿料がアップする仕組みです。
731 名前:デフォルトの名無しさん[SAGE] 投稿日:2008/05/20(火) 14:46:03
集客力のあるブロガーほど報酬が高いのは当たり前
733 名前:デフォルトの名無しさん[SAGE] 投稿日:2008/05/20(火) 14:57:35
ここのところ屋根裏は毎朝宣伝こいてるな
734 名前:デフォルトの名無しさん[SAGE] 投稿日:2008/05/20(火) 14:59:45
集団ストーカー激指&やねうらおはもはや有名
738 名前:デフォルトの名無しさん[SAGE] 投稿日:2008/05/20(火) 17:54:45
以上、集団ストーカーの実演でした。
--
判りやすいと言うかなんと言うか……
741 :
デフォルトの名無しさん :2008/05/20(火) 19:11:12
やねうらおは明日も宣伝をこく。きっとこく。
全角の人以外に空欄はいないので(略)
なんだこいつ・・・きめえ・・・
詰め将棋を研究して数学的になぜ詰めるのかが分かればその延長線上に最強プログラムがあると思うよー あとチェスでいうオープニングの研究もしたほうがいいと思うよー
詰め将棋は既に十分に強いんです
ki2 書式の質問です。 ▲7六歩 △3四歩 ▲2六歩 △4四歩 ▲2五歩 △3三角 ▲4八銀 △4二飛 ▲6八玉 △3二銀 ▲7八玉 △7二銀 ▲5六歩 △4三銀 ▲5八金右 △9四歩 ▲9六歩 △6二玉 ▲5七銀 △6四歩 ▲3六歩 △7一玉 ▲8六歩 △5二金左 ▲8七玉 △7四歩 ▲7八銀 △8四歩 ▲3八飛 △3二飛 ▲6六歩 △5四歩 ▲6七金 △6三金 ▲6八銀 △8二玉 ▲7七銀右 △4五歩 ▲7九角 △5五歩 ▲3七桂 △5四銀 ▲5五歩 △同 角 ▲5六金 △4四角 ▲5八飛 △2六角 ▲4五金 △5三歩 ▲5四金 △同 歩 ▲4三銀 △3三飛 ▲5四銀成 △同 金 ▲同 飛 △3七角成 ▲4六角 △3六馬 ▲4四飛 △4三歩 ▲6四角 △7三銀打 ▲4六飛 △6三馬 ▲4二角成 △5二金打 ▲3三馬 △同 桂 ▲3一飛 △2五桂 ▲3四飛成 △3七角 ▲5四金 △6二馬 ▲2五龍 △5三歩 ▲5五金 △1九角成 ▲6五桂 △4六馬 ▲同 歩 △5七飛 ▲5八歩 △1七飛成 ▲3三角 △6七香 ▲5九金 △6八歩 ▲1八歩 △3七龍 ▲1五角成 △3九龍 ▲4八馬 △1九龍 ▲3七馬 △3九龍 ▲4八馬 △同 龍 ▲同 金 △6九歩成 ▲6七銀 △7九と ▲2九龍 △8九と ▲同 龍 △5四歩 ▲7三桂成 △同 馬 ▲6五金 △5三桂 ▲5四金 △5五桂 ▲7八銀 △2七角 ▲5三金 △同 金 ▲6五桂 △5四角成 ▲5七金 △6四馬上 ▲5六香 △6三金 ▲8八玉 △7三桂打 ▲2一飛 △6五桂 ▲同 歩 △同馬右 ▲6六銀打 △6四桂 この棋譜において最後の行の△同馬右です。これは△同馬直と書くのが正しいと思うのですが。 柿崎将棋では正しく処理されています。何故なのでしょう? 右と書いて右に無ければすぐ下を探すというのが正しいのですか? ちなみに直と書き直しても正しく処理されました。
748 :
747 :2008/05/22(木) 16:01:10
自己レス。同じような記述を複数見つけ、これが正しいと理解しました。 お騒がせしました。
>>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:5筋位取り 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:NHK杯 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:IBM杯 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:NHK杯 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の解析を各自のコンピュータで分析した結果をあつめて 実現しようっていうのがあったとおもうけど それと似たように分散している計算力をあつめて全ての局面を評価するってできない?
分散処理は既に行われてるが全ては無理
将棋も囲碁もその場が今どちらが有利かなんて人によって考えが違うに決まってる だから色んな人工頭脳をもった将棋プログラムを作ればいいと思う 俺には無理だけど
ログも読まず低レベルながらに頑張って口出ししては消えていく そういう輩が時々現れるよね
>>764 ちがうわ 29**81かw
81C40 * 29**40 でもいいか?
このスレの過去スレを読みたいのです。どこかで見れますか? 又は、持っている方UPお願いいたします。
768 :
デフォルトの名無しさん :2008/06/01(日) 12:29:25
ありがとうございます。
どういたしまして
仮にすべての局面を評価できるとしたら、投了直前の局面をすべて生成して勝ち負けつけて 開始局面に向かって戻っていくだけだから、連続的な評価値なんて不要
>>771 戻して行く?
どこで手駒を使ったかまで遡れるのか?
>764 (現在の)局面状態だけを見て各局面への遷移を分類するのは難しい。 あちこちにループが発生する。詳しくはこのスレを頭から良く読んでね。
>771と>772が想定している「全ての局面」の意味が違うようだな。 つまり、その局面に至る経路情報を含めて分類してるのか、 経路情報は捨てているのか?
>775 居ないんじゃないかな? オセロや囲碁と違って将棋は終盤がなかなか収束しない。 終局図が何通りあるのかも良く分からんし。
>>771 投了局面から「詰めろ?」を遡ることで
投了局面より前の局面の勝敗を決定できるのは確かだと思う
だけど更に遡ると、遡ったのとは違う経路で将棋が進んで
違う結果の局面になることがあると思う
一手で形勢逆転するような手があると思う
>>773 ループは枝刈りするとか対策は考えられるんじゃないかな
目標の中間局面に到達するまでの手の経路は
手数が多くても少なくても勝敗には関係ないよね
最短でなくて遠回りしてもいい
さしてるうちに、最初目標としていた中間局面じゃなくて
自分に有利な別の中間局面に変えてもいいし
・ルール上可能な局面(駒の配置図)はそれぞれがネットワーク状に「手」で繋がる ・局面のサブセットにだけ勝敗の評価が決まっているものがある ・局面の遷移がかなり限定されていれば(詰めろみたいに)勝敗の評価を決められる ・そのほかの局面は手によって評価が変わる って感じのイメージを持ってる
上の方で議論になっているけど 将棋の「局面」を見て形勢を判断するためには 単なる盤上や駒台の様子だけではなく その局面に至るまでの経緯も必要 極端な話、たとえば指しかけを引き継いだとして 「この盤面は敵玉に詰みがあるぞ!」と思っても それは千日手の4回目かもしれないとかそういうこと
>777-778 末端局面から遡って勝ち、負け、引き分け(千日手)で 確定的にラベル付けするだけじゃなく、 途中局面に中間的な評価値を付けようって事? おもしろい考え方だが、一体どうやって?
末端局面からさかのぼるのなら途中も当然 「勝ち」か「負け」か「引き分け」になるだろうって
>>779 > それは千日手の4回目かもしれないとかそういうこと
(現在の技術で可能かどうかは知らんが)データベースを引くのだから、現在の局面に
至るまでに詰みがある局面を逃しているはずはないと仮定できるだろう。
だから、連続王手の千日手のことは考慮しなくて良いと思う。
>>779 ソフトが「この盤面は敵玉に詰みがあるぞ!」と思って指したら。
システムから千日手で引き分けと言われるだけで。その事にソフトは何の関係が無いわけ。
それを操作した人間が、あちゃ〜〜前に勝ってたのか、と思うだけ。
それに何の問題があるのか?
引き継ぐ前の事を意識する必要は無い。
>781 もちろん、そうなんだが >777-778が何か面白いアイデア持ってないかな?と。 例えば勝ちに至る経路の広さや近さで評価値を付けるとか。
なんかminmax法も分かってない奴がいるな
>>786 いや、「神ならぬ人間がその盤面を引き継いだとして
どれほど勝ちやすいか」っていう評価値じゃね?
>>782 自分についてはそういう仮定を置くのもアリかもしれないけど
少なくとも相手のことについてはまずいだろう
「うむ、俺が勝つにはこの手しかない!
でも相手にこう王手されるとまずいな…
しかたない。勝ちはあきらめて千日手に持ち込むか…」
というようなケースってあるじゃんか
ところがこの相手の王手が千日手の4回目かもしれない
>>788 与えられた局面が勝ちか負けかを判定するデータベースを構築する話をしているんだろ?
相手がポカして相手が勝てる局面を(その勝ちのための指し手を連続王手の千日手で)負けの状態に
してようが、それはデータベース構築には何の関係もないことだろ。
引き継いだ前の人間の意識を、引き継いだソフトは考慮する必要は無い。 もし考慮して欲しいなら、その旨のインターフェースを作るべき。 しかしその人間の目的を読み取る機能は、最強の将棋ソフト作るより遥かに 困難な人工知能が必要。
>789 実はそのデータベースを構築する事そのものが、その局面に至る経路を考慮する事を要請する。 さもないと探索あるいは末端局面からの遡りが止まらなくなる。 良く考えてみないと分かりにくい事だが、なぜ千日手のルールがあるのかを考えてみよう。
>>789 「それは関係ないことだから関係ないのである。」
では説明になってないぽ
だからさ、一連の流れのある局面が、他の流れのある局面と同じと言う事は無いのかと、言う事だろ。
流れとか「局面」とか、意味のあいまいな言葉を無定義で使うなよ
隣の将棋盤の駒の配置と持ち駒の数や種類が、その隣の違う対局の数時間前のときの全く同じ将棋盤の駒の配置と持ち駒の数や種類がある手において、同一だったと言う事は無いのかと言ってる。
>795 「流れ」と言うのはある局面から別の局面に至る経路の事だよ、多分。 >794じゃないけど。 で、違う経路から見かけ上同一の局面に至る事は それこそ幾らでもあるし、ループする事もある。
798 :
デフォルトの名無しさん :2008/06/01(日) 23:03:43
評価値として 勝ち、負け、千日手、勝ちか千日手、負けか千日手 を定義すれば局面評価DBを作る点では問題無くない?
>>798 問題ないかどうかは、どういう目的で作るのかによるけど
そもそもそのような評価が、駒配置だけを見て可能か
ということに対して懐疑的なんだと思うよ
今の指し将棋プログラムは現状の局面状態(駒割と駒の配置)だけで持って、 盤面を評価してるように見えるから >789のように勘違いする人も居るんだよね。 ところがその評価はかなり荒い近似に過ぎないから通用するのであって、 厳密に確定局面から遡って評価しようとするとそこに至る経路情報が必須になる。 詰め将棋プログラムは確実に経路情報を考慮してるし、しないと答えを間違う。 いわゆるGHI問題。
801 :
デフォルトの名無しさん :2008/06/01(日) 23:29:54
経路情報は局面間を結ぶ有向線として持てると思う 勝ち負けの決まる局面は確かに存在する これらの情報で中間局面をどう評価するかだけど 相手の手が何であっても勝ち局面に遷移できる局面は勝ちたが 相手の手によって勝ち千日手負けのいずれも有りうる局面もあると思う そんな局面は勝ちやすさで評価する 勝ちやすさは例えば勝ち評価値の局面への距離とかで決める そんな単純じゃないと思うけどね
>>800 俺はコンピュータ将棋の開発者で、GHI問題はもちろん知っている。
GHI問題を正しく理解していないのはお前のほうだろ。
詰みのあるすべての局面の集合から逆算してんだぜ?
GHI問題なんか起こるわけないだろ。
ただしそこに至るまでに同一局面が3回以上出てきていないという条件が必要だが。
(連続王手の千日手を発生させないため)
>>802 >ただしそこに至るまでに同一局面が3回以上出てきていないという条件が必要だが。
おいおいw
> 俺はコンピュータ将棋の開発者で、 権威づけか
>>805 実際に作ってもない/作れない/作ったことがない奴に言われたくないね。
作ってるのに理屈がわかってないんだとしたら そっちの方がよっぽど問題のような… そんなに俺様の言うことを聞けって言いたいなら コードの断片でもうpしてからにしろよ できないならおとなしく名無しに戻っとけ
>>807 理屈がわかってないのはお前。
お前はGHI問題が何故発生するのかわかっていない。
>俺はコンピュータ将棋の開発者 イタイ奴が来たなwww 頭おかしんじゃね?
>807 詰め将棋解法プログラムのような答えが 厳密に求められる問題に取り組まないと 開発者と言えども勘違いする可能性はあるな。
>>810 お前もGHI問題が何故発生するのか理解できていない。
812 :
807 :2008/06/02(月) 00:40:44
>>808 いや俺は横から茶々を入れてるだけで
何も言ってないんだけどな
自分以外(正確には自分に異論をいう奴)を全部
一人の人間だと思っちゃうっていうのは
ありがちなことなんだけどかっこよくはないよ
GHI問題については
>>191 あたりから始まって
>>234 とかの議論でさんざんがいしゅつなんだけど
もちろんそのへんはログ読んだ上でのレスだよな?
しかも「お前はわかっていない」とかじゃなくてさ、
だったらちょっと簡単にでいいから説明してみろよ
ほら
経路君のソフト楽しみにしてます^^
814 :
789 :2008/06/02(月) 00:44:07
>>812 詰み局面から逆算するんだぜ。GHI問題なんか起こらないよ。
GHI問題が起きるのは、探索中の循環を即、不詰めと判定するからだ。
GHI問題でよく話題になる図を勝ちの局面であるIから逆算して行くとわかる。
お前ら、シャープの亀山工場で液晶を組み立ててる工員が みんな液晶の仕組みを理解してるだなんて思ってないだろ? そういうことだよ
>814 どのように逆算するの? つまりその逆算する時に経路情報を考慮するの?しないの?
>>814 あー詰み局面から逆算していく話が続いてたのか
その場合で、局面というのは駒配置だけじゃなくて
局面の出現回数も持たなきゃいけないよな
そうしないと、千日手になるはずの手順は
永遠に「勝ち」とも「負け」とも塗られないことになる
ような気がするんだが
○→○→○→○→○ ↑ ↓ ○←○←○ こういうループだけじゃなくて ○→○→○→○→○ ↑ ↓ ○←○←○ こういうループもあるよな
819 :
789 :2008/06/02(月) 00:53:08
>>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の局面の勝ちを判定できている。
>>818 ./ニYニヽ
r、r.rヽ. / (0)(0)ヽ
r |_,|_,|_,|/ ⌒`´⌒ \ で?っていう
|_,|_,|_,|_,| , -) (-、.|
|_,|_,|_人 (^ iヽ__ ノ l |
| ) ヽノ | `ー'´ /
| `".`´ ノ
入_ノ
\_/
/
/
822 :
789 :2008/06/02(月) 00:56:33
823 :
789 :2008/06/02(月) 00:57:20
>>820 すまない。俺は意地悪なんじゃなくて図とか苦手なんだ。ほら…わかるだろ。
824 :
789 :2008/06/02(月) 01:02:58
>>817 > その場合で、局面というのは駒配置だけじゃなくて
> 局面の出現回数も持たなきゃいけないよな
「局面の出現回数」は持たなくてもいい。
>802で書いたが
「ただしそこ(判定したい局面)に至るまでに同一局面が3回以上出てきていないという条件が必要」だが、
これを前提条件とできるなら「局面の出現回数」のデータベースへの記録は不要。
ただし、勝ち/負け/引き分けとラベリングされた局面はすべて記録(データベース上に保持)していることが前提。
>>882 あれ、与えられた局面が勝ちか負けかを判定するデータベース
つまり必勝定跡を構築する話をしているんだと思ってたんだが
そして、その「局面」というのが駒配置だけでよいのか、それとも
駒配置の出現回数も持っていなきゃならないのかだと思ったが
経路という言い方をするからGHI問題と絡んでいるように見えて
いろいろみんな混乱したるんじゃないかな
それで、仮に、駒配置だけで勝ち負けが決まるのだとしたら
もちろん「この局面は千日手」というラベルを貼られる
局面(駒配置)もあると思うのだけど、
詰み局面(駒配置)からたどっていったとき
千日手のラベルを貼る機会というのはどういうとき?
826 :
789 :2008/06/02(月) 01:04:53
827 :
789 :2008/06/02(月) 01:06:49
>>825 > あれ、与えられた局面が勝ちか負けかを判定するデータベース
> つまり必勝定跡を構築する話をしているんだと思ってたんだが
その過程で引き分けデータベースも出来るだろ。
> そして、その「局面」というのが駒配置だけでよいのか、それとも
> 駒配置の出現回数も持っていなきゃならないのかだと思ったが
俺の言う 局面 とは 盤上の駒配置・手番。その局面の出現回数は関係ない。
>>824 あー、その条件があればたぶんそうだよな
でも前に進むなら、ループしたら「千日手」、でいいと思うけど
後ろに戻っているのだから難しい気が
まあ、どうせ局面(駒配置)の数は有限なのだから
全部調べて「勝ち」にも「負け」にもならなかったものは千日手
でいいのかもしれないけど
829 :
789 :2008/06/02(月) 01:20:12
>>825 > 詰み局面(駒配置)からたどっていったとき
> 千日手のラベルを貼る機会というのはどういうとき?
いま、 A,Bが未ラベルとする。Aは自分の手番、Bは相手の手番とする。
このとき A→B→A のような循環を発見した。
AからB以外に行く手は負けとする。
BからA以外に行く手は勝ち(=相手の負け)とする。
このとき自分にとっても相手にとっても千日手を選択するのが最善だからA,Bの局面の最善は引き分け。
このように未ラベルの局面同士の循環を発見して、この循環がお互いの最善であるときこれらの局面を
引き分けのリストに追加する。
825はどうも勘違いしているようだが、このA,Bの局面の「出現回数」を記録しておいてもこの循環の検出の役には立たない。
>>818 下の図は「双方最善を尽くしたら出現しないはずの詰み形」かな
つまりループからしか到達できない詰み形
でもそれを排除してしまったら次の一手解答マシンとは言えないよ
>>829 あー、うんそれならいいよ
ようするに
>>828 の後半と同じことだな
神ならぬ人間から盤面を引き継ぐことはない、という前提なら
たぶんそれでいいんじゃないかと思う
「勝ち筋があるけど、引継ぎ元が棋譜汚しをしてくれたせいで
千日手になるからそれは指せない」とかは考慮しないということで
832 :
789 :2008/06/02(月) 01:28:14
829の続き。 引き分けの検出のために、局面の循環を発見する方法は別の方法が必要だ。 例えば、次の例を考える。 A,B,Cが未ラベルで、Aは自分の手番、B,Cは相手の手番とする。 ・AからB,Cに遷移でき、それ以外は負け ・B,CからAに遷移でき、それ以外は勝ち(=相手の負け) この場合も双方、千日手にするのが最善である。 この循環を検出するためには、AはポインタでありB,Cをポイントしており、 B,CもそれぞれAをポイントしていると考え、JavaVMなどで見られる garbage collectorのようなものを実装する必要がある。(この説明でわかってもらえるだろうか?)
833 :
789 :2008/06/02(月) 01:31:04
832に書き忘れた。 garbageが起きて回収されるなら、それは循環参照がされていたということだ。 garbage collectorの実装はいろいろあるから、詳しくはその手の本を見てくれ。
>>832 あー、GCが循環参照を発見する方法か
でも、現実的な時間にリアルタイムで計算するのではなくて
巨大な次の一手解答集を用意するイメージなのであれば
勝ちでも負けでもないものは引き分け、でいいような
835 :
789 :2008/06/02(月) 01:33:45
>>834 おまい、なかなか頭がいいな。
コンピュータ将棋の開発者だな?大会で待ってるぜ!(`ω´)
名無しに戻る。長々と失礼した。
いや、俺は松原先生の本を昔図書館で何冊か読んだ程度で ゲームの数学は全然わからない素人だからあれだが 寝るぽ 乙
>830 そうだよな。 >829の話は尤もらしいのでつい信用しそうになったが、 先手後手双方、最善を尽くした場合の局面だけでなく、 任意の局面にラベリングしようと思ったら 扱えない局面が出て来そうな気がする。 詰み局面から逆算してデータベース化するだけであって、 そんなもの知らないってんなら、それはそれで良いけど。
ループ内に王手が存在するかどうか吟味しなきゃならないから
>>834 の方法はそのままでは駄目だな
839 :
789 :2008/06/02(月) 01:45:11
>>837 > 任意の局面にラベリングしようと思ったら
「1手詰みの局面」のすべてを表す集合から逆算するって話なんだぜ?
任意の局面にラベリングできるよ。
将棋の初期陣形とは何の関係もない。
詰みに至ることが出来る局面の解は(無限のメモリと無限の計算時間があれば)
すべて求めるに決まってるじゃないか。
盤面が有限だから有限でいいけどな
「どうやっても連続王手の千日手に持ち込まれてしまい負け」が処理できない
842 :
789 :2008/06/02(月) 01:52:19
>>838 それはその通り。
検出された循環(DCG)内で、連続王手にならないループが一つもなければないほうの負け。
双方が王手しあうループしかない場合、互いに逆王手を繰り返すことになるのだが、これは
よく知らないが、将棋のルールでは引き分けなんじゃないかと思う。
843 :
789 :2008/06/02(月) 01:53:07
千日手になるときに手を変えなきゃならないだから その4回目に登場する局面を指す方が負けか すると、「どの地点からループに合流したか」が 重要になってくるような気も…。
845 :
789 :2008/06/02(月) 01:57:15
846 :
789 :2008/06/02(月) 01:58:32
あっ。844は842の双方連続王手のことか。 いま検討していたのだが、双方連続王手は普通の将棋の駒では実現できないようだ。
いや、だから A→B→A が連続逆王手のループだとして A は自分の手番、B は相手の手番だとして C → B → A → B → A → B → A と進めば次で B を指せないからこれは自分の負け D → A → B → A → B → A → B と進めば次で A を指せないからこれは自分の勝ち だったら A とか B は自分の勝ちなのか負けなのか
849 :
789 :2008/06/02(月) 02:07:46
>>848 本当だ。俺には証明はスマートには出来ないが。
851 :
789 :2008/06/02(月) 02:26:14
>>850 俺が1分も考えて出来ないと結論を出した。間違いなく出来ない。
>>849 スマートでなくてもいいから証明してくれ
853 :
789 :2008/06/02(月) 02:46:56
>>852 王手の種類を
(A) 王の移動による王手
(B)駒を打つ・移動させることによる王手とにわける。
Aは、大駒の利きが王によって遮断されて敵玉をにらんでいる状態でなければならない。
しかし、…(中略)で、そのように配置することは不可能である。
Bは、その駒を打つ・移動させることが直前の王手を防ぐ手になっていなければならない。
しかし、直前の王手を、(A)、(B)それぞれの場合について場合分けして考えると
…(中略)でこれまた不可能である。
よって、双方連続王手は不可能である。
854 :
789 :2008/06/02(月) 02:57:31
853補足。大駒には、複数マス進める駒で香も含む、としてくれ。 > しかし、…(中略)で、そのように配置することは不可能である。 この部分は、王の影になっていたのが直進できる駒かそうでないかで場合分けするんだ。 もっとスマートに証明出来るかどうかは知らん。
あらゆる局面(駒配置)にラベルを付けられると仮定して 一手目の局面もラベルがつくのかな?
人が居るみたいだから質問。 最近ブックを実装したんだけどブックにはどんな情報を保持すればいい? 今のところ自分はハッシュ値と評価値とそれを算出した読みの深さと勝ち負けなんかのフラグ。
857 :
855 :2008/06/02(月) 03:17:02
>>856 ごめんよワシには判らんし明日仕事だからもう寝る
了解 お休み
859 :
789 :2008/06/02(月) 03:24:02
>>855 > 一手目の局面もラベルがつくのかな?
839の話をしていて、「一手目の局面」が初期陣形のことを指しているなら、
初期陣形にも勝ち/負け/引き分けのいずれかのラベルが付く。
局面の出現確率がないと古い定跡やマイナーな変化に進んでいきそうではある
861 :
デフォルトの名無しさん :2008/06/02(月) 03:39:08
>>861 理詰めゲームとサイコロ賭博は全く違う話ですから食いつかないかと
未来の名人戦は振り駒というランダム要素を 4回取った方が勝ちというゲームですが何か
未来将棋は同時指しでしょ
戦争シミュレーションにターンとかわけワカランよな。 リアルタイムだろどれもこれも。
局面の遷移履歴によって持駒が変わると思う そうすると次に遷移可能な局面の集合が変わる 局面の履歴か持駒のバリエーションを考慮する必要がある
今頃読んだけど、
>>819 データベースを作ったとして、実際に使う時には経路があるにこしたことはないよね。
例えば、データベースには負けと書いてあっても、実際に指し続けて、もし証
明木のどこかで今までに3回あらわれた局面を通過すれば引き分けになるから。
反対意見ではなくて、経路の活用の余地について関連コメント。
>>867 そんなデータベースは現実的に作れる規模ではないというのはおいとくとして・・・
一体、おまいは何の経路をデータベースに保存しとこうと思うんだ?
与えられた局面から勝ちまでの手順か?勝ちまでの手順は木になってるわけで、
そんなものは全部保存しておけるわけないだろ。
しかし、仮にストレージが無限にあって保存できるとしよう。
では、初期局面から勝ちまでの手順をデータベースから取得しようと思うと、
それこそ終局までのありとあらゆる変化を含んだ木が得られるわけだよな。
これがメモリに入るか?宇宙に存在する原子の数より多いんだぞ。
868の続き。 でも、仮に、無限にデータの入る秘密の箱があって、メモリに読み込まなくてもいいとしよう。 この木のなかに、その局面に至るまでに3回現れた局面があるかどうか調べるのに どれだけのコストが必要になる?仮に現れていることがわかったとして、ではその局面を 回避して勝ちに行く経路があるかどうかをどうやって調べるんだ? それってこのAND/OR木を探索しているのと同じだけコストがかからないか? うまくすれば探索しなくてすむとは思うが、1つの局面に対して莫大なindexを貼る必要があるだろ。 宇宙に存在する原子の数の2乗や3乗で済まないと思うぞ。
まあ、そんな完璧なデータベースがあれば、コンピュータは神様と同じ棋力があるわけで、 人間みたいな間違いだらけの棋力の低い将棋を神様に指継いでもらうということ自体が失礼ってもんだ。 でも、もうちょっと建設的な意見を。 勝ち/負け/引き分けをラベリングするときに、勝ち/負けなら「何手で詰む」というのを記録しておけば、 与えられた局面から終局への距離がわかるから、与えられた局面から終局に近くなるほうに向かって、 「3回あらわれた局面を通過」しないように勝ちを探して探索すればいい。 そうすれば、その探索の深さの範囲内では「3回あらわれた局面を通過」しない勝ちを探すことは出来るだろ。 このときの「探索の深さ」が深ければ深いほど正解に近くなる。この手法のほうが経路なんかをデータベースに 保存するよりよっぽどいい。
>>870 チェスのエンディングデータベースですな
3回あらわれた局面を通過しないように、なんて考える必要はないですよ
局面を遷移するときの線に条件が必要だな 例えば桂馬を持っているとか香車が5マス勧めるとか
>>871 俺も「3回あらわれた局面を通過しないように、なんて考える必要はない」派だが、
867が考えたそうだったので、考えてみた。
867では相手が勝を逃した時に千日手で逃れるには経路が必要になると言ったが、 そんな状況を考える必要はないという立場ならそれでいいよ。 現実的には局面だけのデータベースもストレージに載らないので初めから架空 の議論だと思っていたが、俺が何か前提を見逃しているのかな。 気分を害したなら謝るよ。
データベースを一つのPCで全て持っておく必要はないので 分散格納して連携するとか解決策は考えられる 利用するときはデータベースそのものじゃなくて それを使って調べた結果が判ればいいので 通信手段があれば良い 分析も分割して調べた結果を統合するとか方法はいろいろあるんじゃね?
>>874 867は、データベース上に詰みまでの経路を保存する話に見えたので
868-870のような反応になったのではないかな。
どのみち「経路」(勝ち/負け/引き分けを調べたい局面にいたるまでに3回出現した局面のリスト?)
情報があったとしても、それを用いて引き分けに持ち込むにはデータベース上のラベリングされた節点に
対して、AND/OR木を探索するような処理は必要になるけど。
>>875 分散格納しようにも、格納すべきデータ量が宇宙に存在する原子の数を超えるので、
1つの原子に1bitのデータを書き込めるとしても宇宙すべての物質にデータを書き込んでも足りない
という状況になるのだけど。1つの原子に、もっとたくさんの情報を記録できるような技術があれば
また違ってくるのかも知れないけど。
歩とか同種類の駒は区別しないとか いろいろ工夫する余地はあると思うけどな 全局面がむりなら必要度の高い局面とそれに関係する局面を抽出するとか
>>877 筋違い角とか角換り腰掛け銀とか変化が狭い戦法/すぐに終盤になる戦法は
詰みまで調べてデータベース化する価値は十分あるだろうね。
詰みまで調べられないとしても事前に十分時間をかけて探索して、懸案の局面付近の
最善手(だと思われる手)だけでも持っていればずいぶん違うだろうね。
20年後ぐらいには角換り腰掛け銀なんかはコンピュータによって結論が出てるんじゃないかな。
>874 >876 将棋データベースの問題を考える時は (特に断らなくても)記憶容量と計算量が 実用的限界に納まらない事は当然の前提 として良いと思う。 それでも将棋の局面データベースを (特に現在の局面状態だけに基づいて 最善手を与えるデータベースを) 本当に作れるのか? と言うのは理論的に面白い問題だと思う。
どれだけ圧縮できるかというのも気になる 主成分分析/判別分析の固有ベクトルが分かったら評価関数に使えるし
>880 主成分分析か、大学の時にちょっとだけやったなぁ。 将棋の評価に必要な次元がそんなに落とせるのかどうか?
そういう特徴(ベクトル)を探すのに使えそうだから 今は完全に試行錯誤だから,それよりはマシになるかな,と
9x9の将棋(本将棋)だとデータベースがでかくなりすぎて 実現できないのは分かりきっててモチベーションが下がるので まずは5x5将棋辺りからできないかなって考察するのが良いのかも。 もしできたら、それの性質を見ながら本将棋への類推と応用を考えると。
チェスですら終局までの完全なデータベースって無いのね。 将棋なんてまだまだ遙か彼方だな
チェスなら駒が減る一方だから終盤のデータベースは作れたけど、 将棋は駒減らんからな。5五将棋ですら無理じゃね?
んー、でも昨今のCPUの性能を考えると、どこぞのスーパーコンピュータを借り切ったら、 谷川九段を光速でやっつけることができそうな気がするのですが。
>>886 それが出来るのはスーパーコンピュータの性能のおかげではなくて
最近の谷川の性能のおかげなんじゃないだろうか
時とは残酷だな・・・
スーパーコンピュータの性能をなんだと思っているのだろう。 1台辺りの性能で言えば、高々補助単位一個分の違いでしかないのだが。 # それが充分大きいのは事実だとしても。 手の数の爆発はそんな規模ではないからね。
今だったら並列処理の方が単体のスパコンより、 処理速度が上げられる事実。
単体のスパコンって何だ? 今時、スパコンはスカラー型でもベクトル型でも大抵クラスターだぞ。
NECのSXシリーズのCPUなんて2GHzしかない。 ベクトル演算がどんなに速くても将棋じゃ使わない。 COM将棋で必要な整数演算で比較したらSXシリーズは、 個人で買えるCore2Duo3GHzより遅い ちなみにクラスタ構成にしても将棋は速くならない (選手権にクラスタで参加しているチームはない)
>>323 まで読んだ。あとは流し読み。
将棋の完全解析プログラム検証向けの「最小セット」を考えてみた。
駒種全部再現のために自陣、敵陣の概念と全駒種を用意。
桂馬成らずや、角、飛、香の全種類の動きを再現するために横3列*縦5行は必要。
両者に玉がないといけない。
打ち歩詰めと二歩の再現のために盤上に歩が2個以上ないといけない。
するとこうなった。
┌──┬──┬──┐
│▽香│▽王│▽角│
├──┼──┼──┤
│▽金│▽歩│__│
├──┼──┼──┤
│__│__│__│
├──┼──┼──┤
│▲銀│▲歩│__│
├──┼──┼──┤
│▲飛│▲玉│▲桂│
└──┴──┴──┘
自陣、敵陣が3行づつだから中央は自陣でもあり敵陣でもある。
ただし、歩は敵陣の2段目まで入り込まないと成ることはできないものとする。
駒割りが異なるが飛側が先手、角側が後手とする。
これが先手必勝、後手必勝、引き分けのどれなのか完全解析頼む。
先手必勝か後手必勝になった場合は、あえて最善手より少しだけ悪い手を指したときに陥る引き分けのパターンの解析もよろ。
*千日手手順のアルゴリズム入れる必要があるので重要*
これで将棋の完全解析のためのアルゴリズムは全部入れられると思う。
やりにくかったら駒の配置は適当に並べ替えても可。
俺ど素人なんで変なこと言ってたら咎めておくれ。
先手から突っかけざるを得ず、 それに乗じて3三から玉頭を攻めて後手勝ち のような気がする
かくしてこのスレは 「おまいら最強の将棋解析理論提案してみろよ」 スレとなりました。
局面の評価値を格納するデータベースのことだけど 局面を識別する番号とかと、その評価値が判ればいいので 同じ評価値のものをまとめて記録すればいい 例えば、先手勝ちは、100,000番〜4290,000番って感じ 上手く識別番号を付けることが必要になるかも知れないけど あと仮に評価値が(先手勝ち、引き分け、先手負け)の場合 一番頻度の高いものは記録せずに、見つからなかった場合の規定値にするとかで容量を減らせると思う
>上手く識別番号を付けることが必要になるかも知れないけど 無理
age
>>896 つかさ、先手勝ち・引き分け・先手負けの3つの領域を作って、評価値に応じた領域に保存すりゃよくね?
まぁ、そーゆー事して多少容量減らしても焼石に水なんだが。
>上手く識別番号を付ける これを行う関数は評価関数と等価
901 :
デフォルトの名無しさん :2008/06/19(木) 21:23:35
902 :
デフォルトの名無しさん :2008/06/20(金) 07:00:02
ボナンザなどのSIKOU.DLLを補助するDLLを作れば簡単に強くできそう。 たとえば定跡手はボナンザに考えさせなくていいし、 一手目の候補手だけは ボナンザより良い生成が出来るなら、一手進めた局面をボナンザに考えさせる。
903 :
デフォルトの名無しさん :2008/06/20(金) 07:08:11
フリーで、棋譜ファイルから指し手の登録が出来て、激指やAIやボナンザに変換出来るか、 それらの思考ルーチンを乗っ取って、定跡ならそのまま指し手を返すように出来ない?
904 :
デフォルトの名無しさん :2008/06/20(金) 08:39:06
定跡だけ指すプログラムとその定跡ファイルはこちらで作りますから コンバートまたはSikou.dllに対応させる部分を作ってもらえないですかね?
>>902-904 既存のDLLをソースもないのにどうやって修正するんだ。
直接patchを当てるのか?誰がそんなことすると思うんだ?
902-904は本当にプログラムが一行でも書けるのか?
俺には902の意味自体よくわからないのだがボナンザにしても定跡DBにあるものは
思考していないが、それと何が違うんだ?
906 :
デフォルトの名無しさん :2008/06/20(金) 08:57:03
>>905 定跡フォーマットが公開されていなくて、個人が追加することが難しい。
あと、共通の定跡ファイルが使えるようにすること。
Sikou.dllの仕様は決まっているので、
定跡用のSikou.dll → (リネームなどして)思考用のSikou.dll
と呼び出せば、様々な思考に対応出来る
>>906 ああ、そういう意味か。
定跡を別途用意するんだな?
そしてそれは「柿木将棋」の定跡形式か何かと考えていいんだな?
定跡の指し手を返す部分は、>904によると用意してくれるんたな?
定跡手なら、それをそのまま指して、そうでないならボナンザのSikou.dllを呼び出せばいいんだな?
904のプログラム(定跡だけ指すプログラム)が書けるのに、これの何が難しいんだ?20行ぐらい書くだけじゃないか。
本当に、904のプログラムを用意してもらえるのか。そこんとこどうなの。
909 :
デフォルトの名無しさん :2008/06/20(金) 09:16:32
不可能か、難しい点。 製品版の思考の乗っ取り(仲介) (あとbonanza.exeの制御も) 製品版の定跡ファイルへのコンバート GUIインターフェースで棋譜などを追加するツール作成
910 :
デフォルトの名無しさん :2008/06/20(金) 09:21:06
可能なこと。 指し手確率のある定跡ファイルフォーマットを定めて、 それに将棋倶楽部24 、将棋祭り、2ちゃんなどネットのプロ棋譜 を登録すること。
911 :
905 :2008/06/20(金) 09:22:28
俺、905 = 908ね。
>>909 > 製品版の思考の乗っ取り(仲介) (あとbonanza.exeの制御も)
これは製品版でもボナンザは、Sikou.dllを用いていて、このインターフェース自体は
CSAで標準化(?)されているものと同じだろうから、自前でSikou.dllを用意すればいいということなのでは。
> 製品版の定跡ファイルへのコンバート
それはしないでいいのだろう。
> GUIインターフェースで棋譜などを追加するツール作成
902は、たぶん、柿木将棋か何かでやるのだろう。
柿木将棋用の定跡フォーマットなら優秀な定跡を公開している人は結構いるのでそれをそのまま使うのかは知らないが。
912 :
デフォルトの名無しさん :2008/06/20(金) 09:24:55
将棋倶楽部24で50万局、プロの棋譜で5万局 ほどありますから柿木だと処理しきれないと思います
913 :
905 :2008/06/20(金) 09:34:58
>>912 定跡部分なんだから、序盤はほとんど重複してるし、将棋倶楽部24のも
ボナンザより弱い人が指してるようなの入力しても仕方でしょうに。
せいぜい入力するのは5万局ぐらいでしょ。それなら柿木で十分処理できるよ。
そもそも、1局処理するのに1分としても1日8時間かけて480局しか処理できないよ。
そんなペースで100日やり続けても48000局。これ、誰がやるの?自動で処理するプログラム書くの?
ボナの定跡ファイルはいじれるんだからコンバートプログラム書けば終了だろ
提案ですが、現在は激指や東大将棋などはプロの実践譜を解析して 適当に定跡ファイルを作成していますが、それだとどうしても優劣のつく局面まで 登録されてしまいますが、プロの実践譜をコンピュータで形勢判断させて コンピュータが互角と評価できるところまで自動抽出できるようにすれば、 形勢互角と思われる定跡ファイルを作れるのではないでしょうか? ソフトによって形勢判断に違いがあるので個性が出そう
>激指や東大将棋などはプロの実践譜を解析して適当に定跡ファイルを作成しています 開発者が怒りそうな分だなw
917 :
デフォルトの名無しさん :2008/06/21(土) 20:30:18
>>916 あなたは激指や東大さらにボナの定跡ファイルを見て何も思わないですか?
これは1局じゃないだろ?って思わないですか?
経路君の次は定跡君かよw
919 :
デフォルトの名無しさん :2008/06/22(日) 02:44:04
920 :
905 :2008/06/22(日) 03:15:51
>>919 xmlのparserを書くのが嫌。ファイルが肥大化するのが嫌。ベタテキストで十分。
>>902-904 何か、誰が何を言ってるのかいまいち良く分からんのでアレだが
フリー版で公開されてるボナンザVer2.1ならsikou.dllのソースも
定跡のフォーマットも公開されてるじゃマイか?
sikou.dllは思考部本体ではなくCSA将棋から呼び出されて
本体(bonanza.exe)を呼び出すだけの中継用DLLだけど
bonanza.exeを呼び出す際のインターフェースも公開されて
いるのでかなり好き勝手に操れるはず。
(CSA将棋->sikou.dll:CSA将棋がインターフェースを定義、DLL呼び出し)
(sikou.dll->bonanza.exe:Bonanzaの独自定義、anonymous pipe経由)
実際にbonanza.exeを自在に操るソフト(GUI?)を書いて
みたわけでは無いけれどhackフォルダー以下を見るとそう思える。
商用版(Ver2.1や3.0)では呼び出し方など仕様がちがうのかね?
ボナンザ以外(激指やAIなど)と言うか何にでも共通に使える
定跡ファイルの仕様を定めようとか言うんなら、それぞれの
仕様がどこまで公開されてるのか知らないので良く分からん。
922 :
デフォルトの名無しさん :2008/06/22(日) 08:12:05
>>920 parserは既存のを使えばいい
データ属性の変更や他のXMLベースのユーティリティを使えない
>>922 C++から使えてportableでfreeで商用利用可能で省メモリでファイルをシステムメモリに丸読みしないような
xml parserの実装があるなら是非教えて欲しい。
ワラタ
それぞれの思考に未着した定跡ファイルを一般化して統一し。 無理に使用したところで思考部分が弱くなるだけで意味が無い。
926 :
デフォルトの名無しさん :2008/06/22(日) 18:53:51
>>926 DOMなら、通常DOMツリーとして扱うだろ。あれはファイル全体をメモリ上に丸読みする必要がある。
そもそも、923で書いたような軽量なXML parserの実装はこの世に存在しないんだよ。
XMLは大きなデータを扱うのに適していない。
将棋の定跡なんてたいしたデータ構造ではないし拡張するわけでもないし、
parseが難しいわけでもないから、そんなところにXMLを採用するのは
XMLのことを知らない馬鹿のすることだとしか言いようがない。
他人のふんどしで、楽がしたいだけだろ。
つーか、現状をどう認識していてその上で何がしたいのか もうちょっとハッキリさせてもらわないと賛成も反対も 協力もできそうにないわ。
930 :
デフォルトの名無しさん :2008/06/25(水) 02:13:04
931 :
デフォルトの名無しさん :2008/06/25(水) 02:19:09
>>928 parserを作るとか、データ交換の仕組みを作るとかそういうのが目的なら
自分で作ってもいいけど
目的は違うんじゃないの?
だったら目的と違う部分は既存のものを使ってもいいんじゃないかな
他の用途で作られた機能を利用することもできるんだし
それで足りなくて必要になったらその部分を作ればいいだけ
全て自分で作ることにこだわる必要はないと思うけど?
>>930 SAXはinterfaceの規定だけ。どの実装のことを言ってるんだ?
923で書いたような実装があるなら是非教えて欲しい。
あと文字コードもUnicodeとShift_JISが扱えるやつな。
だいたいな、部分的に読んで行こうが、10MBぐらいで済むはずの定跡ファイルが
XMLで書くと200MBぐらいになるんだよ。それでいてparserが書きやすいわけでもない。
読み込み時間も書き出し時間も長くなる。
自分の作る将棋ソフトからそんなファイルを実行時に読み込むわけにもいかず、
別途自分のソフト用の定跡フォーマットを用意しなければならない。
これではメリットがどこにもない。
最初から標準化された小柄な定跡データフォーマットがあれば、自分のソフト用の
定跡フォーマットもそれを使えばいい。parserを二つも書く必要がなくなる。
933 :
デフォルトの名無しさん :2008/06/25(水) 12:52:09
評価の観点はいろいろあるから932が示した要件を満たさなくても利点は有ると思うけど 使いたくなければそれでいいと思う 時代に取り残されるかも知れないけど
>>933 本当にあんた、一行でもプログラムが書けるのか?寝言はいい加減にしてくれ。
935 :
デフォルトの名無しさん :2008/06/25(水) 18:54:04
未知なものへの拒絶反応だな
モノも論理も出さずよく言うわ
つーかさ、定跡って本当に必要なのか? いっさい使ってなくても別にこまらんのだが。
喪前の思考アルゴリズムが定跡を活かせないタイプのものだからじゃね? 一般に強いとされるゲーム用AIは相当数の棋譜を記憶しているもんだが
定跡を暗記させているわけでもないのに、 どんな状況でも、自動的に定跡を導いちゃうアルゴリズムは凄い 是非公開してくれ
チェスでは普通にコンピュータvsコンピュータから 新しい定跡ラインが登場したりもする。
941 :
デフォルトの名無しさん :2008/06/26(木) 00:02:33
将棋の存在しうる盤の状態は10^150通りらしいぞ 囲碁は10^365な オセロは6x6までなら完全に解明されている チェスを完全に解明したという論文があったけど、続報を聞かないし嘘かいな
解明されたのはチェッカーじゃなくて? チェスは聞いたことない。
>>941 プログラムが一行も書けなくて自分で検証する能力もないくせに
わけもわからず検索して貼り付けなくていいよ。
>>902-904 マイボナの作者がu2bというUSIとBonanzaのsikou.dllの橋渡しをする
プログラムのソースを公開している
そのソースを改造すれば、オリジナルの定跡を指させたり、
Bonaがやってないルートで詰め将棋ルーチンを呼ぶといった改造はできる。
だから将棋はなぜ詰めるのかを数学的に解ければその結果を利用して最強になれるんだって、 だれか本気で詰め将棋を研究すれば人間では勝てなくなるようなプログラムが作れるはず。
既にほとんどの人間は勝てないけど。。。 それよりも一般的に効率よくゲームが強くなる方法があればいい。 まぁ「唯一の確かな基準である勝敗」が調べやすい局面を研究するというのは分かるが。
>>946 詰め将棋は既に本気で研究されてますよ
dfpnでググってみて
いくら読んでも詰みがみつからない序盤から中盤はどうすんだよ 序盤で劣勢になったらプロレベルは挽回不可能
950 :
デフォルトの名無しさん :2008/07/04(金) 03:52:20
そこで定跡の登場たい
>>946 > だから将棋はなぜ詰めるのかを数学的に解ければ
二人零和有限確定完全情報ゲームだから?
千日手があるから詰めない状況もあるんじゃ?
>>952 千日手は攻めてる側が手をかえなきゃならない....と思ってたんだが、
念のためwikipediaを見てみたら
>手番が全く同じ状態が1局中に4回現れると千日手になる。
>千日手になった場合はその勝負をなかったことにする。
ってなってた。そうか、ノーゲームにできるのか。
手を変えなきゃいけないのは連続王手の千日手だろー
攻めてる側が手を変えるというルールはずっと昔のものだ。
つか明文化されたルールってないよね<将棋
どんなゲームにだって、ローカルルールがあるのさw 将棋における日本のローカルルールは 日本将棋連盟が明文化しているらしい。
>>958 明文化しているけれど非公開らしいね
ガイドブックのやつは一般向けのルールってことで
穴を指摘されても修正しません、ということらしい。実際穴はたくさんある。
日本将棋連盟によるルールと、俺んちのルールはちげーんだよ! って言う方ですね?
>959 ルールにはっきりした穴があると思うなら日本将棋連盟にメールか何かで指摘してあげたら? 俺が認識してるルールの多少なりとも曖昧な点は双方入玉時の持将棋宣言くらいだが。
>>962 ゲームのルールを改訂すると、過去の棋符に影響するんじゃないの?
その辺どうなのかな?
まあ、過去は過去ってルールーにしちゃえばいいんだけどねw
964 :
デフォルトの名無しさん :2008/07/07(月) 14:54:48
ルールーwww
このスレでは、コンピュータ将棋協会の対戦ルールで十分だと思われ。 他のルールはスレチ
このスレ、久しく書き込みが無いのに良く落ちないな。
967 :
デフォルトの名無しさん :2008/08/07(木) 22:26:54
そりゃ、あんたみたいなホスマンがいるからネw
968 :
デフォルトの名無しさん :2008/08/11(月) 02:17:34
>>968 !!!
「まるで機械のようだった」(そらそーや)とはどんな打ちまわしだったのでしょうか?
>>969 一旦優勢になると多少の損は気にせず勝ちを最優先する打ち方
実際一目半という微差だったわけで(アマ有段でもこれは難しい)
人間は最善手=最も得する打ち方をするから
>一旦優勢になると多少の損は気にせず勝ちを最優先する打ち方 >人間は最善手=最も得する打ち方をするから ダウト
んじゃ省略した「大抵の」を補足
↑関係無しw
ダウトとか関係無しとかじゃわかんないよ。
>>975 「自称」天才クンは放置した方が賢明だぞ。
まさかのダウト失敗www
Bonanza methodとか強化学習とかで学習したときに、値が極端に大きくなっちゃう人いませんか? 例えば、盤上の駒価値と持ち駒価値を学習したとき 駒価値の値の幅に対して持ち駒の値が極端に大きくなってしまうような
乱数変えてやり直せ バグの可能性やデータがオカシイ可能性もあるが
>>979 ありがとうございます
なんだかんだで結局バグな気がするんですよね・・・
乱数はとりあえず外してるんで、問題にはならないはずなんです
学習途中までは盤上駒価値もそれなりの値で、持ち駒価値もそれなりの値なんですけど
持ち駒価値間の比率が正しいながらも、盤上の駒価値とくらべて極端に大きくなっちゃうため
盤上駒価値まで影響を受けてしまっておかしな値を返してしまっているんです
駒価値は、総和で制御しているんですが持ち駒価値のほうも何か制御が必要なのかなぁと。。。
駒価値の総和がコントロールされてれば 相対的に持ち駒価値も抑えられるはずだよねぇ 全体がまともに動いてれば 最終的な評価値にするところが可変重みになってたりしない?
>981 駒の価値の総和が一定値で抑えられてたとしても盤上の駒の価値と 持ち駒の価値のバランスが崩れて行くって話じゃないの? >980 学習を試した事が無いので当てずっぽうな意見で申し訳ないが、 そういうのを制御するのがペナルティーとか拘束条件とか言う奴じゃ?
>>981 可変重みって言うのは、学習途中の重みってことですか
学習時に行う探索によって得られる末端局面の評価は学習途中の重みでやっています
なので学習途中では、探索も得られる評価値も精度が低い(まったく正しくない)評価関数で評価しています
学習途中評価関数の精度が低いのは、まぁ仕方ない話なんですよね。。。
>>982 バランスが崩れていくって話で正しいです
とりあえず拘束条件としては駒の価値の総和が一定になるように制御してます
>983 拘束条件だけじゃなくペナルティも入れれ。(M2(v)のとこ) スライドの「ペナルティーの導入」のページにあるとおり、 これが正に駒割の割合を高く保つためのもの。
>>980 駒の価値だけ固定しても別解や極小点が出るんだろう。
例えば、位置評価とかで、頻繁に該当するところの点数が全体的に高ければ、
駒の価値が高いのと似た状態になる。
理論上はサンプルを多くすれば解消されるんだろうけど、
Bonanzaのように6万局でもまだ足りないんだろうな。
>>984 やっぱりペナルティ必要ですよね。。。
ペナルティをかけると、その対象の値の絶対値が抑えられるって言うのは理論から分かっているつもりなんですが
・持ち駒価値にペナルティをかけることによって、持ち駒価値が必要以上に値が小さい値になる
・結局駒価値とのバランスが崩れる(持ち駒が小さくなりすぎる)
ような気がして敬遠していました。
スライドの式通りにペナルティを入れれば、バランスが取れた状態で上手くいくのかもしれませんね。
ちょっと理屈は横に置いておいて試してみたいと思います。
色々ご指摘ありがとうございます。
コンピュータ同士の勝負で生成した棋譜をサンプルに学習すればいいじゃない
コンピュータがプロ棋士より強ければな
終盤に近いほどプロより強い
終盤に近くなる前に勝敗が決定していれば、終盤など無意味じゃん。 途中で「まけました。」で終わるだけ
だから学習するんじゃない
そもそも学習する棋譜がプロより強い必要なんか無いだろ。 そこそこ強い棋譜なら大抵のパラメータはそれなりの値になるはず。 飛車しか使えないようなヘボの棋譜とかでもない限り。
プロ棋士の棋譜が入手できない状況なら、それほど強くない対局者の棋譜も意味がある。 しかし、プロ棋士の棋譜を6万局も入手可能な現状でそれでもデータが不足する部分を アマチュアやコンピュータ将棋の棋譜で補う事が果たして有益なのかどうか? 下手に学習するとかえって弱くなる可能性が高いだろう。 既存の棋譜がほとんど無い状況ならコンピュータ将棋の自己対戦棋譜も有用らしい。 柿木さんの行った5五将棋における学習がその例。
教師信号に優先順位なり重みなりをつければいいじゃない
具体的に頼む
伸びそうな話題だ 誰か次スレ立ててくれ
うめ
.
.
1000ならジュースでも飲むか
1001 :
1001 :
Over 1000 Thread このスレッドは1000を超えました。 もう書けないので、新しいスレッドを立ててくださいです。。。