On the power of lookahead in single-player PuyoPuyo

Takenaga, Yasuhiko; Kikuchi, Sho; Quan, Hushan

doi:10.3233/ICG-210189

On the power of lookahead in single-player PuyoPuyo

Article type: Research Article

Authors: Takenaga, Yasuhiko^{; *} | Kikuchi, Sho^{; **} | Quan, Hushan^{; ***}

Affiliations: Department of Computer and Network Engineering, The University of Electro-Communications, Chofu, Tokyo, Japan

Correspondence: [*] Corresponding author. E-mail: [email protected].

Note: [**] Presently with Altech Corporation.

Note: [***] Presently with Dassault Systèmes K.K..

Keywords: Winning strategy, lookahead, PuyoPuyo, Tetris-like games

DOI: 10.3233/ICG-210189

Journal: ICGA Journal, vol. 43, no. 2, pp. 102-113, 2021

Published: 8 November 2021

Get PDF

Abstract

PuyoPuyo is one of the Tetris-type games, which is dealt with as a single-player game in this paper. The player has a winning strategy if the player can keep playing the game infinitely on a gameboard of a constant height. In this paper, we consider how lookahead of input pieces affects the existence of winning strategies in PuyoPuyo, and show conditions that the player cannot win even with lookahead. First, we show the number of colors sufficient to make the player lose on the gameboard of width w when the number of lookahead pieces is m. Next, we show that ten and twenty-six colors are sufficient to make the player lose on the gameboards of width two and three, respectively, no matter how large the number of lookahead pieces is.

1.Introduction

Tetris is one of the most popular video games, and many Tetris-type games have been developed. In Tetris-type games, the player manipulates the game pieces falling from the top of the gameboard and places them on the bottom of the gameboard or the other game pieces. Pieces disappear if the condition defined in each game is satisfied. The player loses when game pieces are piled up to the top of the gameboard. PuyoPuyo (also known as Puyo Pop) (SEGA, n.d.) is one of the Tetris-type games which is played worldwide. In PuyoPuyo, a piece consists of two puyos, each of which has a color. Puyos on the gameboard disappear when four or more puyos of the same color are connected. PuyoPuyo is remarkably different from Tetris (and related tiling problems, e.g., Merlini et al., 2002) at the point that two puyos in a piece are separated so that no blank cells exist below a puyo. Due to the characteristic, chain reactions may occur in PuyoPuyo, which makes it hard to analyze the game. We consider PuyoPuyo as a single-player game, though it is usually a two-player game. The single-player PuyoPuyo can be regarded as a two-player game played between the player and the adversary who gives inputs attempting to make the player lose.

On the complexity of Tetris-type games, several problems on Tetris and PuyoPuyo are proved to be NP-complete (Asif et al., 2019; Breukelaar et al., 2004; Demaine et al., 2017; Matsukane and Takenaga, 2006; Muta, 2005). Also, some (un)decidability results and constructibility of configurations are shown on Tetris in Hoogeboom and Kosters (2004a, 2004b). In the above intractability results, it is assumed that the whole sequence of input pieces is given in advance. However, the player cannot know the whole input in real games. The strategy of the player who cannot know the upcoming pieces is regarded as an online algorithm.

On the strategy of Tetris-type games, we consider that the player has a winning strategy if the player can play the game infinitely using a constant number of rows. That is, if the player does not have a winning strategy, the player cannot win for any gameboard of a fixed height.

Winning strategies of Tetris are shown for several subsets of game pieces, and the non-existence of a winning strategy is proved for some other subsets when input pieces are decided knowing how the previous pieces are placed (Brzustowski, 1992). This result was improved in Burgiel (1997) to show that there exists an input sequence for which the player has no winning strategy even if the player knows the input sequence. The strategy of Tetris is also discussed in Baccherini and Merlini (2007); Şimşek et al. (2016). On a game called Luminus, a condition that the player can keep playing forever is shown in Aloupis et al. (2007).

