終了後に懇親会を行います。
10:00--11:30
- 飛び道具を考慮した逆算法に基づく詰将棋列挙技術
- 川原純 (京都大学大学院情報学研究科)
- 蟻塚正樹 (京都大学情報学科)
- 堀山貴史 (埼玉大学理工学研究科)
- 伊藤大雄 (京都大学大学院情報学研究科)
- ゲームplanarity.netの難しさ
- 岡本吉央 (東京工業大学)
- オセロ求解へ向けた取り組み
- 橋本剛（北陸先端科学技術大学院大学 情報科学研究科）
- 上田徹（北陸先端科学技術大学院大学 情報科学研究科）
- 橋本隼一（北陸先端科学技術大学院大学 情報科学研究科）
11:30--12:45 昼休み
12:45-14:05
- OBDDによるナンバーリンクの解法（ショートトーク）
- 古妻浩一 (電気通信大学)
- 武永康彦 (電気通信大学)
- 一般化三並べの変種の勝敗判定に関する研究
- 八鍬友貴 (東北大学工学部電気情報物理工学科)
- 石野明 (東北大学大学院情報科学研究科)
- 篠原歩 (東北大学大学院情報科学研究科)
- あるルーティングゲームの最適戦略について
- 瀧本英二（東北大）
14:20--17:20
未解決問題・ディスカッション
飛び道具を考慮した逆算法に基づく詰将棋列挙技術：川原純 ・蟻塚正樹 (京都大学) ・堀山貴史 (埼玉大学) ・伊藤大雄 (京都大学)
- 近年の計算機の高速化やメモリ量の増加、洗練されたアルゴリズム設計法の発展により、
与えられた条件を満たす解を1つだけでなくすべて列挙することが、実用上要請される
ようになってきている。前回我々は逆算法による詰将棋の列挙アルゴリズムを提案し、
飛び駒が無い場合について実際に列挙を行った。逆算法とは、詰め手数の少ないものから
順に詰将棋を列挙することで、詰将棋解答プログラムを用いることなく、与えられた条件下で
可能な詰将棋を高速に列挙する手法である。今回の発表では飛び駒を導入した場合の問題点に
ついて考察し、アルゴリズムを提案する。実際に実装を行い、使用駒を香車３枚と玉１枚だけ
に限定した詰将棋の全列挙に成功した。飛び駒が無い場合の最新の結果についても述べる。
[発表資料(ppt)]ゲームplanarity.netの難しさ：岡本吉央 (東京工業大学)
- 与えられた平面的グラフの (交差がないとは限らない) 平面描画に対して，
頂点を移動させることでそれを無交差平面描画に変換するまでの速さを競う1人
ゲームがwww.planarity.netというサイトで公開されている．このゲームの難しさ
を移動させる頂点数最小化問題として捉える側面から研究した．その結果，NP困難
性，近似困難性，最小移動頂点数に関する上界，下界に関する結果などが得られた．
本研究はXavier Goaoc, Jan Kratochvil, Chan-Su Shin, Alexander Wolffとの
共同研究である．
[発表資料(pdf)]オセロ求解へ向けた取り組み：橋本剛・上田徹・橋本隼一 (JAIST)
- 2007年にCheckersが解かれ大きな話題となったが, 次のターゲットとして
オセロの完全解へ向けた取り組みについて紹介する. 核となるソルバーとし
て証明数探索がチェッカーなどの求解に威力を発揮したが, オセロでは２重
カウント問題の影響が大きくdfpnなどの従来手法では探索性能が著しく落
ちる. そこで上記問題の影響を受けない新たな探索法WPNSを提案しオセロ
と詰め将棋でその性能を評価した. その結果はオセロや長手数詰将棋で極め
て有効で, オセロ完全解へ向けた有力なツールであることを示せた.
[発表資料(ppt)]
OBDDによるナンバーリンクの解法：古妻浩一・武永康彦 (電気通信大学)
- ナンバーリンクは盤面に与えられた数字同士を線で結ぶパズルである。
本研究ではこのパズルのOBDD(二分決定グラフ）による解の列挙方法を示した。
一般に短絡解と呼ばれる解のチェックを行い、与えた問題が正当なものであるか
どうかの検証も行なった。
[発表資料(ppt)]
一般化三並べの変種の勝敗判定に関する研究：八鍬友貴・石野明・篠原歩 (東北大学)
- フランク・ハラリイに提案された一般化三並べは、碁盤状の盤面に二者が
交互に石を一つずつ置き、予め定められた、連結した石で定義されるある
形を、回転と反転を許して、先に作った方が勝ちというゲームである。両
者が最善を尽くしたとき、先手必勝である形を「勝ち型」、無限に続けて
も決着がつかない形を「負け型」と呼ぶ。なおゲームの性質上、後手必勝
ではありえない。
これまでの研究で，必勝手順を示すことや計算機によって勝ち型に分類さ
れた形や，畳敷き戦略により負け型に分類されてきた形が知られている．
また，未だ未解明なスネーキーと呼ばれる形も存在する．
本研究では，それらの中でも負け型に着目し，単独では負け型になってし
まう形について，その二つ組を定義し，「二つ組のどちらかの図形を先に
つくる」という新たなゲームＯＲを考案し，その中のいくつかの二つ組に
ついて勝敗判定をした．なお，勝ち型の証明には先手必勝手順を示すこと
で，また負け型の証明には畳敷き戦略を利用することで解を得た．
[発表資料(ppt)]
あるルーティングゲームの最適戦略について ：瀧本英二（東北大）
- 情報処理学会東北支部設立３０周年記念事業の一環として
開催されたプログラミングコンテストの問題が，
有向グラフにおける道の集合を戦略クラスとする零和型の
行列ゲームとみなせることに注目し，その最適混合戦略を求める
問題について考えた．
ここで，一般に，損失行列の大きさはグラフのサイズに関して
指数的となるため，線形計画法などの，損失行列を陽に用いる
標準的な手法はきわめて非効率である．
我々は，オンライン予測の手法とカーネル手法を組み合わせることに
よって，多項式時間で最適混合戦略を求めるアルゴリズムを
与えることに成功した．
[発表資料(ppt)]
世話役 伊藤大雄（京都大学）、岡本吉央（東工大）