数理解析研究所講究録
第 1744 巻 2011 年 48-55

48

UNO は一人でも難しい
UNO is hard, even for a single player
Erik D. Demaine*

Ryuhei Uehara \d ag er
Martin L. Demaine \dag er
Yushi UNO\P

Takeaki UNO \S

アブストラクト．UN
is one of the world-wide well-known and popular card games.
We investigate UNO from the viewpoint of combinatorial algorithmic game theory by giving some simple and concise mathematical models for it. They include cooperative anduncooperative versions of UNO, for example. As a result of analyzing their computational
complexities, we prove that even a single-player version of UNO is NP-complete, while
it becomes in in some restnicted cases. We also show that uncooperative two-player’s
version is PSPACE-complete.
$O$

$P$

1

Introduction

example, if it is multi-player or single-player,

Playing games and puzzles is a lot of fun for everybody, and analyzing games and puzzles haslong been attracted much interests of both mathematicians and computer scientists [8, 11]. One of
the central issues is their computational complexities, that is, how hard or easy to get an answer ofpuzzles or to decide the winner of games [2, 4, 7].
In this paper, we focus on one of the well, andknown and popular card games called
investigate it from the viewpoint of algorithmic
combinatorial game theory [2] to add it to the research list. More specifically, we propose mathematical models of UNO, which is one of the main
purposes of this paper, and then examine their
computational complexities. As a result, even asingle-player version of UNO is computationallyintractable, while we can show that the problem
becomes rather easy under a certain restriction.
$UNO^{\copyright}$

2 Preliminaries
Games are often categorized from several aspects
of propelties that they have when we research
it theoretically. Typical classifications are, forマサチューセッツ工科大学
第 1 著者に同じ
キ北陸先端科学技術大学院大学\S 国立情報学研究所
1 大阪府立大学$*$$\dagger$

imperfect-information or perfect-information, cooperative or uncooperative, and so on [2, 11].
A single-player game is automatically perfectinformation and cooperative, and is sometimes
called a puzzle.

2.1 Game settings
UNOli is one of the world-wide well-known andpopular card games. It can be played by 2-10

players. Each player is dealt equal number ofcards at the beginning of the game, where each(normal) card has its color and number (except forsome special ones called ’action cards’). The basic rule is that each player plays in tum, and one
can discard exactly one of $his/her$ cards at hand in
one’s tum by matching the card with its color or
number to the one discarded immediately before
one. The objective of a single game is to be thefirst player to discard all the cards in one’s hand
before one’s opponents. Thus, UNO is a (i) multiplayer, (ii) imperfect-information, and (iii) uncooperative combinatorial gameIn the real game setting of UNO, it is quite tmethat action cards play important roles to make thisgame complicated and interesting. However, in
this paper, when we model the game mathematically, we concentrate on the most important aspectof the rules of UNO that a card has a color and a$||$

UNO is a registered trademark of Mattel Corporation.

49
number and that one can discard a card only if its
color or number match the card discarded immediately before one’s tum. In addition to obeying
this fundamental property, for theoretical simplicity, we set following assumptions on our mathematical models: (a) we do not take into accounteither action cards nor draw pile, (b) all the cards
dealt to and at hand of any player are open during the game, i.e., perfect-information, (c) we do
not necessarily assume that all the players have asame number of cards at the beginning of a game(unless otherwise stated), (d) any player that cannot discard any card at hand skips one’s tum but
still remains in the game and waits for the nexttum, (e) any player acts rationally, e.g., any player
is not allowed to skip one’s tum intentionally, and(f) the first player can start a game by discarding
any card $he/she$ likes at hand.

