Battleship
So this month I decided that I really wanted to focus on making some visualizations of data to practice using ggplot2 and Tableau. To begin I decided to take a look at a classic board game that I have enjoyed for may years: Battleship.
/pic288374.jpg)
Now I could have just made the visualization and posted it and been done (which will likely happen for many of them this month), but this one piqued my interest enough that I decided to a brief write up about it. I wanted to do a heat-map of a blank board. There are something like 1,925,751,392 different board states according to this table. Which is really too many to do by hand. So instead I decided to look the problem another way, by looking at each ship and the number of positions in which it could cover a given square.
I wish I could say I say down and immediately knew how to do this efficiency, but I used a very naive approach for the board of the ship of length 2. I simply started by counting how many ways I could put a destroyer on each square. Starting this process helped me realize that board has a symmetry in these positions, both vertical and horizontally, meaning I only had to figure out a quarter of the board. I did a lot of this work in excel, but realized that really the boards could be represented with matrices. I would take two matrices and add them together to create the quarter of the board. One matrix would be the horizontal alignment and the other the vertical, which is conveniently the transpose of the other.
In order to determine each of the rows of the matrix I needed to determine the rows/column values. I did this by creating the positions in a grid where a 1 represented a ship covering a square and a 0 was a free space. I then summed the columns and this would be the rows for my horizontal matrix.
The resulting matrices were these.
\begin{align*} V=
\begin{bmatrix}
1 &1 &1 &1 &1 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
\end{bmatrix} H=
\begin{bmatrix}
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
\end{bmatrix}
\end{align*}
Now I could have just made the visualization and posted it and been done (which will likely happen for many of them this month), but this one piqued my interest enough that I decided to a brief write up about it. I wanted to do a heat-map of a blank board. There are something like 1,925,751,392 different board states according to this table. Which is really too many to do by hand. So instead I decided to look the problem another way, by looking at each ship and the number of positions in which it could cover a given square.
I wish I could say I say down and immediately knew how to do this efficiency, but I used a very naive approach for the board of the ship of length 2. I simply started by counting how many ways I could put a destroyer on each square. Starting this process helped me realize that board has a symmetry in these positions, both vertical and horizontally, meaning I only had to figure out a quarter of the board. I did a lot of this work in excel, but realized that really the boards could be represented with matrices. I would take two matrices and add them together to create the quarter of the board. One matrix would be the horizontal alignment and the other the vertical, which is conveniently the transpose of the other.
In order to determine each of the rows of the matrix I needed to determine the rows/column values. I did this by creating the positions in a grid where a 1 represented a ship covering a square and a 0 was a free space. I then summed the columns and this would be the rows for my horizontal matrix.
The resulting matrices were these.
\begin{align*} V=
\begin{bmatrix}
1 &1 &1 &1 &1 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
\end{bmatrix} H=
\begin{bmatrix}
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
\end{bmatrix}
\end{align*}
I then did some simple matrix addition to get the resulting board.
\begin{align*}
\begin{bmatrix}
1 &1 &1 &1 &1 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
\end{bmatrix} +
\begin{bmatrix}
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
\end{bmatrix} =
\begin{bmatrix}
2 &3 &3&3&3 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
\end{bmatrix}
\end{align*}
\begin{align*}
Size 2 =
Size 3 =
\begin{bmatrix}
2 &3 &4&4&4 \\
3 &4 &5 &5 &5 \\
4 &5 &5 &5 &5 \\
4 &5 &5 &5 &5 \\
4 &5 &5 &5 &5 \\
\end{bmatrix}
Size 4 =
\begin{bmatrix}
2 &3 &4&5&5 \\
3 &4 &5 &6 &6 \\
4 &5 &6 &7 &7 \\
5&6 &7&8 &8 \\
5&6 &7&8 &8 \\
\end{bmatrix}
Size 5 =
\begin{bmatrix}
2 &3 &4&5&6 \\
3 &4 &5 &6 &7 \\
4 &5 &6 &7 &8 \\
5 &6 &7 &8 &9 \\
6 &7 &8 &9 &10 \\
\end{bmatrix}
\end{align*}
\begin{bmatrix}
1 &1 &1 &1 &1 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
2 &2 &2 &2 &2 \\
\end{bmatrix} +
\begin{bmatrix}
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
1 &2 &2 &2 &2 \\
\end{bmatrix} =
\begin{bmatrix}
2 &3 &3&3&3 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
\end{bmatrix}
\end{align*}
I then was able to do this for each of the sizes of ships.
\begin{align*}
Size 2 =
\begin{bmatrix}
2 &3 &3&3&3 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
\end{bmatrix}
2 &3 &3&3&3 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
3 &4 &4 &4 &4 \\
\end{bmatrix}
Size 3 =
\begin{bmatrix}
2 &3 &4&4&4 \\
3 &4 &5 &5 &5 \\
4 &5 &5 &5 &5 \\
4 &5 &5 &5 &5 \\
4 &5 &5 &5 &5 \\
\end{bmatrix}
Size 4 =
\begin{bmatrix}
2 &3 &4&5&5 \\
3 &4 &5 &6 &6 \\
4 &5 &6 &7 &7 \\
5&6 &7&8 &8 \\
5&6 &7&8 &8 \\
\end{bmatrix}
Size 5 =
\begin{bmatrix}
2 &3 &4&5&6 \\
3 &4 &5 &6 &7 \\
4 &5 &6 &7 &8 \\
5 &6 &7 &8 &9 \\
6 &7 &8 &9 &10 \\
\end{bmatrix}
\end{align*}
Which with the power of symmetry I was able to create full boards and then heat-maps of each type of ship.
I then combined these to create an overall heat-map for the classic game. A classic game each player is given 1 size 5 ship (Carrier), 1 size 4 ship (Battleship), 2 Sized 3 ships(Cruiser and Submarine), and 1 sized 2 ship (Destroyer). Combining these resulted in this visualization.
So to begin with it is always advisable to start by guessing a square in the middle, given no other information. This is where I intended on leaving this visualization, however, something about this problem grabbed my attention and I wanted to dig a little deeper. You can optimize your guessing a little bit more once you realize that each square correctly guessed can give you more information about adjacent squares. The best way to think about this is by looking at the board as a checker board. The smallest ship size is length 2 which means no matter how you position it, it will always cover a colored square and a blank square. When searching only guess on either colored squares or blank squares but never both, this reduces the number of cells to search by half. Combine this with the heat map above and you may find a spiraling outward pattern may be the most effective.
I did however notice something, due to the smallest ship size being size 2 and the parity this introduces to our system. We can see the information gain from a correct guess by using the heat map for ship size 2. A hit on the edge is more valuable than a hit in the middle as there are fewer directions that the ship can go. This means when positioning your boats you need to keep in mind the information gain that can be had when giving up a hit.
I would like to revisit this in the future to try to work out some more strategies.
Comments
Post a Comment