CTK Exchange
CTK Wiki Math
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "battleship game"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #520
Reading Topic #520
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

  Subject     Author     Message Date     ID  
battleship game japam May-28-04 TOP
  RE: battleship game sfwc May-31-04 1
  RE: battleship game roninkakuhito May-21-06 2
     RE: battleship game iliaden May-21-06 3
         RE: battleship game Graham C Jun-23-06 4
             RE: battleship game Behm Dec-20-07 5
                 RE: battleship game Glenn Chan Mar-08-08 6
                 RE: battleship game Don Jul-29-08 7
                     RE: battleship game Jeff Jun-17-10 8

Conferences | Forums | Topics | Previous Topic | Next Topic
sfwc
Member since Jun-19-03
May-31-04, 11:44 AM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
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
iliaden
Member since Aug-14-05
May-21-06, 11:29 PM (EST)
Click to EMail iliaden Click to send private message to iliaden Click to view user profileClick to add this user to your buddy list  
3. "RE: battleship game"
In response to message #2
 
   >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.
>

I disagree. My main goal is first to locathe the ships, then to destroy them. thus i am trying to hit a ship only once, then forget about it untill all other ships have been hit at least once.

Of course, this might be a mistake, but it's A strategy.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Graham C
Member since Feb-5-03
Jun-23-06, 01:51 PM (EST)
Click to EMail Graham%20C Click to send private message to Graham%20C Click to view user profileClick to add this user to your buddy list  
4. "RE: battleship game"
In response to message #3
 
   Isn't the game really poker-like - i.e. the optimal strategy depends on correctly reading and predicting your opponents' strategy. So that in a sense your best defensive strategy is not to have one - which would include not always placing at random.

(The best strategy placing in one game may well be to place them in exactly the same positions as for the previous one. As long as you don't go it often.)


  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

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK