１日目：３月２日（月）
10:10 -- 11:30
1. ナンスケに対する物理ゼロ知識証明プロトコル
糸山 凌，大舘 陽太（熊本大学）
2. ペンシルパズル「ぬりみさき」の物理的ゼロ知識証明
齊藤 孝一（電通大）
3. 波及効果の物理的ゼロ知識証明プロトコル
村上 航輝，上嶋 章宏（大阪電通大）
4. 麻雀を用いた安全な計算のプロトコル設計
坂本 充，安藤 立紀，吉田 泰大，上嶋 章宏（大阪電通大）11:30 -- 13:30 昼休み
13:30 -- 14:30 招待講演
5. 学習曲線と努力曲線による学習軌跡の読み方
丸岡 章（東北大学）15:00 -- 16:00
6. n面ダイス設計問題
金谷峻介、伊藤大雄（電通大）
7. 歪んだコインで公平なコインを模倣する最適アルゴリズム
上野洸史，上原隆平 (JAIST)
8. ビー玉多面体の研究
鎌田斗南，谷口智子，上原隆平 (JAIST)16:30 -- 17:30
9. 4x4 最弱オセロに対する最強戦略
小笹稜太、木谷裕紀、小野廣隆
10. 不完全情報単貧民における最適戦略
木谷 裕紀、大渡 勝己、小野 廣隆
11. 異手間引分有一般化ジャンケンの無駄手と面白さの解析
鈴木健太、伊藤大雄（電通大）
２日目：３月３日（火）
10:10 -- 11:30
12. 一意的ハミルトニアングラフとSheehanの予想
坂本涼太（電通大）
13. ペンシルパズル「Fill-a-Pix」の作問に関する諸問題の計算複雑性
樋口雄太（豊橋技科大）、木村慧（埼玉大学）
14. ぷよを自由に配置できるぷよぷよの連鎖数判定問題: 色数制限を課した場合
澁谷 諒祐（豊橋技科大）, 木村 慧（埼玉大）
15. 全消し詰めテトリス問題の列挙と検討
三浦月代、橋本剛（松江高専）11:30 -- 13:30 昼休み
13:30 -- 14:30
16. Steiner systemの組合せゲーム分布
入江佑樹（東北大学）
17. 全象（universal）ルールと帰着手法
末續鴻輝（国立情報学研究所）
18. ケーリーグラフ上のNimについて
安福智明（筑波大学）15:00 -- 16:00
19. Triangle Origami Checkerboardパズルの最適解探索
大島和輝（筑波大学）、上原隆平（JAIST）、三谷純（筑波大学）
20. 正三角形ブロック, 正三角形盤面における小規模なスライドパズルの全列挙
川上 直人, 上原 隆平 （JAIST）
21. ライツアウトパズルの解の形状
片又佑美（津田塾大学）
1. ナンスケに対する物理ゼロ知識証明プロトコル：糸山 凌，大舘 陽太（熊本大学）
2. ペンシルパズル「ぬりみさき」の物理的ゼロ知識証明：齊藤 孝一（電通大）
概要：ナンスケとはクロスワードに似たペンシルパズルで，与えられた数字の列すべてを
ルールに従って盤面に配置するものである．本研究では，ナンスケに対してカードや封筒を
用いた物理ゼロ知識証明プロトコルを提案する．３. 波及効果の物理的ゼロ知識証明プロトコル：村上 航輝，上嶋 章宏（大阪電通大）
- 概要：ゼロ知識証明とは対話的証明のひとつであり，証明者はある問題に対する解の存在を，
その解に関する情報を公開することなく証明できる．本研究ではペンシルパズルの中でも俗
に「分断禁」というルールを持つぬりみさきに注目し，ぬりみさきの解に対する物理的なゼ
ロ知識証明の方法を提案する．分断禁は「同じ色で塗られたマスが，全体で縦横に連結して
いなければならない」というルールであり，そのまま検証するのは難しい．そこで田村（2008）
が提案した有向木を作成する手法を応用し，分断禁を検証する方法を考案した．
- 概要：本研究では，ペンシルパズルの1つである波及効果のゼロ知識証明に対す る物理プロトコルについて議論する． 波及効果は，いくつかの領域（部屋と呼ぶ）に分割されたn×nの盤面を 入力とする．各部屋を構成するマス数k'をその部屋のサイズと呼び，部 屋のサイズの最大値をkとする．下記ルールに従い盤面の各マスに1から kまでの数字を入れていくパズルである．
波及効果には2つのルールがあり，1つ目のルールは「サイズk'の部屋に 1からk'までの数字を1つずつ入れる」，2つ目のルールは「縦方向か横 方向に同じ数字を入れる場合は，その数字分のマス数以上離す」という ものである．
カードなどの物理的で身近なアイテムを用いて，物理的な手順でゼロ知識証明を設計する研究は様々なパズルに対して行われている．本発表では波及効果に対して設計したゼロ知識証明を実現するカードベースのプロトコルを紹介する．4. 麻雀を用いた安全な計算のプロトコル設計：坂本 充，安藤 立紀，吉田 泰大，上嶋 章宏（大阪電通大）
5. 学習曲線と努力曲線による学習軌跡の読み方：丸岡 章（東北大学） 招待講演
- 概要：本研究では，麻雀を用いて安全な計算を実現するプロトコルを設計す る．この麻雀プロトコルでは，初期配置としてツモ山・手牌と呼ばれる ものを用意し，各プレイヤーはツモ山と手牌に対し，自分の持つ情報に よって何らかの操作を行う．最後に手牌の状態から，真または偽の出力 を得る．ツモ山と手牌をあらかじめ作為的に用意することや，操作手順 や出力を得る方法によって，正確性・安全性を満たしている．
本研究では，麻雀牌1セットの範疇でツモ山と手牌1組を用意し，国士 無双を用いた51変数までの対称関数の安全な計算，国士無双を用いた5変 数までの一般の関数の安全な計算，九蓮宝燈を用いた29変数までの対称 関数の安全な計算，七対子を用いた67変数までの対称関数の安全な計算 を行うプロトコルを設計した．さらに，麻雀のゲーム進行に似せて4組の 手牌を用意した場合での七対子を用いた4変数までの対称関数の安全な計 算，役の翻数を用いた4変数までの対称関数の安全な計算が行えるプロト コルを設計した．本発表では，麻雀の様々な役を用いて安全な計算が行 えることを示す．
キーワード -- アンチスライドパズル; 整数計画問題; IPソルバ; パズル6. n面ダイス設計問題：金谷峻介、伊藤大雄（電通大）
- 概要：学習によるパフォーマンスの向上に関する2つの結果を示す。
前半では、被験者の集中度(努力)を数値化したbehavior-based entropyの 尺度を導入する。障害物の置かれていないすべてのコマを1度ずつ通り格子面のス タートのコマからゴールのコマに至るルートを描くルート探索問題を被験者に解か せる実験を行い、各セッションの正答数から学習曲線を描き、プラトー(plateau) から急激な上昇が起こるまでのセッションではbehavior-based entropyが高く、 それ以降のセッションでは低いことを明らかにする。この結果より、学習によりコツ をつかんだ後は、わずかな努力で高いパフォーマンスを維持できるという現象を説明 することができる。
後半では、学習曲線の急激な上昇が起きるのは、被験者のルート検索の戦略の転換 によることを示唆する結果を示す。そのために、被験者の動作を試行錯誤アクション とそれまでに描いたルートの部分パスを思い出す想起アクションとしてモデル化して シミュレーションし、急激にパフォーマンスが改善するのは、試行錯誤アクション から想起アクションへの転換によるということを導く。さらに、実験による学習曲線 とシミュレーションによる学習曲線がほぼ一致していることより、このモデル化の 妥当性の一端が示される。7. 歪んだコインで公平なコインを模倣する最適アルゴリズム：上野洸史，上原隆平 (JAIST)
- 概要：任意の面数を持つサイコロを設計する方法として球体モデルとコインモデルの二 つ(上原ら, 2018)が提案されたが, コインモデルによる設計は先行研究である厚 みのあるコイン問題の数理モデルが適用できないことを確認したため, 上原らは 実際に試行を繰り返し実験データを集めることで正角柱による13面ダイスを作成 した.本研究では同様の実験を切頂四面体の面積比を変化させた立体について行 い, それぞれの面の確率と面積の比, 重心との距離の関係式の推測を試みた. また, サイコロの目の配置に関する問題について理想的な配置のひとつに数均衡 ダイス(Boschら, 2017)が提案されている. 本研究では正多面体及びカタランの 立体について数均衡ダイスであるかどうか確認した. その結果, 正二十面体以外 の正多面体及び五方十二面体以外のカタランの立体による数均衡ダイスは存在し ないことがわかった.
8.ビー玉多面体の研究：鎌田斗南，谷口智子，上原隆平 (JAIST)
- 概要：歪んだコインで公平なコインを模倣する最適アルゴリズム 概要：表の出る確率が不明な歪んだコインが手元にあったとしよう． このコインを用いて公平なコインを模倣する「フォン・ノイマンのアルゴリズ ム」が良く知られている．具体的には，コインを2回投げて，HTだったら「表」， THだったら「裏」として，それ以外の場合はコインを振り直すものである． これはあまり効率の良いアルゴリズムではなく，コイントスの回数の期待値は， もっと減らすことができる．こうしたコイントスアルゴリズムのコイントスの 回数の期待値に関する理論的な下界と上界を示し，小数点以下15桁まで下界と 一致する，効率の良いアルゴリズムを構築した．
9. 4x4 最弱オセロに対する最強戦略：小笹稜太、木谷裕紀、小野廣隆
- 概要：ケプラー予想によると，ビー玉を細密充填する方法は，本質的には「自 然な積み方」しかない．しかしこの自然な積み方は，層レベルで見ると「立方 細密充填」と「六方細密充填」とがあり，バリエーションが無限に考えられる． そして，この積み上げた構造の中を観察すると，ビー玉を頂点とする多面体構 造が数多くあることがわかる．例えば正４面体や正８面体は，ビー玉を積み上 げながら接着すれば，簡単に作ることができる．また一方で正３角形，正方形， 正６角形は作れるが，そのままでは立方体は作れない．こうした「積み上げた ビー玉」から構成できる立体の分類と拡張について発表する．
10. 不完全情報単貧民における最適戦略：木谷 裕紀、大渡 勝己、小野 廣隆
- 概要：最弱オセロとは，通常のオセロのルールの下，最後に残ったコマの色をより少なくした方が勝ちとなるものである．本研究では4x4最弱オセロに対する必勝戦略を与える．
11. 異手間引分有一般化ジャンケンの無駄手と面白さの解析： 鈴木健太、伊藤大雄（電通大）
- 概要：単貧民とはトランプゲーム大貧民を簡易化したゲームである。本研究では、不完全情報で行う単貧民ゲームにおいて、有効な戦略の存在性について考察する。
12. 一意的ハミルトニアングラフとSheehanの予想：坂本涼太（電通大）
- 概要：ジャンケンの同型や類型は国内外に多数存在する. 伊藤[TJJCCGG, 2013]はフラ ンスに存在する4手のジャンケンに出す意味の無い「無駄な手」があることに 着目し, ジャンケンにおける無駄な手となる条件やジャンケンの面白さを数値的 に定義し, それの最大値を与えた. この研究の派生として, 2種類の研究がおこな われている. 1つはジャンケンの定義を異なる2手間の引分けも許すように拡張し て, 無駄手の再定義や, 面白さが最大となるジャンケンの構成法について研究し たもので, 面白さの最大値は発見されていない. もう一つの研究では,ジャンケン の合成という手法を用いて伊藤の考案した異手間引分無一般化ジャンケンの最適 戦略の解析がおこなわれた. 本研究はこの2つをより発展させ, 面白さが最大とな る異手間引分有ジャンケンの構成法の解析, 引分けを考慮した新たなジャンケン の面白さの提案, 異手間引分有ジャンケンの最適戦略の考察をおこなった.
13. ペンシルパズル「Fill-a-Pix」の作問に関する諸問題の計算複雑性：樋口雄太（豊橋技科大）、木村慧（埼玉大学）
- 概要：パズルゲーム"Fill"を代表として，すべてのマスを一度ずつ経過する道筋を探す ことを目的としたパズルをしばしば見かける．当ゲームは「一筆書き」と謳っているが， 一般的な一筆書きとは異なり，ハミルトンパスを求める問題となる． ハミルトンパス問題とハミルトン閉路問題の間には密接な関係があり，さらにパズル ゲームでは解を一意に持つことが慣習としてあるため，ここではグラフの性質と ハミルトン閉路の一意性について考える． この話題については，1946年にSmithが「３正則グラフにハミルトン閉路が存在するとき， 少なくとも３つのハミルトン閉路が存在する」ことを示して以降，様々な研究がなされて きた．しかしこれによく似る，Sheehanが唱えた予想は45年の間未だに解決されていない． この予想に対して多角的なアプローチをする．
14. ぷよを自由に配置できるぷよぷよの連鎖数判定問題: 色数制限を課した場合：澁谷 諒祐（豊橋技科大）, 木村 慧（埼玉大）
- 概要：Fill-a-Pixは，Trevor Truran氏により考案，Conceptis社により2003年に開発されたペンシルパズルである．いくつかのマスに0〜9の数字が表出された長方形の盤面として問題が与えられ，盤面上の数字はそれが書かれたマス自身とその周囲の合計9マスのうち何マスを黒で塗りつぶすかを示す．この数字のヒントに従い，盤面の全てのマスを白か黒で塗り分け，絵や文字を浮かび上がらせることがこのパズルの目的である． 本研究では，Fill-a-Pixの作問に関わる諸問題の計算複雑性を取り扱った．Fill-a-Pixに限らず，ほとんどのペンシルパズルにおいては，解が一意である必要性があるため，「解の一意性の検証」，「解が一意になるようにインスタンスを修正」，「解が一意なインスタンスの生成」に対する計算複雑性について考察した．解の一意性の検証の複雑性として，与えられたインスタンスと解に対し別解が存在するかを判定する，別解問題(ASP)のNP完全性と，与えられたインスタンスの解の個数を数え上げる，解の数え上げ問題の#P完全性を示した．また，インスタンス修正の複雑性として，与えられたインスタンスと非負整数kについて，k個以下の解への割り当てを与えて解を一意にできるかを判定するヒント数最小化問題(FCP)のΣ2P完全性を示した．さらに，インスタンス修正という観点でより自然な問題設定として，与えられたインスタンスと非負整数kについて，k個以下の表出制約の追加によって解を一意にできるかを判定する追加制約数最小化問題を提唱し，そのΣ2P完全性を示した． 本講演では，解が一意であるインスタンスの生成の計算複雑性を中心に取り扱う．Fill-a-Pixのような絵を出すことを目的としたパズルの作問のプロセスとして，まず解となる絵柄を作成し，それに対応するインスタンスを作成するという手順が考えられる．そのため，「入力された解に対し，解が一意かつ入力のものに一致するようなインスタンスが存在するか」を判定する，インスタンス生成可能性問題と，さらに表出制約k個以下という条件を追加した最小制約インスタンス生成問題を提唱する．そして，Fill-a-Pixのインスタンス生成可能性問題がco-NPに含まれ，盤面のサイズによってはPに含まれることを示す．
15. 全消し詰めテトリス問題の列挙と検討：三浦月代、橋本剛（松江高専）
- 概要：ぷよぷよとは"ぷよ"と呼ばれる色のついたブロックを盤面に配置し, ぷよを上下左右に4つ繋げることで消してゆくパズルゲームである．消えたぷよの上にぷよがある場合，それらは落下するため, 連続してぷよが消えることがある．このようにぷよが連続して消える現象を連鎖といい，高得点を得るためには長い連鎖を起こすようにぷよを配置することが求められる． 通常, プレイヤーは逐次的に与えられる2つ組のぷよ（ピース）を操作して盤面へ配置するが, 今回扱う問題設定では初期盤面のみが与えられ, 盤面の空いているマスに好きな色のぷよを配置することができる. この特殊ルールにおける最大連鎖数は通常ルールの各盤面における最大連鎖数の上界を与える. 既存結果として, この特殊ルールにおける連鎖数判定問題はNP完全であることを2年前の本研究集会で発表した.しかしながら, 同結果では使用できる色数に制限を与えていなかった. 今回は使用できる色数を14に制限した場合にも同問題がNP完全であることを3-PARTITIONからの帰着により示す. また, 初期盤面がすべて空白マスのとき, 使用できる色数がα(≧4)ならば同問題が多項式時間で解けることを示す. なお, 使用できる色数が2,3の場合については部分的に得た結果を報告する.
16. Steiner system の組合せゲーム分布：入江佑樹（東北大学）
- 概要：詰め将棋や詰碁などのように、近年デジタルゲームを題材とした詰め問題がいくつか研究されている。本稿ではテトリスを題材とし、 特に全消し詰めテトリス問題について検討する。n手全消し詰めテトリス問題を定義し、その列挙アルゴリズムを提案し、実装を行う。実験では作成された問題を紹介し、統計的特徴や面白さについて検討する。
17. 全象（universal）ルールと帰着手法：末續鴻輝（国立情報学研究所）
- 概要：Steiner system の組合せゲーム分布 概要: ゲームの必勝局面全体はとても良い組合せ構造を持つことがある。 例えば、Conway と Ryba はヘキサッドゲームというゲームの必勝局面全体が、 Steiner system S(5, 6, 12) という特別な構造を持つことを示した。それでは 一般に必勝局面全体が与えられた Steiner system になるゲームは存在するのだろうか？ 本講演ではそのようなゲームが構成できることを紹介する。この構成を用いると、 S(5, 6, 12) からは 5040 個のゲームが得られ、その中でヘキサッドゲームは 局面数が最小となる唯一のゲームとして特徴付けられる。さらに、Steiner system から得られるゲームの局面数による度数分布（組合せゲーム分布）を用いることで、 射影的 Steiner triple system を特徴付ける。
18. ケーリーグラフ上のNimについて：安福智明（筑波大学）
- 概要：組合せゲーム理論において，すべてのゲームの値を局面として 持つルールを全象（universal）ルールと呼ぶ．全象ルールはこれまでに "コナネ"が唯一発見されており，発表者は最近，新たな全象ルールとし て"タイル返し"を発見した．さらに計算複雑性の研究でよく用いられる 手法である帰着手法を用いて，"Go on lattice"が全象ルールであることも 証明した．これらの背景を踏まえ，本発表では全象性の証明に関する帰 着手法の有用性について議論を行う．
概要：次のゲームを考える．与えられたグラフの頂点に石がいくつかあり，ある1つの頂点に駒が1つおいてある．プレイヤーはそのコマを隣接頂点に動かす．その際，元いた頂点にある石をいくつか減らす．2人のプレイヤーが交互に駒を動かし，先に駒を動かせなくなったプレイヤーの負けである．このゲームをケーリーグラフ上で行うことを考え，そこで得られた必勝判定についての結果をいくつか紹介する．
19. Triangle Origami Checkerboardパズルの最適解探索：大島和輝（筑波大学）、上原隆平（JAIST）、三谷純（筑波大学）
20. 正三角形ブロック, 正三角形盤面における小規模なスライドパズルの全列挙：川上 直人, 上原 隆平 （JAIST）
- 概要：表裏色違いの正三角形の紙を折り、できるだけ少ない折りの回数でサイズ3の 正三角形パターンを出現させることを目的とするTriangle Origami Checkerboardというパズルがある (「サイズn」は単位正三角形がn段に積み重なった大きさの正三角形のことを指す)。 このパズルのゴールとなるパターンは59通りあり、全パターンに対する折り手順が 人間の試行錯誤により発見されていたが、それらよりも短い手数の折り手順が存在するかどうかは 明らかでなかった。発表者らは、スーパーコンピュータを用いて、開始サイズが4から7の場合は 7手まで、8と9の場合は5手までの範囲で、パズルの解となる手順の列挙を試みた。 その結果、16種類のパターンに対して既知のものよりも効率の良い手順を発見した。
21. ライツアウトパズルの解の形状：片又佑美（津田塾大学）
- 概要：スライドパズルは, 15パズルなど, 盤面上の全ブロックを「スライド」という移動操作によって目的位置へ移動させる, 古典的なパズルである. ここで, スライドを空白との交換操作とみなせば、正方形に限らず、例えば正三角形を用いた三角格子上のスライドパズルも考えることができる. 本研究では, 正三角形ブロック, 正三角形盤面を用いたスライドパズルについて, 全列挙をおこない, 完成可能なパターン数などの調査をおこなう. 現在, 全列挙によって, 大きさ3の正三角形盤面, 大きさ1の正三角形ブロック8個で構成されたスライドパズルについて, 完成可能なパターンは45通り（全体の1/8064）, 最短手数の最大値は16, といった結果が得られている. 完成可能条件（パリティー）については, 調査中である.
- 概要：ライツアウトパズルは人気のあるパズルであり、多くの研究者により研究されてきた。 その研究の多くは可解性や解の個数、つまりラプラシアンの階数に関するものである。 本報告ではK. Sutner氏により可解性が証明されたall one problem、つまり、 全点灯の初期状態に対する解の幾何学的形状がどうなるか、数種類のライトの配置 （タイル張り）についての計算結果を紹介する。 作成したパズルのURL： https://pro4-12b05.firebaseapp.com/
世話役 伊藤大雄、岡本吉央（電気通信大学）