- -pv
スレッドの閲覧状況:
現在、- がスレを見ています。
これまでに合計 - 表示されました。
※PC・スマホの表示回数をカウントしてます。
※24時間表示がないスレのPVはリセットされます。

将棋の完全解析

1名無しさん@おーぷん:2015/08/20(木)05:27:32 ID:ezb()
完全解析をはじめ、全般的に数学的に将棋類を研究するスレ。

どうぶつしょうぎ、3三将棋などの話題も歓迎。

将棋の完全解析は不可能と思われるが、現時点での最善手順の予想はできる。

ここでの最善手の定義は最短で勝てる手(最長で負ける手)。長い詰みより短い必至。
2名無しさん@おーぷん :2015/08/20(木)05:49:25 ID:ezb()
dankogaiのブログによると、将棋の局面のパターン数は10^71、ゲーム木のサイズは10^226だそうだ。この数字がどうやって算出されたのかは気になる。
http://blog.livedoor.jp/dankogai/archives/50070437.html

篠田(2008)によると、将棋の平均手数は115手、合法手の数の平均は80通りなので、80^115 ~ 10^220らしい。
http://www.nara-wu.ac.jp/math/personal/shinoda/legal.pdf
3名無しさん@おーぷん :2015/08/20(木)06:39:11 ID:ezb()
参考までにどうぶつしょうぎの最善手順を示しておく。
http://shogitter.com/publish/e8a0178b2d1497496a28b86448fe0169

http://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/dobutsushogi/sample1.html
に基づき手動で作成。77手目は将棋ったーのバグで☗C1ひよこ打が指せないため、☗C1ひよこ成で代用している。

ところで、どうぶつしょうぎにおいて「ひよこ不成」は許されるかどうか、という問題提起をしたのはおそらく私が世界初ではないだろうか。

同梱の「あそびかたBOOK」では、「一段目まですすむとニワトリに成長」と無条件に書かれているので、不成は反則のように思われる。
http://auctions.c.yimg.jp/images.auctions.yahoo.co.jp/image/ra176/users/1/7/9/1/paralleltwin850don-img600x448-1436782590szzonm5341.jpg
一方で、「将棋のルールと違うところ」と題して「どうぶつしょうぎに反則はありません」と記しているので、(将棋で反則とされる)ひよこ不成も反則ではない、という解釈もできる。
4名無しさん@おーぷん :2015/08/20(木)07:18:46 ID:ezb()
さて、本題の将棋の完全解析、もとい最善手順の予想。

初手は最も利きが増える☗7六歩が最善と仮定して、以下、対称形を保って指し進めていくのが最善と仮定すれば、☗7六歩☖3四歩☗2六歩☖8四歩となって横歩取りのようになるのが自然ではないか。
http://shogitter.com/publish/262c0eb0183137554c555d9cb946de4d

一歩損で後手まずいが、ここで☖7六飛では☗3二飛成(☗4一金までの詰めろ)☖同銀☗2二角成で金損なので不利。よって☖8八角成☗同銀☖7六飛と角交換して歩損を解消し、相横歩取りになるのが最も自然である。
http://shogitter.com/publish/5d7e196ae11b44e3919239dbcfc0e57e

この局面は後手一手損なので、将棋は先手必勝ではなかろうか。
この後は羽生の頭脳に書いてあるとおりに進行し、第3図。
http://shogitter.com/publish/c5df3291e7872dd7929e22c4bc1a08e2

従来はここで☖8一飛☗6二銀成☖同玉☗7四桂☖5一玉☗6三銀で先手勝ちとされていたが、☖7六同飛☗6五玉☖6四歩☗5五玉☖5四歩の北浜新手で今は後手勝ちと結論づけられている。
http://rocky-and-hopper.sakura.ne.jp/Kisho-Michelin/8399/4-8399-0818-4.htm

その第13回全日本プロトーナメント4回戦小野修一七段対北浜健介四段戦はここにある。
http://kifdatabase.no-ip.org/shogi/index.php?cmd=kif&cmds=display&kid=6023
が、都合上、62手目まで同一手順の、将棋の神様同士の対局と考えられる第44期王将戦挑戦者決定リーグ3回戦羽生善治名人対村山聖七段戦を最善手順とさせていただく(この将棋は銀不成が多いのも私の好み)。
http://kifdatabase.no-ip.org/shogi/index.php?cmd=kif&cmds=display&kid=5583

終局図がこちら。
http://shogitter.com/publish/c072b5e58804e5ff9916fac7c57eac4e