On PuyoPuyo, different from the other games mentioned above, the difficulty of the game changes according to the number of colors used in input pieces. Thus, the number of colors can be considered as a parameter. In Takenaga and Shimada (2016), conditions for the existence and non-existence of a winning strategy are studied on single-player PuyoPuyo when the width of the gameboard and the number of colors can be changed. The main results of Takenaga and Shimada (2016) are as follows.

Theorem 1.

When the number of colors of puyos is k, the player has a winning strategy if the width of the gameboard is greater than or equal to k(k−1)2+1.

Theorem 2.

On the gameboard with width w, the player can make no puyo disappear if the number of colors k satisfies the following:

k⩾2(w=1)4(w=2)3w−4(w⩾3)

On Tetris-type games, the player can usually know a few pieces that appear on the gameboard following the one presently on the gameboard. We call them lookahead pieces. However, lookahead pieces are not considered in the above results on the strategy of PuyoPuyo (Takenaga and Shimada, 2016).

In this paper, we consider how lookahead affects the existence of a winning strategy in single-player PuyoPuyo. Lookahead is advantageous to the player and the advantage becomes larger as the number of lookahead pieces increases. However, even with lookahead, the player cannot win if the number of colors is sufficiently large.

We first show the condition that the player loses using the number of lookahead pieces as an additional parameter. In this result, the adversary can choose the input according to the placements of previous pieces. The result also improves Theorem 2 when the number of lookahead pieces is zero. Second, we consider the case with infinite lookahead. In other words, the player knows the whole input sequence in advance. If the number of colors is too large, it seems that the player cannot win no matter how large the number of lookahead pieces is. In this paper, we show that ten and twenty-six colors are sufficient to make the player lose on the gameboards of width two and three, respectively.

The rest of the paper is organized as follows. In Section 2, we describe the rules of PuyoPuyo. In Section 3, we consider the case that the number of lookahead pieces is finite and show the number of colors sufficient to make the player lose. In Section 4, we deal with the case of infinite lookahead and show that the player loses on the gameboard of width two or three when the number of colors is sufficiently large. Section 5 concludes this paper.

2.Rules of PuyoPuyo

In this section, we explain the rules of single-player PuyoPuyo with lookahead. The gameboard is a rectangular grid of width w. A puyo has a color and occupies one cell of the grid. Puyos appear on the gameboard as a piece which consists of two connected puyos. Pieces fall from the top of the gameboard one by one.

A piece can be moved horizontally and be rotated until one of the puyos reaches a cell just above the one already occupied by another puyo or a cell just above the bottom of the gameboard. When one of the puyos of a piece has reached the cell just above a puyo and there exist blank cells under the other puyo of the piece, the puyos of the piece are separated and the latter keeps falling. The separated puyos cannot be moved horizontally.

In addition to the piece falling on the gameboard, the player can see some pieces called lookahead pieces. The i^th lookahead piece is the i^th piece that appears after the piece on the gameboard is placed. The player can decide how to play considering the lookahead. When the player can see m lookahead pieces, just after the piece on the gameboard is placed, the first lookahead piece appears on the gameboard and the i^th lookahead piece becomes the (i−1)^th lookahead piece (2⩽i⩽m). At the same time, the m^th lookahead piece is newly given.

Puyos of the same color which are placed on vertically or horizontally adjacent cells are called a block. If blocks with four or more puyos are made after a piece is placed, all the puyos in the blocks disappear. Just after blocks disappear, puyos placed above them fall down. New blocks with four or more puyos can be made by the fall, which causes a chain reaction. An example of the moves of PuyoPuyo with two lookahead pieces is shown in Fig. 1. In the figure, colors are represented by capital letters. Two lookahead pieces are shown on the right of the gameboard, the first lookahead piece is on the top and the second lookahead piece is on the bottom. A bold arrow means that a new piece appears on the gameboard in the next configuration.

Fig. 1.

An example of moves of PuyoPuyo. See main text for full explanation.

3.PuyoPuyo with finite lookahead

