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

おまいら最強の将棋プ ..

41:デフォルトの名無しさん
07/04/22 09:53:47
>>40
モンテカルロ法を用いた将棋24でレーティング2000以上のコンピュータ将棋ソフトを
是非教えていただきたい。

42:デフォルトの名無しさん
07/04/22 09:55:07
やだ

43:デフォルトの名無しさん
07/04/24 08:23:34
ボナンザが、裏で「遠隔操作」を行っていたことが判明。
これじゃ、一般人が勝てる訳がない・・・

ｽﾚﾘﾝｸ(newsplus板)

44:デフォルトの名無しさん
07/04/24 08:29:47
そりゃボナンザ違いでんがな。

45:デフォルトの名無しさん
07/04/24 20:21:57
マサルさんのボナンザを思い出した

46:デフォルトの名無しさん
07/04/30 15:37:14
おまいら、そろそろ最強の将棋プログラムとやらに
とっかかってくださいよ。

47:デフォルトの名無しさん
07/04/30 15:40:27
SK"2

48:デフォルトの名無しさん
07/04/30 23:48:00
人が切れ負けになるまで「本当に成らなくてよろしいですか？」ダイアログを出し続ける

49:デフォルトの名無しさん
07/05/02 19:50:54
>>46
とりあえず明日逝って来る

50:デフォルトの名無しさん
07/05/03 15:43:44
第17回世界コンピュータ将棋選手権ライブ中継
URLﾘﾝｸ(live2.computer-shogi.org)

51:デフォルトの名無しさん
07/05/03 21:17:55
>>7

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

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

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

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

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

52:デフォルトの名無しさん
07/05/03 23:45:39
VIP擬人化将棋のWikiです。
URLﾘﾝｸ(wiki.livedoor.jp)
将棋の駒を女の子にして将棋が打てるプログラム、是非試してみてください。
URLﾘﾝｸ(shogi.vip2ch.com)

53:デフォルトの名無しさん
07/05/04 13:57:44
プログラム作りたい！　今からとりかかる。　まずは盤だ。　来年は遠いねー。

54:デフォルトの名無しさん
07/05/04 22:36:48
将棋の局面の良し悪しの判定ってどういうふうにやってるの？
コンピュータにまともな判定ができるとは思えないんだけど。

55:デフォルトの名無しさん
07/05/04 23:39:50
駒の損得とか駒の位置関係とか玉の堅さとか・・・

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

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

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

58:7
07/05/05 00:25:26
あ、こっちは英語じゃなかったか。
最近買った別の本と混同しちまったｗ。

59:デフォルトの名無しさん
07/05/09 11:19:00
激指チームが悪事の限りを尽くしているスレはこちらです。
ｽﾚﾘﾝｸ(bgame板)

60:デフォルトの名無しさん
07/05/12 06:36:37
結局は旅人の釣りであったか・・・

61:デフォルトの名無しさん
07/05/12 14:21:59
コンクリートの上で垂直式ブレンバスター。
さすがのジャイアンも・・・
旅人恐るべし。。

62:デフォルトの名無しさん
07/05/16 11:28:13
news : 革新的なAI囲碁プログラム『Crazy Stone』
URLﾘﾝｸ(wiredvision.jp)

63:デフォルトの名無しさん
07/05/16 23:01:19
これは凄いな

64:デフォルトの名無しさん
07/05/19 11:31:46
なんかえらく古い話だと思ったら，原文は去年の9/16じゃないか
翻訳遅すぎ＞Wired
CrazyStoneの最新版は19路でもMoGoより強いかなってとこまで来てる
丁度その秘密を書いた論文が公開されたところ
内容は主にパターン等の自動学習
URLﾘﾝｸ(remi.coulom.free.fr)

65:デフォルトの名無しさん
07/05/20 16:07:13
遅いって言うかWiredは最近までずっと休刊?してたわけだが

66:デフォルトの名無しさん
07/05/21 16:14:03
それは旬を外れた記事を載せる理由にはならんだろ

