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.

My Analysis of Mine Sweeper Algorithms

minesweeper.png

By Laker N.
Age 14
Palo Alto, CA

CodeWars is an online collection of programming challenges ranked by difficulty. It’s community driven, meaning that, though the problems require thinking, they are satisfying to complete. One problem on CodeWars that caught my attention was “Mine Sweeper” by the user myjinxin2015, a prolific creator and the second highest holder of honor, gained by solving and making the site’s code challenges. “Mine Sweeper” is a kyu 1 code challenge, the hardest on the site. (Kyu, or difficulty, ranges from 1 to 8, with 8 as the easiest and 1 as the hardest.)

Despite its ranking, I’ve always liked the idea of Minesweeper. “Mine Sweeper,” however, didn’t involve programming the game; “Mine Sweeper” is kyu 1, because the task is to program an algorithm to solve Minesweeper. Specifically, given a board configuration with a number of the squares identified, fill in the rest.

Though the problem intrigued me, I was at a loss for how to attack it. After some brainstorming, however, I came up with a rule my algorithm could apply to a board configuration to solve unknown squares. If a square has as many empty tiles around it as it needs mines to fulfill its number, then all surrounding squares are mines. If a square needs no more mines, then all unknown surrounding tiles are safe. In code, I assigned each tile the number of mines needed to satisfy its number minus the number of mines already flagged around it. This number I called the tile’s working number. For example, a tile with the number three and two flagged mines around has a working number of one: any unknown tiles around it can act as though it only needs one mine. With working numbers, a tile with number five, three mines flagged around it, and two remaining unknown tiles knows to flag all surrounding unknown tiles. I call the first rule Easy Logic, because most Minesweeper players rely on it before thinking harder.

The code for EasyLogic is split into three functions: one to find tiles who need to flag all surrounding mines, one to find tiles who need to open all surrounding tiles, and one to combine them.

About half of Minesweeper games can be solved with only Easy Logic. A fraction of games, however, evolved into configurations Easy Logic couldn’t untangle. I knew Easy Logic would still be integral to my solution, but I was going to need something more.

The second rule I came up with was significantly more complicated to implement. I call it Contradiction Search. Contradiction Search looks at unknown tiles around known tiles one by one and pretends they are mines. It then applies the rules of Easy Logic to flag mines until one of two outcomes is reached. Either no conclusions can be drawn, or a contradiction is reached. A contradiction is when, as a result of the unknown test tile being a mine, logic indicates that there must be safe tiles in a location. These same safe tiles that must exist if the test tile is a mine deprive another tile of enough mines. The contradiction shows one of the premises must be incorrect; Easy Logic doesn’t fail, so the incorrect premise is that the test tile is a mine. Therefore, the test tile must be safe.

The following image is the comment in the code to explain Contradiction Search.

laker3.png

A simple example of a contradiction is in a 3x2 board in which the bottom row has three ones. See the image for a visual. If Contradiction Search checks the top left square, Easy Logic dictates that, because the middle one has satisfied its one mine requirement, all other surrounding squares are safe. That means that the top middle and top right squares are safe. This, however, deprives the bottom right one of its mine: the two possibilities it had (top middle and top right) are both safe. This is a contradiction and proves that the top left square is safe.

With Easy Logic and Contradiction Search in hand, my algorithm could now solve the majority of Minesweeper boards. Almost all games they failed to solve were unsolvable, meaning there are two or more possibilities, and there is no information to distinguish them. The simplest example of an unsolvable position is a 2 by 1 board with one mine. There is no information that tells whether the mine is in the left square or the right square. To solve the board, a player would need to guess.

In practice, Contradiction Search requires much more computation than Easy Logic. Consequently, to solve boards, the algorithm applies Easy Logic as many times as it can. Either it solves the game or it gets stuck. If Easy Logic gets stuck, I repeatedly run Contradiction Search and Easy Logic again until the algorithm comes out of the rut. If Contradiction Search fails to find anything, chances are the board is unsolvable.

A live demo for this algorithm along with an implementation of Minesweeper on which to use it can be found at www.arongil.com/minesweeper. For those who wish to play it, left click to uncover a square and right click to flag or unflag a mine. The buttons to apply any of the three rules discussed are in the bottom left.

How Does Google Maps Work?

By Noah S.
Age 16
San Mateo, CA

traffic.jpg

Hi! Today I’m going to be explaining graph theory, a complex algorithm used almost exclusively in object oriented languages that shines when you want to know the shortest path from something to another thing. Some applications include finding the shortest route to a location, the smallest number of moves to win a chess game, and the fastest way to solve a Rubik’s cube. Overall, graph theory has a lot of potential when applied to something large, and can really be utilized in many amazing ways. Without further ado, let’s jump right in.

