2016 Spring AI Project – Floppo Bordo

[Pinned post]

As my senior year of high school began to slow down and the college hype began to increase, I looked for simple projects to work on while in the midst of the craziness. I spent a while sitting back and looking at the projects I’ve finished this past school year and remembered a couple of other projects from other people that served as inspiration for my personal projects. Since I learned everything I know about AI from watching lectures and demonstrations online, it was a trip down memory lane to go back and watch those videos in particular. One of the projects I looked back at was a machine learning algorithm that used reinforcement learning for Flappy Bird (A popular mobile game), and I remember being amazed at the actual process of learning that the algorithm went through (see that video here). I decided to challenge myself by making my own Flappy Bird AI to benchmark my current progress, especially in comparison to where I was 6 months ago.

First, however, I had to make a Flappy Bird clone. Making it was surprisingly easy, as it has simple rules and doesn’t require a lot of complex algorithms. Flappy Bird is essentially an endless runner, but the player must tap the bird to fly precariously in between pipes (if the player touches one of these pipes they die and have to start over). Since this was just a quick project, I didn’t bother with making images to go over each of the objects, instead using colored rectangles. The blue rectangle is the player, the black rectangles are pipes, and the green rectangle is the ground.

I used my standard Neural Network algorithm with a genetic algorithm for the machine learning AI (read more about Neural Networks here). It uses 4 inputs – the player’s y position (height from the ground), the y positions of the opening between the closest pipes (the lowest point on the top pipe and the highest point on the bottom pipe), and the horizontal distance between the player and the closest pipe. There are 2 hidden layers of 5 nodes each, and 1 output node (if the output node > 0.5, the bird jumps). I used a sigmoid function (1 / (1 + e^-x)) as my activation function. Reward was based on the score at the end of the run and how far the AI moved the bird to the right.

Now onto the results. It actually learned to jump between pipes fairly quickly, but difficulty came when it needed to jump with precision between the pipes. However, after a little bit of time, it mastered the game perfectly.

start

Start of the simulation. You can see the AI has trouble handling its own jump height.

stend

After about 10/15 minutes of runtime, the AI has mastered the art of jumping in between the pipes.

I enjoyed making this project and seeing how far I’ve come. A while ago, I never would have thought I would have been able to make something like this. If you want to see the code for this project, you can get it here.

Advertisements

2017 Summer App Project – The Stalk Market

As my previous post (linked here) eluded, this is the second and main project I worked on during the latter half of my summer break from Virginia Tech. Described shortly, this project is a stock market tracker of sorts for the game Animal Crossing: New Leaf (ACNL) that is able to run from any handheld Android phone. My main focus for this project was introducing myself to the world of app development, mainly following various tutorials online and playing around with the Android Studio IDE. As such, the actual logic behind this project isn’t too difficult to grasp. As I’ll get into, the stock market in ACNL is rather simple and follows a strict set of rules. Thus, I mainly focused on making the user interface as fluid as possible, to ensure ease of use and practicality while keeping the function of the app in mind.

1

What the app looks like when you open it for the first time. I put a decent amount of effort into ensuring the app looks somewhat decent and is easy to use. Note, all pictures shown here are screenshots taken on my Google Pixel.

First, onto the basics of the stock market in ACNL. Every Sunday, the player can buy Turnips from a particular NPC that visits the town. The price for that particular set of turnips can range anywhere from 90-110 bells (the currency of ACNL). Then, throughout the week, the selling price of those turnips changes depending on the particular pattern for that week. The prices change twice per day (at store-open and 12pm), with the turnips rotting at exactly 6am on Sunday. Thus, the player must guess when he or she should sell all of the turnips they purchased for that week to ensure maximum profits. This is where my app comes in. The user is to enter every price update in-game into the app. Then, when prices are optimal, the app recommends the user to sell all of their turnips.