67:デフォルトの名無しさん
07/05/21 18:45:06
大学が休講になっちゃった。
暇だから将棋の続きやるか。

68:デフォルトの名無しさん
07/05/21 23:24:53
>67
早稲田ですか？

69:デフォルトの名無しさん
07/05/22 09:24:17
はしかで休講になったとこはいっぱいある

70:デフォルトの名無しさん
07/05/22 17:03:14
昨日の午後、突然休講になった大学はそんなに多く無いと思う。
まあ、どうでも良いけどさ。

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

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

73:デフォルトの名無しさん
07/06/08 00:33:24
ちょっと作ってみようと思ったんだけど、やっぱりC言語がいいのかなあ。
できればC#で作りたいんだけど実行速度遅いんかなあ。

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

75:デフォルトの名無しさん
07/06/08 07:47:20
Cに移植(笑)

76:デフォルトの名無しさん
07/06/08 23:44:21
>74
ふーん、そういうやり方でうまく行くんなら俺もまずJavaで書いておいて
C++に"移植"すると言うやり方でやってみようかな。

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

77:デフォルトの名無しさん
07/06/09 00:21:50
でもJAVAとかC#もJITコンパイラの進歩で思ったほど実行効率落ちないみたいだね。
URLﾘﾝｸ(homepage2.nifty.com)

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

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

78:デフォルトの名無しさん
07/06/09 00:33:30
そういうのはほんとはコンパイラの仕事で、賢いコンパイラは
自分で工夫してくれる（べき）ものなんじゃないかと

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

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

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

80:デフォルトの名無しさん
07/06/09 01:41:11
>>77
実行時最適化ができるVM上での動作の方が速くなることも多いよ。
だからLLVM
URLﾘﾝｸ(llvm.org)
なんかが開発されてる。将棋プログラムのような分岐の多いプログラムなら
Cで書くよりも最終的には速くなるかもしれない。

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

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

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

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

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

82:81
07/06/09 01:44:47
>>81は>>79へのレスね。

83:デフォルトの名無しさん
07/06/09 02:00:11
>>80
ってことはJAVAやC#で書いて、Cで作ったDLLを呼び出すのでFA？

84:デフォルトの名無しさん
07/06/09 02:10:19
>>82
>>79は明らかに嘘か無知が入ってるな。
286の時代ならともかく、今手に入るx86 CPUのビットシフトは基本的に１クロックのはず。
例えばAthlonのデータシート
URLﾘﾝｸ(www.amd.com)
とかね。

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

85:デフォルトの名無しさん
07/06/09 02:12:36
前C#で配列の添え字チェックが入らないようにMarshalクラスを使って領域確保してから
配列のように使う改造をしたことはあるけどCには及ばなかった。
>>83
自分はそうしてる。
GUIはC#で評価関数のDLLはCで作ってる。

86:80=84
07/06/09 02:15:29
>>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;
}

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

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

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

89:デフォルトの名無しさん
07/06/09 02:23:50
>>85
>GUIはC#で評価関数のDLLはCで作ってる。
それ超危険。
マネージドコードとアンマネージドコードの切り替えはすごいオーバーヘッドがある。

90:デフォルトの名無しさん
07/06/09 02:40:20
>>89
じゃあ切り替え回数をなるべく少なくするように設計するべきか？
こりゃ設計するだけで一苦労だな。
やはり生産性は落ちるが何も考えずVCあたりで作るのが無難ってことか

91:デフォルトの名無しさん
07/06/09 03:31:21
>>89
そりゃ探索はC#、葉の評価はCみたいにアホな設計の場合でそ。

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

93:デフォルトの名無しさん
07/06/10 12:05:05
>>88
これは失礼ながら全く見当違い。
２のべき乗にするかどうかという議論はあえて余分な領域を取るかどうかという話で、
計算回数が増えるわけではありません。

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

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

96:92,93
07/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
07/06/10 15:49:06
どうでもいいことですが
>>A+i*N*N+j*64+k
はA+i*N*64+j*64+kですね。
86の例では。

