route127の日記： 行止りでも二歩でもない局面の数え上げ

週頭に見た将棋の局面数の数え上げが頭を離れず今週は仕事が手に付かなかった。
色々考えて盤面に味方の「歩」のみ有る場合の行止りと二歩を考慮した局面数を数えてみようと試みた。
盤上に「歩」の駒がn枚ある場合、局面の数は

₈₁C_n

となるが、n≧10の場合は必ずニ歩になるので0～9枚のみの場合を考えることにする。
n=1の場合、取り得る局面の数は、

₈₁C₁=81

となるが、行止りとなる升が9(=₉C₁)あるので有効な局面は72となる。

n=2の場合からニ歩も考慮に入れなければならなくなる。
縦9升×横9升を罫線に沿って縦に分割し、その9列の内から2つを選び、その縦9升×横1升の最上部の行止りとなる升目を除いた8升へ「歩」を打つとすれば、

₉C₂×₈C₁×₈C₁

と書き下せる。
つまり、

（9列から2列を選ぶ場合の数）×（列1の8升から1升を選ぶ場合の数）×（列2の8升から1升を選ぶ場合の数）

と考えるとn=1の場合も

（9列から1列を選ぶ場合の数）×（列1の8升から1升を選ぶ場合の数）

と整理しなおすことができる。

n≦9で一般化すると、

₉C_n(₈C₁)ⁿ

₈C₁=8なので、

₉C_n×8ⁿ

この式の計算値が正しいことを示すには、

₈₁C_n-（無効な局面の数）

を計算し、両者がが合致することを確認すればよい。

n=3の場合の検算例を示せば、直接計算によって計算した値は、

₉C₃×8³=43008

また、無効な場合は、行止りの有る場合と行止りは無いがニ歩（三歩以上を含む）が有る場合とを考える。
行止りが有る場合は、

行止の「歩」が3つ　₉C₃=84
行止の「歩」が2つ　₉C₂×₇₂C₁=2592
行止の「歩」が1つ　₉C₁×₇₂C₂=23004

行止りはないがニ歩が有る場合は、

三歩　₉C₁×₈C₃=504
ニ歩　₉C₁×₈C₂×₆₄C₁=16128

これらの無効例42312(=84+2016+18144+504+16128)を₈₁C₃=85320から除くと

85320-42312=43008

となり、直接計算と値が一致する。

因みに普段使ってるCASIOの電卓に組合せ計算用のnCrボタンがあったので専ら電卓で計算してたが、ワンライナーで計算するなら₉C₃×8³は、

perl -MMath::Counting=:student -e "print combination(9,3)*8**3"

と書ける。

このモジュールを利用して、

perl -MMath::Counting=:student -e "print qq?n=$_ ₉C_{$_}・8^$_/₈₁C_{$_}=?, (combination(9,$_)*8**$_)/combination(81, $_), qq?\n? foreach 0..9;"

こんなワンライナでn=0～9の場合の行止りとニ歩を考慮した盤面が考慮しない盤面に対して占める割合を一覧してみると、

n=0 ₉C₀・8⁰/₈₁C₀=1
n=1 ₉C₁・8¹/₈₁C₁=0.888888888888889
n=2 ₉C₂・8²/₈₁C₂=0.711111111111111
n=3 ₉C₃・8³/₈₁C₃=0.50407876230661
n=4 ₉C₄・8⁴/₈₁C₄=0.310202315265606
n=5 ₉C₅・8⁵/₈₁C₅=0.161144059878237
n=6 ₉C₆・8⁶/₈₁C₆=0.0678501304750472
n=7 ₉C₇・8⁷/₈₁C₇=0.0217120417520151
n=8 ₉C₈・8⁸/₈₁C₈=0.00469449551394921
n=9 ₉C₉・8⁹/₈₁C₉=0.000514465261802653

とnの増加につれ増加する場合の数が抑制されていることが分かる。

成／不成

[cudjo (2713)]

これにさらに成／不成を考慮しなければならないので大変です。
先手／後手は単純に組み合わせ数を考えて掛ければいいだけですが、
と金は行止まりも二歩も関係ないので前提から変わりますから。

Re:成／不成

[route127 (38618)]

