# the_complexity_of_playing_durak__0d362616.pdf

The Complexity of Playing Durak

Edouard Bonnet Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary,

bonnet.edouard@sztaki.mta.hu

Durak is a Russian card game in which players try to get rid of all their cards via a particular attack/defense mechanism. The last player standing with cards loses. We show that, even restricted to the perfect information two-player game, finding optimal moves is a hard problem. More precisely, we prove that, given a generalized durak position, it is PSPACE-complete to decide if a player has a winning strategy. We also show that deciding if an attack can be answered is NP-hard.

1 Introduction

The computational complexity of games is a fruitful research topic which started to formalize in the late seventies [Schaefer, 1978]. From an AI perspective, it offers an insight into what may and may not be computed efficiently in the process of solving a game. The complexity of games has been and is still extensively studied, giving rise to a few tractability results, such as solving in polynomial time NIM [Bouton, 1901] and SHANNON EDGE SWITCHING GAME [Bruno and Weinberg, 1970], and a series of intractability results. For instance, HEX [Reisch, 1981], OTHELLO [Iwata and Kasai, 1994], AMAZONS [Furtak et al., 2005; Hearn and Demaine, 2009], and HAVANNAH [Bonnet et al., 2013a] are PSPACEcomplete, while CHESS (without fifty-move rule) [Fraenkel and Lichtenstein, 1981], GO (with Japanese ko rules) [Robson, 1983], and CHECKERS [Robson, 1984], are EXPTIMEcomplete.

That list suggests that the computational complexity of board games is relatively well understood. The main motivation of this paper is to go towards a similar understanding for card games. Indeed, although card games are arguably as popular as board games, far less is known concerning their complexity. We only know of a handful of results mostly on trick-taking card games. Bridge (or whist) with two hands and a single suit, or with two hands and mirror1

The author is supported by the ERC grant PARAMTIGHT: Parameterized complexity and the search for tight complexity results , no. 280152.

1A suit is said mirror whenever both players have the same number of cards in it.

suits can be solved in polynomial time [Kahn et al., 1987; W astlund, 2005a; 2005b]. Some generalizations of bridge with more hands were proven PSPACE-complete [Bonnet et al., 2013b]. Finally, the complexity of problems linked to the games of UNO [Demaine et al., 2010] and SET [Lampis and Mitsou, 2014] has been studied.

Here, we wish to pursue this line of works by investigating the complexity of durak whose game mechanism is not based on taking tricks. Durak is a two to six-player card game intensively played in Russia and East European countries. Durak is the Russian word for fool which designates the loser. There is no winner in durak, there is just a loser: the last player standing with cards. We sketch a simplified version2 of the rules for two players and without trumps.

The game is played with 36 cards, by keeping the cards from the sixes (lowest cards) to the aces (highest cards) in a standard 52-card deck. Both players, let us call them P and O, are dealt a hand of six cards and their goal is to empty their hand before the opponent does. The remaining cards form the pile. The game is made of rounds. A designated player, say P, leads the first round by playing any card c of his hand. In this round, P is the attacker, O is the defender, and c is the first attacking card. The defender can skip, at any time. In that case, the defender picks up all the cards played during the round (by both players) and puts them into his hand; then, the attacker remains the attacker for the next round. The defender can also defend the current attacking card by playing a higher card in the same suit. Each time his opponent defends, the attacker can (but is not forced to) play an additional attacking card (up to a limit of six cards) provided it has the same rank as a card already played during the round (by either himself or his opponent). If the defender does defend all the attacking cards played by the attacker, all the cards played during the round are discarded and the defender leads the next round, thereby becoming the new attacker. After each round, any player with less than six cards, draws cards in the pile until he reaches the total of six.

In fact, we will consider that the pile is empty and that the two players have perfect information. Why do we make those assumptions? In durak, one does not win but has to avoid losing. While the pile is not empty, or while there are

2For a full description of the rules of Durak, see http://www. pagat.com/beating/podkidnoy durak.html

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

three players or more still in the game, the risk of quickly losing is relatively weak. This is one motivation for focusing on the two-player game with an empty pile. Now, from his hand and the cards played and discarded so far, a player can infer the hand of his opponent, yielding perfect information. More importantly, we almost exclusively prove negative results, and our hardness proofs do not require more than two players, nor a non empty pile, nor trumps.