There are 4 patterns the stalk market can have for any given week, each with its own set of rules that makes it easily distinguishable from the others. Of the patterns that produce positive returns, the player is first tempted multiple times with above average selling prices before the maximum price is observed. The biggest example of this is the big spike pattern, where there are 2 above average prices before the best price, often double that of the previous prices, is observed. My app guesses which pattern is most likely for the given week/set of values, and warns against selling your turnips until it thinks the highest value for the week has been achieved. There is only one pattern in which the player is guaranteed a loss. If you’d like to read more on the various patterns and their strategies, I would recommend visiting this page.

2    3

Though the turnip price in the first picture is much higher than the purchase price (labeled in blue), the app recommends waiting, which pays off with a week-high price 3 times that of the previously shown price, as shown in the second picture.

Once the logic was finished and patted down, I moved onto the user interface portion of the app. The only non-native library I used was GraphView for the plot of prices seen on the upper-half of the screen. The main challenge when coming up with the UI for this project was where to place the buttons and text box in relation to each other and the graph. I ended up with the current design, as I think it looks and feels simple and easy to use. One of the previous designs had all of the buttons underneath the graph in a 2×2 grid pattern, which failed due to the strangeness of fingers as a cursor. Sometimes, I found myself pressing the bottom right button when I meant to press the upper left button, among other similar problems. I’ve found that the current vertical design is a clear and easy solution that wasn’t difficult to implement. Other than button placement, I used in-game and fan art (the background, turnip, and animal figure) for decorating the app. If I were to publish this on the Play Store, I would first want to draw myself or enlist the help of a friend to redraw all of these assets to ensure I didn’t steal content from their creators. As such, you will not be able to find this on the Play Store as of yet. However, if you email me saying you want to put this app to use, feel free to and I will post an app that falls within these guidelines.

This project was fun to explore. I learned a whole lot about Android app development, and created something I can put to use in my future ACNL endeavors. If you’d like to look at the source code, you can see it here.

 

2017 Summer Cryptography Project – Caesar Ciphers and ASCII Tables

Admittedly, the time before my summer semester in Japan was ill-spent in regards to furthering my understanding in the Computer Science world. However, there were still a couple of projects that I did for fun before I left. This first project, a rather simple caesar cipher, was the first of two projects I did. I did this project in particular as a way to brush up on some of the knowledge of the C language I gained during my spring semester CS 2505 class at Virginia Tech. For those unfamiliar with the concept of a caesar cipher, it’s a crude way to encode a chunk of information — simply taking every letter and shifting it up or down a predetermined number of spaces in the alphabet. For instance, the string “abcd” would be encrypted to “bcde” with a caesar key of positive one. Of course, traditionally, wrapping occurs at the ends of the alphabet; meaning z -> a with a key of +1, and a -> z with a key of -1.

There are a couple key parts when it comes to translating this into code. First and foremost, I made it runnable via. the command line. The program expects the file path to the text file the user wants scrambled or unscrambled, along with either ‘e’ or ‘d’ for ‘encode’ and ‘decode’ respectively. Next, instead of letting the letters wrap once at the end/beginning of the alphabet, I allowed the characters to go above/below this limit, possible thanks to the format of the ASCII table.

asciifull

ASCII table

In C, along with the vast majority of programming languages used today, ‘char’ (character) variables are actually stored as integers. Each character is 1 byte, allowing for up to 256 different characters to exist. This not only includes your standard upper/lower case alphabet and numbers, but also special characters, along with some special, machine only characters, like ‘\n’ (new line). So, instead of wrapping at the ends of the alphabet, I wrapped at the ends of the ASCII table (see methods encode and decode in the block below to see how). In regards to my program, this is relevant because it allows for characters to spill over into generally weird or unexpected characters, making it easier on us to program because we don’t need to look for specific ASCII values to wrap around, as well as adding a bit more effectiveness to the final product. Of course, this method won’t fool someone who knows what they’re doing when it comes to decryption, but it should generally prevent friends or co-workers from snooping into information you don’t want shared.

