3 Years War is a project I've created 3 times in different game engines, serving both as a good way to get introduced to a system and as an opportunity to iteratively improve on the same project. This final iteration was an attempt to get as bare-bones as possible for a web app, with minimal glue between its pure JS and WebGL canvas. In doing so, I signed myself up for the common folly of having to make a game engine myself.

Features

• Online Multiplayer and Basic Matchmaking (using socket.io & Node.js)
• Replay System
• Both optimized via a deterministic logic engine seperated from rendering, taking cues from Rollback-based systems
• Various necesary game engine prefabs, including:
  • Menus
  • Buttons (yes, that bare-bones)
  • Animations

As much as it pains me to admit it (and as much as I've forced it on friends and family), few care to know the theoretical details of this research. As such, I've split this project description into two components: A description of the technical difficulty involved in building solutions to this research, and the underlying question it answers. These summaries are admittedly too truncated, but I'm working off of the reasonable assumption that no one wants to read 30 pages of information about this.

The Difficulty of the Work

The program I've created can build a DFA to tell you whether or not a puzzle is solvable. To do this (in extreme summary), it finds out whether or not billions of boards are solvable. Doing this efficiently has been the name of the game, and it's proven to be a super novel and interesting optimization problem. The simplest solution to this is using BFS, which has horrific performance. Naive BFS on one of the longer boards takes so much RAM the process eventually crashes (with 16GB of RAM), and it takes an hour to get there. As a consequence, many orders of magnitude worth of memory/time optimization were required.

Current performance stats:

• average of 1.16 MICROSECONDS taken to solve a board
• Solved 310,094,073 boards in ~6 minutes
• 98% of boards solved via linear-time method (completely skipping any BFS)
• Never exceeded 40mb of RAM in the process

Solutions I've builtto solve this challenge (all in Rust):

1. Brute force BFS starting from a particular board
   • A multithreaded implementation of the same
2. Brute force BFS that consults a global hashmap to see if a board has ever been encountered before, and using those results to prematurely stop BFS.
3. Generating the set of all possible boards of a certain length by taking the set of solved boards and working backwards (Dr. Ravikumar's idea)
4. Improvement on #2 that consults a massively smaller version of the hashmap by utilizing all equivalences already found by the partial DFA
5. Improvement on #4 that also takes advantages of relations between states after a single move (this finds an answer to 90% of solvable boards in linear-time)
6. Improvement on #5 that no longer even uses BFS, instead exclusively working backwards from a truncated version of all solved boards and utilizing rule-based equivalences between states to find all accepting boards for each state. This means impossible boards are never even given any computation time.

An Explanation of the Theory (Intended to be acessible to all audiences)

To understand this project, it helps to know DFAs. A DFA can be thought of as a filter that lets in certain kinds of text and does not allow others. It has many limitations, but when something can be written as a DFA, any action related to it is massively sped up.

As an example, a DFA can be made that only lets through (accepts) a string if it contains exactly one 1.

Secondly, we are working with string rewriting systems (often formally referred to as Semi-Thue systems). An easy example of this actually comes in the form of a board game, Peg-solitaire. In Peg-solitaire, your goal is to make sure that there is only one peg remaining on the pegboard. To do this you have two options:

Whenever you see two pegs next to each other and an empty space beside, you can "jump" over the middle peg and swap the peg on the extremities. When you do that, you can get rid of the middle peg. These rules can be written as 110 -> 001 & 011 -> 100, where 1 represents a peg and 0 represents an empty spot.

An excellent article by my professor and advisor on this project, Dr. Ravikumar, proves that a DFA can be made that filters only the strings that can become a winning peg-solitaire board.

Automatically creating something that builds that DFA is quite difficult, and building such a DFA for any goal and set of string rewriting rules is the focus of my research.

Here's the cool part: any program can be expressed as a series of string rewriting rules. Automatic creation of these DFAs potentially serve as an extremely powerful source of optimization. Currently, performance requirements limit the scope of what programs can actually take advantage of this, and I do not want to give off the impression that this works for any program. Currently it works for a select group of "toy" programs but the idea that you can do it at all is extremely interesting and worth studying further.

The Down Detector was a project commissioned for me by Local Search Appeal in order to solve the visibility problem that they suffered with their websites. Before the Down Detector, they would only know that a site was down after receiving user complaints, which was often days or weeks after the actual outage had occurred and cost an untold amount in lost revenue. Beyond that, manual administration at the company meant that at certain times, phone numbers were being paid for but not being used, alongside other issues.

To solve this, Down Detector was created as a generalized hub to inform the company of any outages with any of their main services. Interfacing with a MySQL database, Down Detector maintained a list of all issues that it could monitor throughout the company, alongside when they first occurred.

The main heart of Down Detector was a cronjob on a single-core Ubuntu machine that would run our monitoring service. Based on a web-scraped copy of every domain the company needed to keep track of, more web scraping was performed on each site to check for outages or errors within commonly used site pages. Additionally, Down Detector interacted with the Call Tracking Metrics API to see if there were any potentially dormant accounts that might indicate an issue elsewhere within the company. Once any new changes had been added to the database, a list of any newfound issues would be sent via email to myself and our operations lead.

This project was created in collaboration with Amit Deb and Bella Gonzalez.

Created in the span of a couple weeks, Go Fish: Definitive Edition was our final project for CS 370 (Problem Solving in a Team Environment). Being responsible for the internal game logic, graphics rendering, and some networking, there were some complex challenges to face in that time frame. Here's the architecture that I eventually devised:

Working off of my experience with 3 Years War, I built a decoupled game logic and game rendering system. More specifically, it used a variant of the MVC paradigm, where events fired from the model went into an animation queueing system that would play back those events in the order recieved, but with delays so that gameplay was actually readable. This made things simple on the game logic end: When a player draws a card, fire an event that the card was drawn and continue running through the logic at any speed. This allowed all bot actions to be computed instantly while still allowing the player's view of events to be easily understood, alongside other benefits.

Additionally, gameplay/bot logic was completely deterministic when using seeded RNG, allowing the only messages that needed to come over the network to be the number of bots/players, player names, RNG seed, and player actions. This greatly simplified the networking, as aside from initialization, networked players could be implemented almost identically to the way that bots were implemented.

The Newkirk Award was an opportunity for students to write curriculum for SSU. Originally intended for upper-division students, Andrew Evans' proposal allowed him and I to write the curriculum for Computer Applications for Scientists as freshmen. Currently taught as a mandatory upper-division Physics class at SSU, we were only able to write this material thanks to our combined knowledge. A project-based course, much of the lesson plan was oriented around creating an animated and accurate model of the solar system. My responsibilities in this project consisted mainly of three tasks:

1. Lesson Planning

Course content was written mainly in LaTeX and consisted of 10 lessons, each intended to be taught over the course of an hour. These went from a cursory understanding of Python and Matplotlib to the more advanced and complex systems that we were going to simulate. Andrew wrote the introduction to Python while I wrote largely about the middle portion of the coursework going from the beginning of our physical simulations to a more in-depth look at Python. Naturally, thanks to the intensive nature of the end of the project, we collaboratively worked on the plan for the final weeks. We were largely given free reign to guide the structure of the course as we saw fit.

2. Homework Assignments

Accompanying each lesson plan, homework was also given via LaTeX documents and step-by-step solutions were given to faculty as separate LaTeX/Python files. Each homework assignment consisted of a few short answer problems intended to take 1 to 2 hours. Additionally, given that it was a project-based course, part of the material for each assignment was using what had been learned to add to our simulation.

3. Final Project

Being a project-based class, significant time was spent ensuring that the final project that we were working towards was reasonable to accomplish and that its steps were documented. Additionally, given that neither one of us had the expertise to make the final project solely on our own, intense collaboration was required in order to build our final result. In the end, we built a physically-accurate model of the solar system that included special relativity (in order to better simulate Mercury's orbit) alongside building a C++ version of the project made to run computationally expensive verification to confirm our model.

Written in two weeks as my final project for Computer Graphics, the accurately named Spring Simulation simulates a series of springs on Mario's face. It's based on a misremembering of the original intro to super Mario 64. I believed that you were able to move any vertex on Mario's face, and it would bounce back and forth as if his whole face was made of Jello. The final product uses three forces to simulate these physics on Mario's face when you move it. There are three forces acting on every vertex:

1. Hooke's Law: Every edge in Mario's face is treated as a spring and its desired length is the length that the edge initially starts at.
2. Returning to Origin: There's a force acting on each edge to return it to its initial position in space. Without it Mario's face would slowly drift away.
3. Drag: As simple as it gets. This just slowly reduces the velocity of any object.

Additionally, in order to fulfill the requirements for the final project, a vertex shader was added. Each vertex becomes more green the more its springs want to expand and more red the more its springs want to contract.

Demos should be available as a more integrated part of the site soon! In the meantime, you can check out the project here.