Again "sea battle". Count the number of possible ship locations
Since the week of the "Sea Battle" on Habré continues, I will add my two cents.
When trying to find the optimal strategy for playing computer games, we quickly come to this approximation:
Suppose that the state of some cells we already know, and we want to make a move that brings us as close as possible to victory. In this case, it makes sense to choose a cell that is occupied by the enemy ship in the largest number of possible ship locations that do not conflict with the information available.
Indeed. If there is only one possible configuration, then we finish the game in one turn, shooting its ships in turns (we know the configuration!) If there are more configurations, then we need to reduce their number as much as possible, thereby increasing the amount of information we have. If we get into the ship, we will lose nothing (after all, the turn remains with us!), And if we miss, the number of remaining combinations will be the minimum possible after this turn.
')
It is clear that this is only an approximation to the optimal strategy. If the enemy knows about our plan, he will try to place the ships so that they do not fall into those cells where we will shoot at the beginning of the game. True, it will help him a little - we still at the end of the end will clamp it into a corner - but it is possible that a certain flexibility would not hurt us. In addition, it is possible that a well-thought-out series of moves, the first of which is not optimal, would lead to a better result. But for now we will not complicate the already difficult task, but try to calculate all the configurations and build a map of the probability of filling the field.
At first glance, the task seems overwhelming. The number of configurations appears to be of the order of 10 20 (in fact, they are somewhat smaller — closer to 10 15 ), so it will take too much time to complete a search. It is not better to go through the colorings of the field and leave only valid ones: all the same, we will have to look through every combination.
What else to try? Any Olympiad will immediately respond - dynamic programming. But how to organize it?
So, we will go from the top down. Suppose that the field we have is divided into two parts - part A consists of the first k lines, and part B from all the others. By filling in a part of a field, we call any coloring of its cells in two colors. The filling of the entire field is called correct, if the black cells form a set of ships that satisfies the rules (ships are straight, do not touch, their lengths form the desired set). Two fillings S1 and S2 of part A will be called equivalent if, for any filling T of part B, the combined fillings of the entire field S1 | T and S2 | T are correct or incorrect at the same time.
To solve the problem we have enough:
Suppose we have an unknown filling S of area A and a known filling T of area B. What do we need to know about S?
First, it's nice to have the full state of the last line. Only in this case will we be able to determine which cells of the first row of area B we can still occupy, and which not.
Secondly, you need to know how many and what finished ships in area A already have. We call the finished ship, which can no longer be extended to area B. In our case, these are either ships that do not have cells in the last row, or ships that lie entirely in it (and occupy two or more cells).
Third, about every ship that can still be extended to area B, we need to know its current length. These ships themselves are easily recognizable by the last line: they occupy one black cell in it, surrounded by white fields.
And that's all. The equivalence class is entirely determined by this data, and not even all their combinations are valid. Calculate how much happened:
Each class is thus described by 27 bits, and their total number is no more than 120 million. In fact, this estimate is greatly overestimated, and the program was able to find 1053612 grades.
Suppose we have a filling S, about which we know only the information described above. We want to extend it one more line: list all the fillings that can be obtained, define classes for them, and for each new class build a density map for the fillings.
First, let's see what lines we can add to our fill. The main criterion is known to all: the black cell of the new line cannot be adjacent diagonally to the black cell of the last line of S. Further, as we already know, in the new line there can not be too long ships. And yet, if one of the vertical ships has a length of 4, then it cannot continue on a new line either. The remaining restrictions are related to the recruitment of ships, and it is more convenient to check them later.
Enumerate all the lines that can be added. If the line has more than one unit in a row, then they form a horizontal ship - we immediately take it into account in the counters of completed ships. With isolated units there are three situations:
Now check if the set of lengths is valid. Let s1, s2, s3, s4 be the number of finished ships of length 1,2,3,4, respectively, and n1, n2, n3, n4 be the number of unfinished ships with corresponding lengths. So that the set does not contradict the conditions, the following is necessary:
Information for the new class is ready. To build a map for it, it is enough to copy the first lines of the old map, and in the next line, add the added bit line multiplied by the number of combinations. Maps of the same class, obtained from different configurations, add up.
After we added 10 lines to the initial empty configuration, we got a list of 1053612 classes, each with its own map. To get a map of all field configurations, we need to go through all these classes, “finish” unfinished ships, count the number of ships of each size, and if it is correct, then add the class map to the total amount.
For an empty 10x10 field, there are 1855545978831780 configurations, and the fill card looks like this (all numbers are divided by 10 9 ):
The fact that it is symmetrical indirectly confirms that there are no gross errors in the program :) The most filled cell is C1, the most unfilled cell is B2.
After the move to C1, the card will look like this:
The sequence of the “best moves” with constant blunders looks like this (see figure):
C1, J8, A8, H1, A4, J4, D10, G10, E1, D2, B3, A2, C9, B10, H9, I10, I7, J6, I5, H6, J2, I3, H4, G5, G2, F3, E4, B7, A6, B5, C6, C3, D4, D5, F6.
It can be seen that the program is not in a hurry to catch the battleships. By move 24, when the “diagonal” algorithm would have had the last move before the guaranteed hit, the number of ships remaining positions is approximately 240 * 10 9 , and for the “diagonal” algorithm it is 260 * 10 9 . The difference is small. It will be necessary to arrange a tournament between these algorithms to find out how important it is.
The optimal algorithm for the game of sea battle GORKOFF
The algorithm of the game in the "sea battle": the shelling of the enemy impersonalis
And older publications:
The theory and practice of the game "Battleship" - honestly born2fly
Sea battle with artificial intelligence - to be honest michurin
When trying to find the optimal strategy for playing computer games, we quickly come to this approximation:
Suppose that the state of some cells we already know, and we want to make a move that brings us as close as possible to victory. In this case, it makes sense to choose a cell that is occupied by the enemy ship in the largest number of possible ship locations that do not conflict with the information available.
Indeed. If there is only one possible configuration, then we finish the game in one turn, shooting its ships in turns (we know the configuration!) If there are more configurations, then we need to reduce their number as much as possible, thereby increasing the amount of information we have. If we get into the ship, we will lose nothing (after all, the turn remains with us!), And if we miss, the number of remaining combinations will be the minimum possible after this turn.
')
It is clear that this is only an approximation to the optimal strategy. If the enemy knows about our plan, he will try to place the ships so that they do not fall into those cells where we will shoot at the beginning of the game. True, it will help him a little - we still at the end of the end will clamp it into a corner - but it is possible that a certain flexibility would not hurt us. In addition, it is possible that a well-thought-out series of moves, the first of which is not optimal, would lead to a better result. But for now we will not complicate the already difficult task, but try to calculate all the configurations and build a map of the probability of filling the field.
At first glance, the task seems overwhelming. The number of configurations appears to be of the order of 10 20 (in fact, they are somewhat smaller — closer to 10 15 ), so it will take too much time to complete a search. It is not better to go through the colorings of the field and leave only valid ones: all the same, we will have to look through every combination.
What else to try? Any Olympiad will immediately respond - dynamic programming. But how to organize it?
We go from the top down. What information do we need?
So, we will go from the top down. Suppose that the field we have is divided into two parts - part A consists of the first k lines, and part B from all the others. By filling in a part of a field, we call any coloring of its cells in two colors. The filling of the entire field is called correct, if the black cells form a set of ships that satisfies the rules (ships are straight, do not touch, their lengths form the desired set). Two fillings S1 and S2 of part A will be called equivalent if, for any filling T of part B, the combined fillings of the entire field S1 | T and S2 | T are correct or incorrect at the same time.
To solve the problem we have enough:
- Describe all equivalence classes of fillings for part A
- For each class, calculate the number of different fillings, and for each cell of area A, indicate in what number of fillings it was black (we call this information the map of this class)
- Describe the recalculation of classes and their maps when adding a new line to area A.
Suppose we have an unknown filling S of area A and a known filling T of area B. What do we need to know about S?First, it's nice to have the full state of the last line. Only in this case will we be able to determine which cells of the first row of area B we can still occupy, and which not.
Secondly, you need to know how many and what finished ships in area A already have. We call the finished ship, which can no longer be extended to area B. In our case, these are either ships that do not have cells in the last row, or ships that lie entirely in it (and occupy two or more cells).
Third, about every ship that can still be extended to area B, we need to know its current length. These ships themselves are easily recognizable by the last line: they occupy one black cell in it, surrounded by white fields.
And that's all. The equivalence class is entirely determined by this data, and not even all their combinations are valid. Calculate how much happened:
- The last line: 10 bits, and not all options are possible: there can not be more than 4 units in a row, and there can not be two groups of 4 units (0111101111). Total turns 909 options.
- Already exhibited ships. From 0 to 4 single decks, from 0 to 3 double decks, from 0 to 2 three decks, 0 or 1 four decks. Only 120 options.
- For each isolated bit of the line - the number of cells in the corresponding vertical ship that fell into A: from 1 to 4. There are no more than 5 such ships, for a total of no more than 1024 variants.
Each class is thus described by 27 bits, and their total number is no more than 120 million. In fact, this estimate is greatly overestimated, and the program was able to find 1053612 grades.
Add a new line
Suppose we have a filling S, about which we know only the information described above. We want to extend it one more line: list all the fillings that can be obtained, define classes for them, and for each new class build a density map for the fillings.
First, let's see what lines we can add to our fill. The main criterion is known to all: the black cell of the new line cannot be adjacent diagonally to the black cell of the last line of S. Further, as we already know, in the new line there can not be too long ships. And yet, if one of the vertical ships has a length of 4, then it cannot continue on a new line either. The remaining restrictions are related to the recruitment of ships, and it is more convenient to check them later.
Enumerate all the lines that can be added. If the line has more than one unit in a row, then they form a horizontal ship - we immediately take it into account in the counters of completed ships. With isolated units there are three situations:
- In the last line, S was an isolated unit, and in the new line it is not in this place. This means that the ship is finished, and its length is added to the counter.
- In the new line there is an isolated unit, but in the last line S in this place was not. So, a new vertical ship has appeared, and its length is now equal to 1.
- An isolated unit is both in the last line S and in the new line. This means that the vertical ship continues and its length increases by 1.
Now check if the set of lengths is valid. Let s1, s2, s3, s4 be the number of finished ships of length 1,2,3,4, respectively, and n1, n2, n3, n4 be the number of unfinished ships with corresponding lengths. So that the set does not contradict the conditions, the following is necessary:
s1<=4 && s2<=3 && s3<=2 && s4+n4<=1 && (s3+s4+n3+n4)<=3 && (s2+s3+s4+n2+n3+n4)<=6 && (s1+s2+s3+s4+n1+n2+n3+n4)<=10 Information for the new class is ready. To build a map for it, it is enough to copy the first lines of the old map, and in the next line, add the added bit line multiplied by the number of combinations. Maps of the same class, obtained from different configurations, add up.
Ending
After we added 10 lines to the initial empty configuration, we got a list of 1053612 classes, each with its own map. To get a map of all field configurations, we need to go through all these classes, “finish” unfinished ships, count the number of ships of each size, and if it is correct, then add the class map to the total amount.
For an empty 10x10 field, there are 1855545978831780 configurations, and the fill card looks like this (all numbers are divided by 10 9 ):
438487 418064 475795 466986 459000 459000 466986 475795 418064 438487 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064 438487 418064 475795 466986 459000 459000 466986 475795 418064 438487
The fact that it is symmetrical indirectly confirms that there are no gross errors in the program :) The most filled cell is C1, the most unfilled cell is B2.
After the move to C1, the card will look like this:
334039 316782 362205 354834 348680 348723 354859 362278 316825 334105 316847 204441 234170 214857 214919 214952 214721 234125 204338 316830 362174 234066 286949 270246 273421 273609 270199 287338 234109 362286 354993 215372 270082 249099 252049 252445 248433 270251 214694 354875 347443 215675 272189 252807 255040 256554 252272 273744 214941 348764 344351 216423 272030 253365 252114 255722 251441 273431 214746 348625 351029 226597 265572 262005 251178 255339 249502 271093 215027 354867 347356 238783 245635 276238 258889 268837 266947 286297 234182 362174 342552 273993 227511 287231 237138 226857 216325 233431 204620 316794 292453 231475 0 269650 316361 349490 359545 360275 316193 333632
The sequence of the “best moves” with constant blunders looks like this (see figure):
C1, J8, A8, H1, A4, J4, D10, G10, E1, D2, B3, A2, C9, B10, H9, I10, I7, J6, I5, H6, J2, I3, H4, G5, G2, F3, E4, B7, A6, B5, C6, C3, D4, D5, F6.
It can be seen that the program is not in a hurry to catch the battleships. By move 24, when the “diagonal” algorithm would have had the last move before the guaranteed hit, the number of ships remaining positions is approximately 240 * 10 9 , and for the “diagonal” algorithm it is 260 * 10 9 . The difference is small. It will be necessary to arrange a tournament between these algorithms to find out how important it is.
Sea Battle Week
The optimal algorithm for the game of sea battle GORKOFF
The algorithm of the game in the "sea battle": the shelling of the enemy impersonalis
And older publications:
The theory and practice of the game "Battleship" - honestly born2fly
Sea battle with artificial intelligence - to be honest michurin
Source: https://habr.com/ru/post/181384/
All Articles