There are still plenty of improvements that can be made to this system to improve it even further and lessen the chance of someone cracking a particular files key. As you can see in this iteration of the program below, the key is static between all files, meaning a correct guess on one file means access to your entire library of secret text files. This could be improved by simply making the key random between files and stored somewhere inconspicuous. For instance, the key could be between 0 and 255, and simply written as the first character of the encoded file. While again, this method would fail almost instantly in the case of a professional crack, it should stump the average Joe for a couple of hours. Or, perhaps this method is repeated for every character in any one file; the key for any given character placed just before or after it. I’m sure you can see how this method can become increasingly complex, and increasingly difficult to break, the longer you think about it.

FILE *f;

int caesar = 5;

int main(int argc, char **argv) {
	if (argc != 3)
		badInput();
	FILE* f = getFile(argv[1]);
	if (strcmp(argv[2], "e") == 0)
		encode(f);
	else if (strcmp(argv[2], "d") == 0)
		decode(f);
	else
		badInput();
	fclose(f);
	return 0;
}

void badInput() {
	printf("Format is '.../caeser <.../fileToEdit.txt> <e/d>'\n");
	exit(1);
}

FILE* getFile(char *url) {
	FILE *f = fopen(url, "r+");
	if (f == NULL) {
		printf("Can't locate file '%s'", url);
		badInput();
	}
	return f;
}

void encode(FILE *f) {
	int c;
	while((c = fgetc(f)) != EOF) {
		fseek(f, -1, SEEK_CUR);
		fputc((c + caesar) % 255, f);
		fseek(f, 0, SEEK_CUR);
	}
}

void decode(FILE *f) {
	int c;
	while((c = fgetc(f)) != EOF) {
		fseek(f, -1, SEEK_CUR);
		fputc((c - caesar) % 255, f);
		fseek(f, 0, SEEK_CUR);
	}
}

The C code behind the Caesar Cipher. If you have any questions about the code feel free to email me: brendan.mccloskey@gmail.com.

This project was an easy, quick, and fun way to stay familiar with the ins and outs of ASCII values and C I/O alike. Feel free to take this idea further and create ciphers of your own!

2017 Spring AI Project – PoNNg

Towards the end of my first year at Virginia Tech, I oddly found myself with more free time than usual. Throughout the year I tried to focus on my neural network study when I could, but sadly, little time arose for me to pursue what I love. However, I always worked on small projects when I could. The majority of this time was spent geared towards learning Linux and Python, both of which I have become somewhat proficient in. Using these newfound skills, I looked back to my roots to see what improvements I could make on my original code from high school and to get back into the field of artificial intelligence in general. The main goal for this project was to create a short, dependable neural network algorithm for personal use in Python. I also wanted to create a system in which 2 neural networks were pitted against each other in some form of competition. I thought pong was a suitable game for this purpose because of its simplicity and competitive nature. My version of it stays, for the most part, true to the original game. 2 paddles, 1 ball, reset and score increase upon the ball exiting the left or right screen. After each bounce, the ball’s y velocity is randomly chosen between [2, 5] to add some randomness to where the ball will be when it reaches the left or right side of the screen. Pygame was used to render the components onto a window.

The general frame of mind I had while creating the neural network algorithm for this project was brevity and simplicity. One of the main issues with my Java implementation from a year ago was the fact that all of the weights were stored in a single 1D array, which isn’t ideal for many reasons. Mainly, it’s confusing to look at and understand the math behind extracting the correct weight at the correct time. To correct this, I switched it from a 1D array to a 3D array, in the format of [layer][input][output], layer being the current index in regards to the hidden layer, input being the “left” set, and output being the “right” set (i.e. input -> hidden, input is the “left” set and hidden is the “right” set). Although confusing at first due to my lack of experience with 3D arrays, I eventually came up with a good system that works just as fine as the original and is slightly easier to understand from an outsiders point of view. e