98:デフォルトの名無しさん
07/06/10 20:53:45
>>93
じゃあたとえばA[i][j][k]みたいな多次元配列なら、j，kは2のべき乗のほうがはやかったりするのですか？

99:デフォルトの名無しさん
07/06/10 21:05:28
>>98
>87

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

101:デフォルトの名無しさん
07/06/26 21:09:07
てかさ、そんな枝葉の事よりもっと重要な評価関数とか探索ルーチンとか考えてるの？＞ALL

102:デフォルトの名無しさん
07/06/27 00:39:54
探索ルーチンは多少悪くてもハードウェアの進歩でどうでもよくなる

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

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

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

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

103:デフォルトの名無しさん
07/06/27 00:41:43
バカｷﾀｺﾚ!!

104:デフォルトの名無しさん
07/06/27 01:55:09
>>102
全然終わってないでしょう。
実際ボナンザはすぐ切れ筋に陥ってしまうようなまだまだ弱いプログラムだし。
自己学習というのも大きな誤解。
人間が決めたパラメータを最適化しているだけ。

105:デフォルトの名無しさん
07/06/27 03:15:52
>102
コンピュータ将棋ソフトを作ってる、あるいは作ろうとしている人間は
例え内心ではそういう事を思っていたとしても決して口にできないな。
口に出したら、じゃトッププロに勝てるものを作ってみせろと
言われるに決まっているから。

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

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

106:デフォルトの名無しさん
07/06/28 08:40:45
逆に評価関数簡素化してパワーでプロ棋士を押し切るなんともｼｮﾎﾞｰﾝな結果になりそうな悪寒

107:デフォルトの名無しさん
07/06/28 10:36:05
>106
それは俺も心配。
ただ、シンプルだけどそこそこ正確な評価関数ってなんだろ？とは思うが。

108:デフォルトの名無しさん
07/06/28 23:02:32
>>107
敵玉が詰み = +1点
自玉が詰み = -1点
持将棋成立 = 0点
先手千日手 = 0点
後手千日手 = 0点

あとはパワーでｗ

109:デフォルトの名無しさん
07/06/29 19:19:40
>108
ごめん、俺には無理。

110:デフォルトの名無しさん
07/07/02 01:32:51
>72
URLﾘﾝｸ(www.fun.ac.jp)
# 久々に読んだけど書けるかな?

111:デフォルトの名無しさん
07/07/07 03:14:18
なあ、今からC＋＋やJavaで指し将棋ソフト作っても
あんまり変わり映えしなさそうだから、Lispで
書いてみようかと思うんだがオマイラどう思う？

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

112:デフォルトの名無しさん
07/07/07 17:49:43
つ URLﾘﾝｸ(hotwired.goo.ne.jp)

113:112
07/07/07 19:40:36
間違えた＿|￣|○
URLﾘﾝｸ(lyrical.bugyo.tk)

114:デフォルトの名無しさん
07/07/08 01:26:42
>>111
Lispではないけど関数型言語を使っているらしいチームが
5月の選手権には何度か参加登録してる
たしかOCamlだったか…
楽しみにしてると参加取り消しだったりした
実際に出場したことがあるかは不明

115:デフォルトの名無しさん
07/07/08 22:28:36
>>111
別に利用するプログラミング言語で変わり映えをつけようとしなくてもいいと思うが。
弱ければ単なる色物で終わってしまう。

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

117:デフォルトの名無しさん
07/07/08 23:17:20
弱けりゃ何で作っても一緒

118:デフォルトの名無しさん
07/07/10 02:47:55
ICOTの囲碁はESPっていう逐次論理型言語を使ってたみたいねー
URLﾘﾝｸ(www.icot.or.jp)
EPSってwikipediaによるとPrologにオブジェクト指向を取り入れたものらしいけど

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

119:デフォルトの名無しさん
07/07/10 02:59:48
>>111
>Lispで書いてみようかと思うんだがオマイラどう思う？
　LISPでどういうやり方でやるかわからんけど、
　探索より知識の積み重ねで指そうと考えてるなら、