After precising the notations, the vocabulary and the rules of durak in Section 2, we show that deciding if one player can defend any attack is NP-hard, in Section 3. The main result of the paper is the PSPACE-hardness of two-player perfect information durak and is presented in Section 4. Our reduction (from 3-TQBF) requires the introduction of several notions: weaknesses, well-covered weaknesses, and strong suits. We believe that those notions can be of importance in designing good artificial players for durak.

2 Preliminaries

For any integers x 6 y, [x, y] := {x, x+1, . . . , y 1, y} and [x] := [1, x]. A card is defined by a suit symbol sj and an integer i called rank, and is denoted by (sj, i). A hand is a set of cards. Example 1. h1 = {(s2, 1), (s3, 1), (s3, 5), (s4, 1), (s5, 3), (s5, 4), (s6, 5)} is a hand. Card (s2, 1) has rank 1 in suit s2.

Definition 1. A durak position P = hh(P), h(O), L, yi is given by two hands h(P) and h(O) of P and O, an indicator L 2 {P, O} of who leads the next round (equivalently, whose turn it is) and a threshold y, that is the maximum number of attacking cards allowed in a round.

Rules. Relation defines a partial order over the cards by: for any suit sj and any i1, i2 2 [r], (sj, i1) (sj, i2) iff i1 6 i2. If c1 c2 and c1 6= c2, we write c1 c2.

A game from an initial position P = hh(P), h(O), L, yi is composed of rounds that are themselves composed of moves. If h(P) = ; or h(O) = ; the game ends, the player still having cards loses, and his opponent wins3. We assume that P is the current attacking player (i.e., L = P). If c1, c2, . . . cp is the list of attacking cards played by P, so far, and d1, d2, . . . dp 1 the list of defending cards played by O then p 6 y, and for each i 2 [p 1], ci di and ci+1 has the same rank as at least one card in {c1, d1, . . . , ci, di}.

