コンピュータ将棋界隈のソフトが誰もミクロコスモスを解けない話
ミクロコスモスという詰将棋の作品がある。橋本孝治氏により1986年に発表された、史上最長の1525手詰めの詰将棋である。*1
コンピュータ将棋黎明期では、まともに指し将棋の指せるプログラムよりも詰将棋を解くプログラムのほうがずっと先に実用化されたと言われている。
コンピュータが詰将棋の解図能力で人間を超えた*2のも随分昔の話で、脊尾昌宏氏によるプログラム「脊尾詰」*3によって、このミクロコスモスも1997年に解かれ、余詰や不詰のない完全作であることが示された。
脊尾氏のプログラムに使用されたアルゴリズムは論文として公開されており、またそのアルゴリズムを発展・効率化させたdf-pnアルゴリズムを長井歩氏が考案し*4、これもアルゴリズムが論文として公開されており、様々な将棋ソフトが終盤用詰めルーチンとして実装している。*5
論文だけでは再現できない詰将棋アルゴリズム
ところがである。このdf-pnアルゴリズム、数十手の詰将棋を解く分には一瞬なのであるが、数百手の超難解詰将棋を解こうとすると、論文のアルゴリズム概略からでは実装を再現できないのである。
世界コンピュータ将棋選手権常連の川端一之氏による「なのは」は、対局機能だけではなく、詰将棋の解図ルーチンにも莫大な労力を割いた将棋ソフトである。
なのはのdf-pnを実装した詰将棋部分だけを取り出したソフトは、「なのは詰め」として氏のwebサイトでも公開されている。
そんななのはでも未だにミクロコスモスの解図には至っていない。
詰将棋ルーチンに挑戦したのはなのはだけではない。やねうら王チルドレンの一つであり、三駒関係に代わる現在最強の評価関数であるNNUE関数を生み出した「tanuki」チームの一人である野田久順氏、同じくやねうら王チルドレンの一つである「Qhapaq」の開発者である澤田亮人氏らがやねうら王に詰将棋ルーチンを組み込んだときも、ミクロコスモスを解くことはできなかった。
実際に超長手順の詰将棋を解くには、df-pnに、論文では詳細に解説されていない
- 詰将棋専用のGC（ガベージコレクション。メモリ不足になったときに、重要度の低いメモリ領域を破棄する）
- 手駒の優越関係（持ち駒が金、金、桂で詰むなら、ここに歩が加わっても詰む、といった関係。）
- 証明駒、反証駒（持ち駒のうち詰めに必要な駒だけを取り出してハッシュに保存する。反証駒は不詰めに必要な最小の駒。優越関係と組み合わせる。）
- 千日手の問題の回避
- 局面に合流があった場合の証明数、反証数のダブルカウントの扱い
等を正しく実装する必要がある*6。が、これらを完璧に実装できた人は現在の将棋ソフト開発者たちの中にまだいないのである*7。詰将棋ルーチンは現代において製法の失われた、ダマスカス鋼、あるいは古刀のような存在となっているのだ。*8
ミクロコスモスを解くエンジンがオープンソースとなる日は来るか？
コンピュータ将棋がオープンソースになり、優秀な頭脳が活発に議論を重ねる中でも、未だに最長の詰将棋を解ける20年以上前のソフトウェアが再現できないというのは興味深いことである。
このミッシングリンクの謎が解けるのは、果たしていつか。それはコンピュータ将棋開発者たちの間で詰将棋ブームがおこった時に違いないが、今はみんなディープラーニングに夢中であり、それはまだ当分先の話でありそうだ。
*1:このミクロコスモスの記録は2020年12月現在もなお破られていない。
*2:とは言え、公開されている将棋ソフトが未だに解けない超長編の詰将棋も未だにいくつか存在する。
*3:現在フリーウェアとして公開されている。
*4:これによって超長手数の詰将棋作品が全て解けたと論文中にはあるが、プログラムは非公開である。
*5:たとえばBonanza、GPS将棋、なのは、やねうら王等。
*6:千日手の問題や局面の合流は厳密なアルゴリズムを実装することはたぶん不可能で、何らかのヒューリスティックスを用いねばならない？
*7:いたらコメントで教えて教えてくれると嬉しいです。でもいたらみんな実装を参考にしてミクロコスモスをとっくに解いてると思うので、いないはず……手元のたぬき詰めはHash16GBで1時間解かせて答えが出なかった。