　ここのHIT将棋が取り組んでいる
URLﾘﾝｸ(homepage1.nifty.com)
　ここの研究室は、プロ棋士がどういう風に手を絞っているからを調べてて、

　はじめから２，３手に絞って、その先を確認して指すタイプとか、
　10手とかたくさんの手を検討して指すタイプとか、
　けっこういろいろなタイプに分かれるらしい。
URLﾘﾝｸ(www.webspace-jp.com)

120:デフォルトの名無しさん
07/07/10 11:07:03
Freisinn :: 一挙公開
URLﾘﾝｸ(yashiromann.sakura.ne.jp)

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

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

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

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

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

121:デフォルトの名無しさん
07/07/10 15:09:08
>120
誤爆かあるいはただの宣伝かい？

122:デフォルトの名無しさん
07/07/15 23:15:41
プロ棋士に勝つ方法

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

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

123:デフォルトの名無しさん
07/07/16 00:11:53
「詰める」を「詰みを読み切る」と思って意味がわからんかった

124:デフォルトの名無しさん
07/07/16 13:11:18
>122
SX-8iってベクトル機だよ？
今主流のコンピュータ将棋が高速に動くとは思えないが？

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

125:デフォルトの名無しさん
07/07/16 13:12:22
>122
それから、「乱戦模様」の「定跡」を作ろうって言ってる？
がんばってね。

126:デフォルトの名無しさん
07/07/16 17:45:34
>122はあちこちにマルチポストしてる愉快犯だから相手にしないように。

127:デフォルトの名無しさん
07/07/16 20:22:02
URLﾘﾝｸ(c-au.2ch.net)
URLﾘﾝｸ(c-au.2ch.net)

128:デフォルトの名無しさん
07/07/17 12:08:43
必至だなｗ

129:デフォルトの名無しさん
07/07/17 17:46:58
既に詰んでますｗ

130:デフォルトの名無しさん
07/07/17 20:00:07
>122はPonanzaというソフトの作者の保本さんです。

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

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

133:デフォルトの名無しさん
07/07/22 01:32:10
>132
将棋はチェスやチェッカーと違って終盤でなかなか手の広さが収束しないんだよ。
もちろん取った駒を盤上の好きなところに打てるからだが。

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

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

135:デフォルトの名無しさん
07/07/24 15:21:51
>>134
なにに反応したのか、当たり前のこと並べて楽しいのか？
んな常識的なこといってもつまらんだけ。
コンピュータ将棋が最強なんて考えている乙君が沸いてきそうだ。

136:デフォルトの名無しさん
07/07/24 18:11:20
>>134
では三色問題も解かれてないと主張するのですね？

137:デフォルトの名無しさん
07/07/24 21:17:16
>>135-136
あんまりいじめてやるな。134が哀れだろ。

138:デフォルトの名無しさん
07/07/24 21:23:06
>>132
中学生さんですか？

139:デフォルトの名無しさん
07/07/24 22:05:40
計算機の速度を考慮する場合と、計算機の速度を度外視する場合は別に考えてね

140:デフォルトの名無しさん
07/07/24 22:40:01
>>139
誰に対しての発言？
意味がよく分からん。

141:デフォルトの名無しさん
07/07/25 10:42:22
132に一言いいたかったんじゃね

142:デフォルトの名無しさん
07/07/26 01:48:34
>>132
>自然淘汰を取り入れた自己進化するアルゴリズム同士をスーパーコンピューターで戦わせまくれば
　まさにGAで対戦させて強い奴を進化させるって話じゃまいか。
　中学生ですか？　は言い過ぎだよ。

　次みたいに名大の人が昔オセロでやってみてる
URLﾘﾝｸ(www.phys.cs.is.nagoya-u.ac.jp)

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

143:デフォルトの名無しさん
07/07/26 11:34:51
将棋でやるとなると相当なマシンパワーが必要だな
アルゴリズムを進化させるアルゴリズムも作るのも大変そうだ

144:デフォルトの名無しさん
07/07/26 15:55:38
>>143
最初は歩だけしか動かせないアルゴリズムや角だけを狂ったように使うアルゴリズムが出てきて面白そうｗ
でも普通の対局できるレベルになるまで何千万世代もかかるだろうね。

