終了後に懇親会を行います
京都市左京区吉田本町
工学部10号館は、吉田キャンパス本部構内[地図]の東端北から二番目の建物
特別招待講演（チュートリアル）
9:30--11:00
ゲームにひそむ数理：中村義作（東海大学 教育開発研究所）
一般講演（発表時間無記入のものは30分）
11:30--12:30
シャノンのスイッチングゲームにおけるペアリング戦略について：高橋良介、瀧本英二（東北大学 情報科学研究科）
Voronoi game on graphs and its complexity：寺本幸生、上原隆平（JAIST）
14:00--15:40
碁石ゲームに関する考察 --- ４目並べ講座（40分）：徳山豪（東北大学 情報科学研究科）
囲碁プログラミングの探索における小目標間の依存関係解決に向けて：美添一樹（東京大学 情報理工系研究科）
逆算法に基づく詰め将棋の列挙：堀山貴史、中塚裕之、岩間一雄（京都大学 情報学研究科）
16:10--17:40
Toward a Polynomial Time Algorithm for 2-Link Puzzle：牧野格三（東京工業大学 数理計算科学専攻）
一般化アマゾンはPSPACE-complete：清見礼（国立情報学研究所）
Rogueの脱出判定問題（15分）：武永康彦（電気通信大学）
整数計画法を用いたスリザーリンクの解法（15分）：杉村 由花（東京大学）
時間：18:00--20:00
場所：カフェレストラン「カンフォーラ」
参加費：未定（2000円程度）
出欠は当日とります。
シャノンのスイッチングゲームにおけるペアリング戦略について：高橋良介、瀧本英二（東北大学 情報科学研究科）
- HEXというゲームは，n x n の盤面では最適戦略を求めることが
- PSPACE困難であるが，n x m の盤面（n≠m）ではペアリング戦略と
- 呼ばれる単純な必勝法が存在することが知られている．
- 本研究では，このゲームを一般化したシャノンのスイッチングゲーム
- において，ペアリング戦略が存在するための条件について考察する．
- [発表資料(ppt)]
Voronoi game on graphs and its complexity：寺本幸生、上原隆平（JAIST）
- The Voronoi game is a two-person game which is a model for a
- competitive facility location.
- The game is done on a continuous domain, and only two special cases
- (1-dimensional case and 1-round case) are well investigated.
- We introduce the discrete Voronoi game of which
- the game field is given as a graph.
- We first show the best strategy when
- the game field is a large complete k-ary tree.
- We also show that the discrete Voronoi game is NP-complete
- on a given general graph, even if 1-round case.
[発表資料(ppt)]碁石ゲームに関する考察 --- ４目並べ講座：徳山豪（東北大学 情報科学研究科）
- 伊藤による碁石ゲームに関する講演（7月２６日）から生じた問題に関する考察を行う。
- 数学的な厳密な話ではなく、どちらかというと、趣味の話ではあるが、
- ゲームを解析する場合の考え方について討論したいと思う。
- 具体的には、縦４、横5のバージョンのパターン生成問題を取り扱う。
- [発表資料(ppt)]
囲碁プログラミングの探索における小目標間の依存関係解決に向けて：美添一樹（東京大学 情報理工学研究科）
- 囲碁においては、盤面全体に対する、速く正確な評価関数を作ることは困難である。
- そのため、小目標ごとのサーチが、囲碁プログラムの間では広く用いられている。
- ここで問題になるのが小目標間の依存関係である。
- 小目標の勝敗に影響を与える範囲を求めて
- 依存関係を解決するアプローチが研究され始めている。
- そのような範囲を求める新たな手法を提案し、囲碁の部分問題を解くことを目指す。
- [発表資料(ppt)]
逆算法に基づく詰め将棋の列挙：堀山貴史、中塚裕之、岩間一雄（京都大学 情報学研究科）
- 近年の計算機の高速化やメモリ量の増加、洗練されたアルゴリズム設計法の発展により、
- 与えられた条件を満たす解を1つだけでなくすべて列挙することが、実用上要請される
- ようになってきている。本発表では、逆算法による詰将棋の列挙アルゴリズムを提案する。
- 逆算法により詰め手数の少ないものから順に詰将棋を列挙することで、詰将棋解答プログラムを
- 用いることなく、与えられた条件下で可能な詰将棋を高速に列挙することができる。
- [発表資料(ppt)]
Toward a Polynomial Time Algorithm for 2-Link Puzzle：牧野格三（東京工業大学 数理計算科学専攻）
- パズル雑誌などに載っているものの中に「ナンバーリンク」と呼ばれるパズルがある。
- 今回、我々はこのパズルをグラフ問題として考え、ｋ-リンクパズルと名づけた。
- 本研究は、そのｋ-リンクパズルに関する研究の第一歩として、
- ｋを2に固定した「2-リンクパズル」に対し、解を持つための必要十分条件について考察する。
- Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コンピュータ上の
- アドベンチャーゲームである。残り体力のないキャラクターが魔物のいる部屋から
- 脱出できるかというパズルがデュードニーの「コンピュータレクリエーション」で
- 紹介されているが、その一般化がNP完全であることを証明する。
整数計画法を用いたスリザーリンクの解法：杉村 由花（東京大学）
- ペンシルパズル「スリザーリンク」の類似パズル「スリザーリンクス」の考案，
- およびその NP 完全性の証明．また，スリザーリンクの整数計画問題としての
- 定式化，およびその実装実験について．
- [発表資料(ppt)]
世話役 伊藤大雄（京都大学）