コンピュータ将棋基礎情報研究所

コンピュータ将棋に関する基礎的な情報を収集し、分析し、発表する所です。英語名称はLaboratory for Fundamental Information on Computer Shogi (LFICS)。

2016年03月

将棋において、一局面の合法手(ルール違反にならずに指せる手)の最大数は593手であると言われています(参照:「State of the Digital Shogics [最先端計数将棋学]」)。例えば、以下のような局面が最多合法手局面に該当します。

手合割:平手
後手の持駒:金三 桂三 歩十七
  9 8 7 6 5 4 3 2 1
+---------------------------+
| ・ ・ ・ ・ ・ ・ ・ ・ 飛|一
|v玉 銀 銀 ・ 銀 ・ 玉 ・ ・|二
| ・ ・ ・ ・ 角 ・ ・ ・ ・|三
| ・ ・ ・ ・ ・ ・ ・ ・ ・|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| ・ ・ ・ ・ ・ ・ ・ ・ ・|七
| ・ ・ ・ ・ ・ ・ ・ ・ ・|八
| ・ ・ ・ 香 ・ 香 ・ 香 ・|九
+---------------------------+
先手の持駒:飛一 角一 金一 銀一 桂一 香一 歩一

なぜ、593手なのか? 本当に593手が最大なのか? 今回は、頭の体操として、この問題について考えてみましょう。

まず、何もないまっさらな盤を想像して、飛角金銀桂香歩と全ての種類の駒を1枚ずつ持ち駒にしている状況を考えましょう。この時、駒を打てる場所の合計は、\[81 + 81 + 81 + 81 + 63 + 72 + 72 = 531\]箇所あります。ここで、桂香歩については打てる場所が制限されていることに注意してください。持ち駒の種類が減ると、打てる場所が63箇所以上も減ることになるため、合法手の数は激減してしまいます。また、同種類の持ち駒の数が増えても合法手の数は変わりません。この531手を基本として、盤に駒を配置していきます。

1.自玉と敵玉の配置。自玉は、2段目2~8筋に置くと最大で8つ動けて、6つの駒が打てなくなるため、差し引きで合法手を2手増やせて、533手となります。3段目だと打てなくなる駒が7つに増えてしまいますし、1段目だと打てなくなる駒は4つですが、動けるマスも5つになってしまうので差し引きで損になります。敵玉については、1段目だと打てなくなる駒は4つ、2段目だと6つなので、本当は1段目に置きたいのですが、後述するように、1段目には飛車を通したいので、1段目の隅か、2段目に置かれることになります(どちらでも飛車の動ける範囲を考慮すると以下の計算は同じです)。よって、ここまでで527手になります。また、打ち歩詰めが発生すると歩が打てなくなってしまうため、打ち歩詰めが出ないように注意します。

2.持ち駒以外の飛車と角の配置。成りと成らずで2倍の手を稼ぎたいので、場所は1~3段目、生のままで置くことを考えます。飛車はどこにおいても動ける箇所の最大は16箇所で変わらないので、打てなくなる駒が4つですむ1段目に配置します。敵玉を1段目において、2段目に飛車ということでも、ここだけ見ると勘定は同じなのですが、2段目には他の駒も配置したいので、結果的に利きの遮断されない1段目に置かれることになります。これで、555手です。また、角の場合、動ける最大箇所は、1段目で8箇所、2段目2~8筋で10箇所、3段目3~7筋で12箇所ですので、打てなくなる駒を考慮しても、3段目3~7筋が最善です。5段目5筋で最大の16箇所になりますが、この時は6箇所しか成れない(馬を置いても4箇所しか余分に動けない)ので、及びません。これで、572手になります。

3.金、と、成香、成桂、成銀の配置。これは2段目以降に置くと最大で6つ動けますが、6つ以上の駒が打てなくなるので、得になることありません。1段目でも、3つ動けて、4つ打てなくなるので、差し引きで損になります。よって、これらの配置は考えなくてもかまいません。

4.持ち駒以外の3枚の銀の配置。銀は2段目2~8筋に置くのが最もよく、最大で5つ動けて、6つ打てなくなるので、成りを考慮すると1枚当たり4手増やすことができます。置けるのは3枚なので、これで584手です。