145:デフォルトの名無しさん
07/07/26 18:56:37
いや、進化させるっていうかたまに突然変異を混ぜればいいのか
それが環境に対してダメな進化（退化）だったら淘汰されるだけか

146:デフォルトの名無しさん
07/07/26 21:01:08
>>142
スパコン同士を戦わせたら何百億円もかかるから採算絶対にあわない。
実現困難な"夢"と非現実的な"夢物語"の間には大きな違いがあるよ。
132はリアルに中学生かもorz

147:デフォルトの名無しさん
07/07/26 21:17:19
>>142
その結果って公知じゃないのか？
その研究はせいぜい学部生の宿題レポのレベルだし

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

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

149:デフォルトの名無しさん
07/07/26 22:56:51
>146
これは非現実的の範疇には入らないと思うが。
「採算」の事を考えてる時点で現実的じゃん。
非現実的ってのはもっと、今後どんだけ科学が発展しても無理！ってものの事を言わないか？

150:デフォルトの名無しさん
07/07/26 23:07:11
んなこたーない
>>146のでも非現実的といえる

151:デフォルトの名無しさん
07/07/26 23:22:32
最強のとか言ってる時点で現実的じゃないような気もするけど。
理論的な最強を目指しているのか？現時点での暫定的な最強を作りたいのか？
前提が定まっていないような

152:デフォルトの名無しさん
07/07/26 23:25:03
>>151
自分は当面目指すのは後者だと思ってる

153:デフォルトの名無しさん
07/07/27 00:00:00
人間破ったらそれでいいんだ
まずはコンピュータの頂点を目指す

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

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

155:デフォルトの名無しさん
07/07/27 03:59:16
>154
「ガンガレ」って誰に言ってるのか知らんが、将棋の全探索は無理だろう？
いくらなんでも現状では。

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

156:デフォルトの名無しさん
07/07/27 04:14:32
全探索というゴールが存在するという事実は重要じゃないか？
あとはそれにどこまで近付けるか、あるいは到達するか

157:デフォルトの名無しさん
07/07/27 12:45:10
>>155
量子コンピュータができれば、将棋の必勝解を一瞬で計算できます。
時間など不要です。
なぜなら量子コンピュータは手順という概念を組み立てる方法では計算しないからです。

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

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

158:デフォルトの名無しさん
07/07/27 12:51:25
応援なんかよりアルゴリズム考えろよ

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

160:デフォルトの名無しさん
07/07/27 13:36:26
>>159
チェスは無限に続くかもしれんが、将棋は同一局面3回出たら引き分け

161:デフォルトの名無しさん
07/07/27 13:36:47
順番からいって次はオセロだろう
いやまぁ自分は量子コンピュータのことよくわかってないんだけどね

162:デフォルトの名無しさん
07/07/27 13:39:56
単純にいって、駒は8種類で成りを加えて、14通り
合計40枚だが、それを考慮しないことにして
高々配置可能な種類は15の81乗程度

163:デフォルトの名無しさん
07/07/27 13:41:40
敵味方を忘れた　将棋の可能な配置パターンは29の81乗以下
それすべてに、勝ち負けを設定すれば将棋は完全に溶けた

164:デフォルトの名無しさん
07/07/27 13:46:38
配置可能なパターンはそれだけでも
次の手番がどっちかとか何回目に出た局面かで勝ち負け引き分け変わるでしょ。

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

166:デフォルトの名無しさん
07/07/27 14:59:13
んぁ～、あつはなついなぁ～

167:デフォルトの名無しさん
07/07/27 15:13:50
手番は2通りしか無いんだし、2通り作ればいいだけだな。

168:デフォルトの名無しさん
07/07/27 15:20:30
>>165
そういえばそうだった

169:デフォルトの名無しさん
07/07/27 15:26:39
>>163
それだと一秒間に一兆パターン調べても終わらないいんだがw
何で今更そんな議論を