O can skip. In that case, we say that O takes the cards. P can add extra attacking cards cp+1, . . . , cq (with p + 1 6 q 6 y) provided that they are of the same rank as a card in {c1, d1, . . . , cp 1, dp 1, cp}. The next position is hh(P) \ {c1, . . . , cq}, h(O) [ {c1, . . . , cq}, P, yi.

O can also try to defend by playing a card dp such that cp dp. In that case, P can continue the attack (if p < y) or skips. If the attacker P skips, the next position is hh(P) \ {c1, . . . , cp}, h(O) \ {d1, . . . , dp}, O, yi. The cards played during the round are discarded, O has defended until the end, and O takes the lead. When a player plays a series of attacking cards that cannot be defended by the opponent, we say that he gives those cards to his opponent.

3A draw occurs if h(P) = h(O) = ;

1 2 3 4 5 6 7

s2 s3 s4 s5 s6

Figure 1: The geometric representation of position h{(s2, 4), (s2, 5), (s3, 3), (s3, 6), (s3, 7), (s4, 2), (s5, 1), (s5, 5), (s5, 6), (s6, 2), (s6, 7)}, h1, P, 1i.

Generalized durak. In generalized durak, there are s suits and the ranks range from 1 to r. The threshold poses some questions. It seems sound that, in a generalization of the game with an unbounded number of suits and ranks, the number of moves within a round is not limited by a constant. Therefore, as a part of the instance, the threshold should be allowed to grow. Besides, it does not make sense to impose that r, s, and y satisfy a constraint that is satisfied by r = 9, s = 4, y = 6 since there is no canonical such constraint. In case y > rs, the threshold cannot come into play, and we denote its value as 1.

Algebraic notation. We write fragments of game, called variations or continuations in the following way. A move is a card, the defensive skip , or the attacking skip ". Pairs of an attacking card and its defensive card are separated by commas. The extra attacking cards played after the defender skips are written to the right of symbol . Rounds are separated by semicolons.

Geometric representation. Each card (sj, i) 2 h(P) is represented by a black disk in (i, j); each card (sj, i) 2 h(O) is represented by a circle in (i, j) (see Figure 1). In the following sections, the suits are indexed by symbols rather than integers and the columns are displayed in a convenient order. Observe that permuting the columns of the representation preserves the position.

Example 2. P has a winning strategy in the position of Figure 1. He can play (s4, 2) (s6, 2); and after both (s3, 3) ; or (s3, 3)(s3, 5), (s5, 5) ; P gives all his cards but (s5, 1) by increasing ranks and finish with (s5, 1). This process will be generalized in Lemma 1.

3 On Defending an Attack

Defending until the end if possible, and taking the first attacking card otherwise, constitutes a decent heuristic for the defender. Unfortunately, we show that deciding if a defense is possible is already a hard problem.

Theorem 1. Given a durak position P, deciding if P can defend any attack of O until the end is NP-hard.

Proof. We reduce from 3-SAT. Let C = {C1, . . . , Cm} be any instance of 3-SAT, where each Ci is a 3-clause over the

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

sx1 sx2 sx3 sx4 sx5 sx6s C1s C2s C3s C4s C5s C6s C7s C8

Figure 2: The durak position P for the instance {x1 _ x3 _ x5, x2 _ x4 _ x6, x3 _ x4 _ x5, x1 _ x2 _ x4, x3 _ x5 _ x4, x2 _ x3 _ x6, x1 _ x2 _ x3, x5 _ x1 _ x6}.

set of variables X = {x1, . . . , xn}. We construct a durak position P = hh(P), h(O), O, 1i with n + m suits, 2n + 3 ranks, and 3n + 5m cards in total (O has n + 3m cards and P has 2n + 2m cards) such that C is satisfiable iff P can defend until the end any attack of O. Let r : {x1, x1, x2, x2, . . . , xn, xn} ! [2, 2n + 1] such that r(xi) = 2i and r( xi) = 2i + 1 for all i 2 [n], and l : [2, 2n + 1] ! {x1, x1, x2, x2, . . . , xn, xn} be the inverse function.

For each variable xi (i 2 [n]), we devote a suit sxi where O has the card (sxi, 1) and P has the two cards (sxi, 2i) and (sxi, 2i+1). For each clause Cj = l1_l2_l3, we devote a suit s Cj where O has the three cards (s Cj, r(l1)), (s Cj, r(l2)), and (s Cj, r(l3)), while P has the two cards (s Cj, 2n+2) and (s Cj, 2n + 3). This ends the construction (see Figure 2 and Figure 3).

First, we may observe that if O starts the attack with a card (s Cj, u), the defense is easy since P can follow this family of variations: (s Cj, u)(s Cj, 2n+2), (s Ck1 , u)(s Ck1 , 2n+ 2), (s Ck2 , u)(s Ck2 , 2n + 2), . . . (s Ckh , u)(s Ckh , 2n + 2), " where each ki (i 2 [h]) is the index of a clause where literal l(u) appears. The only remaining attempt for O is to start attacking with a card (sxi, 1), for some i 2 [n].

If C is satisfiable, we fix a satisfying assignment a : X ! {>, ?}. Symbol > (respectively ?) is interpreted as setting the variable to true (respectively false). P can defend the attack in the following way. On each attacking card (sxi, 1) (i 2 [n]), P plays (sxi, 2i + 1) if a(xi) = > and plays (sxi, 2i) if a(xi) = ?. Now, in each suit s Cj, O can attack with at most two cards, and P can defend with (s Cj, 2n + 2) and (s Cj, 2n + 3). Indeed, if there is a suit s Cj where O can play his three cards of rank, say, u1, u2, and u3, then no literal among l(u1), l(u2), and l(u3) would be set to true by assignment a, so the clause Cj would not be satisfied.

If C is not satisfiable, no assignment a : X ! {>, ?} satisfies every clauses. In particular, after O attacks with all the cards (sxi, 1) (i 2 [n]) and P has to defend with (sxi, ui)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

sx1 sx2 sx3 sx4 sx5 sx6s C1s C2s C3s C4s C5s C6s C7s C8

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

sx1 sx2 sx3 sx4 sx5 sx6s C1s C2s C3s C4s C5s C6s C7s C8

Figure 3: After the continuation (sx1, 1) (sx1, 3), (sx2, 1) (sx2, 5), (sx3, 1) (sx3, 6), (sx4, 1) (sx4, 8), (sx5, 1) (sx5, 11), (sx6, 1) (sx6, 12), corresponding to the truth assignment x1 >, x2 >, x3 ?, x4 ?, x5 >, x6 ?, P can defend until the end.

(ui 2 {2i, 2i + 1}), the assignment defined by a(xi) = > if ui = 2i + 1 and a(xi) = ? if ui = 2i, does not satisfy some clause Cj. Thus, P has played cards of rank r(l1), r(l2), and r(l3) where Cj = l1 _ l2 _ l3. Hence, O can attack with the three cards (s Cj, r(l1)), (s Cj, r(l2)), and (s Cj, r(l3)), and P can not defend, since he has only two cards in the suit s Cj.

4 On Playing Optimally

Proposition 1. Given a durak position P, deciding if P has a winning strategy is in PSPACE.

Proof. We have to show that the length of a game is polynomially bounded by the size of the instance, or equivalently by the total number n of cards in P. Then, we can conclude by doing a depth-first minimax search. A player cannot have the lead on n consecutive rounds. Indeed, when a player keeps the lead, at least one card is transferred, at each round, from his hand to the hand of his opponent. So, if a player keeps the lead for n 1 consecutive rounds, he wins. When the lead goes from a player to his opponent, at least two cards are discarded. Thus, a game cannot contain more than (n 1)n

2 rounds. A round lasts at most n + 1 moves, so the game length is bounded by (n 1)n(n + 1)/2 = O(n3).

We now need some extra definitions and observations.

Definition 2. A weakness for player P is a rank i 2 [r] satisfying the two following conditions: (1) h(P) contains at least one card of rank i, and (2) for each suit sj with (sj, i) 2 h(P), there is a rank i0 > i such that (sj, i0) 2 h(O).

Informally, P has each of his cards of rank i dominated by a card of O. The set of cards of rank i in h(P) is also called weakness and each card of the set is called weakness card. A rank i which is not a weakness for P, or the set of cards of rank i in h(P) is called a non weakness (for P).

Assuming that the threshold y is greater than the total number of cards of rank i, for any i 2 [r], (we will refer to this assumption as (H) in what follows) we may observe that player P, at his turn, can give all his cards of rank i to O, provided that i is a non weakness for P. Indeed, by definition, there is

a suit sj such that (sj, i) 2 h(P) and no card c 2 h(O) satisfies (sj, i) c. Thus, O cannot defend this attack. Therefore, we can show the following.

Lemma 1. Under (H), if P, at his turn, has only one weakness i, then he has a winning strategy.

Proof. If i0 is a non weakness for P, and P gives to O all his (non weakness) cards of rank smaller than i0, then i0 is still a non weakness for P in the resulting position. So, P wins by giving all his non weaknesses to O by increasing ranks and finally plays all his cards of rank i.

Definition 3. A strong suit for player P is a suit sj where he has at least one card and O has none.

We observe that the rank of any card in a strong suit of P is a non weakness for P. We say that P can win by attacking only if he has a winning strategy such that O can never take the lead. Example 3. Let P = hh(P) = {(s1, 1), (s2, 2)}, h(O) = {(s1, 2), (s2, 1), (s2, 3)}, P, 1i. P can win by attacking only due to the variations: (a)(s1, 1)(s1, 2), (s2, 2)(s2, 3), "; (b)(s1, 1)(s1, 2), (s2, 2) ; (c)(s1, 1) ; (s2, 2)(s2, 3), "; and (d)(s1, 1) ; (s2, 2) ;. Note that if O had the lead in P, then he would win by Lemma 1 since he only has 1 as a weakness.

The following lemma is very useful to reduce the number of potentially good first attacking card. Intuitively, it says that if you cannot win by attacking only, it is useless (and possibly harmful) to give cards to your opponent that he will be able to give you back when he will have the lead.

Lemma 2. Under (H), if P has a winning strategy but cannot win by attacking only, O has a card (sj, i) in a strong suit sj, and i is a non weakness for P, then P has a winning strategy that does not start the round with cards of rank i.

Proof. O can accept to take the set S of cards of rank i played by P. O will eventually get the lead back. By definition, P has no card in the strong suit sj of O. It implies that O has not been attacked in sj, so he has exactly the same cards in sj as in the initial position. In particular, (sj, i) 2 h(O) and O can give S back to P all his cards of rank i, making the first attack of P useless.

There is quite a lot of conditions in Lemma 2, and checking that P cannot win by attacking only, to know if the lemma applies, may be problematic. Therefore, we give a sufficient condition implying that a player cannot win by attacking only.

Definition 4. A well-covered weakness for P is a weakness i such that for each (sj, i) 2 h(P), there is a higher card (sj, i0) 2 h(O) and P has no card of rank i0.

Intuitively, if P attacks with a well-covered weakness, O can defend so that P cannot play any other attacking card at this round.

Lemma 3. If P has two well-covered weaknesses, O can prevent P from winning by attacking only.

Proof. Let i1 6= i2 be the two well-covered weaknesses for P. First, we remark that while P gives cards to O which are not of rank i1 or i2, they remain well-covered weaknesses.

(a) The gadget. (b) xi true. (c) xi false.

Figure 4: The existential gadget 9xi.

So, O takes any cards of rank i /2 {i1, i2} without trying to defend. At some point, P has to start an attack with cards of rank i1 or i2. In both cases, O can defend until the end, by definition of a well-covered weakness.

The proof of the following lemma is similar to the proof of Lemma 2 and therefore omitted.

Lemma 4. Under (H), if P has a winning strategy but cannot win by attacking only, then P has a winning strategy that does not start the round with the highest card of some suit.

Theorem 2. Given a durak position P, deciding if P has a winning strategy is PSPACE-complete.

Proof. It is in PSPACE by Proposition 1. We show that it is PSPACE-hard by a reduction from the PSPACE-hard problem QBF which remains so even if all the variables are quantified, the quantifiers alternate starting with 9 and ending with 8. This restricted problem is sometimes called 3-TQBF and consists of deciding whether 9x18x29x3 . . . 8xnφ(x1, x2, . . . , xn) is true or false, where φ is a conjunction of clauses with three literals. We fix a 3-CNF formula φ with m clauses C1, C2, . . . , Cm. We will build a durak position P = hh(P), h(O), P, 2(n + m + 1)i with 3n+16 ranks, 6m+ 11

2 n+8 suits, and 26m+ 29

2 n+24 cards4 such that = 9x18x29x3 . . . 8xnφ is true iff P has a winning strategy from the position P. For technical reasons that will become relevant later, we define 0 = 8x09x18x29x3 . . . 8xnφ0, where φ0 is the conjunction of the 2m clauses x0 _ C1, x0 _ C2, . . . , x0 _ Cm, x0 _ C1, x0 _ C2, . . . , x0 _ Cm. We denote x0 _ Ci by C0

i and x0 _ Ci by C00

i for all i 2 [m]. We observe that is true iff 0 is true, and φ0 is a conjunction of 4-clauses.

Existential quantifier gadget. For each odd i 2 [n], we encode 9xi by devoting four suits s1

i where P has four cards: (s1

i , oi), (s2

i , oi), (s3

i , oi + 1), and (s4

i , oi + 2) and O has four cards: (s1

i , oi + 1), (s2

i , oi + 2), (s3

i , oi + 3), and (s4

i , oi + 3). We set oi := 3i + 7. Figure 4a displays the geometric representation of the existential gadget and the two local outcomes if P decides to set xi to true (Figure 4b) or to set xi to false (Figure 4c).

Universal quantifier gadget. For each even i 2 [n] [ {0}, we encode 8xi by devoting three suits s1

i where P has three cards: (s1

i , oi), (s2

i , oi + 1), and (s3

i , oi + 2) and O has four cards: (s1

i , oi + 1), (s1

i , oi + 2), (s2

i , oi + 3), and (s3

i , oi+3) (see Figure 5). Again, we set oi := 3i+7. For the

4By the form of , integer n is always even.

(a) The gadget. (b) xi true. (c) xi false.

Figure 5: The universal gadget 8xi.

. . . . . .

. . . . . .

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

w s O s P s1,1

d . . . . . . s2

Figure 6: The initial durak position for the instance 9x18x29x38x4

V{x1 _ x2 _ x4, x1 _ x3 _ x4, x2 _ x3, x1 _ x3 _ x4}. The weaknesses are framed by dotted rectangles. P has 3 weaknesses and O has 2 weaknesses.

quantification 8x0 and only for this quantification, P is dealt an extra card (s1

0, 3n + 12).

Clause gadget. We define the rank r(l) of literal l as 3i + 8 if l = xi or 3i + 9 if l = xi. We denote by s(l) the suit wherein O has a card of rank r(l) in the gadget associated to the quantified variable xi with l 2 {xi, xi}. So, if xi is universally quantified, then s(xi) = s( xi) = s1

i while if xi is existentially quantified, then s(xi) = s1

i and s( xi) = s2

i . For each 4-clause C = l1 _ l2 _ l3 _ l4 of φ0, we devote a suit s C. Player P has the 4 cards (s C, r(l1)), (s C, r(l2)), (s C, r(l3)), and (s C, r(l4)) while O has the 5 cards (s C, 5) and (s C, k) for k 2 [3n+13, 3n+16].

Weaknesses and strong suits. We add a suit s O where player O has the cards (s O, k) for k 2 [8, 3n + 9] [ [3n + 13, 3n+16] and P has none, and a suit s P where player P has the cards (s P , k) for k 2 {1}[[8, 3n+9][[3n+13, 3n+16] and O has none. We add 2(n+m) suits s1,k

d (8k 2 [2(n+m)]) where P has (s1,k

d , 1) and O has (s1,k

d , 2), a suit s2

d where P has (s2

d, 3) and O has (s2

d, 4), a suit s3

d where P has (s3

d, 6) and O has (s3

d, 1), and a suit s4

d where P has (s4

d, 5). Finally, we add 2m suits sk

w (8k 2 [2m]), where P has the card (sk

w, 3n + 10) and O has the card (sk

w, 3n + 11).

The construction is now finished (see Figure 6) and P satisfies assumption (H). P has 3 weaknesses: 3, 7, and 3n+10; O has 2 weaknesses: 1 and 5. P has 2 well-covered weaknesses: 3 and 3n + 10, and O only one: 1.

Before going into the details, we give an outline of the proof. P has one weakness more than O and his only hope is to get rid of two weaknesses (7 and 3n + 10) before O takes the lead. To do so, P should start the attack with the lowest card in the gadget encoding the first quantified variable (namely, his weakness card of rank 7). O has to defend, and they slowly climb up from rank 7 to rank 3n + 10 passing through each quantifier gadget. In universal gadgets 8xi, O has two ways of defending: with a card of rank r(xi) or r( xi). In existential gadgets 9xi, P has two suits s1

i to continue the attack, but due to the threshold limit, he has to choose only one. So, P and O act as the existential and the universal player in QBF seen as a two-player game. At the next round, O has to get rid of his weakness of rank 5 and wins iff one clause of φ is not satisfied by their joint assignment.

P has to start the attack with (s1

0, 7). We first show that P has to start the attack with (s1

0, 7) with the idea of getting rid of the two weaknesses 7 and 3n + 10 in the same round. By Lemmas 2 and 4, the three other options are to start the attack with a card of rank 1, 3, or 3n + 10.

In case of the second or third option, O can defend until the end: (s2

d, 4), "; or (s1

w, 3n + 10)(s1

w, 3n + 11), . . . (s2m

w , 3n + 10)(s2m

w , 3n + 11), "; and then O wins with the following strategy, which we denote by S. Player O starts the next round with all his cards (s C, 5) for each clause C of φ0. P has to defend, since otherwise O leads the next round with a single weakness, so O wins by Lemma 1. In particular, P should defend the card (s C0

1, 5). The only way to do so is to play (s C0

1, r(l)) where l appears in C0

1. If l = x0 the winning continuation for O is (s C0

1, r(x0)), (s O, r(x0)) (s(x0), r(x0))(s C0

2, 5) . . . (s C00

m, 5); whereas, if l 6= x0 the variation is (s C0

1, r(l)), (s(l), r(l)) (s C0

2, 5) . . . (s C00

m, 5); and in both cases O leads the next round with only one weakness. Finally, starting an attack with a card of rank 1 cannot help P; O would just skip. Indeed, let S be the set of cards of rank 1 played by P and taken by O. Either S 6= {(s P , 1)}, and O can give all those cards back to P the next time he takes the lead; or S = {(s P , 1)}, but P could give this card to O any time he is the attacker.

P cannot play cards of s P . We show that during the first round starting with (s1

0, 7), P loses if he plays a card (s P , i). Assume P does. O has to take all the cards played during the round, in particular (s1

0, 7). 7 is a new weakness for O, but P has also 1 as a new weakness because he played (s P , i). So, each player has 3 weaknesses and P has still the lead. However, O wins in the following way. While P starts attacks with non weaknesses, O skips. Again, we observe that, as the position is, this step cannot create weaknesses for O. When P starts an attack with a weakness, O defends until the end. This is possible since 3 and 3n + 10 are well-covered

weaknesses, and P has 2(m + n) + 1 cards of rank 1, so he would be allowed to add at most 1 extra attacking card, due to the threshold 2(m + n + 1). One can check that O can always defend this card of rank i. Thus, O will take the lead at least twice. The first time O takes the lead, he attacks with (s1

0, 7). P has to defend, otherwise O wins thanks to strategy S. The second time, O is left with weaknesses 5 and 1, and wins with S.

O should defend until the end. We show that if P does not play a card of the suit s P during this first round, then O should defend until the end. Suppose O skips at some point. Player O takes in his hand the cards played during the round; in particular, the card (s1

0, 7) which is now a weakness card for O, since P has the card (s1

0, 3n + 12) that cannot have been played in the previous attack of P, for it is the only card with rank 3n + 12. P can win by playing (s2

d, 3) in the next round. O has to defend, since otherwise P is left with only one weakness 3n + 10 and wins by Lemma 1. So, the continuation is (s2

d, 4), ";. Now, O leads the round and has 3 weaknesses: 1, 5 and 7. Cards (s1

0, 7) and (s3

d, 1) are well-covered weakness cards for O. P can skip on all the attacks of O until one of these cards is played. Then, he defends and wins by Lemma 1, since O cannot give cards to P that would constitute weaknesses for P.

P and O simulates QBF. If P does not play all his cards of rank 3n + 10 during the first round, and O defends until the end, then O wins. O starts the next round with (s3

d, 1). P has to defend: (s3

d, 6), "; otherwise O wins by Lemma 1. Then, P has the lead, but O wins since he has only one weakness (5), P has two well-covered weaknesses (3 and 3n + 10), and P cannot give cards to O which would be new weaknesses for O. Besides, as P cannot play cards of the suit s P , one can check that O will be able to defend until the end (thanks notably to cards (s C, k) 2 h(O) for k 2 [3n + 13, 3n + 16]). So, P has to find a way of playing all his cards of rank 3n + 10. Therefore, due to the threshold 2(m + n + 1), P can only play one card of rank r(xi) 1 in each existential gadget 9xi. Thus, the first round should be of this form: (s1

0, r(σ(x0))), (si0

0 , r(σ(x0)))(si0

0 , r( x0) + 1), (si1

1 , r( x0)+1)(si1

1 , r(σ(x1))), (si1+2

1 , r(σ(x1)))(si1+2

1 , r( x1) +1), . . . (s1

n, r( xn 1))(s1

n, r(σ(xn))), (sin n , r(σ(xn))) (sin n , 3n + 10), (s1

w, 3n + 10)(s1

w, 3n + 11), . . . (s2m

w , 3n + 10)(s2m

w , 3n + 11), "; where for each even k (resp. odd k), σ(xk) 2 {xk, xk} corresponds to the literal that is set to true by O (resp. P), and ik 2 {1, 2} is the matching index. As in Figure 4 and 5, we interpret the card c of rank in {r(xi), r( xi)} played by O (and discarded at the end of the round) as setting xi to true if the rank of c is r(xi) and as setting xi to false if the rank of c is r( xi). Player O leads the next round. At this point, O has still his two weaknesses: 1 and 5; while P has only one weakness: 3.

If is false, O wins. We recall that and 0 are equivalent. Let us assume 0 is false. Then, O had a strategy in the first round ensuring that there is a clause C0

i = x0 _ l1 _ l2 _ l3

such that (s(l1), r(l1)), (s(l2), r(l2)), (s(l3), r(l3)) are still in h(O). O plays all his cards of rank 5. By Lemma 1, P has to defend. In particular, he has to defend on the card (s C0

i, 5). To do so, P can either play (s C0

i, r(x0)) or (s C0

i, r(lk)) for some k 2 {1, 2, 3}. In the former case, the continuation is (s C0

i, r(x0)), (s O, r(x0)) and O add as extra attacking cards all his cards of rank 5 and potentially his card (s1

0, r(x0)). In the latter case, the continuation is (s C0

i, r(lk)), (s(lk), r(lk)) and again, O gives all his cards of rank 5 to P. In both cases, O wins by Lemma 1.

If is true, P wins. Whichever cards O gives to P, P will not have additional weaknesses. Thus, if P can defend an attack of O until the end, P wins by Lemma 1 (provided that O has still at least one card left). This is equivalent to saying that if O has a winning strategy, he wins by attacking only. Let us show that O cannot win by attacking only. The last attack of O should be (s3

d, 6), "; while all his other cards have been previously given to P. At some point, O will have to play his weakness cards of rank 5. If O has already given (s O, r(x0)) and (s O, r( x0)) to P, prior to this attack, then P can defend: (s C0

1, r(x0)), . . . (s C0

m, r(x0)), (s C00

1 , 5) (s C00

1 , r( x0)) . . . (s C00

m, 5)(s C00

m, r( x0)), (s1

0, r(x0)) (s1

0, 3n + 12), ; (this is why we introduced the dummy variable x0) and P wins. So, we can assume that (s O, r0) is still in h(O) when O starts the attack with cards of rank 5, with r0 2 {r(x0), r( x0)}. As is true, P had a strategy in the first round such that, for each clause C0