個人的には先手後手よりも成不成の場合分けの方が簡単な印象です。
まだ未検証ですが、盤面に味方の「歩」がr枚、味方の「と」がs枚としかない場合、「と」の並べ方は、最上段の9升とその他の72升に分割することで、

s≦9の場合　Σ(m=0,m≦s)₉C_s-m・_72-rC_m
s>9の場合　Σ(m=0,m≦9)₉C_9-m・_72-rC_s-9+m

と書き下せて、これと今回の結果の積を取れば局面の数が計算できるかと思います。

「と」の場合は「歩」のような縛りが無いので、既に埋まっている升を数え上げればすむのに対して、恐らく「歩」同様に置けない升のある「香」とか「桂」との組合せの方が場合分けが複雑なように思います。
冒頭に「先手後手よりも成不成の場合分けの方が簡単」といったのも敵の「歩」の位置によって場合分けが必要だからです。

Re:成／不成

[cudjo (2713)]

香は歩と全く同じルールでいけませんか?
最上列に成っていない香が存在してはいけないだけなので。
桂は制限が1列多くなるだけで、上から2列に成っていない桂が存在してはいけないだけ。

Re:成／不成

[route127 (38618)]

味方の「香」のみn枚ある場合の有効な盤面を考えるのであれば、₇₂C_nと、同様に味方の「桂」がm枚しかない場合であれば₆₄C_mと計算できるのですが、既に盤面に他の駒が有る場合に駒を置く位置が重ならないようにする場合わけが面倒ですよね。

例えば「香」が1枚、「歩」が1枚ある場合、盤面の場合の数は

₇₂C₁・₇₂C₁=5184通り

でもなく、

₇₂C₂=2556通り

でもなく、

₇₂P₂=5112通り

と順列を考慮するか、「香」と「歩」が重なって配置される72通りを先程の

₇₂C₁・₇₂C₁-72=5112

から除くか、あるいは埋まっている升目を考慮した、

₇₂C₁・₇₁C₁=5112

とするかだと考えています。
個人的には最後の案が拡張しやすいのではないかと思います。

また味方の「香」が複数枚ある場合、それが同じ筋にあるかどうかでも場合分けが必要で、「歩」が9枚、「香」が3枚ある場合、

「香」が同じ筋に3枚　{₉C₁・₈C₃}・(₈C₁)⁷・5=5,284,823,040
「香」が同じ筋に2枚　{₉C₁・₈C₂・₈C₁・₈C₁}・(₈C₁)⁶・₇C₁・₆C₁=177,570,054,144
「香」が同じ筋に1枚　{₉C₃・(₈C₁)³}・(₈C₁)⁶・(₇C₁)³=3,867,081,179,136

と場合分けが必要となってくるかと思います。
正直書いてて自分でもよくわからなくなってきてます。
重複を考慮した順列で

₇₂P₁₂/(9!・3!)

からニ歩の場合を除いたものと比べてみないと、場合分けが正しいか判断できませんがしんどくなってきました。

盤面に味方の「歩」のみ有る場合の行止りと二歩を考慮した局面数

[Anonymous Coward]

敵の王将・玉将が無いのなら、打ち歩詰めは存在しませんな。

打ち歩詰め

[route127 (38618)]

打ち歩詰めは組合せの問題ではなく盤面の遷移の問題じゃないかと思う。
歩で王手をかける局面があるとして、その局面がどの局面から遷移してきたのがわからないと、その歩が打ち歩なのかそうでないのか判定が出来ないように思える。

Re:打ち歩詰め

[taka2 (14791)]

「歩の下が空いてない」「歩の上に王がある」なら、打ち歩でしかありえないので、無効な局面でしょう。

歩の下が空いてるなら、打ち歩かもしれないが、突き歩でもありえるので、局面としては有効。

Re:打ち歩詰め

[route127 (38618)]

＞「歩の下が空いてない」「歩の上に王がある」なら、打ち歩でしかありえない
例えば次の盤面を考えたとき、

王　･･･敵
歩　･･･味方
飛　･･･味方

