●セッション1 15分x1, 20分x2
9:30〜9:45
1. GPGPUによる4次魔方陣解法プログラムの実装
齊藤 友輝 (電気通信大学)9:45〜10:05
2. フロンティア法による「Ls in L」と「Sphinxes in Sphinx」の解の列挙
○兼本 樹，斎藤 寿樹 (神戸大学)10:05〜10:25
3. 七金三パズルで作れる凸多角形の全列挙
堀山 貴史 (埼玉大学)，○上原 隆平 (JAIST)，細矢 治夫 (お茶の水女子大学)●セッション2 20分x4
10:40〜11:00
4. 学習によるテトリスAIの実装と考察
○青木 勢馬，橋本 剛（松江工業高等専門学校）11:00〜11:20
5. ガイスターにおける自己対戦による行動価値関数の学習
佐藤 佑史 (電気通信大学)11:20〜11:40
6. 「どうぶつしょうぎ」における意思決定：視線計測装置を用いた分析
島 直之 (東京工業大学)11:40〜12:00
7. "好感度"を導入することによる多人数ゲームの研究について
末續 鴻輝 (京都大学)●昼休み：12:00〜13:20
●セッション3 20分x3
13:20〜13:40
8. 密度の高いシークワーズ問題作成アルゴリズム
◯鍋島 貴大，伊藤 大雄（電気通信大学）13:40〜14:00
9. 波及効果の例題生成について
内藤 政斗，元木 光雄 (金沢工業大学)14:00〜14:20
10. ビルディングパズル最小ヒント数について
中村 陽介 (名古屋大学)●セッション4 20分x3
14:35〜14:55
11. N面サイコロを用いたLiar's DiceおよびBluffにおける最適戦略の導出アルゴリズム
栢沼 凌汰 (電気通信大学)14:55〜15:15
12. Corral Puzzleの整数計画法による解法と評価
○弘中 健太，鈴木 裕章，上嶋 章宏 (大阪電気通信大学)15:15〜15:35
13. 整数計画法を用いたPearl Puzzleの効率的な解法
○貴宮 京一，鈴木 裕章，上嶋 章宏 (大阪電気通信大学)●セッション5 20分x3
15:50〜16:10
14. iGAを用いた方形ピースジグソーパズルの組立て
○高橋 一幸，小保方 幸次 (一関工業高等専門学校)16:10〜16:30
15. 『数の六角パズル』を頭だけ使って解こう
○山中 寿登，小野 廣隆 (九州大学)16:30〜16:50
16. SMTソルバを用いた「竹内の3人の賢者問題」の求解
田中 哲朗 (東京大学)●セッション6 20分x4
17:05〜17:25
17. 単貧民における必勝戦略と必勝判定問題に関する考察
○木谷 裕紀，小野 廣隆 (九州大学)17:25〜17:45
18. 手数が少ない場合におけるグリッド上のボロノイゲームの解析
○杉本 晃弘，斎藤 寿樹，山口 一章，増田 澄男 (神戸大学)17:45〜18:05
19. 一次元クロバーの解析
西野 潤 (電気通信大学)18:05〜18:25
20. 一般化将棋・チェス・囲碁問題の定数時間検査アルゴリズム
○伊藤 大雄, 長尾篤樹, 朴 台根（電気通信大学）●---
[懇親会]
会場・時間は後日発表します。
会場予約の都合上、懇親会の参加には事前登録が必要です。ご協力をお願いします。->[登録ページ]（席数に限りがありますので、早めにお申し込みください。）
1.GPGPUによる4次魔方陣解法プログラムの実装：齊藤 友輝 (電気通信大学)
2.フロンティア法による「Ls in L」と「Sphinxes in Sphinx」の解の列挙：兼本 樹，斎藤 寿樹 (神戸大学)
概要：汎用プロセッサでの魔法陣解法プログラムの実装がいくつか報告されている．
それに対し，並列度が非常に高いGPGPU(General-purpose computing on
graphics processing unit)による実装で高速化を図った．その結果， 4次魔法
陣解法プログラムにおいて汎用プロセッサでの実装より2倍の速度での実装に成
功した．今回用いた構造等価性やGPGPUに実装する際の方法について述べる．[発表資料(pdf)]３. 七金三パズルで作れる凸多角形の全列挙：堀山 貴史 (埼玉大学)，上原 隆平 (JAIST)，細矢 治夫 (お茶の水女子大学)
概要：ある図形に対して，その図形を拡大したものに，いくつかの元の図形を用いて埋め尽くすことのできるとき，その図形をrep-tileであるという．rep-tileの例として L や Sphinx があり，これらに対して，埋め尽くし方の数え上げの研究結果が知られている．本研究では，その数え上げの精度を向上させるため，フロンティア法を用いた数え上げアルゴリズムを提案する．[発表資料(pptx)]
- 概要： タングラムや清少納言知恵の板に代表されるシルエットパズルは，古来より
数多く考案されてきた．こうしたパズルの表現能力の指標として，何通りの
凸多角形が作れるかという問題を考える．タングラムは13種類，清少納言
知恵の板は16種類の凸多角形が作れることがわかっている．これはどちらも
合同な直角2等辺角形がピースの最小単位となっているという特徴を巧妙に
使うと，コンピュータを用いないでも算出することができる．
一方，こうしたパズルはピース数や最小単位となる形によって，困難性が大き
く変わって来る．一般の凸多角形ピースという枠組みで考えると，任意のnに
対して，2ピースで2n通りの凸多角形を作れることがわかっている．また，一
つを除いてすべてのピースが長方形という制限でも，nピースで凸多角形が作
れるかどうかという判定問題がNP完全となることも知られている．
ここではこうしたパズルの一種として，七金三パズルを取り上げる．これは
2015年に発売された黄金比に基づくピース構成のパズルで，ピースはすべて
3角形で，7ピースから構成される．黄金比の性質をうまく用いると，効率の
よい探索アルゴリズムが構成できる．結論として，七金三パズルでは62種類も
の凸多角形が作れることがわかった．
本講演は，細矢治夫・堀山貴史両氏との共同研究に基づく．[発表資料(pdf)]4. 学習によるテトリスAIの実装と考察：青木 勢馬，橋本 剛（松江工業高等専門学校）
5. ガイスターにおける自己対戦による行動価値関数の学習：佐藤 佑史 (電気通信大学)
- 概要：テトリスのAIはヒューリスティックス主体のものがほとんどで、汎用的AI
の報告はされていない。教師あり学習による汎用的なテトリスAIの作成について
実装と考察を行ったので、その結果を示す。[発表資料(pptx)]6. 「どうぶつしょうぎ」における意思決定：視線計測装置を用いた分析：島 直之 (東京工業大学)
- 概要：二人確定不完全情報ゲームであるガイスターにおいて、
局面s、手aに対する勝率の見積もりを計算する関数Q(s,a)を自己対戦による
Sarsa(λ)を用いて学習するAIを作成した。
さらに、通常は不完全情報ゲームには適用できないDf-pnアルゴリズムによる
必勝手探索を、ガイスターのルールを変え完全情報ゲームとすることにより
可能にし、これをAIに組み込んだ。その結果、ランダムプレイヤおよび
従来手法であるモンテカルロ木探索を用いたプレイヤに対し、
勝ち越すことができた。[発表資料(pdf)]7. "好感度"を導入することによる多人数ゲームの研究について：末續 鴻輝 (京都大学)
- 概要：ボードゲームにおける意思決定の研究において、視線計測装置を用いた実験として高橋（2012）や伊藤（2002）などがある。高橋（2012）は囲碁においては上級者になるに従い、プレイヤーの見ている範囲が広くなっていることを観察した。それに対し、伊藤（2002）は将棋においては上級者になるに従い、プレイヤーの見ている範囲が狭まっていることを観察した。このように、ボードゲームの種類によって、プレイヤーの視線の動きには差異が生じている。本論文は、「どうぶつしょうぎ」と呼ばれるボードゲームにおいて初心者と熟達者の視線の動きを比較する。これまで扱ったボードゲームよりも盤面のマス目が少ないため、より精度の高い視線の分析が可能となる。[発表資料(pptx)]
8.密度の高いシークワーズ問題作成アルゴリズム：鍋島 貴大，伊藤 大雄（電気通信大学）
- 概要：囲碁のプロ棋士が人工知能に敗れるなど、近年組合せゲームの
研究は更に深まっている。一方で、3人以上のゲームに関しては研究の
熱が湧きたつには至っていない。この一つの原因は、対局相手が1人では
なく複数になることで、自身にとって適切な一手というものを決定しづらく
なる点にある。今回の発表では"好感度"というものを導入することにより、
適切な一手を2人ゲームの時と同様に再帰的に定義する手法を提唱し、
また、それによって得られる結果を、他の手法による多人数ゲームの
先行研究と交えながら紹介する。[発表資料(pdf)]9. 波及効果の例題生成について：内藤 政斗，元木 光雄 (金沢工業大学)
- 概要：シークワーズは海外ではWord Searchとも呼ばれるパズルで、格子状に文字が
散りばめられた二次元の盤面（行列）から、与えられた複数の単語を探す問題である。
各単語は表の中の縦か横か斜めか８方向の連続する文字から構成されている。シーク
ワーズを解くのは明らかに多項式時間でできるが、逆に単語の集合と盤面のサイズ
（ｎ×ｍ）が与えられて盤面が作成できるか否かを問う問題はＮP完全であることが
分かっている。
本研究では、なるべく密度の高いシークワーズの問題例（盤面）を作成することを
目指した。ここで密度とは、各文字の、それが単語に使用されている回数の平均値と
定義した。広辞苑に含まれる単語のリストを使用して小さい（８×８程度の）サイズ
の盤面を作成した結果を示す。[発表資料(pdf)]10.ビルディングパズル最小ヒント数について：中村 陽介 (名古屋大学)
- 概要：「論理パズル「波及効果」に対する例題生成アルゴリズムの
作成を試みたので，その報告を行う．」[発表資料(pdf)]11. N面サイコロを用いたLiar's DiceおよびBluffにおける最適戦略の導出アルゴリズム：栢沼 凌汰 (電気通信大学)
- 概要：ペンシルパズルの一つにビルディングパズルがある．
ヒントが行列マスの外側４方向にいくつか存在し，これらを満たすラテン方陣を 求める．
このヒントは，マス内の数を建物の高さとみなしたときに置かれた位置から見え る個数を表す数である．
本発表ではこのパズルの最小ヒント数がn-1個であるという予想と，それに関す るいくつかの結果について述べる．[発表資料(pdf)]12. Corral Puzzleの整数計画法による解法と評価：弘中 健太，鈴木 裕章，上嶋 章宏 (大阪電気通信大学)
- 概要： Liar's Diceというゲーム、そしてBluffというLiar's Diceの仲間である2つの類似した
サイコロを用いたボードゲームについて、最適化問題としてモデル化を行い、ナッシュ均
衡を用いて最適戦略を導出するアルゴリズムを作成した。Liar's Dice の先行研究では6
面サイコロを用いた場合についてのみ、 Bluffの先行研究では先手と後手が1つずつのサ
イコロを持ち、サイコロは2から6面のものを用いる場合についてのみ述べられていたが、
本研究ではそれぞれについて任意の数の面を持つサイコロを利用し、Bluffでは先手後手
がそれぞれ任意の数のサイコロを持つ場合についてのモデルを構築し、最適戦略及び両者
が最適戦略を利用した場合の先手勝率を導出するアルゴリズムを構成した。その計算結果
も報告する。[発表資料(pdf)]13. 整数計画法を用いたPearl Puzzleの効率的な解法：貴宮 京一，鈴木 裕章，上嶋 章宏 (大阪電気通信大学)
- 概要：本研究は，整数計画法を用いてCorral Puzzleを現実的な時間で解く
ことで，整数計画法の有用性を考察する．
ペンシルパズルの1つであるCorral Pazzleは下記のルールに従い，
線を引き単純閉路を導くパズルである．盤面には，数字が書かれた
マスがあり，そのマスから上下左右4方向に進んで，閉路にたどり着
くまでのその数字マスを含めたマスの合計数とそのマスに書かれた
数値は一致しなければならない．更に盤面上の全ての数字は閉路の
内側に入り，線は交差や枝分かれしない．
本研究では特にCorral Puzzleのルールにおける閉路性の取り扱いに
着目した2種類の定式化を設計し，通常扱われるサイズ程度の様々な
盤面に対する評価結果により有用な解法を考察する．[発表資料(pdf)]14. iGAを用いた方形ピースジグソーパズルの組立て：高橋 一幸，小保方 幸次 (一関工業高等専門学校)
- 概要：本研究では，ペンシルパズルの1つであるPearl Puzzleを整数計画
問題に定式化し，効率的な解法を試みる．
本パズルは○と●が複数配置された四角格子の盤面に，下記ルールに
従いすべての○と●上に線を引くパズルである．線は交差や枝分かれ
せず，輪を複数作ってはならない．また，○を通る線は必ず○上で直
進し，○の両隣のマスの少なくとも片方で直角に曲がる．●を通る線
は必ず●上で直角に曲がり，●の隣のマスで曲がってはならない．
Pearl Puzzleの定式化の取り組みはすでにいくつか存在する．本発表
では先行研究であるペンシルパズルSlitherlinkの高速解法を参考に
新たな定式化を述べ，既存手法を参考に構築した定式化と比較した
評価結果を示し，整数計画法の有用性を考察する．[発表資料(pdf)]15. 『数の六角パズル』を頭だけ使って解こう：山中 寿登，小野 廣隆 (九州大学)
- 概要：ジグソーパズルとは，分割された小片から画像を復元するパズルである．以前，すべてのピースの形状が等しく方形である，方形ピースジグソーパズルを組み立てるため，遺伝的アルゴリズム(Genetic Algorithm: GA)を適用した．従来の一般的なGAの遺伝的操作を適用すると，同一ピースを複数回使用した致死遺伝子の発生が考えられる．そのため，完全2部グラフ最小コストマッチングによるピースの操作を行うことにより，致死遺伝子が発生しないよう改良した交叉を行った．しかし，分割数が大きいと完成には至らない場合があった．本研究では，隣り合うピースの連続を判断するため，対話型遺伝的アルゴリズム(interactive Genetic Algorithm)による連続情報の取得を行う．提案手法は外山氏の手法と比較し，より効率的に最適解を求めることができたことを示す．[発表資料(pptx)]
16. SMTソルバを用いた「竹内の3人の賢者問題」の求解：田中 哲朗 (東京大学)
- 概要：『数の六角パズル』とはアシェット・コレクションズ・ジャパンから2007年に出版された，「パズルコレクションNo.37」で紹介された問題で，それぞれ1から19までの数が一つずつ書かれた六角形の19個のコマを，大六角形状に配置し，その大六角形の各頂点と中心を結ぶ辺上のコマの数の合計がいずれも38となるようにするものである．このパズルに対する解法が，伊藤・宇野編著「離散数学のすすめ」（現代数学社, 2010）の第8章で「頭とパソコンを使ってパズルを解こう―『数の六角パズル』を題材にして」というタイトルで取り上げられている．そこで紹介されている解法は，コマの配置が満たすべき必要条件をいくつか導出しその必要条件を満たしうる5166通りの解候補を列挙すれば解が見つかることを示した上で，実際にコンピュータプログラムを用いて全列挙するというものである．本研究では，コマの配置が満たすべき必要条件を追加することにより，このパズルの解が手計算を用いても十分導出可能であることを示す．さらに，このパズルの条件である「数の合計がいずれも38」を「数の合計が等しくなる」に緩和した場合について考え，その必要条件群と列挙を通して実際にとりうる合計値について考察する．[発表資料(pptx)]
17. 単貧民における必勝戦略と必勝判定問題に関する考察：木谷 裕紀，小野 廣隆 (九州大学)
- 概要：「竹内の3人の賢者問題」は竹内郁雄によって提案された論理パズルである．本来の設定に関して数学的な考察を元に解を絞り込んだ上で人手で解いた解と，提案者自身による検証プログラムが存在している．本研究では問題を元の定義に忠実にモデル化してSMTソルバの一つのz3を用いて解いた．その結果，発表されている解が誤っていることが分かった．また，一般化した問題を解いて，数の範囲と設問回数に関する予想を立てることができた．[発表資料（修正版）(pdf)（外部サイト）]
18. 手数が少ない場合におけるグリッド上のボロノイゲームの解析：杉本 晃弘，斎藤 寿樹，山口 一章，増田 澄男 (神戸大学)
- 概要：単貧民とは,カードゲーム大貧民を完全情報ゲームとして簡易化したものである.本研究では札の種類を一般化した二人単貧民の勝者決定について考察する.単貧民は二人完全情報性から,カードが配られた時点で先手後手のいずれかに必勝戦略が存在する.本研究では札の種類数に着目したアルゴリズム決定を提案する。また,先手後手の手札が同一のとき単貧民が先手必勝であることを示す.[発表資料(pdf)]
- 概要：ボロノイゲームは,プレイヤーが1対1で行う陣取りゲームである．本研究ではグリッドにおけるボロノイゲームを扱う．プレイヤーは先手後手に分かれてグリッドの格子点をそれぞれ一つ選び，選んだ格子点を陣地とする．これを決められた手数だけ繰り返す。その後，選ばれていないすべての格子点に対して，マンハッタン距離で一番近い陣地が先手であれば先手の領域，後手であれば後手の領域，距離が同じであれば引き分けとする．領域の多いプレイヤーが勝ちとなる．本研究では手数が1の場合の完全解析を行った．手数が2の場合においては計算機実験の結果を基にした考察をいくつか与える．[発表資料(pdf)]
20. 一般化将棋・チェス・囲碁問題の定数時間検査アルゴリズム：伊藤大雄, 長尾篤樹, 朴 台根（電気通信大学）
- 概要：二人の対局者が交互に手をうち，サイコロやカードを切り混ぜるといったランダム要素
を排し，対局者は現在のゲームの局面についての完全な情報を持つことができるというこ
とが特徴である組合せゲームを取り扱う．その中でもクロバーというゲームを一次元に制
限した一次元版クロバーに焦点をあて，様々な盤面の値を求めた．[発表資料(pptx)]
- 概要：盤面を√n×√n、駒や石の数をO(n)個に拡張した将棋、チェス、囲碁の局面が与えられて、それが
先手必勝であるか否かを問う問題は一般化将棋、チェス、囲碁問題と呼ばれ、どれも指数時間完全であるこ
とが分かっている。本研究では、これらに対する定数時間検査アルゴリズムについて考察する。その結果、
将棋、チェスに関しては定数時間アルゴリズムを与えた。囲碁に関しては将棋型の証明を適用することが
困難であるため、まったく異なるアプローチによるアルゴリズムを考察したので、それを解説する。[発表資料(pdf)]
世話役 伊藤大雄、岡本吉央（電気通信大学）