Common Lisp Blog

I found a most amusing link on hackernews. It teaches something about modern Software architecture: http://chaosinmotion.com/blog/?p=622

It really took me a while to tweak and bend this thing into the right direction. It is conceptual the core of any 2-person game and this is the reason why it is worth this work. but what am i trying to accomplish here? My Idea is to create a constuction kit for search strategies. The negamax-procedure itself is only the algorithm how the scores are propagated up the tree. The variables of it are the function successors, that computes the legal successors of any node, terminal that decides if we will use the same negamax in the next level and next-nmx, that can be the next evaluator or -if we are at leaf - the heurstic function.

My goal is to be able to give the lisp compiler declarations like this one:

(defparameter *mate-in-2-solver*
  (mk-ngmx 2 #'false #'legal-successors-check-moves-first
           (mk-ngmx 1 #'false #'check-moves #'score-if-checkmate)))

This definition describes a proper search strategy for a mate-in-2-problem. We will fully expand the game tree on the first two levels and on the third level we will only expand nodes that provide check. At last we will score only checkmates (#'score-if-checkmate). The resulting *mate-in-2-solver* will then be a closure that represents this search strategy.

To achieve this, i had to define the negamax-procedure itself within a labels binding. flet or lambda do not work here, since nmx is recursive and i did not want to mess around with Haskell Curry's Y-Combinator here :-) . After that we have to currify the variable depth away with a lambda on the last line.

(defun mk-ngmx%% (maxdepth terminal successors  next-nmx)
  (labels ((nmx (depth node alpha beta)
             (when (or (<=depth 0) (funcall terminal node))
               (return-from nmx (funcall next-nmx node alpha beta)))
             (dolist (node (funcall successors node))
               (setq alpha (max alpha (- (nmx (1- depth) (force node) (- beta) (- alpha)))))
               (when (>= alpha beta)
                 (return-from nmx alpha)))
             alpha))
    (lambda (node alpha beta) (funcall #'nmx maxdepth node alpha beta))))

There were numbers of questions that i had to check at first. For example, i had to prove that the return-from form will work with a name bound by labels. But it turned out that this was no problem.

At this time I am not shure if the hole thing will work this way until I really get results from a test run.

(defun mk-ngmx (terminal heuristic successors next-nmx)
  (lambda (node alpha beta)
    (if (funcall terminal node)
        (funcall heuristic node)
        (do ((node-list (funcall successors node) (tail node-list)))
            ((null node-list) alpha)
          (setq alpha (max alpha 
          (- (funcall next-nmx (car node-list) (- beta) (- alpha)))))
          (when (>= alpha beta)
            alpha)
         alpha))))

The form above shall be the negamax-closure in its final form. Because of alpha-beta pruning we will have to work with lazy evaluation here to prevent this abstract algorithm from doing to much work. The "lazy-cdr",that is called tail here will performs the do-move function, that is takes a node and a move and returns the resultuing node.

Lazy evaluation is also necessary, because we will have to expand the search depth step by step to achieve a serious pre-sorting. Lazy evaluation will save us some expansions in this scenario. Proper pre-sorting is necessary to take maximum advantage of the alpha-beta-pruning.

mk-ngmx will close over four functions, that together define the search strategy: terminal, that checks if we stop searching, heuristic, that evaluates leaves and successors, that calulates the lazy list of successor-nodes.

Now I will have to bring this contruction to work..

I just made a simple experiment with movelist sortiing. I just sorted the moveslist by the following ugly and inperformant procedure:

(defun sort-ml-solve (node ml color)
;; this handler sorts the ml in a way that the check giving moves
;; appear first.
  (let ((cmoves
         (loop for m in ml
            when (check? (do-move node m) (- color))
              collect m)))
    (append cmoves (remove-if #'(lambda (m) (member m cmoves)) ml))))

This gave me speedup of factor > 11, since the count of nodes that had to be expanded went down from 35000 to 178 for a mate-in-3-problem. I simply was right to start a chess project in common lisp, because no other language lets me do that kind of experiment with that little effort (5 min)! I hope I will learn more and more to write programs in a way, that make such tasks easy to me. If you read my other postings you will know that i only started a chess program in lisp to learn to program in common lisp. My next task will be some kind of factorisation of this software, that i can try out concepts even more easily. I will have to discover the "lispy way". :-)

The actual code and documentation can be found here.

The program is growing and so does the count of building sites in it. I had to insert code to manage the pawn double steps, that i simply forgot at my first shot.

I am doing some investigations on code optimizations. Found an article about compiler optimzations in actual lisp compilers. Since i am mostily working with integers, arrays of integers and lists of integers, i will have to work out, how to tell the sbcl compiler to make use of type information.

But this is not my main issue. I want to get use of possibilities that only lisp offers. In earlier experiments with chess programming I discovered the problem that it is not trivial to build a flexible and convenient way that lets me tell my program, which kind of sorting, move selection and expansion to use at which level. I want this in a way that allows me to compare easily the performance of different strategies. My Idea is now, to generate a chain of negamax-closures by some generator function. Each part of the chain describes the search strategy on the first, second, etc level of the minimax -search. There are four "variables" - encoded in functions - in the negamax-procedure. These are

• the move generator
• the move list sorter
• the procedure that decides if we will search deeper
• the minimax-closure that will search the next level

It should be possible to build a "kit" consisting of intsances of the above procedures and the negamax-procedure itself, that will allow me to easily throw different search engines together this way.

After a debugging session I managed to fix some errors (One with signs an another one with my move generator). Now I've reached a first milestone since the program solved some mate-in-2-problems correctly. I'am glad now, that all the pieces fall into place correctly. After

(solve 2 white)

I am getting the right answer now to the mate-in-2-problem, that is hard-coded into the lisp-file! **RIESIG BREITES GRINSEN ^_^ **

My actual Lisp project is a chess programm. This is just for fun and it's far from ready yet, but I will publish the current state here form time to time. At this time I am trying to to fix some problems with pawn promotions.

You may always take for granted, that the Lisp-guy, who is trying to convice you that Lisp is the right language you, already knows about your prefered language. You can even be sure that he is did much coding in it already. The simple reason is, that only few of them are so lucki to do their bread and butter programming in common lisp. On the other hand, you can take for granted, that the oo-guy, who can not be convinced by lisp-guy never did anything relevant in lisp and its alikes. I suppose that lispers actively know more programming languages than the masses of programmers that are devoted to java,c++ etc.

The simple reason is that only persons who have a feeling, that things could be better will try alternatives to the tools of the masses. This is why you should really listen carefully to what lipers have to say. They most probably know your language und you could most probabley could benefit from their experience. And there will be a good reason, why they stuck with using lisp.

Why do I start this blog? What is my connection to Lisp?

I have tried many different blogging systems. None of them was of the kind I really like. The most drawbacks came from the editors that do not match my needs as an emacs user. And even worse, none of the blogging systems do really support the work with source code. I am not sure how to support RSS-Feeds yet, but I there will be a way - most probably by some Perl hacking. Org-Mode itself has some support for rss but only in the false direction.

This "blogging system" consists just of emacs with org-mode. It supports all the features I need and I hope to be able to adapt or extend it if needed with some further bells and whistles. I will blog in (my relatively poor) English, because i suspect my (not so poor german) would reach far less people. Are there more than 100 germans out there, that are interested in Lisp? I dont know. But I am sure I would not be able to attract more than 10 readers if I did this in german. Luckily the Language Lisp itself is international. And propably more than that. I consider it athough not heavily used to be the single most influencial innovation in practical computing. But I will not start wining here as many Lispers do, that Lisp is not more commonly used in praxi. Sooner or later more and more People will join the Lisp community since there is no real alternative to it.

Lisp is a result of some theoretical conceptions of John McCarthy in the fall of the 50's. As far as I know, he was not interested in the design of a programming language directly, but he made research to get a substitute for the turing machine based on the lambda calculus. Lisp itself was the rusult of some hacking of one of his assistents, who had the idea to convert the simple rules of evaluation into software

Lisp was the second or third programming language I learned. It was in the late 80's. Although I could not effort any system able to drive a lisp interpreter, it took me only 2 or three pages of a computer journal, to feel that there is something very special about this approach of computer interaction.

What I catched then was only the rest of what was left of activity in artificial intelligence: An epoche started, that later on was called the "AI winter". From my point of view the invention of graphical user interfaces and the ubiquitous use of personal computers lead to a situation in which the place for things like artificial intelligence was lost. From there on, the targets of computer usage changed in a way that made computers more usable but less intelectual. Needless to say, that I also lost contact and practice in Lisp. I did my work mostly in C++ and Perl.

Now in the 2010s some other view of computing arises. Programmers, earlier addicted to C++,Java etc learn about closures, functional programming and probably lisp macros, that were invented in the 50s and 60s by lispers. We all together seem to become adult programmers now.

Patrick Krusenotto, Rheinbach, Germany

Drop me a mail if you like:

(defparameter *email* 
  (concatenate 'string "patrick.krusenotto" 
               (string (code-char 64)) 
               "googlemail.com"))