A discarding (or playing) sequence (of cards) of acard set is a sequence of cards
such
A discardingthatandsequence
is feasible ifmatches$\ldots,k-1$
for $j=1,$.
In our mathematical models of UNO, we specify the problems by four parameters: number ofplayers , number of total cards , number of colors and the number of numbers . Two values
and are assumed to be unbounded unless otherwise stated.
$C$$(t_{s_{1}}, \ldots, t_{s_{k}})$$t_{s_{i}}\in C$$t_{s_{i}}\neq t_{s_{j}}(i\neq J2\cdot$$(t_{s_{1}}, \ldots, t_{s_{k}})$$t_{s_{j+1}}$$t_{s_{j}}$

$n$

$p$

$b$

$c$

$c$

$b$

2.3 Models
We now define two different versions of UNO, one
is cooperative and the other is uncooperative.
UNCOOPERATIVE UNO
Instance: the number of players , andplayer ’s card set with colors andnumbers.
Question: determine the first player thatcannot discard one’s card any more.
$p$

$i$

2.2 Definitions and Notations
An UNO card has two attributes called color andnumber, and in general, we define a card to be atuple $(x,y)\in X\cross Y$, where $X=\{1, \ldots, c\}$ is a setof colors and $Y=\{1, \ldots, b\}$ is a set of numbers.
Finite number of players 1, 2, ..., $p(\geq 1)$ can join
an UNO game. At the beginning of a single gameof UNO, each card of a set of cards is dealt to
one player among players, i.e., each player is
initially given a set of cards;$(i=1, \ldots,p)$ . By definition,. Here,we assume that is a multiple set, that is, there
may be more than one card with the same color
and the same number. We denote a card $(x,y)$ dealt
to player by $(x,y)_{i}$ . When the number of players
is one, we omit the subscript without any confusion. Throughout the paper, we assume without
loss of generality that player 1 is the first to play,and players 1, 2, .. ., play in tum in this order.
Player can discard (or play) exactly one card
currently at hand in $his/her$ tum if the color or thenumber of the card is equal to each of the card
discarded immediately before player . In otherwords, we say that a card $t’=(x’,y’)_{i’}$ can be discarded immediately after a card $t=(x,y)_{j}$ if andonly if $(x’=x\vee y’=y)\wedge i’=i+1(mod p)$. We
also say that a card matches a card whencan be discarded after . A discarded card is removed from a set of cards at hand of the player.
$n$

$i$

$C_{i}=\{t_{i,1}, \ldots, t_{i,n_{i}}\}$$\sum_{i=1}^{p}n_{i}=n$

$C$

$i$

$p$

$i$

$i$

$t’$

$t$

$t$

$b$

$c$

We refer to this UNCOOPERATIVE UNO with

$p$

play-

ers as UNCOOPERATIVE UNO-p. This problem setting
makes sense only if $p\geq 2$ since UNO played by asingle player becomes automatically cooperative.

$C$

$p$

$C_{i}$$C_{i}$$t’$

COOPERATIVE UNO
Instance: the number of players ,with colors andplayer ’s card set
numbers.
Question: can all the players makeplayer 1 win, i.e., make player ’s card
set empty before any of the other players
become finished.
$p$

$i$

$C_{i}$

$c$

$b$

$1$

We abbreviate COOPERArIVE UNO played by players as COOPERATIVE UNO-p, or simply as UNO-p.
This problem setting makes sense if the numberof players is greater than or equal to 1. In UNCO$OPERATIVE/CooPERATWE$ UNO, when the number ofplayers is given by a constant, such as UNO-2, it
implies that is no longer a part of the input ofthe problem.
We define UNO-p graph as a directed graph torepresent ’match’ relationship between two cards
in the entire card set. More precisely, a vertex
corresponds to a card, and there is a directed arc
$p$

$p$

$p$

50
from vertex to if and only if their corresponding cards matches (can be discarded immediately after) . Let us consider UNO-I graph, i.e.,
UNO-p graph in case that the number of players$p=1$ . In this case, a card matches if and only
if matches , that is, the ’match’ relation is symmetric. This implies that UNO-I graph becomes
undirected. For UNO-2 graph, a card $t’=(x’,y’)_{2}$matches $t=(x,y)_{1}$ if and only if matches , andtherefore, UNO-2 graph also becomes undirected.
Furthremore, since a player cannot play consecutively when the number of players $p\geq 2$ , UNO-2
graph becomes bipartite. In general, since cards
of a card set is dealt to players at the beginning of a single UNO game, i.e., is partitioned
into $C_{i}=\{(x,y)_{i}\}$ , UNO-p graph becomes a (restricted) p-partite graph whose partite sets correspond to .
$u$

$v$

$t_{v}$$t_{u}$

$t’$

$t$

$t’$

$t$

$t’$

$t$

$n$

$C$

$p$

$C$

$C_{i}$of HP is yes if and only if the answer of an instance of UNO-2 is yes. If there is a Hamilto, in the innian path, say
stance graph of HP, then there is a feasible discarding sequence altematively by player ’s and,’s as, which ends up player ’s card
before player $2’ s$ . Conversely, if there is a feasible,
discarding sequence, it visits all the vertices in of $G’$ exactly once, and thus the correis
sponding sequence of vertices
a simple path visiting all the veltices in $V(G)$ exactly once, that is, a Hamiltonian path in .
The size of an instance of UNO-2 is proportional. Since $|C_{1}|=|V(G)|$ and $|C_{2}|=|E(G)|$ ,tothe reduction is done in polynomial size in $|V(G)|+$$|E(G)|$ , which is the input size of an instance of
HP. This completes the proof.
$P=(v_{i_{1}}, v_{i_{2}}, \ldots, v_{i_{n}})$

$1$

$2$

$((i_{1}, i_{1})_{1},$ $(i_{1}, i_{2})_{2},$ $(i_{2}, i_{2})_{1},$$(i_{n-1}, i_{n})_{2},$$\ldots,$$(i_{n-1}, i_{n-1})_{1}$$1$$(i_{n}, i_{n})_{1})$$((i_{1}, i_{1})_{1},$ $(i_{1}, i_{2})_{2},$ $(i_{2}, i_{2})_{1},$$(i_{n-1}, i_{n-1})_{1},$$(i_{n-1}, i_{n})_{2},$$\ldots$$(i_{n}, i_{n})_{1})$$X$$(v_{i_{1}}, v_{i_{2}}, \ldots, v_{i_{n}})$$G$$|C_{1}|+|C_{2}|$$o$3 Cooperative UNO

Corollary 2 UNO-2 is NP-complete even when
the number of cards of two players are equal.

In this section, we focus on the cooperative version of UNO, and discuss its complexity when thenumber of players is two or one.

Proof. Reduction from HAMiLTONIAN PATII withspecified starting vertex, which is known to be

3.1 Two-players’case

NP-complete [10].
We consider the same reduction in the proof of
Theorem 1. As in that proof, we can assume
without loss of generality. When $|C_{1}|=|C_{2}|$ ,$|C_{1}|\leq$$|C_{2}|$

We first show that UNO-2 is intractable.

cards
we are done. If $|C_{1}|<|C_{2}|$ , add$(n+2, n+2)$ and a single card $(n+2, n+1)$ to,, a single card $(i,n+1)(i\in\{1, \ldots,n\})$ to
and player 1 starts with card $(n+2,n+2)$ . This
forces the original graph to specify a starting (orending) vertex of a Hamiltonian path to be .
$|C_{2}|-|C_{1}|$$C_{2}$$C_{1}$

Theorem 1 UNO-2 is NP-complete.

$G$

Proof. Reduction from HAMiLTONIAN PATH (HP).
An instance of HP is given by an undirected
graph . The problem asks if there is a Hamiltonian path in , and it is known to be NP-complete[10]. Here, we assume without loss of generalitythat is connected and is not a tree, and hence
that $|V(G)|\leq|E(G)|$ . We transform an instance of
HP into an instance of UNO-2 as follows. Letandbe the card set of players 1 and 2, respectively. We define $C_{1}=\{(i, i)|v_{i}\in V(G)\}$ and$C_{2}=\{(i, r) \{v_{i}, v_{j}\}\in E(G)\}$ . Then, notice thatthe resulting UNO-2 graph $G’$ , which is bipartite,
has partite sets
and $Y(X\cup Y=V(G’))$ corresponding to $V(G)$ and $E(G)$ , respectively, andrepresents vertex-edge incidence relationship of. Now we show that the answer of an instance$v_{i}$$an\square$

$G$

$G$

$G$

$C_{1}$$C_{2}$$X$$G$

Single-player’s intractable case

3.2

In single-player’s case, two different versions of
UNO, cooperative and uncooperative ones, be-come equivalent. We redefine this setting as thefollowing:
UNO-I $(So\iota rrAR$ UNO
Instance: a set of cards $(x_{i},y_{i})(i=$1, . .., , where
and
$)$

$C$

$n)$

$n$

$x_{i}\in\{1, \ldots, b\}$$y_{i}\in$

1,.
Question: determine if the player candiscard all the cards.
$\{$$\ldots,$

$c\}$

51
Example3 Let the card set for player 1 is give
by $C=\{(1,3),$ $(2,2),$ $(2,3),$ $(2,3),$ $(2,4),$ $(3,2)$ ,(3,4), (4, 1), (4, 3) . Then, a feasible discarding
sequence using all the cards is $((1,3),$ $(2,3),$ $(2,4)$ ,(3, 4), (3, 2), (2, 2), (2, 3), (4, 3), (4, 1) in this order, for example, and the answer is yes. The corresponding UNO-I graph is depicted in Fig. 1.
$C$

$\}$

$)$

This transformation implies that any vertex $x\in$$V(G)$ is split into three new vertices $(x, e_{i})(i=$$1,2,3)$ to form a clique (triangle), while each incident edge $e_{i}(i=1,2,3)$ to becomes incident. (We call it a “node gadget”
to a new vertex
as shown in Fig. 3.) Then we prepare the card
set of the player of UNO-I to be the set $V(G’)$ ,where the color and the number of $(x, e)$ are and, respectively. We can easily confirm that there
is an edge $e=(t, t’)$ in $G’$ if and only if andmatch, i.e., $G’$ is the corresponding UNO-I graphfor card set . Now it suffices to show that there
is a Hamiltonian path in of an instance of HP-C
if and only if there is a Hamiltonian path in $G’$ .
Suppose there is a Hamiltonian path, say $P=$
, in . We constmct a Hamiltonian
path in $G’$ from as follows. Let
be three consecutive vertices in in this order, and$x$$(x, e_{i})$

$C$

$x$

$e$

$t$

$t’$

$C$

$G$

Figure 1: An example of UNO-I graph.

$G$$(v_{i_{1}}, \ldots, v_{i_{n}})$

$P’$

$P$

$v_{i_{j-1}},$$v_{i_{j}},$$v_{i_{j+1}}$

$P$

let

$e_{1}=\{v_{i_{j-1}}.’and$e_{2}=\{v_{i_{j}}, v_{i_{j+1}}\}$

v_{i_{j}}\},$$e_{3}=\{v_{i_{j}},v_{i_{k}}\}$. Then we replace these three ver,tices by the sequence of vertices$(k\neq j-], ]+1)$