170:デフォルトの名無しさん
07/07/27 15:27:13
>>166
そういえばそうだった

171:デフォルトの名無しさん
07/07/27 17:11:57
>>160
チェスにも同じルールがあるよ、次に完全解析されるゲームはダイヤモンドゲームじゃ無いかと予想
最後まで解けないのは囲碁。

172:デフォルトの名無しさん
07/07/27 20:53:10
同じ局面が３回というのはルールだろうけど、それを記録できなければ
無限に終わらない罠。記録できてこそ３回一致を判定できる罠。

173:デフォルトの名無しさん
07/07/27 22:07:54
>>171
囲碁はもう解けてるだろ
先手必勝

174:デフォルトの名無しさん
07/07/27 22:13:05
>>173
あれ、囲碁って先手の6目（7目？）勝ちって解明されたんだっけか？
教えてクンですまん。

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

176:デフォルトの名無しさん
07/07/27 22:50:42
オセロって完璧に全手解明されてなかったっけ？

177:デフォルトの名無しさん
07/07/27 22:54:29
>>176
オセロ（通常は８ｘ８の事）もまだ解明されてないよ
６ｘ６盤は解かれてるけど

178:デフォルトの名無しさん
07/07/27 22:58:44
>>177
そうでしたか

179:デフォルトの名無しさん
07/07/27 23:11:50
8x8は解明したと力説する奴は結構いるんだけどな。
ぽえむ君だから仕方が無いんだけど、

180:デフォルトの名無しさん
07/07/28 00:18:54
>165の意見は強烈だなぁｗ。

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

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

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

181:デフォルトの名無しさん
07/07/28 00:25:56
>>180
おまえ変だ
完全に勝敗が決まっていたら、勝ちか負けか千日手しかない

182:デフォルトの名無しさん
07/07/28 00:33:30
>>180
勘違いしてるバカ

183:デフォルトの名無しさん
07/07/28 00:39:40
>181
意味不明！

184:デフォルトの名無しさん
07/07/28 00:45:26
全ての局面と試合結果の組データを構築する場合
局面・・・駒の配置と手番の情報だけが必要
結果・・・その局面から全探索した結果（勝ち・負け・千日手）だけが必要

185:デフォルトの名無しさん
07/07/28 01:03:20
>184
同じ形の局面でもそれが何回目の出現かを区別しないで
どうやって千日手だと判定するんだ？？？

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

186:デフォルトの名無しさん
07/07/28 01:13:35
>>185
勝ちでも負けでもない局面はあいこだろが

187:デフォルトの名無しさん
07/07/28 01:15:00
>>185
だからそれは別の問題なんだって。
そっちの話題に関してはもちろん思ってないよ。

188:デフォルトの名無しさん
07/07/28 01:35:13
それよりお前ら開発してるのか？

189:デフォルトの名無しさん
07/07/28 01:39:39
>>180は、こっちで完全無視されたやつじゃないのか?
ｽﾚﾘﾝｸ(bgame板)

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

190:デフォルトの名無しさん
07/07/28 01:41:50
>>188
スレは見てるけど最近将棋の開発はしてないなー
ちょっと前は高速化のためにSSE2の勉強やってたけどどんなところに使えるかな

191:デフォルトの名無しさん
07/07/28 01:45:49
だから特定の局面の勝ち、負け、引き分けを
正確に判定するためにはその局面に至る手順で
区別して扱わない限りそもそも不可能なんだよ。

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

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

192:デフォルトの名無しさん
07/07/28 01:51:14
>>191
おめー頭悪いな

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

194:デフォルトの名無しさん
07/07/28 01:57:41
>>191
＞ところが探索の開始局面にその区別がなかったとすると
＞情報は蓄えられずにどんどん失われて行く。
この部分の解説希望
失われて行く情報とは？

195:デフォルトの名無しさん
07/07/28 02:02:04
>>194
191は頭悪いよ
詰め将棋を解く(勝敗を決定)する事と、
すでに決定されている事の区別が出来ていない