したがって、現時点では将棋は84手で後手必勝、ということになる。
5名無しさん@おーぷん :2015/08/20(木)08:02:29 ID:ezb()
以下、☗5六桂☖5五金☗同玉☖6五竜☗4六玉☖3五竜で、ひとまず将棋の結論は90手で後手必勝である。
http://shogitter.com/publish/a5f3cb1054d2adc358b0405d08f41df1
☗5六桂からは先手の応手は一本道。
☗5六金だと詰みはないようである。なので☗5六金が最善かもしれない。
6名無しさん@おーぷん :2015/08/20(木)08:33:06 ID:ezb()
ところが『将棋世界』2015年6月号飯島栄治七段・著「横歩取り裏定跡の研究」によると、53手目☗8五玉で69手以上で先手勝ちだという。したがって、今のところ将棋の結論は69手以上で先手勝ちということになる。
http://shogitter.com/publish/1031e0bb6c8ae1ca26de8716a1d1e05f

参考URLをいくつか。
https://books.google.co.jp/books?id=87OwCAAAQBAJ&pg=PA184
http://toro.2ch.sc/test/read.cgi/bgame/1420154348/283
http://shogipenclublog.com/blog/2014/08/06/habunozunou/
http://blog.livedoor.jp/ymbr_satoh/archives/52152081.html
7名無しさん@おーぷん :2015/08/20(木)08:47:56 ID:ezb()
相横歩取りに関してはさらに、19手目☗7七銀でponanza-村山戦のように☗7七歩とし、☖7四飛に☗2三角という手もある。
http://shogitter.com/publish/cf4cea4d6a80e34bb1b73526dfd62445
馬を作っても「角なんか打たれ得」と思われる可能性もあるので一概に有利とはいえないが、この場合は有力だという。

参考:
https://book.mynavi.jp/shogi/blog/detail/id=38515
http://ameblo.jp/shogi-strategy/entry-12053635980.html

ともかく相横歩取りは69手で先手必勝というのが現在の結論で、これ以上の手延ばしがあれば教えてもらいたいところ。
8名無しさん@おーぷん :2015/08/20(木)08:57:17 ID:ezb()
そろそろ本気を出すとするか。

今後の研究の方向性としては、「横歩取り☖3三角なら後手必勝」あるいは「2手目☖8四歩なら後手必勝」というのもありうるが、やはり将棋は先手必勝と仮定した上で、「69手よりも長い手延ばしができるかどうか」を考えるのがいいのではないかと思う。

4手目☖8四歩からのチャンチャンバラバラが先手必勝ならば、たとえば4手目☖4四歩として角道を止め、ノーマル四間飛車穴熊などのじっくりした展開にするのが最善であるという可能性も大いにある。

4手目☖4四歩は居飛穴で勝率が悪いとして忌避されてきたが、最長で負ける手=最も長い手延ばしが最善と認識されて日の目を見る、というのは興味深い。ただし急戦が先手必勝でないことが条件だが。

別の方向性としては、「打ち歩詰めがなければ先手必勝」の検証だとか、後手番で千日手または持将棋に持ち込む順の研究なども考えられる。
9名無しさん@おーぷん :2015/08/20(木)09:47:09 ID:ezb()
将棋の局面は明確に詰みがあるのでなければ、どちらかの勝ちを証明するのが困難なのが歯がゆいところ。

暇つぶしにWikipediaの必至局面が必至であることを証明してみる。
Wikipediaの解説は全部の合法手を列挙していないので、厳密な必至の証明になっていないのが気になっていた。
この局面は先手玉が存在しないので将棋の局面ではないが、そこは目をつむる。
https://ja.wikipedia.org/wiki/%E5%BF%85%E8%87%B3#.E4.BE.8B

この局面は☗2二金打までの詰めろである。
後手の合法手は506通り。以下、

* ☖1二金、☖2二歩、☖2二香、☖2二桂、☖2二銀、☖2二角、☖3一角、☖3一玉、☖3三銀、☖3三角、☖4四角、☖5五角、☖6六角、☖7七角、☖8八角、☖9九角
- ☗3二金打まで

* ☖1二飛、☖2二飛、☖5二飛、☖6二飛、☖7二飛、☖8二飛、☖9二飛
- ☗3三桂☖3一玉☗4一金まで

* ☖2二金、☖3二金
- ☗3三桂(1)☖同金☗2二金(2)☖3一玉☗4一金まで

* ☖3一銀、☖3一金
- ☗3三桂まで

* ☖3二飛
- ☗3三桂(1)☖同飛☗2二金(2)☖3一玉☗4一金まで

