Examples of Past Programs I've Written

by Tim Macinta

• 1990 - I wrote a program in eighth grade for the now antiquated Commodore 64 which greatly improved the programmer's ability to read the joystick by eliminating the problem that Commodore created when they decided to have the keyboard and the one joystick port share the same register. I sold the program to COMPUTE! magazine and it was published. They also used it later in an advertising campaign as an example of what their magazine had to offer.

• 1993 - For my high school mathematics honors project I wrote an artificial intelligence video game that taught itself how to win given only the rules of the game. It consisted of a several thousand lines of assembly code written for the Commodore 64.

• 1994 - I wrote several programs for MIT's introductory computer science course The Structure and Interpretation of Computer Programs. A lot of the work for this class was just cookie cutter programming, but my instructor was so impressed with my work that she recommended that the department hire me as a lab assistant.

• 1995 - By this time I had officially been named the webmaster in charge of maintaining my fraternity's homepage and managing our group locker. I began writing small PERL scripts to aid in such things as sorting through mhonarc archived email and generating hyperlinked references to each reference of a particular person (the source is here.)

  This was also year that I took MIT's class Software Engineering. Taking this class immensley improved my programming ability and I learned how to document at the same time. Below are a few of the projects I did for that class listed in chronological order. The code was all written in the CLU programming language.

  • p_table - A simple lookup table.

  • main, message, router, and network - When compiled, these modules produce a program which will take in a description of a network from a file and a list of messages with origin and destination nodes on the network, and will produce a schedule for the efficeint simultaneous delivery of all the messages. The main module defines the actual program while the other modules define data types which are used directly or inderectly by main.

  • Antichess - This was my greatest accomplishment of the semester. As our final project, we were split up into groups and told to design a computer game that plays Antichess. Antichess is set up like chess, and the pieces move as in chess, but the object of the game is to lose all your pieces (possible takes are forced, and the king has no special significance). I was in charge of designing the computer player and endowing it with some level of intelligence.
    • The computer player - The computer player was supposed to be able to produce intelligent moves for a player based upon the current board arrangement. I basically used a mini-max game tree search with alpha-beta pruning with some significant alterations. One obvious optimization was that when the computer only had one possible move to make (such as when a take was forced) it made it without wasting time drudging through the mini-max tree in order to assign it a goodness rating.

      Timing was also considered heavily in the design of the computer player. In antichess, each player has a maximum five minutes to make all his moves. The computer player constanltly recalibrated itself to in order to get the most accurate estimation of how long it took to search a set number of nodes. The computer player then used this callibration along with a preset expected number of moves per game and the given time limit to determine how deep to search in the game tree on each turn. Safeguards were insterted to keep the computer player from running over the five minute time limit (It frequently won with less than one second left and several of its pieces still on the board). Safeguards were also inserted to keep the computer player from eating up too much time on one turn when alpha beta pruning wasn't as effective as usual.

      Probably the most significant alteration to the alpha-beta mini-max search was searching a set number of nodes instead of searching to a set depth. The basic premise for doing this was that if a certain depth in a mini-max search only contained two or three branches the time required to search those few nodes is an order of magnitude below the usual so an extra depth can be added to the search with no great cost. The way this was implimented was that the desired number of nodes to be searched was passed to the first node, which then split this number equally among its branches and passed it on. The child nodes of the main node would then split their number up equally among their respective children and pass it on. This process continued until the remaining nodes to be searched was below a certain small number, then the goodness of the current node was evaluated, thus initializing the alpha-beta mini-max search algorithm.

    • The static evaluator - The static evaluator was written using very simple integer addition and subtraction in order to insure maximum speed. I wrote a program that used a genetic algorithm to determine the optimal weight of the pieces for the static evaluator. (I also used a genetic algorithm to determine the optimal estimate for the nubmer of moves per game.)

    • The chess board - I also helped write a few of the methods for the central data type of the program - the chess board.

  And then I discovered Java and HotJava during the summer. My experience with Java is detailed here.