196:デフォルトの名無しさん
07/07/28 02:04:10
千日手が決定している局面は、そこに至る手順に関係なく千日手なんだよ

197:デフォルトの名無しさん
07/07/28 02:07:06
>>165で言っている事と>>196は同じ事だ

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

198:デフォルトの名無しさん
07/07/28 02:08:26
つまり

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

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

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

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

200:デフォルトの名無しさん
07/07/28 02:23:21
>>199
将棋の完全解析は不可能、を主張しているということでOK?

201:デフォルトの名無しさん
07/07/28 02:23:33
>>199
手順は関係ない
勝ちと負けと引き分けしか無いのだから、局面が与えられればそれは決定するんだよ
探索によって結果が変わるなら、その探索が間違っているだけだ

202:デフォルトの名無しさん
07/07/28 02:30:16
勝敗が決定する局面では、次の指し手は一つに絞られる

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

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

203:デフォルトの名無しさん
07/07/28 02:39:59
>200 >201
違う、違う。
その局面に至る手順により区別して（別の物として）
扱わない限り、その局面が勝ち負けか引き分けかを
決定できないと言ってるんだよ。
つまり局面をその現れる順番で展開したゲーム木を作れば良い。

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

204:デフォルトの名無しさん
07/07/28 02:46:24
>>203は釣りですから無視しましょう

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

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

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

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

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

207:デフォルトの名無しさん
07/07/28 02:59:37
>>205
よーく言いたいこと解った！！サンクス！！
後退解析だけでは駄目なんだね　経路が必要なんだね
で、結局、局面だけでは判断できない･･･ってことか
ちょい目から鱗が落ちたよ漏れの勉強不足を痛感した

208:デフォルトの名無しさん
07/07/28 03:05:35
例えば、勝ちと判別されている局面があったとして
勝つ手順がわかっていたとしても、
既にその局面が3回現れていたとしたらそこへは指せない
と言うことなんだろ???しかし、この場合、1回目で勝っている

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

210:デフォルトの名無しさん
07/07/28 03:10:21
>>206 氏の意見は、O(N!)とO(N)がゴッチャになっていて、
「局面へ至る手順により区別」と「局面による区別」がすり替わっているように思う
その点において、>>203 氏の意見の方が正しそう

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

211:デフォルトの名無しさん
07/07/28 03:10:50
>206
問題があります。
なぜなら勝ち、負け、引き分けが決定するのは飽くまでそこに至る手順により
区別された局面であり、その区別を外して形だけで同一視した局面は
一般的には決定不能だからです。

212:デフォルトの名無しさん
07/07/28 03:14:01
GHIとか言ってるやつは、よく聞け!!!

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

213:デフォルトの名無しさん
07/07/28 03:19:23
>>210
確認。
完全解析の定義は「すべての局面の勝ち負けか引き分けかを決定すること」。
認識は、あってる?

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

214:デフォルトの名無しさん
07/07/28 03:21:18
>>211
完全解析の定義は?
で、完全解析はできるのできないの？

215:212
07/07/28 03:22:26
同じ局面が現れるならそれは千日手である、という点が抜けていた

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

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

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

Wikipedia

218:デフォルトの名無しさん
07/07/28 03:28:37
>213
分からないかな？
局面の形だけで区別したのでは答えが複数あるんだよ。
どういう手順によりその局面に至ったかにより異なる答えが。

219:デフォルトの名無しさん
07/07/28 03:30:01
>>213 氏の言う「完全解析」がもし可能であるとすると、O(N!)→O(N)への射影が可能
しかし、後退解析を使って「完全解析」するのは、GHI問題があるために不可能

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

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

220:デフォルトの名無しさん
07/07/28 03:32:57
>>218
そんなことは聞いていない。
(1)完全解析の定義はあってるかどうか。
(2)>>206の何行目が間違い。
を

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

221:デフォルトの名無しさん
07/07/28 03:33:59
>>208の言う通りだろう

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

222:デフォルトの名無しさん
07/07/28 03:36:21
>>218の言いたいのはこういうことかな

　現在の局面がある

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

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

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

次ページ