コンピュータで将棋の解析を夢見るスレ

先手必勝なのか、後手必勝なのか、引き分けなのか？
XX定跡の局面はどちらが勝ちなのか？などなど

コンピュータを使ってどの程度解析が可能なのか、
その実践方法や例などを含め語ってください

５五将棋完全解析、
まだ？

手始めに誰か、動物将棋の完全解析について語ってくれ

動物将棋は、プロが後手持てば
ソフトに勝ちきれるの？

>>4
動物将棋のプロなんかいないと思うが。
本将棋のプロじゃ負けると思う。

>>3
あんなに駒が少なく自由度も少ないのに、
最善同士の試合で78手もかかるというのがちょっと驚き。
実際にゲームをしてみると、そんなに手数はかからない。
先手が常に千日手狙いの手を指すのでそんな長い手数がかかるのだろうか。

ちょっとこのスレを借りて、「あから総合スレッド」の >>1000に一言反論させてもらうと
似てるかも知れないが目的が違う。

私の場合、先手後手のバランスが取れて無いと人間同士が対局する時のゲーム性を損なうと考えてます。
例えば、先手有利なのがもしも統計的にはっきりしたとしたら実際の対局が詰まらなくなるから
多分、ルールを少しいじる事を考えざるを得なくなるでしょう。
囲碁のコミのようにね。

そうやって、結局バランスを取って行かざるを得ない。

>>7
先手有利なのは統計的にはっきりしてるけど、その差は極めて小さいし、
後手は新戦法を考え出せばいいので、ルールを変える必要が無い。

>>7
完全解析の結果が先手必勝かどうかと人間同士の対局で先手有利かどうかは
関係ないから。将棋のコンピュータ解析が進んで部分的な完全解析が
プロ棋士の定跡に影響を与える頃にはもう将棋のゲームとしての寿命は
尽きてしまうし。

>>8
そう、実戦でバランスが取れていれば良い。
しかし、その理想を極限まで追求すれば互いに最善手を指した時の結論は引き分けと言う事になるんじゃ無いの？
と言うこと。
一方、実戦で引き分けが起きる可能性は極限まで小さくしたい。
(どちらかがわずかでも間違えると相手が勝つ)

そう言うルールを持つのが二人零和完全情報ゲームの理想だと思う。

つまり、コンピューターで解析する事が難しいほど良くできたボードゲーム。
簡単に解析できるのはつまらないボードゲームでしょう。

囲碁はその点は微調整が出来るので（その点だけを見れば）優れていると言える。
コミを適切に調整すれば、双方最善で引き分けになる。
点数制なので実戦では引き分けになることは少ない。

オセロの場合も、
黒番と白番両方で対局して点数を合計するので、
囲碁と同様、
双方最善で引き分けになり、実戦で引き分けになることは少ない。

チェスは先手が将棋以上に有利なので、偶数回勝負は必須。
後手はなるべく引き分けになるように、先手は優勢を保つようにが鉄則。

>>8
数%あるのに極めて小さいと言っちゃう神経が良くわからない。

> オセロの場合も、
> 黒番と白番両方で対局して点数を合計するので、
いったいいつの話をしているのだ？
初期の頃は２局打ちがあったけど、時間が倍かかるので、
公式戦でも１局打ち。
ただし、伏石で引き分け勝ちを選ぶことはできる。

> 双方最善で引き分けになり、実戦で引き分けになることは少ない。
引き分け進行が数多く発見されていて、それを外して勝つことは
難しいので、双方最善で引き分けではないかと言われているが、
完全解析されたわけではないので、厳密に証明されたわけではない。

>>14
> 公式戦でも１局打ち。
今はそうなのか。知らなかった。退化だな。

> 完全解析されたわけではないので、厳密に証明されたわけではない。
いや、双方最善で引き分けというのは偶数ゲームの場合。

>コンピューターで解析する事が難しいほど良くできたボードゲーム

？
コンピューターにとって解析が難しいゲームは人為的にいくらでもつくる事はできるだろうが
それが人間にとって「良くできたボードゲーム」になるかどうかは、まったく別問題

>>16
駒の数や盤面のサイズがでかいために解析が難しいと言うのなら詰まらないゲームでしょうね。
そうでは無くて、サイズはそれほどでも無いのに解析が難しいゲームは良いゲームだと私は思います。

あと、ルール自体は単純で覚えやすいと言うのも良いボードゲームの条件でしょう。
でありながら解析は難しい、すなわち必勝法、あるいは絶対負けない方法が容易には見つからないゲーム。
そう言う本質的な複雑性が高いゲームが良いボードゲームだと思います。

>>18
今後チェスや将棋以上に流行るボードゲームなんて出ないだろう。
あなたの言う特性がどんなに優れていても。

将棋の結論 : 先手必勝、後手必勝、引き分け、いずれも決定不能

それに対する証明を得たが、それを書くには余白が足りない

>>19
将棋が流行っているとはとても言えないと思う。
日本だけのローカルゲームだし。
ボードゲーム自体衰退の一途だよ。

>>21
その将棋以上に流行る２人対人型の純ボードゲームが今後生まれるとは
とうてい思えないよ。

>>17
> そうでは無くて、サイズはそれほどでも無いのに解析が難しいゲームは良いゲームだと私は思います。
サイズだけじゃなく、駒の動きみたいな人為的、作為的ルールも少なくないと。
Vantage Master というゲーム、
将棋を複雑化したような物でこれはこれで非常に面白いのだが、
将棋より戦略性が深いかは疑問。

つまり、どうぶつしょうぎは人間が遊ぶには十分に深いということだねぇ
さすがプロ的には後手有利と研究しちゃう訳だけど、その後完全解析で後手必勝というのは示唆的だ

どの文章を受けて「つまり」なの？
個人的には「十分深い」とは思えないけど。
盤が小さいのに良く出来たゲームだとは思う。

プロの感触が結局、正しかったと言うのは確かに驚嘆したね。

>>20
フェルマーさん、遠慮無く書いてください。

５五将棋とオセロは
どっちの完全解析が先？

フェルマーは判って無かったという説が有力だが、
フェルマーが嘘をついたとは思えない。
うっかり判ったつもりになってしまったのだと思う。
でも結果は正しかった。

将棋の結論は（数学的には）決定可能であることは明らか。
計算可能で、アルゴリズムを具体的に示すことも出来る。
つまり、>>20 は正しくない。

といっても、ルールが厳密であるという仮定は必要か。
「最後の審判」問題は解決したのだろうか。

>>28
勘で答えるとこの順

5目並べ
6x6オセロ
どうぶつしょうぎ
５五将棋
オセロ
9路盤囲碁
10x10オセロ
13路盤囲碁
本将棋
19路盤囲碁
中将棋

七路盤囲碁は
そろそろ？

七路盤囲碁は解析が終わってたと思うので、５五将棋よりは前のどこか。

コンピュータによる完全解析じゃなくて人間による（抜けがあるかもしれない）解析だったかな？
だとすると、どうぶつしょうぎと５五将棋の間に入る。

はさみ将棋が千日手になる証明は？

十六武蔵は？

チェッカーも終了済み

どうぶつしょうぎ
5目並べ
6x6オセロ
チェッカー
オセロ
５五将棋
チェス
10x10オセロ
9路盤囲碁
アリマア
13路盤囲碁
本将棋
19路盤囲碁
中将棋
じゃね

じゃんけん

勝ちに行かなければ負けないが将棋の本質ではないか？
自分が何も手を出せない局面だとしても、どれだけ相手が手得をしていても、双方手を出すことが出来ない
結局、人生の時間では永久に決着が付かないか千日手の繰り返し

昔ウォーゲームというハッカーを題材にした映画があった
核戦争のあらゆる作戦の完全シュミレーションの結果は全てに勝者がいない
三目並べで引き分けを覚えさせて核戦争を回避する結末

将棋はどちらかが徹底的に勝ちに行かなければ決着の付かないゲームではないかと思う

>>37
アリマアのゲーム木の大きさは本将棋と19路囲碁の間らしいぞ。
一局面あたりの合法手が17000以上あるっていうから
もっと難しいかと思ったが、終局までが短いんだな。
http://en.wikipedia.org/wiki/Game_complexity

>>39
将棋に固有の金銀の存在が千日手を
生み出す主要因になってるから
それはありそうな気がする
しかし金銀の屈伸運動で待機が最善
という結論になったらものすごい脱力しそうｗ

>>40
アリマアのソフトもまだ弱いんだね。
さすがに囲碁ほどじゃないけど

>>23
将棋類（チャトランガ由来のゲーム）の駒の動きは、
作為的（合理的理由に乏しい）と思われがちだが、案外そうでもない。

例えば、将棋類で一番特徴のある馬（ナイト）の動きは↓で説明がつく。
□□■□□　■□□□■　□■□■□
□□■□□　□■□■□　■□□□■
■■■■■　□□■□□　□□□□□
□□■□□　□■□■□　■□□□■
□□■□□　■□□□■　□■□■□
原始チャトランガでは2マス進むのが大駒、1マス進むのが小駒だったんだろう。

金銀の動きは↓を前3マス全部行けるようにしたもの。
□■□　■□■
■■■　□■□
□■□　■□■
そのままでは玉や大駒の動きに全くついて行けないので、改良の対象になる。
チェスではクイーンに強化され、シャンチーでは境界を設けて他の駒を弱体化させた。

