This is a version of the game Battleships in which two players attempt to sink all of their opponents ships first. Here, you play vs an AI, which works through Monte Carlo Simulation. Originally this project was designed to build a neural reinforcement learning agent to play the game, however I have been unsuccessful in this goal so far. If anyone reading this has any ideas of how to go about such a thing, I would love to hear them!
Monte Carlo Simulation
The basics of how it works are as follows:
- Take current board state as input
- Create copy of board state
- Simulate a specific number of samples (given by
--monte_carlo_samples), each of which is a random placement of a remaining ship type
- Stack all of the simulations and sum the total number of ships in each square (emphasise ships that overlap existing hits)
- Take the mean for each sqaure, giving us a frequency matrix or heatmap
- Pick the largest value corresponding to a legal move in the matrix
There are two heatmap gifs in this project which demonstrate the probability matrix as a heatmap for every square after each move in the game. Here is one of them:
Done entirely using the
python 3.6 standard library, with the exception of
numpy which is required.
main.py file takes 3 arguments as follows:
--board_size: The size of the board, default:
--ship_sizes: Array of ship sizes to randomly place, default:
--monte_carlo_samples: The number of samples to get the algorithm to do, default:
If you have a slow computer, choose a lower number of samples, but generally 10,000 should get good results in decent time. Make sure not to put spaces between the integers in ship_sizes. Extemely large or small board sizes may have unexpected behaviour, generally the safe range is 5-10, but with appropriate adjustments to the other parameters, sizes outwith this range will work fine.
Once run, the game will initialise two boards of ships randomly (choosing ship locations is not implemented currently), one for you and one for the computer. The key for square types is as follows:
- Sea: ■
- Hit: X
- Miss: □
- Destroyed: *
The player goes first and specifies a move by giving first a letter and then a number to determine the target square.
This project is released under the MIT license, see LICENSE.md for more details.