Michael Fogleman

Projects AboutResumeMore

Projects tagged "ai"

This page highlights several of my personal software projects.

Table of Contents

Rush Hour June 2018

283 Go C++ Game AI

I solved the Rush Hour puzzle game and created a database of every interesting starting position.

Rush Hour is a 6x6 sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996.

I played a clone of this game on my first iPhone several years ago. Recently, I stumbled on the physical incarnation of it and instantly bought it on Amazon for my kids to play. We've been having fun with it, but naturally I was most interested in writing some code to solve the puzzles.

I did more than write a simple puzzle solver. I ended up computing every possible puzzle and built a complete database of every "interesting" starting position. It was quite challenging (and exciting!) so I wrote a whole article about it. Check it out!

Mister Queen October 2014

146 C Game AI

Mr. Queen is a nice little chess engine written in C.

I wrote my first chess engine back in college. It didn't play very well because I never really figured out the advanced search techniques. More recently, after a long hiatus, I tried my hand at writing a chess engine again, and Mister Queen is the result. It's pretty weak among computer chess engines, but it can beat me handily. Features include:

  • Bitboards and "magic" bitboards for board representation and super-fast move generation.
  • Custom, hash-based opening book based on over three million games from the FICS database.
  • Zobrist hashing and a transposition table storing exact values and the best move.
  • Null move pruning, aspiration windows, iterative deepening, quiescence search.
  • Supports the Universal Chess Interface (UCI).
  • Passes all perft tests.

David Kopec used Mister Queen in a chess app for the Apple TV! Read what he wrote about that here.

Ricochet Robot February 2012

54 Python C Game AI

Implementation of a board game called Ricochet Robot including a GUI and a very fast solver.

My friend introduced me to a board game called Ricochet Robot (or Rasende Roboter in its original German form). It's a fun game, but I found it even more fun as a programming problem. I implemented the game in Python, including a user interface and a solver. After that, I sped up the solver tremendously by porting it to C. My solver includes several "tricks" that make it quite fast. See these slides for more details.

Word Warrior April 2006

3 Java Words Game AI

An alternative client for the Internet Scrabble Club.

In the mid 2000s, I often played Scrabble on the Internet Scrabble Club, which was not an official Scrabble website. Thousands of people played online there, but the client was horrible and buggy. I took it upon myself to write my own client, which involved reverse engineering the protocol to communicate with the server. I discovered many security issues (cheating vectors) while doing this. But I just wanted a nice client for playing Scrabble online. I pretty much finished the client, and it worked quite nicely, but it never went much further than that and who knows if it still works.

Future Blocks April 2000

26 QBasic Game AI

Tetris clone that I wrote long ago in high school.

I wrote TONS of programs in QBasic throughout high school. Most of them are lost forever, but a few have survived. I've put a couple programs, including this one, on the Internet Archive for eternal posterity, and there you can play them in the browser. This is a simple Tetris clone but it even includes a computer player that plays quite well!