09:00--10:15 (25分x3)
- Bridge It と Connection の必勝法について
- 松井知己（中央大学理工学部情報工学科）
- ハノイグラフの生成と最短経路の導出
- 村田和也（東京電機大）
- 松浦昭洋（東京電機大）
- 一般化はさみ将棋のEXPTIME完全性
- 方波見尚之（東京電機大学理工学研究科）
- 築地立家（東京電機大学理工学研究科）
10:25--11:40 (25分x3)
- 金図式・銀図式・桂馬図式の全列挙
- 太田圭亮（京都大学工学部情報学科）
- 川原純（京都大学大学院情報学研究科）
- 伊藤大雄（京都大学大学院情報学研究科）
- 堀山貴史（埼玉大学大学院理工学研究科）
- Bonanza Method を用いた囲碁評価関数の設計
- 橋本剛（JAIST）
- 松井利樹（JAIST）
- 野口陽来（JAIST）
- 人間の対戦相手としてのゲームアルゴリズム、話題提供
- 池田心（京都大学）
11:40--12:50 昼休み
12:50-14:40 (25分x3 + 20分* + 15分**)
- 絵画的迷路の作り方
- 岡本吉央（東工大）
- 上原隆平（JAIST）
- 正四面体が通過できる小さな壁穴、およびその高次元版
- 徳重典英（琉球大学教育学部）
- 計算ブロックパズルの問題例生成(*)
- 原口和也 (石巻専修大学)
- 高橋隆一 (石巻専修大学)
- 丸岡章 (石巻専修大学)
- 一般化マクマホン立方体パズルの問題例生成(**)
- 原口和也 (石巻専修大学)
- 柿崎幸大 (石巻専修大学)
- 丸岡章 (石巻専修大学)
- ２行＋αチョンプに関する考察
- 後藤順一（京都大学工学部情報学科）
- 伊藤大雄（京都大学大学院情報学研究科）
Bridge It と Connection の必勝法について：松井知己（中央大学理工学部情報工学科）
- Bridge It はD. Gale によって考案された２人ゲームであり，ペアリング戦略に
基づく先手の必勝法が 存在することが知られている． Connection は，
Bridge It に「先に閉路を作った方が勝ち」という規則 を付け加えてできる
ゲームである．本発表では，Connection に対し， multi-graph
connectivity game に基づく先手の必勝戦略があること を示す．
[発表資料(ppt)]ハノイグラフの生成と最短経路の導出：村田和也・松浦昭洋（東京電機大）
- 本発表では、k本の柱を持つハノイの塔問題に関して、
円盤の置かれた状態を頂点とし、移れる状態間に辺を与えた
グラフである「ハノイグラフ」の一般的な生成法を示す。
さらにハノイの塔問題をハノイグラフ上の最短経路問題
と見たときの、最短経路の計算機による導出結果を示す。
[発表資料(ppt)]一般化はさみ将棋のEXPTIME完全性：方波見尚之・築地立家（東京電機大学理工学研究科）
- はさみ将棋とは、自分の駒を用いて相手の駒をはさんでとる２人対戦型ゼロサムゲーム
であり、日本のはさみ将棋、タイのMak-yakなどが有名である。本稿では、盤面を
n×nに拡張した一般化はさみ将棋の計算複雑さについて考察する。ここでは、縦、横方
向に自由に動く駒に加えて、不動駒も使用するものとする。また、縦横方向に加えて斜
め方向の取りも許すものとし、相手の駒を先に5個取った方が勝ちとする。このとき、
任意に与えられた一般化はさみ将棋の盤面について、勝ち・負け・引き分けのいずれで
あるかを判定する問題が、EXPTIME完全問題であることを証明する。
金図式・銀図式・桂馬図式の全列挙：太田圭亮・川原純・伊藤大雄（京都大学）・堀山貴史（埼玉大学）
- 中塚らによって提案された逆算法による詰将棋の列挙アルゴリズムでは，
詰め上がり図から逆順に手を戻し，生成された局面のデータベースを構
築することで，高速な問題生成，余詰判定を可能にしている．中塚らが
列挙を行なった際の出力を精査した所，いくつかの不適切な出力が確認
でき，結果アルゴリズムの一部に誤りがあるとわかった．実装の面から
アルゴリズムを再検討し，いくつかのアルゴリズムを追加，改良した．
その結果，不適切な出力を修正することができ，列挙された局面は本研
究で定義される正しい詰将棋であることがいえた．また，桂馬図式の完
全列挙を行なうことに成功した．金銀図式に関しては，金銀計4枚までを
使用した列挙を行なうことに成功した．
[発表資料(ppt)]Bonanza Method を用いた囲碁評価関数の設計：橋本剛・松井利樹・野口陽来（JAIST）
- コンピュータ囲碁は近年モンテカルロ木探索によって急激に強くなり、
9路盤ではプロに迫る強さに達した。現在はモンテカルロ法による
勝率計算においていかに「人間らしい」ランダムな手順選択を
させるかが焦点となっており、優れた手の評価関数が必要となる。
本発表ではコンピュータ将棋において評価関数の学習に用いられ
ている勾配法（Bonanza Method）をコンピュータ囲碁に応用する。
囲碁評価関数に合わせたフィルタを与えることで高性能の機械学習に
成功した。
ベンチマークとして，現在世界最強の囲碁プログラムであるCrazy Stone
で用いられている学習手法である「小数化-最大化」と比較実験を行った結果，
大きな性能向上を確認できた。
[発表資料(ppt)]人間の対戦相手としてのゲームアルゴリズム、話題提供：池田心（京都大学）
- 多くのコンピュータゲームでは、何らかの知的なエージェントが「相手」として登場する。
RPG、シューティング、アクションなどではそれらは一段下等な存在であることが多いが、
戦略シミュレーション、対戦パズルなどでは対等な条件での人間格の役割が求められる。
近年のネットワークの発達により実際に人間を相手にすることも容易になりつつあるが、
それでも人間の対戦相手を（いつでも、適切に）するアルゴリズムの重要性は依然高い。
オセロ・チェス等のアルゴリズムの研究は古くからあり、強さという面では
人間を凌駕するものができているゲームは少なくない。
一方で、人間が楽しめる相手とするためには、強さだけでは不十分であり、
強さが調整可能なこと・ただしあからさまな手抜きでないこと（リアルに弱いこと）・
人間に対する教育的立場が取れること・同じ強さの戦略でも複数の個性があること・
振る舞いが人間ぽいこと、などが求められる場合がある。
本発表では、以上の課題を提起し、発表者が取り組んできた二次元ニム・崩珠・
スクラブルについて紹介する。
[発表資料(ppt)]絵画的迷路の作り方：岡本吉央（東工大）・上原隆平（JAIST）
- 入力として与えられた白黒2値ラスター画像から，その画像の黒
ピクセルのみを通過する迷路をランダムに作成する「絵画的迷路
生成問題」に対するアルゴリズムを提案する．黒ピクセルのみを
通過する問題を単純に定式化すると格子グラフ上のハミルトン道
問題となり，NP困難性に直面してしまうが，提案する手法では定
式化を変えることで全域木のランダム生成のみで迷路を作成でき
る．そのため，アルゴリズムは極めてシンプルである．
[発表資料(pptx)]正四面体が通過できる小さな壁穴、およびその高次元版：徳重典英（琉球大学教育学部）
- 正四面体が通過できる「小さな」壁穴を探したい。穴の形が
正三角形、正方形、円の場合について、最小の壁穴を紹介する。
さらに、対応する高次元の問題について、最近得られた結果、
未解決の問題等を紹介する。
[補足資料(pdf)]計算ブロックパズルの問題例生成：原口和也・高橋隆一・丸岡章 (石巻専修大学)
計算ブロックパズルでは n x n のマス目が与えられる.
マス目はいくつかのブロックに分割され, 各ブロックには1つの
整数が付される. このパズルのゴールは, 以下の条件を
満たすように1からnの整数をマス目に埋めることである.
(i) 埋めた数がラテン方陣を成す.
(ii) 各ブロックを埋める数の合計が, そのブロックに付された整数と等しい.
このパズルに対し, 解を1つだけ持つような
問題例の生成アルゴリズムとその高速化について触れ,
更にプレイヤーの振る舞いに関する観察結果を紹介する.
[発表資料(ppt)]一般化マクマホン立方体パズルの問題例生成：原口和也・柿崎幸大・丸岡章 (石巻専修大学)
マクマホン立方体とは各面が相異なる6色を持つ立方体である.
長さ1のマクマホン立方体の集合 (インスタンス) から
長さn (=2,3,...) のマクマホン立方体を構成するパズルを考える.
このパズルに対する Berkove らの結果を紹介したのち,
長さ2の任意のマクマホン立方体を構成できる
最小サイズのインスタンスの生成法を与える.
[発表資料(ppt)]２行＋αチョンプに関する考察：後藤順一・伊藤大雄（京都大学）
チョンプとは、ｎ×ｍの盤面から、２人のプレイヤーが
交互に盤上のブロックを選択し、選ばれたブロックとその右や下に
あるブロックを除去してゆき、最後に最も左上のブロックを
選ばざるを得なくなったプレイヤーが負けとなるゲームである。
チョンプは、先手必勝であることは証明されているが、
その具体的な手順については、一般には知られていない。
また、ゲームの負け型の形は、２行目のブロックの数に対して
周期的に決まることが知られているが、３行チョンプでは、
盤面のサイズを大きくしても、周期はほとんど大きくならない
ことが観察されていた。
本研究では、３行よりも大きいサイズのチョンプについて、
負け型の周期を列挙した。その結果、３行チョンプに比べて、
周期が非常に大きくなることがあることが分かった。
また、２行チョンプに対して、グランディ値を求めることに成功した。
[発表資料(ppt)]
世話役 伊藤大雄（京都大学）、岡本吉央（東工大）