将棋における実現可能局面数について
篠田 正人
奈良女子大学理学部
将棋のゲームとしての複雑さを測る指標として、「指し始めの局面から実現可能である局面数」を提案する。本稿ではこの局面数が   以上 未満であることを証明しその数え上げの方法の概略を述べることで、局面数がおおよそ    程度と推測できることを説明する。

                                                                                        概要
将棋や囲碁のゲームとしての複雑さを測る指標として、そのパターン数の概算値がしばしば用いられ 手、各局面での可能な指し手の数が約  通りであることから  、すなわち  程度のパターンがある。将棋においては、一局の平均手数が約      は同一とみなす（よってすべての局面を先手番として考えてよい）。また、盤の左右を反転させただけの局面については別のものとみなす。主結果は以下の通りである。
主結果 将棋の実現可能局面数は   以上  未満である。

る、と説明されている。しかしこの考え方では、例

将棋の実現可能局面数

 と表記することにす

えば初手から「▲７六歩△３四歩▲２六歩△５四る。  歩」と「▲２六歩△５四歩▲７六歩△３四歩」といの余地があり、 はおおよそ  

う局面を区別しない、すなわちそこまでの手順前後ないかと推測しているが、本報告は実現可能局面数や迂回を考慮しないことになる。将棋においてはこという新たな指標の提案が主目的であるため、精密ういった「途中からの同一局面への合流」が非常にな評価については深入りしていない。以下、第 ! 節

多いため、本報告では初形から実現可能である局面での数の概算値を求め、新たな指標として提案する。

いての証明を述べ、第 # 節で精密な評価を得るためここで言う初形から実現可能である局面とは指し始のアイデアについて簡単に説明する。

めの図から将棋のルールに基づいて現れ得る局面で

 上からの評価あり、「盤上の駒配置・持駒・手番」のいずれか１つでも異なれば別局面とみなす。ただし、局面を「盤上の駒配置・持駒・手番すべて先後逆にしたもの」

 という上下からの評価は改良  程度ではの上からの評価、第 " 節で下からの評価につ

まず、 を上から評価する方針について述べる。
最初に簡単な評価法で  であることを示そう。# 枚の駒をすべて区別し（例えば ! 枚の角となる。ここでのも別のものとして扱う）、それぞれを盤上のいずれ（ 1）はかの枡または駒台に置き、先手後手および成不成の合の数であり、'0は二項係数である。また、'つの筋に ! 枚（ 枚）の歩を配置する場

 !   は玉、歩を盤上に配置した後の盤上の空き枡の数、# は盤上の飛の先手場合の数を数えると、後手／成不成の区別、"

 $ % &  !   !   '    は持駒の配分の場合の数である。これらを    について和を取という評価式が得られる。この評価において、無駄ることで、「玉同筋・歩 ! 枚」の場合の数の評価がなものを算入している要素を以下に挙げる。

得られる。こうした場合の数の評価を双方の玉が同( 同一局面を ! 度以上数えている（同種の駒を区別しているため）じ筋にある場合、異なる筋にある場合それぞれにつ) 同じ枡に複数の駒がある

は、双方の玉が隣接するパターンも除外して数える

いて求める。なお、双方の玉が異なる筋にある場合と、総計は* 行きところのない駒がある

ここで、上記の方法でまだ無駄に数えているもの+ 二歩であるを確認すると, 双方の玉が隣接している*2 行きところのない駒がある（香または桂）- （先手番なのに）後手玉に王手がかかっている-2 （先手番なのに）後手玉に歩以外での王手がかかっている. 先手玉に実現不可能な王手がかかっている/ その他の理由で初形から進み得ない配置となっている. 先手玉に実現不可能な王手がかかっている/ その他の理由で初形から進み得ない配置となっている

以上のうち、()*+,- について部分的に考慮した方法を述べる。まず、双方の玉が同じ筋にある場合である。そこで、さらに -2 の条件について部分的を数える。盤上の同じ筋に双方の玉と双方の歩があに考察する。ここまでのるパターンのうち ()*+,- の条件をクリアしているものは 0 筋

 "   通りで上から評価される。

 1! 通りである。残りの  つの筋

 "   通りのうち、後手玉の前の枡（△５七玉型であれば５八のうち、歩が ! 枚ある筋が  筋、歩が 枚ある筋がの枡）から先手の飛、竜、馬、金、銀、成 筋あるものとする。このとき残りの駒（歩は残り1  !   枚）について、盤上に飛（竜）、角（馬）、銀、成桂、香、成香、と金で王手がかかっている

