I'm writing AI for the game and encountered this article that helped me out. I'm not sure how the probability function is computed. Does it rely on some advanced math I'm not understanding or for each move program generates randomly lots of possible set ups and then computes chance by counting times ship is encountered on the given field?

  • 6
    I'm voting to close this question as off-topic because it's about understanding a blog post, not about software development concepts as explained in the help center. See also the Discuss this ${blog} meta-post which explains why asking about something someone else wrote does not generally make for good questions.
    – amon
    Jul 8 '15 at 13:16
  • @amon I beg to differ. The link helps explaining what the goal of the question is. I don't see how any of the points of the meta post (or its answer) apply here: This is neither a discussion, nor is it about opinions, nor is the material to broad or unclear. Imagine if markovcd only posted an image of the probability function from that blog and asked how to create it: it becomes clear that this is not about the blog post. The question is for an algorithm to construct a probability distribution. As the asker provided additional material to explain his goal, this deserves an upvote, not a close.
    – null
    Jul 8 '15 at 20:57
  • @null - relying upon information hidden behind a link makes for a poor question. Links go stale; information changes; and it forces the reader to make assumptions about what the OP did or did not understand within the linked information. The question could be made more constructive if relevant information was posted and the confusing aspect was clearly called out.
    – user53019
    Jul 9 '15 at 14:16

You enumerate every possible legal position that the largest (surviving) ship can be in. Call that N. Then for each cell, you count up how many of those positions include that cell. Call that c. Then your probability is c/N . You can deliberately targeting the largest ship as the probability map is more concentrated for that one, and therefore most likely to give a successful hint, although the authors continue to do the same for other ship sizes.

Whether this is a good measure is debatable - it assumes all remaining positions are equally likely, which in turn assumes your opponent scatters his ships at random. I suspect humans will tend to follow patterns they believe makes life difficult for the opponent, eg. not having touching ships (so that hitting one won't lead you into hitting another while in TARGET mode).

  • 1
    Note that it's excessively easy to calculate the cell-uses c for a single ship, since all rows and columns of the field are equivalent: we just slide the ship over each field in a row and count how often it was there. At the edges, this is once, twice, ..., until in the middle this is the length of the ship. So given a n-sized row and a s-long ship, for a zero-based coordinate i in the row we can calculate c as c = min(i + 1, s, n - i), for a coordinate (i, j) in the field as c = min(i+1, s, n-i) + min(j+1, s, n-j).
    – amon
    Jul 8 '15 at 13:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.