How Many Steps Does It Take To Surround A Cat? 【Multiple Cat Warning】

Time flies so fast, and it’s already the sixth day of the Lunar New Year in a blink of an eye. Are you still enjoying the holiday? Of course, games are indispensable during the holidays. In this last lazy holiday, why not let the editor take you to play a little game! In this mini-game, you can surround the cute cats with just a few clicks, and then...ahem, enjoy the cold victory!

Back to topic. The game I’m going to talk about today is called Wai Mao. It became really popular in the editor’s circle of friends at the end of 2021. If you haven’t played it yet, you can search for “Wai Mao” in the search engine. Readers with good memories may remember that this is not the first time that this game has become popular. Yes, it is the new skin of "Surround the Nervous Cat" that was popular on WeChat Moments in 2014! Its prototypes date back even further.

Last time I let you off before I came out. Now that I've caught you this time, hey, if I don't surround you today, I'm not the editor of the Second High School!

game introduction

First introduce the rules of the game. The starting kitten is located in the center of the board, and 6-8 obstacles will be randomly placed on the map in advance. Each time we click on the small dot, we can place an obstacle there, and the kitten will move one space to the edge of the map. This continues until the cat is surrounded by obstacles and wins the game, or reaches the edge of the map. The slip away game failed.

When you first get started, you will find that this game is not easy, and it is almost difficult to succeed. Because the chessboard is actually not big, the cat only needs 5 moves to run out of the chessboard boundary, making it difficult to block the kitten.

A natural question then is: if the chessboard is large enough, is it guaranteed to block the kitten? Before answering this question, please let me first introduce the "angel problem" (angel).

angel problem

The angel problem [1] was first seen in the book "Ways" published in 1982, and was proposed by the author of the book, mathematician John H. Conway. This is a game where both players play the roles of angels and demons. The game is played on an infinite square board, and the starting board is empty. Define the positive integer k as the order of the angel. The angel of order k can jump to any square within the k*k range at each step, regardless of whether there are obstacles on the road.

Figure 1 The blue dotted line box shows the movement range of the third-order angel | Source: Wikipedia[1]

In each round, the devil can place an obstacle on the board, but not where the angel is currently, and the angel can move to any place within range that has not placed an obstacle. If the angel cannot move during a round, the demon wins. If the angel can continue the game indefinitely, the angel wins.

Conway has proven [2] (although he said it was shown to him by Burley Camp, the co-author of the book) that as long as the board size is larger than 32*33, the devil will win when k=1.

For the convenience of display, the grid points are transformed into squares here. As shown in Figure 2, it is a 33*33 chessboard, and the angel starts in the red square. No matter how the angel starts, the devil only needs to fill the 8 black squares around the board with obstacles in the first 8 steps. At this time, the angel must be in the blue area in the middle, and there are still 7 steps away from contacting the encirclement.

Figure 2 Level 1 situation where the devil must win | Image source self-made

No matter which direction the angel flees, the devil can place an obstacle every other space to gradually narrow the gap, ensuring that the gap is blocked before the angel touches the edge of the chessboard, so the devil is sure to win.

The first-order angel problem tells us that as long as the chessboard is large enough and we can arrange the encirclement in advance, we will be able to surround the angel. Moreover, the chessboard in the angel problem is eight-connected, that is, the angel can move in eight directions, horizontally, vertically, and diagonally, so it takes at least eight steps to arrange an encirclement. The chessboard in Bei Mao is six connected, so the encirclement circle only requires 6 moves. We define the minimum number of steps for a cat to escape from the center of the blank chessboard as the depth n of the chessboard. It can be seen that the depth of the chessboard for the Kitten Game is 5.

Figure 3 The depth of the game board is 5

Rich gaming experience tells me that n=5 is obviously not enough. If you want to guarantee victory, setting up an encirclement like in the angel problem requires at least 6 obstacles, that is, 6 steps. Because the cat will escape from the chessboard in n moves, and we must spend at least one step to block the escape direction before the cat escapes, the depth n of the chessboard should be at least 6+1+1=8. So how big does the chessboard need to be to ensure victory? The answer is n=8[3]. In the picture, the even-numbered grid points are the obstacles placed by our side, and the odd-numbered grid points are the cat's movement trajectory. It can be seen that in this case, our side will definitely win.

Figure 4 The winning strategy when n=8 | Picture source Zhihu[3]

Therefore, as long as the depth of the chessboard is not less than 8, even if it is a blank chessboard, we will definitely be able to surround the kitten. Correspondingly, in the absence of obstacles, it is impossible for us to surround the kitten when the board depth is less than 8.

So, what about obstacles?

