07/04/06 15:33:54
過去スレ
おまいら最強の将棋プログラムしてみろよ part4
ｽﾚﾘﾝｸ(tech板)
おまいら最強の将棋プログラムしてみろよ part3
ｽﾚﾘﾝｸ(tech板)l50
おまいら最強の将棋プログラムしてみろよ part2
ｽﾚﾘﾝｸ(tech板)
おまえら最強の将棋プログラムしてみろよ！！
URLﾘﾝｸ(pc2.2ch.net)
3:デフォルトの名無しさん
07/04/06 15:34:36
関連スレ
▲コンピュータ将棋スレッド35▽
コンピューター将棋番外編5・アルゴリズム
ｽﾚﾘﾝｸ(bgame板)
▲コンピュータ将棋スレッド35▽
ｽﾚﾘﾝｸ(bgame板)
4:デフォルトの名無しさん
07/04/06 15:35:08
TCP/IP通信プロトコル（コンピュータ将棋協会）
URLﾘﾝｸ(www.computer-shogi.org)
アップローダ (Part3 929氏提供)
URLﾘﾝｸ(gm.a-ark.net)
CSAサーバ (Part3 773氏作、Part3 783氏提供)
アドレス wdoor.c.u-tokyo.ac.jp 4081
棋譜など URLﾘﾝｸ(wdoor.c.u-tokyo.ac.jp)
5:デフォルトの名無しさん
07/04/06 15:35:39
MTD(F)
URLﾘﾝｸ(www.cs.vu.nl)
ゲーム木の探索問題
URLﾘﾝｸ(tt.sakura.ne.jp)
反復深化
URLﾘﾝｸ(tt.sakura.ne.jp)
最良優先探索
URLﾘﾝｸ(kyu.pobox.ne.jp)
遷移確率、激指
URLﾘﾝｸ(www.logos.t.u-tokyo.ac.jp)
GNU shogi
URLﾘﾝｸ(www.cs.caltech.edu)
福将棋
URLﾘﾝｸ(touch-mi.hp.infoseek.co.jp)
6:お前ら奇書、死んだほうがええ。
07/04/06 16:27:37
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あー面倒くさい。あー面倒くさい。
あ
7:デフォルトの名無しさん
07/04/06 23:39:31
ゴメンネ！ オレ必至すぎてゴメンネ！
ボナの最適化アルゴリズムが実は「強化学習」なんじゃないかなー？
と思い始める前に
森北出版の『強化学習』R. Sutton・A. Barto著
(原著：Reinforcement Learning: An Introduction)
をネット書店に注文していて、ちょうど今日届いたもんだから
ちょっと舞い上がっちゃっててね。 そうであってくれると嬉しいんだ。
（でも、もしそうなら既に実現されていて、ちょっとくやしいｗ）
8:デフォルトの名無しさん
07/04/07 01:07:23
強化学習って環境との相互作用から学習するというやつで
バックギャモンのそれは自分との対戦から学習していくという方式
ボナンザのは探索こそしているけれど、環境との相互作用とはいいにくい
だから、強化学習とは違うと思う。
どちらかというと統計的学習じゃないのかな
9:デフォルトの名無しさん
07/04/08 02:55:56
wikipediaのコンピュータ将棋の項を見ていて、
人工知能という単語が目に入った瞬間コーヒーふいた
10:デフォルトの名無しさん
07/04/08 06:14:23
なんで？>>9
11:デフォルトの名無しさん
07/04/08 12:18:15
まあ、昔から人工知能の課題とされて来たものは研究がある程度進展した
段階で必ず、もはや人工知能の課題とはみなされなくなって来た。
音声認識も自動翻訳も人間との（簡単な）会話もチェスも将棋も。
どれもまだ全然完全じゃないんだけどね。
（その昔、チェスを機械に指させる事はリッパな人工知能の課題だった）
つまり「人工知能」って言うのは見果てぬ夢に対して付けられる
看板であって具体的な課題、技術、手法の事じゃないんだよ。
12:デフォルトの名無しさん
07/04/08 12:31:28
なるほど
13:デフォルトの名無しさん
07/04/08 12:46:42
>>11の定義って一般的なの？
別にコンピュータチェスとか将棋とかが人工知能でも違和感ないのだけど
人工知能系の学会ではチェスや囲碁は研究されてないのかな
14:デフォルトの名無しさん
07/04/08 16:09:08
>どちらかというと統計的学習じゃないのかな
正解
15:デフォルトの名無しさん
07/04/10 09:30:12
パターン認識は流石に外れてるかな
ゲームはまだ人工知能に含まれてる
プランニングは十分人工知能だし（ゲームもプランニングの一種）
16:デフォルトの名無しさん
07/04/10 09:47:19
プランニングって何？
計画を立てること？
17:デフォルトの名無しさん
07/04/10 15:51:02
中学生でも知ってる単語だろうが
18:デフォルトの名無しさん
07/04/10 16:44:14
ごめん俺消防だから教えて
19:デフォルトの名無しさん
07/04/10 19:23:22
行動計画だったかな。
目標状態を得るための行動の組み合わせと順序を探索他で決定するやつ。
20:デフォルトの名無しさん
07/04/10 23:36:07
要するに巡回セールスマン問題とかナップザック問題とか言う奴だろ。
実用的にはLSIの配線とかにも利用されてるようだが。
研究者から見れば十分にAIの研究かも知らんが、素人目には
これがAI研究ですって言われてもなあ……ジミだ。
21:デフォルトの名無しさん
07/04/11 11:31:14
アルゴリズムが発見されると、人工知能の課題でなくなっちゃうんだよな。
機械的に手順を踏めば解決しちゃうから。
>>20
それは線形計画法で実用上解決された。
AIとみる人はいないでしょう。
22:デフォルトの名無しさん
07/04/11 14:56:19
NPCみたいに人間の代打扱いするのが人工知能
道具扱いすれば人工知能じゃなくなる、と考えちゃ駄目？
23:デフォルトの名無しさん
07/04/11 16:24:42
俺は人間も本当の知能ではなくて自動機械だと考える派だから
人工知能という物ができたならそれは人間を超えてないとダメ
24:デフォルトの名無しさん
07/04/12 01:30:55
>それは線形計画法で実用上解決された。
線形なものしか扱えませんが。
人工知能の定義として
人間の知能を構成するために必用な技術の総体
というのでどうでしょう？
問題が与えられた時に、
「人間はどうやって問題を解いているのだろう？」
と、人間と対比して考えるのが、
人工知能分野の特徴だと思いますが。
>人工知能系の学会ではチェスや囲碁は研究されてないのかな
難しいので直接扱う人はいません。
小手先の改良をしただけでは研究にはなりませんので。
25:デフォルトの名無しさん
07/04/12 10:06:30
どうでもいいけどお前らほんとに将棋プログラミングしてみてるのか？
ゲ作厨が流入しているだけにしか見えんのだが。
26:デフォルトの名無しさん
07/04/12 21:46:16
>>25
漏れはROMに近いが一応作ってるよ
先週のオープン戦には参加してきた
27:デフォルトの名無しさん
07/04/13 11:22:24
>人間と対比して考えるのが、
>人工知能分野の特徴だと思いますが。
素朴な考えだけど実際は違う
人工知能は「知的」な作業を機械化する技術を開発する分野
やり方が人間と似てる必要も無いし人間と対比させる必要もない
ニューロモルフィズムと言うのがあなたの考え方に近いけど少数派
人間がどうやってるかを考えるのは認知科学（とか神経科学）
28:デフォルトの名無しさん
07/04/13 11:26:32
>要するに巡回セールスマン問題とかナップザック問題とか言う奴だろ。
ぉぃぉぃ
もっと複雑なアプリが山ほどある
例えば介護/警備/レスキューロボットの行動計画とか
大規模な組み合わせ最適化問題は今でも十分AIの研究テーマ
連が木スマソ
29:デフォルトの名無しさん
07/04/13 12:34:04
３球体問題は解けるの？
30:デフォルトの名無しさん
07/04/13 15:41:20
>人工知能は「知的」な作業を機械化する技術を開発する分野
知的の定義は？
31:デフォルトの名無しさん
07/04/13 17:14:16
知的とは人間に出来てコンピュータには出来ない知的行為のこと。
32:デフォルトの名無しさん
07/04/13 17:30:44
それじゃ人工知能の研究の意味ないじゃんw
33:デフォルトの名無しさん
07/04/13 18:22:48
人間の脳も機会と同じく生体分子の形態で思考していると思うよ
34:デフォルトの名無しさん
07/04/14 01:10:31
>>31
循環論法乙。
35:デフォルトの名無しさん
07/04/14 03:20:50
>>29
物理の三体問題のこと？
人工知能とは全然違うと思うけど、いまだに、というか永久に厳密解を
得ることは不可能ですよ。
36:デフォルトの名無しさん
07/04/15 15:04:09
>知的の定義は？
お好きなようにどうぞ
だから人工知能の定義も人によって異なる
37:デフォルトの名無しさん
07/04/20 13:54:43
>人工知能は「知的」な作業を機械化する技術を開発する分野
じゃあ、これは妄言だね
38:デフォルトの名無しさん
07/04/22 06:59:05
お前が将棋プログラミングに全く興味がないのはわかったからあと10年ROMっとけ。
39:デフォルトの名無しさん
07/04/22 09:37:01
将棋だとアルファベータとモンテカルロってどっちが強いのだろう
今のところアルファベータが主流な感じだが
40:デフォルトの名無しさん
07/04/22 09:39:20
大差なし、同じようなもんだ
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から現在の局面になるのだから
結果は千日手なのだよな
223:デフォルトの名無しさん
07/07/28 03:36:37
>212
千日手になるためには同じ局面が"4回"現れる必要があるぞ。
2回目が現れたらその途端に千日手になるわけじゃない。
224:デフォルトの名無しさん
07/07/28 03:37:32
千日手のパラドックス
225:212
07/07/28 03:37:52
>>223
頭を使え!!!
226:デフォルトの名無しさん
07/07/28 03:43:17
>>223
イメージ的に、対局で、詰めろが回避できないと諦めた段階で投了するか、
詰まされるまで指し続けるかの違いかな。
227:デフォルトの名無しさん
07/07/28 03:44:41
>>209, 212
スマン、「で、結局、局面だけでは判断できない･･･ってことか」は、
後退解析の途中で現れる局面についての話題ってことに読み直してくれ。
しかし完全解析って、後退解析以外にそもそも定義できなそうだから、
正しくは後退解析の実行手順の問題と言い換えるべきか？ これで正しい？
228:デフォルトの名無しさん
07/07/28 03:58:02
>222
うん、つまりはそういう事。
すでに以前、局面Aを3回通過してれぱ頑張っても千日手にしかならないが、
そうでなければ（2回あるいは1回通過）勝ち筋があるというわけ。
そして局面Aから現在の局面に来たとしても、必ずしもそこに戻るとは限らない。
229:デフォルトの名無しさん
07/07/28 03:59:50
>>223
神同士が対局してるものとして、
同じ局面が現れる（2回目）って事は、仮に千日手ルールが無ければ3、4、5・・・回目も必ず現れるよね？
んで千日手ルールがあった場合、2回目が現れた時点でその局面は千日手（4回目）なのと同じでしょ？
230:デフォルトの名無しさん
07/07/28 04:21:24
なんだかプログラマというより数学板みたいな感じですね
231:デフォルトの名無しさん
07/07/28 04:28:20
>>230
そう。
>>180は、最初こっちでやってて、逃げ出したみたい。
「将棋って数学に似てるの？」
ｽﾚﾘﾝｸ(bgame板)
こっちでも完全無視。
ｽﾚﾘﾝｸ(bgame板)
で、ここで叩かれていると。
232:デフォルトの名無しさん
07/07/28 04:35:39
>>228
ちょっと待って、整理させてくれ
その「戻らない」場合っていうのを
盤面はもちろんなくていいから例示してくれないか
局面Aから現在の局面に来た過程では、
相手方の協力があったから来たわけだよな
つまりこの千日手含みの手順に入ったからには
相手としても「回避すれば負ける」という事情が
あったわけで、するとやはり千日手が結果の気が
するのだけど
233:デフォルトの名無しさん
07/07/28 04:38:15
うーん、どこで話が噛み合わなくなってるか何となく分かってきた。
皆さんは将棋の神様同士が双方最善を尽くす場合の棋譜を考えてるよね。
だから千日手になるのを避けるために特定の局面を通らない事もあると仮定している。
そう考えるとその時点での局面の形から指し手が一意に定まると（少なくとも結果は同じ）。
私はルール上許される全ての局面に勝ち、負け、引き分けのラベルを貼る事を考えている。
そうすると後退解析するしか方法がなくて、すると>205が書いているように
GHI問題を考慮する必要が出てくる。
234:デフォルトの名無しさん
07/07/28 04:38:59
で、漏れはGHI問題についてググって以下のPDFに辿り着いた
ここの2ページ目だけ読めば、GHI問題については理解した（つもり）
URLﾘﾝｸ(www.fun.ac.jp)
これって詰め将棋のように、手順に基づいて探索ツリー作製していったとき、
サイクル手順に出てくる局面を、「無闇に」不詰として、ハッシュ表に登録することから生じる問題みたい
この「無闇に」ってところが重要で、ホントは2ページ目の局面Aは詰む局面
したがって「完全解析」の是非や、それに何回目の局面の情報が必要か、といった問題じゃなく、
あくまでも探索アルゴリズムの問題だね。最初の議論と、GHI問題の関係は、微妙だよ？
235:デフォルトの名無しさん
07/07/28 04:40:34
>>231
なるほど、横からだが把握した
この板IDないしな
236:デフォルトの名無しさん
07/07/28 04:44:46
>>233 釣りはやめろ
237:デフォルトの名無しさん
07/07/28 04:48:01
>>233
勝ち、負け、引き分けのラベルを貼る＝神同士の対局
238:デフォルトの名無しさん
07/07/28 04:48:10
>>234
ひとまずその2ページ目は見た
言いたいことはわからないでもないが
それは探索の実装の問題ではないかね
ハッシュが誤作動するとかいう問題と
結論がどうであるかということとは関係ない
もっといいアルゴリズムに替えたらいいだけ
この例でいえばEは「千日手」が結論なわけで
何も不明解さはないだろう
連続王手の千日手はまた別にして。
239:デフォルトの名無しさん
07/07/28 04:49:47
>>238は間違えた。「先手勝ち」な。
240:デフォルトの名無しさん
07/07/28 04:52:30
悪い、いろいろ間違えた。
>>238で俺が言いたかったことは>>234が言ってたな。
241:デフォルトの名無しさん
07/07/28 04:55:31
>233
GHI問題は、必ずしも「後退解析」（←これって勝ち筋から手を逆算していくことですよね？）の問題じゃないみたい
手順を追ってツリーを構築していく際に、ある経路では、千日手のように”みえる”局面が、
別の局面では勝ち筋に必要な局面ということ もちろん探索の途中で、うっかり千日手と
登録してしまったところに問題があるのであって、本当は、当然詰む局面
そもそも局面をハッシュしなければ、こういった問題は生じない
ハッシュするにしても、なんらかの形で辿った経路を情報として残せば、問題ない
また、図1で最初にA→Cと探索すれば、最初からこんな問題は生じない
とりあえずGUI問題について語るには、上のPDFの2ページ目を読もうよ
さっきから漏れも色々考えているのだが この論文の2ページ目以上に、簡単にGHI問題を説明するのは無理ぽ
242:デフォルトの名無しさん
07/07/28 04:56:16
>237
初手からの神同士の対局と任意、それも手順を含めた
任意の局面からのそれをごっちゃにしてない？
243:デフォルトの名無しさん
07/07/28 05:00:06
>>242
解析中と解析後はちゃんと区別しろよな
解析後に同一局面が出てくるなら引き分け、そうでなければ同一局面は出てこない
244:デフォルトの名無しさん
07/07/28 05:03:19
>>242
してないよ
245:デフォルトの名無しさん
07/07/28 05:04:58
神様同士の対局というのは、完全なる「次の一手」マシンのことだろ
完全なる「次の一手」マシンというのは、どんな局面を与えられても
勝ち筋があればそれを指し、なければ千日手に持ちこめる順を指し、
それもなければ何か指すというようなものだと思う
このようなマシンを作成することと、すべての局面の勝ち負けがわかる
完全な一覧表を作ることは等価だよ
マシン作成→与えられた局面からマシンに一人将棋をさせる→その勝ち負け
一覧表作成→有効手の中から、移行後の局面が「勝ち」であるものを
（なければ「千日手」を）さがす→それが次の一手
246:デフォルトの名無しさん
07/07/28 05:11:23
現時点での漏れの結論
1) 完全な後退解析が出来れば、
局面だけで勝ち・負け・千日手が解る（→完全解析）
2) 現実のアルゴリズム（これは後退解析でない）で
ツリー構造を作るには、ハッシュ表を使うことが多い
3) むやみにループする局面を千日手としてハッシュ表に登録していくと、
本来の勝ち筋を千日手と間違える問題が生じる(GHI問題)
4) 上記問題を回避するには、ハッシュ表に、千日手と判断するに
至った経路を登録して、局面だけでなく経路を区別する必要がある
5) 4)の事情があるために、「局面だけでは勝ち負けは決まらない」という
誤解が生じている
247:デフォルトの名無しさん
07/07/28 05:17:50
うん、それだ
今>>246がいいこと言った
248:デフォルトの名無しさん
07/07/28 05:18:28
それじゃあ任意の局面が与えられてそこから次の一手を決定する時、
そこまでどんな局面(経路)を辿って来たかについてどんな仮定を置いて
決めるんだい？
どんな経路を辿って来たとしても同じだと言うんならその根拠は？
249:デフォルトの名無しさん
07/07/28 05:20:14
「後退解析」をよくわかってないんだけど何かいい資料無い？
250:デフォルトの名無しさん
07/07/28 05:21:26
ひとり何役やってるの？
まあ、役者不足、ってやつだよね。
251:デフォルトの名無しさん
07/07/28 05:22:23
最低３～４人は居そうだけど
252:デフォルトの名無しさん
07/07/28 05:22:22
>>248
次の一手問題なら経緯は調べないだろが
勝ち負けの判定ならその局面へくる前に勝敗か引き分けが決まっている
253:デフォルトの名無しさん
07/07/28 05:22:54
>>248
いや別に
その「完全なる次の一手全集」を見ながら
バカみたいに指していくだけでいい
もしその局面からは千日手が最善なのであれば
全集には千日手になる手が書いてある
それを指せば、もし一回目や二回目なら
また同じ局面に戻ってくるわけだし
三回目なら、千日手になる
254:デフォルトの名無しさん
07/07/28 05:25:26
>>251
俺、俺より賢い奴、俺と同じくらいの奴、変なことを言う奴
の少なくとも４人はいると俺は思ってる
あと、見てる奴や１レスくらいしかしてない奴が多数
255:デフォルトの名無しさん
07/07/28 05:26:32
>>248
不完全な指し手が指したところから、勝敗を判定するなら
千日手は考慮しなければならない
データベースは使えない
256:デフォルトの名無しさん
07/07/28 05:26:45
>>248
すでに>>206で、「区別の不要」と証明されているんじゃないの？
否定できるなら、してみれば？
まず、>>220の形式で答えるのかな。
257:デフォルトの名無しさん
07/07/28 05:32:06
>>256
横からだけど、ちょっと待って
棋譜は有限だから、「指し手履歴込みの局面」も有限
それらをすべて列挙して勝ち負けを調べればよい
で、「同じ局面でも、指し手履歴の内容によって結論が異なる」
という現象はあるのかないのか
そこが本当の焦点なんじゃないのかと思う
258:デフォルトの名無しさん
07/07/28 05:36:42
>>254
>>185-248辺りでどのレスが誰？
自分のレスがどんな奴だと思われてるかちょっと気になる
259:デフォルトの名無しさん
07/07/28 05:38:36
>>257
「同じ局面でも、指し手履歴の内容によって結論が異なる」 と「区別の必要」の違いは?
とにかく、他にどんな問題があっても、単純に>>206を否定できなければ
「区別の不要」という結論は覆らないでしょう。
260:248
07/07/28 05:45:24
>256
区別が不要だといったいどこで証明されているんだ？
206の主張はトートロジーだよ。
区別が不要だから不要だと言ってるに過ぎない。
>246の1も未証明な仮定だと思うぞ。
261:デフォルトの名無しさん
07/07/28 05:46:07
>>259
えー俺は釣られてるのかな
それとも俺がバカなのか
> その局面は参照するだけで、勝ち負けか引き分けか決定してるよね？
具体的にはここだろう
今は「区別の必要がある」という仮定で話をしているのだろ？
そして、手順を区別した上で勝ち負け表を作ったのだろ？
つまり、同じ局面でも手順が違うものは別物として勝ち負けを
判定したのだろ？
それを整理して、局面だけから勝ち負けがわかるようにするのだろ？
でも、その整理ができるという保証がないよ
「区別の必要がある」という仮定のもとでは
つまり、区別ありの表から区別なしの表を作るときに、
もし区別ありの表において、ひとつの局面が
手順によって勝ちだったり負けだったり結論が異なっていたら、
区別なしの表にまとめることはできないじゃないか
そして、「区別の必要がある」という仮定はまさに
手順によって結論が異なるかもしれないという意味だ
だからこれは「他の問題」なんかじゃなくて本質的な問題だよ
262:デフォルトの名無しさん
07/07/28 05:48:55
>>261
あ、先に言われた
同意
263:248
07/07/28 05:58:14
あー、ようやく分かってくれる人が居た。
264:デフォルトの名無しさん
07/07/28 06:02:15
>>261
> つまり、区別ありの表から区別なしの表を作るときに、
「区別ありの表」とか、「区別なしの表」なんていらない。
単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
完全解析とは、その一つの表を埋めて、完成させること。
解析後は、「局面情報と手番」から「結果」を参照するだけ。
>でも、その整理ができるという保証がないよ
後で整理する作業は発生しない。
全く問題にならない。
よって、>>206の否定にはならない。
反論をお待ちしています。
265:デフォルトの名無しさん
07/07/28 06:08:05
>>264
おまいさん釣りだろう
議論ごっこなら付き合わないぞ
> 「区別ありの表」とか、「区別なしの表」なんていらない。
> 単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
> 完全解析とは、その一つの表を埋めて、完成させること。
> 全く問題にならない。
これらは>>206の論証の結果として得られるものだろう
それを論証の過程で使うのは「結論先取の詭弁」という詭弁
266:デフォルトの名無しさん
07/07/28 06:09:57
>>264
＞「区別が必要」という仮定で、手順により区別して
＞勝ち負けか引き分けかを決定したとするよね?
＞「区別ありの表」とか、「区別なしの表」なんていらない。
まず仮定をぶち壊してるけどこれOKなの？
267:デフォルトの名無しさん
07/07/28 06:10:13
>>261
おまえが言っているのは、完全解析が不可能、ということじゃないか?
完全解析は「すべての局面の勝ち負けか引き分けかを決定すること」。
つまり、表を正しく完成させるということだぞ？
268:デフォルトの名無しさん
07/07/28 06:14:36
>264
「完全解析とは、そのひとつの表を埋めて、完成させる事」
と言うそれが可能だと言う保証がどこにも無いんだよ。
後で整理する作業が必要ないと言うならそれを作る手順は？
269:デフォルトの名無しさん
07/07/28 06:15:26
>>266
> ＞区別ありの表」とか、「区別なしの表」なんていらない。
> まず仮定をぶち壊してるけどこれOKなの？
言葉が、足りませんでしたか。
完全解析時の作業用の表は、たくさん必要です。
完全解析を行った結果出力として、
>単に「局面情報と手番と結果」を持つ表が一つあるだけでよい。
という表があればよい。
ということです。
完全解析ができるということは、この表を得ることができるということです。
反論をお待ちしています。
270:デフォルトの名無しさん
07/07/28 06:19:19
>>267
いや、いま問題になっているのはそうじゃないよ
将棋のルールは、一見、局面（駒の配置と手番）だけでは
勝ち負けが確定しないように見えるじゃんか
同じ手でも千日手になる場合とそうでない場合があるからね
つまり、将棋において状態とは、駒の配置と手番だけではなくて
「局面の出現回数の履歴」も含めたものでなければならない
そう考えられるわけだよ。素朴には。
でも、もちろん感覚的には、そんなことはなくて、履歴などなくても
局面（駒の配置と手番）だけで判断がつくように思える
その感覚が正しいかどうかがいま問題になっているのだよ
将棋というゲームの状態変数として「駒の配置と手番」だけで
十分なのかどうかと
ルールを素朴に読んだだけでは、不十分に思えてしまうわけで
271:デフォルトの名無しさん
07/07/28 06:20:16
>>269
>>270
272:デフォルトの名無しさん
07/07/28 06:23:42
>>268
「将棋の完全解析は不可能」を主張しているわけだ。
これが不可能なら確かに>>206は成り立たないね。
でも、基本的に>>217にもある通り「可能」が、共通認識なんだけど。
つまり、あなたが「将棋の完全解析は不可能」を証明できなければ、
>>206を否定する必要がある。
がんばってくれ。
273:デフォルトの名無しさん
07/07/28 06:27:43
あはは。千日手模様。
>>268、>>270、>>271の最善手は、「千日手」に持ち込むことか。
274:デフォルトの名無しさん
07/07/28 06:28:57
>>272
横からだけどおまいさんの言う「完全解析」っていうのは
あくまで「駒の配置と手番」だけを状態変数としたものだろう
たとえば、三山崩しにおいて、ルールを読んだだけでは
状態変数として「１の山の個数」「２の山の個数」「３の山の個数」
という３つの状態変数が必要に思える
でも実際にはこんなにいらなくて、それらのXORだけあれば
勝ち負けが判定できる
このように状態変数を減らすことが、将棋でもできるかどうか
それが論点だよ
275:248
07/07/28 06:29:04
>267 >269
完全解析の定義を勝手に自己流に狭く定義しないでくれ。
その定義での完全解析ができるという保証は無いだろ？
実際に可能なのは手順込みの局面にラベルを貼る事。
276:デフォルトの名無しさん
07/07/28 06:31:29
>>270
完全解析の定義と、それが可能かどうかを、まず、答えてください。
ここの立場をはっきりしないとお話にならない。
いいですか？
はっきり明記してくださいよ？
277:デフォルトの名無しさん
07/07/28 06:33:23
>>272
＞二人零和有限確定完全情報ゲーム
「完全情報」ってのは手順の情報も含むんだが
君はこの情報を欠落させても欠落させない場合と等価な事を証明する必要がある
278:デフォルトの名無しさん
07/07/28 06:33:52
>>273
レッテル貼りの詭弁
>>272
共通認識というか定理だろう
将棋のルールは駒の配置と手番とそれらの履歴とで
記述されているわけだから、当然「区別ありの表」は
作れるわけだよ
そこから「履歴」を消してもWell-Definedになる、
というのは自明なことではないと思うよ
279:デフォルトの名無しさん
07/07/28 06:38:49
>>277
>>206
280:デフォルトの名無しさん
07/07/28 06:41:11
>>279
そのアンカじゃループしてるよ
何か別の事言ってよ
281:デフォルトの名無しさん
07/07/28 06:48:05
>>274
>>259
282:248
07/07/28 06:50:04
>206の言ってる事はずっと以前からループしてるんだよ。
区別は必要ないから区別しなくて良いってずーっと。
283:デフォルトの名無しさん
07/07/28 06:51:05
>>259
>>261
284:248
07/07/28 06:55:40
あー、疲れた。
この議論だけで徹夜しちまったよ。
285:デフォルトの名無しさん
07/07/28 06:56:36
反論が無くなったようだしとりあえず寝るか
何かあればまた今夜にでも参加するよ
みんなお疲れ
286:デフォルトの名無しさん
07/07/28 06:57:56
>>284
俺もだ
土曜出勤なのにな
>>276に長レスを書いてたんだけどバカらしくなってきた
ああやって「これにレスできないとバカだ」みたいな言い方をするのは
釣り師が一般人を議論に引きずり込むときの常套手段なんだよなあ
287:デフォルトの名無しさん
07/07/28 07:00:10
>>278、>>280
>>276
よろしく。
288:デフォルトの名無しさん
07/07/28 07:00:41
>>276
可能
289:デフォルトの名無しさん
07/07/28 07:01:35
あ、定義もか
誰か出してなかったっけ
290:デフォルトの名無しさん
07/07/28 07:03:19
>>248、>>278、>>280
>>269にも回答よろ。
291:248
07/07/28 07:05:31
皆さん、お疲れさま。
付き合ってくれてアリガトン。
292:デフォルトの名無しさん
07/07/28 07:06:06
「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
293:デフォルトの名無しさん
07/07/28 07:11:27
自分も寝る
おやすみ
294:デフォルトの名無しさん
07/07/28 07:12:23
なんか急に伸びすぎﾜﾛﾀｗｗｗｗ
295:デフォルトの名無しさん
07/07/28 07:32:27
俺は松原先生の本を昔図書館で何冊か読んだ程度で
ゲームの数学は全然わからないからあれだけど
記号や用語などもたぶんでたらめ
状態変数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
となること
296:デフォルトの名無しさん
07/07/28 07:33:13
以下添え数づけ可能なゲームを考える
将棋は「局面の出現回数の総和」で添え数づけ可能
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)の有限性による
297:デフォルトの名無しさん
07/07/28 08:04:52
>>206はごちゃごちゃ言いすぎ。
完全解析を「すべての局面の勝ち負けか引き分けかを決定すること」と
手順を含まずに定義したんだから、解析後に手順が関係ないのは、自明。
この定義で、解析後に手順がどうのと文句つけるのがアホ。
>>292のように、
>「局面情報と手番と手順と結果」を持つ表を作れる事が完全解析ができるということ
と定義に、手順を入れれば、解析後も手順も関係するが、こんな定義初めて見たよ。
298:デフォルトの名無しさん
07/07/28 08:24:01
>>295, >>296 打ち込みサンクス！！
それによると、A'は履歴を含んでいるわけではないのだから、
やっぱり「完全解析」の定義は、局面だけであって、履歴は関係ないんだね
上の議論は、将棋固有のルールを反映したものではないけれど、
将棋もまた上の数学の枠内でのものなのでしょう
「M(X)は空ではない」ってのは、例えば両方ともパスするしかないような
状況はありえないって事だよね？更に勝ち・負け・引き分け以外の
終わり方は、将棋ではあり得ないから、やっぱり将棋は局面だけで、結論がでているんだ
299:デフォルトの名無しさん
07/07/28 11:21:25
途中まで人間が指して、そのあと最強ソフトが指すならデータベースは使えないってことだろ
千日手があるから・・・
全局面をNとしたとき、その局面が何回現れたかを記録した
0から3までの数字列N個分を保持していなければならない
最終的には4のN乗程度の状態を保持しなければ、途中差しは出来ないって事だ
300:デフォルトの名無しさん
07/07/28 11:36:00
>>297
いやいや、>>292などは既存の常識に疑義を言ってるのだから、
「初めて見る」は非難にはならないよ
>>298
数式に惑わされたらだめだろ
>>295-296は何も新しいこと言ってないぞ
そしてさりげに>>295のAは履歴も含んでるよ
Sは手数とか言ってるしな
履歴を持ってないとVが千日手を判定できない
最後の条件は、勝敗未定ならば有効な手がある
ということ
たとえばもしルールでステールメイトを負けにするのを
忘れていたりすると、
M(X)が空（有効な手がない）で、しかも
勝ち負け引き分けのいずれでもない
という状況が発生するね
301:デフォルトの名無しさん
07/07/28 11:45:39
>>295, >>296 の論法で完全解析が可能であるというには、
駒の配置に加えて「この局面が何回目か」というパラメータも
ノードの状態変数として加える必要があるということ。
完全な履歴は必要ないが、何回目かは必要となる
これが「局面の出現回数の総和で添え数字づけ可能」の意味と理解した。
だとすると、途中で人間×２からコンピュータ×２に交代するとして、
全ての局面の出現回数を保持していなくても「この局面は何回目です」と
だけ伝えればいいんでないかい？後は事前に完全解析された結果に基づいて、
最強ソフトが「先手の勝ちです」「後手の勝ちです」「引き分けです」
とだけ伝えてオシマイになるはず。少なくとも十分条件としては。
302:デフォルトの名無しさん
07/07/28 11:47:24
>>301
勝ち負けの決まっている手順の途中に千日手が現れる可能性有り
303:デフォルトの名無しさん
07/07/28 11:53:02
>>299
将棋というゲームの正しいイメージはこうかもしれないな
N個のマスと、それらをつなぐ線があり
マスのうちいくつかは赤か青に塗ってある
二人が交互にマスに石を置いていく
一つのマスには３個まで石を置ける
４個目の石を置いたら引き分けで終了
赤のマスに石を置いたら先手の勝ち
青のマスに石を置いたら後手の勝ち
ただし直前に相手が置いたマスから
線でつながっているいマスにしか置けない
304:デフォルトの名無しさん
07/07/28 12:11:18
>>300
だいぶ問題が絞られてきたね。
確かに、Aが履歴を含むのかどうかで、話は全く変わってくる。
Aに出てくるnって何だ？漏れはX1, X2が、例えば各駒の場所の様な変数で、
nが駒やボードに対応するものかと思った。で、その直積であるAは
履歴を含んでいないな、と。それだと千日手の判定が出来ないから、
少なくとも、「この局面が何回目か」という情報をAnとして加えてやれば、
完全解析の対象になる、という意味だと理解したんだが。
そしてある局面が何度でてくるかという情報は、手順から
考えれば何通りでもありそうなものだが、完全解析の対象としてみた場合、
最善の選択をして射影していくのだから、S(X)が決まってくるのかなと
思ったのだけど？
突き詰めると、やっぱり
> 将棋は「局面の出現回数の総和」で添え数づけ可能
のところが漏れには解らない。
うーん、難しいね、Anの意味とS(X)の意味、もし良かったら教えて
305:デフォルトの名無しさん
07/07/28 12:18:15
>>302
人間が指す以上、必ずしも最善手の連続ではないから、
それまでの履歴に、「完全解析」では出てこない履歴があって、
以後の手順に千日手をもたらす可能性がある。
そのため事前に用意した「完全解析」のテーブルが必ずしも
使えなくなる、でいい？
だとすると、これって結局、GHIの問題とほとんど同じだね
GHIの場合は、探索アルゴリズムが完全でないことに起因、
人間からコンピュータに替わる場合は、それまでの履歴が最善手でないこと
（勝ち負けを見落として、無駄な経路を辿っている）ことが原因
しかしこれらが、将棋の完全解析の可能性を排除するものではない
って、これでいいのかな？
306:デフォルトの名無しさん
07/07/28 12:25:55
>>304
今から出かけるから手早いけどごめん
X1、…、Xnが駒の場所などの変数で、
A1、…、Anがその値集合
たとえばX1は「先手玉の場所」で
A1は{「1一」、「1二」、…、「9九」}
みたいな感じ
それで、「同一局面４回」のルールを記述するために
（立会人に見せて「引き分けですね」と言ってもらうために）
局面の出現回数も、X1、…、Xnの中で持ってなきゃいけない
俺もおまいさんと多分だいたい同じ考えだよ
でも全部の局面の出現回数を持たなきゃいけないと思ってる
問題図までを指すのは神ならぬ人間なのだから、
神様に言わせれば変な手などもあるはず
そこから神様が引き継いだとして
勝つつもりで指してたら、途中で「その局面は４回目ですよ」
といわれて引き分けになっちゃうかもしれない
そんなわけでXnの中にはすべての（膨大な数の）局面に対して
その出現回数をあらわす変数が含まれてる
ことを俺は想定してた
307:デフォルトの名無しさん
07/07/28 12:29:34
>>306の続き
S(X)は「今の状況までの初手からの手数」で、
どうせ有限なのだからそんなの持ち出さなくてもいいのだけど
議論を簡単にするために出してみた
千日手がある以上、無限に多くの手数は指せない
だから手数の多いものから逆にさかのぼって
2000手以上は解明済み… 1000手以上は解明済み…
などとすることができる
>>305
たとえば簡単な状況で、自玉は必至、相手玉には
３種類の詰みが見えてるとする
ここで、もしその詰み手順の途中の局面が
３回出現済みだったら、自分は相手玉を詰めれない
だから千日手引き分けになる
もちろんそうでなければ勝ちになる
これは履歴が結論に影響を与えてるんじゃないかな
308:デフォルトの名無しさん
07/07/28 12:49:16
>>306
なるほど「局面の出現回数の総和」って「全ての(膨大な数の)局面に対してその出現回数」
っていう意味にも読めるね。確かにこれを全て保持したとしても、局面の数が有限であり、
千日手ルールで頭が押さえられているから、それを状態変数とみたてても、取る値は
高々有限集合になって、>>295 の条件を満たす
人間から神様に交代する場合は、確かに全部保持している必要があるだろうね。
先にも書いたように、勝ちの見落としがあるから、GHI問題と同じ現象が生じる。
で、問題なのは「将棋が完全解析されるには、状態変数として、その局面の出現回数だけで
良いのか、それとも全ての局面についての出現回数が必要なのか？」ってところに絞られてきた。
>>296 氏がさらりと書いた、『将棋は「局面の出現回数の総和」で添え数づけ可能』って
いう命題、この証明を載せた文献とかが解れば、それ見てはっきりするんだが
今から出かけるってことだけど、また暇な時に相手してね、サンクス
309:デフォルトの名無しさん
07/07/28 13:17:27
ところで、完全解析って、すべての局面の「勝ち」「負け」「引き分け」の
他に、「何回間違うと状態が変わるか」って情報いらないの？
対局は、必ず「詰み」まで指すものする。
神Aと神Bが対局して、神Aが先手。先手必勝と分かっている場合、神Aは単に「勝ち」を
選んでいけばいいが、「負け」しか選べない神Bはどんな情報を基にたくさんの「負け」の
中から手を選ぶのかな？
また、形勢差がついている局面から「人間vs神」が指し継ぎ、神が神が判断して形勢不利側を持つ。
このとき神は、差を詰めなければいけない訳だが、どんな情報を基に手を選ぶのかな？
310:デフォルトの名無しさん
07/07/28 13:25:12
よく考えたら、その局面の出現回数だけ保持していたとすると、
状態が遷移したとき、次の状態が何回目かなんて解りっこない
したがって、あるノードの千日手判定はできるが、そこから一つ前の手順に
後退解析することすら不可能になってしまう。なぜなら、ノードは
その局面の出現回数しか保持していないため、
局面A(1回目) → 局面B(4回目) → 千日手で引き分け
といったツリー構造があれば、
局面A(1回目) → 局面B(1回目)
局面A(1回目) → 局面B(2回目)
局面A(1回目) → 局面B(3回目)
というツリー構造も必ず存在するわけだから。したがって、全ての局面に
ついての出現回数がないと、そもそも完全解析の際に千日手に至る
手順を落としていくことが全く不可能になってしまう。
結論は「棋譜としての履歴は必要ないが、全ての局面についての
出現回数を保持する必要がある」ってことになりそうだ。
311:デフォルトの名無しさん
07/07/28 13:25:53
(つづき)
でも全ての局面について出現回数を保持するのは、理論的には簡単であっても、
現実的にはまず不可能。で、結局は順番はともかくどういった局面がこれまでに
出てきたか、その回数と共に保持していくことになる（これは実装上の問題であって、
理論的には全ての局面についての出現回数保持と同じ）。
最後の問題は、なぜ全ての局面の出現回数を保持しておけば、
将棋が添え数づけ可能になるかってことだ。>>296 の後半にある
「次が成り立つとき･･･」以下を証明なしに受け入れるとしても、
ここが争点として残る。でないと「以下添え数づけ可能なゲームを考える」
という前提から崩れてしまう
松原先生の本には、この辺の理論は載っているのかな？
312:デフォルトの名無しさん
07/07/28 13:27:04
>309
それを考慮するためには同じ「勝ち」「負け」「引き分け」の結論でも
どんな結果が「勝ち」 or 「負け」側にとってより良いとされる手なのか
その価値基準を事前に定義しておく必要があるよ。
つまり「勝ち」「負け」が既に分かっている局面で、形勢差はどう定義
されるべきなのか？
313:デフォルトの名無しさん
07/07/28 13:29:43
>>309
うーん完全解析の立場からいえば、その時は神様が「負けました」って
頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
したがってその問題は、完全解析の枠内では無いと思うぞ
実際のプログラムを作る場合には、非常に重要になるには違いないが
余談だけど、プロ棋士も、負けのときに形を作って投げるよね
314:デフォルトの名無しさん
07/07/28 13:34:53
>>313
> うーん完全解析の立場からいえば、その時は神様が「負けました」って
> 頭を下げるんだよ。で、ヘボな人間がキョトンとするという。
これって、笑い話だよね？
結果は分かっているから「いきなり投了」ということで、実際は、指せば指せるよね？
指せないとなると、それはそれで変。
315:デフォルトの名無しさん
07/07/28 13:35:53
>>309
囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
316:デフォルトの名無しさん
07/07/28 13:41:52
>>315
>囲碁やオセロなどは目数や石数によって勝ち（負け）の価値が決められるけど、将棋は？
相手玉を詰ませば勝ち。
317:312
07/07/28 13:42:14
>315
詰め将棋に準じて考えれば勝つ側はなるべく短い手数で勝つ手を選び
負ける側はなるべく長い手数で負ける手を選ぶべきなのだろうが、
結論が引き分けの時は？？？
また手数が同じならすべての手順は価値が同じなのか？
私には良く分からない。
318:デフォルトの名無しさん
07/07/28 13:44:13
>>314
笑い話かどうかともかく、相手のミスをどれだけ仮定するかは、実際の将棋対極では
非常に重要な要素に思うぞ、プログラム開発に限らず。いわゆるハメ手ってやつね。
相手がヘボなら、ハメ手を使って早々に対極を終わらせるだろうし、相手が上手ければ
ハメ手を見透かされて逆に咎められるだろうから、そんな手は使わないだろう。
ハメ手は、素人相手の、相手のミスを前提とした手法だが、プロでも形勢が悪いときは
それに近いことをするようだ。たとえば米長さんの本に、状況がこちらに不利であると、
ギャンブルっぽい手をあえて選ぶと書いてあった。
319:デフォルトの名無しさん
07/07/28 13:55:13
神はどう相手にミスを期待して、手を選ぶのか。
神が神でいられるのは、初期局面だけなのだろうか・・・
320:デフォルトの名無しさん
07/07/28 14:02:00
子ノードの勝ち手順の多寡かなぁ・・・
でも手順は少なくても簡明な勝ちもあるだろうし・・・
321:デフォルトの名無しさん
07/07/28 14:14:10
そうか
この議論は>>162-163に対する>>164のレスから始まってるのか
322:180
07/07/28 14:27:08
>321
そう。そして私が>165の意見に対してキツイ事を書いて
これだけ燃え上がってしまった。
今思えば、彼が考えていた前提（神様同士が初手から対局したと仮定）が
分からなかったとは言え、失礼な書き方をしてしまった。
>165さん
今更ですが済みません。ゴメンナサイ！
323:デフォルトの名無しさん
07/07/28 14:29:27
>>317
昔、ちょっとGAをやったとき、生き残り戦略はそんな感じにしてた。
引き分けの時、手数が同じ時は、駒得している手数が長いほうが有利としてた。
324:デフォルトの名無しさん
07/07/28 16:27:51
くどいようだけど、最後に一言だけ言わせて。
既存のゲームの理論を用いて、将棋の完全解析可能性を証明するには、
将棋が添え数づけ可能であることを示す必要があるのだろう。そして局面に、
全ての局面についての出現回数を保持すれば、それが添え数づけ可能になるようだ
しかし、それは「将棋が完全解析可能か」という命題には答えても、
我々が議論してきた問題とは微妙にずれているような気がする。
我々は「将棋を完全解析するのに、局面の出現回数（＝履歴）を保持する必要があるのか？」
という問題を議論してきたはず。これは「将棋は完全解析可能か？」とは違う。
「局面だけで完全解析が出来るか？」という命題は、>>296の理論にもとづいて
行おうとする限りにおいては、千日手の判定ができないため>>300 氏の言っている理由により
証明出来ない。しかしこれは、他の理論で証明することまでも不可能であると言っている訳ではない。
もし局面だけで完全解析が可能だとすると、少なくとも出現回数付きの完全解析から、
一意に射影できるはず。なぜなら後者は前者に情報を追加したものだから。
もし前者で完全解析が可能であるなら、追加した情報（＝局面の出現回数）は
余分な情報であって、後から射影作業によって取り除ける。