In this section, we consider the case that the player can see a finite number of lookahead pieces. In addition to the width of the gameboard and the number of colors, we take the number of lookahead pieces m as another parameter. The following theorem shows the number of colors sufficient to make the player lose.

Theorem 3.

On single-player PuyoPuyo with m lookahead pieces, when the width of the gameboard is w, the player can make no puyos disappear if the number of colors k satisfies the following:

k⩾2(w=1)w+2m+(2m+2)⌊w−13⌋+2(w⩾2)

Proof.

We show how the adversary chooses the input pieces so that the player can make no puyos disappear. When w=1, two colors are sufficient to make the player lose. In this case, if all the pieces consist of puyos with two different colors, the player obviously cannot make four puyos of the same color connected even though the player knows the input sequence.

When w⩾2, the adversary chooses the pieces so that no puyos of the same color are connected vertically and four puyos of the same color are not connected horizontally. To prevent vertical connections to be made, the adversary must decide the new piece (m^th lookahead piece) so that the following conditions are satisfied at any moment.

i) The colors that appear at the top of columns are not included in the falling and lookahead pieces.
ii) All the puyos in the falling and lookahead pieces have different colors.

Note that, from the latter condition, each piece consists of two puyos with different colors. If both conditions are satisfied, the piece falling on the gameboard does not include the colors that appear on the top of the columns. Thus, the conditions are sufficient to prevent the vertical connection of the same color.

When no vertical connection exists, four puyos of the same color must be connected horizontally to make a block of size four. We consider how to prevent such horizontal connections. Divide the columns into intervals that consist of three consecutive columns 3i−2 to 3i (1⩽i⩽⌈w3⌉) as shown in the left gameboard of Fig. 2, where the leftmost column is column 1 and i is the index of an interval. When w is not a multiple of three, the rightmost interval consists of one or two columns. We call a boundary of two consecutive intervals a border. If all the pairs of horizontally adjacent puyos placed on both sides of borders consist of different colors, four puyos of the same color cannot be connected horizontally. To maintain this property, the following condition must be satisfied at any moment.

iii) Any puyo in the falling and lookahead pieces cannot be placed on a cell horizontally adjacent to the puyo of the same color that is on the other side of a border.

Note that, as condition ii) is satisfied, no vertical connection can be made with two puyos in the falling or lookahead pieces.

Fig. 2.

An example to choose lookahead pieces (m=2).

If the heights of the columns on both sides of a border are different, by placing the falling piece and all the lookahead pieces on the lower column, 2(m+1) puyos can be placed on that column. Thus, when the adversary gives the m^th lookahead, it must be chosen so that it does not include the colors used in the 2(m+1) adjacent puyos on the higher column. For example, in the left gameboard of Fig. 2, colors of the m^th lookahead piece GH are chosen so that they do not include the 2(m+1) colors A, B, C, D, E and F on the right side of the border. The colors of the puyos above the 2(m+1) puyos may be used in the m^th lookahead as the m^th lookahead cannot be placed adjacent to them.

Now we count the number of colors necessary to choose the m^th lookahead piece satisfying the above conditions. To satisfy conditions i) and ii), as the number of colors on the top of columns is at most w and the number of colors used in the last m pieces is 2m, at most w+2m colors cannot be used. The number of colors that cannot be used to satisfy condition iii) is at most 2(m+1) for each border, and the number of borders is ⌊w−13⌋. In total, the necessary number of colors is w+2m+(2m+2)⌊w−13⌋+2, where the last term is added so that two colors of the next piece can be chosen without using the prohibited colors. □

When m=0, as the necessary number of colors is w+2⌊w−13⌋+2⩽3w−4 for w⩾5, it also improves the previous result for the case without lookahead in Theorem 2 (Takenaga and Shimada, 2016) for w⩾5.

4.PuyoPuyo with infinite lookahead

In this section, we consider the situation that the player knows all the upcoming inputs, in other words, the number of lookahead pieces is infinite. When the width of the gameboard is one, two colors are sufficient to make the player lose as described in the previous section. We show the necessary number of colors to make the player lose for the cases of widths two and three.