Figure 2: A claw-free graph that is not UNO-I.

$(v_{i_{j-1}}, e_{1}),$In UNO-I graphs, all the vertices whose corresponding cards have either the same color or number form a clique. A graph that contains no induced
is called claw-free [5, 6]. Since at least
two of the three cards that match a card must havethe same color or number, we have the following
fact.
$K_{1,3}$Observation 1 UNO-I graph is claw-free.
Notice that the converse does not hold, that is, theclass of UNO-I graphs is a proper subset of theclass of claw-free graphs (Fig. 2).
Now we can easily understand that UNO-I is essentially equivalent to finding a Hamiltonian pathin UNO-I graph. But unfortunately, we can showthat UNO is hard even for a single player.

$(v_{i_{j}}, e_{3}),$$(v_{i_{j+1}}, e_{2})$$(v_{i_{j}}, e_{2}),$$v_{i_{1}}$$v_{i_{2}}$$(v_{i_{1}}, e_{1})(e_{1}\neq\{v_{i_{1}}, v_{i_{2}}\}),$

$-$

$G$

$G$

$V(G’)=\{(x, e)|x\in V(G), e=\{x,y\}\in E(G)\}$ ,$E(G’)=\{((x, e), (y, e))|e=\{x,y\}\in E(G)\}$.