持ち駒を設ける場合、駒の動きが強すぎると一瞬で終わってしまうので、
馬は特徴を残したまま弱体化させ、強い大駒は1個ずつに減らし、
歩兵は多すぎるので打ち所を制限するなどの改良が必要だろう。

つまり、チャトランガの駒はかなり合理的なものだし、将棋で行われた改良も合理的。
宇宙のどこかで将棋そっくりのゲームが指されていても不思議ではないと思う。

>>39
まったく根拠がないただの想像。
現在の対局の統計にも反してる。

>>43
駒の動きや駒の並びは作為的だよ。
必然であれば、国によっていろんな種類の将棋類のゲームが出来るはずがない。

他に必然性が無いと思うルール
チェスのポーンの動き、キャッスリング、ステイルメイト、
将棋の打ち歩詰め禁止ルール、行き所の無い駒禁止ルール、

>>44
一番大きいのを抜かしてた

> 他に必然性が無いと思うルール
持将棋の点数計算に用いる各駒の点数と、持将棋引き分けが成立する点数

裸玉vs金銀+桂で、金銀が何枚あれば詰むのか知りたい
裸玉vs金銀+香なら裸玉側に持ち歩が4枚あれば詰まないのは自明

>>30
つっこみずらいから、末端局面数を記入しろよ

10^8 どうぶつ将棋 ← 完全解析済み
10^27 6x6 オセロ ← 完全解析済み
10^60 8x8 オセロ
10^120 チェス
10^220 本将棋
10^360 19路盤囲碁

間違い指摘＆補完よろ

>>47
将棋のそれは末端局面数ではない

全局面数は将棋が１０＾８０前後、囲碁（１９路）は１０＾１７０前後

>>44
駒の配置にも必然性はあるよ。
強い駒を外側にして、効率良く使わないといけないように配置してある。

確かに、他の国は作為的にルールを追加していったが、
将棋だけは必然性を重視して進化していった感じがする。

打ち歩詰めは二歩と同じく、歩が多すぎるので打ち所を制限する意味。
後手番の不利をわずかに相殺するので、完成度を更に高めためには必然。

相入玉の点数制だけは変なルールだが、昔は普通に持将棋にしていたものだし、
いずれトライルールなど合理的な方法が取って代わるんじゃないだろうか？

>>47
末端じゃなくて分岐の数で比べなきゃ。

>>48
将棋は平均分岐８０、平均手数115なので、
末端局面数は 80^115 = 約10^220 と、松原の論文に
書いてあったと思うけど。

正しい末端局面数はいくつ？>>48

>>50
> 末端じゃなくて分岐の数で比べなきゃ。
その理由は？

ちなみに、縦型探索で完全解析を行う場合、それに要する時間は
末端局面数に比例する。

後退解析を使う場合は、処理時間・必要記憶容量は全局面数に比例する

>>51
携帯なので調べられないけど全局面数よりは少ないでしょ

>>53
全局面数の方がずっと少ないよ

全局面数は大雑把に計算すると 10^100 ぐらい。

>>53
全局面数ってのはどうやって求められてるの？

>>51
をみるかぎり10^220って数字はいい加減な見積もりでしかないと思うんだけど、

>>49の全局面数は将棋が１０＾８０前後
って数字はもう少しましな根拠があるのかな？

>>56

> >>49の全局面数は将棋が１０＾８０前後
> って数字はもう少しましな根拠があるのかな？
実際には有り得ない局面も含めて甘い計算をすると一つの駒の状態が
(先手持駒(1)+後手持駒(1)+
(配置(9*9) * 状態数(先手・後手・先手成・後手成)(4)))^駒数(40)

ほれ
まず言葉の定義のすり合わせをしとけ
それやらないでまったく違うものを同じ言葉で呼んで罵倒合戦するのがこのスレだからｗ

末端局面数　→

全局面数　→

末端（終端）局面数：
初期状態から縦型探索を行う場合、それ以上の指し手が無い（終局）状態を末端（終端）ノードと呼ぶ。
末端（終端）局面数とは末端（終端）ノードの数のことである。

将棋などのでは、手順前後で同一局面になる場合があるが、それらは別個としてカウントする。

全局面数：
初期状態からルールに従った着手で到達できるユニークな状態（局面）数。

チェス、オセロ、将棋では手順前後で同一局面になる場合が多いので、
末端局面数＞＞全局面数となる。

分岐の少ないゲームでは 末端局面数＜全局面数 となる場合もある。

で結局どっちにしろ宇宙の原子数より大きいから永遠に無理って話で