* ☖4二飛
- ☗3三桂☖3一玉☗2一金まで

* その他全部
- ☗2二金打まで

したがって、この局面は必至である。Q.E.D.

これが完全な必至の証明ってもんよ。
10名無しさん@おーぷん :2015/08/21(金)00:16:17 ID:BgT()
携帯だと☗☖が文字化けするので▲△に変更。

連続王手の千日手関連で面白い話題。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1465787199#161663899

将棋には「打ち歩ステイルメイト」や「最後の審判」など、現行のルールではゲーム値を決定不可能な局面が存在することがすでに示されている。

先手:▲2七銀、▲3八飛
後手:△2九玉、△4九と
先手の持駒:金
後手の持駒:残り全部

で、

▲2八金△1九玉▲1八金△2九玉(')
▲2八金△1九玉▲1八金△2九玉('')
▲2八金△1九玉▲1八金△2九玉(''')
▲2八飛△3九玉▲3八飛△2九玉('''')

は連続王手の千日手になるか、というもの(かっこ内は同一局面カウント)。

私は同一局面4回でかつ、手順中の先手の指し手がすべて王手で構成されているので連続王手の千日手になると思った。
11名無しさん@おーぷん :2015/08/21(金)00:42:29 ID:BgT()
しかし、じゃあこれならどうだろう。

先手:▲1八金、▲2七銀、▲3八飛
後手:△2九玉、△4九と
先手の持駒:なし
後手の持駒:残り全部

(')▲1七金△1九玉▲1八金△2九玉('')
▲2八金△1九玉▲1八金△2九玉(''')
▲2八金△1九玉▲1八金△2九玉('''')

('''')で同一局面4回となるが、手順中の▲1七金は王手ではない。これは連続王手の千日手ではなく、ただの千日手と解釈するのが妥当なのだろうか。

この例は▲1七金で後手が△1九玉を指す必然性がないのでimpracticalだが、もっとpracticalな例を作って世に問う価値はあるかもしれない。

千日手に至るシークエンスの後半が全部王手なのに、連続王手の千日手にならないというのは非直感的ではある。
12名無しさん@おーぷん :2015/08/21(金)01:56:08 ID:BgT()
電王トーナメントルールだと、「同一局面の最初と 4 回目の間の一方の指し手が王手のみだった場合」とされているので、やはり>>11は連続王手の千日手ではないということになるかもしれない。私もそれでいいと思う。
http://info.nicovideo.jp/denou/denou_tournament_rule.pdf
13名無しさん@おーぷん :2015/08/21(金)02:13:10 ID:BgT()
将棋の「局面」の定義は盤面、持ち駒、手番で、この3つが決まればゲーム値が決定できると思われているが、実際は「同一局面4回で千日手」の規約があるので、「これまでに出現した局面」の情報も必要となる。

たとえば初形の局面を見せられて▲7六歩と思いきや、実は4回目なので何も指さずに千日手引き分け、という可能性もありうる。

ただし一般的には将棋ソフト等で局面検討をする際は、「これまでに出現した局面」は空集合であると仮定されていると思われる。

このように過去の指し手が現在の局面評価に影響を与えることを、履歴現象、ヒステリシスと呼ぶ。

その意味では将棋には「流れ」がある、といえるかもしれない。
14名無しさん@おーぷん :2015/08/21(金)02:55:58 ID:BgT()
書き忘れたが、とはいえ「局面」の定義に「これまでに出現した局面」は含まないのが自然だろう。
含んでしまうと「同一局面4回」の千日手の定義を修正しなければならなくなる。
15名無しさん@おーぷん :2015/08/21(金)03:44:12 ID:BgT()
2chに同名のスレ(本スレとは無関係)があったので見てみたが、序盤は「完全解析」の定義で揉めているようで驚いた。
http://www.logsoku.com/r/2ch.net/bgame/1233071054/
完全解析とは、
http://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/dobutsushogi/animal-private.pdf
などで用例があるとおり、もちろん初期局面のみならず▲8六歩も含めてすべての局面のゲーム値を決定し、そこからの双方最善手順を具体的に示すことを指している。
https://en.wikipedia.org/wiki/Solved_game
でいうstrongly solvedにあたる。

このうちultra-weakly solvedの定義が面白く、これは将棋でいえば初期局面のゲーム値を決定することにあたるが、最善手順を一つも示すことなくそれを達成できる場合もある。

このnon-constructive proofの概念を2chの諸氏は理解できるのかどうか。

たとえば「無理数の無理数乗は無理数か」という問題で、√2^√2が有理数ならばNo。無理数なら(√2^√2)^√2 = √2^(√2×√2) = √2^2 = 2は有理数だからNo。よってNo。という非構成的証明が有名。

ちなみに将棋のゲーム値が決定可能であることは証明されており、Zermeloの定理と呼ばれる。そう。将棋が先手必勝と後手必勝と引き分けのいずれであるかはわからなくとも、いずれかであることはわかるのだ。
https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)

ちなみに角落ちが上手必勝であることを証明できたら大したもの。
16名無しさん@おーぷん :2015/08/21(金)04:48:40 ID:BgT()
http://dell.tanaka.ecc.u-tokyo.ac.jp/~ktanaka/dobutsushogi/20090626.pptx.pdf
を参考にどうぶつしょうぎの局面数を自分でも計算してみる。

先手のライオンを置けるマス目は3×4=12通りある。
後手のライオンを置けるマス目は先手のライオンを置いたマス目を除く11通り。したがって、ライオンの組合せは12×11 = P(12, 11) = 132通りになるとのことだ。

このnPrとかnCkとかのpermutationやcombinationのnotationって地域差はどうなってるんだろう。
一応日本独自ではないようだが。数学のテキストだとnCkは二項係数でbig parenthesesで書かれるのが一般的だが、nPrの方はn!/(n-r)!とwholeでas isで書かれるのが多い希ガス。
https://www.mathsisfun.com/combinatorics/combinations-permutations.html

きりんも同じで132通りではないのか。と思いきや、一方が2つきりんを持っているパターンもある。
先手が2つの場合、最初のきりんは12通り、次のきりんは11通りなので132通り。
後手も同じなので132通り。
1-1の場合も132通り。
じゃあ132+132+132=396通りではないか?

いや、盤上には必ずライオンがあるのか。
じゃあ3*4=12ではなく、3*4-2 = 12-2 = 10マスしかないと考えればいいのか。

すると10*9=90通りで、90*3=270通りでは?
いや。田中さんの計算では、2つのきりんを区別しないところまで考慮されているのか。そうか。

ということは、やはりC(10, 2)*2 + 10*9=180通りでいいようだ。
17名無しさん@おーぷん :2015/08/21(金)05:00:28 ID:BgT()
C(10, 2)*2 + P(10, 2)ならわかるが、田中さんのC(10, 2)*2^2ってのはなんだろう。わからない。まあいいや。

ぞうも同じだから180通り、と思いきや、きりんを配置した上でのぞうの配置をもう考えているらしい。
つまり8マスしかなく、C(8, 2)*2 + 8*7 = 112通り、

ひよこは6マスで、C(6, 2)*2 + 6*5 = 60通り、

ニワトリも60通り、先手がニワで後手がぴよが60通り、その逆が60通り、よって60*4=240通り。

よって132*180*112*240=6 3866 8800、6.4×10^8、6億4千万というわけか。

どうぶつしょうぎの持ち駒なしの局面数の上限は638668800である。

なんだかなんで最後全部かけたのかとか、組合せの計算はよくわからんが、そういう定跡だと思っておくことにする。
18名無しさん@おーぷん :2015/08/21(金)05:06:14 ID:BgT()
持ち駒の総数が6個だと3564なのはなんでだろう。

ライオンのみのパターンは132通りある。

その1パターンに対して、6個の持ち駒を2人で分ける。

000000とすれば、総数が6とすれば111111みたいなパターンだ。

つまり全桁の和が6になるような01の6桁の組合せはいくつあるか。

答えは3564/132=27通りらしい。

これは3^3か…?

そうか、(ひよこ, ぞう, きりん)に対して、{先手の持ち駒, 後手の持ち駒, 双方の持ち駒}の3つの状態を付与するから3^3なのか。

なるほど。
19名無しさん@おーぷん :2015/08/21(金)05:19:03 ID:BgT()
じゃあ持ち駒の総数が1個の場合は…?

この場合、先手がひよこを持ってるか、ぞうを持ってるか、きりんを持ってるか、s/先手/後手/かの6通りしかない。

「2人とも駒を持ってる」はありえない。

なんで0のときと同じ局面数なんだろう。

先手がひよこを持っているとする。
ライオンは132パターン。
きりんは180パターン。
ぞうは112パターン。
ひよこは先手の6パターン+後手の6パターン+先手のニワ6+後手のニワ6=24パターン。

132*180*112*24*6=…あれれ?

じゃあとりあえず132*180*112*24として、先手ぞうだと…
132、
180、
先手ぞうが8、後手ぞうが8の16、
ひよこは(C(7, 2)*2 + 7*6)*4=336になるのか!
132*180*16*336か。

先手きりんだと
132
*(10+10)
*(C(9, 2)*2 + 9*8)
*336
=132*20*144*336。

つまり(132*180*112*24+132*180*16*336+132*20*144*336)*2が答えらしい。これはたしかにあら不思議、638668800になる。

ともかく自分でたしかめられてε-(´∀`*)ホッ
20名無しさん@おーぷん :2015/08/21(金)05:37:28 ID:BgT()
うーむ、1567925964の説明ですら簡単に行うのは難しい。どうしたものか…
21名無しさん@おーぷん :2015/08/21(金)05:42:40 ID:BgT()
3x3将棋の局面数を考えてみる。

先手の王将は9通り、後手の王将は8通り、と言いたいところだが、玉の利きがかぶってる局面は禁止されている。

すると、どうも5+3+5+3+3+5+3+5=32通りの玉たちの配置があるようだ。

これは対称性を利用すれば、実質5*4+3*4=32といえる。

王が真ん中にいる局面というのはありえない。
22名無しさん@おーぷん :2015/08/21(金)05:55:49 ID:BgT()
わからん。つまらん。この計算はやめよう。
23名無しさん@おーぷん :2015/11/27(金)16:07:36 ID:7ZG
3ヵ月前は具体的な最善手順ということで、対称的な相横歩取りなどを研究していたが、今はちょっと大人になってもっと鳥瞰的に、包括的な視野で将棋を解明してみようと思う。

爆問学問等でも周知のとおり、将棋の初手は30通りある。対する後手の2手目も30通りである。したがって、都合30×30 = 900通りのゲーム木のノードが本将棋の序盤には存在することになる。
http://www.nicovideo.jp/watch/sm23321471

では、この900通りすべてに最善手順の芽があるのかというと、そうではない。

2手目△3二飛戦法絡みで、初手▲2六歩の場合は3二飛が使えない、すなわち▲7六歩△3二飛という出だしは後手必敗である、というように、「最善手ではない」ノードがあることは今でもわかる。

本論文ではそれを追究し、2手目までの900通りを「これはダメだ」という手、「これは有力」という手、「これは損だ」という手に分類していきたい。
24名無しさん@おーぷん :2015/11/27(金)16:10:42 ID:7ZG
>>23
久しぶりに言葉を発したのでtypoをしてしまった。

>ゲーム木のノードが本将棋の序盤には〜
は「本将棋の2手目までには〜」の誤り。

>▲7六歩△3二飛という出だしは後手必敗〜
は「▲2六歩△3二飛」の誤り。
25名無しさん@おーぷん :2015/12/15(火)09:14:53 ID:zAo
初手は30通り、2手目までは900通りとして、3手目までの組合せは何通りになるのかと考えてプログラムを書いたら、25740通りという結果を得た。

それで "将棋" "25470" でググったら同じことをしている人がいた。この計算はチェスプログラミング業界ではPerft (performance test) と呼ぶようだ。
http://qiita.com/ak11/items/8bd5f2bb0f5b014143c8

と思っていたら、なんといつも見ている2ch名人にやねうら王がさらなる結果を発表していた。同時期に同じことを考えている人が複数いるとは、シンクロニシティを感じる。
http://i2chmeijin.blog.fc2.com/blog-entry-3169.html

一応転載すると、
30, 900, 25470, 719731, 19861490, 547581517, 15086269607, 416062133009, 11661472222632, ...
という数列になる。
26名無しさん@おーぷん :2015/12/15(火)09:26:59 ID:zAo
『2手目の革新 3二飛戦法』という本があるが、「ソフトの評価値がプラスなら勝ち」という判断で、9手目までの「勝ち手順」を列挙すれば、いわゆる序盤戦術に関しては読み切れそうな気がする。

ただし、それはもちろん現時点においてもソフト的に△3二飛が成立している、すなわち△3二飛と指した後、先手が何を指しても後手がソフト的にマイナスにならない手順が少なくとも1つ存在する、という前提によっている。

あるいは、そのような手順は▲7六歩△3二銀▲2六歩△4四歩など無数に存在し、(人間的には不利なことが明らかなので)とても使い物にならないのかもしれない。

なお「プラス」は「一定以上」、「マイナス」は「一定以下」と適宜読み替えていただきたい。

升田幸三賞は△8五飛などかなり深くまで読まなければならず、厳しいだろう。

新着レスの表示 | ここまで読んだ

名前: mail:





将棋の完全解析
CRITEO