Microsoft Events

Game Help

Programmers' Reference

Powered By GitBook

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.

Objective

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.

Adding intelligence to your bot

Editing the Code

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:

1

def calculate_move(gamestate):

2

if gamestate["Round"] == 0: # If we are in the ship placement round

3

# The Placement list adds ships in the order that the ships are

4

# listed in the Game Style e.g. 5,4,3,3,2 places the ship of length

5

# 5 first, the ship of length 4 second, the ship of length 3 third.

6

#

7

# This function does not check for any land and, so, should be used

8

# with a Game Style that does not include land.

9

move = {

10

"Placement": [

11

{

12

"Row": "A",

13

"Column": 1,

14

"Orientation": "H"

15

},

16

{

17

"Row": "B",

18

"Column": 6,

19

"Orientation": "V"

20

},

21

{

22

"Row": "C",

23

"Column": 1,

24

"Orientation": "H"

25

},

26

{

27

"Row": "D",

28

"Column": 1,

29

"Orientation": "H"

30

},

31

{

32

"Row": "E",

33

"Column": 1,

34

"Orientation": "V"

35

}

36

]

37

}

38

else: # If we are in the ship hunting round

39

move = {

40

"Row": "B",

41

"Column": 4

42

}

43

return move

Copied!

Here is an example of a function that takes into account land to ensure that the move is valid:

1

def shipPlacement(gameState):

2

move = [] # Initialise our move list

3

# Start in the top left corner

4

start = (0,0)

5

row = 0

6

column = 0

7

for i in gameState["Ships"]: # For every ship we need to place

8

space = 0

9

start = (row,column) # Start trying to find room at the current row and column

10

while space < i: # Until we find enough room to fit the ship keep on looking

11

if column >= len(gameState["MyBoard"][0]): # If we have reached the end of a row without finding enough room

12

row += 1 # Move to the next row down

13

column = 0 # Start at the beginning of the row

14

space = 0 # Reset the amount of space we have found on the row since the last obstacle

15

start = (row, column) # Initialise the potential start location for our ship

16

if gameState["MyBoard"][row][column] == "": # If the current cell is empty

17

space += 1 # Increment the amount of space we have found on the row since the last obstacle

18

column += 1 # Move to the next column along

19

else: # If there is something blocking a ship being placed

20

space = 0 # Reset the amount of space we have found on the row since the last obstacle

21

column += 1 # Move to the next column along

22

start = (row, column) # Reset the potential start location for our ship

23

# If we have found enough room to place our ship

24

shipPlace = BATHelperFunctions.translateMove(start[0], start[1]) # Call the translateMove hepler function with our coordinates to convert it to a valid move format

25

shipPlace["Orientation"] = "H" # Set the orientation we wish to place our ship as horizontal

26

move.append(shipPlace) # Add this ship placement to our move list

27

# Once we have added all of our ships

28

return {"Placement": move} # Return the valid placement move

Copied!

Case Study

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:

1

import BATHelperFunctions # Allows us to use the helper functions

2

from random import choice # So we can randomly choose an element from a list

3

from random import randint # So we can randomly pick a number

4

5

def calculate_move(gamestate):

6

if gamestate["Round"] == 0: # If we are in the ship placement round

7

move = BATHelperFunctions.deployRandomly(gamestate) # Randomly place your ships

8

else: # If we are in the ship hunting round

9

for i in range(len(gamestate["OppBoard"])):

10

for j in range(len(gamestate["OppBoard"][0])): # Look through every cell on the board

11

if gamestate["OppBoard"][i][j] == "H": # If it has been hit

12

if i > 0 and gamestate["OppBoard"][i-1][j] == "": # Try and guess above

13

return {"Row": chr(i + 64), "Column": j + 1}

14

elif i < len(gamestate["OppBoard"])-1 and gamestate["OppBoard"][i+1][j] == "": # Otherwise try and guess below

15

return {"Row": chr(i + 66), "Column": j + 1}

16

elif j > 0 and gamestate["OppBoard"][i][j-1] == "": # Otherwise try and guess left

17

return {"Row": chr(i + 65), "Column": j}

18

elif j < len(gamestate["OppBoard"][0])-1 and gamestate["OppBoard"][i][j+1] == "": # Otherwise try and guess right

19

return {"Row": chr(i + 65), "Column": j + 2}

20

# If there are no hit ships

21

if gamestate["OpponentId"] == "Barney01": # If we are playing against Barney01

22

move = guess_edges(gamestate) # Call our guess_edges function to choose a target on the edge of the board if available

23

else:

24

move = BATHelperFunctions.chooseRandomValidTarget(gamestate) # Randomly fire at valid sea targets

25

return move

26

27

def guess_edges(gamestate):

28

count = 0

29