4.1.Case of width two

First, we consider the case that the width of the gameboard is two. We can easily observe that at least two vertical connections exist in a block with four or more puyos. When three puyos of the same color are connected vertically, there exist two vertical connections.

The idea of the proofs is as follows. We consider an input sequence such that a subsequence is repeated infinitely. We first obtain an upper bound on the number of vertical connections that can be made using the puyos in the first t rounds of the subsequence. From the upper bound, we can compute an upper bound on the number of puyos that can disappear in t rounds. Finally, we show that the number of puyos that do not disappear and remain on the gameboard can be arbitrarily large as t increases, which means that the player loses.

We first assume that the number of colors is even. In the following, we represent colors by positive integers. A piece with puyos of colors i and j is represented as (i,j). The number of colors is 2n (n⩾2) and the input sequence is such that the subsequence (1,2),(3,4),…,(2n−1,2n) consisting of n pieces is repeated infinitely.

Lemma 4.

When the width of the gameboard is two, at most 4(t−1) vertical connections can be made using the puyos in the first t rounds.

Proof.

A pair of puyos with the same color placed in the same column can possibly make a vertical connection at some moment in the gameplay. Even if two puyos of the same color are not adjacent when they are placed, a vertical connection appears if all the puyos between them disappear.

We consider the maximum number of pairs that can exist in the sequence of puyos placed in a column, all of which can possibly make vertical connections. In the following, when puyo a is placed below puyo b, we write a≺b. Similarly, when a is placed below puyo b or a=b, it is denoted as a⪯b. A pair of puyos a and b is denoted as ⟨a,b⟩, where a≺b must be satisfied. If two distinct pairs ⟨p1,p2⟩ and ⟨q1,q2⟩ satisfy p1⪯q1≺p2⪯q2 as shown in Fig. 3, at least one of the pairs cannot make a vertical connection. This is because ⟨p1,p2⟩ can make a vertical connection only when q1 disappears before ⟨q1,q2⟩ makes a vertical connection. Note that, when p1=q1, these three puyos can be vertically connected. However, as there is p2 between p1 (=q1) and p2, q1 and q2 cannot be vertically connected. (Instead, p2 and q2 can be vertically connected.) It is similar for the case when p2=q2.

That is, any two pairs ⟨p1,p2⟩ and ⟨q1,q2⟩ (p1≺q1) satisfy either of the following relations.

α) p1≺q1≺q2≺p2
β) p2⪯q1

The positions of the two pairs are shown in Fig. 4.

When any two pairs of puyos satisfy the above relations α or β, if puyos in the column are removed in an appropriate order, all the pairs of puyos make a vertical connection at some moment. Here, we do not consider if it is possible to remove the puyos in such a manner in gameplay. However, as the pairs of puyos that make vertical connections in gameplay must satisfy the above relations, the maximum number of such pairs upper bounds the number of vertical connections.

To compute the maximum number of pairs made in a column, we assume that all the puyos in the input pieces are placed in a column. This is because any sequence of puyos placed in a column in gameplay using two columns is a subsequence of some placement of all the puyos in a column. The maximum number of pairs made in a sequence of puyos is obviously not smaller than that made in its subsequence. Therefore, the maximum number of pairs made in such a placement of puyos in t rounds is an upper bound on the number of vertical connections made in a column during the first t rounds. By doubling the upper bound, an upper bound of the total number of vertical connections in two columns is obtained.

From here, to simplify the discussion, we consider pairs of pieces, not pairs of puyos, for a while. A pair of pieces consists of two pieces of the same colors. Remember that colors 2i−1 and 2i appear only in the piece (2i−1,2i). We still assume that all the input pieces are placed in a column. Ignoring the rotation of pieces, the order in which pieces are placed in a column is uniquely determined.

