Adaptive DOE to play "Battleship"

[#1]

Hi All,

  The other day my son asked to play the grid-paper version of "Battleship". Each person had 5 "ships" that were 5, 4, 3, 3, and 2 units in length (and one unit wide). The "ships" were placed on a 10 by 10 grid in X-Y space; each "ship" had a unique set of (x,y) coordinates. For example, one of the 3 unit "ships" could have coordinates (3,4), (4,4) and (5,4). No more than one "ship" can occupy the same (x,y) coordinate. "Ships" can run only vertical or horizontal -- no diagonal layout is allowed.

  We then took turns calling out pairs of coordinates (x,y) to see who got a direct hit on someone else's "ship". Each of us only had 16 turns to try and hit (or sink) as many "ships" of the other person. As we were going through this, I thought to myself that there must be a better approach to maximize ones chances of hitting (and/or sinking) another person's "ship" than just randomly calling out coordinates. Of course, you wouldn't call out a coordinate (x,y) that you've already used as you would know whether you hit a "ship" or didn't.

  At first, I thought that maybe the Custom Design platform would be the right way to go, but if you create a design where Y is "Hit" (0/1 for no/yes), and X1 = x and X2 = y coordinates (10-level discrete numeric), the platform will generate a design where it only uses the high and low levels for each X and Y. By the way, the model terms are just x, y, and the cross term x*y. So, unfortunately, the Custom Design doesn't work.

  The Full Factorial DOE platform won't work because it wants to do 100 runs (10x10 Factorial), and we only have 16 runs (tries) each.

  The RSM DOE platform only works on the high/low levels, and entering 1 and 10 for the low/high levels. The CCD design options don't really fill the space of the 10 by 10 grid where the "ships" would be placed -- too many center runs to be cover the grid space.

  The only other platform that would be applicable for this would be the Space Filling Design. Using the same low/high, 1/10 settings for x and y and "Hit" as the response (this would be binary, 0/1 for no/yes), I can get a DOE table with (x,y) pairings that fill the grid space. I'm not sure what the best choice would be for the space filling design methods, FFF or Uniform, or Latin Hypercube, etc.

  I think more importantly, is that the DOE is fixed, it's not "adaptable" in the sense that based on the result of the first run, how would the DOE then be modified to take into account the known information. Using the 3-unit boat coordinates from above, let's say my first run is to call out coordinates (3,4) and I get a hit. Knowing the layout of the "ships" as either being horizontal or vertical, my next call wouldn't be to follow the DOE at all, but rather call out (3,5), (3,3), (2,4), or (4,4) -- I would increase either x or y by one unit and see what the result is. And so on until the boat is sunk or moving on to the next possible starting coordinate.

  I'd like to find a more scientific method for generating an adaptive DOE that can optimize the 16 runs for generating "hits". Going off a static DOE won't do that because after each run, a coordinate is "used up", and I learn if it's a hit or not. Each run informs the n+1 subsequent run. As far as I know, there does not exist a DOE that can handle something like this, but I'm also not an expert in this field.

  Is random selection of a starting point the best one can do at "Battleship"? I don't think so, but I'm having a hard time figuring out how to have an adaptive DOE that basically has "if/then" statements in it so that it optimizes the use of my 16 tries while taking into account information from the previous step. It would be cool to have an "adaptable" DOE that would optimize your choices for each run so as to maximize your chance of winning in 16 tries.

Thanks for the discussion!,

DS

PS, in searching for JMP and "Battleship", I did find this post by @Jordan_Hiller that shows how JMP can be used to play different games, and @brady_brady wrote JSL code to actually play "Battleship". Very cool! Will be downloading that JSL soon!

[#2]

Fun idea, Diedrich!

Here's an old blog post on this topic, someone figured out how to compute the probability of a ship being on each square of the grid for any given game state. https://www.datagenetics.com/blog/december32011/ After that, you don't even need a model, you can just choose the most probable square. There are some machine learning projects out there as well, but that seems like overkill!

Jordan

[#3]

Hi @Jordan_Hiller ,

  Thanks for the link to the blog, I enjoyed the article.

  I generally understand the concept behind how they went about calculating the probability of a ship being in a certain square -- this would be different for each kind of ship. However, since the probability state for the board would change after each round of play, the choice for the next square to fire on changes, which to me is nothing more than a re-optimized space filling design that takes into account hits/misses/boat size/and number of runs left.

  The blog poster was able to generate an algorithm that can with the game in 34 moves, which is exactly twice the number of squares taken up by the boats. Presumably, it would be possible to generate an optimal decision path that could get the required number of moves to win closer to 17. Maybe not exactly 17, but very close.

  Certainly an ML/AI approach can build an algorithm to win the game, but I agree, that's overkill and not what I'm really after. I am more interested in maybe a blend of what the blog person did and utilizing a DOE. Clearly the probability density function for the game board is critical in making decision choices. But, could one modify that from a purely probability calculation to one which is based on an optimized space filling -- almost like feeding the board's probability function as a "weighting" function for the DOE such that the DOE would generate highest likely hits. It seems to me that generating the highest hit count first and then focusing on sinking would lead to a quicker win versus how the blogger did it, which was to focus on sinking a ship first before moving on to the hunt mode.

  Anyway, I found it interesting to consider and think about, and apparently others have, too!

Thanks!,

DS