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

第14回 研究集会

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

日時  2019年3月10日(日)、11日(月)

場所  電気通信大学 西9号館1階135教室(初日)、西9号館3階AVホール(二日目)[地図]

位置付け等

プログラム(各講演の題目のリンクをクリックすると概要に行きます。)

3月10日(日)西9号館1階135教室

10:00 -- 10:50
1. Posit の必勝戦略の解析
熊崎 良亮,〇元木 光雄(金沢工大)
2. のりのり, 変形版へやわけのゼロ知識証明に対する物理プロトコル
○迫田賢宜(名古屋大), 小野廣隆(名古屋大)

11:00 -- 11:50
3. 敷詰めパズルのZDDを用いた解列挙手法
渡邊晃一朗
4. 凹凸のあるピースにおけるアンチスライドパズルの解析
〇木村 健斗, 天野 一幸

(昼休み)

14:00 -- 14:50
5. 円形ニムとその展開
末續鴻輝
6.. p飽和マヤゲームと対称群の既約表現
入江佑樹

15:00 -- 15:50
7. Multi-layer generalized Petersen graph上で行うCops and Robbers game
菅 亮太
8. 頂点Kaylesに対するモジュラ幅FPTアルゴリズム
小林靖明 (京大)

16:00 -- 17:15
9. パズルの唯一解をめぐるヒント数の計算量について
長尾篤樹(お茶の水女子大学)
10. 平行もしくはジグザグ斜め山谷付き折り目により紙帯の平坦折り
伊藤大雄(電通大)・奈良知惠(明大)・白濱和泉(ecbeing)・○戸村瑞穂(電通大)
11. 雨中走行濡量の公式
伊藤大雄(電通大)

 

3月11日(月)西9号館3階AVホール

09:30 -- 10:20
12. 簡略化された麻雀に対する強化学習の価値関数近似の妥当性の検証
清水大志
13. ニューロ・ダイナミック・プログラミングを用いたリアルゲーム戦略分析
白水 椋大、大久保 幸美、佐藤 真史、豊泉 洋(早稲田大)、鈴木 量三朗(株式会社 シンビー)

10:30 -- 11:20
14. 特殊版クロンダイクの成功率に関する実験的評価
平河 航佑, 深川 大路 (同志社大)
15. Mind the Mind with Synchronous Clocks
堀山貴史 (埼玉大),栗田和宏 (北大),岡本吉央 (電通大),内澤啓 (山形大),上原隆平 (北陸先端大)

(昼休み)

13:30 -- 14:20
16. 亜流オセロ
塚村善弘
17. 逆型ゲームを用いた囲碁の攻合い問題の解析
中村貞吾(九州工業大学)

14:30 -- 15:45
18. 拡張単貧民における必勝判定
木谷 裕紀, 大渡 勝己, 小野 廣隆
19. Making Many Polygons by Simple Fold and One Straight Cut
Hu Guoxin(JAIST), 上原隆平(JAIST)
20. Impossible Folding Font
Erik D. Demaine (MIT), Martin L. Demaine (MIT), 谷口智子(JAIST), 上原隆平(JAIST)

 


[懇親会]

日時:初日(3月10日)の研究会終了後
会場:ラージャ 調布店
参加費:4,000円程度を予定
会場予約の都合上、懇親会の参加には事前登録が必要です。事前登録は->[ココ](2/27(水)締切)

 

 

各講演の概要

1. Posit の必勝戦略の解析:熊崎 良亮,〇元木 光雄(金沢工大)

概要:Positは6×6正方形の盤面で二人のプレーヤーが交互に駒の移動とブロックの
配置を行う,アブストラクトゲームである.駒の移動には制約があり,制約
を満たす駒の移動が先にできなくなったプレーヤーが負けとなる.このゲーム
における必勝プレーヤーの有無をBDDを用いて解析した.

