A while back I found myself with some free time and looking for a new SQL challenge; the only caveat was that I wanted it to be something outside of the normal scope of coding in which I would typically engage. I pondered what would fall into this category and came to the conclusion that a game completely playable from within SQL Server Management Studio would be a great fit. After some careful consideration I decided that the classic game of Battleship would be an ideal candidate. The game is well known, fun, and somewhat lends itself to the natural design and output of SQL queries. So if you've ever wondered what happens when a SQL developer gets bored and is looking for something “exciting” to do, wonder no more…
Battleship is a two player game where the objective is to guess the location of an opponent’s fleet of naval ships hidden throughout an ocean grid. Each player takes turns selecting grid coordinates to fire upon, attempting to determine occupied squares and subsequently sink all of the ships within them.
Each player begins with a fleet of ships which must be placed within a grid and kept hidden from their opponent. They can be positioned either horizontally or vertically (but not diagonally) within the grid spaces. Ships can be situated alongside each other and touch, though they cannot occupy the same physical space and they cannot have any portion extending outside of the grid boundary.
Once each player’s ships have been deployed, the game proceeds in a series of rounds. At the start of each round, players select a grid coordinate to attack in an attempt to locate and sink their opponent’s fleet. The outcome of the shot will be conveyed as either “Hit”, “Miss”, or “Sunk”. The game is over when one player successfully sinks all of their opponent’s ships while still retaining some portion of their own fleet.
There are several variations to the game, but I decided to go with the set of rules for which I am most familiar:
The ocean grid for each player is 10 x 10 in size
Each player gets two grids: one to place their ships on and track their opponent’s shots, and one to track their own shots against their opponent
Each player is allowed one shot per turn, regardless of the shot's outcome
Opponents are informed whether or not their shot resulted in a hit, miss, or sinking (and in the case of a hit or sinking, the name of the ship which was impacted)
Each player starts with five ships, varying in type and the number of squares needed to occupy a position on the grid
Aircraft Carrier: 5 squares
Battleship: 4 squares
Destroyer: 3 squares
Submarine: 3 squares
Patrol Boat: 2 squares
Auto Ship Deployment:
Ships are automatically deployed for both the Human and Computer player. This makes the initial setup process far simpler when using a SQL interface (should you not like the deployment generated at the start of the game, simply re-run the code using the "new game" parameter to produce a different set of ship placements). The auto deployment will determine which ships to place where and whether or not to place them horizontally or vertically. As well, since some players' strategy includes not having ships touch borders and / or not having ships touch each other, each deployment will randomly decide whether or not to use either (or both) of these strategies for the Human and / or Computer player.
The computer AI has been developed to be competitive and present the human player with a decent challenge. Originally it used a basic spacing approach when hunting for ships combined with honing and general position elimination logic when a ship was found. This yielded an average of 49 shots to locate and sink an entire fleet. I decided to implement an additional process which took into consideration which areas of the grid were heavily fired upon versus those which still contained a large amount of open space. This brought the computer player’s average down to 44 shots. At this point I became curious as to what a typical average should be, and after scouring the Net I hit upon a great article by Nick Berry from his DataGenetics website (thanks Nick!). Using this, I modified my code to use an algorithm which creates a pseudo-probability density matrix. This brought the average shots down to 42, making the game quite challenging at times.
Starting The Game / Selecting Coordinates:
The only line of code you will need to deal with and modify is located at line 89 (the "SET @Pick_Human" portion). When starting a new game the variable must be set to NEW. From that point on you will need to populate it with your coordinate picks (for example: E05, J10, B07). Coordinate picks must be three characters in length (E5 is considered invalid, while E05 is considered correct).
At the start of a new game you will be presented with the following:
Two 10 x 10 grids (upper and lower)
The upper grid will be used to record your shots against the computer (it will start off blank and as the game proceeds it will become populated with hit and miss indicators, depending on the outcome of your shot)
The lower grid will display your ship placements and record “hit” and “miss” indicators from shots placed by your opponent
The status summary will show general game information applicable to each player (more on this below)
Upper grid at the start of a new game:
Lower grid at the start of a new game:
Status summary at the start of a new game:
As the game progresses, each of the grids will become peppered with hit and miss indicators (represented by an X or dot, respectively). As well, the most recent shot fired for both the human and computer player will be shown as either a hit (H) or a miss (M):
Upper grid during mid-gameplay:
Lower grid during mid-gameplay:
The status summary will also update with each round of shots. Below we see that the computer player’s last shot was on F09 which resulted in a hit on the Battleship, the computer has sunk the human’s Aircraft Carrier and Destroyer, 3 of 4 possible hits on the Battleship have been achieved, the Patrol Boat and Submarine have yet to be located, and a total of 21 shots have been fired up until this point:
When the game ends you will be shown the computer player’s remaining ship locations should you lose.
Upper grid, revealing the computer player's remaining ship location(s):
Lower grid, showing the final status of the human player's ships:
The status summary confirms that the computer player has successfully sunk all of the human player’s ships:
A game over indicator will also be displayed, confirming the winner and the number of shots taken to defeat their opponent:
I have to admit that I had a lot of fun working on this. It presented some unique challenges and was a change from my normal SQL routine. If you wish, please feel free to post your score (for first win and first loss) in the comments section of this article. I am curious to see how people fare against the computer AI.
Any friendly feedback is always welcome. Enjoy!