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

1 名前：デフォルトの名無しさん mailto:sage [2007/04/06(金) 15:33:11 ] できたらよろこんでやる。 前スレ おまいら最強の将棋プログラムしてみろよ part5 pc11.2ch.net/test/read.cgi/tech/1109307327/ 751 名前：デフォルトの名無しさん mailto:sage [2008/05/24(土) 11:24:13 ] チェスの終盤は、ポーン2個vsポーン2個くらいの状況でも 普通のコンピュータで完全に読みきることは出来ないくらい難しい。 データベースがあると終盤をかなり上手く指すようになるけど 思考力は人間の半分以下 752 名前：デフォルトの名無しさん mailto:age [2008/05/26(月) 03:00:37 ] ネタ提供？　2ch棋譜の内40433件の分析したデータ ＊：先手の勝ち数：後手の勝ち数：＊：＊：戦型 1:739:626:0:0:その他の戦型 2:1282:1131:0:0:横歩取り 3:1994:1785:0:0:中飛車 4:4975:4259:0:0:矢倉 5:4208:3825:0:0:四間飛車 6:1647:1608:0:0:相掛かり 7:516:378:0:0:角交換腰掛銀 8:37:33:0:0:袖飛車 9:928:749:0:0:向飛車 10:1699:1679:0:0:三間飛車 11:646:617:0:0:相振飛車 12:114:121:0:0:右四間飛車 13:847:754:0:0:角換わり 14:737:822:0:0:ひねり飛車 15:40:43:0:0:筋違角 16:123:81:0:0:右玉 17:297:227:0:0:陽動振飛車 18:56:38:0:0:５筋位取り 19:139:144:0:0:角交換その他 20:50:60:0:0:角換わり棒銀 21:34:17:0:0:角換わり拒否 22:18:13:0:0:風車 23:38:20:0:0:棒銀 24:29:23:0:0:タテ歩取り 25:93:98:0:0:雁木 753 名前：デフォルトの名無しさん mailto:age [2008/05/26(月) 03:04:33 ] ＊：先手の勝ち数：後手の勝ち数：＊：＊：棋戦 1:968:881:0:0:王位戦 2:5715:5183:0:0:順位戦 3:837:764:0:0:ＮＨＫ杯 4:1525:1229:0:0:竜王戦 5:146:128:0:0:日本シリーズ 6:228:196:0:0:朝日オープン 7:1438:1385:0:0:その他の棋戦 8:788:680:0:0:棋王戦 9:71:65:0:0:達人戦 10:1503:1308:0:0:棋聖戦 11:741:745:0:0:銀河戦 12:133:107:0:0:レディースオープン 13:865:820:0:0:王座戦 14:653:540:0:0:新人王戦 15:269:212:0:0:名人戦 16:40:43:0:0:朝日アマ名人戦 17:249:230:0:0:勝ち抜き戦 18:127:125:0:0:女流王将戦 19:102:99:0:0:倉敷藤花 20:490:434:0:0:早指戦 21:1122:943:0:0:王将戦 22:116:108:0:0:女流王位戦 23:212:203:0:0:女流名人戦 24:73:80:0:0:近将カップ 25:130:96:0:0:三段リーグ 26:101:104:0:0:早指新鋭戦 27:10:9:0:0:中学生名人戦 28:20:28:0:0:アマ王将戦 29:10:21:0:0:赤旗名人戦 30:59:53:0:0:全日アマ名人戦 754 名前：デフォルトの名無しさん mailto:age [2008/05/26(月) 03:06:15 ] 30:59:53:0:0:全日アマ名人戦 31:13:22:0:0:平成最強戦 32:31:25:0:0:グランドチャンピオン 33:55:63:0:0:鹿島杯 34:25:30:0:0:アマ竜王戦 35:604:538:0:0:全日プロ 36:28:22:0:0:レーティング選手権 37:2:4:0:0:学生王将戦 38:12:20:0:0:小学生名人戦 39:19:15:0:0:学生名人戦 40:11:13:0:0:女流アマ名人戦 41:13:25:0:0:ＩＢＭ杯 42:177:170:0:0:天王戦 43:95:84:0:0:若獅子戦 44:411:333:0:0:名将戦 45:430:309:0:0:十段戦 46:48:41:0:0:若駒戦 47:76:94:0:0:連盟杯戦 48:19:16:0:0:名棋戦 49:100:100:0:0:奨励会 50:43:53:0:0:最強者決定戦 51:27:16:0:0:古豪新鋭戦 52:82:87:0:0:九段戦 53:19:44:0:0:東京新聞杯 54:36:40:0:0:支部対抗戦 55:4:1:0:0:学生女流名人戦 755 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 03:07:24 ] 56:1:0:0:0:新春お好み対局 57:1:0:0:0:細：九段設定戦 58:8:10:0:0:アマ女王戦 59:10:7:0:0:育成会 60:47:61:0:0:都名人戦 61:8:4:0:0:高校竜王戦 62:1:3:0:0:その他の棋戦　　　　　 63:28:18:0:0:大和証券杯 64:1:0:0:0:ＮＨＫ杯　　　　　　 65:0:2:0:0:順位戦　　　　　　　 66:38:30:0:0:朝日杯 67:22:31:0:0:マイナビ 68:0:1:0:0:倉敷藤花戦 756 名前：デフォルトの名無しさん mailto:sage [2008/05/26(月) 03:09:33 ] ＊：先手で勝ち数：先手で負け数：後手で勝ち数：後手で負け数：名前 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:近藤正和 以下省略 757 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 02:43:54 ] >>752みて思ったんだけど将棋の戦型って曖昧だよな 四間飛車だけだと先後どちらが振ったか分からないし、角換わりだけやたらと分類されてたり もっとスマートに記述する方法はないの？ 758 名前：デフォルトの名無しさん mailto:sage [2008/05/28(水) 23:12:53 ] 定跡データベースの樹形図で葉の数が均等になるようにすればよい 759 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 03:58:58 ] DNAの解析を各自のコンピュータで分析した結果をあつめて 実現しようっていうのがあったとおもうけど それと似たように分散している計算力をあつめて全ての局面を評価するってできない？ 760 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 04:53:19 ] 分散処理は既に行われてるが全ては無理 761 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 23:53:06 ] 将棋も囲碁もその場が今どちらが有利かなんて人によって考えが違うに決まってる だから色んな人工頭脳をもった将棋プログラムを作ればいいと思う 俺には無理だけど 762 名前：デフォルトの名無しさん mailto:sage [2008/05/31(土) 23:57:37 ] ログも読まず低レベルながらに頑張って口出ししては消えていく そういう輩が時々現れるよね 763 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 04:05:53 ] ９ｘ９の盤面に8種類のコマが自分と相手の分あって、あとは空だから 81**(8*2+1) で、ルールの制約があるからこれよりもっと少ないと思う www.google.co.jp/search?hl=ja&rlz=1T4GFRD_ja___JP238&q=81**%288*2%2B1%29&btnG=%E6%A4%9C%E7%B4%A2&lr= それまでの手がどうであってもルール上許される配置のどれかになる でルール上許される全ての局面に評価値をつける 勝敗が微妙な局面もあるけど、そこから 自分の勝ちの局面に少ない手で到達できるとか 相手の打ち方によらず確実に勝ち局面に到達できる手とか があるほど評価値を高くするって案はどう？ 764 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 04:24:12 ] >>763 成りがあるから81**29か www.google.co.jp/search?hl=ja&rlz=1T4GFRD_ja___JP238&q=81**29&lr= で特定局面から持ち駒も含めて別の局面へ遷移する手を考える つまり各局面間の遷移に分割して解析する 765 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 04:43:55 ] >>764 ちがうわ 29**81かｗ 81C40 * 29**40 でもいいか？ 766 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 04:47:39 ] 81C40 * 29^40 = 6.65363027 × 10^81 www.google.co.jp/search?hl=ja&q=%2881+choose+40%29*29%5E40&btnG=Google+%E6%A4%9C%E7%B4%A2&lr= 767 名前：デフォルトの名無しさん mailto:age [2008/06/01(日) 10:47:51 ] このスレの過去スレを読みたいのです。どこかで見れますか? 又は、持っている方UPお願いいたします。 768 名前：デフォルトの名無しさん [2008/06/01(日) 12:29:25 ] つ　usapyon.dip.jp/shogi/computer/index.htm 769 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 15:21:19 ] ありがとうございます。 770 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 15:27:02 ] どういたしまして 771 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 19:14:07 ] 仮にすべての局面を評価できるとしたら、投了直前の局面をすべて生成して勝ち負けつけて 開始局面に向かって戻っていくだけだから、連続的な評価値なんて不要 772 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 19:16:13 ] >>771 戻して行く？ どこで手駒を使ったかまで遡れるのか？ 773 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 19:24:15 ] >764 （現在の）局面状態だけを見て各局面への遷移を分類するのは難しい。 あちこちにループが発生する。詳しくはこのスレを頭から良く読んでね。 774 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 19:31:23 ] >771と>772が想定している「全ての局面」の意味が違うようだな。 つまり、その局面に至る経路情報を含めて分類してるのか、 経路情報は捨てているのか？ 775 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 19:57:50 ] 将棋でこういうデータ調べてる人っているの？ www9.atwiki.jp/othello/pages/27.html 776 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 20:11:20 ] >775 居ないんじゃないかな？ オセロや囲碁と違って将棋は終盤がなかなか収束しない。 終局図が何通りあるのかも良く分からんし。 777 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 20:26:01 ] >>771 投了局面から「詰めろ？」を遡ることで 投了局面より前の局面の勝敗を決定できるのは確かだと思う だけど更に遡ると、遡ったのとは違う経路で将棋が進んで 違う結果の局面になることがあると思う 一手で形勢逆転するような手があると思う >>773 ループは枝刈りするとか対策は考えられるんじゃないかな 目標の中間局面に到達するまでの手の経路は 手数が多くても少なくても勝敗には関係ないよね 最短でなくて遠回りしてもいい さしてるうちに、最初目標としていた中間局面じゃなくて 自分に有利な別の中間局面に変えてもいいし 778 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 20:36:36 ] ・ルール上可能な局面（駒の配置図）はそれぞれがネットワーク状に「手」で繋がる ・局面のサブセットにだけ勝敗の評価が決まっているものがある ・局面の遷移がかなり限定されていれば（詰めろみたいに）勝敗の評価を決められる ・そのほかの局面は手によって評価が変わる って感じのイメージを持ってる 779 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 21:47:41 ] 上の方で議論になっているけど 将棋の「局面」を見て形勢を判断するためには 単なる盤上や駒台の様子だけではなく その局面に至るまでの経緯も必要 極端な話、たとえば指しかけを引き継いだとして 「この盤面は敵玉に詰みがあるぞ！」と思っても それは千日手の４回目かもしれないとかそういうこと 780 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 21:49:46 ] >777-778 末端局面から遡って勝ち、負け、引き分け（千日手）で 確定的にラベル付けするだけじゃなく、 途中局面に中間的な評価値を付けようって事？ おもしろい考え方だが、一体どうやって？ 781 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 21:54:38 ] 末端局面からさかのぼるのなら途中も当然 「勝ち」か「負け」か「引き分け」になるだろうって 782 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:01:06 ] >>779 > それは千日手の４回目かもしれないとかそういうこと (現在の技術で可能かどうかは知らんが)データベースを引くのだから、現在の局面に 至るまでに詰みがある局面を逃しているはずはないと仮定できるだろう。 だから、連続王手の千日手のことは考慮しなくて良いと思う。 783 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:03:41 ] >>779 ソフトが「この盤面は敵玉に詰みがあるぞ！」と思って指したら。 システムから千日手で引き分けと言われるだけで。その事にソフトは何の関係が無いわけ。 それを操作した人間が、あちゃ〜〜前に勝ってたのか、と思うだけ。 それに何の問題があるのか? 784 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:05:15 ] 引き継ぐ前の事を意識する必要は無い。 785 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:05:59 ] >781 もちろん、そうなんだが >777-778が何か面白いアイデア持ってないかな？と。 例えば勝ちに至る経路の広さや近さで評価値を付けるとか。 786 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:06:55 ] なんかminmax法も分かってない奴がいるな 787 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:16:22 ] >>786 いや、「神ならぬ人間がその盤面を引き継いだとして どれほど勝ちやすいか」っていう評価値じゃね？ 788 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:21:04 ] >>782 自分についてはそういう仮定を置くのもアリかもしれないけど 少なくとも相手のことについてはまずいだろう 「うむ、俺が勝つにはこの手しかない！ 　でも相手にこう王手されるとまずいな… 　しかたない。勝ちはあきらめて千日手に持ち込むか…」 というようなケースってあるじゃんか ところがこの相手の王手が千日手の４回目かもしれない 789 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:27:28 ] >>788 与えられた局面が勝ちか負けかを判定するデータベースを構築する話をしているんだろ？ 相手がポカして相手が勝てる局面を(その勝ちのための指し手を連続王手の千日手で)負けの状態に してようが、それはデータベース構築には何の関係もないことだろ。 790 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:27:50 ] 引き継いだ前の人間の意識を、引き継いだソフトは考慮する必要は無い。 もし考慮して欲しいなら、その旨のインターフェースを作るべき。 しかしその人間の目的を読み取る機能は、最強の将棋ソフト作るより遥かに 困難な人工知能が必要。 791 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:34:58 ] いや、なんかおまいら話が変な方向へ ひとまず>>165-395あたりは読んでくれ 792 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:37:17 ] >789 実はそのデータベースを構築する事そのものが、その局面に至る経路を考慮する事を要請する。 さもないと探索あるいは末端局面からの遡りが止まらなくなる。 良く考えてみないと分かりにくい事だが、なぜ千日手のルールがあるのかを考えてみよう。 793 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:37:36 ] >>789 「それは関係ないことだから関係ないのである。」 では説明になってないぽ 794 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:38:32 ] だからさ、一連の流れのある局面が、他の流れのある局面と同じと言う事は無いのかと、言う事だろ。 795 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:44:14 ] 流れとか「局面」とか、意味のあいまいな言葉を無定義で使うなよ 796 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:48:07 ] 隣の将棋盤の駒の配置と持ち駒の数や種類が、その隣の違う対局の数時間前のときの全く同じ将棋盤の駒の配置と持ち駒の数や種類がある手において、同一だったと言う事は無いのかと言ってる。 797 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 22:55:09 ] >795 「流れ」と言うのはある局面から別の局面に至る経路の事だよ、多分。 >794じゃないけど。 で、違う経路から見かけ上同一の局面に至る事は それこそ幾らでもあるし、ループする事もある。 798 名前：デフォルトの名無しさん [2008/06/01(日) 23:03:43 ] 評価値として 勝ち、負け、千日手、勝ちか千日手、負けか千日手 を定義すれば局面評価DBを作る点では問題無くない？ 799 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 23:11:41 ] >>798 問題ないかどうかは、どういう目的で作るのかによるけど そもそもそのような評価が、駒配置だけを見て可能か ということに対して懐疑的なんだと思うよ 800 名前：デフォルトの名無しさん mailto:sage [2008/06/01(日) 23:14:47 ] 今の指し将棋プログラムは現状の局面状態（駒割と駒の配置）だけで持って、 盤面を評価してるように見えるから　>789のように勘違いする人も居るんだよね。 ところがその評価はかなり荒い近似に過ぎないから通用するのであって、 厳密に確定局面から遡って評価しようとするとそこに至る経路情報が必須になる。 詰め将棋プログラムは確実に経路情報を考慮してるし、しないと答えを間違う。 いわゆるGHI問題。 801 名前：デフォルトの名無しさん [2008/06/01(日) 23:29:54 ] 経路情報は局面間を結ぶ有向線として持てると思う 勝ち負けの決まる局面は確かに存在する これらの情報で中間局面をどう評価するかだけど 相手の手が何であっても勝ち局面に遷移できる局面は勝ちたが 相手の手によって勝ち千日手負けのいずれも有りうる局面もあると思う そんな局面は勝ちやすさで評価する 勝ちやすさは例えば勝ち評価値の局面への距離とかで決める そんな単純じゃないと思うけどね 802 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:19:51 ] >>800 俺はコンピュータ将棋の開発者で、GHI問題はもちろん知っている。 GHI問題を正しく理解していないのはお前のほうだろ。 詰みのあるすべての局面の集合から逆算してんだぜ？ GHI問題なんか起こるわけないだろ。 ただしそこに至るまでに同一局面が3回以上出てきていないという条件が必要だが。 (連続王手の千日手を発生させないため) 803 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:21:54 ] >>802 >ただしそこに至るまでに同一局面が3回以上出てきていないという条件が必要だが。 おいおいw 804 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:24:48 ] >>803 お前、頭おかしいんじゃねーの？ 805 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:28:27 ] > 俺はコンピュータ将棋の開発者で、 権威づけか 806 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:29:35 ] >>805 実際に作ってもない/作れない/作ったことがない奴に言われたくないね。 807 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:32:17 ] 作ってるのに理屈がわかってないんだとしたら そっちの方がよっぽど問題のような… そんなに俺様の言うことを聞けって言いたいなら コードの断片でもうｐしてからにしろよ できないならおとなしく名無しに戻っとけ 808 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:35:10 ] >>807 理屈がわかってないのはお前。 お前はGHI問題が何故発生するのかわかっていない。 809 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:37:14 ] >俺はコンピュータ将棋の開発者 イタイ奴が来たなｗｗｗ 頭おかしんじゃね？ 810 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:38:47 ] >807 詰め将棋解法プログラムのような答えが 厳密に求められる問題に取り組まないと 開発者と言えども勘違いする可能性はあるな。 811 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:39:57 ] >>810 お前もGHI問題が何故発生するのか理解できていない。 812 名前：807 mailto:sage [2008/06/02(月) 00:40:44 ] >>808 いや俺は横から茶々を入れてるだけで 何も言ってないんだけどな 自分以外（正確には自分に異論をいう奴）を全部 一人の人間だと思っちゃうっていうのは ありがちなことなんだけどかっこよくはないよ GHI問題については>>191あたりから始まって >>234とかの議論でさんざんがいしゅつなんだけど もちろんそのへんはログ読んだ上でのレスだよな？ しかも「お前はわかっていない」とかじゃなくてさ、 だったらちょっと簡単にでいいから説明してみろよ ほら 813 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:43:39 ] 経路君のソフト楽しみにしてます＾＾ 814 名前：789 mailto:sage [2008/06/02(月) 00:44:07 ] >>812 詰み局面から逆算するんだぜ。GHI問題なんか起こらないよ。 GHI問題が起きるのは、探索中の循環を即、不詰めと判定するからだ。 GHI問題でよく話題になる図を勝ちの局面であるIから逆算して行くとわかる。 815 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:45:06 ] お前ら、シャープの亀山工場で液晶を組み立ててる工員が みんな液晶の仕組みを理解してるだなんて思ってないだろ？ そういうことだよ 816 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:48:23 ] >814 どのように逆算するの？ つまりその逆算する時に経路情報を考慮するの？しないの？ 817 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:49:31 ] >>814 あー詰み局面から逆算していく話が続いてたのか その場合で、局面というのは駒配置だけじゃなくて 局面の出現回数も持たなきゃいけないよな そうしないと、千日手になるはずの手順は 永遠に「勝ち」とも「負け」とも塗られないことになる ような気がするんだが 818 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:52:52 ] ○→○→○→○→○ 　 　 　 　 ↑　 　 　 ↓ 　 　 　 　 ○←○←○ こういうループだけじゃなくて ○→○→○→○→○ ↑　 　 　 ↓ ○←○←○ こういうループもあるよな 819 名前：789 mailto:sage [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の局面の勝ちを判定できている。 820 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:55:09 ] ちなみに>>789は意地悪だから図を書いてくれないけど >>234のPDFを参照な 821 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 00:56:26 ] >>818 　　　　 　 　./ﾆＹﾆヽ 　r､r.rヽ. 　/ （0)(0）ヽ r |_,|_,|_,|／　 ⌒｀´⌒　＼　　　で？っていう |_,|_,|_,|_,|　, -）　　　　（-、.|　　　 |_,|_,|_人　(^ iヽ＿＿ ノ　l | |　)　　 ヽﾉ　|　 `ー'´ 　 ／ |　　`".｀´ 　ﾉ 　　　入＿ノ 　＼＿／ 　　 ／ 　 / 822 名前：789 mailto:sage [2008/06/02(月) 00:56:33 ] >>817 > あー詰み局面から逆算していく話が続いてたのか 続いているも何も、最初から最後まで、詰み局面をデータベース化しよう、という話なのだが。 具体的には、これだ。 d.hatena.ne.jp/KZR/20080531/p1 823 名前：789 mailto:sage [2008/06/02(月) 00:57:20 ] >>820 すまない。俺は意地悪なんじゃなくて図とか苦手なんだ。ほら…わかるだろ。 824 名前：789 mailto:sage [2008/06/02(月) 01:02:58 ] >>817 > その場合で、局面というのは駒配置だけじゃなくて > 局面の出現回数も持たなきゃいけないよな 「局面の出現回数」は持たなくてもいい。 >802で書いたが 「ただしそこ(判定したい局面)に至るまでに同一局面が3回以上出てきていないという条件が必要」だが、 これを前提条件とできるなら「局面の出現回数」のデータベースへの記録は不要。 ただし、勝ち/負け/引き分けとラベリングされた局面はすべて記録(データベース上に保持)していることが前提。 825 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:03:49 ] >>882 あれ、与えられた局面が勝ちか負けかを判定するデータベース つまり必勝定跡を構築する話をしているんだと思ってたんだが そして、その「局面」というのが駒配置だけでよいのか、それとも 駒配置の出現回数も持っていなきゃならないのかだと思ったが 経路という言い方をするからGHI問題と絡んでいるように見えて いろいろみんな混乱したるんじゃないかな それで、仮に、駒配置だけで勝ち負けが決まるのだとしたら もちろん「この局面は千日手」というラベルを貼られる 局面（駒配置）もあると思うのだけど、 詰み局面（駒配置）からたどっていったとき 千日手のラベルを貼る機会というのはどういうとき？ 826 名前：789 mailto:sage [2008/06/02(月) 01:04:53 ] あと、終盤のデータベース化については >822 以外にも d.hatena.ne.jp/mkomiya/20080601/1212289142 d.hatena.ne.jp/yaneurao/20080602 このへんも参考にしてくれ。 827 名前：789 mailto:sage [2008/06/02(月) 01:06:49 ] >>825 > あれ、与えられた局面が勝ちか負けかを判定するデータベース > つまり必勝定跡を構築する話をしているんだと思ってたんだが その過程で引き分けデータベースも出来るだろ。 > そして、その「局面」というのが駒配置だけでよいのか、それとも > 駒配置の出現回数も持っていなきゃならないのかだと思ったが 俺の言う　局面　とは　盤上の駒配置・手番。その局面の出現回数は関係ない。 828 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:17:58 ] >>824 あー、その条件があればたぶんそうだよな でも前に進むなら、ループしたら「千日手」、でいいと思うけど 後ろに戻っているのだから難しい気が まあ、どうせ局面（駒配置）の数は有限なのだから 全部調べて「勝ち」にも「負け」にもならなかったものは千日手 でいいのかもしれないけど 829 名前：789 mailto:sage [2008/06/02(月) 01:20:12 ] >>825 > 詰み局面（駒配置）からたどっていったとき > 千日手のラベルを貼る機会というのはどういうとき？ いま、 A,Bが未ラベルとする。Aは自分の手番、Bは相手の手番とする。 このとき A→B→A のような循環を発見した。 AからB以外に行く手は負けとする。 BからA以外に行く手は勝ち(＝相手の負け)とする。 このとき自分にとっても相手にとっても千日手を選択するのが最善だからA,Bの局面の最善は引き分け。 このように未ラベルの局面同士の循環を発見して、この循環がお互いの最善であるときこれらの局面を 引き分けのリストに追加する。 825はどうも勘違いしているようだが、このA,Bの局面の「出現回数」を記録しておいてもこの循環の検出の役には立たない。 830 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:21:27 ] >>818 下の図は「双方最善を尽くしたら出現しないはずの詰み形」かな つまりループからしか到達できない詰み形 でもそれを排除してしまったら次の一手解答マシンとは言えないよ 831 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:27:55 ] >>829 あー、うんそれならいいよ ようするに>>828の後半と同じことだな 神ならぬ人間から盤面を引き継ぐことはない、という前提なら たぶんそれでいいんじゃないかと思う 「勝ち筋があるけど、引継ぎ元が棋譜汚しをしてくれたせいで 千日手になるからそれは指せない」とかは考慮しないということで 832 名前：789 mailto:sage [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 mailto:sage [2008/06/02(月) 01:31:04 ] 832に書き忘れた。 garbageが起きて回収されるなら、それは循環参照がされていたということだ。 garbage collectorの実装はいろいろあるから、詳しくはその手の本を見てくれ。 834 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:31:38 ] >>832 あー、GCが循環参照を発見する方法か でも、現実的な時間にリアルタイムで計算するのではなくて 巨大な次の一手解答集を用意するイメージなのであれば 勝ちでも負けでもないものは引き分け、でいいような 835 名前：789 mailto:sage [2008/06/02(月) 01:33:45 ] >>834 おまい、なかなか頭がいいな。 コンピュータ将棋の開発者だな？大会で待ってるぜ！(｀ω´) 名無しに戻る。長々と失礼した。 836 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:36:56 ] いや、俺は松原先生の本を昔図書館で何冊か読んだ程度で ゲームの数学は全然わからない素人だからあれだが 寝るぽ 乙 837 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:39:22 ] >830 そうだよな。 >829の話は尤もらしいのでつい信用しそうになったが、 先手後手双方、最善を尽くした場合の局面だけでなく、 任意の局面にラベリングしようと思ったら 扱えない局面が出て来そうな気がする。 詰み局面から逆算してデータベース化するだけであって、 そんなもの知らないってんなら、それはそれで良いけど。 838 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:41:33 ] ループ内に王手が存在するかどうか吟味しなきゃならないから >>834の方法はそのままでは駄目だな 839 名前：789 mailto:sage [2008/06/02(月) 01:45:11 ] >>837 > 任意の局面にラベリングしようと思ったら 「1手詰みの局面」のすべてを表す集合から逆算するって話なんだぜ？ 任意の局面にラベリングできるよ。 将棋の初期陣形とは何の関係もない。 詰みに至ることが出来る局面の解は(無限のメモリと無限の計算時間があれば) すべて求めるに決まってるじゃないか。 840 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:47:59 ] 盤面が有限だから有限でいいけどな 841 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:52:00 ] 「どうやっても連続王手の千日手に持ち込まれてしまい負け」が処理できない 842 名前：789 mailto:sage [2008/06/02(月) 01:52:19 ] >>838 それはその通り。 検出された循環(DCG)内で、連続王手にならないループが一つもなければないほうの負け。 双方が王手しあうループしかない場合、互いに逆王手を繰り返すことになるのだが、これは よく知らないが、将棋のルールでは引き分けなんじゃないかと思う。 843 名前：789 mailto:sage [2008/06/02(月) 01:53:07 ] >>841 >>842 844 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 01:56:21 ] 千日手になるときに手を変えなきゃならないだから その４回目に登場する局面を指す方が負けか すると、「どの地点からループに合流したか」が 重要になってくるような気も…。 845 名前：789 mailto:sage [2008/06/02(月) 01:57:15 ] >>844 >>824 846 名前：789 mailto:sage [2008/06/02(月) 01:58:32 ] あっ。844は842の双方連続王手のことか。 いま検討していたのだが、双方連続王手は普通の将棋の駒では実現できないようだ。 847 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 02:02:19 ] いや、だから A→B→A が連続逆王手のループだとして A は自分の手番、B は相手の手番だとして C → B → A → B → A → B → A と進めば次で B を指せないからこれは自分の負け D → A → B → A → B → A → B と進めば次で A を指せないからこれは自分の勝ち だったら A とか B は自分の勝ちなのか負けなのか 848 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 02:05:39 ] >>846 んーそれはほんとなのかな 849 名前：789 mailto:sage [2008/06/02(月) 02:07:46 ] >>848 本当だ。俺には証明はスマートには出来ないが。 850 名前：デフォルトの名無しさん mailto:sage [2008/06/02(月) 02:21:39 ] >>849 出来る気がする。考えてみよう 851 名前：789 mailto:sage [2008/06/02(月) 02:26:14 ] >>850 俺が1分も考えて出来ないと結論を出した。間違いなく出来ない。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef