The basic idea for Over 9000 was inspired by a TopCoder marathon match, except that in their variation multiple shots were fired in a single turn and you were only told which ships were hit without knowing which shots were the hits, and board sizes could be much larger. I was curious to see how it would do and decided to implement it with a few modifications described below. For those who are interested, the problem statement can be found here and the editorial can be found here.
Over 9000 essentially uses a brute force strategy to choose the next place to fire. For each possible ship, try to place it on every possible location. If you can place it, increment a counter of every square the ship is on by 1. Thus, if we assume all layouts of a particular ship are equally likely, we can compute the probability that a given ship will be on a given square simply by dividing by the total number of possible layouts. Consider the example grid below, where 0 represents a known miss, a number from 1 to 5 represents a known hit, and x represents an unknown square (we will consider a smaller grid for simplicity):
xxx0x
4440x
xx0xx
x5xxx
xxx0x
Suppose we are considering ship number 3, with length 3. Here are the 7 possible locations:
3330x xxx03 xxx0x xxx0x xxx0x xxx0x xxx0x
4440x 44403 44403 4440x 4440x 4440x 4440x
xx0xx xx0x3 xx0x3 xx0x3 3x0xx xx0xx xx0xx
x5xxx x5xxx x5xx3 x5xx3 35xxx x5xxx x5333
xxx0x xxx0x xxx0x xxx03 3xx0x 3330x xxx0x
If we look at the top left corner, there is only one configuration, so the probability is 1/7. However, the middle of the right column has probability 3/7 and will thus be more likely to contain this ship, so if we were only trying to find this ship then it would be the best place to fire. However, we have five ships to consider, not only one, and we would like to find the probability of a given square containing any ship using our probabilities for each ship. We will have to make one more assumption to do this and assume that the ship locations are independent of each other. Of course, this is not true due to the constraint that no two ships can overlap, but it does give a good approximation. If you look at the example grid, you will notice that there is a hit on ship 5, making the surrounding locations less likely to contain ship 3.
To compute this probability, we cannot simply add the probabilities of each ship, as this will count some cases twice. Instead, we can compute easily the probability that there is no ship on a given square, as we can simply multiply the probabilities for each ship of that ship not being on a square due to our independence assumption. Since p(not X) = 1 - p(X), then if we define p(n) to be the probability of ship n being on a given square, then the probability of finding any ship on a given square is equal to
1 - (1 - p(1)) * (1 - p(2)) * ... * (1 - p(5)). Once we get the probability for each square, then we can simply pick the square with highest probability that we have not already tried and fire there.
Over 9000 also includes some modifications to this strategy to account for the assumption that all locations are equally likely. This is of course not the case, especially since many people kept the original layouts sent with BruteForce or created their own. To counter this, every square was weighted and when the probabilities were computed, they were multiplied by the weights before determining the maximum. Over 9000's weight grid was based on the observation that human players preferred to place ships on the sides, and thus it gave the squares on the sides a higher weight than the others. In addition, Over 9000 added a small random number to the final probabilities, which had the effects of breaking ties and creating more interesting games, though it likely decreased performance slightly due to non-optimal behavior, as only one shot is fired at a time. However, this did have the positive effect of having no definite worst-case enemy ship placement, as Over 9000 would no longer be deterministic.
There are still some improvements which can be made, however. One simple improvement is to keep track of the games you play and increase the values in your weight grid as you get hits in squares, giving better results against people who play a small set of layouts. Another improvement which can be made is to consider multiple ships at a time instead of one ship, which will help offset the independence assumption. Ideally, we would consider layouts of all ships at once instead of placing single ships, but this would of course take up too much time in the early stages of the game when there is little known information.
Bob uses the same strategy, except that Bob uses only the information that a square was a hit or a miss. Also, Bob does not use either of the modifications described two paragraphs ago.
With regard to ship placement, it would usually make little difference how your ships were placed as a whole, though it was often possible to look at other programs and determine the worst case placement against their program.
Over 9000 essentially uses a brute force strategy to choose the next place to fire. For each possible ship, try to place it on every possible location. If you can place it, increment a counter of every square the ship is on by 1. Thus, if we assume all layouts of a particular ship are equally likely, we can compute the probability that a given ship will be on a given square simply by dividing by the total number of possible layouts. Consider the example grid below, where 0 represents a known miss, a number from 1 to 5 represents a known hit, and x represents an unknown square (we will consider a smaller grid for simplicity):
xxx0x
4440x
xx0xx
x5xxx
xxx0x
Suppose we are considering ship number 3, with length 3. Here are the 7 possible locations:
3330x xxx03 xxx0x xxx0x xxx0x xxx0x xxx0x
4440x 44403 44403 4440x 4440x 4440x 4440x
xx0xx xx0x3 xx0x3 xx0x3 3x0xx xx0xx xx0xx
x5xxx x5xxx x5xx3 x5xx3 35xxx x5xxx x5333
xxx0x xxx0x xxx0x xxx03 3xx0x 3330x xxx0x
If we look at the top left corner, there is only one configuration, so the probability is 1/7. However, the middle of the right column has probability 3/7 and will thus be more likely to contain this ship, so if we were only trying to find this ship then it would be the best place to fire. However, we have five ships to consider, not only one, and we would like to find the probability of a given square containing any ship using our probabilities for each ship. We will have to make one more assumption to do this and assume that the ship locations are independent of each other. Of course, this is not true due to the constraint that no two ships can overlap, but it does give a good approximation. If you look at the example grid, you will notice that there is a hit on ship 5, making the surrounding locations less likely to contain ship 3.
To compute this probability, we cannot simply add the probabilities of each ship, as this will count some cases twice. Instead, we can compute easily the probability that there is no ship on a given square, as we can simply multiply the probabilities for each ship of that ship not being on a square due to our independence assumption. Since p(not X) = 1 - p(X), then if we define p(n) to be the probability of ship n being on a given square, then the probability of finding any ship on a given square is equal to
1 - (1 - p(1)) * (1 - p(2)) * ... * (1 - p(5)). Once we get the probability for each square, then we can simply pick the square with highest probability that we have not already tried and fire there.
Over 9000 also includes some modifications to this strategy to account for the assumption that all locations are equally likely. This is of course not the case, especially since many people kept the original layouts sent with BruteForce or created their own. To counter this, every square was weighted and when the probabilities were computed, they were multiplied by the weights before determining the maximum. Over 9000's weight grid was based on the observation that human players preferred to place ships on the sides, and thus it gave the squares on the sides a higher weight than the others. In addition, Over 9000 added a small random number to the final probabilities, which had the effects of breaking ties and creating more interesting games, though it likely decreased performance slightly due to non-optimal behavior, as only one shot is fired at a time. However, this did have the positive effect of having no definite worst-case enemy ship placement, as Over 9000 would no longer be deterministic.
There are still some improvements which can be made, however. One simple improvement is to keep track of the games you play and increase the values in your weight grid as you get hits in squares, giving better results against people who play a small set of layouts. Another improvement which can be made is to consider multiple ships at a time instead of one ship, which will help offset the independence assumption. Ideally, we would consider layouts of all ships at once instead of placing single ships, but this would of course take up too much time in the early stages of the game when there is little known information.
Bob uses the same strategy, except that Bob uses only the information that a square was a hit or a miss. Also, Bob does not use either of the modifications described two paragraphs ago.
With regard to ship placement, it would usually make little difference how your ships were placed as a whole, though it was often possible to look at other programs and determine the worst case placement against their program.
No comments:
Post a Comment