Where the spirit does not
work with the hand,
there is no art.

- Leonardo da Vinci

0 0 0 0 0 0


I was part of the first graduating class in CS at Cornell not to have to be affiliated with a specific specialization but to be told that CS majors would soon have to do so. Supposedly the department was getting so large that it would have to be split into four individual majors. In fact, I graduated with more fellow CS majors than were matriculated in the entire ILR school.

Computer graphics and artificial intelligence were two of the proposed new departments, but apparently this division still hasn't happened. If it had split before my time, I would have chosen AI in a heartbeat. My AI classes were the only ones I actually enjoyed.

Decision Tree Learning

This is a simple concept that can end up being pretty powerful for classification based on attributes. I haven't found a lot of practical applications for it in game theory, but I did make one (failed) attempt to apply it to image recognition. The basic concept involves measuring the information gain by dividing the data set on each attribute at each branch in the decision tree, by calculating the change in the entropy of the data set. It's a lot simpler than it looks.

I was learning PHP at the time. D-tree learning is a perfect fit with database structures, so I got permission from my professor to use PHP + MySQL instead of the standard Java. I ended up needing to write a lot less code than everyone else.

. dtree.php . id3.php

Genetic Algorithms

Genetic programming is fascinating. I read a story once about someone using genetic principles to arrange FPGAs to perform a particular function, and the resulting arrangement included one that wasn't even logically connected to the others. Apparently the inductance caused by this extra array was beneficial to the resulting output of the whole arrangement.

Unfortunately, genetic algorithms are best suited to Lisp, a language I never bothered to learn. However, we did get a chance to play with the concept using Java. One of our assignments required us to write a program to color the squares of a 10x10 matrix so that no row or column contained the same color. It's a fairly trivial problem, but we had to do it by randomly coloring each square and determining the resulting fitness of the coloration. We then iteratively evolved our solution by randomly coloring tiles based on a measure of how likely they were to improve the solution. It actually converged surprisingly quickly.

This was one of the strategies I tried for solving Paint by Number and Battleships puzzles. It didn't work very well.

Neural Networks

This a very promising field of research, with many practical applications from game theory (e.g. Tesauro's TD-Gammon) to computer vision and unmanned vehicle operation (e.g. Carnegie Mellon's Navlab Project) to image recognition (e.g. Flo Control). They are modeled after our own brains, which are vastly more complex than computers but also vastly slower. It probably won't be long before computers will be emulate very complex human behaviors.

I've done a little bit with neural network programming, but the problems I tried to solve with neural nets weren't very well suited for it. I began the process of defining the structure and training regimen for a neural net that could play hearts, but I quickly determined that the scope of that project was much larger than the time I had to complete it for my class. I then changed my target game to Blackjack, but also had little success.

. heartsneuralnet.txt . bjnntrainer.java . bjanalysis.pdf

pruned search

I've done most AI programming using pruned search algorithms. These are very useful in games with a predefined set of valid moves with no random elements during gameplay (especially most solitaire card games). A simple depth-first search is easy to implement, as it simply involves trying all available moves in turn. If an end state is reached, the algorithm then backtracks and performs the next available move from the previous branch.

Unfortunately, I don't have a quantum computer yet, so unless I want to wait around for a few weeks to see the solution to a particular problem, some pruning has to be done on these searches to keep the program from trying moves that can be calculated to be bad.

I've written quite a few of these to play various games that seemed interesting to solve programmatically. I love word games, particularly Scrabble (and Yahoo's version, Literati). I wrote an extremely fast program that generates the top fifty moves for a given set of tiles and board arrangement. I play a lot of Pogo games, as well, and I wrote a program that finds the best solutions for Perfect Pair Solitaire hands. It's reasonably fast, but not perfect.

Some people call this cheating. I don't use either of these programs when I'm playing, though. There isn't much fun in winning a game if you didn't win it on your own. I actually have a better time writing these programs than playing the game itself, sometimes. I like the challenge of problem solving. I guess that's why I was in the engineering school, not arts.

[ Next]

[identity] [home] [verbosity]


[ ]