$(v_{i_{1}}, e_{2})(e_{2}\neq\{v_{i_{1}},v_{i_{2}}\})$,(same for the ending
two vertices). We can now confirm that the resulting sequence of vertices $P’$ in $G’$ form a Hamilto$(v_{i_{1}}, \{v_{i_{1}}, v_{i_{2}}\}),$$(v_{i_{2}}, \{v_{i_{1}}, v_{i_{2}}\})$

nian path.

Figure 3: A node gadget splits a vertex into three vertices to form a triangle.

For the converse, we have to show that if there
is a Hamiltonian path in UNO-I graph $G’$ , thenthere is in . If visits $(v, e_{i})(i=1,2,3)$ consecutively in any order (call it ”consecutiveness”) for
any . then can be transformed into a Hamiltonian path in in an obvious way. Suppose
not, that is, a Hamiltonian path $P’$ in $G’$ does not
visit $(v, e_{i})(i=1,2,3)$ consecutively. It suffices
to show that suchcan be transformed into another path to satisfy the consecutiveness. See [3]for details.
The reduction can be done in the size proportional to the size of an instance of HP-C. Thus,
$P’$

$G$

Proof. A cubic graph is a graph each of whose
vertex has degree 3. We reduce HAMILTONIAN PATH
for cubic graphs (HP-C), which is known to be
NP-complete [9], to UNO I.
Let an instance of HP-C be . We transform
into a graph $G’$ , where$\cup\{((x, e_{i}), (x, e_{j}))|e_{i}\neq e_{j}\}$to form a subin
andpath in $P’$ . For the starting two vertices, we replace them by the sequence of vertices$P’$

Theorem 4 UNO-I is NP-complete.

$(v_{i_{j}}, e_{1})$

$G’$

$v$

$P’$

$P$

$G$

$P’$

52
the proof is completed.

$\square$

Theorem 4 together with Observation 1 implies
the following fact as a corollary, which is knownin [1].
Corollary 5 HAMLTONIAN PATII
graphs is NP-complete.

for claw-free

