The Complexity of Playing Durak

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 mirror 1

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

1 A 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 version 2 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 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.

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

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.

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.

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 wins 3 . 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 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.

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

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 lhd. 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 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 sCj where O has the three cards (sCj ↪ r(l1)), (sCj ↪ r(l2)), and (sCj ↪ r(l3)), while P has the two cards (sCj ↪ 2n+2) and (sCj ↪ 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 (sCj ↪ u), the defense is easy since P can follow this family of variations: (sCj ↪ u)(sCj ↪ 2n+2)↪ (sCk1 ↪ u)(sCk1 ↪ 2n+ 2)↪ (sCk2 ↪ u)(sCk2 ↪ 2n + 2)↪ ▷ ▷ ▷ (sCkh ↪ u)(sCkh ↪ 2n + 2)↪ lhd 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 sCj , O can attack with at most two cards, and P can defend with (sCj ↪ 2n + 2) and (sCj ↪ 2n + 3). Indeed, if there is a suit sCj 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)

(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 (sCj ↪ r(l1)), (sCj ↪ r(l2)), and (sCj ↪ r(l3)), and P can not defend, since he has only two cards in the suit sCj .

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] sat-

isfying 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)↪ lhd; (b)(s1↪ 1)(s1↪ 2)↪ (s2↪ 2)⇤; (c)(s1↪ 1)⇤; (s2↪ 2)(s2↪ 3)↪ lhd; 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.

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 cards 4 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 C 0 i and ≻x0 _Ci by C 00 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 s1i , s2i , s3i , and s4i where P has four cards: (s1i ↪ oi), (s2i ↪ oi), (s3i ↪ oi +1), and (s4i ↪ oi +2) and O has four cards: (s1i ↪ oi + 1), (s2i ↪ oi + 2), (s3i ↪ oi + 3), and (s4i ↪ 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 s1i , s2i , and s3i where P has three cards: (s1i ↪ oi), (s2i ↪ oi + 1), and (s3i ↪ oi + 2) and O has four cards: (s1i ↪ oi + 1), (s1i ↪ oi + 2), (s2i ↪ oi + 3), and (s3i ↪ oi+3) (see Figure 5). Again, we set oi := 3i+7. For the quantification 8x0 and only for this quantification, P is dealt an extra card (s10 ↪ 3n + 12).

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

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) = s1i while if xi is existentially quantified, then s(xi) = s1i and s(≻xi) = s2i . For each 4-clause C = l1 _ l2 _ l3 _ l4 of φ0 , we devote a suit sC. Player P has the 4 cards (sC↪ r(l1))↪ (sC↪ r(l2))↪ (sC↪ r(l3)), and (sC↪ r(l4)) while O has the 5 cards (sC↪ 5) and (sC↪ k) for k 2 [3n+13↪ 3n+16].

Weaknesses and strong suits. We add a suit sO where player O has the cards (sO↪ k) for k 2 [8↪ 3n + 9] [ [3n + 13↪ 3n+16] and P has none, and a suit sP where player P has the cards (sP ↪ 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 s2d where P has (s2d ↪ 3) and O has (s2d ↪ 4), a suit s3d where P has (s3d ↪ 6) and O has (s3d ↪ 1), and a suit s4d where P has (s4d ↪ 5). Finally, we add 2m suits skw (8k 2 [2m]), where P has the card (skw ↪ 3n + 10) and O has the card (skw ↪ 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 s1i and s2i 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 (s10 ↪ 7). We first show that P has to start the attack with (s10 ↪ 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: (s2d ↪ 3)(s2d ↪ 4)↪lhd; or (s1w ↪ 3n + 10)(s1w ↪ 3n + 11)↪ ▷ ▷ ▷ (s2m w ↪ 3n + 10)(s2m w ↪ 3n + 11)↪lhd; and then O wins with the following strategy, which we denote by S. Player O starts the next round with all his cards (sC↪ 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 (sC01 ↪ 5). The only way to do so is to play (sC01 ↪ r(l)) where l appears in C 01 . If l = x0 the winning continuation for O is (sC01 ↪ 5)(sC01 ↪ r(x0))↪ (sO↪ r(x0)) ⇤ (s(x0)↪ r(x0))(sC02 ↪ 5) ▷ ▷ ▷ (sC00m ↪ 5); whereas, if l 6= x0 the variation is (sC01 ↪ 5)(sC01 ↪ r(l))↪ (s(l)↪ r(l))⇤ (sC02 ↪ 5) ▷ ▷ ▷ (sC00m ↪ 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= ¶(sP ↪ 1)♦, and O can give all those cards back to P the next time he takes the lead; or S = ¶(sP ↪ 1)♦, but P could give this card to O any time he is the attacker.

P cannot play cards of sP . We show that during the first round starting with (s10 ↪ 7), P loses if he plays a card (sP ↪ i). Assume P does. O has to take all the cards played during the round, in particular (s10 ↪ 7). 7 is a new weakness for O, but P has also 1 as a new weakness because he played (sP ↪ 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 (s10 ↪ 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 sP 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 (s10 ↪ 7) which is now a weakness card for O, since P has the card (s10 ↪ 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 (s2d ↪ 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 (s2d ↪ 3)(s2d ↪ 4)↪lhd;. Now, O leads the round and has 3 weaknesses: 1, 5 and 7. Cards (s10 ↪ 7) and (s3d ↪ 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 (s3d ↪ 1). P has to defend: (s3d ↪ 1)(s3d ↪ 6)↪lhd; 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 sP , one can check that O will be able to defend until the end (thanks notably to cards (sC↪ 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: (s10 ↪ 7)(s10 ↪ 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)↪ ▷ ▷ ▷ (s1n ↪ r(≻xn-1))(s1n ↪ r(σ(xn)))↪ (sin n ↪ r(σ(xn))) (sin n ↪ 3n + 10)↪ (s1w ↪ 3n + 10)(s1w ↪ 3n + 11)↪ ▷ ▷ ▷ (s2m w ↪ 3n + 10)(s2m w ↪ 3n + 11)↪lhd; 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, Owins. 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 C 0 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 (sC0 i ↪ 5). To do so, P can either play (sC0 i ↪ r(x0)) or (sC0 i ↪ r(lk)) for some k 2 ¶1↪ 2↪ 3♦. In the former case, the continuation is (sC0 i ↪ 5)(sC0 i ↪ r(x0))↪ (sO↪ r(x0))⇤ and O add as extra attacking cards all his cards of rank 5 and potentially his card (s10 ↪ r(x0)). In the latter case, the continuation is (sC0 i ↪ 5)(sC0 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 (s3d ↪ 1)(s3d ↪ 6)↪lhd; 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 (sO↪ r(x0)) and (sO↪ r(≻x0)) to P, prior to this attack, then P can defend: (sC01 ↪ 5)(sC01 ↪ r(x0))↪ ▷ ▷ ▷ (sC0m ↪ 5)(sC0m ↪ r(x0))↪ (sC00 1 ↪ 5) (sC00 1 ↪ r(≻x0)) ▷ ▷ ▷ (sC00m ↪ 5)(sC00m ↪ r(≻x0))↪ (s10 ↪ r(x0)) (s10 ↪ 3n + 12)↪⇤; (this is why we introduced the dummy variable x0) and P wins. So, we can assume that (sO↪ 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 C 0 i = x0 _ li1 _ li2 _ li3 (8i 2 [m]), there exists ki 2 ¶1↪ 2↪ 3♦ satisfying (s(liki )↪ r(liki )) ◁2 h(O). Thus, P can defend in the following way:

(sC01 ↪ 5) (sC01 ↪ r(l1k1 ))↪ ▷ ▷ ▷ (sC0m ↪ 5)(sC0m ↪ r(lm km ))↪ (sC00 1 ↪ 5) (sC00 1 ↪ r(l1k1 ))↪ ▷ ▷ ▷ (sC00m ↪ 5) (sC00m ↪ r(lm km ))↪ and O, to continue the attack, has to play a card (sO↪ r(liki )) for some i 2 [m]. P takes all the cards played during this round. Now, O has a new well-covered weakness r0 since (sO↪ r0) ≺ (sO↪ r(liki )), (s10 ↪ r0) ≺ (s10 ↪ 3n + 12), and O has no card of rank r(liki ) 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.