Let’s try to visualize the graphs that are mainly used in graph theory. Imagine a bunch of points, with every single point connected to one or two other points. These are called nodes. Nodes are used in many other types of searching algorithms, such as linked lists and trees. Since there are two types of graphs used in graph theory, imagine these two scenarios. First imagine the same points and connections as stated above. This is an undirected graph. An undirected graph is when every line between the points is unmarked. To contrast, now imagine the same graph, but every line between the points has a direction, marked with an arrow. This shows how one node connects to another. Undirected graphs use unmarked lines to indicate that information flows both ways, while directed graphs use marked arrows to indicate information that flows only one way.

Now that we have understood what kinds of graphs exist, let’s discuss the ways they can be utilized. Commonly known as simple graphs, any graph without a clear pattern or shape, and doesn’t loop whatsoever is deemed so. Most graphs used in graph theory are simple graphs. Other types of graphs are non-simple graphs, which can be identified with their use of loops (for example, three nodes all pointing to the next node to form a triangle shape). Another type of graph is an isomorphic graph. These graphs are just simplified versions of the non-simple graph. Since many non-simple graphs end up showing some kind of pattern, usually it can be arranged to form a particular shape. Imagine a bunch of nodes all pointing to each other to form a pentagram or such.

There is one type of graph that stands out, however. It is the weighted graph. A weighted graph is just a normal graph with a catch: Every line that connects two nodes has a weight, usually an integer, of how much it “costs” to use this line. As a result, a path that connects two nodes might end up being longer than a path that goes through 4 or 5 nodes. Knowing the weight allows the algorithm to show signs of sophistication. For example, maybe you see a lot of traffic going to your destination. Weighted graphs allow you to determine the fastest route, and you may end up arriving there a few minutes earlier. Of all the graphs mentioned in this post, weighted graphs are the most complex, but the most fundamental in properly understanding and utilizing this code.

Now let’s talk about how to actually make this code work. If you have experience with linked lists or trees, or basically anything with nodes, it’s pretty simple to understand. You traverse through the graph, starting with node 1, you traverse through the graph (test out every option) until you hit your destination. Then, it calculates the fastest possible route. If weights are not present, it is simply the path with the least amount of lines. If weights are present, however, it will calculate which path has the least weight.

This is graph theory in a nutshell. There are some other small nuances and such, but knowing the stuff that I have written will set you pretty well off. Understanding graph theory will help you understand other object oriented algorithms, like trees and linked-lists (although I would start there if you have no coding experience with nodes).

Anvil: A New Standard for Python Web Development?

By Camille D.
Age 16
San Mateo, CA

Create comprehensive websites simply by dragging and dropping, using Anvil - a Python-based service that takes a multifaceted approach to full-stack web development.  Even with other platforms such as Squarespace and Weebly dominating the ecosystem of drag and drop-based web development, Anvil provides a direct path for users to not only master the art of website creation, but also actively learn the Python language.  

Anvil was built by Meredydd Luff and Ian Davies with simplicity and efficiency in mind—using Anvil, all the time it takes to learn the cornucopia of languages typically employed in web development (HTML, CSS, PHP, SQL, etc.) can be eliminated.  Anvil was also designed for users of any level of experience with Python—aspiring developers may learn Python concurrently while using the service.  

With its abundance of resources and manuals, Anvil’s teaching algorithm passes all tests.  Anvil’s video tutorials1 each give comprehensive procedures on how to use their features, from their multi-user app capabilities to business analytics.  For those like myself, however, who believe in the worked-example effect, the service also introduces an array of premade templates2 with which users can experiment and learn the ropes of building web features with Python.  An Anvil-specific code documentation3 is also accessible through the main page, pictured below, and is structured with an introduction on using Python for the site and a brief set of instructions for each module, component, and function.  

UI design in Anvil both starts and ends in its online IDE, whose facilities streamline the workflow of both front and back-end development.  Among the most convenient features of this IDE is its toolbox from which all the fundamental web components such as links, calendars, and text, are dragged and dropped.  

Though users no longer have to write several lines of HTML and/or CSS to add components on to their page and manipulate them, an issue about this that might arouse concern is that since users are essentially only dragging code into an IDE, they are removing the rigor that comes with typing the code out.  It is important that in teaching students, CoderSchool instructors perhaps allow their students to drag and drop towards the beginning of their using the service, zero in more on how specific bits of code work, and then ease into typing the code out so that they can experience the workflow of creating an app with Python.  Anvil provides all the tools; the most important part is that they are taught in the most effective way possible.

Anvil is a program of substantial educational value, and when taught properly is great for a CoderSchool student who is at least at an elementary school age (even though it provides all the tools, the interface can seem a little sophisticated at times for younger students).  It is also worth noting that the pricing may be on the exorbitant side ($449 monthly for a Business plan), so if the CoderSchool begins to utilize this service, they should adopt it as a standard for teaching web development.  However, with its wide range easily accessible of resources and features, its seamless workflow, and its options to write code in Python or drag and drop, Anvil is  worth the cost for CoderSchool because it will serve as a powerful introductory means for students to learn front-end Python programming.