京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作 重み付き半順序集合ゲームの必勝法 京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄　中村義作 Kyoto University, Japan

Kyoto University, Japan 発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 　4.1.COST 　4.2.毒の経路ゲーム 　4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan

Kyoto University, Japan 発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 　4.1.COST 　4.2.毒の経路ゲーム 　4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan

Kyoto University, Japan Nim 複数の石からなる山がいくつか与えられる。 ２人のプレイヤーが交互に石を取っていく。 －いくつ取っても良いが、１つの山からしか取れない。 最後の石を取ったプレイヤーの勝ち 排他的論理和による必勝手順[Bouton 1901] Kyoto University, Japan

Kyoto University, Japan 組み合わせゲーム理論 Sprague-Grundy定理[Sprague 1935-1936; Grundy 1939] －全ての組み合わせゲームはNimの山で表せる。 適用分野 －誤り訂正符号 －人工知能（例：碁の終盤局面） －ゲーム理論 －計算量理論 －アルゴリズム（例：必勝法） Kyoto University, Japan

Kyoto University, Japan 発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 　4.1.COST 　4.2.毒の経路ゲーム 　4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan

Kyoto University, Japan 半順序集合ゲーム ゲームの盤面としてdag（非閉路的有向グラフ）が与えられる。 交互に節点を１つずつ選んでいく。 選ばれた節点の子孫が消える。 最後の節点を取ったプレイヤーの勝ち。 Kyoto University, Japan

Kyoto University, Japan 半順序集合ゲーム ニムはdag（非閉路的有向グラフ）で表現できる。 Kyoto University, Japan

Kyoto University, Japan 半順序集合ゲーム 半順序集合ゲームは毒節点で表現できる。 －例：Chomp Kyoto University, Japan

Kyoto University, Japan 我々の拡張（１） 毒節点がdagの任意の場所に複数あるものを考える。 両者が整数値の体力を持つ。 毒を取った数だけ体力が減る。 体力が負になったプレイヤーの負け。 （毒節点の数）＞（２者の体力の和） →引き分けは起こらない Alice Life : 0 Bob Life : 2 Kyoto University, Japan

Kyoto University, Japan 我々の拡張（２） 毒節点が正整数値の重みを持ち、その数だけ体力が減るとする。 非毒節点は重み０の節点として考えることができるため、全ての節点が整数値の重みを持つとする。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 1 Kyoto University, Japan

Kyoto University, Japan 我々の拡張（２） 毒節点が正整数値の重みを持ち、その数だけ体力が減るとする。 非毒節点は重み０の節点として考えることができるため、全ての節点が整数値の重みを持つとする。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 1 Kyoto University, Japan

Kyoto University, Japan 我々の拡張（２） 毒節点が正整数値の重みを持ち、その数だけ体力が減るとする。 非毒節点は重み０の節点として考えることができるため、全ての節点が整数値の重みを持つとする。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 -1 Kyoto University, Japan

Kyoto University, Japan 名前の定義 各節点に整数値の重みがあるものを重み付き半順序集合ゲームと呼ぶ。 重みが｛0,1｝であるものを単位毒半順序集合ゲームと呼ぶ。 4 2 -1 Kyoto University, Japan

Kyoto University, Japan 今回の結果（１） 単位毒半順序集合ゲームにおいて、どちらのプレイヤーが必勝手順を持つか判別できる方法を得た。 Alice Life : 0 Bob Life : 2 Kyoto University, Japan

Kyoto University, Japan 今回の結果（２） dagがpathである重み付き半順序集合ゲーム（重み付き経路ゲーム　と呼ぶ）において、多項式時間必勝手順を得た。 3 5 -2 2 Alice Life : 3 Bob Life : 3 Kyoto University, Japan

Kyoto University, Japan 発表構成 １．組み合わせゲーム理論 ２．半順序集合ゲーム ３．単位毒半順序集合ゲーム ４．重み付き半順序集合ゲーム 　4.1.COST 　4.2.毒の経路ゲーム 　4.3.薬と毒の経路ゲーム ５．まとめ Kyoto University, Japan

Kyoto University, Japan 単位毒半順序集合ゲーム 各節点に{0,1}の重みがついている。 両者が整数値の体力を持つ。 取った重み和だけ体力が減る。 体力が負になったプレイヤーの負け。 （毒節点の数）＞（２者の体力の和） →引き分けは起こらない Alice Life : 0 Bob 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

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

Kyoto University, Japan 重み付き半順序集合ゲーム 各節点が整数値の重みを持つ。 両者が整数値の体力を持つ。 取った重み和だけ体力が減る。 体力が負になったプレイヤーの負け。 （重みの和）＞（２者の体力の和） →引き分けは起こらない。 4 Alice Life : 0 Bob Life : 2 2 -1 Kyoto University, Japan

Kyoto University, Japan 重み付き半順序集合ゲーム dagを１本の路に限ったものについて多項式時間必勝手順を与えた。 3 5 -2 -1 1 3 -1 Alice Life : 0 Bob Life : 2 Kyoto University, Japan

Kyoto University, Japan 重み付き経路ゲーム 重み付き経路ゲームを、正と負の節点が混在していることより「薬と毒の経路ゲーム」と呼ぶ。 一方全ての節点の重みが正であるものを「毒の経路ゲーム」と呼ぶ。 3 5 -2 -1 1 3 -1 Alice Life : 0 Bob Life : 2 Kyoto University, Japan

Kyoto University, Japan 重み付き経路ゲーム 重み付き経路ゲームを、正と負の節点が混在していることより「薬と毒の経路ゲーム」と呼ぶ。 一方全ての節点の重みが正であるものを「毒の経路ゲーム」と呼ぶ。 3 5 -2 -1 1 3 Alice Life : 1 Bob Life : 2 Kyoto University, Japan

