組合せゲーム・パズル プロジェクト [HP]

第12回 研究集会

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

日時　　２０１７年３月６日（月）

場所　　名古屋大学 ES総合館２階 ES021講義室 [地図]

位置付け等

プログラム


09:30 -- 10:30
1. 制限付き安定マッチングの確率的解析
大須賀 喜人，田地 宏一 (名大)
2. 木における1ラウンドボロノイゲームの後手の戦略
杉本晃弘，斎藤寿樹 (神戸大)
3. 二人単貧民の必勝判定問題
木谷裕紀、小野廣隆 (九大)
4. コード配色の変更を認めるマスターマインドの推測回数に関する考察
迫田賢宜、小野廣隆 (九大)

10:45 -- 11:45
5. 離散CTによる原子クラスター構造解析と組合せ最適化パズル
中島千尋，大関真之 (東北大)
6. パズル問題で得た知見を一般化して汎用AIを目指す：非ドメイン依存プランニングへの誘い
福永Alex (東大)
7. ペグソリテアフォントについて
及川大志（一関高専），山崎一明，谷口智子，上原隆平 （JAIST）
8. ペグソリティアとフォーティーワンの高速な解の数え上げ
兼本樹，斎藤寿樹（神戸大），上原隆平（JAIST）

（昼休み）

13:15 -- 14:15
9. 盤面上の単語配置問題
原口和也, 佐藤潤一 (小樽商科大)
10. 橋をかけろの解答・問題生成アルゴリズム
渡邊晃一朗 (電通大)
11. ナンプレのチェーン系解法のためのアルゴリズムについて
北本卓也（山口大）
12. ヒントの少ないナンプレの現状
早川友康（タイムインターメディア）

14:30 -- 15:30
13. 立方体展開図パッキング
伊野波 竜矢，井上 慶隆，小澤 孝行，宇野 裕之 （阪府大）
14. 拡張タングラムとラッキーパズルの凸配置について
岩井仁志，渋谷純吾，池田心，上原隆平 (JAIST)
15. 東京2020オリンピック・パラリンピックのエンブレムの多様性について
濱中裕明 (兵庫教育大), 堀山貴史 (埼玉大), 上原隆平 (JAIST)
16. "Sphinxes in Pyramid" and "Sphinxes in Hexagon"
堀山貴史（埼玉大），岡本吉央 (電通大) ，上原隆平（JAIST）

15:45 -- 16:45
17. Polyomino exclusion problem (続・ポリオミノのはみ出し可能な被覆問題)
岡圭吾，稲葉直貴
18. ポリオミノ敷き詰めパズルとライツアウトの定数時間アルゴリズム
竹田美弘, 長尾篤樹, 伊藤大雄 （電通大）
19. ペンシルパズル「シャカシャカ」の最小ヒント数
Michael Biro（Swarthmore College），浜本 知久（阪府大），Christiane Schmidt（Linko¨ping University），宇野 裕之（阪府大）
20. Parallel Crosses Puzzle とその計算量
末續鴻輝，小林 靖明，立木 秀樹 （京大），山田修司 （京産大）

17:00 -- 18:15
21. 一般化詰め中将棋問題のEXPTIME完全性
大森 潤一 (阪電通大)，木場 裕矢 (キヤノンシステムアンドサポート)，上嶋 章宏 (阪電通大)
22. レゾリューションゲーム
荒谷 真典 (東工大)
23. 格子上のマッチ棒パズル
三柴翔平、武永康彦、杉山晴香 （電通大）
24. マッチ棒数式パズルの計算機による求解
井上 慶隆，ヘン・ ブレンドン，宇野 裕之 （阪府大）
25. 多角形パズル問題のヒューリスティックスによる解法の検討
川上直人、橋本剛（松江高専）

 


[懇親会]

日時：研究集会終了後（19:00開始予定）
会場：グランピアット 山手通り店 【 地図 】
会場予約の都合上、懇親会の参加には事前登録が必要です。ご協力をお願いします。事前登録は->[ココ] （2/24(金)締切。ただしこの締切日前でも席数に達し次第締め切ります。早めにお申し込みください。）

 

 

各講演の概要と発表資料

1.制限付き安定マッチングの確率的解析：大須賀 喜人，田地 宏一 (名大)

