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

第13回 研究集会

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

日時  2018年3月6日(火)、7日(水)

場所  大阪府立大学 中百舌鳥キャンパス A12棟サイエンスホール(堺市中区学園町1-1)[地図]

位置付け等

プログラム ->[pdf版]


注:講演時間は質疑込みで一人当たり22分、交代時間1分。講演中の質問を推奨します。発表に使用するパソコンは各自ご用意ください(プロジェクタはVGA入力にのみ対応しています)。

3月6日(火)

10:00 -- 10:45
1. 不偏ゲームのGrundy数に現れる代数構造Loop
末續 鴻輝 (京都大)
2. 一般化ペグソリティアの可解性
伊藤 和司, 武永 康彦 (電通大)

10:55 -- 12:03
3. 5パズルの最短手数とその配置
檜垣 将之 (愛媛県立三崎高等学校)
4. 制約が少ないナンプレの最少ヒント数
早川 友康 (タイムインターメディア)
5. パズル「シャカシャカ」の正方形盤面での最小ヒント数
大塚 幸成, 宇野 裕之 (大阪府立大)

(昼休み)

13:30 -- 15:24
6. 機械学習を用いたカードゲームの人間らしさの実装に関する考察
真鍋 浩太郎 (電通大)
7. DFAを用いた覆面算の解析
野崎 裕樹, 吉仲 亮, 篠原 歩 (東北大)
8. graph grabbing game について
松本 直己 (成蹊大)
9. 消防士問題に対するモジュラ幅FPTアルゴリズム
吉村 純弥 (熊本大),清見 礼 (横浜市大),大舘 陽太 (熊本大)
10. オイラーグラフ上の帰還ゲーム
長尾 篤樹 (成蹊大)

15:40 -- 17:10
11. 麻雀データを用いた人間行動特性
鵜野 秀隆 (早稲田大)
12. 戦術的観点からの変形碁盤間の類似度評価
佐藤 真史 (早稲田大)
13. 分裂式制限ニム
山崎 浩一, 五十嵐 善英 (群馬大), 塚村 善弘
14. ノーパン
塚村 善弘

 

3月7日(水)

09:30 -- 10:38
15. 最小パウロス当選モデル
関本 健悟 (名古屋大), 木谷 裕紀 (九州大), 小野 廣隆 (名古屋大)
16. 手札公開で行う「ババ抜き」の必勝戦略の非存在性について
木谷 裕紀 (九州大), 小野 廣隆 (名古屋大)
17. Simple-Kalahにおける勝敗確定の十分条件
前井 康秀, 木谷 裕紀, 土中 哲秀 (九州大), 小野 廣隆 (名古屋大)

10:50 -- 11:58
18. 地図迷路自動作成プログラム
中村 俊介, 橋本 剛 (松江工業高等専門学校)
19. make10の一般化について
佐伯 元春, 西村 治道 (名古屋大)
20. 「四角に切れ」の定数時間検査アルゴリズム
竹田 美弘, 伊藤 大雄 (電通大)

(昼休み)

13:30 -- 15:01
21. Pyramidの計算複雑性
渡邉 光 (電通大)
22. ぷよを自由に配置できる場合のぷよぷよの連鎖数判定問題
澁谷 諒祐, 木村 慧 (豊橋技科大)
23. ペンシルパズル「Fill-a-Pix」のNP完全性
樋口 雄太, 木村 慧 (豊橋技科大)
24. 盤面を一般化した「フォービドゥン」パズルのASP完全性
田井 翔太, 上嶋 章宏 (大阪電通大)

15:15 -- 16:46
25. 一般化パイプパズルの計算量について
白山 卓夢 (JAIST), 大舘 陽太 (熊本大), 上原 隆平 (JAIST)
26. 公平なサイコロの作り方
谷口 智子, 上原 隆平 (JAIST)
27. 正確な訓練データを使ったニューラルネットワークによるゲーム局面の学習
神保 秀司 (岡山大学)
28. Implementation of Solver and Generator of Matchstick Puzzle Problems
Brandon Heng, Yoshitaka Inoue, and Yushi Uno (Osaka Prefecture University)

 


