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

第7回ミニ研究集会

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

日時  2012年3月8日(木) 9:10〜17:45

場所  大阪商業大学 4号館 2階 425教室

位置付け等

プログラム


(1) 9:10-9:30
イマジナリーキューブ・パズル
立木秀樹 (京都大学)

(2) 9:30-9:50
芸術的タイルの作り方
酒井翔平,○今堀慎治 (名古屋大)

---
休憩 10分
---

(3) 10:00-11:00
[特別講演]
平面をうめるタイル〜特にペンローズタイル作成の秘話〜」
谷岡一郎(大阪商業大学・学長)

---
休憩 10分
---

(4) 11:10-11:30
3点タイル張り問題の解の列挙
○田中成俊、羽原貴広、武永康彦(電通大)

(5) 11:30-11:50
Tantrixタイルを用いた Tantrix Match のNP完全性の証明
○柳谷 不比等 (大阪電気通信大学大学院 工学研究科),
塚本 翔平 (大阪電気通信大学 情報通信工学部 情報工学科),
上嶋 章宏 (大阪電気通信大学大学院工学研究科)

(6) 11:50-12:10
Type-LやTを含む制限に注目したセル迷路問題の計算複雑さの解析
○木場 裕矢 (大阪電気通信大学大学院 工学研究科),
植谷 昌博 (富士通ネットワークソリューションズ株式会社),
上嶋 章宏 (大阪電気通信大学大学院工学研究科)

---
昼食 70分
---

(7) 13:20-13:40
ひとりにしてくれ数
○鈴木顕,内澤啓 (東北大学 大学院情報科学研究科),
宇野毅明(国立情報学研究所)

(8) 13:40-14:00
ペンシル系パズルにおける解のユニーク性が引き起こす解き手の不公平性の改善方法
村岡真澄(東海大学)

(9) 14:00-14:10
ペンシルパズルにおける“面白い問題”の評価と作成
高雄 智成 (北陸先端科学技術大学院大学)

---
休憩 10分
---

(10) 14:20-14:40
名人の知とコンピューターの知 ―第2報―
中川 武夫(JAIST)

(11) 14:40-15:00
UCB+ 法を用いた Big Two AI の研究
○万代悠作, 橋本剛 (松江工業高等専門学校情報工学科)

(12) 15:00-15:20
後退解析を用いた完全情報七並べの解法導出
深川大路 (同志社大学 文化情報学部)

---
休憩・移動 10分
---

15:30-16:30
[見学会] アミューズメント産業研究所展示室 見学

---
休憩・移動 15分
---

(13) 16:45-17:05
色塗りゲームとゲームカラーリング数
関口 陽介(慶應義塾大学大学院理工学研究科)

(14) 17:05-17:25
区間表現をもつグラフ上でのFloodingゲームについて
上原隆平(JAIST)

(15) 17:25-17:45
一般化川渡り問題について
○伊藤大雄(京都大学),
Stefan Langerman(Universite Libre de Bruxelles),
吉田悠一(京都大学)

---
休憩・移動 15分
---

