組合せゲーム・パズル ミニプロジェクト

第2回ミニ研究集会

[日時・場所] [位置付け] [プログラム] [各講演の概要と発表資料]

日時  2007年3月16日(金)、10:30〜16:45

場所  豊橋技術科学大学 豊橋駅前サテライト・オフィス テクノス-U [詳細]

(豊橋市松葉町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

各講演の概要と発表資料

「整数計画法によるパズル解法」実習報告:岡本 吉央 (豊橋技術科学大学)

平成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)]


世話役 伊藤大雄(京都大学)、岡本吉央(豊橋技科大)