@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00106500,
 author = {Maxime, Audinot and Francois, Bonnet and Simon, Viennot and Maxime, Audinot and Francois, Bonnet and Simon, Viennot},
 book = {ゲームプログラミングワークショップ2014論文集},
 month = {Oct},
 note = {Battleship is a two-player game, where each player tries to guess the positions of the opponent's ships. In this paper, we consider a simplified sub-problem, by assuming that the opponent places the ships randomly. Our goal is to compute the optimal deterministic strategy that sinks the ships with the smallest average number of shots. First, we describe algorithms to compute this exact minimal average number of shots. Our implementation on small grids allows us to show that greedy strategies are not always optimal. The usual grid used in the real game is too big for computing the exact optimal strategy, so in the last part of the paper, we show how to compute lower and upper bounds of the optimal average number of shots., Battleship is a two-player game, where each player tries to guess the positions of the opponent's ships. In this paper, we consider a simplified sub-problem, by assuming that the opponent places the ships randomly. Our goal is to compute the optimal deterministic strategy that sinks the ships with the smallest average number of shots. First, we describe algorithms to compute this exact minimal average number of shots. Our implementation on small grids allows us to show that greedy strategies are not always optimal. The usual grid used in the real game is too big for computing the exact optimal strategy, so in the last part of the paper, we show how to compute lower and upper bounds of the optimal average number of shots.},
 pages = {67--74},
 publisher = {情報処理学会},
 title = {Optimal Strategies against a Random Opponent in Battleship},
 volume = {2014},
 year = {2014}
}