Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[eHalcyon]

And for the rest of you: why u no visit Canada?

Having acrophobia and living across the ocean is a nombo. I swear, that's the only reason!

That's not a good excuse.  Boats exist!

[KingZog3]

And for the rest of you: why u no visit Canada?

Having acrophobia and living across the ocean is a nombo. I swear, that's the only reason!

That's not a good excuse.  Boats exist!

We could also beam you here.

[Kirian]

And for the rest of you: why u no visit Canada?

Having acrophobia and living across the ocean is a nombo. I swear, that's the only reason!

Are there a larger than normal number of acronyms in Canada?

[KingZog3]

And for the rest of you: why u no visit Canada?

Having acrophobia and living across the ocean is a nombo. I swear, that's the only reason!

Are there a larger than normal number of acronyms in Canada?

No, we just have a lot of acrobats.

[shraeye]

I have not seen any set of rules that, when applied iteratively, solves any given uniquely solvable instance of Sudoku. Maybe you have a bad source of Sudoku boards. That being said, I agree that Sudoku gets old really fast.

I got pretty burnt out on Sudokus once; now I solve those and many other puzzles at nikoli.com as my daily brain work-out.  I'm pleasantly surprised to find out that I'm somewhat frequently in the top 25 solve times for sudoku puzzles.

[soulnet]

acrophobia

So, that's what that red A stands for? WOW, sorry for misinterpreting you all this time.

[blueblimp]

I was assuming that one worked out the rules for oneself We're a cut above the average forum when it comes to logic.

In that case, isn't it a puzzle of working out play rules? I thought the point that you were making is that if you know the play rules, then it's just about observation.

[DG]

Monopoly, Cluedo, and Battleships have plenty of strategy to work out in the first play as well.

[liopoil]

I've always wondered what optimal battleship play is. It's more complex than it seems. Of course, playing optimally against someone who plays with very little strategy will still only yield a win rate slightly above .5, but it seems interesting anyway.

[KingZog3]

I've always wondered what optimal battleship play is. It's more complex than it seems. Of course, playing optimally against someone who plays with very little strategy will still only yield a win rate slightly above .5, but it seems interesting anyway.

I think a checker board approach covers the most ground with the fewest pieces.

[liopoil]

I've always wondered what optimal battleship play is. It's more complex than it seems. Of course, playing optimally against someone who plays with very little strategy will still only yield a win rate slightly above .5, but it seems interesting anyway.

I think a checker board approach covers the most ground with the fewest pieces.

sure, but it's not that simple. Within the checkerboard, you should still spread out your moves. There is also strategy in placing your ships. I've searched the internet a bit and didn't find anything conclusive.

[Awaclus]

I find rock-paper-scissors strategy incredibly intriguing.

[KingZog3]

I find rock-paper-scissors strategy incredibly intriguing.

It's intriguing that there even is strategy. And tournaments.

[eHalcyon]

Read about the other 6 great gambits here!  Number 5 will blow your mind!

[Davio]

I've always wondered what optimal battleship play is. It's more complex than it seems. Of course, playing optimally against someone who plays with very little strategy will still only yield a win rate slightly above .5, but it seems interesting anyway.

I think a checker board approach covers the most ground with the fewest pieces.

sure, but it's not that simple. Within the checkerboard, you should still spread out your moves. There is also strategy in placing your ships. I've searched the internet a bit and didn't find anything conclusive.

The main problem with games like this is:

Let's say I devise an algorithm which plays optimally against a pseudo-random human ship placement (humans are bad at randomness so we get no clusters and everything spread out pretty evenly).
You could then devise a ship placement algorithm which preforms optimally against my devised algorithm.
Then I'd have to react to that with a new algorithm and so on.

To know which algorithm to use, I have to know what you're going to use. But if you say, select an algorithm at random, we're back to square 1 so I just end up with an algorithm which performs best against totally random ship placement. And I wonder whether such an algorithm exists.