概要：本報告では，安定マッチングを求めるためのゲール・シャプレーアルゴリズムにおいて，男女それぞれが第k番目までの選好しか表明できない，という制限を加えたときに，成立するペア数の平均を求めることを考える．容易にわかるように，第一位のみを表明した場合には，ペア数の平均は1となるが，それを，第2位まで，第3位までに拡張し，シミュレーション実験と比較する．また，全順位を表明した場合の極限を考えることで，男性最適アルゴリズムとの整合性があることを示す．[発表資料(pptx)]

2.木における1ラウンドボロノイゲームの後手の戦略：杉本晃弘，斎藤寿樹 (神戸大)

概要：(r,k)-ボロノイゲームはグラフの上で対戦する陣取りゲームである．先手と後手のプレイヤーはグラフ上の頂点をそれぞれ順番にk個ずつ選び，これをラウンド数r回繰り返す．選ばれていない頂点は，その頂点から距離がより近い頂点を選んだプレイヤーの陣地となり，陣地数の多いプレイヤーが勝利となる．本研究では，ラウンド数が1でかつグラフがp分木（pは定数）のボロノイゲームにおいて，先手の選んだk個の頂点が与えられた場合に，後手に勝利する手が存在するかどうかを判定する動的計画法を用いた多項式時間アルゴリズムを示す．[発表資料(pdf)]

３. 二人単貧民の必勝判定問題：木谷裕紀、小野廣隆 (九大)
概要：単貧民とは, 不完全情報多人数ゲームであるカードゲーム大貧民を完全情報ゲーム
として簡易化したものである. 本研究では札の種類を一般化した二人単貧民の勝者決定に
ついて考察する. 単貧民は二人完全情報性から, カードが配られた時点で先手後手のいず
れかに必勝戦略が存在する. 本研究では手札の枚数の総数nに対し, O(nlogn)時間で二人
単貧民の必勝プレイヤーとその必勝戦略を求めることができることを示す．[発表資料(pdf)]

4. コード配色の変更を認めるマスターマインドの推測回数に関する考察：迫田賢宜、小野廣隆 (九大)