>初期状態からルールに従った着手で到達できるユニークな状態（局面）数
これは状態数と言った方が分かりやすいな。
局面というと言葉の意味が人によってまちまちだから、これを計算しておいて
「明らかに10^220より少ないだろ、せいぜい(ry」なんて得意げに言っちゃう奴が定期的に出てくる。

>>60
そこでホワイトライトですよw

>>50
そんなことを言ったら
ほとんどのアブストラクトゲームのルールが作為的じゃ無いことになるな。
「アブストラクトゲームの中では比較的ルールが作為的な方だ」
という表現なら満足？

二人完全情報ゼロ和有限確定ゲームを前提として、
言葉を定義しよう

ゲーム木：
初期状態からすべての手を考えて分岐させていって作った木
木の各状態をノードと呼ぶ

総ゲーム数：
考えられるゲームの総数
ゲーム木の末端のノード数

局面：
ゲーム木のノードで、それより下流のゲーム木がまったく同じであるようなノードを同一視したものを
局面と呼ぶ。

ゲームグラフ：
局面の、手による遷移を表わした有向グラフをゲームグラフと呼ぶ

※特に断りが無ければ、（明らかな悪手を含む）すべての手、対称形も考える

将棋の場合、

同一手番、同一盤面、同一持ち駒、の状態が現れた場合に千日手としても解析に影響は無い。

必要であれば、ルールの曖昧性解決として以下を用いる。

最後の審判問題 ===> 作意通りとする
合法手が無い場合 ===> 負け
双方連続王手 ===> 先に同一局面になった手を非合法とする（成立しないことが証明出来てる？）
持将棋 ===> コンピュータールール

多くの場合、
局面＝[手番、盤面、持ち駒] であるが、
厳密には異なる。（最後の審判のような局面や双方連続王手の場合）

>56
二歩をせずに、持ち駒が先手歩が○○枚、後手××枚、香車が……とやって、
残りの駒をばら撒いて行くと、可能な組合せは10^70を切るくらいまで減らせる。
頑張れば10^69以下には出来そう。

基本方針は、歩と香が重なったり、王が金二枚とかに王手されてたり、そういう
あり得ない局面も「少し」合法とみなして多めにカウントする。

だから、「10^70以下」みたいな上限値となる。この理由は計算が簡単なのと、
全ノードの葉、10^220に対する見積もりだから
下限は処理がかなり面倒なので、10^40以上とかくらいなら出せるけどあとはやりたくない

>>63
いや、ほとんどのチャトランガ系ゲームはかなり作為的な進化をしているよ。
でも将棋は違う。

>>66
全局面数って完全解析に関係あるの？
全ての詰みパターンをデータベースにするぐらい？

>>59
あら、なんかかぶってたのね。
>>64 の「総ゲーム数」が >>59 の「末端（終端）局面数」ですね。

将棋の総ゲーム数（末端局面数）は実は非常に多い。

[手番、盤面、持ち駒]の組み合わせが10^73程度で、
同一の[手番、盤面、持ち駒]が4回現れた時点で終局とすると、
最長 3*10^73 手程度のゲームが存在する。
1手の分岐が2だとしても、
2^(3*10^73) 程度、
つまり 10^10^72.95 程度は存在する。

同一の[手番、盤面、持ち駒]が2回現れた時点で終局としてもあまり変わらず、
10^10^72.48 くらい。

将棋の総ゲーム数が 10^220 というのは、
常識的な手数で終わる、ある程度まともなゲームに限定したもの。

>>67
> 全局面数って完全解析に関係あるの？
どうぶつ将棋のように全局面がメモリに収まるくらい少なければ、
それらを全部ハッシュテーブルに登録し、完全な後退解析を行うことができる。

チェスは全局面を記憶するのが無理なので、駒が少なくなった終盤のみを
後退解析している。

6x6 オセロは充分局面数が多く全局面を記憶できないが、
オセロは千日手が無いのでアルファベータ縦型探索で完全解析できる。

300手までの完全解析で実質の答えなんじゃないかという気がする。

>>69
双方が協力して詰むように指す「バカ詰め」というのがあるが、
双方が協力して詰まさないように指す「バカ将棋」というのがあったらそうなるわけだな。
永遠に指し続ける事はできないが、宇宙の終わりまで指す事はできそうだ。

>>71
> 300手までの完全解析で実質の答えなんじゃないかという気がする。

まず完全解析の意味を調べてから出直して下さい。

>>67
むしろ、完全解析をするうえで不必要な数字は
総ゲーム数＝末端（終端）局面数の方だと思う。

そして、それは１０の220乗なんかではなく、
>>69が見積もったようなとてつもない数字になる。

そして、総局面の方はおおざっぱに計算しても、
>>66のように10^70以下程度であることはわかる。

そして、それはルール上許される可能な全ての局面であり、
王手放置のような勝ちを目指しているのなら、絶対にあらわれない局面を
非常に多く含んでいる

実際に考慮しなければいけないのは初期状態から始まって、
勝ちを目指した場合に発生しうるすべての局面なのであって、
その数が果たして計算可能な数なのかどうかが問題なんだと思う

>>73
すまない。300手までの全幅探索と訂正する。
そのうち、ソフトの形成判断で大差の枝を狩って出た結論が完全解析の答えと同じの可能性があるんじゃないかなと。

>>76
その「同じ」だと言うことをどうやって知るのか、あるいは証明するのかが問題なんですけど。

>>77
いや、別に>>76は証明することについて話してはいないだろ。
ただ単に、>>76に書いてあるような妥協した方法で得た答えと、
真の完全解析をやって得た答えが一致しているなんてこともありそうだという、
予想を書いただけだと思う。

２ｃｈにちょっと思ったことを書いた。なんの問題もないだろ。

>>71
俺は２４で最長６２２手で詰ませたことがある。

>>78
じゃあ突っ込まれることも甘んじて受けないと

>>78
そう言う単なる個人的な予想で良いのであれば、私は今のコンピューター将棋の評価関数で
高々300手くらいの深さを読んだ結果は間違ってる可能性が高いと思いますね。

これも単なる印象による個人的予想。

>>81
個人的予想を言い合うのでいいんですよ。それしかできないから。
300手で決まらない場合は後手勝ちとかのルールに改めてもらえば
解析を夢見る人たちは少しは楽になれる。
実戦の採用手数はいくらなんだろうか。

>>82
公式対局で300手以上掛かったものが実際にあるようです。

http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1024024105

今回の竜王戦2局の羽生が▲64角のところ23香成を指せていれば+600もの先手優勢(激指六段+++)の判断だったけど、この評価間違ってたの？
探索打ち切りのためには
今後評価精度が問われる

※ヒューリスティックな評価関数で枝刈りを行うと、完全解析にはなりません※

あと、定義で大事なのは
解析にもレベルがあって
http://en.wikipedia.org/wiki/Solved_game
Strong： 全ての局面での双方の最善手順が判明する
Weak： 初期局面での双方の最善手順が判明する
Ultra-weak： 初期局面が勝ち、負け、引き分けのいずれかが判明する
の3種があり、将棋ではどれも不可能だと考えられています

Weakをあらわすのに完全解析という言葉は誤解されやすいので
勝敗解析とか別の言い方をしたほうが良いかもしれません

>>85
昔は、「完全読み」、「必勝読み」って言ってたよ。
前者が −∞、∞ をα値、β値としてアルファベータ評価開始するのに対して、
後者は -1, +1 をα値、β値として与えてた。

>>86
それぞれ「Weak」と「Ultra-weak」に対応するって事？
最善手順が判明するには同じ必勝手順のうちどれが「最善」なのかが
評価関数のパラメーターに正しく反映されてる必要があるね。

例えば勝つ側から見て最短で、負ける側から見て最長の手順であると言うような。

>>85
あーそうなのか。
ずっとweakが完全解析だと思っていた。

と言うか「完全解析」と言う用語にはこれまで定まった共通理解が無かったんだよね。
人によってStrongだったりWeakだったり、甚だしい場合Ultra-weakの意味で使ってたりするので。

これからはどの意味で使ってるのか、ハッキリさせてから議論しましょう。

>>87
ごめん、ちょっと勘違いしてた。

特定の局面で最善手を探す＞完全読み＞−∞、＋∞でアルファベータ探索
特定の局面で勝つ手を探す＞必勝読み＞-1, +1 でアルファベータ探索

上記はある局面での話なので、完全読みを探索可能な局面から順次実行していけば
最善手順が判明する。

したがって、Strong ＝ 全ての局面で完全読み、Weak ＝ 初期局面でのみ完全読み
Ultra-weak = 初期局面でのみ必勝読み

だった。

話していて気付いたのだがWeak解析するにあたって、
βカットしつつ探索する際の最長深さは見つかった最善手順の深さと同程度と考えて良いわけだよな。
最善手順がn手なのにそれを得るのに必要な探索深さがn^2とか言う事は無いよね。

>>85
勝ち、負け、引き分け
だけで判断するなら、
Weak も Ultra-weak もほとんど同じだと思うんだけど。

負ける側はすべての合法手が最善手だし、
勝つ側は各局面で勝つ手を1個選べば良い。
Ultra-weak が判明すれば判りそう。

あ、方法最善で引き分けの場合は違うような気がしてきた。

300手以上詰まなかったら後手の勝ち。
千日手ルール、持将棋ルール無し
だと引き分けが無いし、非現実的な手数になることもない。

これの初期局面での勝ち負け判別をHyper-weakとかにしようか。

>>92
ええ、だからそれは「最善」をどう定義するかによるんですよ。
今までに完全解析された「どうぶつしょうぎ」や3x3将棋の場合は「勝つ側から見て最短、負ける側から見て最長の手順」が「最善」とされています。

勝ち、負け、引き分けの結論だけで判断しましょう(手順の長さは気にしない)と言うのがUltra-weak解析。

>>94
> 勝ち、負け、引き分け
> だけで判断するなら、

>>95
そうです、定義から考えればそれは自明なんです。

300手以上詰まなかったら後手の勝ち。
千日手ルール、持将棋ルール無し

これと

300手以上詰まなかったら先手の勝ち。
千日手ルール、持将棋ルール無し

これの結果が同じなら Ultra-weakの結果はこれらの結果と同じ。
異なれば、
双方最善で引き分けか、負ける側が最長手順を選べば詰むまで300手以上かかる。

と言えるんじゃないか。

Hyper-week と Ultra-week はそれほど大きな違いは無さそう。

>>92
世の中には最善手順は分からない（計算できない）けど先手または後手の必勝を証明できるゲームがある
WikiにあるようにHexやChompというのがそれで、Ultra-weakに分類される
将棋の場合がどうなのかはわからない

�@駒をぶつけなければ、永久に勝負の付かないゲーム
これが将棋の本質

�A1マスに表現可能な配置は有限
即ち、有限数

�B解析というのは、評価
完全解析という奴は頭悪いからしらみ潰ししか考えられない
しかしそれでも評価自体完璧な精度でないといくらでも駒を後戻りしたり出来る

つまり�@がある限り堂々巡り巡り
仮に評価が完璧なら有利の段階で打ち切って終わりといえる

結局、結果引き分けの不毛な時間を将棋関係者は費やしてるだけじゃないか

>>97
120手でさえムリといわれるのに300手なんて夢のまた夢でしょう
300手と制限つけることに意味はほとんどないと思われる

>>99
駒をぶつけずに千日手を目指す事が双方に取って最善なら、つまり結論が引き分けならそうですけどね。
駒をぶつけた方から勝つ手順がもしあればそうとは限らないでしょ？

良く考えると >>91 で書いた事は探索の順序が最適化(早く結論が出る手から探索する)されていない限り、言えない気がして来た。

>>100
いやべつに300という数字に特別な意味は無いよ。
ただ単に10^10^72.48 よりずっと少なくするのが目的。

--------
[先手勝ち] を 1, [引き分け] を 0, [後手勝ち] を -1 とする。

n手以上詰まなかったら先手の勝ち。 千日手ルール、持将棋ルール無し
のルールの最善手同士の結果の数値化を A(n) とする。
※A(n) は 1, -1 のいずれかの値となる

n手以上詰まなかったら後手の勝ち。 千日手ルール、持将棋ルール無し
のルールの最善手同士の結果の数値化を B(n) とする。
※B(n) は 1, -1 のいずれかの値となる

手数制限無し、千日手ルール有り、持将棋ルール無し
これの結果を S とする。
※S は 1, 0, -1 のいずれかの値となる

A(n) ≧ B(n)、A(n) は単調非増加、B(n) は単調非減少となる。

A(n) = B(n) となるnが存在すれば、
S = [この時のA(n)の値] となり、
A(n) = B(n) となるn が存在しない、つまりすべてのnに対して A(n)=1, B(n)=-1 であれば、
S = 0 となる。

>>99
動物将棋の完全解析は終わり、後手必勝が判明したわけだが、
それについてどう思う？

>>103
いや、n手以内に先手が勝つ、負ける、引き分けの3つの結果しかないわけだから、
そんな長い証明をしなくても自明だろ

また、その証明は任意のｎについて成り立つのだから、
単調増加などと数列の概念を持ち出す意味はまるでない

>>105
なにも証明してないけど。
長い手数を調べなくても結果が分かるという説明をしただけ。

>>103-105
深さn手までの全幅探索で得られる結論は先手勝ち、後手勝ち、引き分け、それに加えて不明。
結論が先手勝ちか後手勝ちならn手までに結果が得られるのは分かるが、
深さn手以内の探索で結論が千日手だと分かるのはどういう時だろう？

もしかしたら将棋の総ゲーム数が得られる深さまで探索しない限り、
結果が「千日手」だと言う結論は出せないのかな？

何かそんな気がして来た。

少なくとも、
4回同一の[手番、盤面、持ち駒]まで調べなくても
2回同一の[手番、盤面、持ち駒]までの検索で十分なことは分かる。

n を増やしていって勝負がつかなければ千日手の可能性が増える
ということは言えると思う。
たとえば、n=10^10 の時に結論が出なければ、おそらく結論は引き分けだろう
と予想することは出来る。
あくまで予想だが。

>>107

まず、>>103はある局面から深さｎの探索をすると言った話ではなく、
開始局面からｎ手以内に勝敗が決まらない場合を引き分けと定義しているから、
>>105ではその前提で書いたんだ。つまり、不明のことを持って引きわけとしている。

>深さn手以内の探索で結論が千日手だと分かるのはどういう時だろう？

双方連続王手の千日手は存在しないのか、しらなかった。

あ、そうか。
探索してるうちにまだ結論が確定して居ないすべての枝の末端から根の方を見て、
同一局面が二回以上現れていれば結論は千日手として良いわけか。

>>110
私は「引き分け」と「不明」は飽くまで別として考えていたよ。

http://www.math.nara-wu.ac.jp/personal/shinoda/legal.pdf
文字化けで全然読めないけど将棋の合法局面数の見積もりが１０＾６８〜１０＾６９　であるっていう論文

全く文字化けとかしてない

>>111
ええと、あなたではなく>>103の人の話にのったということです
>>92、>>97を見ると分かると思うんだけど、
この人は300手以内に詰みが無い場合を引き分けときちんと定義して話を進めていたので

命題. 将棋における最大分岐数は593である.　
http://www.math.nara-wu.ac.jp/personal/shinoda/bunki.html

篠田さんってのは清水女流にレクチャーしていた数学者で元アマ竜王

>>114
ええ、それは分かってるつもりなんですけど、私は私で何の仮定も置かずに厳密に考えたらどうなるのか？
を考察してたと言うわけです。

書いてる事が紛らわしくて申し訳ない。

>>112
昔局面数を計算したことがあった。
詰みで終局ではなく、王を取った時点で終局として、王を取る前までの局面を数えるのであれば
それほど難しくは無くて、70桁近い値を正確に求めた。
つまり、>>112 の論文でいうA, B, C, D までを考慮し、H, I, J, K を考慮しない場合の正確な数。

>>116
何の限定もないとして、
結果を調べるアルゴリズムを考えてみよう。
>>65 のような曖昧性は当然排除出来ると仮定して。

計算時間を考慮しないなら簡単で、
単純にminmax法で良い。
メモリ使用量も非常に少なくて済む。

メモリが無限にあって、多少アルゴリズムを気にする場合、
[手番、盤面、持ち駒] によるグラフを作っていくことになるであろう。
ここで、局面 と [手番、盤面、持ち駒] の違いをどうするか
という問題にぶちあたる。
双方連続王手の千日手となる状態が存在しないそうなので、
あとは最後の審判のみが違いということになる。
最後の審判の結果次第ではこれも気にしなくて良いのだが....

[手番、盤面、持ち駒] を点にした有向グラフは,
点の数が10^70以下、
矢印の数は10^73以下、
なので、
グラフ作成の計算オーダーも大まかにはそのくらい。

全合法局面数１０＾６８〜１０＾６９のうち激指、GPS、ボナンザ、YSSがほぼ互角（例えば評価値±２００以内とか）って
判断する局面数はどのくらいだろうか？

>>118
深さ優先探索のMinMax法でも、必要なメモリ使用量が本当に非常に少なくて済むだろうか？
もしかしたら「後退解析」と同様のすべての局面[手番、盤面、持ち駒]数と同程度のオーダーまで
深い探索をする必要があるでは無いか？と言うのが
>>108 >>111で書いた事の出発点なんです。

で、何か深そうな気がして来た（もしも結論が千日手の場合）と言うわけです。

>>120
それはわからないけれど、その中にも>>85の言うweakの解析をするうえで
不必要な局面はまだ相当含まれるだろうとは思う。
たとえば、開始局面から歩を全て取り除き持ち駒としたような局面は
互角と評価されるだろうが、おそらくweakの解析をする場合に必要ないと思う。

>>119 の続き

グラフが出来たら、
末端から順に結論を書いて矢印を消していく。
負けへ繋がる点への矢印は消す。
ループは、勝ちへ繋がる矢印がある場合はその点の結果は勝ちとしてループを切る。
ここまでは簡単。

この後、分岐の無いループを解決していくと、
あとは複雑に分岐したループが残る。
これをどうしようか。

>>121
あ、ごめん。適当に書いちゃった。
単純minmax法だと、最長手数分のメモリが必要ですね。

[手番、盤面、持ち駒] を点にした有向グラフ
の方が少なくて済みそう。

>>120
ほぼ互角と判断する局面数を数える意味はないだろ。
持ち時間5時間以上のタイトル戦においても評価値が一手で1000以上落ちるような
手をトッププロが指すのだから。
完全解析において解析対象となる局面は合法手で構成されるすべての局面だよ。

>>122
＞開始局面から歩を全て取り除き持ち駒としたような局面
人間の感覚だと先手必勝だけど、
「打ち歩詰め」が後手の不利を少し緩和できるというのがはっきり分かるね。

>「打ち歩詰め」が後手の不利を少し緩和できるというのがはっきり分かるね。
ぜんぜん分かりません。
解説お願い。

末端スタート逆算状楽観的定跡解析定跡研究法

使うコンピュータ将棋ソフトウェア

AI将棋17（暗黒面に落ちた山下さんのボナンザメソッド手法YSS）で
幅100手、深さ15手（30手）で、検討。
読み抜けがないのでこれが最上。

+500で勝ちと判定し巻き戻し。
-2000で負けと判定し巻き戻し。

将棋の[手番、盤面、持ち駒]の組み合わせは 約 10^70 通り。
将棋の総ゲーム数は 10^10^70 くらい

囲碁の[手番、盤面]の組み合わせは約 2*3^361≒10^172 通り。
手数は中国ルールでも最長で10^172手位のゲームがあることになる。
それぞれ分岐が100位だとすると、
総ゲーム数は 100^10^172≒10^10^172 くらい

13路盤だと[手番、盤面]の組み合わせは約10^81
総ゲーム数は約10^10^81
これでも将棋よりずいぶんと多い。

マジレスしようかとも思ったけど、
そういえばID:Xkp3fyteみたいな知恵遅れを隔離するスレだったな
まぁどんどんやってくれ

>>130
いや、そう言わず、マジレスしてみろ。
具体的にどのレスをどう馬鹿にしてみたいのか興味ある。

石が死ななきゃ手が単調に減少していく、
多コウでもなきゃループはしない。たとえ大石死んでも進行はしていく、
初期局面ではもっと打てる場所が一杯ある。

等々じゃまいか

すべての合法手を含む総ゲーム数だから、
だんだんと石が増えていくなんて仮定は出来ない。

http://www.nicovideo.jp/watch/sm222407
たとえばこんな糞ゲームもカウントする。

> 初期局面ではもっと打てる場所が一杯ある。
最大分岐は初手の362
（おおざっぱな概算だからこの数字にこだわってもしょうがないと思うけど）

上限を調べるという意味では、
[手番、盤面] の組み合わせ ＜ 2*3^361
最大手数 < 2*3^361
最大分岐 ≦ 362
総ゲーム数 ＜ 362^(2*3^361) ＜ 10^10^172.95 ＜ 10^10^173

※超コウルール有りの中国ルールでの計算
※日本ルールだと無限に続けることが出来るので、総ゲーム数は無限

>>133
あまりにも上から抑え過ぎていて数字に意味が少ないとは思うけど、
主張は間違っていない気がする。
ただ、言葉遣いとして、上限というのは数学用語としては不適切で、
上界を一つ示したという方が正しいと思う。

で、>>130はこれについてどう思うんだ？
具体的にどこがおかしいとも指摘せず、誹謗中傷することしかできないならもう書き込まないでくれよ。
おおかた、主張を正しく理解することもできずに馬鹿にしているんだろうけど。

＞100^10^172≒10^10^172 くらい
を見て、反射的に間違いだと思ったに一票いれとこう

比較的実際の値に近い下界を探すのは比較的難しい。

19路盤囲碁の盤面の組み合わせは、
2*3^361 のに対して、黒の存在出来ない石をすべて取り除いた盤面にカウントするとした場合、
最大2^181回重複して数える盤面が出てくる。
よって、
『[手番、盤面]の組み合わせ』 ＞ 2*3^361 / 2^181 ＞ 10^118
となる。

つまり、
10^118 ＜ 『[手番、盤面]の組み合わせ』 ＜ 10^173

総ゲーム数はもっと難しい。
最長手数の1/100の手数までは、100手に1手は終局とならない手が2種類以上存在すると仮定すると、
総ゲーム数 ＞ 2^(10^118/100/100) ＞ 10^10^113

つまり、
10^10^113 ＜ 総ゲーム数 ＜ 10^10^173

将棋の >>112 の見積もりに比べて範囲がおおざっぱすぎる。
もっと狭い範囲に絞れないものか。

将棋も囲碁も総局面数の方が末端ノード数より圧倒的に少ないのが明らかなのだから、
完全解析がもし可能なら総局面数に依存する方法を取るしかないだろう。
末端ノード数の概算値を求めることに意味はないと思う。

天文学的に巨大なDBを用意して現れた局面ハッシュを全部保存照合すれば
総局面数でどうにかなるかもね

「充分なメモリと探索速度があれば、殆どの枝は手順前後と千日手で
合流／打ち切り可能となるから結局は10^70だけでいい」

ということかな。
逆に言うと10^70分が確保出来ないと手順前後と千日手の判断がつかずに
10^220（以上）の複雑さと同等の困難な問題になってしまう？

局面数5*10^20のチェッカーも解かれたけど
それも全ての局面について勝敗を求めたりしないで
終盤データベースを利用しながらも、普通にゲーム木探索の方法でだった

先読みである点数以下の手は負けとみなして
それ以外を勝敗つくまで探索して、現実的な解を得られるかどうかってところじゃないかな

負けとみなす点数を段階的に下げていって、実際の負けの点数になれば
真の解になるという

>>139
十分な(いくらでも大きな)メモリー容量があれば後退解析(Retrograde Analysis)と言う方法が使えるので
、探索回数もほぼそのオーダーで済ませられると思われます。
その代わり10^70と言うそれこそ天文学的数字のメモリーが必要なわけですが。

それが確保できそうに無いと言う前提で、もっと少ないメモリー容量で済ませられないか？と考えると
ゲーム木をβカットしつつ探索する事を考えて 10^220の√ で10^110回のオーダーを探索する必要が出て来るわけです(Weak解析の場合)
その場合も縦型探索の深さ分はメモリー上に持ってないとならないので、
最小限、どの程度のメモリー容量があれば済むのか良く分かって無いわけですが。

>>142
βカットは完全解析でもなんでもない。
不完全な推定による解析でいいなら後退解析に必要な局面数も１０＾７０などではなく
もっとはるかに減らせるだろう。

>>143
βカットは推定じゃ無いですよ(理論的保証あり)
StrongにはならないだけでWeak解析には使えます。

>>144
ああ失礼。そっちは完全解析の話だったのね。どっちにしろ１０＾１１０じゃお話にならないね。
内容としては>>141に対してのレス。

いや141は実際的にも意味がある手法
最良優先といって段階的に閾値を下げていって
その時点での準最適解を元に探索していくと、大幅に探索局面を減らせるだけでなく
どこで打ち切っても一応意味のある手順が求められる

最後には真の解が得られるって書いてあるでしょ

>142

思考実験として、
「最善を尽くせば先手短手数で勝てるが、一手間違えれば延々と均衡のとれた戦いが続く」
ような局面からはじまる将棋類ゲームの解析というのを考える事が出来るから、結局は
初期局面の性質依存だろうしねぇ

null moveでカットの候補になるような「どうしようもない局面」のultlaweak解析が高速に出来ると、
相当絞り込めるんだろうけど

>>146
その方法に意味がないというのではないが、その手法を取るなら末端ノード数の概算値は
まったく関係ないね。

まあ完全解析用スレみたいなもんだからなぁ
>1的には特定定跡の終盤解析ネタも入ってるけど

研究支援としては、局面に対する詰み探索と、全候補手の勝・敗・分け・不明の一覧表示が欲しいな
ありえなそうな手が新手になったりする訳で、ホントに駄目な手をイチイチ調べるのがメンドイだろうから

>>137
だね。

そして、>>85の定義におけるweakまたはultra-weakに限って議論を進めるならば
（strongが不可能なのは議論の余地がないと思うので）
総局面１０＾６８〜１０＾６９のうちのほとんどが必要ない。
では、weakまたはultra-weakの解析をする上で必要な計算資源はどれくらいなのか？
どこまで減らすことが可能なのか？
そういった内容に限って話した方が有意義だと思う。

将棋の総局面数や総末端ノード数の大きさについて話すのは
コンピュータでの解析の可能性について議論する上で意味がないと思う。
（それらを全て計算するのが不可能なのはわかりきっているから）

strongが「現在想定される計算モデルでは、現実的な計算資源で不可能だ」と
断言するのは違うと思うよ
「可能かもしれないし、不可能かもしれない」としかまだ言えない
不可能であるというためには、「絶対に必要な」計算量を証明付きで出さないといけないが、
そんな研究はまだない

今の段階で言えることは、せいぜい一般化将棋が、将棋盤のサイズnに対して、
EXPTIME完全だということぐらいだろ
それだけでは、不可能だとは断言できない

>>151
>>85の定義で
Strong： 全ての局面での双方の最善手順が判明する

なのだから、>>112の見積もりにより１０＾６８〜１０＾６９の各局面に
おける最善手を示す計算をしなければならない。
それがどれくらいになるかはわからないが、仮に（ありえないが）各局面につき1ビットだとしても
コンピュータに扱える計算量ではないことは明らか。
これで議論終了だと思うけど、ちがうのか？

>>153
85の定義では説明が省かれているが、答えを全て予め計算する必要はないし、
記憶しておく必要もない
入力が与えられたら、その場で逐次計算できればいい

(ただ、確かに将棋の場合別の問題があり、千日手の問題があるため、
入力の与え方にもブレイクスルーがなければstrongの計算は不可能）

>>154
たしかに、その通りだ。
大幅に勘違いしていたことに気付いた。

同じ勘違いをしている人もいると思うので、非常に簡単でつまらない例を用いて説明したい。

次のような二人対戦のカードゲームを考える。
各々に1〜１００の数字の書かれたカードを配る。
毎試合、各自手札からカードを一つだけ選び出し合い、
大きな数字の書かれたカードを出した方の勝利とする。使ったカードは二度と使えない。
第ｎ試合目に勝利した方に１０＾（−ｎ）の点数が入るとする。
これを第1試合から第100試合まで行い合計点数が高い方の勝利とする。

このようなゲームを考えた場合、総ゲーム数は（１００！）＾２
総局面数は１〜１００試合目の持ち札の組み合わせのパターンの総数なので
Σ（n=1~100) (100Cn)^2 　＞　 (100C50)^2 　　>　 (2^50)^2　=　2＾100　＞　10＾30

と、総ゲーム数、総局面数ともに非常に多いが、

これのultra-weakは引き分け
weakは両者１００から順に大きいカードを出す手順
strongは残った手札を大きい方から順に出すことであり、
strongを行うに当たり、コンピュータがすべきことは手札を大きい方から順にソートすることのみで
どんな低スペックのパソコンでも瞬時に行える計算になる。

局面をすべて列挙して、
局面間の遷移も列挙する。
ここまでのアルゴリズムは簡単。

この遷移図の末端から後退解析をしてゲームスタート時の局面にたどりつければ良いが、
多くの局面からなる複雑なループが残った場合のアルゴリズムはどうすれば良い？
ループは連続王手のループも含み、連続王手でないループも含み、
連続王手であるループ中の打ち歩による逆王手も含むとする。

また、
手数を含めての最善を求める場合や、
最後の審判のような手が現れた場合、
[手番、盤面、持ち駒]に対して最善手や結果が決まるのではなく、
[手番、盤面、持ち駒]の状態になるまでに、どんな[手番、盤面、持ち駒]が何回現れたか
も含めたものに対して最善手や結果が決まるので、
過去に現れた[手番、盤面、持ち駒]をも含めて列挙しないといけない。
こうなると、計算オーダーが一気に上がる。

>>157
>局面をすべて列挙して、
>局面間の遷移も列挙する。
>ここまでのアルゴリズムは簡単。

アルゴリズムが簡単でも、すでにその時点で実行不可能でしょ？
そのような力づくの方法を用いずに最善手を判断する方法が
存在するかどうかが問題なのだと思う。

ああ、でも、力づくでも何でもいいから完全解析を行うアルゴリズムと
それに必要な計算量のオーダーの対応を把握するのは価値があるかも。

この方法だと、これくらい無理、この工夫をするとこの程度ましになる。
そういうのを把握しながら可能性を探っていくとよさそう。

基準となる簡単で間違いのないオーダーのデカイ手法を最初に挙げるのは大事

>>157
連続王手のループは王手を掛けてる方が手を変えないと負けになるので結論を出せるはず。
そのループは王手を掛けてる方が負け。

王手が絡まずに単にループしてるなら、そのループに飛び込む場合の結論は千日手で引き分け。

連続王手のループ中の打ち歩による逆王手などの「最後の審判」問題的なのは分からない。
はっきりしないのはルールに不備があるからで解析手法のせいでは無いと思う。

互いに王手を繰り返す、連続逆王手のループは存在しないと言われている。これがもし存在すると、確かに後退解析では決定不能になってしまう。
(どこからループに飛び込んだのかの経緯によって勝ち負けが決まるので)

>161
連続逆王手はほとんど不可能なんだけど、証明がめんどくさすぎて……
「連続逆王手が可能な将棋ライクゲーム」が簡単につくれる以上、
「将棋のルールでは不可」という、非常に筋悪な展開にならざるをえない

一応、玉が動かせない、歩、桂、銀、金、と、杏、圭、全で王手出来ないなど部分的な制約は解っていて、
飛二枚か飛＋香で角、銀が行き来して空き王手を繰り返すパターンと、角二枚で飛車が行き来する
パターンだけが残る。

ここまで来たら、双玉の位置を全パターン舐めつくせば終わりそうだけど、証明方法としては余りにも芸が無いしな……

あり？ 例え連続逆王手による千日手ループが存在したとしても、
そこに先手後手のどちらから飛び込んだかによって
その枝(指し手)の勝ち負けは決定可能な気もして来た。

後退解析で決定不能になるのはやっぱりルールに不備がある
（実際の対局でも勝ち負けが決まらない）場合だけなのかな？

良く分からなくなって来たｗ

>>161
「結論を出せるはず」じゃなくて
具体的なアルゴリズムは？
その時の計算量の概算は？

たとえば、末端を後方から順番に処理していって末端をすべて無くした後、
結論が出ないノードが非常に多く（たとえば10^65個くらい）残ったとする。
残ったものは、末端となるノードが存在せず、多くの分岐が存在する複雑なループとなっている。
分岐の仕方によっては連続王手や打ち歩による逆王手を含んでいるものもある。
どのノードからどのように解決していきますか？その時に計算量は？
単に「後退解析を使う」という言葉だけで簡単に済ませられるものではない。

> はっきりしないのはルールに不備があるからで解析手法のせいでは無いと思う。
「最後の審判」の問題を理解していない？
「最後の審判」はルールの解釈が２通り存在する。
「最後の審判」の問題の局面で、打ち歩が許されるという解釈と許されないという解釈。
ここで、打ち歩が許されるという解釈のルールである場合には、
ある条件を加えれば[手番、盤面、持ち駒]に対して最善手が決まるので比較的簡単であるが、
打ち歩が許されないという解釈のルールである場合には、
[手番、盤面、持ち駒]に対して最善手が決まらない。
（連続王手の繰り返しのどこからスタートしたかで打ち歩が許されるか許されないかが変わる為）

「最後の審判」の問題の局面で打ち歩が許されるという解釈の場合で
先手必勝、後手必勝、引き分けを解明するようなアルゴリズムの中で
私が考えているものを説明する。

0. [手番、盤面、持ち駒]を局面とする
1. 局面をノードとするゲームグラフを作成する
2. 末端となる局面を選び、[勝ち][負け][引き分け]のマークを付ける
3. 2. を繰り返し、末端となる局面が無くなるようにする
4. ノードを以下で定める同値類に分ける (計算オーダー 不明)
        ノードAからノードBへのルート、ノードBからノードAへのルートいずれも存在する場合に
        A=B とするような同値関係による同値類
5. 同値類をノードとするゲームグラフを作成する
    ※同値類の定義から、3. のゲームグラフにはループが存在しない
6. 4. のグラフの末端となる同値類を1個選ぶ
7. 5. で選んだ同値類の中の局面の中で、[勝ち]の局面に繋がるパスが存在する局面に[勝ち]のマークを付け、それ以外のパスを消す (計算オーダーn)
8. 4. の中の局面に対して2.〜7.を再び行い、4. で選んだ同値類の中に[勝ち]に繋がるパスが存在する局面が存在しないようにする
9. 4. の中の局面に対し、先手がどのようなパスを選んでも、
    先手が連続王手のループとなるか先手負けとなるような局面を探し、後手勝ちのマークを付ける
10. 4. の中の局面に対し、後手がどのようなパスを選んでも、
    後手が連続王手のループとなるか先手負けとなるような局面を探し、先手勝ちのマークを付ける
    ※
11. 4. の中のマークがついていない局面に対して引き分けのマークを付ける
12. 6. に戻る

よく知らないけど将棋よりもっと簡単なゲームで自分の考えを実証してみたら。

3. 9. 10. の具体的アルゴリズムは不明。
よって計算オーダーも不明。

それ以外の項目は、総局面数をnとした時に、計算オーダーは n 〜 n log n に出来る。

3. 9. 10. じゃなくて 4. 9. 10. だった。

9. 10. は一応計算オーダーnに出来るアルゴリズムがあるが、面倒なので細かく説明しない。

残るは 4. の具体的アルゴリズムだけ。

3. までですべて解決してしまうだろうという楽観論なら
4. 以降は全く考える必要が無いのだが。

>>165
複雑なループの場合、まず連続王手のループを塗りつぶします。
ここから王手をかけてる方からの脱出路が無い場合、つまりこのループが孤立している場合には王手を掛けてる側の負け。
(元々、互いにそれ以外のパスを選ぶと負けになるのでループが出来上がった)

連続王手のループから他へ（連続王手では無いただのループへ）の脱出路がある場合には
連続王手にならないループへ逸れる事ができるので、全体が単なる千日手引き分けのループになります。
一方からの連続王手のループが逆側からの連続王手のループとくっついている場合には
結局、連続逆王手のループが出来上がるので良く分からない(そんなループがあり得るのかどうかも)

結局、話を複雑にしてるのは最後の審判問題と連続逆王手による千日手ループが起き得るのか得ないのか？
だと思いますよ。

現在までに実戦で出現していないような超レアケースを前提に思考停止したって
しょうがないだろう。そんなもんは解析者が適当にルールを決めて解析すりゃいいんだよ。
細かいルールなんて時代や国、場合によっては大会によっても変わるんだから。

>>166
参照の数字が間違っているような気がするんだけど、あってる？

5. 同値類をノードとするゲームグラフを作成する
　※同値類の定義から、3. のゲームグラフにはループが存在しない

は、３ではなく５のゲームグラフだと思うんだけど。
３のゲームグラフと言った場合、何を指しているのかがはっきりしないし、
４の同値類の定義がまるで関係してこない。

その他いろいろ納得いかないから、書きたい内容と書いている内容が一致していることを
確認して欲しい。

>>170
連続王手のループから抜けるパスを選んだ時に勝ちか負けかが分からないと
そのループに入っても連続王手側が負けかどうかもわからないので、
結局 >>166 の 4. の作業が必要な気がするんだけど、
必要無いの？

>>171
別に思考停止してないと思うけど。

>>172
5. 同値類をノードとするゲームグラフを作成する
　※同値類の定義から、5. のゲームグラフにはループが存在しない
こうでした。

あと、7. 以降の4. 5. へのリンク はすべて 6. へのリンクの間違いです。

書いたあと番号をずらしたので間違っちゃいました。

4. が肝で、4. 以外はわりと当たり前かな？と思います。
1.〜8. の準備はすべて 9. 10. 11. のアルゴリズムを簡単にするためのものです。

>>17
将棋がまさにそれですね。

>>30
本将棋＞自由布石囲碁＞チェス＞オセロ

なんか難しく考えすぎてたみたい。

末端をすべて判別し終わって、
ループしか残って無い場合、
勝負がつくのは連続王手のループしかない。

勝ちか負けの場合は必ず
「連続王手を回避するには、既に負けだと分かっているノードに行くしかない」
というようなループが存在するはず。
そこから処理をすればいい。
そのようなループが存在しなくなっても結論が出ていなければ、千日手による引き分け。

双方連続王手のループは存在しないらしいので、
残る問題は、最後の審判の問題となる局面で打ち歩が許されないというルールの場合のみ。

>>43
本来の将棋は飛車角なしでスタート。
↓
複雑化のため大型化。
↓
大型化にともなってコマの強力か多様化。
↓
本来の将棋でコマの再利用の大発明。
↓
本来の将棋＋コマの再利用＋飛車角
＝
本将棋

＝世界で最も複雑なチャトランガの子。

>>175
>末端をすべて判別し終わって、

これは>>166のどの場面のことをいってるの？
３？８？

>>175
分かってくれたみたいで嬉しいです。

>>177
>>175さんでは無いですけど、先手玉か後手玉が詰められた本当の末端局面から一手ずつ遡って
先手勝ち、あるいは後手勝ちが判定できるすべての局面にラベル付けし終わった状態を指してるのだと思います。

そうなった後でもまだラベル付けされていない局面とは結局、最善を選ぶと
その指し手のパスがループして戻ってくるためにラベル付けできない局面の集合です。

すなわち、千日手のループか連続王手の千日手のループだと言う事になります（連続逆王手の千日手が存在しない場合）

>>179
その理屈はわかります。
ただ、それをそのまま実行する方法は、
>>160のいう簡単で間違いのないオーダーのデカイ手法として、
一つの出発点にはなっているかもしれないけれど、
本当の末端局面を網羅する段階ですでに実行不可能なような気がします。

この方法をとるとしたばあい、似たような末端局面を一つのグループにまとめて考える
ような工夫をすることによって、考慮すべき末端局面の数を減らすことが重要だと思います。

>>166のアイデアにはそのあたりの工夫が含まれているような気がしたので、
>>175の末端を全て判別し終わったという場合として、
どの操作をし終えた場面を指しているのかを確かめたかったわけです。

おそらく、>>166の8の操作を終えた場面のことを意図しているとは思っていますが。

>>180
その辺りは>>175さんに聞いてみないと本当のところは分かりませんね。
また、末端局面をすべて洗いだす段階で、
今のコンピューターのメモリー容量を軽く超えてしまいそうだと言う事にも同意します。

>>177
>末端をすべて判別し終わって、
これは、>>166 の 3. です。

4. のアイデアは、複雑なループを分解するのには役立ってますが、
8. 9. 10. に対して必須では無いようでした。

先手必勝、もしくは後手必勝の場合は、3. の段階で解析終了し、
双方最善で引き分けとなる場合、
4. で初期盤面を含む大きなループと、双方入玉した状態の大きなループと、その他の細かいループ多数
に分かれるのではないかと個人的には思っています。

> 本当の末端局面を網羅する段階ですでに実行不可能なような気がします。
実現性を考えれば、1. の段階で無理です。計算時間もメモリ容量も。
実際に解析できる可能性があるのは、短手数での先手必勝もしくは後手必勝の戦略が存在する場合のみと思います。

> この方法をとるとしたばあい、似たような末端局面を一つのグループにまとめて考える
> ような工夫をすることによって、考慮すべき末端局面の数を減らすことが重要だと思います。
左右を反対にした局面や、先手後手を入れ替えた局面なら同一視出来るでしょうが、
それ以外は全く想像がつきません。

私にとってひとつ気がかりなのは >>166で言う 1. 2. 3.のプロセスを完了するための処理量(探索量)が、
必ずしも全局面数Nの定数倍で済まないような気がする事です。

ある末端に近い局面の結論を出すために実はそこから遥かに遡ったところにある局面の結論が必要
なんて事がもしあり得るとすると、探索量はNでは無く、N^2に比例すると言うような事もあり得るような。

そうなると必ずしも後退解析が処理量的にゲーム木を展開する方法より有利とは言えなくなってしまいます。

>>166

四四将棋でプログラム作って試せ

動物将棋でもいいぞ

>>182
よくわからなくなりました。

>>175の
>ループしか残って無いというのは何を指すのでしょうか？
>>166の3の段階では末端の局面の勝敗の判定しかしてないので、
何も除外されてないと思うのですが。

また、例えば必至の場合は勝負はついているわけですが、

>>175
>勝ちか負けの場合は必ず
>「連続王手を回避するには、既に負けだと分かっているノードに行くしかない」
>というようなループが存在するはず。

これには必至の場合が含まれるとは思いますが、

>勝負がつくのは連続王手のループしかない。

これには当然含まれません。

>>166の２が勝敗を判定し、そのノードはグラフから除外し、
その直前のノードをあらたに末端とみなし勝敗を判定するというようなことなら
話はわかりますが、そうならそうと書いて欲しいと思います。

>>183
1. 2. 3. の計算オーダーはNにすることが出来ます。

--- 1. ---
まず、局面 <===> 整数値 となる1:1対応を考えます。

こうすると、任意の局面に対する記憶領域へのアクセスを定数時間に出来ます。
1:1対応の出来が良い程、使用メモリを減らすことが出来ます。

A. 初期局面をまずキューに入れます。
B. キューから局面を取りだし、
C. マークを付け、
D. 1手で進める局面に対して相互リンクを張り、
E. リンクを張った、マークのついてない局面すべてをキューに入れます。
F. B.〜E. を繰り返し、キューが空になれば、ゲームグラフ作成完了

1個の局面は1回しかキューに入らず、
1手で進める局面は高々定数なので、(最大593?)
1. の計算オーダーはNということになります。

--- 2. 3. ---
A. すべての局面に対し、1手で遷移できる局面数を[未解決リンク先数]として書き込みます
B. [未解決リンク先数]が0のものをすべてキューに入れます
C. キューから局面を取りだし、
D. [先手勝ち][後手勝ち]の結論を書き、
E. C.の局面に1手で行ける局面の[未解決リンク先数]を1減算し、
F. E. が0になった局面すべてキューにいれます。
G. C.〜F.を繰り返せば2. 3. が完了します。

1個の局面は1回しかキューに入らないので、
2. 3.の計算オーダーはNということになります。

>>187
なるほど、やはり>>166の2，3において、

>E. C.の局面に1手で行ける局面の[未解決リンク先数]を1減算し、
>F. E. が0になった局面すべてキューにいれます。

この操作をするのですね。それなら話はわかります。
また、

>B. [未解決リンク先数]が0のものをすべてキューに入れます

とありますが、勝敗の判定を一度もしていない初期の段階で
[未解決リンク先数]が0　という場合は
玉がとられてしまって、勝負が決している場合しかないと思うのですが、
局面として玉がとられた場合も含んでいるということでよろしいですか？

1手先に[勝ち]が結論であるノードが1個でもあれば、そのノードは[勝ち]ですので、
これも全部結論を書きこんじゃいます。
これが 7. 8. です。
2. 3. と同時に出来ますね。

つまり、>>187 の --- 2. 3. --- の F. と G. の間に以下を足せば良いです。
C. の局面の結論が C. の手番側の負けである場合、C. に1手で行ける局面をすべてキューに入れます

>>188
> [未解決リンク先数]が0　という場合は
> 玉がとられてしまって、勝負が決している場合しかないと思うのですが、
一応、現在の将棋のルールを正しくゲームグラフに示すのであれば、
[自分の王が詰んだら負け] なので、詰みの局面が初期の末端になると思います。
王手を（回避できるのに）回避しない手は反則なので、遷移図には書きません。
もちろん、王が取られる局面までをゲームグラフに示しても結果はまったく変わりません。

王手がかかっていなくても合法手が存在しなければ末端になります。
この辺はルールで定められていませんので、適当にルールを決めて結果を書きます。

>>185
> >>166の3の段階では末端の局面の勝敗の判定しかしてないので、
> 何も除外されてないと思うのですが。

>>187 >>189 の処理が終わった段階で、まだ初期局面での結論が得られていないとした場合、
結論が得られていないノードのみからなる部分グラフは末端が存在せず、
その部分グラフから出る手は負けになる手になってるはずです。
この意味で「ループしか残って無い」と書きました。

>>186
すべてを正確に書くと非常に時間がかかるので、けっこう適当に記述してます。
適当に補ってください。

>>191

>　>>187 >>189 の処理が終わった段階で、まだ初期局面での結論が得られていないとした場合、
>　結論が得られていないノードのみからなる部分グラフは末端が存在せず、
>　その部分グラフから出る手は負けになる手になってるはずです。
>　この意味で「ループしか残って無い」と書きました。

そういうことならばわかります。

>>187
納得し、かつ安心しました。

どこかですべての未確定局面の[未解決リンク先数]が1以上になって
そこから先に進まなくなる事があるのでは無いか？と少し心配しましたが
それが起きるとしたら未解決リンクがすべて相互リンクになってしまった、
つまり、残りがすべてループのパスである場合だけですね。

>>191
> すべてを正確に書くと

すべてを正確に書けと言っている訳ではない。

ポイントは押さえて書けと言っている。

どうぶつしょうぎのルールを一部改定、連続王手の千日手は負けなバリアントルールを「動物将棋」として、
これで試してみてはどうか。

>>195
ここを見ると「どうぶつしょうぎ」も解析するためにはメモリーを最大13GByteも使うらしいんだよね。

http://media.itc.u-tokyo.ac.jp/ktanaka/dobutsushogi/20090626.pptx.pdf

これを個人が趣味のパソコンで解析するにはちょっと荷が重そう。
メモリーを節約する手法を考え出せば何とかなるのかも知れないけど。

最初はこれとか、
http://d.hatena.ne.jp/nishiohirokazu/touch/20090601/1243860840

昔、Webに出ていた3x3のSuper Mini Shogiなどで後退解析を試してみるのが良さそうな気がする。

いきなり将棋の完全解析を考えるより
動物将棋を以下に少ない計算資源で解析するかを
競った方が将棋の完全解析につながるかもね

13GBぐらい、いまや、どうってことないな

13Gというのはちょっと困るんだな。今、普通にメモリ沢山乗せると12Gがキリの良いとこだから。
まあ頑張って24G積めばオンメモリーか。

俺のプログラムはどうぶつしょうぎをdf-pnで後手勝ちと結論付けた。
Ultra-weak解決だけれどね。
メモリは2G使用。所要時間は2000秒程。
多分1Gあれば時間は長くなっても解けると思う。

>>199
4GBx3追加して18GBにすりゃいじゃん

そのへんのPCであっさり解析されたんじゃぁ、ありがたみがないなぁ。
もっとルール複雑にしたほうがよさそうだね。
らいおんは、ほかのどうぶつを食べちゃって、も持ち駒としてう打てなくするとか。。。。って、これじゃさらに簡単になるだけか。。。

>>202
いや、複雑になるよ。
通常のどうぶつしょうぎは駒の数が常に8枚なのに対し
>>202どうぶつしょうぎは駒の数が7以下の場合があるので、場合の数が増える。

らいおんできりんやぞうを食べた場合、通常のどうぶつしょうぎでは圧倒的に有利になるので
勝ちと結論が出るまでの計算量が少なくなる場合が多いが
>>202どうぶつしょうぎは有利さの度合いが小さくなるので、勝ちと結論が出るまでの計算量が多くなる。

>>203
実際にカウントしないで適当なこと言わない方が良いと思うよ。

>>202
うまくルールを調整すれば、双方最善手を指した時の結論が千日手引き分けになって
ちっとやそっとで解析できないものに…ならないだろうな。

局面数を今より爆発的に増やせるわけでは無いから。

まあ、当分は解析できないような規模のミニ将棋なら「5五将棋」が既に存在するから、それで十分なんじゃないの？

>>205
過去と同一の[手番、盤面、持ち駒]になったら引き分けのルールでは双方最善で引き分けとなるゲームに対し、
過去と同一の[手番、盤面、持ち駒]になったら負けのルールに変更したゲームは、
非常に解析が難しくなる。

たとえば、双方ライオンだけでも簡単にはどちらが勝つか分からない。

>>207
後退解析を使って、そんなに難しくなるかな？
普通にバックトラックして勝ち、負けを決められなかった局面で作られるループの結論が
千日手引き分けだったのが、先手後手のどちらが先にループに飛び込んだかで勝ち負けが
決まるだけだと思うけど。

手番も局面情報の一部として扱ってるわけだから、その局面への遷移(指し手)を示す枝は
塗り分けられるんじゃ無いの？

>>208
単純なループじゃなければ、どちらが先にループに入ったかだけじゃ勝敗は決まらないと思う。
たとえば、ライオンだけの場合は全体が大きなループになっているけど、
単純に勝敗は分からない。
おそらく、盤面サイズや初期位置で勝敗が異なると思う。

とりあえず、>>207 の例の具体的アルゴリズムを考えてみてほしい。

>>207
>たとえば、双方ライオンだけでも簡単にはどちらが勝つか分からない。
後退解析プログラムを書いて調べてみた。

どうぶつ将棋と同じ3x4で中央に玉がいて、相手の１段目にトライすると勝ち、
というルールでは以下の結果になった。

先手が直進すると先手の勝ち、
斜め前に移動すると引き分け、
横に移動すると先手の負け

>>210
トライルールを忘れてた。
トライルール有りで3x4でライオンだけだと5手で先手が勝ってしまう。
とすると、>>207 の条件に当てはまらない。
トライルールは無しじゃないとだめだね。
まあでもここまで単純だと、普通に解析出来ちゃうと思うけど。

[局面数] だとなんとか手に負えるが
[総ゲーム数] だと全く手に負えないようなゲームだと
「同一局面になる手は禁止」のルールが有るのと無いのとでは大きく解析の難易度が異なるはず。

> 斜め前に移動すると引き分け、
>>207 のルールだと引き分けは無いんだけど....

どうぶつ将棋の盤にらいおんだけ配置、
トライルールなしで同一[盤面、手番]になる手を禁止のルールでの解析を行って見た。

まず、各局面で勝つ手が1個見つかった所で解析を止める普通のツリー解析だと、
80億局面くらいでやっと解析が完了。
先手勝ち。

各局面に非常に簡単な評価値（相手のらいおんの動ける場所の数）を導入し、
1手の先読みで評価値の高い順に解析したところ、
24万局面くらいで解析完了。
先手、後手が接していない状態であれば、どんな配置でも先手が勝ち。

ちなみに、盤を4x4にしたら、評価値導入後でもまったく解析が終わりそうにない。

特定局面から完全解析を目指せばいい
富岡流44角成の局面が先手勝ちかどうかとか
それならソフトもちっとは人間の役に立つ

本将棋の[盤面、持ち駒]の総数は、
囲碁の12路盤の盤面総数より多く、
囲碁の13路盤の盤面総数より少ない。

┌─┬─┬─┐
│◇│○│＿│
├─┼─┼─┤
│＿│＿│＿│
├─┼─┼─┤
│＿│●│◆│
└─┴─┴─┘
３ｘ３ の盤面にライオンとキリンを上図のように配置した場合、
どうぶつ将棋ルール（トライルールあり）では、双方の最善手は
どうなりますか？

なんとなく千日手引き分けな気がする。

　　 Ａ　　Ｂ　　C
　┌─┬─┬─┐
１│◇│○│＿│
　├─┼─┼─┤
２│＿│＿│＿│
　├─┼─┼─┤
３│＿│●│◆│
　└─┴─┴─┘

最初、C3->C2, A1->A2, C2->C1 とキリンを捨てて、
B1->C1 と取らせて、B3->A2。B1キリンと受けても
B2キリンで先手の勝ち、と思ったんだけど。
4手目に B1->A1 と逃げられるとあとが続かないんだよね

やっぱ引き分けか

万が一、機械がプロに勝てたとしても、プロの存在価値は消えないだろうね。
だってコンピュータの指し手を、解説してもらうとすれば、
やはり将棋に精通している方ならば、何が起きているのか分かるのでは？

存在価値が消えはしないがずっと縮小する。

>>218
オセロはソフトの方が人間のチャンピオンよりはるかに強いのだが、
ソフトの指し手は人間には解説・理解不能なことがよくある。

あと、全日本トップクラスの解説を聞いて、あとでソフトでチェックしたら
間違ってたということもあった。

将棋も同じだよ。

つまりそのぐらい圧倒的になっても解説の仕事はあるわけだｗ

いやだから、人間トップよりはるかに強くなったソフトの指す手の意味は
人間トップでも理解不能で、解説はあてにならないって言ってんだよ

つまりそのぐらいあてにならない解説でも仕事はあるわけだ

今はオセロの解説の仕事ってのは無いよ。

何１０年も前にオセロが流行ってた頃は、囲碁将棋みたいに新聞にオセロの棋譜が
載ってて、それに解説書いてた人もいたけどね。

くだらないけど興味のある局面（？）ならたくさんある
玉のみ対持ち歩2枚はどちらが勝ちか、とか（多分千日手）

最近は２Ｔとか３Ｔバイトのハードディスク安く買えるけど、
将棋ではどう生かせばいいのかわからない。
これらがいっぱいになるほど定跡積めば、ほとんど無敵かと思うけど。

初手からは厳しいけど、80手ぐらいから解析可能なソフトあれば、実用的な価値はあるね。

>>224
規模やソフトの強さが違うからオセロみたいに、仕事がなくなることはないと思う。

連珠の棋譜が新聞に載ったのは知ってるけど、オセロが載ってるのは聞いたことがない

もしかしたら、ガンダム以上にありえないかも知れませんね。
分子素子が実現すれば・・・もしかしたら、
それでも難儀か、江戸時代からあるのにね。

>>229
1980年代はじめころ、デイリースポーツにオセロの棋譜・解説が載ってた
国会図書館にでも行って確認してみろ

>>230　http://www.nec.co.jp/rd/innovative/quantum/top.html
＞スーパーコンピュータでも計算に1千万年かかると言われている300桁の素因数分解を、数十秒で解いてしまうと言われる量子コンピュータ
これ一応小規模なのは実現済みで、大規模化が成功したら将棋の解析くらいは楽勝？

>>232
将棋や囲碁を解くのは素因数分解とは比べ物にならないくらい難しい事が分かっている。
なので、量子コンピューターが実用化したくらいでは全然望み無し。

ほう　数学的な単純化ができないとゆうことかな
局面パターンの数は限られてても各パターンのつながりがややこしいとか
だとするとまだまだ先は長いか

別の言い方をすれば、量子コンピューターを使って将棋や囲碁を現行のコンピューター以上に効率良く解くアルゴリズムが見つかっていない。
そう言うアルゴリズムがありそうだと言うメドも感触も無い。

>>235　調べてみたらまじらしいな！PSPACE問題だとか。すげえ、数だけで考えてた俺が間違ってたわ

　412 ：ご冗談でしょう？名無しさん：2010/04/11(日) 21:55:56 ID:???
　 >>410-411
　 いやー、どっちを証明するのも無理そうなんだよね。

　 一昨年だかの日経サイエンスの記事によれば、チェスや将棋を完全に解明するのは量子コンピュータでも　
　 多分、解けないクラス(NP完全よりさらに質の悪いP-SPACE問題)に属する問題らしい。

　 http://www.nikkei-science.com/page/magazine/0806/200806_080.html

　 ところが、量子コンピュータがNP完全問題を解けると言う見込みも今のところ無いし。

　 量子コンピュータの実用化が難しいと言う話じゃ無くて、たとえ出来ても理論的、アルゴリズム的に解くのが難しいらしい。

>>230です
>>232
300桁といったら、あから以上ではありませんか。それを数十秒とは、
実現したら、物凄いでしょうね。

まさか、将棋を作った人達も、スパコンが登場して、それでも解析出来ない程とは
夢にも思わなかったでしょう。

そりゃ思わなかっただろうな（笑）

その頃コンピューターと言うか、自動計算機をただの空想であっても考えついていた人がもし居たら凄いな。

まあ「量子コンピュータでも無理」というのがどこまで行くかにもよるか。
つまり、「クラス的に量子コンピュータでも全然駄目」なのか、
「完全解析は無理だが、ノイマン型よりかはものすごい高速」なのか。
後者なら、部分的な解析とか、小さい問題なら解けるとかあるしな

まあ量子コンピュータのアルゴリズム自体がまだロクにないからなんとも言えないが、
今の所夢の技術でもなんでもないな、コンピュータ将棋的には

問題の困難さで言うと以下の通りらしい。

P-SPACE＞NP＞量子コンピュータで早く解ける問題＞ノイマン型で早く解ける問題
将棋やチェスの完全解析はP-SPACE

つまり現状では一応「クラス的に量子コンピュータでも全然駄目」らしい
ただＤＮＡコンピュータみたいな思いもよらぬ手法が出てくる可能性は常にある

>>239
ライプニッツ