金、銀（成銀）、桂（成桂）、香（成香）、と金がそれぞれ 、、、、 、 、 枚あるものとすると、ものを排除する。これは、最初の玉と歩配置パター

これらを飛から順に空き枡に置き（条件 *-./ンのうち後手玉の前の枡が空いているものを選び、については考慮しない）、残りはどちらかの持ち駒

その後の飛〜と金の配置においてこの枡に該当するとすればその配置数は駒がある場合の数、として数えることができる。こ0  1! の結果、$0 & $0    &' 1  "    110   

 $'0  !   &#$"  &
 $'0  !     &# $"  &
 $'0  !       &! $  &
 $'0  !         &# $  &
 $'0  !           &# $  &
 $'0  !            &# $  &
 $'0  !             &! $ '  !    &0 #   という上からの評価が得られる。
上からの評価のさらなる精密化のためには、特に*2 および -2 の条件（後手玉に正面以外から王手がかかっている）をチェックする必要がある。ここで、盤面にある駒が（玉を含めて）"' 枚以下であるものは "   通り未満であることが簡単に示せる

ため、当面はほとんどすべての駒が盤上にあるものと考えることにする。*2 の条件については、盤面!

にある（成っていない）桂はおよそ !30、香はおよ

初形から盤面の駒を先手１一玉、後手９九玉のみとし、持ち駒を調整する。

そ 30 の確率で行きところがないため、半数以上の! 先手２二と、後手８八とを発生させる。
" 残りの盤上の駒のうち、成駒を作って配置する。

局面で *2 の条件にひっかかるものと思われる。また -2 の条件については、後手玉に真正面以外からの王手が掛かっているものも半数以上あると思われ# 成っていない駒を盤上に打つ。先手後手の手数る。これに加えて . の条件、例えば先手玉に ! 枚調整は▲２一と▲２二と、または△８九と△８の金で同時に王手が掛かっているようなもの考慮に八との往復で行う。

   通りのうちすべての条件をの順で行えばよい。この補題により、あとは条件を割程度ではないかと推測され満たす局面数を数えればよいことになる。ここで、の値を知るためには、ここまでで上記補題は先手の２二とが２一または１二、後手の述べた局面作成アルゴリズムによって局面をランダ８八とが８九または９八、また全体を左右反転させムに発生させ、それらのうちどの程度が本当に実現ても同様に成り立つことを考えると、上図の条件を可能局面であるかを判定してその割合を見積もる、満たす局面数を "といった手段が考えられる。この方法の実行についられることになる。

入れると、0 #クリアするものはる。より正確なまず、歩の配置を考える。"〜' 筋のうち歩を !ては第 # 節で改めて述べる。

枚置く筋が  筋、歩を枚だけ置く筋が  筋あり、
!0 筋のうち歩を ! 枚置く筋が  筋、歩を 枚だけ置く筋が  筋あるとすると、二歩禁を考慮すれ

 下からの評価
下からの評価に関しては、具体的に実現可能局面

ばこれらの組み合わせはである条件を述べ、その条件を満たすものの数を数える。

 "  ! 倍した下からの評価が得$ & $    &'

0  ' 1  # " !
ｈ ｈ ｈ ｈ ｈ ｈ ｈ Ａ 玉 一ｈと Ｂ 二ｈｋｈ 三ｈｋｈ 四ｈｋｈ 五▲ｈｋｈ 六ｈｋｈ 七ｈ 八ｈ ｈ ｈ ｈ ｈ ｈ ｈ 九1 $#  & $#   &"1 "通りある。ここで、"1（ "）は１三〜１九の枡に歩を ! 枚（ 枚）置く場合の数である。残りの飛（竜）、角（馬）、金、銀（成銀）、桂（成桂）、香（成香）、△と金をこの順に盤上または駒台に順に置き、その先手後手および成不成を定めることにする。まず１枚目の飛の盤上の位置は、盤上 の位置を除いても少なくとも #' ヶ所（! %  % ! % ）あるこ