概要：ゲーム・マスターマインドは2人によるゲームであり, 出題者があらかじめ定め
たピンの配置に対するクエリーを通して解答者がそのピンの配置を推定するゲー
ムである. 最もよく遊ばれているマスターマインドは, 6色4本のピンを配
置するものであり, それはどのような配置であったとしても, 必ず5回のクエ
リーによりピンの配置を知ることができることが知られている.
本研究ではそのルールを拡張した 「出題者が1回だけコードの一部
を変化させることができる」場合についての推測回数について考察する.
この場合, 推測回数の自明な上界は10回であること,
推測回数に少なくとも9回は必要であることがわかった. [発表資料(pptx)]
5. 離散CTによる原子クラスター構造解析と組合せ最適化パズル：中島千尋，大関真之 (東北大)
概要：電子顕微鏡によって得られた電子散乱強度から金原子クラスターの3次元構造を再構成する逆問題を考える 。この問題は電子線によって平面に射影された像から立体構造を推定する逆問題であり、ノノグラム（あるいはピクロス）と呼ばれるパズルと似た数理構造を持つ。
つまりパズルの問題が材料科学実験の中に宿った例となっている。
我々はこの問題の解の不定性を解析（充足解の数を数える）や、正則化により解を与える試みを研究している。講演では、解の個数の解析や正則化の内容を紹介するとともに、この再構成問題とピクロスの問題設定や性質の違いについて議論する。
6. パズル問題で得た知見を一般化して汎用AIを目指す：非ドメイン依存プランニングへの誘い：福永Alex (東大)
概要：人工知能分野における非ドメイン依存プランニング問題(Domain-independent Planning)
とは、形式的な言語で表現された初期状態、目的、及びルールを与えられ、特定の問題に対する知識に依
存せず、なるべく汎用な手法を用いて問題を解決する枠組みの研究分野であり、倉庫番、ハノイの塔等多くのパズル問題はPlanning問題として表現できる。
一方、特定のパズル・ゲームに対する研究で得た知見をPlanningの枠組みに組み込むことにより、汎用AIを目指す研究に貢献することも可能である。
特定のパズル問題（倉庫番）に対する考察及び探索手法から始まり、その手法を非ドメイン依存Planningの枠組みで多くの問題に対して自動的に対応可能にした事例を紹介する。
7. ペグソリテアフォントについて：及川大志（一関高専），山崎一明，谷口智子，上原隆平 （JAIST）
概要：ペグソリテアとは代表的なパズルの一つである．理論計算機科学の視点からは，
このパズルはNP完全であり，一般に手に負えないことが1990年に証明されてい
る．実際のパズルの盤面には33個の穴があり，ここに32本のペグが乗っている．
パズルの愛好家によって多くの解が手作業で見つけられ，また1990年代には発
見的アルゴリズムも開発された．しかし近年の（スーパー）コンピュータに高
速なアルゴリズムを実装すれば，このサイズのパズルであれば，すべての解を
数分で列挙することができる．言い替えると，妥当な大きさの実際のペグソリ
テアは，現実的な意味で解くことができる．この技術を使うと，次のような
「ペグソリテアフォント」をデザインすることができる．ペグソリテアの盤面
の大きさとして5×7を選び，35個の穴のうち，中央を除く34箇所にペグを置く．
まず，この初期盤面から到達可能なすべてのパターンをスーパーコンピュータ
で全列挙した．その結果，初期盤面から到達可能な1,045,173,439個のパター
ンを得た．この到達可能なパターンの中から，フォントを抽出（あるいはデザ
イン）した．つまりすべてのアルファベットは，初期状態から到達可能なパター
ンであり，それぞれについてソリテアパズルを楽しむことができる．[発表資料(pptx)]
8.ペグソリティアとフォーティーワンの高速な解の数え上げ：兼本樹，斎藤寿樹（神戸大），上原隆平（JAIST）
概要：ペグソリティアは世界中で楽しまれている有名なパズルで，プレイヤーはジャンプというルールに従って盤面に置かれたペグを1つずつ取り除いていき，ゴールとなる盤面を目指すパズルである．
また類似したパズルに，ペグソリティアとジャンプのルールは同じで，盤面が異なるフォーティーワンというパズルがある．
本研究では，これらのパズルの解の総数を求めるアルゴリズムを提案する．
アルゴリズムは動的計画法に基づいた力任せ探索に，効率的な枝刈りを取り入れたもので，このアルゴリズムがこれら2つのパズルに対して現実的な計算時間で解を数え上げることを示す．[発表資料(pdf)]
9. 盤面上の単語配置問題：原口和也, 佐藤潤一 (小樽商科大)
概要：単語配置問題とは, nxn盤面と辞書 (単語の集合) が与えられ,
辞書に含まれる単語を盤面上に「うまく」配置することを問う問題である.
これはクロスワードパズルやスケルトンパズルの生成問題を一般化した問題である.
本研究ではこの問題を整数線形最適化問題として定式化し, ソルバを用いて解を求める.
既存のパズルの再現や, 特徴的な辞書を用いたパズルの生成など, いくつかの実験を行った.
本発表ではその結果を報告する.[発表資料(pdf)]
10.橋をかけろの解答・問題生成アルゴリズム：渡邊晃一朗 (電通大)
概要：本研究はニコリのペンシルパズル「橋をかけろ」の問題を，絵をもとにして生成
できるアルゴリズムを作成することを目的としている．生成された問題を解くと，
入力に使用した絵が浮かび上がってくる．まず「橋をかけろ」の問題をゆるく解
く「近傍島アルゴリズム」と，それを利用し，問題の解の唯一性を判定するアル
ゴリズムを作成し，問題生成アルゴリズムの内部で利用した．これによって，問
題生成アルゴリズムで生成される問題は唯一の解を持つようにすることができた．[発表資料(pdf)]
11. ナンプレのチェーン系解法のためのアルゴリズムについて：北本卓也（山口大）
概要：ナンプレは世界中で広く行わえているパズルである。
本発表では、ナンプレを解くためのチェーン系の解法のための
アルゴリズムについて述べる。
チェーン系の解法は強力ではあるが、時間がかかるという欠点を
持っている。そこで無駄を省いた計算法について考察する。
また、ALS( Almost Locked Set )とチェーン系アルゴリズムとの
関係について述べる。[発表資料(pdf)]
12.ヒントの少ないナンプレの現状：早川友康（タイムインターメディア）
概要：以下のナンプレを生成した。
・10x10(2x5), ヒント数22
・12x12(2x6), ヒント数32
・12x12(3x4), ヒント数30
・15x15(3x5), ヒント数48
・16x16(4x4), ヒント数55
・25x25(5x5), ヒント数146
これらについて報告する。[発表資料(pdf)]
13. 立方体展開図パッキング：伊野波 竜矢，井上 慶隆，小澤 孝行，宇野 裕之 （阪府大）
概要：有限盤面に対して与えられた形を詰込む（切取る）パッキング問題は，
タイリングとともに基本的である．
本研究では，長方形盤面に対して立方体展開図のパッキング問題に対し，
その先行研究を整理しいくつかの進展を報告した上で，新たな未解決な問題を探る．
14. 拡張タングラムとラッキーパズルの凸配置について：岩井仁志，渋谷純吾，池田心，上原隆平 (JAIST)
概要：タングラムや清少納言知恵の板は代表的なシルエットパズルである．
このパズルはどちらも，凸多角形のピース7つから構成されている．
各ピースはポリアボロ（直角2等辺3角形を基本とする図形）であり，
全体の面積は直角2等辺3角形16枚分である．こうしたパズルで凸多角形を作ろ
うとすると，タングラムで13種類，清少納言知恵の板では16種類作れることが
わかっている．同じ制約のもとで7ピース組のパズルを考えると，19種類作れ
るパターンがあることが近年明らかになった．しかしピース数を減らして，
6ピース以下のパズルを考えると，最大何種類作れるか，わかっていなかった．
本研究ではまず，ピース数を2から6までとしたときに作れる凸多角形の種類を
最大化する問題を考える．具体的に最大値を与えるピース構成をすべて特定し
た．次にこの手法を拡張し，ラッキーパズルで作れる凸多角形の個数を考えた．
この数値はパズル業界では以前から21であると言われていたが，
それが正しいことを確認できた．[発表資料(pptx)]
15. 東京2020オリンピック・パラリンピックのエンブレムの多様性について：濱中裕明 (兵庫教育大), 堀山貴史 (埼玉大), 上原隆平 (JAIST)
概要：「組市松紋」と呼ばれる、東京2020オリンピック・パラリンピックの
エンブレムには、「多様性と調和」のメッセージが込められている。
これらのエンブレムは、3種類の長方形からなり、いずれも
辺の長さの同じ3種類の菱形に由来している。したがって、
エンブレムは、これらの菱形の12角形へのタイリングとみなすことができる。
本講演では、2n 角形へのタイリングと紐の交差との対応について述べ、
タイリングの列挙結果を示す。
16. "Sphinxes in Pyramid" and "Sphinxes in Hexagon"：堀山貴史（埼玉大），岡本吉央 (電通大) ，上原隆平（JAIST）
概要：ピラミッドの中にスフィンクスを敷き詰めたり，正六角形の中に
スフィンクスを敷き詰める問題について，考えたことを発表する．
17. Polyomino exclusion problem (続・ポリオミノのはみ出し可能な被覆問題)：岡圭吾，稲葉直貴
概要：ポリオミノTを何枚か重ねずに使ってポリオミノSを覆える（Sからはみ出しても良い）とき、
SはTによって覆えるということにする。T の回転、裏返しは許す。
Sが穴の開いていないどんなポリオミノTによっても覆えるとき、Sは「必ず覆える」ということにする。必ず覆えるポリオミノをすべて求めたい。逆に、そうでないポリオミノに関しては、それを覆えないポリオミノを見つけたい。例えば、覆われる側のポリオミノを I ペントミノ とすると、覆う側のポリオミノとして、下図のような、I を覆えないポリオミノが存在する。(１×５が覆えない)
２０１０年にこの問題に関して発表したが、その後の進展について発表する。必ず覆えるポリオミノの候補を有限個まで減らすことに成功し、未解決のポリオミノの数が20個となった。特に、9-omino 以上のポリオミノには、それを覆えないポリオミノが存在することを構成的に示した。(発見に使用したプログラム)[発表資料(pdf)][Google slideへのリンク]

 

