UNO is Hard, Even for a Single Player

カードゲームUNOの計算複雑性に
ついて
西関研究室
8662
塩谷健仁
１
研究背景
・組合せ的ゲーム
マインスイーパ、オセロ、チェス、テトリス
・研究対象：UNOの計算複雑性
２
UNOとは？
３
カードの種類
・数字カード
色｛1,…,ｃ｝と数字｛1,…,ｂ｝１つずつの組み合わ
せを持つ。
・アクションカード
‘Skip’, ‘Reverse’, ‘Draw 2’, ‘Wild’, ‘Wild Draw 4’
が存在する。
簡単化のためアクションカードは、ないものと
して考える。
４
UNOのルール
・プレイヤーは１人以上とする。
・プレイヤーがカードを出す順番は決められて
おり、一番最初の人は最初にどんな手札でも
1枚捨てることができる。
・次の人からは直前に場に出されたカードと色
または数字が同じである手札を1枚捨てるこ
とができる。
・最初の人が手札を全て捨てるか、途中で誰か
が出せなくなるまでゲームは続く。
５
例
START
６
UNO問題
・１人UNO問題
入力：プレイヤー１人に配ったｎ枚のカード
質問：ルールに則って、そのプレイヤーが全てのカードを捨て
る為の出し方があるか
・ｋ人UNO問題
入力：プレイヤーｋ人にそれぞれにｎ枚配った合計ｋｎ枚の
カード
質問：ルールに則って、最初のプレイヤーが持つ全てのカー
ドを捨てる為のｋ人のプレイヤー全員での出し方があ
るか
７
既存研究
１人UNO問題、２人UNO問題はNP完全
故に１人UNO問題、２人UNO問題を解くこ
とは現実的な時間では難しいと思われる
参考文献
E. D. Demaine, M. L. Demaine, R. Uehara, T. Uno, and Y. Uno,’’UNO Is Hard,
Even for a Single Player’’, Lecture Notes in Computer Science, Vol. 6099, pp.133-144, Springer(2010).
８
既存研究
色の個数cが定数である１人UNO問題は
2
c
O(n )時間で解ける。
参考文献
E. D. Demaine, M. L. Demaine, R. Uehara, T. Uno, and Y. Uno,’’UNO Is Hard,
Even for a Single Player’’, Lecture Notes in Computer Science, Vol. 6099, pp.133-144, Springer(2010).
９
研究結果
色の個数が２あるいは３の１人UNO問題
は線形時間で解けることを示した。
2色 O(n4)
O(n)
3色 O(n9)
O(n)
１０
・ 2色UNO問題
（1, ）,…,｜（2, ）,…,
・3色UNO問題
出し方を3通りに集約
（1、）,…,｜（２、）,…, ｜（３、）,…,
１１
まとめ
1人UNO問題で色数が２あるいは３の場合に、
既存研究の結果より計算時間を短縮できた。
今後の課題
色数が一般にｃ（定数）の場合でも、既存の
研究結果より計算時間を短縮するアルゴリ
ズムを開発。
１２
終
想定質問1
・アクションカードがあると、どうなります
か。
2色UNO問題と3色UNO問題の場合、
例えばDraw２カードがあっても、1人
UNO問題は線形時間で解けます。
想定質問２
・ｂ≦ｎとは限らない場合どうなりますか。
O(nlogn)で解けます。
想定質問３
・色が4色以上の時、線形時間で解けま
すか。
現在、考えています。
想定質問４
2
c
・どうしてO(n )なのか。
UNOカードを、カードの持つ要素である色と数字
に対応させた2次元平面格子状の点で表します。こ
れらの点を全て通るハミルトン路を探す問題を、ｃを
定数とした1人UNO問題と同等のものとして考えま
す。ハミルトン路を探す問題を解くのにO(nc2)時間か
かるので、ｃを定数とした1人UNO問題はO(nc2)時間
かかります。
これからの研究
・1人UNO問題で色数と数字数（３、ｂ）に
おいて、更に短い多項式時間で判定で
きるよう考える。
・ｋ人UNO問題についても研究していく。
１１
２人UNO
この場合でも１人UNOと同じく
難しいと言える
おそらく何人でやっても難しいと予想
UNOのルール
• 全員にカードを配り、順番にカードを捨てていく。
• 最初の人はどんなカードでも1枚捨てることがで
きる。
• 次の人からは直前に場に出されたカードと色ま
たは数字が同じであるカードを1枚捨てることが
できる。
• 一番早く手持ちカードを全て捨てることができた
人が勝ち。
• カードを捨てられなくなった人は負け。
パラメータ
プレイヤー数ｐ＝１
色集合X＝{１,…,ｃ}
数字集合Y＝{１,…,ｂ}
カード（ｘ、ｙ）∈X×Yとみなす。
「カード（ｘ’、ｙ’）を（ｘ、ｙ）の直後に出すことがで
きるための必要十分条件は、ｘ’＝ｘまたは
ｙ’＝ｙ」←ルールの肝
１人UNO
• 入力：ｎ枚のカード、ただし色数はｘ、数字の
数はｙ
• 出力：手持ちカードを全て出しきり上がれるか。
１人UNO
例：ｎ＝９のとき、プレイヤーの手持ちカード集
合（ｃｉ、ｂｉ）を
（１、３）（２、２）（２、３）（２、３）（２、４）（３、２）
（３、４）（４、１）（４、３）としたとき
次のUNOグラフというものを考える。
UNOグラフ
「１枚のカード」 →
「２枚のカードを連続して出せる」 →
（２，４）
と表す。
（４，１）
（２，２）
（２，３）
（４，３）
（３，４）
（３，２）
（２，３）
（１，３）
このように一人ＵＮＯをＵＮＯグラフに置き換える。
１人ＵＮＯで勝つためには
（２，４）
（４，１）
（２，２）
（２，３）
（４，３）
（３，４）
（３，２）
（２，３）
（１，３）
ＵＮＯグラフがハミルトン路を持つ→カードを出し切れる組み合わせを持つ。
キュービックグラフ
• 例
Ｇ
a
d
x
s
y
u
t
b
z
c
キュービックグラフがハミルトン路を持つかどうかはＮＰ完全。
キュービックグラフとＵＮＯグラフが同値だと示せれば、
ＵＮＯグラフがハミルトン路を持つかどうかはＮＰ完全だと言える。
Ｇの変形
Ｇ
Ｇ’
e1
e3
v
(v,e1)
(v,e3)
e2
(v,e2)
このように１つの頂点を３つに分割する。
Ｇの変換
Ｖ（Ｇ´）＝｛（ｘ，ｅ）｜ｘ∈Ｖ（Ｇ），ｅ＝｛ｘ，ｙ｝∈Ｅ（Ｇ）｝
Ｅ（Ｇ´）＝｛（（ｘ，ｅ），（ｙ，ｅ））｜ｅ＝｛ｘ，ｙ｝∈Ｅ（Ｇ）｝∪
｛（（ｘ，ｅｉ），（ｘ，ｅｊ））｜ｅｉ≠ｅｊ｝
(a,x)
(b,y)
(c,s)
(d,x)
(a,y)
(b,t)
(c,u)
(d,t)
(a,s)
(b,z)
(c,z)
(d,u)
これはカードの色ｘと数字ｙの（ｘ、ｙ）をルール通りに連続して出せる部分を結
んでいる。→ＵＮＯグラフと等価
グラフG’(UNOグラフ)
(a,x)
(d,x)
(a,y)
(a,s)
(d,t)
(b,y)
(b,t)
(c,s) (c,u)
(b,z)
(c,z)
Ｇ⇔Ｇ’を証明していく。
(d,u)
GからG’へ
Ｇがハミルトン路Ｐ＝(Vi1,…,Vin)を持つ。
PにおけるVij-1,Vij,Vij+1
(Vij-1,e1)
(Vij,e1)
(Vij,e3)
P’における(Vij-1,e1),(Vij,e1),(Vij,e3),(Vij,e2),(Vij+1,e2)
最初と最後：(Vi1,e1)(e1≠{Vi1,Vi2}),(Vi1,e2)(e2≠{Vi1,Vi2}),
(Vi1,{Vi1,Vi2}),(Vi2,{Vi1,Vi2})
(Vij,e2)
よってＧ→Ｇ’
(Vij+1,e2)
G’からGへ
(a,x)
(a,y)
(a,s)
中の全てを連続して通ってから次へいくなら、
明らかにG’→Gが分かる。
(v,e1)
(v,e2)
(a1)
(v,e3)
(v,e1)
(v,e2)
(a2)
(v,e3)
連続して通らないケース１
(v,e1)
(v,e2)
(b’)
(v,e3)
(v,e1)
(v,e2)
(b)
(v,e3)
連続して通らないケース２
(v,e1)
(v,e2)
(c’)
(v,e3)
(v,e3)
(v,e1)
(v,e2)
(c)
まとめ
Ｇ⇔Ｇ’＝ＵＮＯ-1が示せたので1人ＵＮＯにお
いて全てのカードを出し切ることは難しいこと
が証明された。

Download Report