3.3 Single-player’s tractable caseIn the remaining part of this section, we will showthat such an intractable problem UNO-I becomes
tractable if the number of colors is bounded bya constant. It will be solved by dynamic programming (DP) approach. To illustrate the DP for UNO1, we first introduce a geometric view of UNO-I
graphs.
Since an UNO card $(x,y)$ is an ordered pair of
integer values standing for its color and number, it
can be viewed as a (integer) lattice point in the 2dimensional lattice plane. Then an UNO-I graphis a set of points in that plane, where all the points
with the same x- or y-coordinate form a clique.
We call this way of interpretation a geometric viewof UNO-I graphs. The geometric view of an instance in Example 3 is shown in Fig. 4 (a). Now
the problem $UN$ , which is equivalent to finding a Hamiltonian path in UNO-I graphs, asks if,
for a given set of points in the plane and startingand ending at appropriate different points, one canvisit all the points exactly once under the condition that only axis-parallel moves are allowed ateach point (Fig. 4 $(b)$ ).
$c$

$y$

(number)$y$forms a Hamiltonian path if and only if it is a single path that spans . Suppose a subgraph is aspanning path of . If we consider a subset ‘of the point set , then $P[C’]$ (the subgraph ofinduced by $C’$ ) is a set of subpaths that spans$G[C’]$ . We count and maintain the number of setsof subpaths by classifying subpaths into three disjoint subsets according to the types of their two
endpoints.
Starting with the empty set of points, the DP
proceeds by adding a new point according to a
fixed order by updating the number of sets of subpaths iteratively. Finally when the set of points
grows to , we can confirm the existence of a
Hamiltonian path in by checking the numberof sets of subpaths consisting of a single subpath(without isolated vertices). Remark that, throughout this DP, we regard for convenience that an isolated vertex by itself contains a (virtual) path starting and ending at itself that spans it.
$P$

$G$

$C$

$G$

$C$

$P$

$C$

$G$

Mechanism. To specify a point to be added in
an iteration of the DP, we define a relation on
the point set , where $x(t)$ and $y(t)$ are x- and ycoordinates of a point , respectively: Let andbe two points in , then $t\prec t=y(t)<y(l)$or $(y(t)=y(t)\wedge x(t)<x(t’))$ . When $t=t’$ , a tie
breaks arbitrary. This relation $\prec defines$ a total order on , and we refer points in toaccording to the increasing order of . We also
define $C_{t}=\{t_{i}|1\leq i\leq f\}$ . Now points are addedfrom to , and consider when a new point$=(x(t_{l}),y(t_{I}))$ is added to. It must be added
either to two, one or zero endpoints of different
subpaths to form a new set of subpaths.
Now let $P(t)$ be a family of sets of subpaths. (Recall that we regard that an
spanning
isolated vertex contains a path spanning itself.)
Then we classify subpaths in a set of subpathsin the following manner: for any subpath
and the y-coordinates of its two endpoints,(type-h), (ii) exactly one
either (i) both equal(type-v), or (iii) none equalsof two equals(type-d) holds. We count the number of such
three types of subpaths infurther by classifyof their endpoints.
them
x-coordinates
by theing(Notice that types-h, -d are symmetric but type-v
is not with respect to x-coordinate.) For this purpose, we prepare some subscript sets: a set of subscripts $K=\{1, \ldots, c\}$ , sets of unordered pair of$\prec$

$C$

$t’$

$t$

$t$

$C$

$C$

$C$

$n$

$t_{1},$$\ldots,$$t_{n}$$\prec$$t_{1}$$t_{n}$$t_{\ell}$$C_{\ell-1}$$G[C_{\ell}]$$\mathcal{P}$$\in \mathcal{P}(t)$$P\in \mathcal{P}$$x$(color)$y(t_{I})$$y(t_{\ell})$Figure 4: (a) Geometric view of a UNO-I graph, where
all the edges are omitted and (b) a Hamiltonian path in
the UNO-I graph.

Strategy. Let be a set of points and be an
UNO-I graph defined by . Then a subgraph
$C$

$n$

$C$

$G$

$P$

$y(t_{\ell})$$\mathcal{P}$53
subscripts
and $I^{+}=I\cup\{\{i, i\}|i\in K\}$ , andsets of ordered pair of subscripts $J=K\cross K$ and$J^{-}=J-\{(i, i)|i\in K\}$ .
We now introduce the following parameters ,and to count the number of subpaths in$I=(\begin{array}{l}K2\end{array})$

$h$

$d$

$v$

$\mathcal{P}(f))$$\mathcal{P}(\in$:$h_{\{i,i’\}}$: #subpaths in

and

$P$

for

$(x_{i’},y(t_{l}))$: #subpaths inwith endpoints$\{i, i’\}\in I^{+}$, the one whose one enda graph induced by), and the other(counted inpoint is$(k,y)(y<y(t_{l}))$(counted
whose one endpoint is. The number of such paths is the sum ofinand . See
those for all the combinations of[3] for details.
$C_{l-1}$$(x_{i},y(t_{\ell}))$$v_{(i,i’)}$$d_{\{j,k\}})$

