Minimax Algorithms

Hello World!

In the fall I'm going to have a class in C++, so I'm hoping to get a head start by making an AI tic-tac-toe player in C++! Tic-tac-toe has been “solved“, which means that there are (sometimes multiple) objectively correct moves for every situation. As a result, it’s fairly easy to teach a machine how to play it.

Artificial Intelligence is a huge umbrella term. It includes supervised learning, unsupervised learning, and many other techniques. AI typically means neuronets these days, but not always. In this case, I used a minimax algorithm. The machine analyzed all future states of the game, and determined which would result in the most victories. It then chose that move. This is the same strategy that Deep Blue the chessbot used in 1997 to beat Kasperov, so I called my AI Shallow Blue.

It took a while, and I encountered many dead ends, after two switches of IDEs and several days, I got it working! After a few days I thought I had a solution. I played the game a few times, and it either tied or won. Then I gave it to my dad and brother, and every game they played, they were able to beat the AI! So I went back to the drawing board and designed a new type of minimax function. It was based off of this implementation, but in C++ rather than python, and I constructed the Board and Player objects a bit differently.

I also learned a lot about about making smart debug messages! Debug messages are when you have the code output something that will tell you about what exactly your code is doing. There was one function that I didn’t think was every being called, so I instructed it to output “woot” whenever it ran. Turns out it was called quite often.

As of now, it the project still incomplete. It compiles, but it doesn’t win every game. I might finish it as some point, but as of now I have other things to do and I’ve learned what I was hoping to learn. I am told that this is the sad fate of all side projects, and while I promised myself when I started that I wouldn’t end up doing this, it appears that I will end up allowing my side project to languish along with all the other uncompleted side projects. Oh well.

In other news, I got a research gig with Professor Lowe-Power at UC Davis! Other than having the hands-down best name for an engineering professor, Lowe-Power is researching computer architecture, and is currently working on the gem5 simulator! I won't be working on the simulator itself, instead I will be designing a web application which will translate the results into human readable data. This might end up being my job next summer, which would be nice because I could take Davis classes on the side, but would be a bummer because I wouldn’t get paid, and would instead have to rely on Future Mira who is already completely screwed by college loans.

Turns out the cybersecurity club at Davis has been invited back to CPTC at Stanford! CPTC at Stanford is one of the biggest cybersecurity competitions in the country, where universities from all over the US compete in a capture-the-flag style hacking competition. These competitions are generally structured so that there are several codes, called ‘flags’, hidden in some operating system or network system. Your goal is to find all the flags before the time is up. In a well-designed CTF, each flag will be hidden in a different part of the network, and it will take different skills to get to each flag. I’m going with them to compete, and while I know almost nothing, I should learn a lot and am very excited.

At work, I’m translating my bash script to python. As I mentioned previously, the program that runs NIF is very messy. Java code compiles to a ‘JAR’ file, which is then run, and does whatever you programmed it to do. When you have a large codebase, you may want to compile to several different JAR files, and the NIF controls code has very many different JAR files. They all depend on each other to run. In addition, these JAR files depend on third-party JAR files downloaded from the internet, and these third-party JAR files depend on other files, and it’s a huge mess. So I wrote a BASH script to analyze the files and their dependencies, and produces HTML code that lists the dependencies, the classes contained within the JAR file, files that depend on it, hash functions which ensure that the code has not been corrupted, and the manifest file which is a file that is put in most jar files which sometimes gives information about the JAR, and is sometimes useless. Since the generated files are in HTML, which is what webpages are written in, the list of dependencies is made of links that link to the HTML files generated for those jar files. Unfortunately, writing BASH that outputs HTML is an abomination. BASH was never meant to do stuff other than make operating system tasks easier. So I’m translating it to python so it will be easier to maintain.Also, I’m improving the CSS code of the files so that they look nicer and are more readable. CSS is the code used in webpages when you are trying to make the webpage look nice, rather than a bunch of text and maybe some boxes. I typically focus on function rather than style, so working on CSS is a nice challenge for me.

May you be ever victorious in your future endeavors!
M.E.W