Let Pi be the i^th piece and [a,b] (a<b) be the pair of pieces with Pa and Pb. As pieces in a pair must be of the same colors, b−a is a multiple of n. Similar to the case of pairs of puyos, if two pairs [a,b] and [a′,b′] satisfy a⩽a′<b⩽b′, it is impossible to make vertical connections both in the pair [a,b] and in the pair [a′,b′]. Therefore, we consider the set of pairs of pieces, such that any two pairs satisfy either of the relations similar to the above relations α or β.

First, we consider the number of pieces necessary to make k pairs of pieces any two of which satisfy relation α. That is, there exist k pairs [ai,bi] (1⩽i⩽k) satisfying a1<a2<⋯<ak<bk<⋯<b2<b1 and there exist no other pair between a1 and b1. Consider the pairs [ai,bi] and [ai+1,bi+1]. The number of pieces between ai and ai+1 is ai+1−ai−1. Similarly, the number of pieces between bi+1 and bi is bi−bi+1−1. The sum of them is ((bi−ai)−(bi+1−ai+1))−2=cn−2 for some positive integer c, which is at least n−2. Now we consider the number of pieces necessary to make k such pairs. There are at least n−1 pieces between ak and bk. The sum of the number of pieces between ai and ai+1 and that between bi+1 and bi is at least n−2 for each i. Also, 2k pieces are needed to make k pairs. In total, at least (n−1)+(k−1)(n−2)+2k=kn+1 pieces are necessary.

Conversely, we can show that k pairs of pieces can be made using any consecutive kn+1 pieces by induction on k. When k=1, one pair can be made on n+1 consecutive pieces. Assume that m pairs can be made using any consecutive mn+1 pieces. If there exist (m+1)n+1 consecutive pieces, as the first and the last pieces have the same colors, a pair can be made using them. As there remain (m+1)n−1=mn+1+(n−2)⩾mn+1 pieces between them, m+1 pairs can be made in total.

Until now, we have considered the case that any two pairs of pieces satisfy relation α. Now we consider the case that pairs may satisfy relation β. We show that if k pairs can be made using a set of consecutive pieces, k pairs such that any two of which satisfy relation α can be made using the same set of pieces. Assume that groups of r pairs and s pairs exist, both consisting of pairs that satisfy relation α as shown in the left side of Fig. 5. Also, assume that there exists no other pair on the set of pieces. To make r pairs and s pairs, rn+1 and sn+1 pieces are required, respectively. As the bottom piece in the r pairs and the top piece in the s pairs may be the same piece, at least (r+s)n+1 pieces are used to make these pairs. The r pairs and the s pairs cannot share more than one piece because otherwise there exist pairs that satisfy neither α nor β. Thus, it is possible to make r+s pairs any two of which have relation α using these pieces. By repeatedly applying this process, any set of pairs can be transformed into pairs such that any two of them satisfy relation α using the same set of pieces. Therefore, it is impossible to make k pairs of pieces using fewer than kn+1 consecutive pieces. From the above discussion, kn+1 consecutive pieces are necessary and sufficient to make k pairs.

We compute an upper bound on the number of pairs of pieces made from pieces of the first t rounds. In t rounds, tn pieces are placed. If there exist k pairs of pieces, tn⩾kn+1 is satisfied. Thus, at most t−1 pairs of pieces can be made. Now we go back to pairs of puyos. If there exists a pair of pieces, two pairs of puyos can be made using the puyos in these pieces. Then the number of pairs of puyos made in a column is at most 2(t−1), which is an upper bound on vertical connections made in a column using the puyos in the first t rounds. As puyos can be placed in two columns, at most 4(t−1) vertical connections can be made. □

As vertical connections are necessary to make puyos disappear, the number of puyos that disappear can also be bounded from above. We prove the next lemma to compute an upper bound. Note that a block with six or more puyos may be created by a chain reaction. Though there seems to exist a limit on the size of a block, we do not consider it here as the limit is not obvious.

Lemma 5.

Consider a block with at least four puyos on the gameboard of width two. The ratio of the number puyos in a block to the number of vertical connections in the block is at most 52, which can be achieved when the number of puyos is five. The second-largest ratio is two, which can be achieved when the number of puyos is four, six, or eight.

