Optimal Strategies against a Random Opponent in Battleship

• Item type: Symposium(1)
• 公開日: 2014-10-31
• タイトル: Optimal Strategies against a Random Opponent in Battleship
• タイトル / 言語: en
• タイトル: Optimal Strategies against a Random Opponent in Battleship
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Departement Informatique et Telecommunications, ENS Rennes, France
• 著者所属: School of Information Science, JAIST, Japan
• 著者所属: School of Information Science, JAIST, Japan
• 著者所属(英): en
• 著者所属(英): Departement Informatique et Telecommunications, ENS Rennes, France
• 著者所属(英): en
• 著者所属(英): School of Information Science, JAIST, Japan
• 著者所属(英): en
• 著者所属(英): School of Information Science, JAIST, Japan
• 著者名: Maxime, Audinot; Francois, Bonnet; Simon, Viennot
• 著者名(英): Maxime, Audinot; Francois, Bonnet; Simon, Viennot
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌情報: ゲームプログラミングワークショップ2014論文集; 巻 2014, p. 67-74, 発行日 2014-10-31
• 出版者 / 言語: ja
• 出版者: 情報処理学会