重み付き半順序集合ゲームの
必勝法
京都大学 情報学研究科 通信情報システム専攻
高田智史
joint work with
伊藤大雄 中村義作
Kyoto University, Japan
発表構成
１．組み合わせゲーム理論
２．半順序集合ゲーム
３．単位毒半順序集合ゲーム
４．重み付き半順序集合ゲーム
4.1.COST
4.2.毒の経路ゲーム
4.3.薬と毒の経路ゲーム
５．まとめ
Kyoto University, Japan
発表構成
１．組み合わせゲーム理論
２．半順序集合ゲーム
３．単位毒半順序集合ゲーム
４．重み付き半順序集合ゲーム
4.1.COST
4.2.毒の経路ゲーム
4.3.薬と毒の経路ゲーム
５．まとめ
Kyoto University, Japan
Nim
• 複数の石からなる山がいくつか与えられる。
• ２人のプレイヤーが交互に石を取っていく。
－いくつ取っても良いが、１つの山からしか取れない。
• 最後の石を取ったプレイヤーの勝ち
• 排他的論理和による必勝手順[Bouton 1901]
Kyoto University, Japan
組み合わせゲーム理論
• Sprague-Grundy定理[Sprague 1935-1936; Grundy 1939]
－全ての組み合わせゲームはNimの山で表せる。
• 適用分野
－誤り訂正符号
－人工知能（例：碁の終盤局面）
－ゲーム理論
－計算量理論
－アルゴリズム（例：必勝法）
Kyoto University, Japan
発表構成
１．組み合わせゲーム理論
２．半順序集合ゲーム
３．単位毒半順序集合ゲーム
４．重み付き半順序集合ゲーム
4.1.COST
4.2.毒の経路ゲーム
4.3.薬と毒の経路ゲーム
５．まとめ
Kyoto University, Japan
半順序集合ゲーム
• ゲームの盤面としてdag（非閉路的有向グラフ）が与えら
れる。
• 交互に節点を１つずつ選んでいく。
• 選ばれた節点の子孫が消える。
• 最後の節点を取ったプレイヤーの勝ち。
Kyoto University, Japan
半順序集合ゲーム
• ニムはdag（非閉路的有向グラフ）で表現できる。
Kyoto University, Japan
半順序集合ゲーム
• 半順序集合ゲームは毒節点で表現できる。
－例：Chomp
Kyoto University, Japan
我々の拡張（１）
•
•
•
•
•
毒節点がdagの任意の場所に複数あるものを考える。
両者が整数値の体力を持つ。
毒を取った数だけ体力が減る。
体力が負になったプレイヤーの負け。
（毒節点の数）＞（２者の体力の和）
→引き分けは起こらない
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
我々の拡張（２）
• 毒節点が正整数値の重みを持ち、その数だけ体力が減
るとする。
• 非毒節点は重み０の節点として考えることができるため、
全ての節点が整数値の重みを持つとする。
• （重みの和）＞（２者の体力の和）
→引き分けは起こらない。
4
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
2
1
我々の拡張（２）
• 毒節点が正整数値の重みを持ち、その数だけ体力が減
るとする。
• 非毒節点は重み０の節点として考えることができるため、
全ての節点が整数値の重みを持つとする。
• （重みの和）＞（２者の体力の和）
0
→引き分けは起こらない。
4
0
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
2
0
1
我々の拡張（２）
• 毒節点が正整数値の重みを持ち、その数だけ体力が減
るとする。
• 非毒節点は重み０の節点として考えることができるため、
全ての節点が整数値の重みを持つとする。
• （重みの和）＞（２者の体力の和）
0
→引き分けは起こらない。
4
0
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
2
0
-1
名前の定義
• 各節点に整数値の重みがあるものを重み付き半順序集
合ゲームと呼ぶ。
• 重みが｛0,1｝であるものを単位毒半順序集合ゲームと呼
ぶ。
0
4
0
2
Kyoto University, Japan
0
-1
今回の結果（１）
• 単位毒半順序集合ゲームにおいて、どちらのプレイヤー
が必勝手順を持つか判別できる方法を得た。
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
今回の結果（２）
• dagがpathである重み付き半順序集合ゲーム（重み付き
経路ゲーム と呼ぶ）において、多項式時間必勝手順を
得た。
3
5
0
-2
Alice
Bob
Life : 3 Life : 3
Kyoto University, Japan
2
0
発表構成
１．組み合わせゲーム理論
２．半順序集合ゲーム
３．単位毒半順序集合ゲーム
４．重み付き半順序集合ゲーム
4.1.COST
4.2.毒の経路ゲーム
4.3.薬と毒の経路ゲーム
５．まとめ
Kyoto University, Japan
単位毒半順序集合ゲーム
•
•
•
•
•
各節点に{0,1}の重みがついている。
両者が整数値の体力を持つ。
取った重み和だけ体力が減る。
体力が負になったプレイヤーの負け。
（毒節点の数）＞（２者の体力の和）
→引き分けは起こらない
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
（２）両者の体力が同じならば、
（ａ）子孫を持たない節点が全て毒ならば、後手
（ｂ）そうでないならば、全ての毒節点とその祖先を縮約し、１つの毒節点にした普通
の半順序集合ゲームにおいて必勝手順を持つプレイヤーと同じ
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
単位毒半順序集合ゲームで必勝手順を持つプレイヤーは、
（１）両者の体力が異なるならば、体力の多いプレイヤー
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
（２）両者の体力が同じならば、
（ａ）子孫を持たない節点が全て毒ならば、後手
（ｂ）そうでないならば、全ての毒節点とその祖先を縮約し、１つの毒節点にした普通
の半順序集合ゲームにおいて必勝手順を持つプレイヤーと同じ
Kyoto University, Japan
単位毒半順序集合ゲーム
• 我々は以下の結果を得た。
定理１
（ｂ）そうでないならば、全ての毒節点とその祖先を縮約し、１つの毒節点にした普通
の半順序集合ゲームにおいて必勝手順を持つプレイヤーと同じ
Kyoto University, Japan
発表構成
１．組み合わせゲーム理論
２．半順序集合ゲーム
３．単位毒半順序集合ゲーム
４．重み付き半順序集合ゲーム
4.1.COST
4.2.毒の経路ゲーム
4.3.薬と毒の経路ゲーム
５．まとめ
Kyoto University, Japan
重み付き半順序集合ゲーム
•
•
•
•
•
各節点が整数値の重みを持つ。
両者が整数値の体力を持つ。
取った重み和だけ体力が減る。
体力が負になったプレイヤーの負け。
（重みの和）＞（２者の体力の和）
0
→引き分けは起こらない。
4
0
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
2
0
-1
重み付き半順序集合ゲーム
• dagを１本の路に限ったものについて多項式時間必勝手
順を与えた。
3
5
0
-2
-1
1
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
3
-1
0
重み付き経路ゲーム
• 重み付き経路ゲームを、正と負の節点が混在して
いることより「薬と毒の経路ゲーム」と呼ぶ。
• 一方全ての節点の重みが正であるものを「毒の経
路ゲーム」と呼ぶ。
3
5
0
-2
-1
1
Alice
Bob
Life : 0
Life : 2
Kyoto University, Japan
3
-1
0
重み付き経路ゲーム
• 重み付き経路ゲームを、正と負の節点が混在して
いることより「薬と毒の経路ゲーム」と呼ぶ。
• 一方全ての節点の重みが正であるものを「毒の経
路ゲーム」と呼ぶ。
3
5
0
-2
-1
1
Alice
Bob
Life : 1
Life : 2
Kyoto University, Japan
3
重み付き経路ゲーム
• 重み付き経路ゲームを、正と負の節点が混在して
いることより「薬と毒の経路ゲーム」と呼ぶ。
• 一方全ての節点の重みが正であるものを「毒の経
路ゲーム」と呼ぶ。
3
5
1
Alice
Bob
Life : 1
Life : 2
Kyoto University, Japan
毒の経路ゲームの多項式時間
必勝手順
• まずCOSTというゲームの多項式時間必勝手順を
得る。
• それを利用して毒の経路ゲームの多項式時間必勝
手順を得る。
Kyoto University, Japan
ＣＯＳＴ
• 路グラフが与えられ、各節点に正整数の重みがついてい
る。
• ２人のプレイヤーが交互に葉より好きな数の節点を取っ
ていく。
• 両者は自分の取る重み和を最小にすることを目的とする。
6
1
Kyoto University, Japan
4
3
1
2
ＣＯＳＴ
補題２
路グラフが v1 , v2 ,, vn で与えられており、それぞれの節点の重み
が w1 , w2 ,, wn であるとき、先手の最善重み和 LWnと後手の最善重
み和 RWnは以下の式で与えられる。
LW1 w1
RW1 0
LWn wn min{LWn 1 , RWn 1 }
RWn max{LWn 1 , RWn 1 }
Kyoto University, Japan
補題２の証明
（証明）
LWn
min{wn RWn 1 , wn wn 1 RWn 2 , wn wn 1 wn 2 RWn 3 , }
wn min{RWn 1 , wn 1 RWn 2 , wn 1 wn 2 RWn 3 , }
wn min{RWn 1 , min{wn 1 RWn 2 , wn 1 wn 2 RWn 3 , }}
wn min{RWn 1 , LWn 1 }
Kyoto University, Japan
補題２の証明
RWn
i 1 wi LWn
n
i 1 wi wn min{RWn 1 , LWn 1 }
n
i 1 wi min{RWn 1 , LWn 1 }
n 1
RWn 1 LWn 1 min{RWn 1 , LWn 1 }
max{RWn 1 , LWn 1 }
（証明終了）
Kyoto University, Japan
ＣＯＳＴの最善手順
• ３個取るのが最善手順である場合・・
minの選択で過去 i 回に渡りLWが選ばれ、i+1回目で
RWが選ばれた場合、i+1個取るのが必勝手順である。
Kyoto University, Japan
ＣＯＳＴ
定理３
COSTの最善重み和と最善手順は O(n) 時間で求まる。
6
1
Kyoto University, Japan
4
3
1
2
ＣＯＳＴの計算例
LW1 6,
LW2 1 min{6,0} 1, LW3 4 min{1,6} 5,
RW1 0
RW2 max{6,0} 6
RW3 max{1,6} 6
LW4 3 min{5,6} 8, LW5 1 min{8,6} 7, LW6 2 min{7,8} 9,
RW4 max{5,6} 6
6
RW5 max{8,6} 8
1
Kyoto University, Japan
4
3
RW6 max{7,8} 8
1
2
毒の経路ゲーム
• 全ての節点の重みが正整数であるもの。
アルゴリズム１ 毒の経路ゲームの解法
１．次の条件を満たす正整数 m を見つける。
（条件：葉から m 番目の節点までの重み和は体力の和より少ないが、葉から m+1番目の
節点までの重み和は体力の和より多い）
２．葉から m 番目の節点までをCOSTで解いて両者の最善重み和
AW,BW を求める。
３．AW LA , BW LB となった場合、プレイヤーBはCOSTの解法より勝
てる。
Kyoto University, Japan
毒の経路ゲーム
• 全ての節点の重みが正整数であるもの。
アルゴリズム１ 毒の経路ゲームの解法
４．AW LA , BW LB となった場合、葉から m+1 番目の節点までを
COSTで解いて両者の最善重み和AW,BW を求める。
５．AW LA , BW LB となった場合、プレイヤーBはCOSTの解法より
勝てる。
６．AW LA , BW LB となった場合、 m+1 番目の節点の重みを減らす
ことで AW LA , BW LB となるようにする。その時プレイヤーBはCOST
の解法より勝てる。その減らす値は二分探索により求める。
Kyoto University, Japan
補題４
補題４
AW LA , BW LB となった場合、プレイヤーBはCOSTの解法より勝て
る。
（証明）
• プレイヤーBはCOSTの解法に従う限り最大でもBWの重
み和しか取らなくてよい。即ちプレイヤーAは最小でもAW
の重み和を取らなくてはならず、必ず体力を失って負け
てしまう。（証明終了）
Kyoto University, Japan
定理５
定理５
アルゴリズム「毒の経路ゲームの解法」は毒の経路ゲームの必勝手順を
ああああ
O(n log w) 時間で計算する。ただしmax{w1 , w2 ,, wn } w
（証明）
• まず条件（葉から m 番目の節点までの重み和は体力の和より少ないが、葉から
m+1番目の節点までの重み和は体力の和より多い）を満たす正整数 m は必ず
見つかる。
• 葉から m 番目の節点までのゲームを考え、COSTで解く。
• 重み和は体力の和より少ないので、ここまでのゲームで両方とも体
力を失うことは有り得ない。ああああああああああああ
• よって以下の２つのケースしか有り得ない。
(i) AW L A , BW LB
(ii) AW L A , BW LB
Kyoto University, Japan
定理５
• (i) AW LA , BW LB の場合、補題４よりプレイヤーBは勝てる。
•(ii) AW LA , BW LB の場合、m+1番目の節点までのゲームを考え、
COSTで解く。
• 重み和は体力の和より多いので、ここまでのゲームで両方とも体力
を残すことは有り得ない。
• よって以下の２つのケースしか有り得ない。
(a)AW L A , BW LB
(b) AW L A , BW LB
Kyoto University, Japan
定理５
• (a)AW LA , BW LB の場合、補題４よりプレイヤーBは勝てる。
• (b) AW LA , BW LB の場合、m+1番目の節点の重みを減らしああ
AW LA , BW LBあとなるようにする。減らす値は二分探索により
あ
求める。
AW LA , BW LB
• なお、m+1番目の節点の重みを x 減らせばあああああああああああ
であり、x+1減らせば AW LA , BW LB となるような状況は起こり
得ないため、上記の減らす値は必ず存在する。
• 補題４よりプレイヤーBは勝てる。
O(n)
• 計算時間は二分探索に O(logw) 時間かかりCOSTの計算にあああ
時間かかるため O(n log w)
（証明終了）
Kyoto University, Japan
薬と毒の経路ゲーム
• 薬と毒の経路ゲームは O(n)時間で毒の経路
ゲームに変換され、毒の経路ゲームが解ければ
薬と毒の経路ゲームも解ける。
定理６
「薬と毒の経路ゲーム」の必勝手順は O(n log w) 時間で求まる。
Kyoto University, Japan
まとめ
• 単位毒半順序集合ゲームの必勝プレイヤーを知る方法を得た。
• 重み付き経路ゲームの多項式時間必勝手順が求められた。
今後の課題
• dagを一本の路に限定しない重み付き半順序集合ゲームの必勝法。
• 重み付き毒節点、体力といった概念により、二者の対立関係が多様
に表現できる。
→これにより、ゲーム理論に新しい知見をもたらすことはできないか。
Kyoto University, Japan
© Copyright 2024 ExpyDoc