5.持ち駒以外の3枚の香車の配置。香車は明らかに9段目に配置するのがよく、7つ打てなくなる代わりに、最大で8箇所うごけて、2箇所で成りの選択ができます。つまり、1枚当たり最大で3手増やすことができるので、合計して、593手になります。

6.桂馬と歩の配置。歩は明らかに置くと損です。桂馬も2箇所しか動けませんので、成りを考慮しても、打てなくなる数を上回ることはできません。なので、どちらも置かない方が得ということになります。

まとめると、

  1. 自玉は2段2~8筋で自由に動ける場所。敵玉は1段目の隅か、2段目で打ち歩詰めがない場所。
  2. 飛車は1段目、角は3段目3~7筋で自由に動ける場所。
  3. 金、と、成桂は2段目2~8筋の自由に動ける場所に配置可能(不必要)。
  4. 3枚の銀を2段目2~8筋の自由に動ける場所に配置。
  5. 3枚の香車を9段目の自由に動ける場所に配置。
  6. 持ち駒は全種類。

とすれば、最大の593手になります。

ただし、上記の記述は、それぞれの駒が最も得をするように配置された場合にそうなるというだけで、そのような配置が実際に可能であるのかについては何も言っていません。配置の可能性については、実際にそういう局面を発見できれば、結果的に可能であったと言うことができます。これについては、たかだか有限個ですし、計算可能な程度に可能性も限られていますので、コンピュータに聞いてみるのが楽でしょう。

ということで、実際にコンピュータを用いて、上記の配置を網羅的に探索してみると、左右反転対称性と持ち駒の違いを除けば、ただ一つの局面のみが上記の条件を満たすということが分かります。それが、記事の冒頭に示した最多合法手局面です。

以上、今回は、頭の体操として、一局面の合法手の最大数が593手であることの証明をしてみました。「数学的な話なのに、コンピュータを使うのは汚い」というような反応もあるかもしれませんが、その辺はプラグマティック(実用主義的)に対処するのが筆者の流儀ですので、ご容赦ください。

ゲームの進行具合を表す指標として「進行度」という量が用いられることがあります。この量は、通常、ゲーム開始時には0、終了時には1になるように規格化され、また、ゲームの進行に合わせて増加するように定義されます。例えば、サッカー等のように時間によって終了するゲームであれば、時間が進行度に対応しますし、野球等のようにターン回数によって終了するゲームであれば、回数が進行度に対応することになります。同様に、バレーボールであれば点数が、マラソンであれば走行距離が進行度に対応します。

一般的に、進行度は重要な情報であり、選手は進行度によって戦略を変えますし、観衆も進行度を参照しながら観戦を楽しみます。テレビやラジオ等の中継においても、まずは進行度(に対応する情報)、次に形勢という流れで実況されることが多いかと思います。

将棋の場合には、手数が進行度に対応すると考えられます。例えば、100手で終了する対局においては、1手進むごとに進行度が1%ずつ進むと考えるわけです。この「1手進むごとに終了手数分の1だけ進行する」という進行度の定義はシンプルかつ明瞭であり、終局手数さえ分かれば、誰でも簡単に計算することができます。

ただし、この定義には明らかな問題点があります。それは、将棋はいつ終局するか分からないため、対局中は終局手数が分からないということです。つまり、この定義によれば、進行度が確定するのは終局後であり、対局中の進行度は推測するしかないということになります。

実はこの問題は、延長や早期終了がありうる野球やサッカー等でも同じように存在していたのですが、その際には延長等はあくまでも特殊条件下における例外であるということで、あまり気にする必要はありませんでした。その点、将棋は、規定の終局手数が存在しないため、対局中に進行度を推測するのが難しいタイプのゲームになっているわけです。

「対局中に進行度を推測する」というのは、言い換えると、「対局中に残り手数を予測する」というのと同じことになります。局面等の情報から「これは長くなりそうだ」等と予測することは、人間なら誰しも意識的、もしくは無意識的にやっていることだと思われます。進行度や残り手数を精度よく推測することは、それがどれくらい勝率に寄与するかはさておき、将棋の技術の一つだとは言えるでしょう。

