有向マトロイドとは

2006年度
情報科学演習Ⅲ
今井研課題説明会
２００６年４月７日
今井研究室の研究テーマ
『アルゴリズム』の研究
今井研究室の研究テーマ
計算幾何
計算代数
グラフ理論
組合せ論
暗号理論
離散・連続最適化
計算量理論
メタヒューリスティックス
今井研究室の研究テーマ
未踏域への挑戦
現実社会への応用
今井研究室の研究テーマ
未踏域への挑戦
量子
現実社会での応用
交通流解析
ゲーム理論
ネットワーク
今井研究室の研究テーマ
交通流解析
ゲーム理論
量子
ネットワーク
計算幾何
計算代数
グラフ理論
組合せ論
暗号理論
離散・連続最適化
計算量理論
メタヒューリスティックス
演習の内容
研究について


文献を探す、調べる
分かりやすい発表
テーマを自力で見つける能力




ことを身につける
研究のための基礎訓練


自分で考える
ひとりよがりなテーマでは意味がない！
何を研究すればよいのか？
なぜその研究が必要か？
もちろん質問は歓迎


メールor研究室
今井研セミナーの見学も歓迎
日程

毎週水曜日13：00から２１４にて

都合が悪い場合はflexibleに対応します
１週目：テーマ設定
２週目：中間発表
３週目：中間発表
４週目：最終発表
前もってセミナー担当の鈴木([email protected])に
連絡があれば１週目から発表が出来ます
演習Ⅲテーマの対応関係ゲームツリー
サーチ
量子計算
交通流解析
ゲーム理論
量子
ネットワーク
計算幾何
有向マトロイド
計算代数
実現可能性判定
ゼロ知識証明
グラフ理論
組合せ論
暗号理論
離散・連続最適化
計算量理論
メタヒューリスティックス
演習Ⅲ研究テーマ
 離散数学

有向マトロイド実現可能性判定
 ゲームツリーサーチ
 計算量理論・暗号理論

ゼロ知識証明
 ゲーム理論
 量子計算

この他希望があれば
対応します
対話証明・隠れ部分群問題・量子ウォーク
質問はメールまたは研究室(311,314)まで
情報科学演習III 課題
-- 有向マトロイドの実現可能性
判定 -中山裕貴（博士３年）
森山園子（助手）
有向マトロイドとは？
有向マトロイド = oriented matroid
{+, －, 0}の符号
matrix（行列） + roid（のようなもの）
行列を用いて表される様々な対象を、符号に抽象化して考える
抽象化の例：
6 5
z
4
y
3
7
1
5
1 2
3 4
x
6
有向グラフ
2
線形計画問題
超平面配置
(4)
(-++-+)
サイクルの集合：
{12, 456, 7}
(1)
(5)
分割された各領域：
{ (++++++), … }
領域が各超平面に対してどちら側にあるか
(2)
( c ) (3)
(g)
有向マトロイド計画問題
（有向）マトロイドと行列表現のギャップ:
マトロイドが与えられたとき、行列として表すことができるか？
マトロイド
存在するとは限らない
必ず存在する
z v5 yv
4
v6
極大な独立集合
(124,456以外のすべて）
有向版に拡張する
（符号を考える）
v1
v3
v2
x
有向マトロイド
存在するとは限らない
必ず存在する
従属ならば０、
独立ならば行列式の符号
が与えられたとき、行列として表せるか判定する
＝有向マトロイドの実現可能性判定問題
有向マトロイドの実現可能性判定問題：
・正確に判定することは難しい
・実現可能（or 不可能）なものの一部を、
ある性質を用いて高速に判定する
（性質：非ユークリッド性、非HK*性、双二次最終多項式･･･）
今回の演習の内容：
・有向マトロイドが実現可能（or 不可能）であるための
条件について、文献・論文の講読
・余裕があれば、実装も
・他に自分のやりたいことがあれば、
それをやるのもよいでしょう
ゲームツリーサーチ
担当美添、八登
ゲームツリーサーチの意義

目標が明確


評価基準が明確



人間の世界チャンピオンに勝つ
強いアルゴリズムが良いアルゴリズム
広大な探索空間を扱う
ある程度のリアルタイム性が求められる

挑戦する価値のある問題である
研究の背景
ゲームプレイングアルゴリズムの進歩

サーチアルゴリズムの進歩によりプログラムが
強くなった

ゲームツリーサーチ自体の研究





最良優先 : A*、SSS*、…
αβのヴァリエーション : αβ、PVS、MTD(f)、…
証明数 : PN*、DFPN、…
Threat based : λサーチ、GTS、λDFPN、…
評価関数の研究


ゲームごとに特有の研究
統計的手法、強化学習などの一般的な方法
研究の背景 : ゲームプレイング
プログラム/コンピュータの強さ

チェッカー : CHINOOK (Jonathan Schaeffer)


リバーシ : Logistello (Michael Buro)


1997にKasparovに勝利
中国将棋


1996に世界チャンピオン村上に勝利
チェス : Deep Blue


1992, 1994にTinsleyと対戦
チェスと将棋の中間の強さらしい
専用ハード
+
並列化
将棋 :激指、 YSS 、IS将棋、…


アマ五段クラス角落ちでプロ(勝又五段)に勝利
アマ竜王戦ベスト16 (激指)
今回の目標

逐次のゲームツリーサーチアルゴリズムの性質を理解
する


性質を理解しなければ効率の良い並列化はできない
並列ゲームツリーサーチに関する文献を購読する


既存研究の並列化の対象は主にαβ
証明数サーチなどの並列化の既存研究は少ない



もちろん挑戦しても良い
逐次のゲームツリーサーチを書いてみる
さらに時間があれば並列化をしてみる
αβの基本

65
αカット、βカットによ
り探索が省略され
る
候補手が理想的な
順番にソートされて
いれば、探索ノード
数は元のツリーの
ノード数のほぼsqrt
になる[Moore and
Knuth 1975]
83

65
62
65
90
62
Max node
Min node
65
35
90
49
62
30
83
80
並列化の難しさ

αβの動作のつもり



基本的には深さで打ち切る
反復深化をする場合
枝刈りと探索延長


どの分岐が正解にたどり着く
か不明

ある程度予測可能
他の分岐の情報が枝刈りに必
要

何らかの通信が必要
探索空間
この場合の最善手
参考研究



Synchronousな並列化
 YBWCなど
Asynchronousな並列化
 APHID
Transposition Table Driven Scheduling
 TDSAB
チャレンジャーな人はDFPNやλサーチの
並列化に取り組んでも良い
参考研究が少ないので1ヶ月では難しいと思われる
計算量理論・暗号理論
（ゼロ知識証明）
永岡悟（M1）
高橋敏明（M1）
上野賢哉（M2）
理学（Science)
工学（Engineering）
実社会への応用
計算量理論
人の役に立つ
一般性
（幅広い事象を包括できる）
普遍性
（１００年たっても価値が変わらない）
暗号理論
対象を絞り込んだその場限りの理論で人の役に立たないもの
工学（Engineering）
アルゴリズムの設計と限界
認証システム
理学（Science)
近似不可能性
PCP定理
（確率的対話証明）
対話証明系
ゼロ知識証明
ゼロ知識証明
ある情報を持っていることを示したいが、
情報そのものは隠しておきたい



