Time flies so fast, in the blink of an eye it is already the sixth day of the Chinese New Year, are you still enjoying the holiday? Of course, the holiday is indispensable to the game, in this last lazy holiday, it is better to let xiaobian take you to play a small game! In this mini-game, you can surround the cute cats with a single tap, and then enjoy... Cough, enjoy the cold victory now!
Back to the point. The game I want to talk about today is called Wei Kitten, at the end of 2021, in my circle of friends is really a fire, if you have not played it, you can search for "Wei Kitten" in the search engine. Readers with a good memory may remember that this game is not the first time it has been fired, yes, it is the new skin of the "Surrounding Nerve Cat" that was fired in the circle of friends in 2014! Its prototypes can be traced back even earlier.
Last time I did not go out of the mountain to let you go, this time since I caught, hey hey, today I don't surround you, I am not the second small editor!
Game Introduction
First, let's talk about the rules of the game. The starting kitten is located in the center of the board, and 6-8 obstacles are pre-placed randomly on the map. Each time we click on the dot, we can place an obstacle there, and the kitten will move a block towards the edge of the map, and repeat it until the cat is surrounded by obstacles and wins the game, or reaches the edge of the map to slip away and the game fails.
When you first get started, you will find that this game is not simple, and it is almost difficult to succeed. Because the chessboard is actually not large, the cat only needs 5 moves to run out of the board boundary, and it is difficult to block the kitten.
So a natural question is: if the board is large enough, is it guaranteed to block the kitten? Before answering this question, let me introduce the "angel problem."
Heavenly messenger question
The Angel Problem[1] first appeared in the 1982 book Winning Ways, written by mathematician John F. Kennedy. Proposed by John H. Conway. This is a game in which both players play as angels and demons respectively. The game takes place on an infinitely large grid board, the starting board is empty. Define the positive integer k as the order of the angels, and the k-order angels can jump to any block in the k*k range at each step, regardless of whether there are obstacles in the road.
Figure 1 The movement range of a 3rd order angel in a blue dotted box | source Wikipedia[1]
In each round, demons can place an obstacle on the board, but not in the current angel's position, and the angel can move to any place within range that is not placed with an obstacle. If in a round, the angel cannot move, the demon wins. If the angel can continue the game indefinitely, the angel wins.
Conway has shown that[2] (although he says it was shown to him by the book's co-author Berly Kemp) that demons are victorious in cases where the size of the board is greater than 32*33 and k=1.
For the convenience of display, the grid is pointed into a square here. Figure 2 shows a 33*33 chessboard with angels starting in the red square. No matter how the angel starts, the first 8 steps of the demon only need to fill the obstacles with 8 black boxes around the board, at which point the angel must be in the middle of the blue area, 7 steps away from the contact circle.
Figure 2 Order 1 Demon Victory | Figure is derived from the system
No matter which direction the angel fled, the demon could gradually narrow the gap by placing an obstacle every block, ensuring that the gap was closed before the angel touched the edge of the chessboard, so the demon was victorious.
The first-order angel problem tells us that as long as the chessboard is large enough for us to arrange the circle in advance, we will definitely 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, so it takes at least eight steps to arrange a circle. The board in the kitten is six connected, so the circle only needs 6 steps. We define the minimum number of moves for a cat to escape from the center of a blank board as the depth of the board n, and as you can see, the board depth of the kitten game is 5.
Figure 3 The depth of the game board is 5
Extensive gaming experience has taught me that n=5 is clearly not enough. If victory is to be guaranteed, it takes at least 6 obstacles, or 6 steps, to place a circle like in the angel problem. Because the cat's n-step will escape from the board, and we must spend at least one step to block the direction of the escape before the cat escapes, the depth of the board n should be at least 6+1+1=8. So how big does the chessboard need to be to guarantee a win? The answer is n=8[3]. In the figure, the even number of grid points is the obstacle placed by our side, and the odd number grid points are the trajectory of the cat and cat in turn, which can be seen that in this case, we are bound to win.
Figure 4 The winning strategy at n=8| the source of the figure is known[3]
Therefore, as long as the depth of the board is not less than 8, even if it is a blank board, we can definitely 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 are the obstacles?
Finally back 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 a number of steps to arrange a circle, and then improve the circle through encirclement. The only difference is that since the board is not large enough, we have to use the existing obstacles to arrange the encirclement. Like the depth of a board, we define the depth of the encirclement as the minimum number of moves the cat takes to escape the encirclement. Obviously, the deeper the encirclement, the more steps we have left to lay out the defensive line.
Let's first examine what the encircling circle should look like: the encircling circle should be hexagonal, the same shape as the chessboard, and each edge passes through the center of each grid point, and it is not allowed to be directly connected diagonally. Only each vertex of the enveloping circle (such as points 1-6 in Figure 6 below) or the lattice points adjacent to the vertex (points 7-15 in Figure 6 below) have obstacles to block the cat. If there are no obstacles in the above positions, there is no guarantee that the enclosure will be closed when the cat is chased here.
Fig. 5 The red line does not pass through the center of all the passes through the grid, which is a wrong diagonal connection. The dark blue polyline above is the correct conjunction
If a vertex or a lattice point adjacent to it has an obstacle on the bounding circle, we call the vertex complete, defining the degree of completion of a bounding circle as the number of completed vertices. Let's take an example to illustrate.
Fig. 6 An example of a circle of encirclement
Figure 6 is a prototype of a circle of encirclement, and you can see that points 1, 2, 11, 4, and 5 all have obstacles, and their corresponding vertices are completed. But it is not a complete encirclement, because vertex 6 is unfinished. If the cat escapes from the top right to the upper left, the cat will flee to the 16th point after we block the 8th point, at which time 6 and 7 are empty, and the cat and the cat escape. Vertex 5, although it has an obstacle, is also a vertex in itself and cannot be counted as an adjacent point to vertex 6. So the degree of completion of this encirclement is 5.
From the situation that the depth of the board is 8, we can know that when the encirclement is completed, that is, the degree of completion is 6, if the cat is at least 2 blocks away from the encircling circle, we can win by placing obstacles according to the position of the cat and cat. That is to say, the winning condition is that the depth of the encirclement + the completion of the encircling circle is at least 8. Fortunately, the cat in the picture above is 3 blocks away from the encirclement, that is to say, the depth of the encirclement is 3, as shown in the following figure, we only need to make up for the missing points in the encirclement, we can guarantee victory. That's why, after reading this article, our first step falls at point 6, which doesn't seem to need to be prioritized. Figure 7 below shows the winning method of circumferential cats in Figure 6.
Figure 7 The winning method of Figure 6
It should be noted that drawing circles is also skillful. For example, the following Figure 8 has two ways of AB drawing circles, and the completion of the surrounding circle is 5. If the encirclement between points 4 and 5 is planned according to the red A scheme, the depth of the enveloping circle is 2, the depth of the 5+ 2 enveloping circle is 3, and the 5 + 3 = 8 can surround the cat. So the way you draw circles is also very important!
Fig. 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 depth of the board is only 5, so in most cases it is impossible to win, if you want to surround the kitten, refresh it as much as possible!
In reality, though, the kitten in the game isn't too clever, and its escape logic is just a single-layered greedy algorithm: only considering what currently seems to be the best escape route. So we can use this point to set a trap, induce the cat to take out the extra number of moves, so as to win the chessboard that cannot be won, interested readers and friends must try it.
The secret to surround the cats and cats!
Finally, let's sum up the secrets of surrounding cats! It only takes three simple steps.
Step 1: Delineate the encirclement according to the existing initial obstacles, and make the encirclement as deep as possible, provided that as many vertices are completed.
Step 2: Determine whether the completion of the encircling circle + the depth of the enveloping circle ≥8? If it is less than then there is no guarantee to surround the cat, directly reset.
Step 3: Complete the encirclement first, and then block the cat's location to win.
Write at the end
Remember the angel problem at the beginning? This problem has not been completely solved. At present, when the order k of angels is relatively small, such as k = 2, mathematicians have proved that angels are victorious on an infinitely large chessboard, but for angels of any finite order, the question of which one can win has no answer. Perhaps, the one who can solve this problem is the smart you. It doesn't matter if you can't solve it, at least, you learn how to catch cats, right?
bibliography:
[1] Wikipedia Angel Question
[2] John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.
[3] Zengjia's answer - Zhihu
The cover source is Sohu.com, and the emoji source network
Edit: fiufa
The reproduced content represents the views of the author only
It does not represent the position of the Institute of High Energy of the Chinese Academy of Sciences
Edit: lili
Great videos Don't miss out