May 29, 2013 at 16:07Again "Sea battle". We count the number of possible ship locations
Since the week of "Sea battle" on Habré continues, I will add my two cents.
When trying to find the optimal strategy for playing for a computer, we quickly come to this approximation:
Suppose that we already know the state of some cells, and we want to make a move that brings us closer 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 contradict the available information
Indeed. If there is only one possible configuration, then we end the game in one turn, shooting his ships in turn (because 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 available to us. If we get into the ship, then we won’t lose anything (after all, the move remains with us!), And if we miss, the number of remaining combinations will be the minimum possible after this move.
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 the cells where we will shoot at the beginning of the game. True, this will help him a little - we still end up pinning him in a corner - but it is possible that some flexibility would not hurt us. In addition, it is possible that a thoughtful series of moves, the first of which is not optimal, would lead to a better result. But 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 unbearable. The number of configurations seems to be of the order of 10 20 (in fact, they are slightly smaller - closer to 10 15), so it will take too much time to completely bust. It’s not better to go through the coloring of the field and leave only the acceptable ones: anyway, we have to look at each combination.
What else to try? Any Olympiad will answer right there - dynamic programming. But how to organize it?
So, we will go from top to bottom. Suppose that our field is divided into two parts - part A consists of the first k lines, and part B consists of all the rest. Filling part of the field is any coloring of its cells in two colors. Filling the entire field is called correct if 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 it is enough for us:
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?
Firstly, 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 ones not.
Secondly, you need to know how many and which completed ships in area A already exist. Finished we mean a ship that can no longer be extended to area B. In our case, it’s either ships that do not have cells in the last line, or ships that lie entirely in it (and occupy two or more cells).
Thirdly, about each ship that can still be extended to area B, we need to know its current length. These ships themselves are easy to recognize by the last line: they occupy one black cell in it, surrounded by white fields.
And that’s it. The equivalence class is entirely determined by this data, and not even all of their combinations are valid. Let's calculate how much it turned out:
Each class is thus described by 27 bits, and their total number is not more than 120 million. In fact, this estimate is very high, and the program was able to find 1053,612 classes.
Suppose we have the filling S, about which we only know the information described above. We want to extend it by one more line: list all the fillings that can be obtained, define classes for them, and build a density map for each new class.
First, let's see what lines we can add to our filling. The main criterion is known to everyone: the black cell of the new line cannot be adjacent diagonally to the black cell of the last line S. Further, as we already know, in the new line there cannot be too long ships. And yet, if one of the vertical ships has a length of 4, then he cannot continue to a new line either. The remaining restrictions are related to the set of ships, and it is more convenient to check them later.
Iterate over all the lines that can be added. If there are more than one unit in a row in a row, then they form a horizontal ship - we immediately take it into account in the counters of finished ships. There are three situations with isolated units:
Now check if a set of lengths is valid. Let s1, s2, s3, s4 be the number of completed ships of length 1,2,3,4, respectively, and n1, n2, n3, n4 be the number of unfinished ships with the corresponding lengths. To ensure that the kit does not contradict the conditions, the following is necessary:
Information for the new class is ready. To build a map for it, just copy the first lines of the old map, and in the next line enter the added bit line multiplied by the number of combinations. Cards 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 the configurations of the field, we need to go through all these classes, “finish” the unfinished ships, calculate the number of ships of each size, and if it is correct, then add the class map to the total.
For an empty 10x10 field, 1855545978831780 configurations turned out, and the fill map 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 populated cell is C1, the most unfilled cell is B2.
After the move to C1, the card will take the following form:
The sequence of “best moves” with constant misses looks like this (see the 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 in no hurry to catch battleships. By the 24th move, when the "diagonal" algorithm would have left the last move before a guaranteed hit, the number of remaining ship locations 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 in order to find out how significant it is.
The optimal algorithm for playing sea battle GORKOFF
The algorithm for playing the sea battle: shelling the enemy impersonalis
And older publications:
Theory and practice of the game Sea battle - honestly born2fly
Sea battle with artificial intelligence - honestly michurin
When trying to find the optimal strategy for playing for a computer, we quickly come to this approximation:
Suppose that we already know the state of some cells, and we want to make a move that brings us closer 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 contradict the available information
Indeed. If there is only one possible configuration, then we end the game in one turn, shooting his ships in turn (because 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 available to us. If we get into the ship, then we won’t lose anything (after all, the move remains with us!), And if we miss, the number of remaining combinations will be the minimum possible after this move.
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 the cells where we will shoot at the beginning of the game. True, this will help him a little - we still end up pinning him in a corner - but it is possible that some flexibility would not hurt us. In addition, it is possible that a thoughtful series of moves, the first of which is not optimal, would lead to a better result. But 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 unbearable. The number of configurations seems to be of the order of 10 20 (in fact, they are slightly smaller - closer to 10 15), so it will take too much time to completely bust. It’s not better to go through the coloring of the field and leave only the acceptable ones: anyway, we have to look at each combination.
What else to try? Any Olympiad will answer right there - dynamic programming. But how to organize it?
We go from top to bottom. What information do we need?
So, we will go from top to bottom. Suppose that our field is divided into two parts - part A consists of the first k lines, and part B consists of all the rest. Filling part of the field is any coloring of its cells in two colors. Filling the entire field is called correct if 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 it is enough for us:
- Describe all padding equivalence classes for part A
- For each class, calculate the number of different fillings, and for each cell of area A, indicate how many fillings it was black (we call this information a map of this class)
- Describe the conversion 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? Firstly, 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 ones not.
Secondly, you need to know how many and which completed ships in area A already exist. Finished we mean a ship that can no longer be extended to area B. In our case, it’s either ships that do not have cells in the last line, or ships that lie entirely in it (and occupy two or more cells).
Thirdly, about each ship that can still be extended to area B, we need to know its current length. These ships themselves are easy to recognize by the last line: they occupy one black cell in it, surrounded by white fields.
And that’s it. The equivalence class is entirely determined by this data, and not even all of their combinations are valid. Let's calculate how much it turned out:
- The last line: 10 bits, and not all options are possible: there can not go more than 4 units in a row, and there can not be two groups of 4 units (0111101111). A total of 909 options.
- Already exposed ships. From 0 to 4 one-deck, from 0 to 3 two-deck, from 0 to 2 three-deck, 0 or 1 four-deck. Only 120 options.
- For each isolated bit of a line, the number of cells in the corresponding vertical ship falling into A: from 1 to 4. There are no more than 5 such ships, totaling no more than 1024 options.
Each class is thus described by 27 bits, and their total number is not more than 120 million. In fact, this estimate is very high, and the program was able to find 1053,612 classes.
Add a new line
Suppose we have the filling S, about which we only know the information described above. We want to extend it by one more line: list all the fillings that can be obtained, define classes for them, and build a density map for each new class.
First, let's see what lines we can add to our filling. The main criterion is known to everyone: the black cell of the new line cannot be adjacent diagonally to the black cell of the last line S. Further, as we already know, in the new line there cannot be too long ships. And yet, if one of the vertical ships has a length of 4, then he cannot continue to a new line either. The remaining restrictions are related to the set of ships, and it is more convenient to check them later.
Iterate over all the lines that can be added. If there are more than one unit in a row in a row, then they form a horizontal ship - we immediately take it into account in the counters of finished ships. There are three situations with isolated units:
- In the last line S there was an isolated unit, but in a new line in this place it is not. So the ship is finished, and its length is added to the counter.
- There is an isolated unit in the new line, but in the last line of S there wasn’t any in this place. So, a new vertical ship has appeared, and its length is now equal to 1.
- An isolated unit is in the last line of S, and in a new line. This means that the vertical ship continues, and its length increases by 1.
Now check if a set of lengths is valid. Let s1, s2, s3, s4 be the number of completed ships of length 1,2,3,4, respectively, and n1, n2, n3, n4 be the number of unfinished ships with the corresponding lengths. To ensure that the kit 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, just copy the first lines of the old map, and in the next line enter the added bit line multiplied by the number of combinations. Cards 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 the configurations of the field, we need to go through all these classes, “finish” the unfinished ships, calculate the number of ships of each size, and if it is correct, then add the class map to the total.
For an empty 10x10 field, 1855545978831780 configurations turned out, and the fill map 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 populated cell is C1, the most unfilled cell is B2.
After the move to C1, the card will take the following form:
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 “best moves” with constant misses looks like this (see the 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 in no hurry to catch battleships. By the 24th move, when the "diagonal" algorithm would have left the last move before a guaranteed hit, the number of remaining ship locations 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 in order to find out how significant it is.
Sea Battle Week
The optimal algorithm for playing sea battle GORKOFF
The algorithm for playing the sea battle: shelling the enemy impersonalis
And older publications:
Theory and practice of the game Sea battle - honestly born2fly
Sea battle with artificial intelligence - honestly michurin