1. SATソルバを利用したお絵かきロジックの問題作成支援ツール：長坂哲，伊藤寛之，酒井正彦，草刈圭一朗，西田直樹，坂部俊樹 (名古屋大学大学院情報科学研究科)
- お絵かきロジックは，マスが白黒で塗られた絵に対して，各行と列において黒の
連続する数の並びの情報から，元の絵を復元するパズルである．
問題を解いて得られる絵が一意に定まる必要があるため，問題作成は容易ではない．
本発表では，お絵かきロジックの問題作成支援ツールについて述べる．
本ツールでは，解の一意性の判定に和積標準形(CNF)の論理式の充足可能性判定
ツール(SATソルバ)を利用した．
本発表では，CNFのコーディング方法について紹介し，
一意性判定の際に得られる情報を問題作成に役立てる手法について述べる．
また，問題作成支援ツールのデモを行なう．[発表資料(pdf)]
2. ヒント数が少ない対称形のナンプレの生成：早川友康 (岩手大学大学院)
- ナンプレと呼ばれているパズルにおいて、
ヒント数が17で線対称形の問題を、
既に発見されているものを含め
6問生成することができた。
3. ポリオミノのはみ出し可能な被覆問題：岡圭吾 (東京大学)，稲葉直貴(タイムインターメディア知識工学センター)，飯野玲（日本評論社）
- ポリオミノTを何枚か使ってポリオミノSを覆える（Sからはみ出しても良い）とき、
SはTによって被覆可能ということにする。ただし、Tどうしを重ねてはいけない。
回転、裏返しは許す。
このとき、穴の開いていないどんなポリオミノTによっても被覆可能なポリオミノ
Sをすべて求めたい。例えばSとして Pペントミノを考えると、どんなポリオミノT
によってもSは被覆可能であることが証明できる。また、Sとして Iペントミノを
考えると、添付画像のような被覆不可能なポリオミノTの例が存在する。
この問題に関する研究の進展について発表する。[発表資料(pptx)]
4. iPhone/iPod Touch向けアプリケーション リーチの作成：藤本拓也, 大西建輔 (東海大学)
-
我々は, 研究テーマの一つとして, iPhone/iPod Touch向けアプリ
ケーションの作成を行っている.
今回, 我々は三目並べの変形であるリーチと呼ばれるゲームを実装
した. リーチは, 3x3 の市松模様の盤面に3個づつの白と黒のコマを
使い, プレイする対戦型ゲームである.
今回作成したアプリケーションは, 人間同士での対戦だけでなく,
コンピュータとの対戦も可能である. コンピュータには, easy,
middle, hardと3つの戦略を作成した. 今回の発表では, 主にコンピ
ュータの戦略について述べる.[発表資料(pdf)]
5. モンテカルロ法を用いた立体四目並べ対戦プログラム：林佳佑（中央大学理工学部情報工学科）
-
モンテカルロ法を用いた立体四目並べのプログラムを数種類作成し、
プログラム同士を対戦させた場合の勝率と処理時間を示す。
m目並べに対する Erd?s-Selfridge の定理を利用し、
ランダムプレーアウト部分の変更を行った結果、より少ないプレー
アウト回数で他プログラムより良い、もしくは同等の勝率を記録した。[発表資料(ppt)]
6. コンピュータ囲碁におけるRoot並列化：副島佑介 (東工大)
- コンピュータ囲碁では，モンテカルロ木探索を利用する方法が最も有効であり，モンテ
カルロ木探索の並列化は，囲碁プログラムの強さを改善する手法の一つである．現在主流
となる並列化手法にはRoot 並列化とTree 並列化が存在する．本研究では強豪囲碁プログ
ラムFuego を用いて，Root 並列化とTree 並列化の両手法の再評価を行った．結果Tree
並列化の方が先行研究に比べて，より性能が高い並列化手法であることが示された．
次に，従来のRoot 並列化手法であった総和制と，今回提案するコンピュータ囲碁にお
けるRoot 並列化手法の合議制との2 つのRoot 並列化をFuego に実装し，その性能を調
査した．その結果，合議制Root 並列化の方が総和制に比べより性能が高い事が示された．
最後に，大規模なCPUコア数を用いた場合のRoot 並列化の効果の予測を行った．64CPU
コアを用いた実験で，Chaslot らの先行研究とは異なり，Root 並列化の有効性だけでなく
限界も示すことができた．一致率を用いた実験では，Root 並列化の限界点および，効果
の特徴などを発見する事ができた． [発表資料(pptx)]
7. Kaboozle is NP-complete even in a strip form：上原隆平 (北陸先端大)
-
Kaboozle is a puzzle that consists of four square cards.
Some color paths are drawn and some holes are made on the cards.
The objective of the puzzle is to join a color path by piling the cards (and filling the holes).
This seems to be a typical NP-complete problem since we can flip and rotate the cards.
Hence we restrict ourselves strictly; glue all the cards into a strip-form, and
specify the folding directions (mountain/valley) on each glued-edge.
That is, now the problem becomes finding just a folding order of
the strip paper since cards cannot be flipped and rotated any more.
Even in such a restricted case, the problem is still NP-complete.Keywords: Kaboozle, origami, silhouette puzzle [発表資料(pdf)]
8. パス上のボロノイゲーム：清見礼, 斎藤寿樹, 上原隆平 (北陸先端大)
-
ボロノイゲームをグラフ上に一般化したゲームについて考える.
このゲームは一般のグラフ上での勝敗判定がPSPACE完全である
ことが知られている. 一方で, グラフクラスを制限した場合,
パス上ですら先手後手のどちらが勝ちになるかが知られていない.
我々は, パス上のボロノイゲームが(1つの例外的な場合を除いて)
引き分けであることを示す.[発表資料(pdf)]
- 交替性計算は、古典的非確率的計算モデルの中で
最も複雑なものであるにもかかわらず、非決定性計算と比較して、
活発に議論されてきたとは言い難い。
本発表では、交替性計算の研究の発端となった Chandra らの
「交替性計算量による決定性計算量の特徴付け定理」や
(IP^A != PSPACE^A のような) Orponen の「特徴付け定理を破る神託分離定理」、
そして組合せ二人ゲームなどとの関係など、
交替性計算の「過去」から「現在」までの既存研究をサーベイする。
次に、交替性計算の「未来」を展望する。
例えば、初期の Chandra らの研究から30年以上経過しているにもかかわらず、
非決定性計算と交替性計算については、自明な包含関係しか知られていない。
非自明な関係が解れば、計算量理論の大きなブレイクスルーとなる。
もっとも、この問題の解明への道程は険しいと思われるため、
相対世界などより緩和された条件下での包含関係や、NP完全問題でないが
Pにも属さないような問題への並列計算モデルとしての適用など、
「交替性計算の潜在的能力」を模索する。 [発表資料(ppt)]
-
前回，任意の連結ピクセル白黒画像を解に持つ迷路を，
2×2の縮尺変更を行うことで容易に生成する方法が提案された．
一方で，迷路の入口と出口が隣り合わせになり，
左手法でミスなく解けてしまうという課題があった．
本発表では，任意の位置に入口出口を置くために，
3x3の縮尺変更を行う拡張版を提案する．
さらに，「質の良い」迷路を生成するための
いくつかの工夫を紹介する．[発表資料(ppt)]
-
正解路を塗りつぶすと絵が浮かび上がる迷路の作成方法として，
与えられた白黒画像を2x2に拡大する方法が提案された．
しかし，入口と出口が隣接した迷路しか作れないという課題があった．
本発表では，ある条件を満たす白黒画像に対して，
指定された入口と出口を持つ2x2に拡大した迷路を作成する方法を提案する．[発表資料(pdf)]
12. カーネル法を用いたコンピュータ将棋における静的評価関数の学習：末廣大貴（九州大学）
- 近年、コンピュータ将棋における評価関数の作成には、Boanza Methodなどによる
機械学習が広く用いられている。しかし、従来の手法において、局面評価に用いる
特徴ベクトルは、駒の損得などの単純なものから駒の位置関係などの複雑なものま
で、様々なものが用いられている。これらの特徴は全て作成者が考え、用意しなけ
ればならず、有効な特徴を見い出すには専門的な知識が要求される。
そこで、本発表では、単純な特徴ベクトルの二項関係、三項関係などの特徴を自動
的に学習に取り込むために、SVM（サポートベクターマシン）とカーネル法を用い
た手法を提案する。 [発表資料(pptx)]
13. テトリスに対するオンラインアルゴリズム：猿渡慎也, 藤原洋志, 藤戸敏弘 (豊橋技科大)
-
本研究ではパズルゲーム「テトリス」をオンライン問題として定式化し、
より多くの行を消そうとするアルゴリズムを考えた。本研究におけるテ
トリスは、テトロミノの列を先の分からない入力とし、それをアルゴリ
ズムによって盤面に配置して消すことのできた行の総数を利得とし、こ
の利得を最大化することを目標とする問題と定式化した。またゲーム
オーバーによる影響を無視するため、使用する盤面の高さは無制限とし
た。このようなテトリスについて任意のテトロミノ列に対してなるべく
大きな利得を得るアルゴリズムを開発するため、競合比を評価尺度とし
て用い評価を行った。その結果として、アルゴリズムによる盤面及び利
得の変化を状態遷移図で捉えるという手法により、盤面の幅を4、テト
ロミノをある2種類に制限したとき競合比2.5以下となるアルゴリズムを
示すことに成功した。 [発表資料(ppt)]
14. Poset Game の周期に関する考察：後藤順一，伊藤大雄（京都大学 大学院 情報学研究科）
- チョンプは長方形の盤面を初期盤面として、２人のプレイヤーが
交互にブロックを選び、それとその右下にあるブロック全てを除去して
いき、最後に左上のブロックを選ばざるを得なくなったプレイヤーが負
けとなる、ニム型のゲームである。チョンプは半順序集合ゲームのクラ
スに含まれる。ある種の半順序集合ゲームについては負け型が周期性を
持つことがByrnesの周期性定理によって知られているが、その周期長は
有限ということが分かっているだけで具体的な数式として得られてはい
ない。本発表では、３行チョンプに対して周期の解析を行い、その周期
が2^O(c^2)で抑えられることを示す。 [発表資料(pptx)]