[liopoil]

No matter what strategy I use the optimal setup strategy will be a weigthed random, even against a strategy that assumes the opponent is using a weigthed random. The optimal strategy would also take into account how well the opponent is doing.

[Kuildeous]

I've always wondered what optimal battleship play is. It's more complex than it seems. Of course, playing optimally against someone who plays with very little strategy will still only yield a win rate slightly above .5, but it seems interesting anyway.

I think a checker board approach covers the most ground with the fewest pieces.

Pretty much. I haven't played Battleship in several, several years, so I wonder if my strategy would change, but I did fairly well with the following plans:

* Attack in a checkerboard pattern so that there no launch more than two away from another launch. This ensures that a Destroyer could not hide in between attacks.
* If the Destroyer is destroyed, then spread the gaps out to no more than three away. If both Submarine and Cruiser are destroyed, then no more than four away. And if the carrier is somehow the only survivor, then no more than five away.
* Do not cluster ships next to each other. When a launch is a hit, then the next logical step is to orthogonally blast that piece of map. If he happens to hit the adjacent ship, then you've let your opponent know where two of your ships are with effectively one random launch.
* If I played against someone who didn't realize the checkerboard method works, then I would avoid letting him know that is my strategy by picking different points of the checkerboard to target. In other words, don't launch A1, C1, E1, etc., but instead launch C3, E7, H8. In the end, it becomes a checkerboard (unless I find that Destroyer first).
* Depending on how well I know the opponent, I could play mind games. Cluster the entire fleet in one tiny area so that most of his launches will miss, but when he hits a ship, he destroys it and possibly assumes that there are no other ships nearby. Of course, this fails spectacularly if he hits the others with incidental shots.

So, yeah, there is a strategy in Battleship, but it's not a real big thinker. I suppose that depends on how much you want to fake out your opponent. There is that.

[soulnet]

I don't think checkerboard is best. You want to find the big ships early, because they are easier and they provide more information. There is a subset of the checkerboard that is best to find the 4-length ship quicker. A simple example is going down diagonally from A1, A4, A7, D1, G1, etc, but there are some better than this because they are equally good at locating a 4-sized ship and better at locating a 3-sized one. However, there is likely a lot more than that.

Also, liopoil is completely right. A non-deterministic algorithm can easily be the optimal way of playing, even if the opponent knows you are playing it. The game is finite, zero-sum and can be considered perfect information (in the sense that, both players have the same info before ship placement, and after ship placement, the extra info of knowing where my own ships are does not matter at all against an optimally playing opponent)* so there is at least one Nash equilibrium for the game, thus, there is a randomized algorithm that plays perfectly and has a .5 expected winning rate against itself (obviously).

*We need to assume optimally playing, because the knowledge we may get from knowing our boats is an assessment on how close our opponent is to discover some boat. However, an opponent playing optimally would not play in such a way that his information is beneficial to us. I am not 100% sure of this last part, but still, even if it is not perfect information, it is close, and it is likely that the Nash equilibrium exists.

[blueblimp]

I don't think it matters whether it's perfect information for a Nash equilibrium to exist (and to be an optimal solution of a linear program). A way to see this is to recast battleship as a 2-player zero-sum simultaneous play game as follows. Suppose that each player uses a pure (i.e. non-random) strategy, so that each move is determined by the information that has been revealed to them so far in the game. Then you can think of the "game" as being the simultaneous choice of pure strategies before play begins. That falls into the theory of 2-player zero-sum simultaneous play games, which says that there is a pair of mixed (i.e. randomized) strategies for the players that is a Nash equilibrium, and they are given by an optimal primal-dual solution pair to a linear program.

