Research – Ono Laboratory

はじめに

最近，「一般化ぷよぷよのより強い計算困難性」なる研究を発表しました（東北大学の江藤宏先生，九州大学の木谷裕紀先生との共同研究．国内研究会であるゲームプログラミングワークショップで江藤先生による口頭発表．2021年12月30日現在，pdfはここから取れます）．

これは有名なビデオゲーム「ぷよぷよ」を一人用のパズルと見立てたとき，かつそれを一般化した場合，どの程度難しいものであるのかを（最適化）アルゴリズム論的に分析したものです．今回「最適化技術の応用・実践」に関する記事を集めよう，ということになりましたので，ちょうどよい題材ということで，この研究をより一般向けに解説してみようと思います．一般向けですので証明自体には踏み込まず，既存の定理と得られた定理の意義をおよそわかっていただくことをこの記事の目標とします．ただし「ぷよぷよ」について関してはおよそルール等がわかっている方を対象としています．ぷよぷよ自体をご存じない方はWikipedia や，セガによるぷよぷよポータルサイトをご覧になった上でこの記事を読んでいただけると幸いです．

詰将棋とは将棋が元となったパズルゲームであり, 将棋が今の形になったのと同時期に生まれたとされています．詰将棋のルールは将棋のルールに加え，いくつかの固有のルールがあります．その固有のルールのうち，代表的なものとしては攻め方の各手は王手でなければならない，などがあります．

長手数詰将棋とは詰将棋の一種で，名前の通り長手数からなるもので，詰将棋パラダイスなどの専門誌などで「作品」が発表されています．通常，詰将棋は「原則解答手順は一通りに定まる (余詰めが存在しない) 」という性質を満たしていなければならないのですが，長手数詰将棋はその長手数の実現のため，慣例的にこの「余詰めが存在しない」性質に関しては目をつぶることとなっています．

実際， 2019年3月現在の最長手数詰将棋作品とされているものは「ミクロコスモス」(橋本孝治)の1525手ですが，これにも余詰めが存在することが知られています．つまり，ミクロコスモスは厳密には「詰将棋」の条件を満たしていません．さらに詳しく述べると，現在知られている長手数詰将棋は2019年1月末時点のランキング上位1位から16位までの全てに余詰めが存在することが知られています．つまりこれらも厳密な意味では「詰将棋」の条件をみたしていないこととなります．

そのような観点から見ると，余詰めのない厳密な意味での過去最長の詰将棋は「STARSHIP TROOPER」(2010 年．摩利支天，625 手詰め) でした．これは長手数第17位にランクされています．

そこで私（都）は，「余詰めのない長手数詰将棋」の手数を更新することを目標に卒業研究に取り組みました．様々なアプローチをとった結果，既存の「桃花源」(添川公司，767手詰め，ランキング10位)という長手数詰将棋を改変することで本来の詰将棋のルールにのっとった，過去最長となる767手の詰将棋を作成することに成功しました．もちろんこの結果は「桃花源」があってものものですし，私の作品などではなく添川公司さんの作品というべきものと思いますが，実質的には「桃花源」が厳密な意味での過去最の余詰めのない長手数詰将棋となったということで，添川さんには喜んでいただけるのではと思っています．

カテゴリー: Research

「ぷよぷよは計算困難」―パズル・ゲームと最適化アルゴリズム―

はじめに

長手数詰将棋「桃花源・改」