Proof.

In this proof, we consider only the puyos that constitute a block. Puyos in a block are placed in some consecutive rows. We can assume that a puyo exists in the left column of all the rows for the following reason. Consider a maximal series of consecutive rows such that puyos in a block exist only in the right column. If the row just above or just below them contains a puyo in the block only in the left column, the puyos do not constitute a block. Thus, the rows just above and below them are either a row with two puyos of the block or a row with no puyo of the block. Therefore, the number of vertical connections does not change by moving the puyos in the right column to the left column. An example is shown in Fig. 6. In this figure, only the puyos in the block are shown and the other cells are occupied by puyos of other colors or empty.

Now we compute the minimum number of vertical connections necessary to make a block with m puyos. Let the block be positioned in h rows (⌈m/2⌉⩽h⩽m). We can assume that h puyos are placed on the left column. When there exists no vertical connection in the right column, the number of vertical connections is h−1, and the ratio is m/(h−1). It becomes larger as h decreases.

When there exists at least one vertical connection in the right column, there exist h−(m−h)=2h−m cells that do not include the puyo of the block in the right column. Thus, there exist at least (h−1)−2(2h−m)=2m−3h−1 vertical connections in the right column. As there exist at least (h−1)+(2m−3h−1)=2m−2h−2 vertical connections in two columns, the ratio is at most m/(2m−2h−2). The ratio becomes larger as h increases.

As there are m−h puyos in the right column, there exists no vertical connection in the right column when 2(m−h)−1⩽h. That is, h⩾(2m−1)/3. From the above discussion, in both cases, the ratio is not larger than the values obtained by assigning h=(2m−1)/3. In both cases, the ratio is 3m/(2m−4), which is smaller than 2 for m⩾9. By considering the cases of 4⩽m⩽8, we can easily check that the ratio can be 5/2 when m=5 and 2 when m=4,6 and 8. The ratio 52 is achieved on the block as shown in Fig. 7. □

Fig. 3.

An illegal position of two pairs.

Fig. 4.

Legal positions of two pairs.

Fig. 5.

Modify the pairs of pieces without reducing the number.

Fig. 6.

Move puyos to the left column.

Fig. 7.

A block with ratio 5/2.

Fig. 8.

The situation that three puyos are vertically connected.

The next theorem is the main result of this section.

Theorem 6.

Consider the single-player PuyoPuyo on a gameboard of width two. When the number of colors is ten or larger, there exists an input sequence for which the player loses even when the player knows the whole input sequence.

Proof.

First, consider an upper bound on the number of puyos that disappear in the first t rounds. From Lemma 5, it seems that the number is maximized if all the blocks disappear in the form of Fig. 7. However, two vertical connections are made with three puyos in this block. To produce a block of the form, the maximum number of vertical connections decreases by one. The reason is as follows. The three puyos in the vertical connections come from three different pieces with the same colors ((p1,q1), (p2,q2) and (p3,q3) in Fig. 8). In the proof of Lemma 5, we have assumed that two pairs of puyos can be made from a pair of pieces. However, if three puyos are vertically connected, at most three pairs of puyos can be made using two pairs of pieces. To make two pairs of puyos with a pair of pieces, two pieces must be placed in different directions as shown in Fig. 8. In this case, two pairs of puyos ⟨p1,p2⟩ and ⟨q2,q3⟩ satisfy neither α nor β.

Assume that m blocks with the form of Fig. 7 disappear. Then, after the first t rounds, the number of vertical connections is at most 4(t−1)−m from Lemma 4 and the above argument. In the above m blocks, 5m puyos disappear. By using the remaining 4(t−1)−m−2m vertical connections, at most 2(4(t−1)−3m) puyos can disappear by Lemma 5. In total, the number of puyos to disappear is at most 5m+2(4(t−1)−3m)=8t−8−m. It means that the number of puyos to disappear is maximized when m=0. That is, it is not efficient to produce blocks of Fig. 7. Therefore, at most 8t−8 puyos can disappear during the first t rounds.

