Computer Go reference bots

Interested in Computer Go? Then you probably already know about Don Dailey's excellent work on providing a number of Monte Carlo reference implementations. So far, he has managed to implement it in two three different languages (Java, C and some language called Vala).

The announcement is here and the Java bot is available here. It's not the prettiest Java code out there, but Don is a C programmer (I think) so he is excused. It was very interesting and educating to study the code. I've been reading a lot of the Monte Carlo Computer Go papers but I've always felt as if I've missed something fundamental since my understanding of how it works felt too... simple.

Now that I've seen the code I can say, with confidence, that it *is* quite simple. Implementing a Monte Carlo method, that is. Getting a decent (let alone, good) AI-player for 19x19 Go seems quite far from simple.

Pattern matching function declarations in Python part II

Ok, so the pattern matching idea kind of backfired.

I was under the impression that a function's default arguments wouldn't be evaluated until the function was called. Which would have meant that I could've changed them, into valid Python code, in the decorator function. But... that's not the way it works.

My first attempt at something more interesting than matching a constant failed miserably. I wanted to use a variable to constrain that matching process. For example:

>>> @patternmatched
... def foo(lst = [__, var, var, __]):
...   pass

should match any lst which is a list and where there is, at least one, repeated element somewhere in it. Both [1,1,2,3,4] and [3,2,1,1,2] should match, whilst [1,2,1,3,1] shouldn't.

Unfortunately. Trying the above results in a NameError since both __ and var are unbound. And, seeing that, I remembered that this is *exactly* what happened about three years ago when I was trying out various syntaxes for PyRete. It's the reason I decided to put all of the matching in the if-statement instead of in the function arguments.

But, it's not quite time yet to give up. There are several possible ways to go about this. The "best" choice is probably to use Andrew's python4ply, or maybe PyPy. Either way, I'll get a chance to compare and contrast the work of implementing a DSL in Python versus Common Lisp.

Handling defrules in MPS, executing the RHS

I've been rewriting the deftemplate code for MPS more or less from scratch... but I'll have to talk about that some other time. It's high time to focus on the defrule macro(s). I'll break this up into several posts and I'll start with the function for executing the RHS.

