Introduction: Voice-based Battleship Game for Arduino (with AI)

This Instructable explains how to build a voice-based Battleship game for Arduino. Arduino's moves are determined by an AI that approximates all possible ship positions. Thanks to the MOVI speech recognition board, no Internet or WiFi is required and it all fits neatly onto an Arduino UNO, powered by a 9V battery. No more buttons, no more fiddling with small game figures that get lost... See the video above for the result!

The voice control can be configured to other commands than the ones shown in the video above. MOVI also supports other languages, like Spanish and German. For more information on MOVI, check out their page.

This Instructable assumes basic familiarity with Arduino and electronic projects. Please check out the Arduino and the MOVI Instructable first, if you need to get familiar with these types of projects. Otherwise, let's go!

Step 1: Ingredients

To build the Battleship game you need:

  • An Arduino-compatible board, we used an Arduino Uno. An Arduino Due, Intel Edison, MicroChip WF32 or another compatible board has more memory and a faster CPU. This will improve the performance of the AI.
  • MOVI Speech Recognizer and Synthesizer shield for Arduino.
  • A loudspeaker that plugs into a headphone jack. Or for better speech recognition performance: A headset with a microphone.
  • A power supply, e.g. 12V 500mA or 4 AA alkaline batteries (rechargeables: use 5). We use a 9V battery here just to show it's possible.
  • Good old pen and paper to draw the ships. Optional: We use Wikipedia's template.
  • Optional: A laptop that can read and write SD cards. This allows to update MOVI's firmware to play game music (as shown in the video).

Step 2: Programming

  1. Follow the steps as outlined in MOVI's Instructable to setup your MOVI board with Arduino.
  2. Take your laptop and fire up your Arduino IDE. I prefer the early one: v1.0.x.
  3. Connect the laptop via USB to the Arduino board.
  4. If you have not already, download the MOVI library at http://www.audeme.com/downloads.html and install it. This project used library version 1.10 or later. For music, you need version 1.12 or later.
  5. Download the sketch below into the Arduino IDE, compile it, and upload it to the board.
  6. MOVI should now learn the Battleship sentences. It is important to have MOVI learn the sentences before connecting a battery as MOVI can take damage if the power supply is disconnecting while in training mode. Once MOVI has trained the sentences, the game will start.

If MOVI is not training sentences despite it being connected and the game starts without further training (and as a consequence doesn't work), try restarting the Arduino and MOVI and also following the messages in the Serial Monitor. This sketch uses more sentences than originally allowed by MOVI's specifications, so training appeared a bit shaky to me.

Once the sentences are trained, you can either play and be happy ;-) or continue in this Instructable for more information.

Step 3: Assembly

This step shows you how to disconnect the Battleship game and make it truly untethered. Make sure the Battleship sentences have been trained as described in the previous step. Then:

  1. Solder a headphone jack to a speaker.
  2. Connect the speaker.
  3. Use a 9V battery clip and connect a 9V battery to it.
  4. Connect the red wire (+) of the battery cables to VIN.
  5. Connect the black wire (-) of the battery clip to GND.
  6. MOVI should start. Just as shown in the video.

Step 4: Alternative: Headset

For better speech recognition results and/or not to disturb fellow citizens, you can also connect a headset as shown in the pictures. This is highly recommended as it can be frustrating when MOVI recognizes a coordinate wrongly because of some ambulance passing by outside.

Step 5: Rules of the Game

We recommend printing out and using Wikipedia's template but any piece of squared paper with a coordinate system will do. Also, get a pen or pencil.

The rules of the game are the turn-by-turn rules described on Wikipedia and are summarized as follows:

One player is you and the other player is Arduino. The game is played on four grids, two for each player. The grids are 10×10 and the individual squares in the grid are identified by letter and number. In this game, the NATO alphabet is used to encode the letter, e.g. "alpha 10" or "charlie 9". On one grid, the player arranges ships and records the shots by the opponent. On the other grid, the player records their own shots. Before the game begins, each player secretly arranges their ships on their primary grid. Each ship occupies a number of consecutive squares on the grid, arranged either horizontally or vertically. The number of squares for each ship is determined by the type of the ship. The ships cannot overlap (i.e., only one ship can occupy any given square in the grid) and around each ship is a 1-square buffer. The types and numbers of ships allowed are the same for each player. This game uses the 1990 Milton Bradley version of the rules which specify the following ships:

  • 1 ship of 5 squares,
  • 1 ship of 4 squares,
  • 1 ship of 3 squares,
  • 2 ships of 2 squares,
  • and 2 ships of 1 square.

After the ships have been positioned, the firing rounds of the game start. In each round, each player takes a turn to announce a target square in the opponent's grid which is to be shot at. The opponent announces whether or not the square is occupied by a ship: "Miss" is announced if no ship is hit. "Hit" is announced if a ship is hit but there are still unhit squares on the same ship, and "Sunk" is announced if a hit resulted in all squares of a ship being hit. The attacking player notes hit or miss on their own "tracking" grid in order to build up a picture of the opponent's fleet. After a player gets a hit, the player continues shooting until he or she gets a miss. When all of a player's ships have been sunk, the game is over and the opponent wins.