Finally, we return to our original question: how to use existing obstacles to surround cats on an n=5 chessboard. In fact, the idea here is still the same, that is: first use several steps to lay out an encirclement, and then complete the encirclement by enclosing it. The only difference is that since the chessboard is not big enough, we have to use existing obstacles to lay out the encirclement. Like the depth of the chessboard, we define the depth of the encirclement as the minimum number of steps for the cat to escape from the encirclement. Obviously, the deeper the encirclement, the more steps we have left to set up a defensive line.

Let’s first study what the encircling circle should look like: the enclosing circle should be a hexagon, the same shape as the chessboard, and each side should pass through the center of each grid point. Direct diagonal connections are not allowed. Only when there are obstacles at each vertex of the encircling circle (such as points 1-6 in Figure 6 below) or the grid points adjacent to the vertex and on the surrounding circle (points 7-15 in Figure 6 below) can the trigger be activated. To the effect of blocking cats. If there are no obstacles in the above position, there is no guarantee that the circle will be closed when the cat is chased here.

In Figure 5, the red connecting line does not pass through the center of all circles passing through the grid points, which is a wrong oblique connection.The dark blue polyline above is the correct connection method

If a vertex or its adjacent grid points have obstacles on the enclosing circle, we call the vertex completed, and define the completion degree of an enclosing circle as the number of completed vertices. Let's give an example to illustrate.

Figure 6 An example of a surrounding circle

Figure 6 is a prototype of an encircling circle. You can see that there are obstacles at points 1, 2, 11, 4, and 5, and their corresponding vertices are all completed. But it is not a complete encirclement because vertex 6 is unfinished. If the cat escapes from the upper right to the upper left, after we block point 8, the cat will escape to point 16. At this time, both points 6 and 7 are empty, and the cat escapes. Although there is an obstacle at vertex 5, it is also a vertex in itself and cannot be counted as an adjacent point to vertex 6. So the completion degree of this encirclement is 5.

From the situation where the board depth is 8, we can know that when the encirclement is completed, that is, when the completion degree is 6, if the cat is at least 2 blocks away from the encirclement, we can definitely win by placing obstacles according to the cat's position to encircle it. In other words, the winning condition is that the depth of the encirclement + the completion of the encirclement are at least 8. Fortunately, the cat in the picture above is 3 blocks away from the encircling circle, which means the depth of the encircling circle is 3. As shown in the picture below, we only need to fill in the missing points in the encircling circle to ensure victory. This is why for those of us who have read this article, our first step is at point 6, which does not seem to require priority containment. Figure 7 below shows the winning method of surrounding the cat in the example in Figure 6.

Figure 7 The winning method of Figure 6

It should be noted that there are also skills in drawing encirclement. For example, in Figure 8 below, there are two ways to draw a circle, AB, and the completion degree of the surrounding circle is both 5. If the encirclement circle between points 4 and 5 is planned according to the red plan A, the depth of the encirclement circle is 2, the depth of the 5+2 encirclement circle is 3, and 5+3=8, which can surround the cat. So the way you draw a circle is also very important!

Figure 8 Two different encirclement methods

However, due to the limitations of the game conditions, there are only 6-8 obstacles at the beginning, and the board depth is only 5, so it is impossible to win in most cases. If you want to surround the kitten, refresh more!

However, in fact, the kitten in the game is not very smart. Its escape logic is just a single-layer greedy algorithm: it only considers the best escape route currently. Therefore, we can use this to set up traps to induce cats to take extra steps, thereby winning the unwinnable chessboard. Interested readers must give it a try.

The secret to keeping cats around!

Finally, let’s wrap up our tips for keeping cats around! It only takes three simple steps.

Step 1: Define the encircling circle based on the existing initial obstacles, and make the depth of the encircling circle as large as possible while ensuring that as many vertices as possible are completed.

Step 2: Determine whether the completion degree of the enclosing circle + the depth of the enclosing circle ≥ 8? If it is smaller than the value, it is not guaranteed to surround the cat and will be reset directly.

Step 3: Complete the encirclement first, and then encircle the cat's location to win.

write at the end

Remember the angel problem mentioned at the beginning? This problem has not actually been completely solved. At present, when the order k of angels is relatively small, such as k=2, mathematicians have proven that angels must win on an infinite chessboard. However, for any angel of finite order, there is no answer to the question of which side can win. . Maybe, the one who can solve this problem is you who are smart. It doesn’t matter if you can’t solve it, at least you learned how to catch the cat, right?

references:

[1]

[2]John H., The angel, in: () Games of No, 29 of MSRI, pages 3–12, 1996.

[3] Zeng Jia’s answer - Zhihu

The cover comes from Sohu.com, and the emoticon package comes from the Internet.