Coding Battleship with Game Theory

By Noah S
Age 16
San Mateo, CA

black-and-white-blur-board-game-541538.jpg

Game theory is actually not the name of a youtube channel. It is, but that term is actually derived off a complex study called “Game Theory”. Game theory is the study of interactions between intelligent “things”. Whether this thing is a human, AI, or some other kind of rational thinking thing it up to you. Game theory is most commonly used in political science and economics, although its use can also be widened to cover topics like logic and computer science. This is what I researched while I made my battleship, which utilized 2 intelligent things as well, the player (you) and the AI. This topic is very broad, so I will discuss some examples and try to tie them together at the end of this post.

One famous study of game theory is the “prisoner’s dilemma”. Two prisoners, A and B, are being interrogated for the same crime. If both prisoners rat each other out, they get 5 years of prison. If A rats out B, A is set free while B must serve 10 years, and vice versa. If they both stay quiet, however, they each only have to serve 2 years in prison. Even though they both have a significantly better outcome if they both stay silent, the probability of them cooperating is actually very low, and the odds of at least one of them ratting the other out is significantly high. While the reasons are really implied since there is no direct answer (like how in english class there are many ways to interpret something, while in math there is only 1 answer), the risk of getting rewarded by being set free outweighs all other costs, including not receiving the most severe punishment of 10 years, leads many to do so. In addition, mistrust of the other also magnifies this effect.

Another example is battleship. I actually made a program that runs battleship with a complex AI. The board layout is actually determined both a combination of statistics and game theory. When playing battleship, one of the player’s primary goals is to aim for more open spaces to shorten the game and give themselves a better chance at winning. But where should a player aim to give themselves the largest chance at hitting a target? This is determined by game theory. While there is no way to play battleship to give yourself a 100% chance at winning, as it is a luck-based game, there are spots you can fire that give yourself a slight edge. For example, if you see a 4 space opening, you know that a carrier (5 slots) cannot fit there. If you see a spot completely surrounded on all sides by misses, you know that there cannot be a ship in there, and as a result that space may as well count as a miss. This is what I coded into the AI in my battleship game to make it more human-like. By covering the board with probabilities of locations that are most likely to harbor a ship (pun intended) in relation to the amount of ships left and the different types they are, a player (or AI) can use game theory to their advantage to win the game.

To tie these together, game theory is a super broad study that has many different uses. Anything that requires an interaction between intelligent beings all comes back to this idea of game theory. Being able to mathematically predict the most possible and reasonable outcome is very useful in many occupations. I hope I can apply game theory to many different projects in the future. But for now, I will continue to improve upon the battleship game I am making right now.