However, most opponents do not randomly place their ships around the board. I wanted to note that this algorithm is designed to perform optimally in the presence of randomness.
#BEST LOOKING BATTLESHIP ONLINE GAME HOW TO#
If any readers have ideas or suggestions on how to improve the coloring to make it closer to plots produced by Matplotlib, I am absolutely open to hearing them.
#BEST LOOKING BATTLESHIP ONLINE GAME CODE#
GIF by author.įor my Pygame visualization above, I had to code the heat map coloring system from scratch. To find which square to fire on next, we choose the square in the heat map with the highest value.Īn example game played with the probabilistic algorithm.
We can do this for every ship and combine the probabilities to get a generalized heat map for all the ships on the board. By doing these calculations for every square on the board, we can generate a “heat map” showing which squares are most likely to have a Carrier on them. By contrast, the corner square at row zero, column zero has only two ways for a Carrier to be placed on it, giving it a weight of two. The Carrier can be placed on top of it in 10 different ways horizontally, and 10 different ways vertically. Consider a central square like the one at row four, column four. This is simply because there are many more possible ways to place a ship in the center of the board than on the outside. If we assume that ships are placed randomly, it’s far more likely that we’d see a ship in the middle of the board than at an edge or corner. Instead of choosing random squares to guess in the targeting stage, we can use probability to inform our decision. To further improve the algorithm’s targeting strategy, we turn to a new approach. At worst, the original strategy hit all 100 squares, while the improved version never went past 88 squares. Notably, the worst case for the original strategy is much worse than for the improved one. There are some marginal gains between the original and improved Hunt / Target strategy. Lastly, there are five ships total on the board, with lengths of five, four, three, three, and two. This is crucial information since it reveals that we no longer need to continue firing in this particular area.
Second, once all squares of an opponent’s ship have been hit, the opponent must declare that their ship has been sunk. First is that no ships can overlap: while ships can be adjacent to other ships, they can not be stacked on top of each other. I assume anyone reading this is familiar with the basic rules of Battleship, but I’ll give a quick recap of some rules that are particularly important for the AI implementation. For those who want it, everything is available at my Github. I decided to recreate his strategies and to post the source code publicly for anyone who wants to play around with or modify it. His explanation of the algorithm is brilliant, but I was unable to find any source code for his implementation. His post begins with a relatively weak algorithm, but he builds it into a powerful solution that can dramatically outperform many other methods.
That video led me to this blog post by Nick Berry of DataGenetics, who describes the algorithm in great detail. In the video, they describe a probability-based algorithm that leads to strategies far more sophisticated than a human player could reasonably use. One of the most viewed pieces of media on the topic is a Youtube video by the channel Vsauce2. Online you can find a wide array of approaches, from reinforcement learning to genetic algorithms to Monte Carlo methods. Image by author.īattleship seems to be a pretty popular format to test a variety of AI strategies. Example Battleship game using probabilistic search.
0 kommentar(er)