[懇親会]

日時:初日(3月6日)の研究会終了後(18:00開始予定)
会場:ダルマ食堂 :大阪府堺市東区白鷺町1-6-11(会場から徒歩7分程度)【 地図
参加費:3,500円程度
会場予約の都合上、懇親会の参加には事前登録が必要です。事前登録は->[ココ] (3/02(金)締切)

 

 

各講演の概要

1. 不偏ゲームのGrundy数に現れる代数構造Loop:末續 鴻輝 (京都大)

概要:不偏ゲームとは、完全情報ゲームであって、プレイヤーに応じて可能な着手が異ならないゲームのことであり、20世紀初頭からその代数的性質が議論され、代表的な結果としてはNIM(石取りゲーム)の必勝局面が、石の個数の2進表記を用いて求められることなどが知られている。また、NIMの議論を拡張して得られるGrundy数とは、すべての不偏ゲームの局面に対して定義できる数であり、必勝者の判定に強力な役割を果たす。そのため、ゲームの局面に対してGrundy数を簡単に計算する方法が存在するかどうかはこの分野における重要なテーマである。本研究においては、二つのパラメータを用いて局面を定義できる一部のゲームについて、その各局面のGrundy数を、パラメータを軸に取って表にまとめると、さながら演算表のように見え、群の仲間であるLoopという代数的構造を持っていることを示す。さらに、このようにゲームのルールから導かれたLoopがどのような性質を持っているのかということについて考察する。

2. 一般化ペグソリティアの可解性:伊藤 和司, 武永 康彦 (電通大)

概要:ペグソリティアを一般化したグラフ上のペグソリティアが提案されているが、これは通常のペグソリティアを表現できない。通常のペグソリティアを表現できる一般化を提案し、直積で表されるどのようなグラフが解を持つ、つまりペグを1個にできるかを考察する。[発表資料(pptx)]

3. 5パズルの最短手数とその配置:檜垣 将之 (愛媛県立三崎高等学校)
概要:数学パズルの1つに「15パズル」がある。15パズルとは,1〜15の番号が書かれた15個の正方形の駒を4×4の碁盤目状のボードで1つだけ空いた箇所にスライドすることによって,左上から右に向かって番号順に並べるパズルのことである。15パズルには解けるパズルと解けないパズルがあるが,解けるパズルに関しては15パズルの中にある任意の5パズル(2×3−1パズル)を順番にスライドすることで15パズルを解くことができる。そこで,本研究では5パズルに着目し,解ける5パズルの最短手数の最大値とその配置について,実際にパズルを動かしながら考察した。また,研究の発展として,5パズルを従来の平面としてではなく,円柱状にした場合の最短手数とその配置についても考察した。

4. 制約が少ないナンプレの最少ヒント数:早川 友康 (タイムインターメディア)

概要:ナンプレの最少ヒント数は17と証明されている。また、ブロックの制約が無い9×9のラテン方陣のパズルの最少ヒント数は20と考えられている。今回、その間のブロックが1〜3つの場合について調べたころ、ブロックが斜めに3つある場合ではヒントを16個まで減らせることが分かった。[発表資料(pdf)]
5. パズル「シャカシャカ」の正方形盤面での最小ヒント数:大塚 幸成, 宇野 裕之 (大阪府立大)
概要:ニコリのシャカシャカというペンシルパズルについて,正方形盤面において唯一解を持つための最小ヒント数に関するいくつかの新しい結果を報告する.
6. 機械学習を用いたカードゲームの人間らしさの実装に関する考察:真鍋 浩太郎 (電通大)
概要:近年,将棋や囲碁等でもプロプレイヤーに勝利するゲームAIが登場してきている.その一方で,強さではなく人間らしさの評価に関する研究が注目されている.そこで我々は,UNOをベースとして,プレイヤー同士が攻撃しあう様々な役カードを有するMADに,オリジナルルールを加えゲームAIの開発を進めている.現在は判断に乱数を用いたプログラムを作成しているが,これに機械学習を用いた個性を付加する場合の,人間らしさの評価と学習方法についての考察を行う.[発表資料(pptx)]
7. DFAを用いた覆面算の解析:野崎 裕樹, 吉仲 亮, 篠原 歩 (東北大)
概要:覆面算とは文字で与えられた数式の各文字に数を割り当てることにより正しい数式を導くパズルであり,その正しい数式を導く割り当てを覆面算の解と呼ぶ. 本研究は,k進数の加算の覆面算を網羅的に解析することを目的とする. 本発表では,k進数上で解を持つ覆面算を受理するDFAを効率よく構築するアルゴリズムを示す. さらに,このDFAを解析することにより,覆面算を列挙する手法を提案する. 特に,n桁の覆面算の総数を表す陽関数を,k=2と3に対してそれぞれ導出することに成功した.[発表資料(pptx)]
8. graph grabbing game について:松本 直己 (成蹊大)
概要:graph grabbing gameとは,2007年にP. Winklerによって定義された重み付き連結グラフ上におけるゲームで,グラフが非連結にならないように二人のプレイヤーが1頂点ずつ交互に取り除き,その重みを自身の得点として獲得していくゲームである.本講演では, graph grabbing game に関する最近の研究動向について発表を行う.[発表資料(pptx)]
9. 消防士問題に対するモジュラ幅FPTアルゴリズム:吉村 純弥 (熊本大),清見 礼 (横浜市大),大舘 陽太 (熊本大)
概要:消防士問題とは,グラフ上で燃え広がる炎の被害を最小化するための消防活動を求める問題である.この問題は非常に限定された入力(森など)に対しても,NP困難であることが知られている.本研究では,モジュラ幅を用いて既知のFPTアルゴリズムを一般化し,この問題が効率的に解ける範囲を拡大する.[発表資料(pdf)]
10. オイラーグラフ上の帰還ゲーム:長尾 篤樹 (成蹊大)
概要:本発表では以下のような無向オイラーグラフ上での二人ゲームについての紹介を行う.
1.偶次数無向グラフ上のある節点に石が置かれている状況から始まる.
2.プレイヤーは交互に石を「まだ使用されていない枝」が接続している節点へ石を動かす.
3.最初に石が置かれていた節点へ石を動かせたプレイヤーの勝利
このゲームにおいて,入力グラフと初期節点がある条件を満たすとき後手必勝であることが確認できており,その条件と証明手法の紹介を行う.また,本ゲームはシンプルであるが先行研究がほとんど確認できていないため,このゲームの名前を含め,関連情報を広く募集する事も本発表の目的となる.
11. 麻雀データを用いた人間行動特性:鵜野 秀隆 (早稲田大)
概要:麻雀ゲームにはたくさんの選択行動があり、ゲーム中常に人間は選択の機会を与えられています。本研究では選択行動の中の1つである立直(リーチ)に焦点を当て、麻雀の牌譜データを元に立直(リーチ)に関する人間の選択行動を分析します。
12. 戦術的観点からの変形碁盤間の類似度評価:佐藤 真史 (早稲田大)
概要:囲碁は一般的に正方形の碁盤を用いて行われるが、ルールの性質上任意の無向グラフで行うことができる。これら特殊な碁盤上の囲碁はそれぞれ有効な戦術が異なるため、無向グラフを用意するだけで似ているゲームを簡単に大量に用意できる。今回は、ゲーム間の類似度という概念を有効な戦術という観点から評価する手法を提案する。[発表資料(pptx)]
13. 分裂式制限ニム:山崎 浩一, 五十嵐 善英 (群馬大), 塚村 善弘
概要:「棒消しゲーム」と「制限ニム」を混ぜ合わせたゲーム。ルールは
(1)隙間なく並べた石、「k0個一列」をA、B、が交互に取る、取れる数は1〜m個。
(2)取る1〜m個の石は何処からでも良いが、全て隣接してなければならない。
(3)直前に相手が取った数は取れない。但し、1個は何時でも取れる。
(4)最後に取らされた方が負け、逆ニム。
m=5の場合の検討例を示す。[発表資料(pptx)]
14. ノーパン:塚村 善弘
概要:「正直者(H)、嘘つき(L)、天邪鬼(K、答えが不定)が居て、Yes、No、で答えられる質問合計3問で誰が何者か当てる。」この問題は有名であるが、これに追加して、この中、1人がノーパン(M)である。同じく3問で誰がMか当てる。H,L,K,は当てる必要はない。当てればその娘が今宵デートに応じる。3人ともお互いの属性と誰がノーパンかは知っている。[発表資料(pptx)]
15. 最小パウロス当選モデル:関本 健悟 (名古屋大), 木谷 裕紀 (九州大), 小野 廣隆 (名古屋大)
概要:投票システムとは,意思決定の一形式であり,投票者の集団が選択肢の順列を各人の選好の形で投票した際に,どの選択肢を集団の意思とするかを定めるものである.その決定のためのルールを投票システムにおける当選方式と呼ぶ.パウロス当選モデルとは,5つの選択肢からなる投票システムにおいて,5つの当選方式を考えた際,その5つの当選方式によって選ばれる選択肢がすべて異なるもののことを言い,これまで55人の投票者からなるパウロス当選モデルが知られていた.本研究では,11人からなるパウロス当選モデルを与え,これが妥当な仮定の下での最小例であることを示す.[発表資料(pdf)]
16. 手札公開で行う「ババ抜き」の必勝戦略の非存在性について:木谷 裕紀 (九州大), 小野 廣隆 (名古屋大)
概要:全国的に認知度、人気が高いトランプカードゲームの一つにババ抜きがある。ババ抜きはゲームの性質上不完全情報であるためいわゆる必勝戦略は存在しない。本研究では手札公開で行う完全情報の「ババ抜き」ゲームを定義し、その最適戦略について考察した。また、プレイヤー4人以上のときすべてのプレイヤーが最善をつくすと「千日手」が発生して引き分けとなる局面が存在することを示した。[発表資料(pdf)]
17. Simple-Kalahにおける勝敗確定の十分条件:前井 康秀, 木谷 裕紀, 土中 哲秀 (九州大), 小野 廣隆 (名古屋大)
概要:Kalahは,2人で行う完全情報ゲームであり,それぞれのプレイヤーが順番に石を動かす中でより多くの石を自身のstoreに入れることを目的とするゲームである.本論文ではKalahのルールを単純化したSimple-Kalahにおいて,Simple-Kalahにおいてある条件を満たす盤面が与えられたときの必勝戦略を与え,その条件の有効性について検証を行う.また,状態遷移グラフを描いたときにそのグラフのノード数が指数サイズとなる盤面があることについて証明し,完全ゲーム木を用いるアルゴリズムでは必勝戦略の導出が困難であることを示す.[発表資料(pdf)]

 