i = x0 _ li

3 (8i 2 [m]), there exists ki 2 {1, 2, 3} satisfying (s(li

ki)) /2 h(O). Thus, P can defend in the following way: (s C0

1, 5) (s C0

k1)), . . . (s C0

km)), (s C00

1 , 5) (s C00

k1)), . . . (s C00

m, 5) (s C00

km)), and O, to continue the attack, has to play a card (s O, r(li

ki)) for some i 2 [m]. P takes all the cards played during this round. Now, O has a new well-covered weakness r0 since (s O, r0) (s O, r(li

0, 3n + 12), and O has no card of rank r(li

ki) nor 3n + 12. O has two well-covered weaknesses 1 and r0. So, by Lemma 3, O cannot win by attacking only, and by the previous remarks, O loses.

5 Perspectives

Our proof of PSPACE-hardness for two-player durak relies on a finite threshold. One could look for a reduction which does not use the threshold feature. We also leave as an open question if the seemingly very simple two-player durak with a single suit is solvable in polynomial time.

[Bonnet et al., 2013a] Edouard Bonnet, Florian Jamain, and

Abdallah Saffidine. Havannah and Twix T are PSPACEcomplete. In Computers and Games - 8th International Conference, CG 2013, Yokohama, Japan, August 13-15, 2013, Revised Selected Papers, pages 175 186, 2013.

[Bonnet et al., 2013b] Edouard Bonnet, Florian Jamain, and

Abdallah Saffidine. On the complexity of trick-taking card games. In IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, 2013. [Bouton, 1901] Charles L Bouton. Nim, a game with a com-

plete mathematical theory. The Annals of Mathematics, 3(1/4):35 39, 1901. [Bruno and Weinberg, 1970] J. Bruno and L. Weinberg.

A constructive graph-theoretic solution of the shannon switching game. Circuit Theory, IEEE Transactions on, 17(1):74 81, Feb 1970. [Demaine et al., 2010] Erik Demaine, Martin Demaine, Ryuhei Uehara, Takeaki Uno, and Yushi Uno. Uno is hard, even for a single player. In Fun with Algorithms, pages 133 144. Springer, 2010. [Fraenkel and Lichtenstein, 1981] Aviezri S. Fraenkel and

David Lichtenstein. Computing a perfect strategy for n n Chess requires time exponential in n. Journal of Combinatorial Theory, Series A, 31(2):199 214, 1981. [Furtak et al., 2005] Timothy Furtak, Masashi Kiyomi, Takeaki Uno, and Michael Buro. Generalized Amazons is PSPACE-complete. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 132 137, 2005. [Hearn and Demaine, 2009] Robert A. Hearn and Erik D.

Demaine. Games, Puzzles, and Computation. A K Peters, July 2009. [Iwata and Kasai, 1994] Shigeki Iwata and Takumi Kasai.

The othello game on an n n board is pspace-complete. Theoretical Computer Science, 123(2):329 340, 1994. [Kahn et al., 1987] Jeff Kahn, Jeffrey C. Lagarias, and

Hans S. Witsenhausen. Single-suit two-person card play. International Journal of Game Theory, 16(4):291 320, 1987. [Lampis and Mitsou, 2014] Michael Lampis and Valia Mit-

sou. The computational complexity of the game of set and its theoretical applications. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, pages 24 34, 2014. [Reisch, 1981] Stefan Reisch. Hex ist PSPACE-vollst andig.

Acta Informatica, 15:167 191, 1981. [Robson, 1983] John M. Robson. The complexity of Go. In

IFIP, pages 413 417, 1983. [Robson, 1984] John M. Robson. N by N checkers is exp-

time complete. SIAM J. Comput., 13(2):252 267, 1984. [Schaefer, 1978] Thomas J. Schaefer. On the complexity of

some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185 225, 1978. [W astlund, 2005a] Johan W astlund. A solution of twoperson single-suit whist. The Electronic Journal of Combinatorics, 12(1):R43, 2005.

[W astlund, 2005b] Johan W astlund. Two-person symmetric whist. The Electronic Journal of Combinatorics, 12(1):R44, 2005.