2. のりのり, 変形版へやわけのゼロ知識証明に対する物理プロトコル:迫田賢宜(名古屋大), 小野廣隆(名古屋大)
概要:ゼロ知識証明とは, 証明者が「ある命題が真であることを知っている」と伝えるのに, それ以外の知識を漏らすことなく, 検証者に証明できるようなやりとりの手法である.
これは情報セキュリティに大きく関わる手法であるが, カードなどの物理的な道具を用いることによっても実装可能であることが知られている. これらのプロトコルは, 人の手によって道具を用いて実行されるため, 高校生といった非専門家にもプロトコルの安全性や実行の過程などを理解しやすいという利点をもつ.
2009年に数独に対する物理的ゼロ知識証明プロトコルが考案されて以降, さまざまなペンシルパズルに対する物理プロトコルが考案されている.
本研究ではNP-完全問題として知られる, のりのりと変形版へやわけの2つのペンシルパズルに対する物理プロトコルを考案する.
3. 敷詰めパズルのZDDを用いた解列挙手法:渡邊晃一朗
概要:ペントミノなどの敷詰めパズルは厳密被覆問題に定式化して解くことができる.厳密被覆問題の解を効率良く列挙する手法として,Algorithm DXZ(西野ら,2017)が開発されたが,本研究では,これを敷詰めパズルに特化した手法を開発し,その性能の考察を行った.

4. 凹凸のあるピースにおけるアンチスライドパズルの解析:〇木村 健斗, 天野 一幸

概要:ある大きさの箱と指定されたある形のピースが与えられたとき,
同じ形のピースを箱に詰め,
全てのピースがどんな方向にも動かないような詰め方を求める問題を考える.
このような問題をアンチスライドパズルとよぶ.
答えの中でピースの個数が最少となるようなものを最適解とする.
その最適解を探すことが本研究の1つの目標である.
 天野ら(JIP,2015)はこの問題を整数計画問題として定式化し,
IPソルバを用いて解くことで,
いくつかの形状のピースに対して解析を行った.
しかし, より複雑な形状のピースを用いた場合の最適解については明らかでない.
 本研究は, 凹凸のある7種類の形状のピースに対して,
最適解の探索および理論的定式化を目指す.
キーワード -- アンチスライドパズル; 整数計画問題; IPソルバ; パズル
5. 円形ニムとその展開:末續鴻輝
概要:円形ニム(Circular Nim)CN(n,k)とは、いくつかの石でできたn個の山が円形にならんでおり、
プレイヤは、隣接する高々k個の石の山から、好きな数だけ石を取っていくゲームである。最後の石を取った
方(最終手を着手した方)の勝ちである。
 このゲームはよく知られたゲームであるNimの変種であり、CN(n,1)はn山Nimとみなせる。また、CN(n,n)も全体
を一つの山としてNimとみなすことができ、CN(n,n-1)はMoore's gameの特殊な場合とみなすことができ、必勝者
が判定できるが、nとkの関係がそれ以外の多くの場合は未解決である。
 ここでは、すでに必勝判定法が知られているいくつかの場合について紹介し、さらにそれらの既存研究を様々に