18:00--
[懇親会]
U・コミュニティホテル 1階 [アクセス] [施設情報]
会場予約の都合上、懇親会の参加には事前登録が必要です。ご協力をお願いします。->[登録ページ](3月4日〆切

 

 

各講演の概要と発表資料(発表資料は後日掲載予定)

1. イマジナリーキューブ・パズル:立木秀樹 (京都大学)

重六角錐イマジナリーキューブ(H)は、底辺:高さ=2:3 の二等辺三角形の面を側面
とする正六角錐2つを底面で貼り合わせた十二面体です。また、反三角錐台イマジナリーキューブ(T)は、
辺:高さ=4:√6の正三角錐の片方の底面の各頂点の周りを切ってできた反三角錐台です。
H と Tは、立方体と同じように直交する3方向から見て正方形に見える立体(イマ
ジナリーキューブ)であり、立方体の箱に入れることができます。ここで紹介
するパズルは、H3個とT6個を、2倍の大きさの立方体の箱に入れるというものです。
箱が2倍なので、8個までは入ることがすぐに分かりますが、問題は、9個立体がある
ことです。このパズルは、HとTの特筆すべき性質と、HとTが空間充填するという性質に基づいて
います。

 
 

2. 芸術的タイルの作り方:酒井翔平,○今堀慎治 (名古屋大)

平面を隙間なく,かつ重なりなく埋め尽くすことのできる図形をタイルと呼ぶ.
タイルは芸術と深い関わりを持ち,様々な芸術作品や文様の中に現れてきた.
本研究では,入力として与えられた図形にできるだけ近い形状のタイルを作成する問題を考える.
この問題に対する既存の手法を紹介し,その改良法を提案する.[発表資料(pdf)]


3. [特別講演] 平面をうめるタイル〜特にペンローズタイル作成の秘話〜: 谷岡一郎(大阪商業大学・学長)


4. 3点タイル張り問題の解の列挙:○田中成俊、羽原貴広、武永康彦(電通大)

3点タイル張り問題とは、一辺がn個の点からなる三角形格子に、小三角形タイルを
敷き詰める問題である。本研究ではOBDDやZDDを用いて3点タイル張り問題の解の
列挙を行なった。また、列挙した解のうち回転や裏返しで同一となる解を除いたもの
の個数を調べた[発表資料(pptx)]

5. Tantrixタイルを用いた Tantrix Match のNP完全性の証明:
○柳谷 不比等 (大阪電気通信大学大学院 工学研究科),
塚本 翔平 (大阪電気通信大学 情報通信工学部 情報工学科),
上嶋 章宏 (大阪電気通信大学大学院工学研究科)

本研究では,パズルゲーム“Tantrix Match”(Tantrix)の計算複雑
さを解析する.本パズルは正六角形のタイルを下記ルールに従い,六
角格子の盤面に配置するパズルである.
タイルに描かれる路の組み合わせは4種類あり,各路は4色で色付けさ
れており,路の色付け制限などを考慮した全56種類のタイルを用いる
ことが一般的である.
このタイルが手持ちタイルとして複数枚与えられ,数枚の動かせない
タイルがすでに配置され,手持ちタイルを配置できる場所が定められ
た盤面に対し,隣接するタイルの路が同色になるような全手持ちタイ
ルの配置を目的としたパズルである.通常,終了時にタイルに囲まれ
たタイルの配置されない場所(穴)は存在しない.
Tantrixの計算複雑さに関する議論は未解決であるが,穴の制限を外し,
手持ちタイルを配置する位置は予め指定され,回転のみを選択できる
場合のNP完全性は,M. Holzerらにより証明されている.一方で手持ち
タイルの配置位置の指定制限は,Tantrixの本来の自由度を大きく歪め
ており,評価として充分とはいえない.
そこで本研究では(穴の制限のみを外した) Tantrix Match のNP完全
性をCircuit-SATからの多項式時間還元により証明する.[発表資料(pdf)]

6. Type-LやTを含む制限に注目したセル迷路問題の計算複雑さの解析:
○木場 裕矢 (大阪電気通信大学大学院 工学研究科),
植谷 昌博 (富士通ネットワークソリューションズ株式会社),
上嶋 章宏 (大阪電気通信大学大学院工学研究科)

 本研究では,回転型セル迷路と呼ばれるパズルを扱う.この迷路は,
正方形のセルが格子状に並べられた盤面で,プレイヤーがスタートセ
ルからゴールセルへ移動可能かを問う問題であり,移動中に訪問され
たセルが回転し盤面の状態が変化するという特徴をもつ.セルの種類
は,路の方向の組み合わせを考慮すると,Type-O, U, L, I, T, Xの
全6種存在する.
 本問題は,路の種類やセルの回転規則に制限を設け,制限ごとの計
算複雑さの解析が行われている.先行研究において使用するセルを
Type-U, I, X,回転規則を右回転90°に制限した場合のPSPACE完全性,
Type-U, I, Xのうちいずれか1種類のみに制限した場合の多項式時間
可解が示されている.一方で,Type-LやTに関する制限での計算複雑
さは明らかでない.本発表では,未解決であるType-LやTを含む制限
の計算複雑さについて発表する.[発表資料(pdf)]

7. ひとりにしてくれ数:○鈴木顕,内澤啓 (東北大学 大学院情報科学研究科),宇野毅明(国立情報学研究所)

「ひとりにしてくれ」はニコリによって広められたペンシルパズルのひとつである.多くの
ペンシルパズルはNP完全であることが知られており,「ひとりにしてくれ」もそのひとつで
ある.本研究では,その「ひとりにしてくれ」に使われる整数の種類の数に着目した.「ひ
とりにしてくれ」は,使用する整数の種類が少なすぎても多すぎてもユニークな解を持つ問
題を作ることができない.そこで,ユニークな解を持つ問題を作るために少なくとも何種類
の整数が必要となるかを表す「ひとりにしてくれ数」を提案し,その上界と下界を与えた.
さらに,最大何種類の整数を用いてもユニークな解を持つ問題を作ることが出来るかを表す
「最大ひとりにしてくれ数」を提案し,その上界と下界を与えた. [発表資料(ppt)]


8. ペンシル系パズルにおける解のユニーク性が引き起こす解き手の不公平性の改善方法:村岡真澄(東海大学)

ペンシルパズルはユニーク解であることが前提で作られている場合が多い。人によって解き慣れてくると、
これから解く問題は解がユニークである事を暗黙の了解として解き始める。問題によって、
解がユニークである事を暗黙の了解とすると理詰しやすくなる。解き手の立場では、
解がユニークである事を知っている人と知らない人を比べると、解く過程で公平性の問題がある。
本研究の目的は幾つかのパズルを例に挙げて、問題を解き慣れた人と初心者とを比較して不公平が
生じないような問題の作り方を追及することである。[発表資料(pdf)]

9. ペンシルパズルにおける“面白い問題”の評価と作成:高雄 智成 (北陸先端科学技術大学院大学)

ペンシルパズルにおける“面白い問題”とそうでない問題の違いを考察し,
“問題の面白さ”の定量的な評価方法を模索する.[発表資料(ppt)]

10. 名人の知とコンピューターの知 ―第2報―:中川 武夫(JAIST)

 2011年度、将棋名人第7局(森内9段 vs. 羽生名人)の各指し手の評価値を著者らの一人、
米長邦雄(永世棋聖)が決定した。同時に、コンピューター・ソフト「激指」によるこれら指し手の評価値も求めた。
 本論文においては、米長と「激指」の評価の類似と相違をデータ解析、並びに情報力学モデルを用いて検討・考察
を加えた。[発表資料(pptx)]

11. UCB+ 法を用いた Big Two AI の研究:○万代悠作, 橋本剛 (松江工業高等専門学校情報工学科)

本研究では中華圏を中心に人気の高いカードゲーム「Big Two」を題材に多人数不完全情報ゲーム AI について論じる.
Big Two は日本のカードゲーム「大貧民」によく似ているが, 出せるカードの組み合わせが
大貧民は 2167 通りに対し Big Two は 19898 通りとより複雑なゲームである.
実験により, 大貧民で成功したモンテカルロ法と UCB 値を組み合わせたアルゴリズムが
Big Two でも有用であることを示す.
またより強くするためにモンテカルロ法と UCB+ 値を組み合わせたアルゴリズムを提案し, 実験により優位性を示す.[発表資料(pptx)]

12. 後退解析を用いた完全情報七並べの解法導出:深川大路 (同志社大学 文化情報学部)

日本では最も代表的なカードゲームである七並べを題材に,
後退解析を用いた解法の導出と検証について研究を行った.[発表資料(pdf)]

13. 色塗りゲームとゲームカラーリング数:関口 陽介(慶應義塾大学大学院理工学研究科)

 2人のプレイヤーがグラフの頂点を与えられた色で交互に彩色していき,最後まで彩色
できたら先手の勝ちというゲームを色塗りゲームと呼ぶ.このとき,先手必勝になるため
に必要な色数をそのグラフのゲーム彩色数(game chromatic number)という.
 このゲーム彩色数を評価する1つの方法としてゲームカラーリング数(game coloring
number)を利用する方法がある.現段階で森や外平面グラフなどのゲームカラーリング数
がわかっていて,その値はゲーム彩色数の上限を与えている.
 本講演では主に平面グラフにおけるゲームカラーリング数について紹介する.一般の平
面グラフのゲームカラーリング数は17以下であることが知られているが,内周を制限した
場合にはその評価を強くすることができる.特に内周が4以上の場合は先手の戦略を工夫
することで14以下にまで切り下げられる.[発表資料(pptx)]


14. 区間表現をもつグラフ上でのFloodingゲームについて:上原隆平(JAIST)

Flooding gameとは,グラフ上の一種の彩色ゲームである.
近年,Flood-It,Mad Virus,HoneyBeeといった名前でオンラインで
楽しむことができる.ここ1〜2年,さまざまなグラフクラス上での
flooding game の計算量が活発に研究されている.例えば最大次数3の
木の上での1人ゲームでもNP完全であることがわかっている.本研究では,
区間表現を持つグラフクラス上で,このゲームの計算量を研究した.
そして特に彩色数が重要なパラメータであることがわかった.
色の数が定数に制限されている場合,interval graph の上でのゲームは
多項式時間で解ける.ところが,色の数が制限されない場合は,proper
interval graph 上でもNP完全となることがわかった.[発表資料(pdf)]

15. 一般化川渡り問題について:
○伊藤大雄(京都大学), Stefan Langerman(Universite Libre de Bruxelles), 吉田悠一(京都大学)

3人の男がそれぞれ一人ずつ未婚の妹を連れて川にさしかかった。川には二人乗りの
ボートが一艘あり、それを使って6人が向こう岸に渡りたい。ただし、男は警戒心が
強く、自分の妹が、自分の居ない所で他の男と同席することは我慢できない。上手く
渡る方法を示せ。これは最古の娯楽数学の本と言われる、アルクインによってラテン
語で書かれた「青年達を鍛えるための諸問題」にある問題で、その後様々なバリエー
ションを生んだ。また、その一般化も試みられており、Csorbaら[ESA07]によって
「アルクイン数」なる概念も提唱されている。本発表では、より一般性のある問題が
扱える別の定式化を提唱する。そしてボートの利用回数を最小にする問題では、ボー
トのサイズが3の場合にNP困難であり、逆に2の場合には、多くの部分問題が多項
式時間で解けることを示した。さらに到達可能性のみを問う場合には、たとえボート
サイズが3以上でも、多くの部分問題が多項式時間で解けることを予想している。[発表資料(pdf)]

世話役 伊藤大雄(京都大学)、岡本吉央(北陸先端科学技術大学院大学)