posted
Ok, my 7 year old son just sunk my #$@# battleship.
We are talking the classic game of Battle Ship. We each place our 5 ships on our own 10 x 10 grid. Then we try to guess where our opponent put their ships, and hope that they don't find ours. Each ship straddles two to five sections of the grid, so if you hit a part of the ship, finding the rest is easy.
I have a very logical and formulated strategy ensuring that there are no wholes left in the grid where even his smallest ship may hide.
He shoots out totally at random. I mean a random number generator would get a headache trying to figure out where he was pulling the coordinates from.
So how come he wins as often as not.
Is there a better strategy, or is strategy in Battleship just another name for Dumb Luck?
OK Math-nerds. What is the best "Game Theory" for Battleship.
Posts: 11895 | Registered: Apr 2002
| IP: Logged |
posted
You should start with a search phase, where you just shoot randomly trying to find the enemy ships. During the search phase you should ignore half the board; if you colour it chess-board fashion, you can ignore the white or black squares, as you choose. Within that constraint, you should shoot at random; any pattern can be predicted (over a series of matches) by the opponent and taken advantage of when he palces his ships. For example, it is a totally losing strategy to shoot A1, B2, A3, B4..., because your opponent would just put all his ships down in the opposite corner. Then once you've found a ship, you shoot in all the places where it could still be. There is no strategy that will consistently beat this one, at least as Battleship is usually played.
My father, having learned the game in a smarter age, added some fillips that made it a little more interesting: You would fire a sequence of three shots, and your opponent would report "One hit on battleship, two misses", but would not tell you which of your shots was the hit. This made searching a little more interesting, although not very.
Posts: 10645 | Registered: Jul 2004
| IP: Logged |
posted
Did you ever do the little flotilla, with all the boats in one 5x5 square? It always worked against me, never for me. Posts: 11017 | Registered: Apr 2003
| IP: Logged |
posted
You could also add the rule that if you lose your battleship you also lose one shot, and if you lose your carrier you lose another. This makes it worth while to create a search grid that the big ships can't slip through at first, and mop up the smaller ones later when you've sunk the big ones. But as strategies go, this is not exactly very interesting.
Posts: 10645 | Registered: Jul 2004
| IP: Logged |
posted
I suspect that most people's placement is determined by personal preferences and theories far more than real attempts at optimal avoidance or randomness.
As such, the optimal strategies will vary by player, given a database of previous knowledge.
Without that knowledge, I suspect the optimal search strategy has the following properties:
1. It does not attempt to leave no holes for even his smallest ship. You'll spend too much time searching for the small ship in places that couldn't hold one of the bigger ships.
2. Starts in the center. There are more ways a ship could be in one of the more central holes than one of the edge area holes, due to the boundary.
3. Does eliminate all or almost all possible hiding places for ships of length four or more in the first pass.
4. In a good portion of the board eliminates hiding places for ships of length three or more right off the bat, and can be efficiently filled in to eliminate further spots for ships of three or more on the rest of the board.
5. Does not proceed uniformly off the board, because even for spaces that aren't made impossible, it will reduce the number of possible ways the ship could be in them. Thus it will sweep across the board first in large strides then filling in the intervals, targeting the highest probability spaces first before hitting the places that have had their possible orientations lowered by the previous placements.
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
Nope, still beneficial, but for subtle reasons.
Each placement on a wider search grid will eliminate more possibilities (and out of a smaller set, too) for the larger ships; you have a much higher probability of hitting a ship in the beginning with a wider search grid.
Now, as you fill the grid in to find the smaller ships (we'll assume that can be done optimally), it seems like they should converge to the same time (since by passing on the search for the smaller ships in the beginning, you've just put it off until now, unless you became lucky). But it doesn't, because each time you find a ship you reduce the search grid, so finding more ships earlier (which will happen with a properly chosen wider search strategy) is an improvement. Now, exactly what width of grid will be optimal, I'm not sure. My suspicion is three and a fraction, where some areas are grid 3 and some areas are grid 4.
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
For some reason, I'm ridiculously good at battleship, but I think that's only because I read my opponents particularly well (a thing I've picked up from chess, I think).
I read their level of intelligence in basic strategy, experience in this particular game, and then I try to get in their heads about how they would set up and how they'll go about fighting their opponent. MOST people will always attack in a style consistent with their own setup (but not the same locations, of course).
Mathematically, it's a boring guessing game, and the best strategy is to set up a checkerboard grid of some sort, based on diagonals. I usually start 3-8 squares off of a corner, go into the center, and created a lopsided X. Every 3-5 shots, I'll take a random shot according to a "new grid" I may have inadvertently created, and making sure to hit the outer edges.
My setup strategy is as random as possible. I try to avoid the outer square except to use it for the end of a ship pointing in. I use the next inner square often, and try to avoid the inner 12 squares. Bunches of more than 3 are never good, though 2 ships side by side can be gold if your opponent sinks one, because the other will likely be ignored until endgame.
Posts: 1314 | Registered: Jan 2006
| IP: Logged |
posted
When we were younger, my brothers and I came across an extremely complicated pencil-and-paper version of battleship. You had a certain number of points to spend on stuff like bombers, recon planes, etc. It was great fun.
Posts: 3546 | Registered: Jul 2002
| IP: Logged |
Printer-friendly view of this topic
![[Laugh]](graemlins/laugh.gif)
You got beat at Battleship.![[Grumble]](graemlins/grumble.gif)