Screenshot from 2017-04-09 19-13-31

Example of a 3D weight storage system for a neural network with 2 input nodes, 1 hidden layer of 3 nodes, and 1 output node. The number of rows corresponds to the “input” layer (input -> hidden; input is the input layer, hidden -> output; hidden is the input layer) and the number of columns corresponds to the “output” layer (hidden and output in the above example).

In this project, I experimented around with neural networks of varying sizes before settling on a simple 2 node input, 3 node hidden layer, and 1 node output network. The input was the vertical and horizontal distance between the paddle and the ball over the total height/width of the game window. When given more input nodes like the x and y velocity of the ball, it was observed that the neural networks were able to accurately predict where the ball would hit the paddle when it reached the side of the window (as opposed to just following the ball’s y component), but the time it took to reach this point was incredibly long and results varied over different situations (i.e. the angle the ball was approaching the paddle, etc.). Fitness was given based on how many matches the neural network won, but was punished twice as hard for every match (first to 3 points) lost (+1 for win, -2 for loss). A standard breeding process was performed after each match in which the parents were the 2 best performing networks in a population and the child was the worst, with the child weights having 2/3 chance of being from either of the parents and 1/3 chance of being the average of the parent weights. There was a 6% chance of any weight being erased and assigned a random value between (-1, 1). After each match, the loser was replaced by a randomly selected network from the population (it was ensured that the two networks playing each other were not the same one). Each paddle’s neural network can be seen displayed on its side of the board — each circle being a node and each line being a weight. A blue weight signifies a negative value and a red weight signifies a positive value.

Getting on to the actual project, the rate at which the neural networks became “good” at the game varied on each run. In my experience, it could be as short as 100 breeds, and as long as around 2000. However, for each run, the neural networks followed the same general pattern every time — make no attempt to move for the ball, show some attempt at chasing the ball or “reacting” the ball when it came close, and successfully chasing the ball.

before

Right when the program started. You can see the paddles move to either the top or the bottom of the screen, paying no attention to the ball.

during.gif

Networks show some learning — they now react to the ball when it approaches them, though they do not move to the correct y value as of yet.

after

The end of the pattern. Networks demonstrate ability to chase after the ball and hit it every time. At this point, the match time is indefinite.

Although this project seemed simple at first, there were many different stages it went through while in development. At first, the input size for the neural networks was complex (including paddle location, ball location, ball velocity). However, after a lot of playing around, consistent improvement was shown when this list was refined to just the distance between the paddle and the ball. In retrospect, this makes sense, as decreasing the complexity of any problem makes it easier to solve. Although, maybe with more patience, a more unique strategy could have been developed with more inputs. I encourage you to download my source code and play around with yourself if you are at all interested in doing so (here).

2016 Spring AI Project – TicTacToe & Brute Search

As my senior year of high school began to slow down and the college hype began to increase, I looked for simple projects to work on while in the midst of the craziness. Looking at the history of Artificial Intelligence, I began to read up on the different methods AI developers used before modern AI existed (Neural Networks would be an example of a modern day technique). I also decided to code this project in Python in order to broaden my skills with other languages (and because Python is pretty fun to use).

Artificial Intelligence for games like TicTacToe and Minimax are prime examples of early stage AI – programs that brute search their way through an entire list of possible situations in order to find the best action to take. However, brute searching only works on games with a small amount of game boards. For instance, Minimax is a really simple game because the amount of choices and paths players can take is very limited. TicTacToe ramps it up a little (about 9! or 362,880 different ways to play the game), but is still feasible with a little bit of load time. Games like chess, however, are almost impossible to brute search just from the sheer amount of games possible (about 10^10^50 games, in fact, there are more games of chess than grains of sand on the Earth). This means that although brute searching is an alright method to use when creating game AI, it isn’t always the most efficient, and other options should be considered the more complex the game is.