Ｃ 玉と Ｄとがわかる。このようにして、飛（竜）、角（馬）、金、銀（成銀）、桂（成桂）、香（成香）、と金を盤上にそれぞれ 、、、、 、 、 枚配置し残りは上図のように、

 先手玉は１一、後手玉は９九に置く。先手２二持駒とすると、この場合の数は$#'   &# $"  &と、後手８八とを置く。

 残りの "1 枚の駒は、１一、１二、２一、２二、

 $1     &# $"  &
 $'"       &! $  &
 $'"         &# $  &
 $'"           &" $  &
 $'"            &" $  &
 $'"             &! $ '    &８八、８九、９八、８九以外の '" 枡のいずれかまたは駒台に置く。ただし、行きところのない駒はないようにする。

 盤面 の枡には飛または竜は置かない。
 盤面 4 の枡には角または馬は置かない。
補題 上記条件を満たす局面はすべて実現可能局面である。

通り考えられる。" は桂を盤上に置くときどの枡で実際、上記条件を満たす局面は次のように実現すあっても先手後手／成不成の区別が少なくとも " 通ることができる。

"

りはあることによる。これらの積を    について和を取ることで、上の局面（先手番）で後手玉に王手がかかっているわけではないが、この直前の指し手が存在しない

 #1   
以上の評価では、なるべく簡明にし似たような局面であっても、次の局面（先手番）

   を示は実現可能局面である。
0  ' 1  # " !

すことを目的としたため最善の評価とは言い難い。

ナシ

例えば、２二の駒をと金から金に変えることで何通りかの場合を新たに作ることができる。ただし、具玉という下からの評価が得られる。

ことから実現不可能局面であることが言える。しか一二三四五六七八九

金 とと と と と△体的に実現可能な局面を構成していく方針では到底よい評価にはたどり着けず、たとえ玉位置も変えてのよい評価（例えば、有効数▲
飛二角二金三銀四桂四 玉香四歩十三
この局面は▲７二金（打）△９一玉としたものと字 桁目の確定）のためには、第 ! 節の最後で述べみなせる。もちろん、この節の最初に述べた「有効たような確率的判断が必要ではないかと考える。そ

数字１桁の確定」程度の目標であれば、こうしたのためには、まず（実現可能かどうかわからない）「実現可能かどうか疑わしい局面」はすべて捨てて局面をランダムに発生させるアルゴリズムと、あるもそれほど影響はないものと思われるが、この２つ提示された局面が「実現可能かどうか」を判定するの図の違いを正確に自動判定するようなアルゴリズアルゴリズムが必要となる。

ムの構成も一つの興味として考えられる。参考のた 

程度が限界で より正確な評価に向けて前者については、特に (・) 以外の細かい条件を指定せず、例えば駒を玉から歩までを盤上にランダムにおいていき、もし玉が隣接したり二歩が発生しめ、一見で実現可能とはわかりにくい局面の例をもう一つ掲げておく。（図は先手番）
0  ' 1  # " !
金馬
金 金金 竜成銀 成銀 成銀 △成銀 成桂 成桂 成桂 成桂 成香 成香 成香 成香と と と と と と と と と ナ
シと と と と と と と と と最終目標であるたらその時点でキャンセルする、としたほうが、多少無駄が生じるにしてもわかりやすくなるものと思われる。
後者については、問題になるのは「実現可能かど▲うかの判定が微妙」な局面である。最初に述べた条件のうち「/：その他の理由で初形から進み得ないナシ配置となっている」についてここまで説明しなかっは下記のものがある。
0  ' 1  # " !
玉と とと と と とナシ△▲飛二角二金四銀四桂四 玉香四歩十二

一二三四五六七八九馬

たが、(〜. に該当せず / に該当する局面の例に

 まとめ本稿では #1

一二三四玉 五六七八九竜 玉

いくなどとしてもせいぜいはないかと思われる。

     0 #    という評価を得た。今後の課題として考えられることは のより正確な評価または推測値を得る
 他のゲーム（囲碁等）における局面数の推測
 ある局面が実現可能であるかどうかを判定するアルゴリズムの考案などがある。

# e