ミニ研究集会「組合せゲーム・パズル」
武永 康彦
電気通信大学情報工学科
科学研究費補助金の特定領域研究「新世代の計算限界」の活動の一環として、
組合せゲーム・パズルに関するミニ研究集会が昨年の9月12日に京都大学で行なわれ
ました。
世話役をして頂いたのは京都大学の伊藤大雄先生です。
中村義作先生の特別講演に加え、一般の講演が9件行なわれ、かなりの人数が
集まり盛況の研究集会となりました。
私がこの研究集会に参加した大きな理由のひとつは、
中村先生の特別講演が行なわれるというということでした。
LAには同じような人がかなり多いのではないかと思うのですが、昔からパズル、
ゲームの類が好きで高校、大学の頃（だったと思う）を中心にブルーバックス
あたりから始まって、この手の本をかなり読んでいて、その中に
中村先生の本も何冊か含まれていました。他に主な名前をあげると、
藤村幸三郎、高木茂男、H.E.デュードニー、M.ガードナー、などなど。
（でも少し調べてみたら、当時読んだ本の多くが現在入手困難のようで残念です。）
もっと若い人だと、芦ケ原伸之、秋山仁、P.フランクル、あたりでしょうか？
(ちょっと毛色が違いますが、最近では「ニコリ」から入った
人が一番多いのかも。私も創刊間もない頃買っていました。ニコリなどしか
知らない人は上に名前を挙げた人の本もぜひ読んでみて下さい。)
最近も、中村先生の「ゲームにひそむ数理」（秋山仁と共著、森北出版）
という本の内容の一部を新1年生向けの少人数セミナーで使わせて頂きました。
この本はお勧めです。この日の講演もこの本の内容が元になっていました。
講演開始前にはマジックも披露されたらしいのですが、当日朝東京を出た私は少し
遅れてしまい見逃してしまいました。マジック好きもパズル好きと通じる部分が
あると思います。
(私は実演能力はほぼ
皆無です。それなのに、昨年は初めて大勢の前で1ネタ演じることに、、、)
各講演の概要は以下のとおりです。
- ゲームにひそむ数理：中村義作（東海大学）
-
１人ゲームから、ペグ・ソリテア、ナイトの周遊、２人ゲームから、
１つ山くずし、２つ山くずしについて、その背後に潜む数理を紹介した。
- シャノンのスイッチングゲームにおけるペアリング戦略について：
高橋良介、瀧本英二（東北大学）
-
「HEX」というゲームは，n x n の盤面では最適戦略を求めることが
PSPACE困難であるが，n x m の盤面（n≠m）ではペアリング戦略と
呼ばれる単純な必勝法が存在する。
このゲームを一般化したシャノンのスイッチングゲーム
において、ペアリング戦略が存在するための条件について考察した。
- Voronoi game on graphs and its complexity：寺本幸生、上原隆平（JAIST）
-
ボロノイゲームとは、競争的施設配置問題をモデル化した2人ゲームである。
このゲームを離散化してフィールドがグラフで与えられる場合を考え、
グラフが木の場合の最適戦略、一般のグラフの場合の計算困難性を
明らかにした。
- 碁石ゲームに関する考察 --- ４目並べ講座：徳山豪（東北大学）
-
伊藤による五目ならべに似た碁石ゲームに関する講演から生じた、
碁石によるパターン生成問題について、主に縦4個、横5個の列を生成する問題に
ついて考察した。
- 囲碁プログラミングの探索における小目標間の依存関係解決に向け
て：美添一樹（東京大学）
-
囲碁においては盤面全体に対する、速く正確な評価関数を
作ることが困難なため、囲碁プログラムでは小目標ごとのサーチが
広く用いられている。ここでは、小目標の依存関係を解決するため、
`利き'の範囲を求める新たな手法を提案した。
- 逆算法に基づく詰め将棋の列挙：堀山貴史、中塚裕之、岩間一雄（京都大学）
-
逆算法により詰め手数の少ないものから順に詰将棋を列挙す
ることで、詰将棋解答プログラムを用いることなく、与えられた条件下で可能な
詰将棋を高速に列挙する手法を提案、実装した。列挙した中から得られた
作品？も示された。
- Toward a Polynomial Time Algorithm for 2-Link Puzzle：牧野格三（東京工業大
学）
-
「ナンバーリンク」と呼ばれるパズルをｋ-リンクパズルというグラフ問題として
考え、ｋを2に固定した「2-リンクパズル」に対し、解を持つための
必要十分条件について考察した。
- 一般化アマゾンはPSPACE-complete：清見礼（国立情報学研究所）
-
「アマゾン」というゲームを一般化したゲームの勝敗判定は、終盤戦においてすら
NP完全であることが示されているが、ここでは、一般の局面の勝敗判定が
PSPACE完全であることを示した。
- Rogueの脱出判定問題：武永康彦、高野悟、山瀬達郎（電気通信大学）
-
コンピュータ上のアドベンチャーゲーム「Rogue」において、残り体力のない
キャラクターが魔物のいる部屋から脱出できるかというパズルの一般化が
NP困難であることを示した。
- 整数計画法を用いたスリザーリンクの解法：杉村由花（東京大学）
-
「スリザーリンク」の類似パズル「スリザーリンクス」を考案し、
そのNP完全性を証明した。また、スリザーリンクを整数計画問題として
定式化し、その実装実験を行なった。
講演の内容に興味を持たれた方は、
このページをご覧頂ければ、多くの講演については発表資料も掲載されています。
このテーマの第2回の研究集会も開催されると思いますので、また皆さんの
面白い研究成果を聞かせてもらえるのを楽しみにしています。