変形したゲームについても議論する。
6. p飽和マヤゲームと対称群の既約表現:入江佑樹
概要:ゲームと表現の間の一つのつながりを紹介する. 1970年代頃, 佐藤幹夫は
「マヤゲームのSprague-Grundy関数の明示公式」と「対称群のフック公式」
の形が似ていることなどから, 両者には見かけ以上の関連があることを予想した.
本講演では対称群の既約表現の次数に関する定理を与え, この定理からp飽和マヤ
ゲームのSprague-Grundy関数の明示公式が得られることを紹介する. [発表資料(pdf)]
7. Multi-layer generalized Petersen graph上で行うCops and Robbers game:菅 亮太
概要:Multi-layer generalized Petersen graph上で行うCops and Robbers game
概要:Cops and Robbers gameとは,警官と泥棒のプレイヤー2人がそれぞれ警官と泥棒に見立てた互いの駒を頂点に配置,移動させ,最終的に警官の駒が泥棒の駒がいる頂点へ移動できるかどうかを争うゲームである.
本研究では,Multi-layer generalized Petersen graph上で行われるゲームについての解析を行い,警官のプレイヤーが勝つために必要な最小の数の上界を示した.
8. 頂点Kaylesに対するモジュラ幅FPTアルゴリズム:小林靖明 (京大)
概要:頂点Kaylesに対するモジュラ幅FPTアルゴリズム
概要: 頂点Kaylesはグラフ上で行う二人プレイヤーゲームで,各プレイヤーは交互に頂点とその隣接点すべてをグラフから削除していき,頂点を削除できなくなったプレイヤーの敗北である.このゲームにおいて先手に必勝戦略が存在するかどうかを判定する問題はPSPACE完全であることが知られている.本発表では,与えられるグラフのモジュラ幅が小さい場合は頂点Kaylesが効率よく解けることを示す.[発表資料(pdf)]
9. パズルの唯一解をめぐるヒント数の計算量について:長尾篤樹(お茶の水女子大学)
概要:一般的なNP完全な問題とは異なり,(NP完全な)パズルのインスタンスを作成する場合は解が唯一解となることが望ましい.
本講演では,『あるパズルのインスタンスが解をもつか』というありふれた問題からさらに踏み込み,
『与えられた解以外に解をもつか』『与えられた解が唯一解となるようなk個のヒントを追加する手法が存在するか』という既存の問題を紹介し,
『あるインスタンスが解を持たず,解を持つようなk個のヒントを削除する手法が存在するか』『同様に唯一解となるように削除する手法が存在するか』
という問題がどのような計算量クラスとなるかを考察する.
また,余裕があればそれらがそのクラスでの完全問題となることを示す.
10. 平行もしくはジグザグ斜め山谷付き折り目により紙帯の平坦折り:伊藤大雄(電通大)・奈良知惠(明大)・白濱和泉(ecbeing)・○戸村瑞穂(電通大)
概要:平坦折り可能性問題は折り紙数学の代表的な問題であり,それは有限平面より
なる紙とその上に書かれた折り線の集合が与えられたときに,各折り線に指定
された山折りか谷折りかの指示通りにすべての折り線を同時に平坦に折ること
ができるかという問題で,NP完全であることが知られている.しかし多項式時
間で解ける部分問題もいくつか知られており,その代表的なものとして,紙を
長方形の帯に限定し,折り線を紙帯の長軸方向に対して垂直とした場合(一次
元山谷付き平坦折り問題)には,線形時間アルゴリズムがArkinらによって与
えられている.本研究では,紙帯上の折り線が長軸となす角度を($\pi/2$に
限らず)任意の角度$\theta$ですべて等しい(すなわち全ての折り線は平行)
とした問題と,合計の角度が$\pi$となるような2種類の折り線が交互にジグザ
グ状に並んでいる問題を考えた.そして前者に対し線形時間アルゴリズムを与
え,後者に対しては常に平坦折り可能となることを示した.[発表資料(pdf)]
11. 雨中走行濡量の公式:伊藤大雄(電気通信大学)
概要:「雨の中を走っても歩いても濡れる量は同じ」という俗信がある。
本講演ではこの俗信がなぜ生まれたかを解説し、では実際は、雨中を歩行
するのと走行するのと濡れる量はどれぐらい違うのかについて考察した。
その結果、無風状態で通常の雨量または豪雨の中を通常の体型の人間がある程度の距離を
通常の歩行速度で歩いた時に濡れる量を1とした場合、同条件でそのx倍の速さで走った
場合の濡れる量を表す非常に簡潔な公式を得たので紹介する。[発表資料(pptx)]
12. 簡略化された麻雀に対する強化学習の価値関数近似の妥当性の検証:清水大志
概要:強化学習を麻雀に適用し、各牌の残り枚数を考慮した打牌ができるかどうかの検証を行った。ゲームを強化学習に適用する際にはテーブル型という全ての状態行動対の価値を保持する方法が基本であるが、通常の麻雀では状態数が大きすぎてこの方法を用いることは難しい。そのため本研究では簡略化した一人プレイや複数人プレイでの麻雀に対して、価値関数を近似した強化学習を適用した。価値関数の近似には線形近似やより高度な機械学習手法を用い、それぞれの手法で各牌の残り枚数を考慮した打牌ができるかどうかの考察を行った。[発表資料(pptx)]
13. ニューロ・ダイナミック・プログラミングを用いたリアルゲーム戦略分析:白水 椋大、大久保 幸美、佐藤 真史、豊泉 洋(早稲田大)、鈴木 量三朗(株式会社 シンビー)
概要:近年将棋や囲碁のようなボードゲームでは、AIによる最適手の探索の有効性が実証されている。しかし、テニスなどのリアルなスポーツゲームでは必ずしも自分の狙い通りの戦略が実現できない場合も多い。不確実な状況での最適戦略を導出する方法として、ニューロ・ダイナミック・プログラミングという最適化手法が研究されている。本研究ではオセロとテニスへの応用を題材に、汎用AI学習ツールYOLOを用いた画像認識とニューロ・ダイナミック・プログラミングを組み合わせる手法の可能性を議論する。
14. 特殊版クロンダイクの成功率に関する実験的評価:平河 航佑, 深川 大路 (同志社大)
概要:クロンダイクはトランプを用いたソリティアの代名詞的な組合せ一人ゲームである.カードの枚数を一般化した確定ゲーム版クロンダイクはNP困難であることが知られている.一方,標準的な52枚のカードを用いた確定ゲーム版クロンダイクの理論的な成功率についてはかなり高いことが分かっているものの,未だに決定されていない.本発表では,確定ゲーム版クロンダイクの特殊版について,計算機実験を用いた成功率の解析を行う.[発表資料(pdf)]
15. Mind the Mind with Synchronous Clocks:堀山貴史 (埼玉大),栗田和宏 (北大),岡本吉央 (電通大),内澤啓 (山形大),上原隆平 (北陸先端大)
概要:2018年のドイツ年間ゲーム大賞にノミネートされた『The Mind』は
Wolfgang Warschが制作したスキャンダラスなカードゲームである.
この研究では,プレイヤーの時計が同期しており,各プレイヤーに
配られるカードが1枚である場合を考える.そのとき,与えられた
制限時間内にプレイヤーたちが勝利する確率を最大にする戦略を見
つけるアルゴリズムを導出した.[発表資料(pdf)]
16. 亜流オセロ:塚村善弘
概要:1. 両面が左半分白、右半分黒のハーフの石を2個作る。ひっくり返しても同じ模様。
2. 競技者各々がハーフを1個づつ持ち、任意の局面で打つ。
3. 打たれたハーフは白石とみなしても、黒石とみなしても良い。[発表資料(pptx)]
17. 逆型ゲームを用いた囲碁の攻合い問題の解析:中村貞吾(九州工業大学)
概要:組合せゲームの勝敗条件が,「着手できなくなったプレイヤの勝ち
(最後に着手したプレイヤの負け)」とするものは逆型ゲームと呼
ばれる.ここでは,囲碁の攻合い局面を逆型の非不偏ゲームとして
記述して,その勝敗の解析を行なう.
18. 拡張単貧民における必勝判定:木谷 裕紀, 大渡 勝己, 小野 廣隆

