The optimal algorithm of the game in the sea battle
A couple of days ago, I was surprised to learn that some of my friends do not know how to play sea battle. Those. Of course, they know the rules, but they play somehow haphazardly and in the end often lose. In this post I will try to explain the main ideas that will help improve the level of your game.
There are many options for sea battle, but we will consider the most common option with the following set of ships:
All listed ships should be placed on a square field of 10 by 10 cells, and the ships can not touch either the corners or the sides. The playing field itself is numbered from top to bottom, and the verticals are marked with Russian letters from “A” to “K” (with the letters “E” and “Y” being skipped).
')
An enemy field of the same size is drawn next to it. With a successful shot at the enemy's ship, a cross is put on the corresponding cell of the enemy field and a second shot is fired, a point is made in the corresponding cell if the shot is unsuccessful, and the turn passes to the enemy.
In the game of sea battle there is always an element of chance, but it can be minimized. Before proceeding directly to the search for the optimal strategy, one obvious thing needs to be voiced: the probability of hitting the enemy ship is higher, the fewer unchecked cells left in its field, and the lower the more unchecked cells left in your field, the same is the probability of hitting your ships. So For an effective game you need to learn two things at once: optimal shooting at the enemy and optimal placement of your ships.
In the following explanation, the following notation will be used:
The first and most obvious rule for optimal firing is the following rule: do not shoot at the cells directly surrounding the destroyed enemy ship.
In accordance with the notation adopted above, in the figure, those cells that already have had unsuccessful shots are marked in yellow, the cells with shots which ended in a hit are marked in red, and the cells that have not been shot with are marked with green, but it can be guaranteed that They are not (ships can not be there, because according to the rules of the game ships can not touch).
The second rule immediately follows from the first rule: if you managed to destroy an enemy ship, you must immediately finish it in order to get a list of guaranteed free cells as early as possible.
The third rule follows from the first two: you must first try to make the biggest ships of the enemy. Perhaps this rule is not obvious to you, but if you think a little, you can easily see that by destroying the enemy battleship, we will at best get information about 14 guaranteed free cells, and destroying the cruiser, only about 12.
So The optimal shooting strategy can be reduced to the targeted search and destruction of the largest enemy ships. Unfortunately, it is not enough to formulate a strategy; it is necessary to propose a method for its implementation.
First, let's consider a 4-by-4-square plot of the game board. If there is an enemy battleship in the area in question, then it is guaranteed to be routed in no more than 4 shots. To do this, shoot in such a way that there is exactly one checked cell on each horizontal and vertical line. Below are all options for such shooting (excluding reflections and turns).
Among all these options, only the first two options are optimal on a field of 10 x 10 cells, ensuring that a maximum of 24 shots hit the battleship.
After the enemy battleship is destroyed, it is necessary to start the search for cruisers, and then the destroyers. In this case, as you may have guessed, you can use a similar technique. Only now it is necessary to break the field into squares with a side of 3 and 2 cells, respectively.
If you used the second strategy when searching for a battleship, then to search for cruisers and destroyers you need to shoot at the following fields (the green fields are that you already shot when searching for the battleship):
There is no optimal strategy for the search for boats, so at the end of the game you have to rely mainly on luck.
The optimal strategy for locating ships is, in a sense, inverse to the optimal strategy for shooting. When firing, we tried to find the largest ships to reduce the number of cells that need to be checked, at the expense of guaranteed free cells. This means that when placing ships it is necessary to install them in such a way that in case of their loss, to minimize the number of guaranteed free cells. As you remember, the battleship in the center of the field opens 14 fields for the enemy at once, but the battleship standing in the corner opens only 6 fields for the enemy:
Similarly, a cruiser standing in the corner, instead of 12 fields, opens only 6. Thus, having placed large ships along the field border, you leave more room for boats. Because there is no strategy to search for boats, the enemy will have to shoot at random, and the more free fields you have left by the time you catch the boats, the harder it will be for your opponent to win.
Below are three ways to accommodate large ships, which leave plenty of room for boats (marked in blue):
Each of the above arrangements leaves exactly 60 free cells for boats, which means that the probability of accidentally hitting the boat is 0.066. For comparison, the random placement of ships is worth mentioning:
With this arrangement, only 21 cells remain for the boats, which means that the probability of hitting the boat is already 0.19, i.e. almost 3 times higher.
In conclusion, I want to say that you should not spend too much time playing sea battle. I especially want to warn you against playing lectures. When I sat in Wabi Sabi and played a sea battle with my girlfriend, a waitress passed by and said that she played very well, because practiced a lot on pairs. Who knows what she would have worked if she had attended lectures at one time?
PS In the comments absolutely correctly indicate that there were already similar publications on Habré, it would be wrong not to put links to them:
habrahabr.ru/post/82221
Rules of the game
There are many options for sea battle, but we will consider the most common option with the following set of ships:
All listed ships should be placed on a square field of 10 by 10 cells, and the ships can not touch either the corners or the sides. The playing field itself is numbered from top to bottom, and the verticals are marked with Russian letters from “A” to “K” (with the letters “E” and “Y” being skipped).
')
An enemy field of the same size is drawn next to it. With a successful shot at the enemy's ship, a cross is put on the corresponding cell of the enemy field and a second shot is fired, a point is made in the corresponding cell if the shot is unsuccessful, and the turn passes to the enemy.
Optimal strategy
In the game of sea battle there is always an element of chance, but it can be minimized. Before proceeding directly to the search for the optimal strategy, one obvious thing needs to be voiced: the probability of hitting the enemy ship is higher, the fewer unchecked cells left in its field, and the lower the more unchecked cells left in your field, the same is the probability of hitting your ships. So For an effective game you need to learn two things at once: optimal shooting at the enemy and optimal placement of your ships.
In the following explanation, the following notation will be used:
Optimal shooting
The first and most obvious rule for optimal firing is the following rule: do not shoot at the cells directly surrounding the destroyed enemy ship.
In accordance with the notation adopted above, in the figure, those cells that already have had unsuccessful shots are marked in yellow, the cells with shots which ended in a hit are marked in red, and the cells that have not been shot with are marked with green, but it can be guaranteed that They are not (ships can not be there, because according to the rules of the game ships can not touch).
The second rule immediately follows from the first rule: if you managed to destroy an enemy ship, you must immediately finish it in order to get a list of guaranteed free cells as early as possible.
The third rule follows from the first two: you must first try to make the biggest ships of the enemy. Perhaps this rule is not obvious to you, but if you think a little, you can easily see that by destroying the enemy battleship, we will at best get information about 14 guaranteed free cells, and destroying the cruiser, only about 12.
So The optimal shooting strategy can be reduced to the targeted search and destruction of the largest enemy ships. Unfortunately, it is not enough to formulate a strategy; it is necessary to propose a method for its implementation.
First, let's consider a 4-by-4-square plot of the game board. If there is an enemy battleship in the area in question, then it is guaranteed to be routed in no more than 4 shots. To do this, shoot in such a way that there is exactly one checked cell on each horizontal and vertical line. Below are all options for such shooting (excluding reflections and turns).
Among all these options, only the first two options are optimal on a field of 10 x 10 cells, ensuring that a maximum of 24 shots hit the battleship.
After the enemy battleship is destroyed, it is necessary to start the search for cruisers, and then the destroyers. In this case, as you may have guessed, you can use a similar technique. Only now it is necessary to break the field into squares with a side of 3 and 2 cells, respectively.
If you used the second strategy when searching for a battleship, then to search for cruisers and destroyers you need to shoot at the following fields (the green fields are that you already shot when searching for the battleship):
There is no optimal strategy for the search for boats, so at the end of the game you have to rely mainly on luck.
Optimal placement of ships
The optimal strategy for locating ships is, in a sense, inverse to the optimal strategy for shooting. When firing, we tried to find the largest ships to reduce the number of cells that need to be checked, at the expense of guaranteed free cells. This means that when placing ships it is necessary to install them in such a way that in case of their loss, to minimize the number of guaranteed free cells. As you remember, the battleship in the center of the field opens 14 fields for the enemy at once, but the battleship standing in the corner opens only 6 fields for the enemy:
Similarly, a cruiser standing in the corner, instead of 12 fields, opens only 6. Thus, having placed large ships along the field border, you leave more room for boats. Because there is no strategy to search for boats, the enemy will have to shoot at random, and the more free fields you have left by the time you catch the boats, the harder it will be for your opponent to win.
Below are three ways to accommodate large ships, which leave plenty of room for boats (marked in blue):
Each of the above arrangements leaves exactly 60 free cells for boats, which means that the probability of accidentally hitting the boat is 0.066. For comparison, the random placement of ships is worth mentioning:
With this arrangement, only 21 cells remain for the boats, which means that the probability of hitting the boat is already 0.19, i.e. almost 3 times higher.
In conclusion, I want to say that you should not spend too much time playing sea battle. I especially want to warn you against playing lectures. When I sat in Wabi Sabi and played a sea battle with my girlfriend, a waitress passed by and said that she played very well, because practiced a lot on pairs. Who knows what she would have worked if she had attended lectures at one time?
PS In the comments absolutely correctly indicate that there were already similar publications on Habré, it would be wrong not to put links to them:
habrahabr.ru/post/82221
Source: https://habr.com/ru/post/180995/
All Articles