09:30--10:20 (25min x 2)
- 1. スライディングブロックパズルを用いた画像再構築
- 牧田純弥 (中央大学 理工学部 情報工学科)
- 2. SATソルバを用いたSpiral Galaxies Puzzlesの解法ツール
- 舟野 勝彦，上嶋 章宏 (大阪電気通信大学 大学院 工学研究科)
10:30--11:45 (25min x 3)
- 3. タントリックスの整数計画法による解法
- 木野 歩佳, 宇野 裕之 (大阪府立大学)
- 4. ZDDのリンクパズルへの応用
- 川原純，斎藤寿樹，鶴間浩二，湊真一，○吉仲亮 (JST ERATO)
- 5. 二分決定グラフを用いたお絵かきロジックの複数解の検出
- 堀山貴史 (埼玉大学)
11:45--14:00 昼休み
14:00--14:50 (25min x 2)
- 6. 色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性
- 木場 裕矢*，宗重 成央**，上嶋 章宏* (*大阪電気通信大学 大学院 工学研究科, **大阪電気通信大学 情報通信工学部 情報工学科)
- 7. ランキングSVMを用いたコンピュータ将棋における評価関数の学習
- 末廣大貴（九州大学）
15:00--15:50 (25min x 2)
- 8. 半順序集合ゲーム周期性定理の拡張
- ○後藤順一、伊藤大雄（京都大学 大学院 情報学研究科）
- 9. ハラリィの一般化三並べの変種 --- 共喰い動物ゲーム
- Jean Cardinal*, Sebastien Collette*, 伊藤大雄**, Matias Korman*, Stefan Langerman*, ○堺谷光**, Perouz Taslakian* (* Department of Computer Science, Universite Libre de Bruxelles, ** 京都大学 大学院 情報学研究科)
16:00-16:50 (25min x 2)
- 10. 単位円板による点集合の排他的被覆問題
- 岡山陽介，清見礼，○上原隆平 (北陸先端科学技術大学院大学)
- 11. フレームで凸体をつかむ
- 徳重典英 (琉球大学教育学部)
17:00--17:50 (25min x 2)
- 12. Hoffmanパズルの拡張とその解析
- 後藤新，上原隆平 (北陸先端科学技術大学院大学)
- 13. ある帽子ゲームとその変種について
- 岡本 吉央 (北陸先端科学技術大学院大学)
1. スライディングブロックパズルを用いた画像再構築：牧田純弥 (中央大学 理工学部 情報工学科)
本研究では，２つの画像を入力し，スライディングブロックパズルを生成するシステムを構築
する。このシステムは，一方の画像を分割し並び替えることで，他方の絵を近似し，これをパ
ズルの初期配置とする。良い並び替えを求める問題を割当問題に定式化し, これを解いている。
また, 得られたパズルを解く解法を実装し, 実際の必要手数の確認を行った。
2. SATソルバを用いたSpiral Galaxies Puzzlesの解法ツール：舟野 勝彦，上嶋 章宏 (大阪電気通信大学 大学院 工学研究科)
- ペンシルパズルのひとつであるSpiral Galaxies Puzzles（SGP）は
NP完全に属する問題である．SGPは，格子状の盤面とその上に配
置された円の集合が入力として与えられ，各円を中心とした連結な
点対称図形で盤面を分割するパズルである．
本発表では，SGPが持つ制約条件を表現するCNF論理式を構成し，
SATソルバを用いてSGPを解く手法を述べる．SGPからSATへ符号化す
る際，各点対称図形の連結性チェックを管理する論理式のサイズが
全体の大部分を占め，連結性の符号化法の工夫が計算時間にも影響
を与えると考えられる．本発表では，そのような論理式サイズの削
減手法についても述べ，論理式サイズと計算時間についての評価を
示す．[発表資料(pdf)]
3. タントリックスの整数計画法による解法：木野 歩佳, 宇野 裕之 (大阪府立大学)
- タントリックスというパズルを計算機で解くことを考える.
そのためにまず2種類の問題設定を与え, その上でそれらを整数計画問題として定式化する.
最後に, 数理計画ソルバを用いて解いた結果を提示する. [発表資料(pdf)]
4. ZDDのリンクパズルへの応用：川原純，斎藤寿樹，鶴間浩二，湊真一，吉仲亮 (JST ERATO)
ナンバーリンクやスリザーリンクといったパズルは，与えらたグラフから特殊な
条件を満たす次数２以下の部分グラフを抽出するようなタイプの制約充足問題であり，
これらをリンクパズルとして包括的に理解される．
本発表では， Knuth による ZDD を用いたパスの列挙アルゴリズムを発展させ，
これらのリンクパズルに関する諸問題に応用する手法を提案する．一例として，
スリザーリンク問題の解決アルゴリズムを実装し，既存の解決アルゴリズムと比較する．
我々の手法は，他のリンクパズルにも応用可能である他，さらに，問題の生成等，
他の関連諸課題にも応用される．[発表資料(pdf)]
5. 二分決定グラフを用いたお絵かきロジックの複数解の検出：堀山貴史 (埼玉大学)
お絵かきロジックは、各行および各列に与えられた制約数を満たす
ように２次元格子上のマスを白黒に塗り分ける問題である。本発表
では、二分決定グラフ (BDD: Binary Decision Diagrams) を用いて
お絵かきロジックを解く方法を示す。この手法では、制約条件それ
ぞれを BDD により表し、それらの論理積を計算することで、すべて
の制約条件を満たす解の BDD を得る。この BDD は、全制約条件を
満たす解すべてを保持していると捉える事ができるため、グラフを
たどって解の個数を数えることで、解の一意性を容易に保証するこ
とができる。[発表資料(pdf)]
6. 色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性：木場 裕矢*，宗重 成央**，上嶋 章宏*(*大阪電気通信大学 大学院 工学研究科, **大阪電気通信大学 情報通信工学部 情報工学科)
- 本研究ではパズルゲーム“ぷよぷよ”を一般化した，一般化ぷよぷよ
の連鎖数判定問題の未解決問題について扱う．連鎖数判定問題とは，
入力として初期盤面，ピースの列，正整数kが与えられ，k連鎖可能か
判定する問題のことである．
先行研究では，3-PARTITIONからの多項式時間還元において，4色の色
ぷよとおじゃまぷよを用いてNP完全性を証明していたため，4色より少
ない色数やおじゃまぷよを用いない制限での計算複雑さは未解決となっ
ていた．本発表では，先行研究における還元手法を工夫し，色数を3色
に制限した場合と，おじゃまぷよを用いず色数を5色に制限した場合の
NP完全性を証明する．前者については，先行研究において4色の色ぷよ
を使用している還元部品の，3色で再構成を実現することで証明でき，
後者については，3色に制限した還元手法を元に，おじゃまぷよの代わ
りとして絶対に消滅しない位置に色ぷよを配置することにより証明した．
[発表資料(pdf)]
7. ランキングSVMを用いたコンピュータ将棋における評価関数の学習：末廣大貴（九州大学）
近年、将棋における評価関数の設計は、機械学習を用いたものが主流と
なっている。ただし、評価項目（特徴）は作成者の棋力、感覚に基づい
て用意されることが多く、これまで複雑な特徴が数多く提案されてきた。
本研究では、SVMとカーネル法を用いた評価関数の学習方法を提案する。
カーネル法を用いることで、将棋に必要である複雑な特徴を、明示的に
用意せずに学習を行うことができる。また、評価関数の学習問題を、合
法手後の局面を順位付けるランキング問題ととらえ、SVMを用いて学習を
行う手法を提案する。[発表資料(pdf)]
8. 半順序集合ゲーム周期性定理の拡張：後藤順一、伊藤大雄（京都大学 大学院 情報学研究科）
半順序集合ゲームは、ニムを含むゲームのクラスである。盤面とし
て非閉路的有向グラフ（ダグ）が与えられ、二人のプレイヤーが交
互に節点を選んでいく。その際、選ばれた節点とその子孫を盤面か
ら除去してゆき、最後の節点を選択したプレイヤーが勝ちとなる。
このゲームに対してS. Byrnesが2002年に与えた周期性定理では、
二本の無限に伸びうるチェーン以外は定数サイズである半順序集合
ゲームに対して、任意のグランディ値の出現がチェーンの長さに対
して周期性を持つことが証明された。我々はその定理を拡張し、
チェーン上の各節点を、ある条件を満たすダグで置き換えた場合に
も周期性定理が成立することを示す。[発表資料(pptx)]
9. ハラリィの一般化三並べの変種 --- 共喰い動物ゲーム：Jean Cardinal*, Sebastien Collette*, 伊藤大雄**, Matias Korman*,Stefan Langerman*, 堺谷光**, Perouz Taslakian* (* Department of Computer Science, Universite Libre de Bruxelles, ** 京都大学 大学院 情報学研究科)
- ハラリィの一般化三並べは，碁盤状の盤面に先手、後手が交互に一つずつ
石を置き、予め定めされたポリオミノ（動物とよぶ）を作ることができた
プレイヤーが勝ちというゲームである。本研究では、このハラリィの一般
化三並べをさらに変化させた、共喰い動物ゲーム（Cannibal Animal Games）
というゲームを提案する。このゲームは、無限盤面上で行われ、先手は一
手で一つの石を置くが、後手は指定された動物そのものを一手で置く。こ
れを交互に繰り返し、先手が目標の動物を作ることができれば先手の勝ち。
後手の目標はこれを防ぎ続けることである。本ゲームはハラリイの一般化
三並べにおいて成立した単調性が無く、その分、解析が複雑となっている。
研究の結果、いくつかの勝ち型と負け型を明らかにした。その過程で、先
手の「囲い込み戦略」、後手の「ペアリング戦略」、さらに既存の負け型
から新しい負け型を作ることのできる「穴明け補題」など、このゲームの
解析に有用な道具を開発した。[発表資料(pptx)]
10. 単位円板による点集合の排他的被覆問題：岡山陽介，清見礼，上原隆平 (北陸先端科学技術大学院大学)
2009年に稲葉が「任意の10点の点配置は単位円で排他的に覆うことができる」
という証明を与えた．この証明は確率的方法によるもので非常に独創性がある．
一方で「任意のk点の点配置は単位円で排他的に覆うことができる」という問
題そのものも非常に興味深い．このkの上界はいくつだろうか．上原・浅野の
簡単な考察により「単位円をどう配置しても覆えない」108個の点配置が与え
られた．その後，Peter Winkler により60個の点配置が与えられ，さらに最近，
Veit Elser により55個の点配置が与えられた．本発表では，岡山陽介，清見
礼，上原によって得られた54個の点配置について紹介する．[発表資料(pdf)]
11. フレームで凸体をつかむ：徳重典英 (琉球大学教育学部)
針金を曲げて作った平面上の閉曲線をフレームという。立体にフレームを取り付けて
持ち運べるだろうか。球はどんなフレームをつけても滑り落ちてしまってつかめない。
Zamfirescuはほとんどの凸体は円形フレームでつかめることを示した。我々は、
三角形フレームがつかめる凸体はないこと、および、三角形でないどんな凸フレーム
もある四面体をつかめる（だけでなく固定できる）ことを示した。これらの結果について
報告する。この発表は Imre Barany, 前原闊との共同研究に基づくものです。[発表資料(pdf)]
12. Hoffmanパズルの拡張とその解析：後藤新，上原隆平 (北陸先端科学技術大学院大学)
- Hoffmanパズルとは，大きさa×b×cのブロック27個を大きさ(a+b+c)×(a+b+c)
×(a+b+c)の箱に詰め込むパズルで，とても難しいパズルとして知られている．
これは1978年にHoffmanにより提案され，1981年にConwayとCutlarが21通りの
解があることを示した．Hoffmanパズルでは(a+b+c)/4<a<b<cを満たす任意の
(a,b,c)に対してパズルが成立する．2004年，Knuthはこの条件を
(a+b+c)/4=a<b<cにしたパズル(以下HKパズルとする)を考案した．Knuth は
4a=(a+b+c)が成立することを利用して，28個目のブロックが入ることを示した．
2005年にGeorge Millerがパズル作家の閉じた会議(IPP)でこのHKパズルを配布
したが，講演者の知る限りではあまり広くは知られていない．本発表では，
後藤新と上原による，HKパズルの研究結果を紹介する．
具体的には，以下が得られた．
1. HKパズルには28個詰め込む解が20通り存在する．
2. HKパズルには29個目のブロックは入らない．
3. HKパズルに28個目が入る条件は(a+b+c)/4=a<b<cだけではない．
HKパズルで28個目を詰め込める必要十分条件は，
(a<b≦4a/3, 5a/3≦c<2a, (b-a)=(2a-c))である．[発表資料(pdf)]
13. ある帽子ゲームとその変種について：岡本 吉央 (北陸先端科学技術大学院大学)
n人のプレイヤーの頭に赤か白の帽子が一様ランダムにかぶせられ，
各プレイヤーが自分の帽子の色を推測する．プレイヤー同士はコ
ミュニケーションをとれず，他のプレイヤーの帽子の色を見ること
だけできる．そして，一斉に，プレイヤーは自分の帽子の色を答え
るか，あるいは自信がなければパスをする．1人以上がパスをせず，
パスをしなかったプレイヤーが全員正解したら，(パスしたプレイ
ヤーも含めて) プレイヤー全員が勝利し，誰かが間違った答えを言
うか，あるいは，全員がパスした場合はプレイヤー全員が敗北する．
このゲームとその変種について，知られている事項と少し考えたこ
とを発表する．[発表資料(pptx)]
世話役 伊藤大雄（京都大学）、岡本吉央（北陸先端科学技術大学院大学）