セッション１ 10:30-11:1510:30-10:45 (ショート)
1. 魔方陣の解の構造等価性について
酒井正彦 (名古屋大学)10:45-11:00 (ショート)
2. Threes!と2048は難しい
ステファン・ランガーマン (ULB)，○宇野裕之 (大阪府立大学)11:00-11:15 (ショート)
3. スライドパズルの操作回数に関する考察
小保方幸次 (一関高専)セッション２ 11:30-12:20
11:30-11:55
4. 遺伝的アルゴリズムによるパズル問題の自動生成：四角に切れ
藤原博文 ((株)タイムインターメディア 知識工学センター)11:55-12:20
5. 凸多角形を数多く作れる裁ち合わせパズルの研究
勝又一穂，○上原隆平 (JAIST)セッション３ 13:45-14:35
13:45-14:10
6. 線対称パズルの難しさについて
Matias Korman (NII), ○大舘 陽太 (JAIST), Marcel Roeloffzen (東北大), 上原 隆平 (JAIST), Andre´ van Renssen (NII)14:10-14:35
7. 線対称パズルの解法について
○奥村 俊文 (JAIST), 大舘 陽太 (JAIST), 上原 隆平 (JAIST)セッション４ 14:50-15:40
14:50-15:15
8. 1次元盤面における不連続な目標形のハラリイの一般化三並べ
末續鴻輝 (京大)15:15-15:40
9. 凸配置＋１点の三角取りの必勝戦略
○飯塚昂史，上原隆平 (JAIST)セッション５ 15:55-16:35
15:55-16:10 (ショート)（発表中止）
10. マインスイーパーの最適戦略
荒谷 真典 (東工大)16:10-16:35
11. Monte Carlo Tree Search を用いた Connect Four 最強 AI
石本航太 (上智大)セッション６ 16:50-17:40
16:50-17:15
12. 引分け有り一般化ジャンケンの引分け数の連続性
○塩野芳直、伊藤大雄 (電通大)17:15-17:40
13. 一般化将棋・チェスの定数時間検査可能性について
○朴 台根、伊藤大雄 (電通大)
1. 魔方陣の解の構造等価性について：酒井正彦 (名古屋大学)
2. Threes!と2048は難しい：ステファン・ランガーマン (ULB)，○宇野裕之 (大阪府立大学)
概要：魔方陣の解の数え上げの高速化には、解の構造等価性を用いて探索空間
を抑える方法が有効である。回転と対称以外の構造等価性について述べ、
サイズ５の魔方陣への適用結果を示す。３. スライドパズルの操作回数に関する考察：小保方幸次 (一関高専)
概要：We analyze the computational complexity of the popular computer games
Threes!, 2048 and many of their variants. For most known versions expanded to a n × n board, we
show that it is NP-hard to decide whether a given starting position can be played to reach a
specific (constant) tile value.4. 遺伝的アルゴリズムによるパズル問題の自動生成 --- 四角に切れ：藤原博文 ((株)タイムインターメディア 知識工学センター)
- 概要：ジグソーパズルのような絵合わせパズルと、15パズルのようなスライドパズルを
組み合わせたパズルを考案した。このパズルは、ある画像を同サイズのピースに
切り分けランダムに並べ替えられた画像から、元画像を推測復元する。ただし、
復元は隣接するピースの入れ替えのみで行う。このような、パズルをとくための
計算時間と操作回数を競う競技会を実施したので、その結果と傾向を紹介する。5. 凸多角形を数多く作れる裁ち合わせパズルの研究：勝又一穂，○上原隆平 (JAIST)
- 概要：２年前にコンピュータ支援によるナンバーエリア（四角に切れ）の問題生成を説明しましたが、
その後、遺伝的アルゴリズムを利用して問題を自動生成できるようにしました。
難易度の制御、長方形形状の制御、場所による難易度のばらつきの制御、
一部のヒントを固定しての問題作成など、多様な制御が行えます。
実行中の進化状況のグラフ表示なども行っています。- 詳細は『実践遺伝的アルゴリズム』オライリーで説明しています。
プレゼンでは、デモを中心に報告します。6. 線対称パズルの難しさについて：Matias Korman (NII), ○大舘 陽太 (JAIST), Marcel Roeloffzen (東北大), 上原 隆平 (JAIST), Andre´ van Renssen (NII)
- 概要：タングラムや清少納言知恵の板は，古来から伝わる裁ち合わせパズルである．
どちらも正方形を7ピースに分割したもので，どのピースも単位二等辺直角三
角形にさらに分割することができる．単位二等辺三角形だけを考えると，可能
な凸多角形は20種類存在する．タングラムはこのうち13種類，清少納言知恵の
板はこのうち16種類作れることがわかっていた．近年，7ピース分割では
19種類までしか作れないことが構成的に示された．つまり，20種類作れる分割
方法は存在せず，7ピース分割で19種類作れるものが具体的に存在する．
本研究では，この結果をさらに押し進め，19種類作れる7ピース分割は全部で
4通りあることを明らかにした．7. 線対称パズルの解法について：○奥村 俊文 (JAIST), 大舘 陽太 (JAIST), 上原 隆平 (JAIST)
- 概要：線対称パズルの目的は，与えられたいくつかの多角形ピースを重ならないように並べて線対称図形を作ることである．
2003年に北沢忠雄氏によって考案された SYMMETRIX を筆頭に，多くの非常に優れた線対称パズルが発表されている．
その一つの特徴として，4ピースや3ピースなど少ないピース数であるにもかかわらず非常に難しいという点がある．
本発表では，線対称パズルの難しさの一つの側面としてそのNP困難性について紹介する．8.1次元盤面における不連続な目標形のハラリイの一般化三並べ：末續鴻輝 (京大)
- 概要：線対称パズルとは，いくつかの多角形のピースを重ならないように並べて線対称な図形にするパズルである．
線対称パズルはピースをポリオミノに限定してもNP困難（Kormanら 2015）である．
ピースをポリオミノに限定した場合に対して，整数計画問題としての定式化を行い，計算機実験を行った．
一般の場合については，ピース数を定数とした場合に対する多項式時間アルゴリズムについての考察を述べる．9. 凸配置＋１点の三角取りの必勝戦略：○飯塚昂史，上原隆平 (JAIST)
- 概要：ハラリイの一般化三並べは広く研究されているが、多くは目標形について、
マス同士がつながっているもののみを扱っている。この制限をなくすことで、ハラリイの
一般化三並べに対する新たなアプローチを探りたいということが本研究の目標である。
しかしながら、2次元の盤面のまま制限をなくした場合、研究対象となる目標形があまりにも
爆発的に増加するため、まず手始めに、盤面を1次元に限定して研究を行った。10.マインスイーパーの最適戦略：荒谷 真典 (東工大) （発表中止）
- 概要：紙と鉛筆で遊ぶ二人ゲームで「三角取り」と呼ばれるものがある．与えられた
点集合で，三角形分割が完成するまで交互に線を引き，自分が完成させた
三角形が多いプレイヤーが勝ちである．一般の場合の判定問題はNP完全で，
点が凸配置の場合は先手有利であることが近年明らかになった．
本研究では，凸配置の内部に1点加えた場合を考えた．
この場合は後手有利となる戦略があることを構成的に示す．11. Monte Carlo Tree Search を用いた Connect Four 最強 AI：石本航太 (上智大)
- 概要：マインスイーパーゲームにおいて、初手はどこをクリックするのがよいかを考える。
そのためには戦略を決める必要があるが、ここでは最適戦略をゲーム木の全探索によって調べ、
初手以外は最適戦略をとったときの初手の違いによる勝率の変化、および、盤面および地雷の個数と最適戦略が選ぶ初手の関係を調べる。12. 引分け有り一般化ジャンケンの引分け数の連続性：○塩野芳直、伊藤大雄 (電通大)
- 概要： チェス，オセロなど対戦型ゲームのAIは，人間の思考を模倣した手法により，人間と同程度もしくはそれを越える性能を発揮してきた，一方で、囲碁の対戦AIは有効なヒューリスティックの作成が難しいなどの問題のため，従来の手法では高い性能を発揮することができなかった．
しかし，2006年に従来手法と大きく異なったアプローチである Monte Carlo Tree Search(MCTS) という手法を利用したAIが登場し，世界大会での優勝，ハンデ付きではあるもののプロ棋士へ勝利するという快挙を成し遂げる．これをきっかけに，MCTSがゲームAIの分野で注目を集めるようになる．近年，MCTSは囲碁だけでなく，多くのゲームAIで採用され，従来手法を上回る性能を発揮している．
本研究では，Connect Four というゲームを題材に MCTS を実装したAIを作成し，従来手法との性能の比較を行う．13. 一般化将棋・チェスの定数時間検査可能性について：○朴 台根、伊藤大雄 (電通大)
- 概要：３手のジャンケンをn手に一般化したジャンケンの性質を考察する。
ジャンケンにおいて、ある手xの代わりに出して不利になる事の無い手yのことを、
xに「優越する」手と呼び、それに優越する手が存在する手を「無駄な」手と呼ぶ。
無駄な手の無いジャンケンを「効率的な」ジャンケンと呼ぶ。
効率的なジャンケンについては伊藤によって2010年にいくつか性質が明らかに
なっているが、本研究では異なる手の間に引分けがあるジャンケンについて考察した。
（世界には異なる手の間に引分けが定義されている５手のジャンケンも存在する。）
2014年の本研究集会で、効率的なn (≧4) 手のジャンケンにおいて引分け対の
最大数は(nC2)-n+1であることを示した。また最小数はn=4で1、n≧5で0である。
今回は、この上下限の任意の整数tに対して、引分け数tの効率的なn手のジャンケンが
存在することを証明する。
- 概要：本研究では、将棋、チェス、囲碁などをサイズnに一般化した問題の定数時間検査
可能性について考察する。
盤面を√n×√nに拡張し、王将（またはキング）以外の駒の数をO(n)個に増やした
ものを一般化将棋（チェス）と定義する。同様に、盤面を√n×√nに拡張し、石の数
をO(n)個に増やしたものを一般化囲碁と定義する。この一般化将棋、チェス、囲碁の
任意の局面Sを入力として与えて、そこから先手と後手が最善を尽くしたときに先手が
勝つか否か判定する問題をそれぞれ一般化将棋、一般化チェス、一般化囲碁問題と呼ぶ。
本研究では一般化将棋問題と一般化チェス問題は定数時間検査可能であることを示す。
世話役 伊藤大雄、岡本吉央（電気通信大学）