(This doesn't help much with actually finding the solution, since the LP is computationally infeasible as formulated here, because there are too many pure strategies to consider.)

[soulnet]

I don't think it matters whether it's perfect information for a Nash equilibrium to exist (and to be an optimal solution of a linear program).

Wikipedia agrees with you. I would still like to know whether it is true that it is perfect information or not.

[blueblimp]

You want to find the big ships early, because they are easier and they provide more information.

I'm no battleship expert, but I propose the opposite: knowing where the smaller ships are provides you more useful information than knowing where the larger ships are, so you'd prefer to find them first. Intuitively, the information about small ship positioning is more useful because the smaller ships are harder to find, as you point out.

This gets to the same strategy conclusion as you got to, just with slightly different justification.

A little more precisely, here are some properties of the ideal checkboard-like pattern for finding a ship of length L:

• A ship of length L will intersect exactly one square in the pattern.
• A ship of length >L will intersect at least one square in the pattern, possibly more.
• The pattern occupies 1/L of the squares in the board if L evenly divides the board side length. Otherwise it's a little fewer.

Imagine that you're searching for a single ship, which has known length L. If you're using a checkerboard-like pattern, then because of property 1, you just need to find the one square in the pattern that intersects the ship. (Then you can sink the ship pretty quickly afterward.) You might as well search the pattern in random order, so you'll find the ship in expected (P+1)/2 tries if the pattern has P squares. P is inversely proportional to L, so the expected number of tries required to find a single ship is also inversely proportional to L.

Since the full game of battleship is at least as hard as finding the smallest ship, knowing where the smallest ships are is very helpful because you can make your search pattern more coarse. But if you're using a pattern for a ship of length 2 to find a ship of length 2, then for expected value it doesn't matter which order you test the squares as long as each square is in expectation visited with try (P+1)/2, so you might as well search in such a way that if you get lucky and find all the smallest ships early on, all the squares you searched are part of the coarser pattern you switch to at that point. (I think this is what you were saying in your post.)

For ships with powers of 2 lengths in a board with side lengths also powers of 2, it's pretty straightforward how to select subpatterns. When the ship lengths aren't powers of 2, it's not as easy. For example, if there are two ships, one length 2 and one length 3, then there's no ideal pattern for the length 3 ship that's a subpattern of any ideal pattern for the length 2 ship. So I guess you'd start where the patterns intersect, and if you haven't found the length 2 ship yet, then start looking at squares that are only in its pattern and hope you don't have to look at too many of them.

[soulnet]

I'm no battleship expert, but I propose the opposite: knowing where the smaller ships are provides you more useful information than knowing where the larger ships are, so you'd prefer to find them first. Intuitively, the information about small ship positioning is more useful because the smaller ships are harder to find, as you point out.

The premise makes no sense to me. Of course the position of a smaller boat is better to know, but since you need to find all boats, you cannot decide the order on which one would be better to know. The point about big boats is that they give more extra information, i.e., information that is useful to find other boats.

[blueblimp]

I'm no battleship expert, but I propose the opposite: knowing where the smaller ships are provides you more useful information than knowing where the larger ships are, so you'd prefer to find them first. Intuitively, the information about small ship positioning is more useful because the smaller ships are harder to find, as you point out.

The premise makes no sense to me. Of course the position of a smaller boat is better to know, but since you need to find all boats, you cannot decide the order on which one would be better to know. The point about big boats is that they give more extra information, i.e., information that is useful to find other boats.

It might just be that we mean something different by "useful". What I mean is, suppose there is an oracle that could tell you the position of one boat of your choice. I would always ask it for the position of the smallest boat.

I don't see how knowing the position of a big boat gives you extra information at all.

[navical]

I don't see how knowing the position of a big boat gives you extra information at all.

Some (many? all?) Battleship versions include a rule that different ships can't be in adjacent squares. So finding a big ship rules out a large area of the board.

[liopoil]

Soulnet says what I meant in better words.

I don't see how knowing the position of a big boat gives you extra information at all.

Some (many? all?) Battleship versions include a rule that different ships can't be in adjacent squares. So finding a big ship rules out a large area of the board.

Hmmm, I've never heard of that rule, and break it often.