将棋方程式を発見した！(12)

今回は、将棋で詰みのある局面をデータベース化することを考えてみる。

チェスは終盤に進むに従い、盤上の駒が減っていく。取った敵駒は使えないから、局面が収束して行く。この局面を分類してデータベース化しようという試みは古くからある。

Playing Chess with God(Radium Software)
http://d.hatena.ne.jp/KZR/20080531/p1

将棋でこれと同じことが出来るかを考えてみる。

将棋では詰みのある局面が何通りあるか実は知られていない。すべての合法的な(二歩とかになっておらず、初期陣形から合法手のみで到達可能な)詰みの局面を列挙するだけでもかなり難しい。

まず、簡単な詰みをデータベース化することを考えてみよう。詰みに関係のない駒の配置は何らかの形で wildcard として扱っておけば、ある程度圧縮はできるだろう。ここでは、次のような表記を導入しよう。

・自分の利きが必要な場所を青丸。(ここ以外にも利きはあっても良い)
・敵の利きがあっても構わない場所を赤丸。
・敵玉が移動できない場所を緑丸。これは盤の端で移動できないか、さもなくば、こちらの駒が利いていて移動できない(このとき敵の利きがあっても構わない)ものとする。
・自駒は詰めるのに必要な最小駒(これ以上駒がある分には構わない)

次図は、5手詰みである。青丸のところから銀を打ち込んで、どう逃げても金二枚あるので詰む。

ここで用いた青丸・赤丸・緑丸以外に、自駒なら何でも良い記号や、敵駒なら何でも良い記号、空間が空いていなければならない記号なども導入すると良いだろう。

このようにして7×7の升目に対して即詰みのある形をデータベース化することを考える。1枡の表記が2-bitで済むとして、手駒のことは無視するとしても、7×7×2-bit = 98-bitもある。

結果は勝ちと負けだけで 1-bitで表現するとしよう。(本当は、引き分けもあるので1つの局面を表現するのには log2(3) bit = 1.59 bit必要だが) このとき全ての組み合わせを保存しようと考えると、2**98 bit必要である。(**は指数) これは、到底既存の記録媒体に収まりそうにない。

詰みのある局面はこのすべての局面のうち10億局面に1つ(そんなに低いはずないのだが)だとしたら収まるだろうか？

2**98 / 10億 ≒ 2**98 / 2**30 *1 = 2 ** (98-30) = 2**68 bitのデータ量になる。byteに直すと 2**65 byte。惜しくも64-bitのアドレス空間に収まらない。本当はそのデータがどの局面の結果であるかを表現するためのデータが必要なのでこの何倍かが必要だが、そのへんも含めて、おまけで2**64 byteにぴったり収まるとしよう。

記録媒体は何にするかは知らないが仮に夢のように速い4GB(2**32 byte)の記憶媒体が1円で手に入るとしよう。そうすれば2**64は、この4GBが2**32個あればいいので2**32円≒42億円。

とまあ、7×7枡のデータベース化は現在では不可能である。4×4ぐらいなら可能なのだと思うけど、そんな小さな升目なら、たいていは3手までの詰みなのでDBをlook upに要する時間より詰みかどうか実際にゲーム木を探索して判定したほうが速いだろう。

結局、詰みのDB化はメモリ容量的にも計算時間的にも難しいという結論になる。

それとは別に、コンピュータ将棋で上図のように色分けするアイデアは、使えるかも知れない。長手数の詰みを発見した場合、詰みに必要な条件を上図のように抽出しておけば、同一手順での詰みは小さな計算時間で求まるかも知れない。ただし、それがkiller moveより本当に速くなるのかどうかは私にはよくわからない。

「詰む形」とは対極にある、Z(「絶対に詰まない形」)のほうが、データベース化するのが容易だろう。Zは比較的形が限られているし、Zは自玉周辺の比較的小さなエリアの情報だけで決まることが多いからだ。

*1:2**10=1024≒1000なので、2**30=(2**10)**3=1000**3≒10億