この盤面に遷移するための道筋は、打ち歩以外にも、
1. 敵の王が寄せてくる
2. 味方の飛車が後詰に入る
等考えられるように思います。
もし「歩」が1段目であれば2の条件をなくすことは出来ますが、「王」が寄せてきたという場合が考えられ、打ち歩であると判定することは出来ないように思えます。
というわけで冒頭の条件で打ち歩の判定をするのであれば、もっと条件をきつくしなければいけないのではないでしょうか。
個人的には打ち歩詰めをあくまで組合せとして表現するのであれば、「相手番かつ『王』を動かす際」に制限をかける方が「味方の歩」に制限をかけるよりもすっきりするような予感がします。

Re:打ち歩詰め

[taka2 (14791)]

王手放置 [shogi.or.jp]という反則がありますので、

> 1. 敵の王が寄せてくる
これは、「自ら王手をかけた」という「王手放置」の一種であり、敵方の反則負け

> 2. 味方の飛車が後詰に入る
その前の敵側の手が、歩で王手をかけられた状態なのに「王手放置」しているので反則

ということで、どちらも局面として除外可能です。

Re:

[Anonymous Coward]

route127さんの示している局面は、
・二歩や行き止まりは考慮されている
・王手放置は考慮されていない
という前提で、空いているマス目に自動的に配置されているのだと思います。
そして、自動的な配置に王手放置のロジックが組み込まれていないと言うことは
その局面が「敵の王が寄せてきた」のか「味方の飛車が後詰に入った」のか
「打ち歩詰め」なのかは判断できない。って事じゃないかなあ……。

Re:打ち歩詰め

[taka2 (14791)]

いや、元コメで route127さんは「打ち歩詰めは組合せの問題ではなく盤面の遷移の問題」の述べているので、
「組み合わせの問題として、打ち歩でしかありえない局面が存在するので、それは数え上げから除外できる」という話です。

大元のFLCN2さんのエントリでも、王手放置に関しては「王と玉は隣接することがない」という限定的な状況について言及されていますし、
「王手放置は完全除外」はできなくても、できるだけ局面数の数え上げを減らすことを目的として、「打ち歩詰めという限定的な状況については王手放置を除外」するのは意味があるかと。

ニ歩

[Anonymous Coward]

イ歩やロ歩やハ歩もあるのでしょうか。

# フォントによっては見分けがほとんどつかない

二歩・行止まりを考慮すべきか

[Anonymous Coward]

問題は「すべての局面」を数え上げることです。
この際、直前の一手が何だったかは考慮の対象外とします。

王手放置という反則があって、王が相手の駒の利き筋に移動する「自殺行為」も反則になるのですが、
直前の一手を考慮しない場合、王手がかかったか王の自殺行為移動なのか判定できません。

で、二歩・行止まりの反則も「すべての局面」の中に数えるべきだという気がしてきました。
(二歩で決着がついた将棋の最終局面として出現するから)
でも、三歩とか複数二歩とか複数行止まりとかはその以前に勝負がついてしまうので出現しない局面ということになります。

Re:二歩・行止まりを考慮すべきか

[route127 (38618)]

読んでて確かに遷移の終端として行止りや二歩も数え上げるべきなのかと思えてきました。
また二歩は認めても三歩とか複数二歩を認めないのは「一度に一手しか指せないこと」の表現でもありますよね。
などと感心していたら複数二歩の実例を上のACの人 [srad.jp]が挙げてくれてて振り出しに戻る感じ。

Re:

[Anonymous Coward]

組合せによる局面数の概算というのは、将棋の完全解析の難易度を測る一つの指標で、
これは合法手の積み重ねによって将棋の解析していく中で、
最大このだけの局面数を解析できればよい（ただし網羅する必要はない）って数だと思うんですよね。
逆に言えば、合法手の積み重ねによる難易度の概算で、組合せによる概算を超えてしまうような数を出している人は
重複による局面の合流を考慮できてない、将棋の解析の難易度を過大評価してるって事です。
合法手しか考慮しない（コンピュータの）将棋の解析では、二歩や行止まりの局面は登場しませんし、
完全解析の難易度とかそういう指標として使うなら、二歩や行止まりは除外した方が良いと思うんですよね。
余談ですが、人間同士の対局の場合、反則は自動終了ではなく、対局者とか第三者の指摘が必要です。
なので、複数二歩が盤面に現れたり、反則した方が勝ったり、そういう可能性がないとは言えません。
（例えば、二歩後に13手進んだ高橋道雄九段と安用寺孝功六段の銀河戦の対局）