{"id":5252,"date":"2021-04-17T10:26:28","date_gmt":"2021-04-17T17:26:28","guid":{"rendered":"https:\/\/mattfife.com\/?p=5252"},"modified":"2021-04-17T13:30:06","modified_gmt":"2021-04-17T20:30:06","slug":"optimal-battleship","status":"publish","type":"post","link":"https:\/\/mattfife.com\/?p=5252","title":{"rendered":"Optimal Battleship"},"content":{"rendered":"\n

Nick Berry, president of DataGenetics, meticulously analyzes different strategies<\/a> to play the classic board game Battleship (he also has done Chutes & Ladders<\/a>,\u00a0Candyland<\/a>\u00a0and\u00a0Risk<\/a>)<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

It’s a great example of how computer scientists often work. He explores a host of techniques and analyzes the results by calculating how often you’ll get a perfect game, median number of guesses, and how bad it gets in the worst case. <\/p>\n\n\n\n

He examines 4 major strategies:<\/p>\n\n\n\n

  1. Pure random searching<\/li>
  2. Hunt and Target – Hunt randomly until you get a hit, then proceed methodically to sink the hit ship.<\/li>
  3. Hunt and Target with parity – since the minimum length of a ship is 2 units, you need only search even or odd squares<\/li>
  4. Hunt and Target with parity combined with a probability density function<\/a>. <\/li><\/ol>\n\n\n\n

    His fourth approach is the most fascinating. The system calculates every possible configuration of the remaining ships, and then sums up the probability of a ship on each square. At the beginning, all the squares are basically equally probable, but as more and more guesses are made, the number of possible configurations decreases. If you continually calculate the sum of these possibilities, pick the square with the highest probability and repeat this process, you get significantly better results.<\/p>\n\n\n\n