Then f(A) is the strategy which has the highest win rate against A.ĭefinition: a strategy is optimal if f(A) beats A with a probability of 0.5 or less. Since you're interested in attacking the 'best' strategy, you should probably view it adversarially: In particular, if no strategy is optimal, there is a theorem like: 'for any strategy A, there is a strategy B that beats it.' I'm not sure whether that's the case. The average goes up by approximately 9 million, but we lose at most 1% more of our games and win approximately 79% we'd usually lose).įrom here, it is likely that there are non-transitive strategies! That is, a triplet of strategies (A, B, C) where A beats B, B beats C, and C beats A. A worse average can still be a better strategy if you tend to beat your opponent more often (for example, hypothetically it takes 1000000000 moves more in one fairly unlikely game that occurs 1% of the time, but makes 1 fewer move on the other 99% of games where we were previously tied 80% of the time. Note that I'm not looking at the average time to sink all ships here- although it's easier to optimize, it's not what determines whether you'll win. One strategy 'beats' another if in a random game it is now likely that it sinks all ships before its opponent does.

A 'strategy' for battleship is a pair (P, C) where P is a probability distribution used to place your ships in the beginning of the game and C is a function that chooses (possibly probabilistically) what move to make next based on the results of moves so far from both players.

Best battleship layout