One of the main roadblocks I hit along the way on this project was dealing with recursion. I am familiar with recursion and its usefulness, but for more complicated tasks like this, it can become confusing at times (especially writing in an unfamiliar language, might I add). For those who don’t know much about recursion, it’s essentially a function that calls itself in order to simplify a problem. It’s complicated in that its formation is very abstract and you have to keep some key issues in mind while creating recursive functions (i.e., making sure you don’t accidentally create a function that loops indefinitely). After some frustration / hair pulling out, I was able to overcome the challenge and write a program that performs pretty well. Basically, the AI looks at each possible choice it has and finds the probability it will win if it chooses that path taking into consideration all possible game boards extending from that board. After probabilities for each possible spot to play are calculated, the AI chooses the option with the highest probability of success.

Screen Shot 2016-03-31 at 10.24.41 PM

Here the AI is controlling Xs and I am controlling Os. You can see the AI was successfully able to perform a double attack, forcing a win for Xs.

This project was fun to make. Comparing it with the Neural Networks I’ve made this year, It’s amazing to see how far Computer Scientists have come in terms of Artificial Intelligence and the ability for computers to recognize patterns and solve problems. If you want to see the code for this project, you can get it here: https://github.com/mccloskeybr/tictactoe

2016 Spring AI Project – LD33 & Neural Networks

As my senior year of high school began to slow down and the college hype began to increase, I looked for simple projects to work on while in the midst of the craziness. Thinking that it had been a while since I had made anything relating to artificial intelligence, I wanted to refresh my mind on Neural Networks and machine learning in general. Since I needed a game to attach an AI to, I naturally thought back to my Ludum Dare 33 game (linked here), as it was a rather simple game that wouldn’t be hard for a computer to master.

I used a Neural Network (read more about Neural Networks here) with 2 input nodes (one to tell when an arrow was close and another to tell when a house was close), 2 hidden layers of 5 nodes each, and 4 output nodes (controlled each of the 4 keys required to play the game: punch, block, jump, move right). The activation function was again a sigmoid (1 / (1 + e^-4.9x)). I used a genetic algorithm with a 10% mutation rate on each gene passed down in order to weed out bad Networks and incentivize growth of good Networks.

Screen Shot 2016-03-25 at 11.11.00 PM

Graphic displaying the structure of the Neural Network I used for this project. Inputs were either a -1 or a +1 depending on whether or not its specific object was close (-1 for false, +1 for true). A key was pressed if its respective output value was > 0.5 (the range for the sinusoid I used was (-1, 1)).

Despite my belief that my game was easy, initial runs of the simulation proved that although scoring points was easy, there were too many ways to earn points, which confused the networks. The Networks easily figured out that moving right was a good way to earn points as points were given based on how many civilians are squished, but it had a hard time figuring out that it could squish civilians longer if it blocked arrows. However, after many many iterations, Networks could generally figure out a better strategy for scoring (whether it be jumping on houses to destroy them or blocking arrows). Despite the Networks learning how to score points better, I have yet to see a perfect strategy formed (one that jumps on houses AND blocks arrows), which may be solved if I ran more iterations of the simulation.

ld33aistart.gif

Starting out you can see that it doesn’t do anything. Usually, if it does anything, it holds down random keys, causing its actions to be sporadic at best.

ezgif-2212419532.gif

After ~5 minutes of the simulation running, the AI finds out that walking right is a good strategy for getting points.

ld33aiBLOCK.gif

After a considerably long time, the AI has figured out blocking is a good combo with walking, as it can walk longer distances than if it wasn’t blocking. However, it hasn’t found out that destroying houses is a good source of points.

All in all I think this was a great refresher for AI. Since I’ve been mostly working on games these past few months, it was also a good break from the grind that asset creation is becoming. Also, learning that machines aren’t always as bright as I may think they are is a great lesson to take going forward in my AI career. If you want to see the code for this you can see it here: https://github.com/mccloskeybr/LD33