18. 地図迷路自動作成プログラム:中村 俊介, 橋本 剛 (松江工業高等専門学校)
概要:迷路自動作成における面白さへのアプローチとして,本研究では地図を題材とした方法を検討する.提案手法を元に作成した地図迷路自動作成プログラム「中村迷路」を紹介し,評価を行う.道が多く複雑な東京都の地図を含む多くの地図を実用的な時間内で迷路化できた.[発表資料(pdf)]

19. make10の一般化について:佐伯 元春, 西村 治道 (名古屋大)

概要:make10とは1から9の4つの数字から四則演算と括弧をつかって10にすることができるかどうかを問うパズルである.本講演では,make10を一般化した問題をいくつか考え,それらの計算複雑さについて得られたことを報告する.[発表資料(pptx)]
20. 「四角に切れ」の定数時間検査アルゴリズム:竹田 美弘, 伊藤 大雄 (電通大)
概要:「四角に切れ」とは、正方形の盤面Sとその盤面上の一部のマス目に正整数が配置されているものが入力として与えられ、目的は、Sを複数の長方形に分割して、各長方形にはその面積と等しい値の正整数が一つずつ含まれているようにするパズルである。一方、定数時間アルゴリズムはビッグデータとの関係で近年注目を浴びているが、最近では、将棋やチェスなどのボードゲームやライツアウトやポリオミノといったボードパズルが定数時間検査可能であることが示されている。本発表では、盤面を√n×√nにした「四角に切れ」が定数時間検査可能である、すなわち、与えられた入力が解を持つのかを検査する定数時間アルゴリズムが存在することを示す。[発表資料(pdf)]
21. Pyramidの計算複雑性:渡邉 光 (電通大)
概要:Pyramidはトランプを用いる一人パズルゲームである。プレイヤは盤面からカードを取り除いていき、全てのカードを取り除くことができれば勝利となる。Pyramidで用いるトランプのランク数を一般化したとき、プレイヤの勝利可能性を判定する問題はNP完全であることが知られている。本研究では、トランプのランク数に加えてスート数を一般化したときの計算複雑性を調査した。
22. ぷよを自由に配置できる場合のぷよぷよの連鎖数判定問題:澁谷 諒祐, 木村 慧 (豊橋技科大)
概要:ぷよぷよとは"ぷよ"と呼ばれる色のついたブロックを盤面に配置して行うパズルゲームである.落下する2つの組となったぷよ(ピース)を操作し,盤面へ配置する.同じ色のぷよが4つ以上連結するとそれらは消える.また,消えたぷよの上にぷよがある場合,それらは落下する.この時再びぷよが4つ以上連結して消えることがある.このようにぷよが繰り返し消える現象を連鎖といい,連鎖数が大きくなるほど得点も高くなる.そのため,連鎖数が大きくなるようにぷよを配置することが求められる.2006年,松金と武永は「初期盤面とピース列が与えられたときk連鎖以上を起こすことが可能であるか」という一般化ぷよぷよの連鎖数判定問題がNP完全であることを示した.
 本講演では入力として初期盤面のみが与えられ,空白マスにぷよを自由に配置して良い場合の連鎖数判定問題を考える.この場合の連鎖数は,ピース列に関係なくぷよを配置できるという意味で,一般化ぷよぷよにおける連鎖数の上界を与える.
 本講演では上記の連鎖数判定問題がNP完全であることを3SATからの帰着により示す.また,初期盤面が全て空白マスである場合には同問題が多項式時間で解けることを示す.