As the total number of puyos in t rounds is 2nt, the number of puyos that remain on the gameboard after t rounds is at least 2nt−(8t−8)=(2n−8)t+8. When n⩾5, the number of the remaining puyos becomes arbitrarily large as t increases. It means that the player loses. Even when the number of colors is larger than ten, it is sufficient to use only ten of them to make the player lose. □

It may be possible to show that the player loses when the number of colors is nine by applying similar ideas for an odd number of colors. However, for the input sequence such that (1,2),(3,4),…,(9,1),(2,3),…,(8,9) is repeated infinitely, the above method is not sufficient to prove it because three puyos can be efficiently connected vertically.

4.2.Case of width three

In this section, we apply the above method to the gameboard of width three. The input sequence is the same as the one considered in the case of width two. The only difference is that the number of vertical connections necessary to make a block disappear is one.

Lemma 7.

Consider a block with at least four puyos on the gameboard of width three. The ratio of the number of puyos in a block to the number of vertical connections in the block is at most 4, which is achieved when the number of puyos is four.

Proof.

We consider only the puyos in a block. First, consider a maximal series of consecutive rows such that puyos in the block exist in the left and the right columns, and not in the middle column as shown in Fig. 9. Then, either the row just above them or the row just below them must include puyos in all the columns. Because otherwise, the puyos are not connected. Without loss of generality, we assume that the row just below them has three puyos. There exist four cases of the row just above the consecutive rows shown in Fig. 9, where the patterns symmetric to the ones in the list are omitted. In any case, by moving the puyos surrounded by a rectangle to the middle column, there exist no rows such that puyos exist only in the left and the right columns. The move keeps the connectivity of puyos without changing the number of vertical connections.

Next, consider a maximal series of consecutive rows such that puyos exist only in the left column. As in the proof of Lemma 5, in the rows just above or just below them, puyos exist both in the left and the middle column or no puyos exist in the row. Then the puyos in the left column can be moved to the middle column without changing the number of vertical connections. A similar discussion holds for the rows such that puyos exist only in the right column. After all the moves, each row in the block includes a puyo in the middle column.

Fig. 9.

Possible locations of puyos.

Now we fix the number of rows h which is used for the block and consider the maximum ratio when we change the number of puyos in the block. From the above discussion, we can assume that every row contains a puyo of the block in the middle column. When there is no vertical connection in the other columns, the ratio is maximized when m is the largest. As at most ⌈h/2⌉ puyos can be placed in the right and left columns respectively, the ratio is (h+2⌈h/2⌉)/(h−1).

If the number of puyos becomes larger, whenever we add a puyo to the left or the right column, the number of vertical connections increases at least by one. As h−1<h+2⌈h/2⌉, ((h+2⌈h/2⌉)+1)/((h−1)+1)<(h+2⌈h/2⌉)/(h−1) holds. Then the ratio becomes smaller as the number of puyos increases. Therefore, the maximum ratio is (h+2⌈h/2⌉)/(h−1) for any fixed h. When we change the value of h, we can see that the ratio is maximized when h=2 and the ratio is 4. □

Theorem 8.

Consider the single-player PuyoPuyo on a gameboard of width three. When the number of colors is twenty-six or larger, there exists an input sequence for which the player loses even when the player knows the whole input sequence.

Proof.

This theorem is proved similarly to Theorem 6. As the upper bound on the number of pairs of puyos obtained in the proof of Lemma 4 can be applied to each column, the total number of vertical connections is at most 3·2(t−1). From Lemma 7, at most 4·6(t−1) puyos disappear in t rounds. Thus, the number of puyos that remain on the game board after t rounds is at least 2nt−24t+24. When n⩾13, the number of remaining puyos becomes arbitrarily large as t increases, and the player loses. □

5.Conclusion

