(豊橋市松葉町2丁目10番地 豊橋市企画部都心活性課事務所1階部分 豊橋駅東口を出て徒歩5分程度)
10:30--12:15
- 「整数計画法によるパズル解法」実習報告
- 岡本 吉央 (豊橋技術科学大学)
- ヒントの位置が指定されたナンプレの高速な生成法
- 稲葉直貴(名古屋工業大学)
- 数独インデックス
- 戸神星也、渡辺治(東京工業大学)
12:15--13:45 昼休み(1時間30分)
13:45--14:55
- スネーキーの置き石1の必勝法
- 宮川博光、伊藤大雄(京都大学)
- 正六角盤面上の一般化三並べ
- 入倉弘介、松浦昭洋(東京電機大学)
14:55--15:15 休憩(20分)
15:15--16:45
- シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
- 高橋良介、瀧本英二(東北大学)
- 重み付き半順序ゲームの必勝法
- 高田智史、伊藤大雄(京都大学)、中村義作(東海大学)
- Rogue脱出判定問題のPSPACE完全性 (ショートトーク)
- 新井滋、武永康彦(電気通信大学)
「整数計画法によるパズル解法」実習報告:岡本 吉央 (豊橋技術科学大学)
- 平成18年8月上旬に高専4年生を対象として「整数計画法によるパズル
- 解法」という体験実習を行なったので、その報告をします。この1週間
- に渡る実習では、論理のことばを算術のことばに置き換えるところから
- 始めて、実際に魔方陣の作成や、数独、ののぐらむ、覆面算などのパズ
- ルを整数計画問題として定式化して、ソルバで解かせることまでを体験
- してもらい、最終日には各自のアイディアを報告する発表会を行ないま
- した。この報告では、実際の進め方、題材とするパズルの選定、注意
- 点、解け具合などをまとめる予定です。
- [発表資料(ppt)]
ヒントの位置が指定されたナンプレの高速な生成法:稲葉直貴(名古屋工業大学)
- ナンプレ(数独)と呼ばれているパズルに対して
- 任意の指定された位置にヒントを持つような
- 唯一解の問題を高速に生成する手法を開発した。
- 数独というパズルの全解に対してスパコンを用いて番号付け
- を行い,4G程度に圧縮したデータを作成し,それを元に,
- 解⇔番号を10秒程度で求めるプログラムを作成した.
- ちなみに,インデックスは22桁の数になる.
- [発表資料(pdf)] [論文へのリンク]
スネーキーの置き石1の必勝法:宮川博光、伊藤大雄(京都大学)
- フランク・ハラリイの提案した一般化三並べとは、碁盤状の盤面
- に二者が交互に石を一つずつ置き、予め定められた、連結した石
- で定義されるある形を、回転と反転を許して、先に作った方が勝
- ちというゲームである。両者が最善を尽くしたとき、先手必勝で
- ある形を「勝ち型」、無限に続けても決着がつかない形を「負け
- 型」と呼ぶ。なおゲームの性質上、後手必勝ではありえない。こ
- れまでの研究でスネーキーと呼ばれる図形のみ、勝ち型か負け型
- か未解明であり、さらにスネーキーのハンディキャップ数(勝ち
- 型になる必要最小限の置き石数)についても、2以下であること
- が分かっているのみであった。本研究では、スネーキーの置き石
- 1の先手必勝手順を示す。この結果、スネーキーのハンディ
- キャップ数が0または1であることが分かった。
- [発表資料(ppt)] [必勝法資料(pdf)]
正六角盤面上の一般化三並べ:入倉弘介、松浦昭洋(東京電機大学)
- 正六角盤面上でハラリイの一般化三並べを考察した。
- これまでに明らかとなった,5細胞生物までの生物
- の勝ち型,負け型に関する結果を報告する。
- [発表資料(ppt)]
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて:高橋良介、瀧本英二(東北大学)
- シャノンスイッチングゲームとは,与えられたグラフの頂点に
- 2人のプレイヤーが交互に石を置いていくゲームである.先手の
- 目的は指定された2頂点を結ぶパスの1つを自分の石で占有する
- ことで,後手の目的はそれを阻止することである.どちらのプ
- レイヤーが必勝戦略を持つかを判定する問題はPSPACE完全で
- あることが知られている.
- 本発表では,後手の戦略をペアリング戦略と呼ばれる単純な
- 戦略に限定したとき,後手が必勝戦略を持つかどうかを決定す
- る問題の複雑さが$\Sigma_2^P$完全であることを示す.
- [発表資料(ppt)]
重み付き半順序ゲームの必勝法:高田智史、伊藤大雄(京都大学)、中村義作(東海大学)
- 本発表では「重み付き半順序集合ゲーム」というものを導入する。
- これは半順序集合ゲームの集合の要素に重みを付けて拡張したもの
- である。両プレイヤーは非負の体力を持ち、要素を取る毎にその重
- みの合計だけ体力を失う。そして先に体力が負になったプレイヤー
- が負けである。我々はこのゲームにおける必勝法を考察した。
- 第一に、重みが0か1かのどちらかである場合において以下の定理
- を発見した。
- (1)両者の体力が異なるなら、大きい体力を持つプレイヤーが
- 必勝手順を持つ。
- (2)両者の体力が同じで、全ての極大要素が正の重みを持つな
- ら、後手のプレイヤーが必勝手順を持つ。
- (3)その他の場合は、問題を(従来の重み無しの)半順序集合
- ゲームに帰着できる。
- そして第二に、一般の重みの場合において、半順序が全順序であ
- る場合における多項式時間必勝手順を発見した。
- [発表資料(ppt)]
Rogue脱出判定問題のPSPACE完全性:新井滋、武永康彦(電気通信大学)
- Rogueはキャラクタ端末のディスプレイでよく親しまれていた、コン
- ピュータ上のアドベンチャーゲームである。残り体力のないキャラク
- ターが魔物のいる部屋から脱出できるかという問題が、空腹度のパラ
- メータを設定した場合PSPACE完全であることを示す。
- [発表資料(ppt)]
世話役 伊藤大雄(京都大学)、岡本吉央(豊橋技科大)