$i,$

$i’$

$j$

$(x_{j},y(t_{l}))$,with endpoints$(x_{i’},y’)$$(i,i’)\inJ$ and $y’<y(t_{l})$ ,
and
for
$P$
: #subpaths in with endpoints$v_{(i,\Gamma)}$$P$$(x_{i},y(t_{e}))$$(x_{i},y’)$$d_{\{i,i’\}}$

and

for

$(x_{i’},y’’)$$\{i, i’\}\in I^{+}$

and $y’,y”<y(t_{l})$ .
$i$Then we define a $(2|I^{+}|+|J|)$ -dimensional
vector $z(P)$ for a set of subpaths $P$

$j$

$i’$

$k$

$(\in$

as$P(f))$$h_{\{1,c\}},$ $h_{\{2,2\}},$$v_{\{1,c\}}$,$\langle d_{\{1,1\}},$$\ldots,$$v_{\{2.1\}}$$\ldots,$,$(\vec{h};\vec{v};\vec{d})$$=$$z(\mathcal{P})$$h_{\{2,c\}},$ $h_{\{3,3\}},$$v_{\{2,2\}}$

,

...,

$d_{\{1,c\}},$ $d_{\{2,2\}},$$\ldots,$$\ldots,$$v_{\{2,c\}},$$=$$(\langle h_{\{1,1\}},$$h_{\{c,c\}}\rangle;\langle v_{\{1,1\}},$$v_{\{3,1\}},$$d_{\{2,c\}},d_{\{3,3\}}$$\ldots,$, ...,$\ldots$$\ldots$$v_{\{c,c\}}\rangle$$d_{\{c,c\}}\rangle)$

,
,

;

.

Finally, for a given vector, we define thenumber of setssatisfying
ini.e.,a family $P(f)$ by,. Now the objective of the DP is to determine if there exists a
vector, wheresuch that
all the elements inand are except for exactly one element is 1.
Recursion. As we explained, the DP proceeds byadding a new point to. When is added, it
is connected to either $0,1$ or 2 endpoints of existing different paths, where each endpoint hasorin its coordinate. The recursion of the DP
is describedjust by summing up all possible combinations of these pattems. We treat it by dividingthem into three cases, one of which has two subcases: (a) a set of base cases; (b) a case in whichis added as the first point whose y-coordinate is, and (bl) as an isolated vertex, or (b2) as tobe connected to an existing path; (c) all the other$(\vec{h};\vec{v};J)$$z(\mathcal{P})=(\vec{h};\vec{v};\vec{d})$$\mathcal{P}$$f(f, (\vec{h};\vec{v};\vec{d}))$$f(f, (\vec{h};\vec{v};\mathcal{J}))$$=|\{\mathcal{P}|\mathcal{P}\in P(f), z(SP)=(\vec{h};\vec{v};i)\}|$$f(n, (\vec{h};\vec{v};\vec{d}))\geq 1$$(\vec{h};\vec{v};\vec{d})$$\vec{h},\vec{v}$$\ell \mathscr{V}$$0$$C_{\ell-1}$$t_{\ell}$$t_{\ell}$$y(t_{l})$$x(t_{l})$Figure 5: An example case of the DP.

Timing analysis. We first count possible combinations of arguments for $f$ . Since varies from to, there arepossible values. All of
andelements,
each of which can have $O(n)$havepossible valpossible values, and therefore
ues in all. To compute a single value of $f$ , it requires $O(n^{4})$ lookups of previously computed vallookups
ues of $f$ in case (c), whileand check-sums in cases (bl) and (b2), which isgreater than $O(n^{4})$ . Therefore, the total mnning$f$$\Theta(n)$

$n$

$0$

$\vec{d}$$\vec{h},\vec{v}$$\Theta(c^{2})$$O(n^{c^{2}})$$O(n^{3c^{2}})\cross O(n^{2})$time for this DP is$O(n^{6c^{2}+3})=n^{O(c^{2})}$, which is polynomial in
is a constant.

$\Theta(n)\cross O(n^{3c^{2}})\cross O(n^{3c^{2}+2})=$
$n$

when

$c$

Since the role of colors and numbers are symmetric in UNO games, we have the following results.
Theorem 6 UNO-I is in
if (the number of
numbers) or (the number of colors) is a constant.
$P$

$b$

$c$

$t_{\ell}$$y(t_{e})$cases.

