In an effort to learn more about AI programming techniques, I'm trying to port M. Tim Jones' AI Application Programming examples from C to Ruby. I'm planning to port these (porting notes are here) in no particular order.

• Simulated Annealing
• Adaptive Resonance Theory
• Ant Algorithms
• Neural Networks and the Backpropagation Algorithm
• Genetic Algorithms
• Artificial Life
• Expert Systems
• Fuzzy Logic
• The Bigram Model (Hidden Markov Models)
• Intelligent Agents

The errata for the book is posted on Tim's web site.

This project is hosted by RubyForge, forums and such-like are here.

Chapter 2 - Simulated Annealing

Updated 10/23/03: Done with translation of the n-Queens solver, code is here. Here's a solution to a 16 queen board (took about 15 hours (!!) to run):

. . . . . . Q . . . . . . . . .
. . . . . . . . Q . . . . . . .
. . Q . . . . . . . . . . . . .
. . . . . . . . . . . . . Q . .
. . . Q . . . . . . . . . . . .
. . . . . . . . . Q . . . . . .
. . . . . . . . . . . . . . . Q
. . . . Q . . . . . . . . . . .
Q . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . Q .
. . . . . . . . . . . . Q . . .
. . . . . . . Q . . . . . . . .
. Q . . . . . . . . . . . . . .
. . . . . . . . . . . Q . . . .
. . . . . Q . . . . . . . . . .
. . . . . . . . . . Q . . . . .

Chapter 3 - Adaptive Resonance Theory

Updated 4/24/04: Done with the translation of the "Customer Personalization" example; code is here. Not too tricky a translation; only about 450 lines of C code.

Here's some sample output:

For customer 0, the best recommendation is 2 (Snickers)
Owned by 2 out of 3 members of this cluster
Already owns: Kit-Kat Heath-Bar
For customer 1, the best recommendation is 4 (Pen)
Owned by 1 out of 2 members of this cluster
Already owns: Paper Pencil Binder
For customer 2, the best recommendation is 0 (Hammer)
Owned by 2 out of 3 members of this cluster
Already owns: Screwdriver Wrench Tape-Measure

• Refactored some of the 2D arrays into a Vector class
• Doing some array traversal - can it be replaced with Array.select or Array.collect?

Chapter 4 - Ant Algorithms

Updated 10/22/03: Traveling Salesman via ant algorithm is done, code is here.

• TODO: Refactor the code a bit more; use more objects and fewer array indexes
• Here's the graph of the cities and the calculated shortest path for 30 cities traversed by 30 ants. It took 90 seconds to run:

  

Chapter 5 - Neural Networks and the Backpropagation Algorithm

Updated 03/11/04: Game neurocontroller translation is done, code is here. This was a fairly easy one to translate, and some sizeable duplicate chunks were easy to refactor away.

• Here's a sample output:

  [tom@hal ch5]$ ./backprop.rb
  Network is 100% correct
  2111 action Attack
  1112 action Hide
  0000 action Wander
  0111 action Hide
  2013 action Hide
  2103 action Hide
  0103 action Run
  [tom@hal ch5]$
  

Chapter 6 - Genetic Algorithms

Updated 04/23/04: Done, code is here.

• Solved an example system (xy + (y*2) + z) in around 10 seconds with with MAX_PROGRAM of 8:

  Generation 0
          Maximum fitness = 200.000000 (380)
          Average fitness = 14.066667
          Minimum fitness = 0.000000
          Crossovers = 1219
          Mutations = 521
          Percentage = 0.070333
  Generation 1
          Maximum fitness = 380.000000 (380)
          Average fitness = 16.601667
          Minimum fitness = 0.000000
          Crossovers = 1211
          Mutations = 465
          Percentage = 0.043689
  Found solution
  Program 2925 : 04 01 02 04 03 03 03
  Fitness 380
  

• Bounced some emails back and forth with Tim; seems like large values of MAX_PROGRAM tend to cause problems since they contain lots of NOPs and SWAPs. 8 instructions seems to be a good place to start.
• Refactored out various classes - Generation, StackMachine, Stack, Population. Still more to do, I'm sure.

Chapter 7 - Artificial Life

Updated 11/14/03: About 30% done, code is here. This is going to take a while; there are about 1050 lines of code to translate, while other chapters had much less - simulated annealing, for example, was only 280 lines of code. On the other hand, a lot of the code is just disappearing and being replaced with calls to Array.collect and the like. Yay!

