著者

Maxime Audinot Francois Bonnet Simon Viennot

雑誌

ゲームプログラミングワークショップ2014論文集

巻号頁・発行日

vol.2014, pp.67-74, 2014-10-31

---

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.