The MPS syntax (a subset of CLIPS') for defrule looks like this:

  defrule-construct
    ::= (defrule rule-name
          conditional-element*
          =>
          expression*)

  conditional-element
    ::= template-pattern-CE ¦ assigned-pattern-CE ¦
        not-CE ¦ and-CE ¦ or-CE ¦ test-CE ¦
        exists-CE ¦ forall-CE

  assigned-pattern-CE
    ::= single-field-variable <- template-pattern-CE

  not-CE     ::= (not conditional-element)
  and-CE     ::= (and conditional-element+)
  or-CE      ::= (or conditional-element+)
  test-CE    ::= (test function-call)
  exists-CE  ::= (exists conditional-element+)
  forall-CE  ::= (forall conditional-element
                         conditional-element+)

  template-pattern-CE
    ::= (deftemplate-name single-field-LHS-slot*)

  single-field-LHS-slot
    ::= (slot-name constraint)

  constraint ::= ?  connected-constraint


  connected-constraint
    ::= single-constraint ¦
        single-constraint & connected-constraint
        single-constraint ¦ connected-constraint

  single-constraint
    ::= term ¦ ~term

  term       ::= constant ¦ single-field-variable ¦
                 :function-call ¦ =function-call

  single-field-variable
    ::= ?variable-symbol

I'm quite far from having all of the above supported, but I've got enough to show how the function that executes the RHS of a rule works.

The defrule macro works by expanding into a series of macro calls which handle more and more specific cases in the processing. The macro itself is quite simple

(defmacro defrule (name &body body)
  (let ((rhs (cdr (member '=> body)))
        (lhs (ldiff body (member '=> body))))
    `(progn
       (compile-lhs ,name ,@lhs)
       (compile-rhs ,name ,@rhs))))

As you can see, it expands into two other macro-calls: compile-lhs and compile-rhs, where the first parses the conditional-elements and, in the process, creates two symbol-tables (fact-bindings and variable-bindings) with all of the variables it can find.

The second macro handles the RHS and looks like this:

(defmacro compile-rhs (name &body rhs)
  (when (null rhs)
    (setf rhs '(t)))
  `(defun ,(make-sym "RHS/" name) (activation)
     (let* ((token (activation-token activation))
            ,@(mapcar #'make-fact-binding (reverse fact-bindings))
            ,@(mapcar #'make-variable-binding (reverse variable-bindings)))
       ,@rhs)))

So, if we evaluate this:

MPS> (defrule foobar
       ?foo <- (foo (bar ?bar) (baz 1))
        =>
       (format t "~%~A ~A" ?foo ?bar))

it expands into this (among other things):

(DEFUN RHS/FOOBAR (ACTIVATION)
  (LET* ((TOKEN (ACTIVATION-TOKEN ACTIVATION))
         (?FOO (NTH 0 TOKEN))
         (?BAR (DEFTEMPLATE/FOO-BAR ?FOO)))
    (FORMAT T "~%~A ~A" ?FOO ?BAR)))

Most of the work is with figuring out how to assign values to each of the variables. I'm using a simple list as the structure for the tokens. WMEs (fact objects) are added in the order they appear in the list of conditional elements. Once all of the WMEs are bound, all of the variable-bindings are bound by using the automatically constructed accessor methods for those structs.

The actions in the RHS are simply spliced into the let* form at macro-expansion time which completes the function definition. It is then evaluated and stored with the rule's production node. Later, when that production node is left-activated, it creates an activation (with the WMEs and some additional meta-data like timestamps and such) and places it in the conflict-set. If that activation ever triggers a rule, it is passed as an argument to the RHS function.

Since I haven't got enough of "the rest" of MPS in place. We're going to have to mock an activation and call the function directly to see whether or not it works.

MPS> (rhs/foobar (make-activation :token (list (foo (bar 1) (baz 1)))))
#S(DEFTEMPLATE/FOO :BAR 1 :BAZ 1) 1
NIL
MPS>

There's really not much more to say about the RHS so I'll stop here. The LHS is a bit more complicated and I hope that I can show some of that code soon.

Pattern matching function declarations in Python

All those who have tried to write a rules-based program know that there are, at least, two differences between "regular" programming and rules-based programming. The first is that you have no direct control over the flow of execution and the second is that, instead of specifying input parameters, you specify patterns that should be matched for a certain "function" (or rule) to be invoked.

The bit about giving up control is quite difficult for most programmers (at least the ones I know) and it doesn't translate well to other types of programming anyway. But it would be interesting to try and add pattern matching functions to a language such as Python and see whether it could be useful (or at least fun to experiment with).

It's not a new idea. The first language to support pattern matching this way was Snobol (version 4 I think) which was introduced in the late 60s/early 70s. Both Haskell and Erlang has it and there are a bunch of others as well, Qi and Prolog to mention a few.

I'm thinking about something along the lines of:

>>> from patternmatching import *
>>> @patternmatched
... def fac(n = 0):
...   return 1
...
>>> @patternmatched
... def fac(n = int):
...   return n* fac(n = n-1)
...
>>> fac(5)
120
>>>

The idea is that the first function would handle any calls to the fac function where the parameter n is 0 and the second function would handle any calls where the parameter n is an int (but not 0). And, yes. I've got the above working already. The tricky bits are providing more elaborate forms of pattern matching with the available syntax.

I'll be back shortly with some code...

When should I use a rule engine?

This is an interesting question that I think about quite a lot. I consider myself somewhat of a rule engine evangelist and I've always felt a bit annoyed that it's so difficult to explain the benefits of a rules based approach to others.

The textbook answer to the question is that a rule engine should be used when the problem is ill-structured and the solution is difficult or impractical to describe with an algorithm or when the knowledge required to formulate a solution changes frequently. But that's just words.

I've tried to find an ill-structured problem that is small enough to use as an example but I'm not really sure one exists. The best I've got so far is the problem of translating a number to text, where 0 <= number <= 99. It's an ill-structured problem that is easy to grasp but still translates to an ugly implementation with a lot of special-cases-handling in most programming languages. Not that it translates to a very pretty CLIPS application either... but I guess that comes with the territory.

Anyone got a better idea?

CLIPS is not a Lisp

In a recent thread on JBoss Drools' Rules Users mailing list, Mark Proctor writes:

... The Drools DRL language itself was designed as a more intuitive and less verbose language, this becomes increasinly important as you start to add more complex syntax which becomes harder to read with a lisp approach. I think most people in here would agree that the Drools DRL approach is an improvement over the lisp approach of clips/jess - apart from the die hard lisp fans.

I might be a die hard Lisp fan, but if you ask me, the problem is not that CLIPS (and Jess) are Lisp-like it's that they are Lisp-like.

CLIPS doesn't use a Lisp approach. It might look that way, but the similarities are only skin-deep. CLIPS lack one of the most fundamental requirements for being Lispy, namely, code as data. It lacks other things as well, but given that capacity (or in other words to be able to provide a higher level syntactical abstraction on top of CLIPS) there would be nothing wrong with CLIPS syntax that couldn't be fixed with CLIPS syntax. Yes. I know about build and eval but they'll only take you so far. It's not that I'm unhappy with CLIPS, but I honestly believe a Lisp-based CLIPS would be so much better.

My apologies to Mark. This rant has nothing to do with JBoss Drools. It's just that his post had the magic words in it ;-)

Structuring data via behavioural synthesis

I am one of the those who have been (and some still are, I guess) waiting for Geoff Wozniak to post a link to his thesis, Structuring data via behavioural synthesis, on his blog Exploring Lisp. To my surprise, it turns out that someone at the University of Western Ontario has published it already, only "bad" thing with that is of course that now I want to see the code even more.

Working out some kinks

I've been a student of Lisp(s) for roughly five years now. Unfortunately, sometimes, pretty simple bugs show up and bite me. I'm a bit embarrassed to say this but... I haven't written anything about MPS for a while because I've had a problem with the proof-of-concept code. Or, so I thought. It turned out that the agenda function used mapcan instead of mapcar. Funny (well...) thing is that since I thought it used mapcar it took me quite a while to find it.

CrazyStone vs Aoba Kaori

Yet another Computer Go program wins a handicap game (8 stones) against a professional Go player. Earlier today, CrazyStone (running on a PC with 8 processors) played Aoba Kaori (4P) at the FIT2008 conference (here are some photos) and won by resignation.

In a couple of weeks, MoGo plays Myungwan Kim (again) at the Cotsen Go Tournament. It will be interesting to see whether or not they can repeat the success from the US Go Congress. I have a feeling that Kim will have adapted to MoGo's playing style.

Roman numerals

Yesterday we had another GothPy meeting. Apart from getting some formalities out of the way, Emily showed us how to do the FizzBuzz kata in just over 4 minutes. Quite impressive. This was one of the things she and Michael Feathers had done for the Programming with the Stars competition at Agile 2008.

We were also supposed to tackle a "new" kata, converting numbers to roman numerals, but a debate about what rules should be used to guide the conversion (for example, should 1999 be 'IMM' or 'MCMXCIX'?) got us into doing an english translation instead (converting numbers to english text). And as the smug Lisp weenie I have turned into I couldn't help but to inform everyone that the built-in format directives ~@R and ~R solves those problems quite neatly. The hard part is of course to write the Lisp implementation ;-)

Anyway, as usual, it turned out we thought about the problem a bit differently but we quickly converged around a "good enough" strategy even though it wasn't particularly pretty and we ended up with lots of code duplication. I learned a lot though. It put my previous solution in a different light and it's always interesting to see and hear how others tackle awkward problems like this.

And BTW. Here is my attempt at the Roman numerals kata (using doctest):

def as_roman_numeral(num):
   """
   Returns a string containing the roman numeral representation of num or
   None if num is outside of range(1,4000).
 
   >>> as_roman_numeral(4000) == None
   True
   >>> as_roman_numeral(1)
   'I'
   >>> as_roman_numeral(99)
   'XCIX'
   >>> as_roman_numeral(888)
   'DCCCLXXXVIII'
   >>> as_roman_numeral(1999)
   'MCMXCIX'
   >>> as_roman_numeral(2001)
   'MMI'
   """
 
   units       = [0, 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
   tens        = [0, 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
   hundreds    = [0, 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
   thousands   = [0, 'M', 'MM', 'MMM']
 
   if num in xrange(1,4000):
       th, mils = num//1000, num%1000
       h, cents = mils//100, mils%100
       te, u    = cents//10, cents%10
       return "".join(numerals[digit] for digit, numerals in [(th, thousands),
                                                              (h, hundreds),
                                                              (te, tens),
                                                              (u, units)] if digit > 0)
   else:
       return None

It works with numbers in range(1,4000) and it implements the rules as described on Wikipedia.

MPS inference engine, the rest of the implementation

In the last post I mentioned a few of the design choices I've made for the Rete Network implementation. The rest of the engine is quite straight forward and simple. There's really not much to talk about but I'll show some code anyway ;-).

Another thing though, and a bit more interesting really, is that I have been thinking about whether or not I should try to stay true to CLIPS' behaviour and functionality in the misc engine functions as well.

For example, the agenda function currently returns a list of all activations on the agenda and CLIPS prints them but returns no value. Similarly there's facts which behaves like get-fact-list instead. Used at the REPL there's little difference in what the user sees but the reason I've made them different is because then I can write other functions on top of them.

Ok. As promised, some code. Here is the run function (which uses agenda):

|(defun run (&optional (limit -1))
|  (do* ((curr-agenda (agenda) (agenda))
|        (execution-count 0 (+ execution-count 1))
|        (limit limit (- limit 1)))
|       ((or (eq limit 0)
|            (= (length curr-agenda) 0)) execution-count)
|    (let* ((activation (first curr-agenda))
|           (rhs-func (make-sym "RHS-" (string (activation-rule activation))))
|           (prod-mem (make-sym "PRODUCTION-" (string (activation-rule activation)) "-MEMORY")))
|      (funcall rhs-func activation)
|      (store '- activation prod-mem))))

and here is the assert function (I'm shadowing the built-in assert function, still accessible as cl:assert though):

|(defun assert (&rest facts)
|  (incf timestamp)
|  (dolist (fact facts)
|    (store '+ fact 'working-memory)
|    (mapcar #'(lambda (node) (funcall node '+ fact timestamp))
|            (gethash (type-of fact) (gethash 'root rete-network)))))

I hope that they are at least somewhat readable to others.

I've now finished the functions that make up the inference engine implementation. And it works... as long as you manually divide your program into alpha, beta and production nodes and connect them properly in the Rete Network ;-)

MPS inference engine, the Rete Network implementation

It's difficult to talk about the MPS defrule macro and the code it expands to without first explaining the environment in which it is meant to run. So I'll try to explain and describe my current thoughts and ideas that make up the design of the MPS inference engine in this and following posts.

The engine is made up of some I/O functions (assert and retract), the Rete Network, a Conflict Resolver and an Execution Engine. The Rete Network is the most central part of the whole thing so I'll start there.

It is basically implemented within a hash-table. This is the simplest possible representation of a Rete Network that I can think of. There are, of course, a few helper functions to abstract away some of the book keeping details of this design choice. During rule compilation there are functions for adding a node/memory and connecting nodes/memories with each other and at run time there are functions to propagate facts/tokens, access contents of and store facts/tokens in memory.

A processing node (for example an alpha node) is implemented as a function and is stored in the hash-table as well. A very simple LHS construct like:

|(defrule foo
|  (bar (baz ?baz&:(> ?baz 10)))
|  =>)

would be represented in the Rete Network by the following function:

|(defun bar-baz->-10 (key fact timestamp)
|  (when (> (deftemplate/bar-baz fact) 10)
|    (store key fact 'bar-baz->-10-memory)
|    (propagate key fact timestamp 'bar-baz->-10)))

A join node is represented by two functions (one for left and one for right activation) and is slightly more complex (but not much). If we change the LHS to:

|(defrule foo
|  (bar-1 (baz ?baz))
|  (bar-2 (baz ?baz))
|  =>)

we would have to create a join node for joining facts on the ?baz variable. It would look something like this:

|(let ((left-memory  'bind-bar-1-memory)
|      (right-memory 'bind-bar-2-memory))
|  (defun join-bar-1-baz-and-bar-2-baz-left (key token timestamp)
|    (dolist (fact (contents-of right-memory))
|      (when (eq (bar-1-baz (nth 0 token))
|                (bar-2-baz fact))
|        (store key (append token (list fact)) 'join-bar-1-baz-and-bar-2-baz-memory)
|        (propagate key (append token (list fact)) timestamp 'join-bar-1-baz-and-bar-2-baz))))
|
|  (defun join-bar-1-baz-and-bar-2-baz-right (key fact timestamp)
|    (dolist (token (contents-of left-memory))
|      (when (eq (bar-1-baz (nth 0 token))
|                (bar-2-baz fact))
|        (store key (append token (list fact)) 'join-bar-1-baz-and-bar-2-baz-memory)
|        (propagate key (append token (list fact)) timestamp 'join-bar-1-baz-and-bar-2-baz)))))

As you can see variables are expanded into "positions" everywhere in the functions. Variables are, however, available and bound in the execution context of the production node's RHS function.

There are some more bits and pieces that are good to know. The root node, for example, is a hash-table. Each deftemplate-type is a key and the value contains a list of alpha nodes.

Compilation consists of (apart from expanding the rule's LHS into a number of functions) a series of calls to add-to-root and connect-nodes. Since each node is responsible for propagating as well as storing facts/tokens in memory we can connect the processing nodes to each other directly. The example above would be compiled with:

|(add-to-root 'bar-1 #'bind-bar-1) ; This might not be necessary! We should
|(add-to-root 'bar-2 #'bind-bar-2) ; be able to connect directly to the join.
|(connect-nodes 'bind-bar-1 #'join-bar-1-baz-and-bar-2-baz-left)
|(connect-nodes 'bind-bar-2 #'join-bar-1-baz-and-bar-2-baz-right)
|(connect-nodes 'join-bar-1-baz-and-bar-2-baz #'production-foo)

This is all theory, though. I don't actually have all of the defrule macro in place so the final version might very well expand into something different. But I hope this conveys the general idea of the Rete Network implementation.

Handling deftemplates in MPS

There are three parts to my MPS (Minimal Production System) experiment, the "engine" itself and the deftemplate and defrule macros. So far, I've spent most of my time on the deftemplate macro. It turned out to be a bit trickier than I thought to implement. Mostly because I was stuck thinking about too complex macro expansions (which I never got to work).

Here is the syntax as BNF (well, sort of[1]):

|  deftemplate-construct
|    ::= (deftemplate deftemplate-name
|                     [comment]
|                     single-slot-definition*)
|
|  single-slot-definition
|    ::= (slot slot-name [default-attribute])
|
|  default-attribute
|    ::= (default ?NONE | expression) |
|        (default-dynamic expression)

It is a subset of CLIPS' deftemplate syntax. There are no multislots and no constraint-attributes for slots (types, ranges and such). But, apart from that, it is more or less the same[2]. And here's how it works:

|; SLIME 2007-03-14
|;;;; Compile file / [...] /mps. ...
|CL-USER> (in-package :mps)
|#[Package "MPS"]
|MPS> (deftemplate foo
|       (slot a-slot)
|       (slot a-default-slot (default 1))
|       (slot required-slot (default ?NONE)))
|FOO
|MPS> (foo)
|
|The slot: REQUIRED-SLOT in deftemplate: FOO requires an explicit value.
|   [Condition of type SIMPLE-ERROR]
|
|Restarts:
| 0: [ABORT] Return to SLIME's top level.
| 1: [ABORT-BREAK] Reset this process
| 2: [ABORT] Kill this process
|
|Invoking restart: Return to SLIME's top level.
|; Evaluation aborted
|MPS> (foo (required-slot 1))
|#S(DEFTEMPLATE/FOO :A-SLOT NIL :A-DEFAULT-SLOT 1 :REQUIRED-SLOT 1)
|MPS> (deftemplate bar
|       (slot default-gensym (default (gensym)))
|       (slot dynamic-gensym (default-dynamic (gensym))))
|BAR
|MPS> (bar)
|#S(DEFTEMPLATE/BAR :DEFAULT-GENSYM #:G31 :DYNAMIC-GENSYM #:G40)
|MPS> (bar)
|#S(DEFTEMPLATE/BAR :DEFAULT-GENSYM #:G31 :DYNAMIC-GENSYM #:G41)
|MPS>

The macro expands into a defstruct (deftemplate/foo) and another defmacro (foo) that is used as a constructor for the template. The reason it is a macro and not a regular function is because a function's arguments are evaluated whilst a macro's is not. And since there's no function named a-slot or a-default-slot etc. So we'd be thrown into the debugger if we tried to evaluate something like (foo (a-slot 1)).

Here's the macroexpansion of a simple template:

|MPS> (pprint (macroexpand-1 '(deftemplate foo
|                               (slot a)
|                               (slot b (default 1)))))
|
|(PROGN (DEFSTRUCT DEFTEMPLATE/FOO "" (A NIL) (B 1))
|       (DEFMACRO FOO (&REST SLOTS)
|         ""
|         (CALL-DEFSTRUCT-CONSTRUCTOR 'DEFTEMPLATE/FOO SLOTS)))
|; No value
|MPS>

Most of the code is spent checking that the template follows the syntax described in the BNF. The expansion itself is rather simple, almost trivial (it is the last progn below).

|(defmacro deftemplate (deftemplate-name &body body)
|  "
|  The deftemplate construct is used to create a template which can then
|  be used by non-ordered facts to access fields of the fact by name.
|
|  Examples:
|  (deftemplate object
|    (slot id (default-dynamic (gensym)))
|    (slot name (default ?NONE))           ; Makes name a required field
|    (slot age))
|  "
|
|  (macrolet ((signal-deftemplate-error (msg &rest args)
|               `(error (concatenate 'string "~&The deftemplate ~A contains at least one invalid slot-definition: ~S." ,msg)
|                       ,@args)))
|    (let ((comment "")
|          (defstruct-name (intern (concatenate 'string "DEFTEMPLATE/" (string deftemplate-name))))
|          (defstruct-slots '()))
|
|      ;; Extract the documentation string
|      (when (stringp (car body))
|        (setf comment (car body))
|        (setf body (cdr body)))
|
|      ;; Check syntax and extract slot-specifiers
|      (dolist (slot body)
|        (let* ((slot-name (cadr slot))
|               (curr-defstruct-slot `(,slot-name nil)))
|          (unless (eq (car slot) 'slot)
|            (signal-deftemplate-error "~&Expected SLOT instead of ~A."
|                                      deftemplate-name slot (car slot)))
|
|          (when (> (length slot) 2)
|            (dolist (default-attribute (cddr slot))
|              (unless (consp default-attribute)
|                (signal-deftemplate-error "~&Expected (default ?NONE|expression) or (default-dynamic expression) instead of ~A."
|                                          deftemplate-name slot default-attribute))
|              (unless (or (eq (car default-attribute) 'default)
|                          (eq (car default-attribute) 'default-dynamic))
|                (signal-deftemplate-error "~&Expected DEFAULT or DEFAULT-DYNAMIC instead of: ~A."
|                                          deftemplate-name slot (car default-attribute)))
|              (if (eq (car default-attribute) 'default)
|                  (if (eq (cadr default-attribute) '?NONE)
|                      (setf curr-defstruct-slot `(,slot-name (required ',slot-name ',deftemplate-name)))
|                      (setf curr-defstruct-slot `(,slot-name ',(eval (cadr default-attribute)))))
|                  (setf curr-defstruct-slot `(,slot-name ,(cadr default-attribute))))))
|
|          (setf defstruct-slots (append defstruct-slots (list curr-defstruct-slot)))))
|
|      `(progn
|         (defstruct ,defstruct-name
|           ,comment
|           ,@defstruct-slots)
|
|         (defmacro ,deftemplate-name (&rest slots)
|           ,comment
|           (call-defstruct-constructor ',defstruct-name slots))))))

and here are the functions used as helpers:

|(defun required (slot-name deftemplate-name)
|  (error "~&The slot: ~A in deftemplate: ~A requires an explicit value." slot-name deftemplate-name))
|
|(defun as-keyword (sym)
|  (intern (string-upcase sym) :keyword))
|
|(defun call-defstruct-constructor (defstruct-name &rest slots)
|  (let ((constructor (intern (concatenate 'string "MAKE-" (string defstruct-name)))))
|    (apply constructor (mapcan #'(lambda (slot)
|                                   `(,(as-keyword (car slot)) ,(cadr slot)))
|                               (car slots)))))

I should probably try to write a macro to abstract away all those (intern (concatenate 'string ...)) calls but otherwise, that's about it for deftemplate. Next up is getting all of the defrule construct working (which feels like a much tougher task).

[1] I hate that I still haven't found a good way of sharing code using Blogger. Tips and pointers are very welcome!

[2] The default and default-dynamic attributes in CLIPS take a variable number of expressions (at least according to the BNF found in the CLIPS Basic Programming Guide, Appendix H). I assume it assigns the value of the last as the default but I haven't tried. Anyway, if you want to evaluate several expressions in that place you're going to have to wrap it explicitly in a progn (effectively making it one expression).

MoGo beats Myungwan Kim (8P) at US Go Congress

From the AGA newsletter (via the ComputerGo mailing list):

COMPUTER BEATS PRO AT U.S. GO CONGRESS:
In a historic achievement, the MoGo computer program defeated Myungwan Kim 8P (l) Thursday afternoon by 1.5 points in a 9-stone game billed as “Humanity’s Last Stand?” “It played really well,” said Kim, who estimated MoGo’s current strength at “two or maybe three dan,” though he noted that the program – which used 800 processors, at 4.7 Ghz, 15 Teraflops on a borrowed European supercomputer – “made some 5-dan moves,” like those in the lower right-hand corner, where Moyogo took advantage of a mistake by Kim to get an early lead. “I can’t tell you how amazing this is,” David Doshay -- the SlugGo programmer who suggested the match -- told the E-Journal after the game.

“I’m shocked at the result. I really didn’t expect the computer to win in a one-hour game.” Kim easily won two blitz games with 9 stones and 11 stones and minutes and lost one with 12 stones and 15 minutes by 3.5 points. The games were played live at the U.S. Go Congress, with over 500 watching online on KGS. “I think there’s no chance on nine stones,” Kim told the EJ after the game. “It would even be difficult with eight stones. MoGo played really well; after getting a lead, every time I played aggressively, it just played safely, even when it meant sacrificing some stones. It didn’t try to maximize the win and just played the most sure way to win. It’s like a machine.”

The game generated a lot of interest and discussion about the game’s tactics and
philosophical implications. “Congratulations on making history today,” game organizer Peter Drake told both Kim and Olivier Teytaud, one of MoGo’s programmers, who participated in a brief online chat after the game. At a rare loss for words in a brief interview with the EJ after the game, Doshay wondered “How much time do we have left? We’ve improved nine stones in just a year and I suspect the next nine will fall quickly now.”

- reported by Chris Garlock

Amazing! Though, the last quote (by David Doshay) should probably be taken with a grain of salt.

[Update 2008-08-09] Apparently, David was misquoted.

A Minimal Production System

I've been experimenting a bit with bits and pieces of a production system in Common Lisp for a few days now. It all started as a fun exercise in Common Lisp macrology (the idea was to convert CLIPS syntax into executable Common Lisp code) but since things have fallen into place so neatly. I thought maybe it would be worth implementing parts of CLIPS syntax and functionality. So now, the only question is: which parts to implement?

I'm not going to do anything about data types and built-in functions. I'll add support for ?variables but that's about it (no multifields and no globals) and as far as constructs go I'll manage with defrule and deftemplate (no implied/ordered facts). If it doesn't turn out to be too difficult I'll try to include connected constraints in defrule but I won't bother with slot constraints in deftemplates (types and such). I'm hoping to include all CEs but it depends on how hairy it gets.

So. What have I missed? Is there something unnecessary on the list?

[Update 2008-08-03]: Hm. I guess I forgot about a bunch of engine commands. So here goes. Assert and retract seem stupid to leave out, as does run. I'll probably be annoyed not to have facts so I guess that's in as well. Load, clear, reset and agenda feel necessary but I think I'll only work with one conflict resolution strategy (depth) though.

Human-Computer 19x19 Go Showdown

From the Computer-Go mailing list:

On Thursday, August 7, at 1:00 PM (Pacific time), Kim MyungWan 8p will take on MoGo, the world’s strongest computer Go program. MoGo will connect remotely from France, where it will be running on a supercomputer boasting over 3,000 processor cores. The game will be broadcast on KGS.

Sweet! I guess I'll get an answer to some questions quite a bit sooner than I expected.

AI -TV from 1984

José of Programming Musings found a video with Daniel Bobrow explaining CLOS from 1987. Being somewhat of a history-geek, I really love this type of thing and I've managed to collect a few interesting links myself.

One that I can particularly recommend is Computer Chronicles: Artifical Intelligence (1984) which is a twenty minute TV show featuring, among others, John McCarthy and discusses AI in general, Expert Systems and Lisp.

Sling Blade Runner IV

I've been doing some more work on my kōan, Sling Blade Runner. I've given up on the beam-stack search approach. I doubt it will improve results much. If any at all.

Instead I have spent some time on improving the extend method so that it can find more extensions. And it is becoming quite efficient in exploring the neighbourhood of any given pair of titles. Previously it was only looking for extensions between two adjacent titles in the chain but now it searches for extensions between end-points in a whole sequence of titles instead. Consider the chain [A,B,C,D,...]. Now, if there's an extension between A and C, other than, and that is longer than [B], the chain is extended with it.

This, simple, tweak makes the search slower (of course) but it also improves the lengths of almost all chains that are explored. It rarely ends up with a chain that is shorter than 235 titles and most end up longer than 250 (246 was the previous best) titles.

The longest chain found is now 265 titles:

1 THE GOSPEL
2 THE GOSPEL OF JOHN
3 JOHN Q
4 Q AND A
5 A RIVER RUNS THROUGH IT
6 IT HAPPENED AT THE WORLDS FAIR
7 FAIR GAME
8 GAME OF DEATH
9 DEATH BECOMES HER
10 HER MAJESTY MRS BROWN
11 BROWN SUGAR
12 SUGAR AND SPICE
13 SPICE WORLD
14 WORLD TRADE CENTER
15 CENTER STAGE
16 STAGE FRIGHT
17 FRIGHT NIGHT
18 NIGHT OF THE LIVING DEAD
19 DEAD BANG
20 BANG BANG YOURE DEAD
21 DEAD MAN WALKING
22 WALKING AND TALKING
23 TALKING ABOUT SEX
24 SEX AND THE OTHER MAN
25 MAN OF THE HOUSE
26 HOUSE OF DRACULA
27 DRACULA DEAD AND LOVING IT
28 IT HAPPENED ONE NIGHT
29 ONE NIGHT STAND
30 STAND IN
31 IN GODS HANDS
32 HANDS ON A HARD BODY
33 BODY AND SOUL
34 SOUL FOOD
35 FOOD OF LOVE
36 LOVE IS THE DEVIL
37 THE DEVIL RIDES OUT
38 OUT COLD
39 COLD FEVER
40 FEVER PITCH
41 PITCH BLACK
42 BLACK LIKE ME
43 ME WITHOUT YOU
44 YOU LIGHT UP MY LIFE
45 MY LIFE SO FAR
46 FAR FROM HOME THE ADVENTURES OF YELLOW DOG
47 DOG RUN
48 RUN SILENT RUN DEEP
49 DEEP BLUE
50 DEEP BLUE SEA
51 SEA OF LOVE
52 LOVE WALKED IN
53 IN OLD CALIFORNIA
54 CALIFORNIA SPLIT
55 SPLIT SECOND
56 SECOND BEST
57 BEST MEN
58 MEN WITH GUNS
59 GUNS OF THE MAGNIFICENT SEVEN
60 THE MAGNIFICENT SEVEN
61 SEVEN YEARS IN TIBET
62 TIBET CRY OF THE SNOW LION
63 LION OF THE DESERT
64 DESERT HEARTS
65 HEARTS OF DARKNESS A FILMMAKERS APOCALYPSE
66 APOCALYPSE NOW
67 NOW YOU SEE HIM NOW YOU DONT
68 DONT BOTHER TO KNOCK
69 KNOCK OFF
70 OFF THE BLACK
71 THE BLACK ANGEL
72 ANGEL EYES
73 EYES OF AN ANGEL
74 ANGEL BABY
75 BABY SECRET OF THE LOST LEGEND
76 LEGEND OF THE LOST
77 THE LOST BOYS
78 BOYS LIFE
79 LIFE OR SOMETHING LIKE IT
80 IT TAKES TWO
81 TWO MEN WENT TO WAR
82 WAR OF THE WORLDS
83 THE WORLDS FASTEST INDIAN
84 INDIAN SUMMER
85 SUMMER CATCH
86 CATCH ME IF YOU CAN
87 YOU CAN COUNT ON ME
88 ME MYSELF I
89 I WANT TO LIVE
90 LIVE FOREVER
91 FOREVER YOUNG
92 YOUNG SHERLOCK HOLMES
93 SHERLOCK HOLMES IN WASHINGTON
94 WASHINGTON SQUARE
95 SQUARE DANCE
96 DANCE WITH A STRANGER
97 STRANGER IN THE HOUSE
98 THE HOUSE OF THE DEAD
99 DEAD OF NIGHT
100 NIGHT AND THE CITY
101 THE CITY
102 CITY OF ANGELS
103 ANGELS WITH DIRTY FACES
104 FACES OF DEATH
105 DEATH WISH
106 WISH UPON A STAR
107 A STAR IS BORN
108 BORN TO BE WILD
109 WILD THINGS
110 THINGS TO COME
111 COME AND GET IT
112 IT RUNS IN THE FAMILY
113 THE FAMILY MAN
114 MAN ON FIRE
115 FIRE ON THE MOUNTAIN
116 THE MOUNTAIN MEN
117 MEN IN BLACK
118 BLACK HAWK DOWN
119 DOWN WITH LOVE
120 LOVE AND DEATH
121 DEATH WISH V THE FACE OF DEATH
122 DEATH SHIP
123 SHIP OF FOOLS
124 FOOLS RUSH IN
125 IN THE WINTER DARK
126 DARK STAR
127 STAR TREK IV THE VOYAGE HOME
128 HOME ALONE
129 ALONE IN THE DARK
130 DARK BLUE
131 BLUE CAR
132 CAR 54 WHERE ARE YOU
133 YOU CANT TAKE IT WITH YOU
134 YOU ONLY LIVE ONCE
135 ONCE IN THE LIFE
136 LIFE AS A HOUSE
137 HOUSE PARTY
138 HOUSE PARTY 3
139 3 NINJAS
140 3 NINJAS KNUCKLE UP
141 UP CLOSE AND PERSONAL
142 PERSONAL BEST
143 BEST OF THE BEST
144 BEST OF THE BEST 3 NO TURNING BACK
145 NO TURNING BACK
146 BACK TO SCHOOL
147 SCHOOL OF ROCK
148 ROCK STAR
149 STAR TREK THE MOTION PICTURE
150 PICTURE BRIDE
151 BRIDE OF THE MONSTER
152 MONSTER HOUSE
153 HOUSE OF FRANKENSTEIN
154 FRANKENSTEIN AND THE MONSTER FROM HELL
155 FROM HELL
156 HELL UP IN HARLEM
157 HARLEM RIVER DRIVE
158 DRIVE ME CRAZY
159 CRAZY AS HELL
160 HELL NIGHT
161 NIGHT FALLS ON MANHATTAN
162 MANHATTAN MURDER MYSTERY
163 MYSTERY ALASKA
164 ALASKA SPIRIT OF THE WILD
165 THE WILD
166 THE WILD ONE
167 ONE NIGHT WITH THE KING
168 THE KING AND I
169 I SPY
170 SPY HARD
171 HARD EIGHT
172 EIGHT MEN OUT
173 OUT OF THE BLUE
174 BLUE SKY
175 SKY HIGH
176 HIGH CRIMES
177 CRIMES OF PASSION
178 PASSION IN THE DESERT
179 DESERT BLUE
180 BLUE STEEL
181 STEEL DAWN
182 DAWN OF THE DEAD
183 THE DEAD
184 DEAD MAN ON CAMPUS
185 CAMPUS MAN
186 MAN TROUBLE
187 TROUBLE EVERY DAY
188 DAY OF THE WOMAN
189 THE WOMAN IN RED
190 RED EYE
191 EYE FOR AN EYE
192 EYE OF GOD
193 GOD TOLD ME TO
194 TO DIE FOR
195 FOR THE BOYS
196 THE BOYS
197 BOYS AND GIRLS
198 GIRLS WILL BE GIRLS
199 GIRLS GIRLS GIRLS
200 GIRLS OF SUMMER
201 SUMMER LOVERS
202 LOVERS AND OTHER STRANGERS
203 STRANGERS WHEN WE MEET
204 MEET JOE BLACK
205 BLACK AND WHITE
206 WHITE HUNTER BLACK HEART
207 HEART CONDITION
208 CONDITION RED
209 RED RIVER
210 RIVER OF NO RETURN
211 RETURN OF THE FLY
212 FLY AWAY HOME
213 HOME ALONE 2 LOST IN NEW YORK
214 NEW YORK NEW YORK
215 NEW YORK COP
216 COP LAND
217 LAND OF THE DEAD
218 DEAD END
219 END OF DAYS
220 DAYS OF HEAVEN
221 HEAVEN CAN WAIT
222 WAIT UNTIL DARK
223 DARK CITY
224 CITY OF JOY
225 JOY RIDE
226 RIDE THE HIGH COUNTRY
227 COUNTRY LIFE
228 LIFE WITH FATHER
229 FATHER OF THE BRIDE
230 BRIDE OF THE WIND
231 THE WIND AND THE LION
232 THE LION KING
233 KING OF THE JUNGLE
234 THE JUNGLE BOOK
235 JUNGLE BOOK
236 BOOK OF LOVE
237 LOVE LIFE
238 LIFE IS BEAUTIFUL
239 BEAUTIFUL PEOPLE
240 PEOPLE I KNOW
241 I KNOW WHERE IM GOING
242 IM GOING HOME
243 HOME ALONE 3
244 3 NINJAS KICK BACK
245 BACK TO THE BEACH
246 BEACH PARTY
247 PARTY MONSTER
248 MONSTER IN A BOX
249 BOX OF MOON LIGHT
250 LIGHT OF DAY
251 DAY FOR NIGHT
252 NIGHT MOTHER
253 MOTHER NIGHT
254 NIGHT ON EARTH
255 EARTH GIRLS ARE EASY
256 EASY MONEY
257 MONEY FOR NOTHING
258 NOTHING BUT TROUBLE
259 TROUBLE IN PARADISE
260 PARADISE ROAD
261 ROAD HOUSE
262 HOUSE PARTY 2
263 2 DAYS IN THE VALLEY
264 VALLEY GIRL
265 GIRL WITH A PEARL EARRING

The results vary a bit depending on search depth (not that surprising really) so there may still be some possible improvements by just modifying parameters.

[Update 2008-07-20] The longest chain found is now 268 titles long.

Using printout and readline in PyCLIPS applications

I am trying to help a CLIPS user compile his application into a Windows executable (.exe) by following the description in one of my previous blog posts. But his application relies on the built in functions read and printout. And my blog post says nothing about that type of situation since all of the times I've done this before have been with applications that have GUIs and I've never had to bother with command line interaction.

The problem is, more specifically, that PyCLIPS consumes all calls to printout and read without printing to screen or requiring any user input. This may seem like a stupid design decision at first, but if you consider the many situations and environments that PyCLIPS can run in. It starts to feel like a rather sensible approach since it's obviously impossible to know what the right thing to do is. If you need user interaction via command line, you can provide Python functions that perform I/O for you.

So. Just to be clear. PyCLIPS does not constrain the possibilities for interaction with CLIPS in any way. It just doesn't make any assumptions about how it should best be done.

Ok. Fair enough. But, what to do?

First off. I don't want to have to maintain different versions of the application just to perform I/O. I need a way to dynamically dispatch I/O to either the built in functions (if it's run in CLIPS Dialog) or to my Python functions (if it's run in PyCLIPS).

Here is a simple application that uses printout and read:

|(deffacts start
|  (sum 0))
|
|(defrule calc-sum
|  ?sum <- (sum ?s)
|  =>
|  (retract ?sum)
|  (printout t "Enter a number or Q to quit: ")
|  (bind ?input (read))
|  (if (numberp ?input)
|   then (bind ?s (+ ?s ?input))
|        (assert (sum ?s))
|   else (if (or (eq ?input q)
|                (eq ?input Q))
|         then (printout t "Sum = " ?s crlf)
|         else (printout t "Invalid input: " ?input crlf)
|              (assert (sum ?s)))))

It works like this:

CLIPS> (load "sum.clp")
!!!$*
TRUE
CLIPS> (reset)
CLIPS> (run)
Enter a number or Q to quit: one
Invalid input: one
Enter a number or Q to quit: 9
Enter a number or Q to quit: 8
Enter a number or Q to quit: 5
Enter a number or Q to quit: Q
Sum = 22

When I first thought about how to make this program run (with as little effort as possible) in PyCLIPS, I didn't think that it would be very difficult. I was actually quite certain I'd be able to monkey-patch PyCLIPS with my I/O functions. CLIPS, however, was far from impressed with my attempt. So, a slap on the wrist later, I settled on (manually) replacing all function calls to printout, readline and read to deffunction wrappers (printout1, readline1 and read1) instead.

Here are the CLIPS deffunctions:

|(deffunction printout1 (?logical-name $?args)
|  (if (member$ python-call (get-function-list))
|   then (funcall python-call pyprintout ?logical-name $?args)
|   else (progn$ (?arg $?args)
|          (printout ?logical-name ?arg))))
|
|(deffunction readline1 ($?logical-name)
|  (if (> (length$ $?logical-name) 0)
|   then (bind ?logical-name (first$ $?logical-name))
|   else (bind ?logical-name t))
|
|  (if (member$ python-call (get-function-list))
|   then (funcall python-call pyreadline ?logical-name)
|   else (readline ?logical-name)))
|
|(deffunction read1 ($?logical-name)
|  (if (> (length$ $?logical-name) 0)
|   then (bind ?logical-name (first$ $?logical-name))
|   else (bind ?logical-name t))
|
|  (if (member$ python-call (get-function-list))
|   then (eval (funcall python-call pyread ?logical-name))
|   else (read ?logical-name)))

They look quite hairy. I know. But they're generic so it's not something you'd have to write and modify for each application that you want to be able to run in both CLIPS and PyCLIPS. There's also some Python boiler plate. It looks like this:

|import clips
|
|def pyprintout(*args):
|  for arg in args[1]:
|    if arg.cltypename().upper() == "SYMBOL":
|      if arg.upper() == "CRLF":
|        print
|      elif arg.upper() == "TAB":
|        print "\t",
|      else:
|        print arg,
|
|    else:
|      print arg,
|
|def pyreadline(*args):
|  return raw_input()
|
|def pyread(*args):
|  return raw_input()
|
|clips.RegisterPythonFunction(pyprintout)
|clips.RegisterPythonFunction(pyreadline)
|clips.RegisterPythonFunction(pyread)

Once we've got all of the above in place. We can load, reset and run from within a PyCLIPS script and have the application work directly in the Windows command line.

C:\...>python sum.py
Enter a number or Q to quit:  one
Invalid input:  one
Enter a number or Q to quit:  9
Enter a number or Q to quit:  8
Enter a number or Q to quit:  5
Enter a number or Q to quit:  Q
Sum =  22

C:\...>

The files sum.py and sum.clp contain the whole application if you're interested. The point of all this is of course to be able to compile the PyCLIPS application into an executable. Step for step instructions on how to do that can be found here.

[Update 2008-07-14] I just fixed the pyprintout function (in sum.py), so that it also prints symbols. The code I added is marked with red.

What would *you* do with a thousand cores?

Anwar Ghuloum's post Unwelcome advice has caused a bit of a stir recently. Probably not in the way he wanted though. The comments are full of questions and doubts about whether they (Intel) can back up their claims of soon-to-come-thousands-of-cores-processors. And, more importantly, if they *can* - programming in itself will be very different from how we do it today so it's meaningless to think about it in terms of how it's done now.

But, regardless of all that... More than a thousand cores in a single processor. What would *you* do with that? One area that I think looks particularly promising is Computer Go. That many cores may well be the tipping point of AI players in Go. Will they finally be able to move up into the (professional) Dan levels?

In the upcoming tournament at the European Go Congress (in Leksand, Sweden) they're provding hardware with 2 cores. If we ignore practical scaling problems for a minute, what would the effect of an additional 998 cores be? Many of the top players today (like MoGo and CrazyStone) rely on "easily" parallellizable statistical methods (see UCT and Monte Carlo methods for more info). And the more playouts you can perform within a given time the better the resulting play. At least in theory.

I may well be underestimating the problem. I know. But it would be very interesting to see how much of an improvement can be made by just adding more raw power.