|
|
|
|
|
|
|
|
CTK Exchange
japam
guest
|
May-28-04, 12:06 PM (EST) |
|
"battleship game"
|
regarding to battleship,whats the best strategy for it, i think it is be related to the shape of the ships,maybe some modular arithmetic? is it in the puzzles pages?? |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
sfwc
Member since Jun-19-03
|
May-31-04, 11:44 AM (EST) |
|
1. "RE: battleship game"
In response to message #0
|
Ah, battleship. That takes me back. I haven't played battleship for years. So far as I am aware, the best strategy for battleship is unknown. Indeed, it appears to be one of those computationally very hard and not particularly elegant problems which could only be solved by 'brute force and ignorance', and where storing the solution would be quite a feat. However, the following, although clearly non optimal (many possible improvements spring to mind), seems to be quite good and simple enough to implement with a short program. To place your ships: Place the largest ship at random, then place the next largest ship at random in such a way that it does not intersect the first ship. Continue in this manner until all ships are placed. To make a shot: for each square on the board where you have not yet made a shot, calculate the expected number of battleships through that point, on the assumption that the battleships' locations are independant and that each such ship is uniformly distributed over all positions where it could be given your current information. These assumptions are, of course, false. But they are a good approximation to the truth, and they make the calculation easy. Pick at random between those squares which maximise this expectation. I suspect that a computer using this strategy would be better than most human players. But I would be happy to be proved wrong. It is not in the puzzles pages, because it isn't a very interesting puzzle. More of a game of skill and luck. Thankyou sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
roninkakuhito
guest
|
May-21-06, 05:30 PM (EST) |
|
2. "RE: battleship game"
In response to message #0
|
I think that ship placement should be random with these constraints. All ships are to be considered as boundries. All edges are to be considered as boundries. No ship shall be placed adjacent to any boundry other than itself. This is because when a given ship is struck once, your next moves are aimed at locating the rest of a ship. The four squares surrounding the strike are possibly optimal strike positions, so no other ship should be within the four squares that are potential search spots. Actual search patterns are something I am not sure about. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
|
Behm
guest
|
Dec-20-07, 02:57 PM (EST) |
|
5. "RE: battleship game"
In response to message #4
|
When on offense make a checker board, firing at random (don't start from the top left and make a checkerboard), until you sink the patrol boat. Which would look like this .0.0.0.0.0.0.0 0.0.0.0.0.0.0. .0.0.0.0.0.0.0 Then when all ships are 3 blocks or larger increase the spacing between the diagonal lines to two empty spaces. which would look like this .00.00.00.00 0.00.00.00.0 00.00.00.00. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Glenn Chan
guest
|
Mar-08-08, 10:11 PM (EST) |
|
6. "RE: battleship game"
In response to message #5
|
Behm has a good suggestion. I'd add my suggestions: You might want to search the center squares first. Suppose the battlefield was 3X3, and that there is only 1 ship and it takes up 2 squares. There are 12 possible positions for that ship. If you fire at the center square, you eliminate all but 8 positions. If you fire at the corner, you eliminate all but 10 positions. If you fire at an edge, you eliminate all but 9 positions. Because the ships can't be placed on a edge and wrap around to the other edge, there is a bias for ships to be located on center squares. ---------------- Non-mathematical considerations: 1- People probably do not place their ships randomly. e.g. in lotteries, the distribution of lottery picks is skewed towards certain numbers. In battleship, I suspect it's likely that people do not place their ships randomly. If I were playing, I might try to hide a ship in the corner. There may be a tendency not to cluster ships together. This is probably a smart idea anyways. If you hit a ship, you will eventually need to search and find the rest of the ship. If you cluster, the search might accidentally find the other ships in the cluster. But, there is also a small chance someone might do extreme clustering and put all five of their ships together. ---------------- You might be able to gain an edge by reading the other player. If you could do this, it may be by far the best strategy. ---------------- Should you try to sink a ship right away when you find it? I suspect the answer is usually yes. Suppose you've found three ships. By sinking them, you know the size of the last ship. And you can adjust your search pattern accordingly, since you know how big the gaps between your lines of searching need to be. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Don
guest
|
Jul-29-08, 12:53 PM (EST) |
|
7. "RE: battleship game"
In response to message #5
|
The checkerboard was once my preferred strategy, but I've recently come around to the opinion that it's inefficient. Your first strategy is guaranteed to locate all ships of size 2 or greater (all of them); your second strategy above is guaranteed to locate all ships of size 3 or greater. What I do now is this: .000.000.0 0.000.000. 00.000.000 000.000.00 .000.000.0 This is guaranteed to locate all ships of size 4 or greater, and I believe (but have not proved) that it's a more efficient search strategy than the simple checkerboard. This is because there's a greater than 50% chance that I find the destroyer (the size 2 ship) with this initial, coarse search. If I do, then I don't need to proceed to a checkerboard. If I don't find the destroyer, then I fill in the checkerboard as per your first strategy above. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
|
Jeff
guest
|
Jun-17-10, 06:17 AM (EST) |
|
8. "RE: battleship game"
In response to message #7
|
How about this: U: set of unknown (remaining) squares M: set of previous misses H: set of previous hits For every U(i,j) compute the possible number of ways that each of the 5 types of ships could lie on top of it, given your knowledge of previous hits H(i,j) and misses M(i,j). We can call this score N(i,j) Rank order all N(i,j) and consider only those U(i,j) that are tied for the higest score, N(i,j). Among these U(i,j); fire on the square that will give you the most valuable information. The way to do this is to recalculate N(i,j) for all squares within X squares of an edge assuming that you will miss. X is the length of you opponent's longest ship still afloat. A known miss or a sunken ship counts as an edge. Repeat |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|