I want to know where the best place to go is. We'll simulate the first go and see which squares are best, if any.
The hypothesis is that the centre rows and columns are better because the aircraft carrier must be there somewhere, because it's so long. Human intuition about placement is obviously a factor too, but we'll worry about that later.
Later we can also look at strategies for continuing the game.
Do this in a very simple way for now. Everything is beaten into submission, no finesse.
import numpy as np
# Set some basic parameters
boats = [2,3,3,4,5]
board_x = 10
board_y = 10
trials = 10000
board = np.zeros((board_y,board_x),dtype=int)
print board
[[0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0]]
def make_board():
board = np.zeros((board_y,board_x),dtype=int)
for boat in boats:
# Decide a direction, True is N-S, False is E-W
direction = np.random.choice([True, False])
# Decide a position, accounting for length of boat
if direction == True: # then N-S
while True:
endpoint_row = np.random.randint(board_y-boat+1)
endpoint_col = np.random.randint(board_x)
if np.sum(board[endpoint_row:endpoint_row+boat, endpoint_col]) > 0:
continue
else:
for i in range(boat):
board[endpoint_row + i, endpoint_col] = 1
break
else: # then E-W
while True:
endpoint_row = np.random.randint(board_y)
endpoint_col = np.random.randint(board_x-boat+1)
if np.sum(board[endpoint_row, endpoint_col:endpoint_col+boat]) > 0:
continue
else:
for i in range(boat):
board[endpoint_row, endpoint_col+i] = 1
break
return board
print make_board()
[[0 0 0 0 0 0 0 0 0 0] [0 1 0 1 1 1 1 1 0 0] [0 1 1 1 0 0 0 0 0 0] [0 1 0 0 0 0 1 1 1 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0] [0 0 0 1 1 1 1 0 0 0] [0 0 0 0 0 0 0 0 0 0]]
Make the board lots of times, and simply add up the ship positions over time. Then we can normalize to the number of trials for probabilities.
all_boards = np.zeros((board_y,board_x),dtype=float)
for i in range(trials):
all_boards += make_board()
print all_boards
[[ 753. 1096. 1397. 1601. 1667. 1646. 1491. 1359. 1029. 778.] [ 1070. 1333. 1585. 1779. 1832. 1828. 1718. 1619. 1309. 1147.] [ 1363. 1602. 1777. 1914. 2008. 2061. 1934. 1921. 1592. 1462.] [ 1546. 1793. 2011. 2128. 2178. 2175. 2065. 2052. 1744. 1615.] [ 1634. 1836. 2018. 2161. 2252. 2212. 2157. 2049. 1818. 1654.] [ 1662. 1827. 1996. 2200. 2268. 2254. 2231. 2016. 1828. 1674.] [ 1622. 1825. 1940. 2152. 2205. 2186. 2119. 1975. 1798. 1530.] [ 1405. 1651. 1768. 2013. 2036. 2047. 1962. 1843. 1655. 1373.] [ 1101. 1394. 1551. 1767. 1865. 1867. 1760. 1614. 1409. 1102.] [ 786. 1133. 1357. 1539. 1603. 1592. 1496. 1372. 1115. 747.]]
Plotting is easy in IPython — we just have to issue a magic command first, then import a library.
% matplotlib inline
import matplotlib.pyplot as plt
Now we can make a plot very easily with imshow
.
plt.imshow(all_boards)
plt.show()
We'll normalize to the number of trials to get probabilities.
np.set_printoptions(precision=2)
probs = np.zeros((board_y,board_x),dtype=float)
probs = all_boards / trials
print probs
[[ 0.08 0.11 0.14 0.16 0.17 0.16 0.15 0.14 0.1 0.08] [ 0.11 0.13 0.16 0.18 0.18 0.18 0.17 0.16 0.13 0.11] [ 0.14 0.16 0.18 0.19 0.2 0.21 0.19 0.19 0.16 0.15] [ 0.15 0.18 0.2 0.21 0.22 0.22 0.21 0.21 0.17 0.16] [ 0.16 0.18 0.2 0.22 0.23 0.22 0.22 0.2 0.18 0.17] [ 0.17 0.18 0.2 0.22 0.23 0.23 0.22 0.2 0.18 0.17] [ 0.16 0.18 0.19 0.22 0.22 0.22 0.21 0.2 0.18 0.15] [ 0.14 0.17 0.18 0.2 0.2 0.2 0.2 0.18 0.17 0.14] [ 0.11 0.14 0.16 0.18 0.19 0.19 0.18 0.16 0.14 0.11] [ 0.08 0.11 0.14 0.15 0.16 0.16 0.15 0.14 0.11 0.07]]
We can also finesse the plot a bit, e.g. with a different colourmap, and without interpolation (to see each square).
plt.figure(figsize=(8,8))
plt.imshow(probs, cmap=plt.get_cmap('autumn_r'), interpolation='nearest')
plt.colorbar(shrink=0.75)
plt.title('Battleship probabilities', size=18)
plt.yticks(range(board_y), [chr(65 + x) for x in xrange(board_y)])
plt.xticks(range(board_x), [x+1 for x in range(board_x)])
plt.show()