Chapter 8 - Expert Systems

Updated 7/13/04: Working on rule parser, can parse antecedents and consequents now.

Chapter 9 - Fuzzy Logic

Updated 10/16/03: Battery charger and predator prey examples complete, code is here.

• The predator/prey example was fun because I had to relearn some trigonometry. Also, I had to tweak the membership functions a bit - the first time through I made the center spike profile too wide and so the predator kept waiting too long to turn towards the prey.
• To regenerate the predator graph:

  ./fuzzy.rb < predator_data.txt && ./predator_gnuplot

• To regenerate the battery graph:

  ./fuzzy.rb -battery < battery_data.txt && ./battery_gnuplot

• TODO: Write partial FCL parser, encode rules, load from file

Battery charger example: below is a graph (thanks gnuplot!) showing the relationships between the battery's voltage and temperature - you can see when the fast charger kicks in and when it falls back to trickle charge mode.

Predator/prey example: below is an image of the predator seeing the prey and turning towards it.

Chapter 10 - The Bigram Model

10/30/03: Done, code is here. Here's a sample run (I used some quotes from C. S. Lewis as the corpus):

 It is always something couldn't guessed That's one reasons I suppose must conclude.
 It's Badness is idle talk any final victory over materialism No Christian indeed no good game without rules In.
 Safety happiness can only cobblers to say whether teeth were being well governed Everything except some natural inferior.
 When humans should have need of the reasons It's a real Right and the percentage cannot increased.
 Perfect humility dispenses with the first sketch As long as judging value result Who can be found to the.

TODO: Refactor some of those arrays into classes - especially bigram_array.

Porting notes

• The code in this book doesn't use setjmp() or doubly-indirect pointers or other hairy C stuff - it's mostly just loops and functions. This makes porting it a lot easier.

• I'm porting in several steps:
  1. Do an initial "raw" port by just translating C to Ruby
  2. Pick a blob of associated data items, refactor them into a Ruby class
  3. Add tests, back to step 2

• Ruby is _so_ much less wordy than C - not having to type all the parentheses and semicolons and such is really nice.

• If someone wanted to do this and preserve speed, it'd probably be best to just write Ruby extensions that wrap the AI stuff (thx to Rich Kilmer for this comment)

• Writing more tests will alleviate some problems I'm having - i.e., forgetting the "@" on a instance variable. It's kind of an odd situation, though... I don't really understand how some of the algorithms work, so writing tests for them is hard since I have to step thru the entire function with sample values. I feel like the tests I'm writing are too high-level or something.

• Watch for C code like this:

  if (foo) {
  	/* do something */
  }
  

  It needs to be translated to

  if foo != 0 
  	# do something
  end
  

  in Ruby. In other words. "non zero" in C needs to be translated to "not nil and not zero" in Ruby.

• A do..while forever loop in C can be done like this in Ruby:

  loop do
  	# do stuff
  end
  

  Thanks to Brian Schroeder for suggesting this idiom vs my previous idea of while [loop body] end until !true

• Translate pre- and post-increment statements correctly. C code like this:

  int x = 0;
  printf("Value = %d\n", x++);
  

  prints out "Value = 0". Since Ruby doesn't have an postincrement operator, make sure you put the incrementor _after_ the print statement. Like this:

  x = 0
  puts "Value = #{x}\n"
  x += 1
  

  This bit me something fierce on the Ant Algorithm code. Of course, what really bit me was that I didn't write any unit tests. Gack.

• C has the static keyword which can be used inside functions to indicate that a variable is only initialized once. This translates to a class-level variable in Ruby. At least, that's the best comparison I can think of at the moment, comments are welcome.

• Some fairly verbose C idioms can go away when converting to Ruby... for example, instead of manually traversing an array to find the largest element, just use Array.max. Thanks to Charles Comstock for suggesting this in lieu of my original suggestion of the O(n) Array.sort[0].

• If the C code references RAND_MAX, it's defined in stdlib.h. On my Linux 2.4 workstation it's 2147483647.

• The preprocessor can be tricky. If you've got C code like:

  #define RAND_WEIGHT ( ((float)rand() / (float)RAND_MAX) - 0.5)
  

  remember that a call to the rand() function is being inserted each time the preprocessor expands the macro. So you can't just define a Ruby constant RAND_WEIGHT - if you do, you'll always get the same value. You need to define a new rand_weight method and call that instead.