while count < 50: # While we haven't given up trying to find a valid edge

30

(row, column) = choice( # Randomly choose one of the following:

31

[

32

(0, randint(0, len(gamestate["OppBoard"][0])-1)), # A random cell along the top edge

33

(len(gamestate["OppBoard"])-1, randint(0, len(gamestate["OppBoard"][0])-1)), # A random cell along the bottom edge

34

(randint(0, len(gamestate["OppBoard"])-1), 0), # A random cell along the left edge

35

(randint(0, len(gamestate["OppBoard"])-1), len(gamestate["OppBoard"][0])-1) # A random cell along the right edge

36

]

37

)

38

if gamestate["OppBoard"][row][column] == "": # If the move is valid

39

return {"Row": chr(row + 65), "Column": column + 1} # Set values to a valid move

40

else: # Otherwise increase number of attempts by one

41

count += 1

42

# If we have given up trying to find a valid edge

43

return BATHelperFunctions.chooseRandomValidTarget(gamestate) # Randomly fire at valid sea targets

Copied!

This code is inefficient, see if you can improve its performance and its strategy!

Advanced

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:

1

while True:

2

if self.game_cancelled:

3

break

4

5

if game_state['IsMover']:

6

move = battleships_move.calculate_move(game_state)

7

move_results = self.make_move(move)

8

9

if move_results['Result'] != 'SUCCESS':

10

break

11

12

game_state = move_results['GameState']

13

14

else:

15

16

# ---- Code here will be called on your opponent's turn ----

17

18

# ----------------------------------------------------------

19

20

poll_results = self.poll_for_game_state()

21

22

if poll_results['Result'] != 'SUCCESS':

23

break

24

game_state = poll_results['GameState']

25

26

if game_state['GameStatus'] != 'RUNNING':

27

break

Copied!

Bot strategy

Here are some suggestions of strategies to improve your bots performance.

Randomise your ships

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.

Randomise your shots

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.

Model your opponent's board

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.

Reduce unnecessary moves

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.

Programmer's Reference

The gamestate

Example gamestate JSON

1

{

2

'Ships': [5, 4, 3, 3, 2],

3

'IsMover': True,

4

'Round': 1,

5

'ResponseDeadline': 1543861722513,

6

'MyScore': 0,

7

'OppScore': 0,

8

'MyBoard': [

9

['L', 'L', '0', 'H0', 'H0', 'H0', '0', ''],

10

['L', 'L', '1', 'H1', 'H1', 'H1', '', ''],

11

['L', 'L', '', 'M', '', '', '', ''],

12

['L', 'L', '', '', '', '', '', ''],

13

['L', 'L', 'L', 'L', '', '', '', ''],

14

['L', 'L', 'L', 'L', '', '', '4', '2'],

15

['', '', '3', '3', '3', '', '4', '2'],

16

['', '', '', 'M', 'M', '', '', '2']

17

],

18

'OppBoard': [

19

['L', 'L', '', '', '', '', '', ''],

20

['L', 'L', '', '', '', '', '', ''],

21

['L', 'L', 'M', '', '', '', '', 'M'],

22

['L', 'L', '', '', 'H', 'H', '', ''],

23

['L', 'L', 'L', 'L', '', 'H', 'M', ''],

24

['L', 'L', 'L', 'L', '', '', '', ''],

25

['', 'M', '', '', '', '', '', 'M'],

26

['', '', '', '', '', '', 'M', '']

27

],

28

'GameStatus': 'RUNNING',

29

'GameId': 2398045,

30

'OpponentId': 'housebot-practise'

31

}

Copied!

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

Understanding the boards

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.

Making a valid move

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.

Ship Placement Move

Here is an example of a valid ship placement move:

1

# The Placement list adds ships in the order that the ships are

2

# listed in the Game Style e.g. 5,4,3,3,2 places the ship of length

3

# 5 first, the ship of length 4 second, the ship of length 3 third.

4

#

5

# This function does not check for any land and, so, should be used

6

# with a Game Style that does not include land.

7

{"Placement": [

8

{

9

"Row": "A",

10

"Column": 1,

11

"Orientation": "H"

12

},

13

{

14

"Row": "B",

15

"Column": 6,

16

"Orientation": "V"

17

},

18

{

19

"Row": "C",

20

"Column": 1,

21

"Orientation": "H"

22

},

23

{

24

"Row": "D",

25

"Column": 1,

26

"Orientation": "H"

27

},

28

{

29

"Row": "E",

30

"Column": 1,

31

"Orientation": "V"

32

}

33

]

34

}

Copied!

Ship Hunting Move

Here is an example of a valid ship hunting move

1

{

2

"Row": "B",

3

"Column": 4

4

}

Copied!

Helper Functions

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 2yr ago