将棋における最大分岐数

篠田 正人(奈良女子大学理学部)

ゲームの複雑さを測る一つの指標として, 局面における分岐数, すなわちその時点での可能な着手数, が考えられる([1]). 将棋において, その数が 593である局面の存在が [2] において示されている. この数は囲碁および チェスの最大分岐数よりも大きなものである.

本報告では, この593が将棋における最大数であることを示す.

命題. 将棋における最大分岐数は593である.

まず, 分岐数を考える局面とは
(1) 双方の玉が盤上に存在する.
(2) 40枚の駒をすべて使用している.
(3) 先手番.すなわち, 後手玉に王手が掛かっていない
(4) 初形から実現可能
とする. もちろん, (4)だけで条件としては十分であるが, ここでは敢えて 条件(1),(2),(3)に注意しておく.

可能な局面数は有限であるから, 分岐数の最大値が存在する. この値を M と書くことにする. [2] より, 明らかに M >= 593 である. 最大値 M を実現する局面の一つをQとおく.

さて, 分岐数は

(盤面の駒を動かす)+(持駒を打つ)

と表わされる.

補題. Qにおいて,先手の持駒は飛角金銀桂香歩を各一枚は含む.

証明. 例えば飛が持駒にないとする.盤面にある飛による可能な指し手は 最大32通りであるが, この飛を持駒にすると飛を打つ手が少なくとも41通りは存在する(盤の升目81から駒の総数40を引いたもの). 他の駒についても同様.(終)

この補題より, 最大分岐数を考えるには上記(1)-(4)の条件に加えて

(5) 先手の持駒は飛角金銀桂香歩を各一枚は含む

を加えてよい.

各局面の分岐数を調べる時, 盤面に何もない状態から駒を1枚ずつ置いていき,分岐数の変化をたどっていくことにする.

関数 H(x,Y) を, 駒 x を盤面 y (in Y) に置いたときの

(盤面の駒 x による可能な指し手) -(盤面 y が塞がれたことによる持駒を打つ手の減少数)

の最大値とする( x が成っている場合も考慮する). 例えば,

H(銀, 一段目) = 4-4 = 0
(銀引き2通り * 成不成の選択 = 4 , 飛角金銀の打ち場所の減少より -4 )

である.

また, Y を省略した場合は盤面全体を表すこととする. このとき必要な H の値を列記すると,

H(飛, 一段目) = 32-4 = 28, H(飛, 二段目) = 32-6 = 26

H(角, 三段目) = 24-7 = 17, H(角, 二段目) = 20-6 = 14

H(金) = 6-6 = 0,

H(銀, 二段目) = 10-6 = 4, H(銀, 三段目) = 10-7 = 3,

H(桂) = 6-6 = 0,

H(香, 九段目) = 10-7 = 3,

H(歩) = 6-6 = 0,

H(先手玉, 二段目) = 8-6 = 2,

H(後手玉, 二段目) = 0-6 = -6, H(後手玉, 一段目) = 0-4 = -4

である.

盤面に何も(双方の玉も)なく, 持駒に飛角金銀桂香歩がある状態の分岐数は, それぞれの打てる場所を考えれば

81*4 + 72*2 + 63 = 531

となる. ここで, 桂, 香, 歩の打ち場所には制約があることに注意しておく. 後手の駒,先手の金, 桂, 歩を盤上に置いても分岐数は増えないこと, および条件(5)から, H を用いて

M <= 531 + 28 + 17 + 4*3 + 3*3 + 2 - 4 = 595

という評価が出来る.

命題の証明. M > 593 であると仮定する.このとき, M を実現する局面に おいて飛および後手玉は盤面一段目になければならない.さもなければ,

H(飛,一段目) - H(飛, 二段目) = 2

H(後手玉, 一段目) - H(後手玉, 二段目)=2

であることより M <= 595-2 = 593 となるからである. ここで条件(3)を考える. 飛と後手玉が一段目にあり,後手玉に王手が掛かっていないことから,飛はある一段目の升(後手玉のあるところ)には動けない.このことから, 可能な指し手の最大数から少なくとも2減少することになる.よって M>593 に反する.(証明終)

参考文献

[1] 松原仁, 将棋世界.

[2] 野崎昭弘, ロジカルな将棋入門.