Now we can give the DP formula for computing. We just explain the idea of
the DP by illustrating one of the cases appearing
in the DP in Fig. 5. In this example, consider asubpath in a graph induced bywhose two endpoints have and in their x-coordinates. It will
be counted in. Then this subpath can be generated by adding point to connect to two paths in$f(f;(\vec{h};\vec{v};\vec{d)})$$C_{l}$$x_{}$

4 Uncooperative UNO
In this section, we deal with the uncooperative
version of UNO. Especially, we show that it is intractable even for two player’s case. For this purpose, we consider the following version of GENERALlZED GEOGRAPHY, which is played by two play-ers.

$x_{j}$$h_{\{r_{J}7}$$t_{\ell}$

GENERALIZED GEOGRAPHY
Instance: a directed graph, and a token

54
placed on an initial vertex.
Question: a tum is to move the token toan adjacent vertex, and then to remove
the vertex moved from from the graph.
Player 1 and 2 take tums, and the firstplayer unable to move loses. Determine
the loser.

Figure 6: Split a vertex into two edges so that edges
correspond to cards.

$-$

It is well-known that GENERALIZED GEOGRAPHY is
PSPACE-complete [7], and a stronger result ispresented.

Theorem 7 [7] GENERALIZED GEOGRAPHY for bipartite graphs is PSPACE-complete.
Now we show the hardness result for UNCOOP-ERATIVE $UNO-2$ .

Theorem 8 UNCOOPERATIVE UNO-2 is PSPACEcomplete.
Proof. Reduction from GENERALIZED GEOGRAPHY
for bipartite graphs (GG-B).
with $V(G)=$Let (directed) bipartite graph$X\cup Y$ be an instance of GG-B, where
and are$r(\inX)$
two partite sets, and let
be an initial vertex.
To constmct a corresponding UNCOOPERATIVE UNO2 instance, we first transform into another graph
$G’$
where
$G$

$X$

$Y$

$G$

$V(G’)=\{u_{s}, u_{t}, u_{c}|u\in V(G)\}$,$E(G’)=\{(u_{t}, u_{c}), (u_{c}, u_{s})|u\in V(G)\}$(Fig. 6). By constmction, we can confirm that $G’$is a bipartite graph with $V(G’)=X’\cup Y’$ , where
and $Y’=\{u_{s},$$u\in Y\}\cup\{u_{c}|u\in X\}$ . We let $\mu=r_{t}(\in X’)$ be an
initial vertex. It is easy to confirm that player 1
can win the game GG-B on if and only if theplayer wins on $G’$ . Then we prepare card setsfor players $i(=1,2)$ by$u_{l}|$$G$$C_{i}$$C_{1}=\{(x, e), (e,y)|e=(x,y)\in E(G’), x\in X’,y\in Y’\}$$\cup\{(e, e)|e=(y, x)\in E(G’), x\in X’,y\in Y’\}$ ,$C_{2}=\{(y,e), (e, x)|e=(y,x)\in E(G’), x\in X’,y\in Y’\}$$\cup\{(e, e)|e=(x,y)\in E(G’), x\in X’,y\in Y’\}$.

This means that we prepare three cards for eacharc in $E(G’)$ , one for player and two for player$e$$3-i$ (Fig. 7).

$i$$(e, e)_{2}$$(x, e)_{1}$$y$$(e,y)_{1}$$(x, e)_{2}$$(e,y)_{2}$–$x$$(e, e)_{1}$$y$Figure 7: Prepare three cards $(x,e)_{1},$ $(e,e)_{2}$ andfor an arc $e=(x,y)$ , and three cards $(e,y)_{2},$ $(e,e)_{1}$ andfor an arc $e=(y,x)$ .
$(e,y)_{1}$$(x, e)_{2}$Now we show that player 1 can win in an UNC00PERATlVE UNO-2 instance if and only if player 1
can win in an GG-B instance $G’$ and . To show
this, it suffices to show that any feasible playing
sequence by players 1 and 2 in an GG-B instancecorresponds to a feasible discarding sequence altematively by players 1 and 2 in the corresponding
UNCOOPERATTVE UNO-2 instance, and vice versa.
Suppose a situation that player 2 has just discarded a card. The discarded card belongs to either one of the following five cases: (i) $(e, x)$ for$e=(y, x)$ , (ii) $(y, e)$ for $e=(y, x)$ , (iii) $(e, e)$ for$e=(x,y)$ . Among those, for cases (ii) and (iii),
since player 1 starts the game (player 1 always
played before player ’s tum), there exists exactly
one card (outgoing arc) that matches the one discarded by player 2 from the end vertex of the arc
corresponding to the card. This forces to traverse$G’$ along the directed arc (in forward direction),
which implies to remove corresponding end vertex from $G’$ . The only case we have to care about
is case (i), where there may be multiple choices forplayer 1. In this case, once player 1 discarded oneof match cards, the player will never play anothermatch card afterwards, since the only card that canbe discarded immediately before it has played andused up. This implies that vertex is removed
from $G’$ . (The argument is symmetric for player 1
except that the initial card is specified.)
Now we verify that UNCOOPERATIVE UNO-2 is in
PSPACE. For this, consider a search tree for UNC00PERAFlVE UNO-2, whose root is for player 1 andevery node has outgoing arcs corresponding to
$s’$

$2$

$U\{(u_{s}, v_{t})|(u, v)\in E(G)\}$$X’=\{u_{s}, u_{t}|u\in X\}U\{u_{c}|u\in Y\}$

$x$

$x$

55
each player’s possible choices. Since the numberof total cards for the two players is , the numberof choices at any tum is $O(n)$ and since at least
one card is removed from either of the player’s
card set, the number of depth of the search tree isbounded by $O(n)$ . Therefore, it requires polynomial space with respect to the input size. Thus theproof is completed.
$n$$\square$Corollary 9 UNCOOPERATIVE UNO-2 is PSPACEcomplete even when the number of cards of two

players are equal.

$|C_{2}|-|C_{1}|$$C_{2}$$r’(=r_{t})$We deeply appreciate Nicholas J. A. Harvey at
University of Waterloo, Canada, for fmitful discussions and valuable comments with his deep insight at the early stage of this manuscript.

References[1]

A. A. Bertossi. The edge Hamiltonian path problem is NP-complete. Information Processing Letters 13, 157-159 (1981).

[2] E. D. Demaine. Playing games with algorithms:

Proof. Similar arguments to the ones in the proofof Corollary 2 can work. Let $M$ be an integer
greater than any label included in vertices andarcs, appearing in the proof of Theorem 8. Now
if $|C_{2}|<|C_{1}|$ , add $|C_{1}|-|C_{2}|$ cards $(M, M)$ that will
not be used at all to . If $|C_{1}|<|C_{2}|$ , add
cards $(M+1, M+1)$ and a single card $(M+1, M)$ to, and a single card $(M, r_{t})$ to, to start at vertex$C_{1}$

Acknowledgments$C_{2}$

after playing all these dummy cards.

Algorithmic combinatorial game theory. Lecture

Notes in Computer Science, Vol. 2136, 18-32,

Springer (2001).
[3] 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.
[4] S. Even and R. E.
. A combinatorial problem which is complete in polynomial space. .
$Ta\dot{\eta}an$$J$$ACM23,7]\alpha-719$ (1976).

