Battleships
Battleships is an excellent, mid level introduction to developing game playing bots.
More complicated than Noughts and Crosses, but less of a challenge than Travelling Sales Drone, Battleships strategy is more easily defined, and, ultimately, easier to implement.
Play against one of our Housebots, or, play against your own bots or your friends bots. The aim of the game is to sink your opponent's ships before they sink yours. First you both place your ships on your side of the board. Ships must fit entirely on the board, they cannot overlap one another or be placed on land.
Once you have both placed your ships you take turns choosing a location on your opponent's board to fire at, you cannot fire at the same place twice. Your shot can result in either missing all ships, hitting a ship, or sinking a ship.
The first player to sink all of their opponent's ships will win the game. If the Game Style you are playing consists of more than one deal, then the player who has won the most games from the total number of deals will win the game.
Once you are ready to start improving your bot you should draw your attention to the calculate_move() function, this is where all the action happens. This function is called every time the server wants you to make a move. It receives a dictionary of information containing the state of the game, namely the gamestate. For greater detail on the contents of the gamestate check out the Understanding The Gamestate section of our Battleships Quick Reference Guide.
From this information it is your task to determine two things:
- 1.Which round you are in.
- 2.What your move for this round is going to be.
You can specify your move by returning a valid dictionary of the form specified in the Making A Valid Move section of our Quick Reference Guide from the calculate_move() function.
For example:
def calculate_move(gamestate):
if gamestate["Round"] == 0: # If we are in the ship placement round
# The Placement list adds ships in the order that the ships are
# listed in the Game Style e.g. 5,4,3,3,2 places the ship of length
# 5 first, the ship of length 4 second, the ship of length 3 third.
#
# This function does not check for any land and, so, should be used
# with a Game Style that does not include land.
move = {
"Placement": [
{
"Row": "A",
"Column": 1,
"Orientation": "H"
},
{
"Row": "B",
"Column": 6,
"Orientation": "V"
},
{
"Row": "C",
"Column": 1,
"Orientation": "H"
},
{
"Row": "D",
"Column": 1,
"Orientation": "H"
},
{
"Row": "E",
"Column": 1,
"Orientation": "V"
}
]
}
else: # If we are in the ship hunting round
move = {
"Row": "B",
"Column": 4
}
return move
Here is an example of a function that takes into account land to ensure that the move is valid:
def shipPlacement(gameState):
move = [] # Initialise our move list
# Start in the top left corner
start = (0,0)
row = 0
column = 0
for i in gameState["Ships"]: # For every ship we need to place
space = 0
start = (row,column) # Start trying to find room at the current row and column
while space < i: # Until we find enough room to fit the ship keep on looking
if column >= len(gameState["MyBoard"][0]): # If we have reached the end of a row without finding enough room
row += 1 # Move to the next row down
column = 0 # Start at the beginning of the row
space = 0 # Reset the amount of space we have found on the row since the last obstacle
start = (row, column) # Initialise the potential start location for our ship
if gameState["MyBoard"][row][column] == "": # If the current cell is empty
space += 1 # Increment the amount of space we have found on the row since the last obstacle
column += 1 # Move to the next column along
else: # If there is something blocking a ship being placed
space = 0 # Reset the amount of space we have found on the row since the last obstacle
column += 1 # Move to the next column along
start = (row, column) # Reset the potential start location for our ship
# If we have found enough room to place our ship
shipPlace = BATHelperFunctions.translateMove(start[0], start[1]) # Call the translateMove hepler function with our coordinates to convert it to a valid move format
shipPlace["Orientation"] = "H" # Set the orientation we wish to place our ship as horizontal
move.append(shipPlace) # Add this ship placement to our move list
# Once we have added all of our ships
return {"Placement": move} # Return the valid placement move
Let’s say we would like to implement the following strategy:
- 1.In the first round we will just randomly place our ships.
- 2.In the second round if we haven't hit any ships we will randomly guess a location in the sea.
- 3.If we have hit a ship we will randomly choose one of the adjacent tiles.
- 4.If we are playing the particular bot “Barney01”, we will guess around the edges of the board.
We will make use of the built in helper functions from the battleships_helper_function module.
There is a helper function called deployRandomly() that we can use to randomly place our ships.
There is also a helper function called chooseRandomValidTarget() that we can use to randomly guess a location in the sea.
You can read more about the helper functions in the Helper Functions section of our Quick Reference Guide
The code looks like the following:
import BATHelperFunctions # Allows us to use the helper functions
from random import choice # So we can randomly choose an element from a list
from random import randint # So we can randomly pick a number
def calculate_move(gamestate):
if gamestate["Round"] == 0: # If we are in the ship placement round
move = BATHelperFunctions.deployRandomly(gamestate) # Randomly place your ships
else: # If we are in the ship hunting round
for i in range(len(gamestate["OppBoard"])):
for j in range(len(gamestate["OppBoard"][0])): # Look through every cell on the board
if gamestate["OppBoard"][i][j] == "H": # If it has been hit
if i > 0 and gamestate["OppBoard"][i-1][j] == "": # Try and guess above
return {"Row": chr(i + 64), "Column": j + 1}
elif i < len(gamestate["OppBoard"])-1 and gamestate["OppBoard"][i+1][j] == "": # Otherwise try and guess below
return {"Row": chr(i + 66), "Column": j + 1}
elif j > 0 and gamestate["OppBoard"][i][j-1] == "": # Otherwise try and guess left
return {"Row": chr(i + 65), "Column": j}
elif j < len(gamestate["OppBoard"][0])-1 and gamestate["OppBoard"][i][j+1] == "": # Otherwise try and guess right
return {"Row": chr(i + 65), "Column": j + 2}
# If there are no hit ships
if gamestate["OpponentId"] == "Barney01": # If we are playing against Barney01
move = guess_edges(gamestate) # Call our guess_edges function to choose a target on the edge of the board if available
else:
move = BATHelperFunctions.chooseRandomValidTarget(gamestate) # Randomly fire at valid sea targets
return move
def guess_edges(gamestate):
count = 0
while count < 50: # While we haven't given up trying to find a valid edge
(row, column) = choice( # Randomly choose one of the following:
[
(0, randint(0, len(gamestate["OppBoard"][0])-1)), # A random cell along the top edge
(len(gamestate["OppBoard"])-1, randint(0, len(gamestate["OppBoard"][0])-1)), # A random cell along the bottom edge
(randint(0, len(gamestate["OppBoard"])-1), 0), # A random cell along the left edge
(randint(0, len(gamestate["OppBoard"])-1), len(gamestate["OppBoard"][0])-1) # A random cell along the right edge
]
)
if gamestate["OppBoard"][row][column] == "": # If the move is valid
return {"Row": chr(row + 65), "Column": column + 1} # Set values to a valid move
else: # Otherwise increase number of attempts by one
count += 1
# If we have given up trying to find a valid edge
return BATHelperFunctions.chooseRandomValidTarget(gamestate) # Randomly fire at valid sea targets
This code is inefficient, see if you can improve its performance and its strategy!
Also you may like to edit the method play_game() from the battleships_layout.py module. The method is called during both player's turns. To maximise your efficiency, you may like to do some processing here while your opponent calculates their move. In particular you may want to add code to the following section:
while True:
if self.game_cancelled:
break
if game_state['IsMover']:
move = battleships_move.calculate_move(game_state)
move_results = self.make_move(move)
if move_results['Result'] != 'SUCCESS':
break
game_state = move_results['GameState']
else:
# ---- Code here will be called on your opponent's turn ----
# ----------------------------------------------------------
poll_results = self.poll_for_game_state()
if poll_results['Result'] != 'SUCCESS':
break
game_state = poll_results['GameState']
if game_state['GameStatus'] != 'RUNNING':
break
Here are some suggestions of strategies to improve your bots performance.
There are many different ways to arrange your ships at the start of a game. If you choose the same locations every time, your opponent will soon realise and start guessing accordingly. One strategy is to randomly place your ships each game, this is a massive improvement. (But still isn't perfect) You can use the inbuilt helper function, deployRandomly() to achieve this. See if you can think of a better solution though.
In most of our Game Styles there are dozens of possible cells to fire at, if you follow a pattern to determine where to fire next your opponent may be able to place his ships to avoid your guesses. Add some randomness to your shots to prevent this exploit. Use the chooseRandomValidTarget() helper function if you want completely random shots, however this on its own is not a good strategy either.
What are the opponent’s ship positions likely to be, based on probabilities and history?
The probability of a randomly placed ship being in a certain position on the board isn't the same for all locations. Calculate the probability distribution of ships appearing in each location and you will be able to make more educated guesses. Some positions may never be able to hold a ship, so don't waste your time guessing there!
To improve your guesses even further try remembering your opponents and where they placed their ships. You might be able to discern a pattern! For example at the end of each game you could record your opponent's name and the locations of their ships (assuming you know where they are) and using this you could construct a table of probabilities describing the likelihood of each player placing their ships in given locations. Maybe one of your opponent's regularly places his ships on the edges of the board, if you recognise this you could immediately start guessing the edges of the board first next time you play against them. See the case study talking about this on our Adding Intelligence To Your Bot page.
There are plenty of techniques to reduce the maximum number of moves needed to finish a game of battleships. Some are obvious, like guessing near the location of a hit for the rest of the ship or not guessing in a location where a ship wouldn't be able to fit, others are less obvious. See if you can implement them all.
Example gamestate JSON
{
'Ships': [5, 4, 3, 3, 2],
'IsMover': True,
'Round': 1,
'ResponseDeadline': 1543861722513,
'MyScore': 0,
'OppScore': 0,
'MyBoard': [
['L', 'L', '0', 'H0', 'H0', 'H0', '0', ''],
['L', 'L', '1', 'H1', 'H1', 'H1', '', ''],
['L', 'L', '', 'M', '', '', '', ''],
['L', 'L', '', '', '', '', '', ''],
['L', 'L', 'L', 'L', '', '', '', ''],
['L', 'L', 'L', 'L', '', '', '4', '2'],
['', '', '3', '3', '3', '', '4', '2'],
['', '', '', 'M', 'M', '', '', '2']
],
'OppBoard': [
['L', 'L', '', '', '', '', '', ''],
['L', 'L', '', '', '', '', '', ''],
['L', 'L', 'M', '', '', '', '', 'M'],
['L', 'L', '', '', 'H', 'H', '', ''],
['L', 'L', 'L', 'L', '', 'H', 'M', ''],
['L', 'L', 'L', 'L', '', '', '', ''],
['', 'M', '', '', '', '', '', 'M'],
['', '', '', '', '', '', 'M', '']
],
'GameStatus': 'RUNNING',
'GameId': 2398045,
'OpponentId': 'housebot-practise'
}
A description of each field in the gamestate.
Key | Description |
Ships | A list of integer lengths of ships that both you and your opponent are expected to place on the board. |
IsMover | A Boolean value indicating whether it is your turn to move. It will always be true when in the calculate_move() function. (Delve deeper into the code if you want to do some processing during your opponent's turn.) |
Round | An integer value of 0 or 1, with 0 representing the ship placement round and 1 representing the ship hunting round. |
ResponseDeadline | The epoch time, in milliseconds, that a successful move has to be sent and received by to prevent you from timing out. |
DealNumber | Which deal you are up to in the match, this key only appears when the value of DealsTotal is greater than 1 |
DealsTotal | The total number of times you are going to play a whole game of Battleships in this match, this key only appears when the value is greater than 1 |
MyScore | Your current score in this game, increases by one for every deal you win. The player with the largest score at the end wins. |
OppScore | Your opponent's current score in this game, increases by one for every deal they win. The player with the largest score at the end wins |
MyBoard | A 2-dimensional array of strings representing the state of your board |
OppBoard | A 2-dimensional array of strings representing the state of your opponent's board, with their ships hidden of course |
GameStatus | A string that will have value "RUNNING" if the game is in progress or a reason the game has ended otherwise |
GameId | An integer representing the unique game id for the current game |
OpponentId | A string containing the name of your opponent |
The strings in your board can contain the following values:
- "" - A cell that hasn't been hit that contains nothing on your board, or contains unknown on your opponent's board.
- "L" - A cell containing land that hasn't been hit.
- "M" - A cell containing nothing that has been hit.
- "LM" - A cell containing land that has been hit. (Why are you firing at land?)
- "H" - A cell on your opponent's board containing a ship that has been hit.
- "Hx" - A cell on your board containing ship number x that has been hit.
- "Sx" - A cell on either player's board containing ship number x that has been sunk.
- "x" - A cell on your board containing ship number x.
Depending on which round you are in the value you have to return from the calculate_move() function is as follows:
- If you are in the ship placement round your move should be a dictionary with key name 'Placement' and value Move. Move is a list of dictionaries, one for each ship, with the following key value pairs:
- 'Row' which takes values 'A','B',etc.
- 'Column' which takes values 1,2,etc.
- 'Orientation' which take values 'H' or 'V'.
- If you are in the ship hunting round your move should be a dictionary with the following key value pairs:
- 'Row' which takes values 'A','B',etc.
- 'Column' which takes values 1,2,etc.
Here is an example of a valid ship placement move:
# The Placement list adds ships in the order that the ships are
# listed in the Game Style e.g. 5,4,3,3,2 places the ship of length
# 5 first, the ship of length 4 second, the ship of length 3 third.
#
# This function does not check for any land and, so, should be used
# with a Game Style that does not include land.
{"Placement": [
{
"Row": "A",
"Column": 1,
"Orientation": "H"
},
{
"Row": "B",
"Column": 6,
"Orientation": "V"
},
{
"Row": "C",
"Column": 1,
"Orientation": "H"
},
{
"Row": "D",
"Column": 1,
"Orientation": "H"
},
{
"Row": "E",
"Column": 1,
"Orientation": "V"
}
]
}
Here is an example of a valid ship hunting move
{
"Row": "B",
"Column": 4
}
- deployRandomly(gamestate) - Given the current gamestate, returns a valid move that deploys all the ships randomly on a blank board.
- deployShip(i, j, board, length, orientation, ship_num) - Returns whether a given location (i,j) and orientation ("H", "V") can fit a given ship (ship_num) onto given board and, if it can, updates the given board with that ship's position.
- chooseRandomValidTarget(gamestate) - Given the current gamestate, returns a valid move that randomly guesses a location on the board that hasn't already been hit.
- shipsStillAfloat(gamestate) - Given the current gamestate, returns a list of the lengths of your opponent's ships that haven't been sunk.
- selectUntargetedAdjacentCell(row, column, oppBoard) - Returns a list of cells adjacent to the input cell that are free to be targeted (not including land).
- translateMove(row, column) - Given a valid coordinate on the board returns it as a correctly formatted move.
- Ship placement round - The first move in a game of battleships where you choose where you wish to place your ships.
- Ship hunting round - All subsequent moves where you guess a location you think your opponent's ships may be.
- Epoch time - The number of seconds (or in our case milliseconds) that have elapsed since January 1 1970 00:00 UTC.
Last modified 3yr ago