1. ぷよを自由に配置できるぷよぷよの連鎖数判定問題: 色数制限を課した場合：○澁谷諒祐（テクノプロ・エンジニアリング），木村 慧（九州大学）
2. 色数を制限したぷよぷよの計算困難性について：○江藤宏（東北大学）， 木谷裕紀（九州大学），小野廣隆（名古屋大学）
概要：ぷよぷよとは"ぷよ"と呼ばれる色のついたブロックを盤面に配置し，ぷよを上下左右に4つ繋げることで消してゆくパズルゲームである．消えたぷよの上にぷよがある場合，それらは落下するため，連続してぷよが消えることがある．このようにぷよが連続して消える現象を連鎖といい，高得点を得るためには長い連鎖を起こすようにぷよを配置することが求められる．通常，プレイヤーは逐次的に与えられる2つ組のぷよ（ピース）を操作して盤面へ配置するが，今回扱う問題設定では初期盤面のみが与えられ，盤面の空いているマスに好きな色のぷよを配置することができる．この特殊ルールにおける最大連鎖数は通常ルールの各盤面における最大連鎖数の上界を与える．既存結果として，この特殊ルールにおける連鎖数判定問題はNP完全であることを第13回本研究集会で発表した．しかしながら，同結果では使用できる色数に制限を与えていなかった．今回は使用できる色数を14に制限した場合にも同問題がNP完全であることを3-PARTITIONからの帰着により示す．また，初期盤面がすべて空白マスのとき，使用できる色数がα(≧4)ならば同問題が多項式時間で解けることを示す．なお，使用できる色数が2，3の場合については部分的に得た結果を報告する．本発表の内容は中止となった第15回本研究集会で発表する予定だったものと，関連研究を除いて同一である．
３. グラフ上の色付きドロップ順次交換の計算量：○岡田 優斗（名古屋大学），木谷 裕紀（九州大学），大舘 陽太（名古屋大学），小野 廣隆（名古屋大学）
- 概要：本研究では，盤面サイズ，色数に関して一般化したオフライン型パズルとして，一般化ぷよぷよの計算複雑度について考える．我々の結果は以下のとおりである： (1) 連鎖数最大化はぷよ2色（おじゃまぷよあり），あるいはぷよ3色（おじゃまぷよなし）でもNP 困難，(2) P≠NP の仮定の下で， ぷよ4色（おじゃまぷよあり）の連鎖数最大化に対しては近似比の精度保証が落下するぷよ数nの多項式以下となるような多項式時間近似アルゴリズムは存在しない， (3) 全消し判定はぷよ4色（おじゃまぷよなし）でもNP 完全である．
- 概要：グラフの各頂点に置かれた色付きドロップを遷移規則に従って初期配置から目標配置へと再配置するパズルを考える． このパズルでは，初めに移動ドロップを任意に選び，その後は移動ドロップを現在の頂点から隣接頂点の一つへ移動させることを繰り返す． 移動ドロップが他の頂点へ移動するたび，移動ドロップと移動先に置かれたドロップは交換され，ドロップの配置は遷移する． 本研究ではこのパズルに対し，指定された移動回数以下での初期配置から目標配置への遷移が可能か否か判定する問題を考える． この問題に対し得られた結果として，複数のグラフクラス上でのNP完全性と，ある条件を満たす特殊なグラフに対し高速に動作するアルゴリズムを紹介する．
4. Computational Complexity of Ball/Water Sort Puzzles：伊藤健洋（東北大学），川原純（京都大学），湊真一（京都大学），大舘陽太（名古屋大学），斎藤寿樹（九州工業大学），鈴木顕（東北大学），○上原隆平（北陸先端科学技術大学院大学），宇野毅明（国立情報学研究所），山中克久（岩手大学），吉仲亮（東北大学）
5. ゲーム、デザイン、可換環: 射影的 Steiner triple system の特徴付け：○入江佑樹（東北大学）
- 概要：近年，複数本の試験管内に与えられた色付きの水やボールを並べ替えるオンラインパズルが遊ばれている．これは色付きの単位の移動に自然な制約があり，効率よく並べ替えるのは難しい．この移動規則の制約は，元に戻せない規則と元に戻せる規則が混在していて，組合せ遷移の枠組みから見ると興味深いパズルである．本研究ではこのパズルを一般化した問題の計算量的な困難性を研究した．
6. 連続フック引き抜きゲームとそのGrundy数：安福智明（国立情報学研究所），○多田将人（筑波大学）
- 概要：ゲームを用いて、組合せ構造を研究する一つの手法を紹介する。話の始まりは Conway と Ryba によるヘキサッドゲームという二人対戦ゲームにある。このゲームの面白さは、必勝局面全体が Steiner system S(5, 6, 12) という特別なデザイン構造を持つ点にある。それでは、ヘキサッドゲームのようにデザイン構造を持つゲームは他にもあるのだろうか？本講演では一般の Steiner system に対してそのようなゲームが構成できることを紹介する（この構成法は Steiner system に限らず、より一般のある種の組合せ構造に対して適用できる）。また構成したゲームを用いると、射影的 Steiner triple system と呼ばれる族が特徴付けられる。さらにこの結果はある次数付き環を用いて記述でき、ゲーム、デザイン、可換環がつながる。なお本講演の主な部分は、第15回の研究集会にて紹介予定だったものである。
7. 拡張削除ニムについて：安福智明（国立情報学研究所），坂井公（神奈川大学），篠田正人（奈良女子大学），○末續鴻輝（国立情報学研究所）
- 概要：Young図形上で行われるフック引き抜きゲームは，組合せゲームであり，Sato-Welterゲームと同型なゲームである．また，その拡張とみなされるd-complete poset上で行われる平明ゲームは，組合せゲームであり，A,D,E型を中心としたLie代数のルート系により定まるWeyl群の構造に対応する様々な性質をもつことが知られている． 本講演では，Young図形とB,C型Weyl群に関する多田の研究をもとに考案した，各箱に対して番号付けが与えられたYoung図形上で行う組合せゲームである「連続フック引き抜きゲーム」について紹介する． また，「山状番号付け」が与えられた長方形型Young図形を開始局面とする連続フック引き抜きゲームについて，各局面のGrundy数に関するいくつかの結果について紹介する．
8. 「52人でババ抜きしてみた」の一般化と特殊化：○岡本吉央（電気通信大学）
- 概要：削除ニム（Delete Nim）とは，石の山二つが与えられて，プレイヤーはいずれかの山を選び削除し，残りの山を分割して相手に手番を渡すという，ニムの変種である．着手できなくなった方が負け（正規形）として考えた場合，与えられた局面に必勝局面があるかどうかの判定や，その局面のSprague-Grudy数の値について，効率よく求める方法が知られている。本研究では，山の数を三つ以上にした場合について，いくつかのルールを提案し，それぞれの必勝局面の効率のよい判定方法について紹介する．
9. グラフマッチング型ゲームに対する必勝判定アルゴリズム：○吉渡叶（名古屋大学），木谷裕紀（九州大学），土中哲秀（名古屋大学），小野廣隆（名古屋大学）
- 概要：はじめしゃちょーの古いYouTube動画「52人でババ抜きしてみた」について考えたことを発表する予定です．ほぼできていないのですが，自分の手元でくすぶらせていてもしょうがないので，「考えたい問題の紹介」と「予想の紹介」がメインになると思います．
10. 一人ですべてのマッチョを笑顔にする声の掛け方に関する研究：○田崎鈴（九州工業大学），斎藤寿樹（九州工業大学）
- 概要：辺ケイレスは単純無向グラフ上で行われる2人ゲームであり，組合せゲーム理論で研究されていたケイレスを計算論的観点から一般化する形で，1978年Schaeferにより定義された．辺ケイレスでは各プレイヤは自分の手番において辺を1つ選択する．このとき選択された辺とその両端点，さらにその両端点に接続していた全ての辺は削除される．これを2人のプレイヤで交互に繰り返し，先に自分の手番で選択できる辺が無くなった方が負けである．辺ケイレスにはゲーム中に2人のプレイヤが選択した辺の集合が極大マッチングであるという特徴がある．また，辺ケイレスの非不偏ゲームを色付き辺ケイレスを定義すると，色付き辺ケイレスでゲーム中に2人のプレイヤが選択した辺の集合はマッチングである．同様の性質を持つゲームは他にもいくつか存在し，このようなマッチング構造を持つゲームを総称してグラフマッチング型ゲームと呼ぶことにする． 本研究ではグラフマッチング型ゲームに対する必勝判定アルゴリズムを提案する．はじめに，入力グラフの頂点数をnとしたとき，動的計画法に基づくO*(2^n)時間必勝判定アルゴリズムを設計する．このアルゴリズムは辺ケイレスのゲーム中に出てくる局面が常に入力グラフの誘導部分グラフであることを利用して，辺ケイレスの局面に関する再帰計算を行う．また色付き辺ケイレスに関しても，アルゴリズムの一部を修正することによりO*(2^n)時間で必勝判定可能であることを示す．さらに，上記のアルゴリズムに頂点被覆を利用した等価判定を加えて重複計算を省くことにより，入力グラフの頂点被覆数kに関するO*(1.1893^(k^2+6.340k))時間必勝判定アルゴリズムを提案する．最後に，入力グラフを木グラフに限定した場合，O(1.4143^n)時間で必勝判定が可能であることを示す．
11. タギロンのASP完全性：長尾篤樹（お茶の水女子大学），○芳賀朋恵（お茶の水女子大学）
- 概要：「そこまで絞るには眠れない夜もあっただろ」はマッチョ大会の会場でマッチョに掛け声をかけ，マッチョを笑顔にするカードゲームである． プレイヤーは手札の掛け声カードを使って，マッチョカードに掛け声をかけていく．声をかけられたマッチョは笑顔になり，一定回数の掛け声をかけられたマッチョは満足して退場していく． 通常，このゲームは複数のプレイヤーで行い，山札や他プレイヤーの手札がわからない不完全情報ゲームである．プレイヤーたちは順にマッチョに声をかけ，マッチョに掛け声を掛けられなくなったプレイヤーから脱落していき，最後まで声をかけ続けられたプレイヤーが勝利となる．本研究ではこのカードゲームを完全情報でかつ，一人で行う場合において，すべてのマッチョを満足させることができるかを判定するアルゴリズムを提案する．
12. Computational Complexity of Kirby：太田涼平（岩手大学）, 伊藤大修（岩手大学）, ○山中克久（岩手大学）, 平山貴司（岩手大学）
- 概要：本研究では論理ボードゲーム"タギロン"に関して、ASP完全性を示す。ASP完全性とは、ある問題の別解をみつける問題がNP完全であるという概念である。ASP完全性を示すためにはASP帰着という帰着を用いる。ASP帰着とは、帰着元の問題に対するインスタンスに加えてその問題に対する解も入力として与え、帰着先の問題のインスタンスおよび解に変換し、別解が存在するかどうかを出力する帰着である。この帰着は帰着元の問題がASP完全な問題である必要がある。 先行研究で、タギロンは一人ゲームに制限した”タギロン充足性問題”としてNP完全性が示されている。本研究では先行研究で定義されたタギロン充足性問題に対して、部分和問題からのASP帰着を示し、タギロンのASP完全性を証明する。また、部分和問題のASP完全性を示すために3-CNF-SATから部分和問題へのASP帰着も確認する。
13. スイッチギミックを備えたアクションゲームの計算複雑さの解明：〇橋本 雄輝（大阪電通大学），上嶋 章宏（大阪電通大学）
- 概要：We investigate the computational complexity of Kirby. Kirby is one of side-scrolling character action games. In this game, a player operates the character Kirby. He can walk, run, jump and ``hover'' by inhaling the air. More precisely, inhaling a lot of air makes Kirby light, then Kirby can repeatedly hover in the air. Our contribution is to show the computational complexity of Kirby. By applying the general framework by Aloupis et al., 2015 for showing PSPACE-hardness, we prove the PSPACE-completeness of Kirby.
14. パズルにおける仮置きの個数と埋め方の統計：○中島千尋（東北文化学園大学）
- 概要：本研究では，ビデオゲームの中でも特にスイッチギミックを備えたアクションゲームに注目し，3Dパズルアクションゲームである「Portal」，任天堂から発売された「ワリオランド」「ペーパーマリオ」「星のカービィSDX」の4つのビデオゲームの計算複雑さを解析する．具体的には，これらのうち前3タイトルのPSPACE完全性と，後者のNP困難性を証明する． PSPACE完全性の証明は，各ゲームで登場する様々なスイッチ機構等を駆使してガジェットを作成することで，TQBFからの還元を実現する．星のカービィSDXのNP困難性は，杭を叩くと特定のブロックが破壊される仕組みを主に使用し，3SATからの還元を示すことで証明する．
15. YOMENの解空間サイズとヒント数：○平野巧稀（名古屋大学），木谷裕紀（九州大学），土中哲秀（名古屋大学），小野廣隆（名古屋大学）
- グラフの3彩色問題などを例に、1人で解くパズルに関して統計力学的手法による数値解析により彩色の仕方（埋め方）の総数など統計的な性質を調べ、仮置きの個数等に対してどう振る舞いが変わるかなどを示し、パズルを解く難しさにどう関連するかを議論する。
16. 確率的Mullerゲームにおける非協調的合成問題：○小出走（名古屋大学），関 浩之（名古屋大学）
- 概要：YOMENは2020年に発売されたコード推理型ゲームであり，推理の対象は色付きブロックの配置である．本発表ではYOMENの解空間のサイズの見積もりとヒント数に関する考察を紹介する．
17. レプ・タイルの定式化を用いた各種ソルバの性能比較：番原 睦則 (名古屋大学)，橋本 健二 (名古屋大学)，堀山 貴史 (北海道大学)，湊 真一 (京都大学)，中村 駆 (北陸先端科学技術大学院大学)，西野 正彬 (日本電信電話株式会社)，酒井 正彦 (名古屋大学)，○上原 隆平 (北陸先端科学技術大学院大学)，宇野 裕之 (大阪府立大学)，安田 宜仁 (日本電信電話株式会社)
- 概要：多プレイヤー非ゼロサムゲームをモデルとして，合理的に行動する複数のコンポーネント(環境)に対するシステムの合成問題が研究されている.このモデルは，環境がシステムに対し完全に敵対的とは限らず，独自の目的を持つという状況を表現できる.このモデルには協調的合成問題と非協調的合成問題とがある.一方，金融市場などの多くの応用においては，自然手番の存在(プレイヤーの行動以外の要因による確率的な状態遷移)と環境の非協調性の両方の概念をもつ枠組みが必要となると考えられるが，そのような設定での理論的研究がなされていない.本研究では，確率的多プレイヤー非ゼロサムゲームの非協調的合成問題を定義した．そしてこの問題は，Mulle目的，無記憶純粋戦略のもとで，Σ^p_2完全であることを示した．また，非確率的ゲームにおいては Σ^p_2可解，NP困難であることを示した.
18. d次元ポリキューブ詰込み問題の定数時間検査アルゴリズム：○南保 敦（電気通信大学），伊藤 大雄（電気通信大学）
- 概要：レプ・タイルとは，うまく分割すると自分自身と相似な複数の合同図形に分割できる図形のことをいう．またポリオミノとは，単位正方形を辺同士接着することで得られる多角形のことをいう．これらの概念は1950年代にソロモン・ゴロムが導入・研究し，1960年代にマーティン・ガードナーによって広く知られることとなった．それ以来，レクリエーション数学やパズルのコミュニティで広く親しまれている．本研究では，よく知られた3種類のポリオミノのレプ・タイルに焦点をあてる．ポリオミノのレプ・タイルは単純で定式化も容易であるため，多くのソルバで自然な形で定式化して解かせることができる．つまり異なるソルバを比較するための共通の基盤としての役割を果たすことができる．本研究では，共通のレプ・タイルを代表的なパズルソルバ，整数計画ソルバ，SAT系ソルバで解くことを試みた．結果として，こうした単純なパズルを解くという課題においては，パズルソルバが最も解く能力が低く，SAT系ソルバが最も強力であることが明らかになった．さらに，ソルバによって見つかったいくつかのレプ・タイルの性質を活用し，かなり大きなサイズにまで，特定のレプ・タイルの完全解析に成功した．これは50年以上にも及ぶこれらのレプ・タイルの解析に終止符をうつ結果である．
概要： ポリキューブとは、複数の単位立方体の面同士を辺が一致するようにつなぎ合わせて作られる図形である。与えられた空間（立方体など）に複数の与えられたポリキューブを隙間やはみ出しなくすべて詰込むことを目的としたパズルが存在し、ここではこのパズルをポリキューブ詰込み問題と呼ぶ。一般的に解かれているポリキューブ詰込み問題は、ソーマキューブやベドラムキューブなどがある。 また、定数時間アルゴリズムとは入力のデータサイズに依存しない定数個のデータしか読まずに結果を出すアルゴリズムであり、ビッグデータを扱うのに適していることから近年注目を浴びつつある。これまでに将棋、チェスなどのボードゲームや、ライツアウト、ポリオミノ、四角に切れなどのボードパズルに対する定数時間アルゴリズムが存在することが示された。 本発表では、ポリキューブ詰込み問題を任意の次元上で扱うパズルの問題として拡張し、この問題に対して与えられた入力が解を持つのかどうかを検査する定数時間アルゴリズムが存在することを示す。
世話役 伊藤大雄（電気通信大学）、岡本吉央（電気通信大学）、長尾篤樹（お茶の水女子大学）