Kyoto University, Japan 重み付き経路ゲーム 重み付き経路ゲームを、正と負の節点が混在していることより「薬と毒の経路ゲーム」と呼ぶ。 一方全ての節点の重みが正であるものを「毒の経路ゲーム」と呼ぶ。 3 5 1 Alice Life : 1 Bob Life : 2 Kyoto University, Japan

Kyoto University, Japan 毒の経路ゲームの多項式時間必勝手順 まずCOSTというゲームの多項式時間必勝手順を得る。 それを利用して毒の経路ゲームの多項式時間必勝手順を得る。 Kyoto University, Japan

Kyoto University, Japan ＣＯＳＴ 路グラフが与えられ、各節点に正整数の重みがついている。 ２人のプレイヤーが交互に葉より好きな数の節点を取っていく。 両者は自分の取る重み和を最小にすることを目的とする。 6 1 4 3 1 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 ＣＯＳＴの最善手順 ３個取るのが最善手順である場合・・ minの選択で過去 i 回に渡りLWが選ばれ、i+1回目でRWが選ばれた場合、i+1個取るのが必勝手順である。 Kyoto University, Japan

Kyoto University, Japan ＣＯＳＴ 定理３ COSTの最善重み和と最善手順は　　　　時間で求まる。 6 1 4 3 1 2 Kyoto University, Japan

Kyoto University, Japan ＣＯＳＴの計算例 6 1 4 3 1 2 Kyoto University, Japan

Kyoto University, Japan 毒の経路ゲーム 全ての節点の重みが正整数であるもの。 アルゴリズム１　毒の経路ゲームの解法 １．次の条件を満たす正整数 m を見つける。 （条件：葉から m 番目の節点までの重み和は体力の和より少ないが、葉から m+1番目の節点までの重み和は体力の和より多い） ２．葉から m 番目の節点までをCOSTで解いて両者の最善重み和AW,BW を求める。 ３． となった場合、プレイヤーBはCOSTの解法より勝てる。 Kyoto University, Japan

Kyoto University, Japan 毒の経路ゲーム 全ての節点の重みが正整数であるもの。 アルゴリズム１　毒の経路ゲームの解法 ４．　　　　　　　　　　　　　となった場合、葉から m+1 番目の節点までをCOSTで解いて両者の最善重み和AW,BW を求める。 ５．　　　　　　　　　　　　　となった場合、プレイヤーBはCOSTの解法より勝てる。 ６． となった場合、 m+1 番目の節点の重みを減らすことで　　　　　　　　　　　　　となるようにする。その時プレイヤーBはCOSTの解法より勝てる。その減らす値は二分探索により求める。 Kyoto University, Japan

Kyoto University, Japan 補題４ 補題４ 　　　　　　　　　　　　　となった場合、プレイヤーBはCOSTの解法より勝てる。 （証明） プレイヤーBはCOSTの解法に従う限り最大でもBWの重み和しか取らなくてよい。即ちプレイヤーAは最小でもAWの重み和を取らなくてはならず、必ず体力を失って負けてしまう。（証明終了） Kyoto University, Japan

Kyoto University, Japan 定理５ 定理５ アルゴリズム「毒の経路ゲームの解法」は毒の経路ゲームの必勝手順をああああ　 時間で計算する。ただし （証明） まず条件（葉から m 番目の節点までの重み和は体力の和より少ないが、葉から m+1番目の節点までの重み和は体力の和より多い）を満たす正整数 m は必ず見つかる。 葉から m 番目の節点までのゲームを考え、COSTで解く。 重み和は体力の和より少ないので、ここまでのゲームで両方とも体力を失うことは有り得ない。ああああああああああああ よって以下の２つのケースしか有り得ない。 Kyoto University, Japan

Kyoto University, Japan 定理５ 　　　　　　　　　　　　　の場合、補題４よりプレイヤーBは勝てる。 　　　　　　　　　　　　　の場合、m+1番目の節点までのゲームを考え、COSTで解く。 重み和は体力の和より多いので、ここまでのゲームで両方とも体力を残すことは有り得ない。 よって以下の２つのケースしか有り得ない。 Kyoto University, Japan

Kyoto University, Japan 定理５ 　　　　　　　　　　　　　　の場合、補題４よりプレイヤーBは勝てる。 　　　　　　　　　　　　　　の場合、m+1番目の節点の重みを減らしあああ　　　　　　　　　　　あとなるようにする。減らす値は二分探索により求める。 なお、m+1番目の節点の重みを x 減らせばあああああああああああであり、x+1減らせば　　　　　　　　　　　　　となるような状況は起こり得ないため、上記の減らす値は必ず存在する。 補題４よりプレイヤーBは勝てる。 計算時間は二分探索に　　　　　　時間かかりCOSTの計算にあああ時間かかるため （証明終了） Kyoto University, Japan

Kyoto University, Japan 薬と毒の経路ゲーム 薬と毒の経路ゲームは　　　時間で毒の経路ゲームに変換され、毒の経路ゲームが解ければ薬と毒の経路ゲームも解ける。 定理６ 「薬と毒の経路ゲーム」の必勝手順は　　　　　　時間で求まる。 Kyoto University, Japan

Kyoto University, Japan まとめ 単位毒半順序集合ゲームの必勝プレイヤーを知る方法を得た。 重み付き経路ゲームの多項式時間必勝手順が求められた。 dagを一本の路に限定しない重み付き半順序集合ゲームの必勝法。 重み付き毒節点、体力といった概念により、二者の対立関係が多様に表現できる。 →これにより、ゲーム理論に新しい知見をもたらすことはできないか。 今後の課題 Kyoto University, Japan