概要:「単貧民」とは, 不完全情報多人数トランプカードゲーム「大貧民」を完全情報ゲームとして簡易化したものである. この「単貧民」は札の種類を一般化した二人単貧民の勝者決定が線形時間でできることが知られている. 本研究では単貧民のいくつかの自然な拡張を与え, その必勝判定に関して示す.

 

19. Making Many Polygons by Simple Fold and One Straight Cut:u Guoxin(JAIST), 上原隆平(JAIST)

概要:計算折り紙の分野では,与えられた任意の平面グラフが一刀切りによって切り
出せるという万能定理がよく知られている.この万能定理の証明において
Demaineらは複雑な折り方を多用している.その後,折り方を全層単純折りに
限定し,一つの単純多角形を一刀切りで切り出すという問題が研究されている.
ここでは,この研究の「一つの単純多角形」を「複数の単純多角形」に一般化
した場合についての研究の現状と課題を発表する.[発表資料(pdf)]
20. Impossible Folding Font:Erik D. Demaine (MIT), Martin L. Demaine (MIT), 谷口智子(JAIST), 上原隆平(JAIST)
概要:Hyper Cardと呼ばれる,一見すると折るのが不可能に見える折り紙がある.
これはマーティン・ガードナーのサイエンティフィック・アメリカン誌の記事
をきっかけに知られるようになり,マジックショップなどでも売られている.
近年の折り紙シミュレータや折り紙を表現するファイルフォーマットなどの
開発により,こうした既存の折り紙からやや離れたパズル的な折り紙もコン
ピュータで表現できるようになってきた.本発表では,こうした「一見不可能
に見える折り紙」の技法でデザインしたフォントや,その可視化について紹介
する.
 

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