コンピュータ将棋においても、評価関数の精度向上や持ち時間の管理等のために、進行度の推測が行われることがあります。実際、過去には、序盤・中盤・終盤で評価関数を推移させる手法が注目された時期もあり、その頃には進行度に関する研究もよく行われていました。筆者はその辺の研究に詳しくないのですが、主に、成り駒や持ち駒、玉周辺の駒や利きの数などから“進行度”を算出していたようです。ただし、その時の“進行度”というのは、必ずしもゲームの進行具合を表す指標量ではなく、あくまでも複数の評価関数を推移させるための変数量(全体で一つの評価関数と考えれば、評価項目の一つ)にすぎず、様々な定義が乱立していました。純粋に終局手数を予測しようとする研究はほとんどなかったのではないかというのが筆者の印象です。

さて、前置きが長くなりましたが、今回は、局面の情報は抜きにして、「手数分布のみから進行度を推定するとどうなるか」ということを調べてみたいと思います。

使用する手数分布は、棋士棋譜集(2015年11月版)とfloodgate棋譜集(2012~2015年版)から、レート差200以内で256手までの投了棋譜に限定し、先手勝利と後手勝利に分けて規格化を行って得られたものです。それぞれの棋譜集については、以下の記事をご覧ください。

また、それぞれの棋譜集に対応する手数分布については、「手数分布はガンマ分布で近似できるか?」の記事に記載してあります。

各手数における進行度の平均値を以下に示します。各手数において平均を取る際に、すでに投了済みの棋譜はデータから取り除かれています。また、256手までの棋譜に限定しているため、256手においては進行度は全て1になっています。

sm

どちらの棋譜集においても、グラフの概形は似たような形になっています。これは元々の手数分布が似ているためです。ただ、詳細に見ていくと違いもあり、例えば、floodgate棋譜集の方が棋士棋譜集よりも全体的に進行度が低めに出ています。これは、floodgate棋譜集の方が棋士棋譜集よりも平均手数が大きいことに由来します。

仮に、進行度を機械的に3分割して、“序盤”/“中盤”/“終盤”を区別したとすると、平均値で見た場合、棋士棋譜集では、36手までが“序盤”、75手までが“中盤”ということになり、また、floodgate棋譜集では、41手までが“序盤”、85手までが“中盤”ということになります。平均手数が約16手ほど違うため、それぞれの区分の長さも約5手ほど変わるようです。平均手数の違いが主に投了のスタイルに由来すると考えるとすると、この結果は余り納得いくものではないかもしれませんが、仮に機械的に定義した場合にはそうなるという結果です。

続いて、各手数における進行度の標準偏差を示します。これは、上図の平均値を推定値だと考えた時に推定の誤差の目安となる量です。標準偏差についての詳細は、「平均と標準偏差:それって不偏推定値?」の記事をご参照ください。

ss

結果を見ると、やはりデータのばらつきが大きく、手数の情報からだけでは精度よく推定することができないということが確認できます。この結果は、将棋において「対局中に進行度を推測する」ことの難しさを示すものだと言えるでしょう。

これ以上の精度で進行度を推測するには、局面の情報が必要になります。上述の先行研究で行われているように、手数に加えて、持ち駒の数等の適当な変数群を用意して、機械学習の手法で最適化を行えば、それなりに高精度な推測も可能になるものと思われます。ただ、詳しいことは実際にやってみないと何とも言えません。

以上、今回は「手数分布のみから進行度を推定するとどうなるか」という結果を示しました。やはり高精度の推測を行うには、局面情報を活用する必要があるようです。

また、今回の手法は、精度には疑問符が付くものの、局面情報に依らずに手軽に推測値が得られるという点では優れた面も有しています。特に、「手数分布はガンマ分布で近似できるか?」の記事で提示したガンマ分布近似を併用すると、直接的に手数分布を使わなくても、手数分布の平均と標準偏差の値のみから進行度の近似推定値を簡単に算出することもできるようになります。進行度推定の第零近似(様々な補正を加える前の最も荒削りな近似値)として、何かの役に立つこともあるかもしれません。

このページのトップヘ