In this paper, we have considered the limit of the power of lookahead in single-player PuyoPuyo. We have shown the number of colors sufficient to make the player lose for two cases. The first case is that the player can see m lookahead pieces, and the second case is that the player knows the whole input sequence and the width of the gameboard is two or three.

In the proof of the latter result, an upper bound on the number of vertical connections is considered. However, the upper bound seems not tight because, in many pairs, puyos in a pair cannot be vertically connected in the gameplay. Also, vertically connected puyos may not be made to disappear. Thus, it seems possible to reduce the number of colors necessary to make the player lose. However, it must require a very detailed analysis. To show similar results on the gameboard of width four or larger, we must be able to deal with blocks that disappear with no vertical connections.

Acknowledgements

This work was supported by JSPS KAKENHI Grant Number 18K11601.

We would like to thank anonymous reviewers for their invaluable comments.

References

1	Aloupis, G., Cardinal, J., Collette, S. & Langerman, S. ((2007) ). Lumines strategies. In Proc. 5^th International Conference on Computers and Games. LNCS (Vol. 4630: , pp. 190–199). Springer.
2	Asif, S., Demaine, E.D., Lynch, J. & Singhal, M. ((2019) ). Tetris is NP-hard even with O(1) columns. In The 22^nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³) (pp. 37–38).
3	Baccherini, D. & Merlini, D. ((2007) ). Combinatorial analysis of Tetris-like games. Discrete Mathematics, 308: , 4165–4176. doi:10.1016/j.disc.2007.08.009.
4	Breukelaar, R., Demaine, E.D., Hohenberger, S., Hoogeboom, H.J., Kosters, W.A. & Liben-Nowell, D. ((2004) ). Tetris is hard, even to approximate. International Journal of Computational Geometry & Applications, 14: (1–2), 41–68. doi:10.1142/S0218195904001354.
5	Brzustowski, J. (1992). Can you win at Tetris? Master’s thesis, University of British Columbia.
6	Burgiel, H. ((1997) ). How to lose at Tetris. Mathematical Gazette, 81: , 194–200. doi:10.2307/3619195.
7	Demaine, E.D., Demaine, M.L., Eisenstat, S., Hesterberg, A., Lincoln, A., Lynch, J. & Yu, Y.W. ((2017) ). Total Tetris: Tetris with monominoes, dominoes, trominoes, pentominoes, …. Journal of Information Processing, 25: , 515–527. doi:10.2197/ipsjjip.25.515.
8	Hoogeboom, H.J. & Kosters, W.A. ((2004) a). Tetris and decidability. Information Processing Letters, 89: , 267–272. doi:10.1016/j.ipl.2003.12.006.
9	Hoogeboom, H.J. & Kosters, W.A. ((2004) b). How to construct Tetris configurations. International Journal of Intelligent Games & Simulation, 3: (2), 97–105.
10	Matsukane, T. & Takenaga, Y. ((2006) ). NP-completeness of maximum chain problem on Puyopuyo. Trans. IEICE, J89-D: (3), 405–413. (in Japanese).
11	Merlini, D., Sprugnoli, R. & Verri, M.C. ((2002) ). A strip-like tiling algorithm. Theoretical Computer Science, 282: (2), 337–352. doi:10.1016/S0304-3975(01)00074-3.
12	Muta, H. ((2005) ). Puyopuyo is NP-complete, IEICE technical report. In COMP2005-14 (pp. 39–44) (in Japanese).
13	(c)SEGA (n.d.). SEGA ∣ PuyoPuyo portal site, http://puyo.sega.jp/portal/index.html (accessed 27 Nov. 2020) (in Japanese).
14	Şimşek, Ö., Algorta, S. & Kothiyal, A. ((2016) ). Why most decisions are easy in Tetris – and perhaps in other sequential decision problems, as well. In Proc. 33^rd International Conference on Machine Learning (Vol. 48: , pp. 1757–1765).
15	Takenaga, Y. & Shimada, Y. ((2016) ). Strategies for single-player PuyoPuyo. ICGA Journal, 39: (2), 1–14.