23. ペンシルパズル「Fill-a-Pix」のNP完全性:樋口 雄太, 木村 慧 (豊橋技科大)
概要:Fill-a-Pixは,Trevor Truran氏により考案,Conceptis社により2003年に開発されたペンシルパズルである.いくつかのマスに0〜9の数字が与えられた長方形の盤面として問題が与えられ,盤面上の数字はそれが書かれたマス自身とその周囲の合計9マスのうち何マスを黒で塗りつぶすかを示す.この数字のヒントに従い,盤面の全てのマスを白か黒で塗り分け,絵や文字を浮かび上がらせることがこのパズルの目的である.本講演では,回路SAT問題からの多項式時間還元により,Fill-a-Pixの解の存在判定がNP完全であることを示す.

24. 盤面を一般化した「フォービドゥン」パズルのASP完全性:田井 翔太, 上嶋 章宏 (大阪電通大)

概要:本研究では,ペンシルパズルの1つであるフォービドゥンの計算複雑さを解析する.フォービドゥンとは,パズル作家の稲葉直貴氏が考案し,数学セミナー2017年7月号で紹介されたパズルで,下記のルールに従い盤面上に丸を配置していくパズルである.四角格子状の盤面には,丸を配置できない黒マスの領域と,それ以外にあたる白マスの領域がある.初期盤面には,予め丸が配置されたいくつかの白マスがあり,「丸は縦横一直線上に4つ以上連続してはならない」というルールに従い,全ての丸が縦横でひとつながりになるよう,プレイヤーは白マスに丸を配置する.本研究では,フォービドゥンの別解問題(ASP)の計算複雑さを議論する.このパズルの計算複雑さは明らかになっていない.本発表では,フォービドゥンの盤面を一般化した,一般化フォービドゥンのASP完全性を,各頂点の次数が3以下の平面無向グラフにおけるハミルトン閉路問題からの多項式時間一対一還元を用いて証明できることを示す.