2016 Spring Game Project (In Progress) – Adventures of Mark

A lot has happened since my previous update nearly a month ago. The main area of my focus has been switching from a top down view to something more isometric (think games like Earthbound), and the perspective challenges that are associated with that. I’ve also added a lot of new objects, tiles, and items (including various shops). Making this game has really opened my eyes to just how many assets and things of the like are required for not just indie-games like this, but professionally done AAA titles as well, and how difficult and tedious asset creation can be at times.

One of my more recent undertakings has been overhauling the way I create levels in the game. Before, I used a system of images where each pixel was a tile in the level, which was tedious and inefficient for a variety of reasons. Memory wise, it required a relatively large amount of effort to load each level. Making the levels themselves was also difficult because I had to use a specific set of colors with precise R, G, and B values to get the desired outcome, and didn’t get to see what the final outcome would look like until I loaded it into the game. Now, I use a level editor that I made myself that really facilitates level making because you can actually see the tiles you’re placing instead of just solid colored pixels.

Screen Shot 2016-03-15 at 12.47.26 PM

Although it is a simple editor, it has everything I need to make levels quickly and efficiently. The lighter tiles are floor tiles while the darker tiles are walls. The blank spaces are place holders while I create more tiles to be input into the game.

Screen Shot 2016-03-15 at 12.48.14 PM

The map I created inside the level editor loaded into game.

It did take a little while to complete the map editor, and I still have to add objects, but the benefits definitely outweigh the costs. Now, the tile IDs are saved to a text file that can be easily read and made into a tile map that’s loaded pretty quickly.

Screen Shot 2016-03-15 at 5.06.39 PM

The text file created by the editor to be loaded into the game. This particular text file creates the level shown above.

When I first thought of making a level editor, I thought the idea was a good one, but backed away because I wasn’t familiar with a lot of the window components needed to make one (for instance JButtons and JToolBars). However, I’m glad I worked through and figured out how everything meshes together because making it was fun and interesting, and I can make levels more efficiently from now on.

If you want to see the game as it progresses in detail, you can visit the github repo here: https://github.com/VolitionDevelopment/The-Adventures-of-Mark

2016 Spring Game Project – Plane Challenge

As my senior year of high school began to slow down, I began to look at more relaxing and laid-back  projects. Games, to me, are fairly low stress as there isn’t that much problem solving (at least at the early stages), so I decided to make a couple of games during my final semester of High School.

On my spring break trip to Grand Cayman, I decided I wanted to see how much of a game I could make on the plane ride down. This resulted in a fairly simple game that was completed in roughly 2 hours (give or take 10 minutes). Granted, I did start laying the ground work while I was waiting to board, but most of the work was done on the plane itself.

The game itself ended up being about planes. As I didn’t have too much time to work on it, I decided to make a simple endless runner in which the player dodged obstacles while trying to get as far as they could get without dying. The player, in my game, controls a plane that can move left and right, dodging debris while also picking up health packs.

Screen Shot 2016-03-06 at 11.38.42 AM

As you can see, I really whipped out my AP Drawing art skills on this one. In reality, I wanted to spend more time coding than on asset creation (which definitely shows in the final product).

One of the challenges of making this game was creating an endlessly looping background. The way I ended up doing it was having one image that was the size of the window (500 x 500 pixels) that was stacked on top of itself 3 times. The resulting picture scrolls down and when it hits a specific point (close to the end), it jumps back up exactly 1 image height and continues to scroll down, resulting in the illusion of an endlessly scrolling image.

If I had a bit more time to work on this project, I’d first add a menu, then a scoring system that went up the longer the player was alive.

I’m now going to start uploading all of my projects to Github, so exploring the code is a little bit easier. If you want to see the code for this project, you can see it here: https://github.com/mccloskeybr/PlaneProject

2016 Spring Game Project (In Progress) – The Adventures of Mark