Step 6: Gameplay With Arduino

Arduino will ask to position the ships. After that, it's the user's turn. The user announces a coordinate in the form of a letter (NATO alphabet) and number combination e.g., "bravo 2".

Arduino will then respond with either "hit", "miss", or "hit and sunk". Arduino will also automatically detect a lost or won game and announce accordingly. If it's a miss, the turn goes to Arduino. Arduino will say a coordinate (based on it's estimation of the highest likelihood for a ship) and then waits for a user's response. Allowed user responses are:

  • "Miss" -- announces a miss
  • "Hit" -- announces a hit. That means a ship has been hit but not sunk.
  • "Sunk" -- announces a ship has been hit on all squares. Sunk must be announced instead of hit in this case.
  • "Repeat" -- asks Arduino to say the coordinates of the last move again.
  • "Pass" -- passes the turn to Arduino. Useful for allowing the computer to start the game.
  • "Surrender" -- quits a game with "game over" and starts a new game.

If the user announced "hit", "sunk", or "pass", Arduino will make the next move. If it's a "miss", it's the user's turn again.

Have fun! In case you do encounter any trouble, especially with the speech recognition, we recommend checking out MOVI's forum.

Step 7: Optional: Adding Music

Our demo video shows music being played at the beginning and end of the game. In order for this feature to be enabled, MOVI's firmware needs to be updated to at least v1.10 and MOVI's library should be 1.12 or higher.

The latest version of MOVI's Arduino library can always be found on github btw. To upgrade the firmware and install the music files follow this Instructable, except don't install the Spanish files (unless you want to change the language). Instead, put the following files on the SD card:

http://www.noiseforfun.com/waves/musical-and-jingles/NFF-bulletin.wavhttp://www.noiseforfun.com/waves/musical-and-jingles/NFF-bulletin.wav

and (use free download option): http://www.playonloop.com/2015-music-loops/facing-destiny/

Please respect copyright licenses, which depend on how you use the files and this program.

After you uploaded the files to the SDcard, uncomment the

#define PLAYMUSIC

command in the Battleship code and upload the sketch to the Arduino again.

Attachments

Step 8: Optional: Tune the AI

AI stands for "Artificial Intelligence" and is the part of the Arduino sketch that is concerned with coming up with Arduino's next move. If you open the Serial Monitor of your Arduino IDE with a connected Battleship board, you can observe the output of the AI. The image above shows an example. The first matrix shows Arduino's (supposedly hidden) playing field. If you want to cheat, all you have to do is hit the 4s. :-) After every move, Arduino also shows the user's playing field as estimated by the AI based on the previous moves. 0 stands for unknown, 1 for miss, 2 for hit and 4 for known sunk ship.

So how does the AI work and how can it be tuned?

The best way to estimate the next move would be to calculate the probabilities of all possible placements of the opponents' ships based on what was learned from previous moves and then select the square that has the highest probability. That's easier said than done though since there are some problems with this approach. First, it is currently unknown how to calculate the ship placement probabilities with an explicit formula. The reason for this is that Battleship can be reduced to "bin packing", which is NP complete [1]. Second, simulating all possible placements requires iterating through about 2 billion possibilities [2] which is prohibitive on a desktop computer but even more so on an Arduino.

Therefore, I have chosen to implement an AI based on stochastic simulation. Rather than systematically going through all possible configurations of the board which, as explained, would take way too much time and possibly more memory than is available on an Arduino, the algorithm creates a small random sample of all possible placements given the knowledge from previous moves. The hope is that the field with the highest probability of containing a ship will be found by approximating the likelihoods for each square with a small number of representative placements. In some quick experimental runs I found that 1000 placements usually creates a good approximation, more iterations are always better of course and everything below 100 iterations feels like the moves become random. Since I wanted this program to be able to run on an Arduino Uno, I chose 500 iterations, which creates a wait time of about 2-3 seconds. If you have a stronger board, like the Arduino Zero or Due, or are OK to wait a couple more seconds, I certainly recommend increasing the constant NUMITER in the sketch to 1000. Last but not least [1] also tells us that we cannot easily decide wether a placement with a number of ships will allow for more ships to be placed and/or how many possibilities there are for these ships. Therefore, I chose to have that decided randomly as well. The algorithm tries to place a new ship NUMPLACINGATTEMPTS times. I default that number to 100 because my trial runs showed that to be a good. A lose excuse for that number is that each ship has an expected 50 fields to be placed in and for each of them it's either horizontal or vertical. But again, it's a very wiggly excuse. The number is better explained with magic (and experimentation). In anyways, you can safe some time by setting this number down to a lower value, even though everything below 20 seemed unreliable. Or you can play it safe if you have a more powerful board and increase the number.

In anyways, it's worth noting, that Battleship AIs are constantly under development. People even have competitions about them.

References:

[1] Merlijn Sevenster: BATTLESHIPS AS DECISION PROBLEM, ICGA Journal, Sep 2004 https://pdfs.semanticscholar.org/b623/82bcebee19a7cfeb1cfc18e6b1b05c680dfb.pdf

[2] http://forums.xkcd.com/viewtopic.php?p=3186221

Microcontroller Contest 2017

Participated in the
Microcontroller Contest 2017