25. 一般化パイプパズルの計算量について:白山 卓夢 (JAIST), 大舘 陽太 (熊本大), 上原 隆平 (JAIST)

概要:パイプパズルとは、マッチングパズルの一種である。与えられたカードにはパイプが描かれていて、このパイプを接続しながら、与えられた盤面上のスタート地点とゴール地点をひとつながりにすることがパズルの目的である。通常のマッチングパズルでは、局所的な整合性を保ちながら盤面を埋めることが目的であるが、パイプパズルでは、すべてのパイプカードをひとつなぎにした経路を構築するところに大きな特徴がある。本研究では、まず一般化パイプパズルがNP完全問題であることをしめす。次に限定的な2つの場合に多項式時間で解けることを示す。[発表資料(pdf)]

26. 公平なサイコロの作り方:谷口 智子, 上原 隆平 (JAIST)

概要:世の中には多種多様なサイコロが売られていて、公平なものもあれば、公平でないものもある。特に、公平であるかのように見えるが公平でないサイコロもある。本講演では、公平なサイコロをデザインするためのスキームを2種類提案する。1つ目は一様な球体を「無限の目を持つ公平なサイコロ」と見なすモデルに基づくスキームである。2つ目はコインを「公平な2面サイコロ」と見なすモデルに基づくスキームである。実際にはコインには厚みがあるため、3つ目の面、側面がある。コインの厚みを増せば、表/裏の出る確率はいくらでも0に近づけることができる。この事実を使えば、3以上の任意の自然数nに対して、表や裏の出る確率を1/nにすることができる。この厚みの算出方法を議論する。[発表資料(pdf)]

27. 正確な訓練データを使ったニューラルネットワークによるゲーム局面の学習:神保 秀司 (岡山大学)

概要:二人零和有限確定完全情報ゲームで存在し得る任意の局面から両対局者が最善を尽したときの勝敗を完全に解析して例が幾つか知られているが,ペンタゴ (Pentago) と呼ばれる五目並べを発展させた形の市販のボードゲームもその中の一つであり,2014年にその達成が報告されている.さらに,その完全解析結果の一部がパブリックドメインで公開されている.著者らは,ペンタゴの局面についてそこから両対局者が最善を尽したときの勝敗,すなわち形勢判断を比較的単純な構造の画像認識用ニューラルネットワークを改造したものに学習させることを試みたが,正解率は約85パーセントで頭打ちになってしまう現象が見られた.現在、90パーセントを超える正解率を目標にしている.最近の画像認識用ニューラルネットワークは,多数の構造が提案され性能も飛躍的に向上しているので,そのような成果がペンタゴの局面の形勢判断にも応用できることが期待できる.さらに,著者らは,与えられた局面を前処理して得た情報を元の局面と共に与えることにより形勢判断の正解率を向上させることができるのではないかと期待している.この場合の前処理の一例として,特定の配置を含む盤面の形勢情報の割合を予め計算しておくなどである.今回の発表では,現在停滞気味の研究について現状を報告し,質疑応答により良いアイデアが得られることを期待している.[発表資料(pdf)]

28. Implementation of Solver and Generator of Matchstick Puzzle Problems:Brandon Heng, Yoshitaka Inoue, and Yushi Uno (Osaka Prefecture University)

概要:We developed a GUI application of matchstick puzzle. We equip two main functions with this application: one is a matchstick equation puzzle problem generator, and the other is problem solver.
 

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