$\square$

W. Frydrych and Z. Skupie\’{n}. Non-traceabilityof large connected claw-free graphs. Journal ofGraph Theory 27, 75-86 (1998).
[6] R. Li. Finding Hamiltonian cycles in {quasi-claw,$K_{1,5}+e\}$ -free graphs with bounded Dilworth
numbers. Discrete Mathematics 309, 2555-2558[5]5 Concluding Remarks
In this paper, we focused on UNO, the well-known
card game, and gave two mathematical models forit; one is cooperative (to make a specified playerwin), and the other is uncooperative (to decide theplayer not to be able to play). As a result of analyzing their complexities, we showed that these
problems are difficult in many cases, however, we
also showed that a single-player’s version is solvable in polynomial time under a certain restriction.
As for an obvious future work, we can try gaining speedup in dynamic programming for UNO1 with constant number of colors by better utilizing its geometric properties. In this direction,
it may be quite natural to ask if $U_{N}o-I$ is fixedparameter tractable. Another probable direction is
to investigate UNO-I graphs from the structural
point of view, since they form a subclass of clawfree graphs and seem to have interesting properties
by themselves. It is also quite probable to modify
our models more realistic, e.g., to take draw pile
into account (as an additional player), to make all
players’ cards not open, and so on.

$K_{1,5},$(2008).
[7]GO is
D. Lichtenstein and M. Sipser.
polynomial-space hard. J. $ACM27,393-401$(1980).

Mathematical Games: The
Entire Collection of his Scientific American
Columns. The Mathematical Association ofAmerica (2005).
[9] M. R. Garey, D. S. Johnson and R. E.
an.
The planar Hamiltonian circuit is NP-complete.
SIAM Journal of Computing 5, 704-714 (1976).
[10] M. R. Garey, D. S. Johnson. Computers andIntractability: A Guide to the Theory of NPCompleteness. W. H. Freeman and Company[8] M. Gardner.

$Ta\dot{\eta}$(1979).
[11] R. A. Heam and E. D. Demaine. Games, Puzzles,
and Computation. A. K. Peters (2009).