Screen Shot 2016-02-10 at 11.51.36 PM

I’m currently working on a 2D Java game with inspiration coming from games like Final Fantasy and Undertale called The Adventures of Mark. It features a typical too-tired-for-this-shit college pizza delivery boy who must embark on an adventure down the block to earn his pay. Will his Tolerance and Brain Power hold true? Find out, nightly, on the GitHub repository featuring this project located here. This is definitely one of the larger games I’ve worked on and is filling me with more and more determination each day.

Screen Shot 2016-02-10 at 11.57.54 PM

Current state of the battle system. All of the assets (except the fonts) are drawn digitally and animated by myself.

I’m collaborating on the game with a friend of mine, Jackson Yeager (his portfolio). Although Jackson may have more knowledge than myself when it comes to various data structures, he has less experience with game making. Regardless, I’m sure both of us will learn something from this project, and I would definitely recommend you take a look at it if you’re at all interested.

I’ll be updating this post/making new ones as the game progresses.

2015 Winter Cryptography Project – P / NP, The Clique Problem

I recently read a book titled The Golden Ticket by Lance Fortnow in which the P / NP Problem and its importance to the theory of Computer Science are heavily discussed. Explained briefly, the P / NP Problem asks if every single problem can be solved quickly and efficiently. In relations to cryptography, P / NP is crucial because it allows for the creation of hard math problems to, for example, be able to hide private information on a public network. One of the most famous P / NP Problems, the Clique problem, was discussed and is, in my opinion, one of the more intriguing problems in the book.

Take, for example, a society called Frenemy, in which every citizen either has a 50% chance to be friends or a a 50% chance to be an enemy with a person they just met. In Fortnow’s book, he details how it would be virtually impossible to find all cliques of varying sizes (difficulty/time to find all cliques increases as size of desired clique increase) inside of this society (A clique is a group of people in which everyone is friends with all other members). At first, I didn’t think it would be that difficult to find the largest clique, but after making a simulation for myself, I was proven otherwise.

I stayed true to the Frenemy rules in my simulation – every time someone meets someone else, they have a 50% chance to either be their friend or their enemy. I experimented with varying population sizes as well as varying amounts of citizens in which each person can meet. I made two methods in order to experiment, one in which everyone meets everyone else in the society, and one in which everyone meets everyone on their own street (9 total streets in which 1/9 of the total population lives on each given street). To make the data easier to set up and understand, each citizen is given an identification number as well as an ‘address’, the number of street they live on. I aimed to find every single clique of size 3 in the society, and to see for myself how difficult it became to find them as population size increased.

Screen Shot 2016-01-13 at 1.49.10 PM

A couple of cliques present in a population size of 100 in which citizens met everyone on their own street.

I found that the total time to generate the population and find cliques of size 3 took much much longer the higher the population size was, which makes sense in hindsight. Adding a single citizen to a population size of 20 where everyone meets everybody doesn’t have nearly the impact as adding a citizen to a population size of 10,000,  as the number of updates a computer has to make to each citizen’s list of friends and enemies for a population of 10,000 is much larger. When I was reading Fortnow’s book, I didn’t put much thought into the rate at which the updates change as population size grows. I naively thought growth was generally linear, allowing total computations to find all cliques of size 3 to be relatively small compared to the actual value. Only after I made my own simulation did I truly understand the difficulty surrounding finding a solution to the Clique problem. If you find find yourself with some free time, I would recommend making a simple simulation like this for yourself so you can see the results firsthand.

I’d like to thank Lance Fortnow for pushing me to explore this problem through his book, as all P / NP problems (not just the Clique problem) are profoundly interesting in their own rights. And, if you’re planning to look more into the P / NP problem, Lance Fortnow’s The Golden Ticket is a must read. The discussion as well as the existence of the P / NP Problem has really expanded my understanding of Computer Science and the importance of not only the physical act of coding, but the theory behind CS as well.