証明者と検証者が対話を行う
盗聴、検証者のなりすましによる情報漏洩を防ぐ
認証などへの応用が期待される
Password : ＊＊＊＊＊＊＊
３彩色問題を使用したゼロ知識証明の例
1
6
2
5
3
証明者
6
検証者
4
1.色の対応をランダムに置換
1
1
2
2
6
3
5
3
5
4
2.色情報を箱に入れ
鍵をかけて送る
4
(1,4)
3.枝をランダムに１つ
選んで送る
4.対応する鍵を送る
5.対応する箱を開け
異なることを比較
ゲーム理論
牟田秀俊、加藤公一、西鳥羽二郎
ゲーム理論とは…



複数の行為主体がいる
各主体が自分の利得が最大となるよう行動する
行動が状況や相手に影響を及ぼす

以上の特徴を持つモデルを分析する学問

実用的なおもしろさ


ネットワーク解析
計算量的なおもしろさ

Nash均衡点を求める難しさは？
Nash均衡と計算量
利得行列(囚人のジレンマ):
B:黙秘
B:自白
とある囚人の話
 両方黙秘

A:黙秘
3,3
10 , 1

片方のみが自白

A:自白
1 , 10
8,8


両方とも3年
自白した方1年
黙秘した方10年
両方自白

両方とも8年
Nash均衡と計算量
利得行列(囚人のジレンマ):

B:黙秘
A:黙秘
A:自白
3,3
1 , 10
B:自白
10 , 1
8,8
Bさんが黙秘なら


Bさんが自白なら


Aさんは自白
Aさんは自白
結局Aさんは自白
Nash均衡と計算量
利得行列(囚人のジレンマ):
B:黙秘


B:自白

A:黙秘
3,3
10 , 1
A:自白
1 , 10
8,8
Nash均衡点
同様に考えると
Bさんも自白
Aさんは自白だった

結局自白×自白に
落ち着く
Nash均衡と計算量
利得行列(囚人のジレンマ):
B:黙秘
B:自白
A:黙秘
3,3
10 , 1
A:自白
1 , 10
8,8
二行二列は簡単
じゃあ巨大なら？
Nash均衡点を求める多
項式時間アルゴリズ
ムはあるのか？
OPEN
Nash均衡点
演習Ⅲの課題
ネットワーク解析
計算量
ユーザーが利己的な
時のスループットの
解析
Open Problem:
Nash均衡を求める
問題の計算量
(PとNPの間?)
Nash均衡
最適化
凸多面体
Nash均衡を求める問
題は線形相補性問題
で表せる
他の
均衡点
市場解析等
量子計算
長谷川、加藤(D2)
乾(M2)、鈴木(M1)
背景
量子効果による高速化への限界
量子効果を積極的に利用した計算原理
古典の場合と
準指数的なギャップ
Shorのアルゴリズム
素因数分解
RSA暗号が破られる
Groverのアルゴリズム
非ソートデータの検索
原理

重ね合わせ

並列計算
隠れ部分群問題
G
入力：群GとGを定義域とする関数f
H
g1H
…
g kH
fにはGの部分群Hに関する制約があり、
fの入力と出力からHを求めたい
f
Shorのアルゴリズムの基本部分は
Gが巡回群の隠れ部分群問題
S
量子ウォーク
一言で言えばランダムウォークの量子版
しかしその性能は全く違う
Glued Tree
Start
goal
・・・
ランダムウォークの機能を持ったロボットが左から右に移動するのに・・・
古典だと
d
2
量子だと
d
2
量子積分
古典で難しい関数の積分計算を
赤い格子の個数を速く（！）数える
ことで計算可能
対話証明
このような計算モデルで量子の場合の
計算能力を見る
課題

演習3の課題として



基礎となる部分について学ぶ
関連論文を読む
実際の問題に取り組む
などを予定している

Download Report