18. ポリオミノ敷き詰めパズルとライツアウトの定数時間アルゴリズム：竹田美弘, 長尾篤樹, 伊藤大雄 （電通大）
概要：ボードゲームに対する定数時間アルゴリズムを構築した。
具体的には、ポリオミノ敷き詰めパズルとライツアウトについて、
与えられた局面が実行可能（解を持つ）かそれからε遠隔かを検査する
定数時間アルゴリズムを与えた。[発表資料(pptx)]

19. ペンシルパズル「シャカシャカ」の最小ヒント数：Michael Biro（Swarthmore College），浜本 知久（阪府大），Christiane Schmidt（Linko¨ping University），宇野 裕之（阪府大）

概要：ニコリによるペンシルパズル「シャカシャカ」の計算複雑さは，
Demaine らによりNP完全であることが知られている．
またBiroらはシャカシャカが一意解を持つために必要な最小ヒント数の上界を与えている．
本研究では，その上界を改善するとともに，新たにヒント数の下界を与える．
20. Parallel Crosses Puzzle とその計算量：末續鴻輝，小林 靖明，立木 秀樹 （京大），山田修司 （京産大）
概要：Parallel Crosses Puzzle は，2種類の深さの n 個の溝のある 2n 本の棒を，深さが合うように n x n に組み合わせる，山田修司氏が考案したパズルである。このパズル，および，その変形したパズルの計算量について述べる。
21.一般化詰め中将棋問題のEXPTIME完全性：大森 潤一 (阪電通大)，木場 裕矢 (キヤノンシステムアンドサポート)，上嶋 章宏 (阪電通大)
概要：本研究では，古将棋の一種である中将棋の計算複雑さを議論する．
中将棋とは（縦）12×（横）12マスの盤面で，本将棋での桂馬以外の
7種と中将棋独自の14種を合わせた21種類の駒を使用して勝敗を競う
ゲームである．本将棋とは異なり，桂馬がなく，持ち駒の概念がない
ことから，中将棋は本将棋の単純な拡張にはなっていない．本研究で
は詰め将棋と同様の連続王手制限を設けた問題を詰め中将棋と呼び，
この問題のEXPTIME完全性を証明する．
本研究では連続王手制限付き一般化チェスのEXPTIME完全性の証明を
参考に，既知のEXPTIME完全性問題であるG4ゲームから対数領域還元
可能であることを示す．なお，チェスのナイトと同種の駒が中将棋に
はないことに注意されたい．我々の還元は初期盤面に成り駒がないと
いう制限を満たす．
22. レゾリューションゲーム：荒谷 真典 (東工大)
概要：CNF論理式に対する操作である導出原理(resolution principle)を用いたパズルゲーム, レゾリューションゲームを定義した. このゲームが解を持つかどうかの判定問題は論理式の節の大きさが3以上としてよいならNP完全であるが, 2以下とした場合はまだわかっていない. 発表では, 節の大きさが２以下の場合でも, ゲームのルールに変更を加えるとNP完全を示せる場合や, 多項式時間で解けてしまう場合があることをについて話す.
23. 格子上のマッチ棒パズル：三柴翔平、武永康彦、杉山晴香 （電通大）
概要：マッチ棒パズルはマッチ棒を指定された本数動かして条件を満たす配置にするパズルである。
本研究では、マッチ棒を置く位置を格子上に限定し、指定された形を作る問題、正方形を
指定された個数作る問題のアルゴリズム、計算複雑さを示す。

24. マッチ棒数式パズルの計算機による求解：井上 慶隆，ヘン・ ブレンドン，宇野 裕之 （阪府大）

概要：マッチ棒パズルの一種に，マッチ棒で表された誤った数式を
指定された本数のマッチ棒を移動し正しく直すものがある．
本研究では，その問題を計算機で解くことを試みた．

25. 多角形パズル問題のヒューリスティックスによる解法の検討：川上直人、橋本剛（松江高専）

概要：高専プロコンで単純多角形ピースを枠穴に入れるパズル（多角形パズル）が出題された.
多角形パズルはタングラムより形の自由度が高く、多角形詰込み問題に100％詰込み可能条件を加えたものと位置付けられる。
本研究では結合度を計算するヒューリスティックスを使う手法を提案し、実験と考察を行う.[発表資料(pptx)]
 

世話役　伊藤大雄、岡本吉央（電気通信大学）