Download presentation
Presentation is loading. Please wait.
1
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
重み付き半順序集合ゲームの必勝法 京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作 Kyoto University, Japan
2
Kyoto University, Japan
発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 4.1.COST 4.2.毒の経路ゲーム 4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan
3
Kyoto University, Japan
発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 4.1.COST 4.2.毒の経路ゲーム 4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan
4
Kyoto University, Japan
Nim 複数の石からなる山がいくつか与えられる。 ２人のプレイヤーが交互に石を取っていく。 －いくつ取っても良いが、１つの山からしか取れない。 最後の石を取ったプレイヤーの勝ち 排他的論理和による必勝手順[Bouton 1901] Kyoto University, Japan
5
Kyoto University, Japan
組み合わせゲーム理論 Sprague-Grundy定理[Sprague ; Grundy 1939] －全ての組み合わせゲームはNimの山で表せる。 適用分野 －誤り訂正符号 －人工知能（例：碁の終盤局面） －ゲーム理論 －計算量理論 －アルゴリズム（例：必勝法） Kyoto University, Japan
6
Kyoto University, Japan
発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 4.1.COST 4.2.毒の経路ゲーム 4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan
7
Kyoto University, Japan
半順序集合ゲーム ゲームの盤面としてdag（非閉路的有向グラフ）が与えられる。 交互に節点を１つずつ選んでいく。 選ばれた節点の子孫が消える。 最後の節点を取ったプレイヤーの勝ち。 Kyoto University, Japan
8
Kyoto University, Japan
半順序集合ゲーム ニムはdag（非閉路的有向グラフ）で表現できる。 Kyoto University, Japan
9
Kyoto University, Japan
半順序集合ゲーム 半順序集合ゲームは毒節点で表現できる。 －例：Chomp Kyoto University, Japan
10
Kyoto University, Japan
我々の拡張（１） 毒節点がdagの任意の場所に複数あるものを考える。 両者が整数値の体力を持つ。 毒を取った数だけ体力が減る。 体力が負になったプレイヤーの負け。 （毒節点の数）＞（２者の体力の和） →引き分けは起こらない Alice Life : 0 Bob Life : 2 Kyoto University, Japan
11
Kyoto University, Japan
我々の拡張（２） 毒節点が正整数値の重みを持ち、その数だけ体力が減るとする。 非毒節点は重み０の節点として考えることができるため、全ての節点が整数値の重みを持つとする。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 1 Kyoto University, Japan
12
Kyoto University, Japan
我々の拡張（２） 毒節点が正整数値の重みを持ち、その数だけ体力が減るとする。 非毒節点は重み０の節点として考えることができるため、全ての節点が整数値の重みを持つとする。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 1 Kyoto University, Japan
13
Kyoto University, Japan
我々の拡張（２） 毒節点が正整数値の重みを持ち、その数だけ体力が減るとする。 非毒節点は重み０の節点として考えることができるため、全ての節点が整数値の重みを持つとする。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 -1 Kyoto University, Japan
14
Kyoto University, Japan
名前の定義 各節点に整数値の重みがあるものを重み付き半順序集合ゲームと呼ぶ。 重みが｛0,1｝であるものを単位毒半順序集合ゲームと呼ぶ。 4 2 -1 Kyoto University, Japan
15
Kyoto University, Japan
今回の結果（１） 単位毒半順序集合ゲームにおいて、どちらのプレイヤーが必勝手順を持つか判別できる方法を得た。 Alice Life : 0 Bob Life : 2 Kyoto University, Japan
16
Kyoto University, Japan
今回の結果（２） dagがpathである重み付き半順序集合ゲーム（重み付き経路ゲーム と呼ぶ）において、多項式時間必勝手順を得た。 3 5 -2 2 Alice Life : 3 Bob Life : 3 Kyoto University, Japan
17
Kyoto University, Japan
発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 4.1.COST 4.2.毒の経路ゲーム 4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan
18
Kyoto University, Japan
単位毒半順序集合ゲーム 各節点に{0,1}の重みがついている。 両者が整数値の体力を持つ。 取った重み和だけ体力が減る。 体力が負になったプレイヤーの負け。 （毒節点の数）＞（２者の体力の和） →引き分けは起こらない Alice Life : 0 Bob Life : 2 Kyoto University, Japan
19
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー （２）両者の体力が同じならば、 （ａ）子孫を持たない節点が全て毒ならば、後手 （ｂ）そうでないならば、全ての毒節点とその祖先を縮約し、１つの毒節点にした普通 の半順序集合ゲームにおいて必勝手順を持つプレイヤーと同じ Kyoto University, Japan
20
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
21
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
22
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
23
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
24
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
25
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
26
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ 単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、 （１）両者の体力が異なるならば、体力の多いプレイヤー Kyoto University, Japan
27
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ （２）両者の体力が同じならば、 （ａ）子孫を持たない節点が全て毒ならば、後手 （ｂ）そうでないならば、全ての毒節点とその祖先を縮約し、１つの毒節点にした普通 の半順序集合ゲームにおいて必勝手順を持つプレイヤーと同じ Kyoto University, Japan
28
Kyoto University, Japan
単位毒半順序集合ゲーム 我々は以下の結果を得た。 定理１ （ｂ）そうでないならば、全ての毒節点とその祖先を縮約し、１つの毒節点にした普通 の半順序集合ゲームにおいて必勝手順を持つプレイヤーと同じ Kyoto University, Japan
29
Kyoto University, Japan
発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 4.1.COST 4.2.毒の経路ゲーム 4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan
30
Kyoto University, Japan
重み付き半順序集合ゲーム 各節点が整数値の重みを持つ。 両者が整数値の体力を持つ。 取った重み和だけ体力が減る。 体力が負になったプレイヤーの負け。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 -1 Kyoto University, Japan
31
Kyoto University, Japan
重み付き半順序集合ゲーム dagを１本の路に限ったものについて多項式時間必勝手順を与えた。 3 5 -2 -1 1 3 -1 Alice Life : 0 Bob Life : 2 Kyoto University, Japan
32
Kyoto University, Japan
重み付き経路ゲーム 重み付き経路ゲームを、正と負の節点が混在していることより「薬と毒の経路ゲーム」と呼ぶ。 一方全ての節点の重みが正であるものを「毒の経路ゲーム」と呼ぶ。 3 5 -2 -1 1 3 -1 Alice Life : 0 Bob Life : 2 Kyoto University, Japan
33
Kyoto University, Japan
重み付き経路ゲーム 重み付き経路ゲームを、正と負の節点が混在していることより「薬と毒の経路ゲーム」と呼ぶ。 一方全ての節点の重みが正であるものを「毒の経路ゲーム」と呼ぶ。 3 5 -2 -1 1 3 Alice Life : 1 Bob Life : 2 Kyoto University, Japan
34
Kyoto University, Japan
重み付き経路ゲーム 重み付き経路ゲームを、正と負の節点が混在していることより「薬と毒の経路ゲーム」と呼ぶ。 一方全ての節点の重みが正であるものを「毒の経路ゲーム」と呼ぶ。 3 5 1 Alice Life : 1 Bob Life : 2 Kyoto University, Japan
35
Kyoto University, Japan
毒の経路ゲームの多項式時間必勝手順 まずCOSTというゲームの多項式時間必勝手順を得る。 それを利用して毒の経路ゲームの多項式時間必勝手順を得る。 Kyoto University, Japan
36
Kyoto University, Japan
ＣＯＳＴ 路グラフが与えられ、各節点に正整数の重みがついている。 ２人のプレイヤーが交互に葉より好きな数の節点を取っていく。 両者は自分の取る重み和を最小にすることを目的とする。 6 1 4 3 1 2 Kyoto University, Japan
37
Kyoto University, Japan
ＣＯＳＴ 補題２ 路グラフが で与えられており、それぞれの節点の重みが であるとき、先手の最善重み和 と後手の最善重み和 は以下の式で与えられる。 Kyoto University, Japan
38
Kyoto University, Japan
補題２の証明 （証明） Kyoto University, Japan
39
Kyoto University, Japan
補題２の証明 （証明終了） Kyoto University, Japan
40
Kyoto University, Japan
ＣＯＳＴの最善手順 ３個取るのが最善手順である場合・・ minの選択で過去 i 回に渡りLWが選ばれ、i+1回目でRWが選ばれた場合、i+1個取るのが必勝手順である。 Kyoto University, Japan
41
Kyoto University, Japan
ＣＯＳＴ 定理３ COSTの最善重み和と最善手順は 時間で求まる。 6 1 4 3 1 2 Kyoto University, Japan
42
Kyoto University, Japan
ＣＯＳＴの計算例 6 1 4 3 1 2 Kyoto University, Japan
43
Kyoto University, Japan
毒の経路ゲーム 全ての節点の重みが正整数であるもの。 アルゴリズム１ 毒の経路ゲームの解法 １．次の条件を満たす正整数 m を見つける。 （条件：葉から m 番目の節点までの重み和は体力の和より少ないが、葉から m+1番目の節点までの重み和は体力の和より多い） ２．葉から m 番目の節点までをCOSTで解いて両者の最善重み和AW,BW を求める。 ３． となった場合、プレイヤーBはCOSTの解法より勝てる。 Kyoto University, Japan
44
Kyoto University, Japan
毒の経路ゲーム 全ての節点の重みが正整数であるもの。 アルゴリズム１ 毒の経路ゲームの解法 ４． となった場合、葉から m+1 番目の節点までをCOSTで解いて両者の最善重み和AW,BW を求める。 ５． となった場合、プレイヤーBはCOSTの解法より勝てる。 ６． となった場合、 m+1 番目の節点の重みを減らすことで となるようにする。その時プレイヤーBはCOSTの解法より勝てる。その減らす値は二分探索により求める。 Kyoto University, Japan
45
Kyoto University, Japan
補題４ 補題４ となった場合、プレイヤーBはCOSTの解法より勝てる。 （証明） プレイヤーBはCOSTの解法に従う限り最大でもBWの重み和しか取らなくてよい。即ちプレイヤーAは最小でもAWの重み和を取らなくてはならず、必ず体力を失って負けてしまう。（証明終了） Kyoto University, Japan
46
Kyoto University, Japan
定理５ 定理５ アルゴリズム「毒の経路ゲームの解法」は毒の経路ゲームの必勝手順をああああ 時間で計算する。ただし （証明） まず条件（葉から m 番目の節点までの重み和は体力の和より少ないが、葉から m+1番目の節点までの重み和は体力の和より多い）を満たす正整数 m は必ず見つかる。 葉から m 番目の節点までのゲームを考え、COSTで解く。 重み和は体力の和より少ないので、ここまでのゲームで両方とも体力を失うことは有り得ない。ああああああああああああ よって以下の２つのケースしか有り得ない。 Kyoto University, Japan
47
Kyoto University, Japan
定理５ の場合、補題４よりプレイヤーBは勝てる。 の場合、m+1番目の節点までのゲームを考え、COSTで解く。 重み和は体力の和より多いので、ここまでのゲームで両方とも体力を残すことは有り得ない。 よって以下の２つのケースしか有り得ない。 Kyoto University, Japan
48
Kyoto University, Japan
定理５ の場合、補題４よりプレイヤーBは勝てる。 の場合、m+1番目の節点の重みを減らしあああ あとなるようにする。減らす値は二分探索により求める。 なお、m+1番目の節点の重みを x 減らせばあああああああああああであり、x+1減らせば となるような状況は起こり得ないため、上記の減らす値は必ず存在する。 補題４よりプレイヤーBは勝てる。 計算時間は二分探索に 時間かかりCOSTの計算にあああ時間かかるため （証明終了） Kyoto University, Japan
49
Kyoto University, Japan
薬と毒の経路ゲーム 薬と毒の経路ゲームは 時間で毒の経路ゲームに変換され、毒の経路ゲームが解ければ薬と毒の経路ゲームも解ける。 定理６ 「薬と毒の経路ゲーム」の必勝手順は 時間で求まる。 Kyoto University, Japan
50
Kyoto University, Japan
まとめ 単位毒半順序集合ゲームの必勝プレイヤーを知る方法を得た。 重み付き経路ゲームの多項式時間必勝手順が求められた。 dagを一本の路に限定しない重み付き半順序集合ゲームの必勝法。 重み付き毒節点、体力といった概念により、二者の対立関係が多様に表現できる。 →これにより、ゲーム理論に新しい知見をもたらすことはできないか。 今後の課題 Kyoto University, Japan
Similar presentations
