Archive for the ‘Architecture’ category

Capyblanca is now GPL’d

July 9, 2008

In 1995, Douglas Hofstadter wrote:

“A visit to our Computer Science Department by Dave Slate, one of the programmers of Chess 4.6, at that time one of the world’s top chess programs, helped to confirm some of these fledgling intuitions of mine. In his colloquium, Slate described the strict full width, depth-first search strategy employed by his enormously successful program, but after doing so, confided that his true feelings were totally against this type of brute-force approach. His description of how his ideal chess program would work resonated with my feelings about how an ideal sequence-perception program should work. It involved lots of small but intense depth-first forays, but with a far greater flexibility than he knew how to implement. Each little episode would tend to be focused on some specific region of the board (although of course implications would flow all over the board), and lots of knowledge of specific local configurations would be brought to bear for those brief periods.”

That was, of course, many years before I would meet Doug.

How do chess players make decisions? How do they avoid the combinatorial explosion? How do we go from rooks and knights to abstract thought? What is abstract thought like? These are some of the questions involving the Capyblanca project. The name, of course, is a blend between José Raoul Capablanca, and Hofstadter’s original Copycat Project implemented by Melanie Mitchell, which brought us so many ideas. Well, after almost 5 years, we have a proof-of-concept in the form of a running program, and we are GPL’ing the code, so interested readers might take it to new directions which we cannot foresee. Some instructions are in the paper, and feel free to contact me as you wish.

The manuscript is under review in a journal, and a copy of the working paper follows below. Interested readers might also want to take a look at some of my previous publications in AI and Cognitive Science:

(i) Linhares, A. & P. Brum (2007), “Understanding our understanding of strategic scenarios: what role do chunks play?”, Cognitive Science, 31, pp. 989-1007.

(ii) Linhares, A. (2005), “An active symbols theory of chess intuition”, Minds and machines, 15, pp. 131-181.

(iii) Linhares, A. (2000), “A glimpse at the metaphysics of Bongard Problems”, Artificial Intelligence, 121 (1-2), pp. 251-270.

Any feedback will be highly appreciated!

–Alex

Capyblanca paper under reviewUpload a Document to Scribd
Read this document on Scribd: Capyblanca paper under review
Advertisements

Plot-Whither

April 24, 2008

This week, the Spirit moved me to dig through the boxes of books still unpacked from our move down here from Bloomington, and so I’ve been reading Fluid Concepts and Creative Analogies again — since I’ve just started, I’ve been thinking about Seek-Whence and its domain.

Naturally, my mind turned to the representation of the concepts involved. My last burst of creative energy with Copycopycat’s Slipnet and definitional language got bogged down when I started thinking more seriously about the conceptual structure of the Copycat domain, because the conceptual structure is, of course, the Hard Part. And while reading about Seek-Whence I realized that part of the reason it’s the Hard Part is that it’s not done yet — that is to say, when putting together Copycopycat, I’m trying to do two things at once. First, I’m trying to build a FARGitecture based on my notion of conceptual structure. But secondly, I’m trying to do so in a perceptual context.

Well, perception is hard. Maybe, I realized, it would be easier if I already had some of the mechanics of the whole conceptual structure thing done.

So. In writing about Seek-Whence, Doug (as is his wont) demonstrates a whole list of sequences which are part of the domain. And he mentions in passing (as is his wont) that representing the template for a sequence is kind of tricky.

Well, yeah. It’s tricky because it’s fundamental to cognition, this breaking down of the world into semantic units we can manipulate. Along the way, we use powerful perceptual and analogy-making tools, and those are cognition per se, but without that basic set of mechanisms, it’s all too big a chunk to bite off. Or so I posit.

This morning, though, I had an interesting notion: what if, instead of trying to do everything at once in the creation of a new conceptually-based FARGitectural variant, I were simply to try to come up with some semantic units which could be used to model — to think about — sequences in the Seek-Whence domain? Not to worry about how they get there (yet), just … build them by hand and try to do something with them.

But if that’s the task, the “do something with them” just leaps out, doesn’t it? Well, two somethings: the “easy” one — which is to take a semantic sequence structure and generate terms in the sequence using whatever arithmetic tools seem appropriate — and the “good” one. Which is to do variants on a theme.

The name of this project is equally obvious: Plot-Whither.

Now if I can only get the Muse interested …

Open sourcing a slipnet viewer!

April 19, 2008

(This page will be updated with further details as soon as soon as possible; I am setting up the repository asap)

Hello world!

After reading this fantastic book and playing with this, I think one good way to proceed is to open-source some parts of a FARG framework which are not at its core, but are extremely useful and everyone could benefit from them.

I’m thinking first about a slipnet viewer. A java class that receives a list of nodes and links, and creates a nice view of the ongoing slipnet at any point in time. A node might consist of its activation levels and a bitmap to display inside the node (sometimes we may want to display something other than a string), while a link might include just the nodes it connects, (perhaps) a direction, and a string (to show up distances and for those with IS-A beliefs). It is a good tool for debugging and for propaganda purposes.

The class would get this information and create another bitmap, now with a beautiful view of the current slipnet: close nodes appear close to each other, distant nodes appear distant, and their activity levels are displayed. From my past life in combinatorial optimization, I have a hunch that this is NP-hard, so we may be resorting to some heuristic that works.

It should be in java, to run in everybody’s machine, and also because everyone knows java and could either make a call to it from their own weirdo language or rewrite the code for their project.

In this initial stage, no windows or anything fancy should be done. Just get the data in and output a bitmap with the slipnet. But if our collaboration works, we could go bigger, triggering a window in a new thread and having a great display running in true parallel style. That would, I think, be a first step that everyone would benefit from.

This is small stuff, of course, but it’s annoying to redo it everyday in every single project. It takes some time to do, and distracts from the core issues. Our productivity will rise. So, as Micheal Roberts once said, instead of having “obsessive geniuses” working under the basement, we should finally stop doing the same things over and over again. We should finally start collaborating like a small research group.

Or as a start-up company.

That’s some distributed temperature right there, Dude!

March 31, 2008

I’ve been thinking about massively parallel FARG, distributed temperature, and distributed coderacks:

Now, whenever a codelet is about to change something up, why add it to the global, central, unique, coderack? I don’t see a good reason here, besides the “that’s what we’ve always done” one. If a codelet is about to change some structures in STM, why not have (i) a list (or a set, or a collection, etc.) of structures under question & (ii) create a list-subordinated coderack on the fly? Instead of throwing codelets into a central repository, they go directly to the places in which they were deemed necessary. There are multiple repositories for codelets, multiple coderacks.

I argued that I liked the idea because (i) it enables parallelism of the true variety, (ii) it helps us to solve the stale codelets issue, and (iii) programming can (in principle) be done gradually, still in simulated parallel.

Now, I was wrong about temperature all along. Here’s a new idea:

Imagine that each of the coderacks has the following behavior: Get a RANDOM codelet, then run it.

That’s massively parallel temperature right there. Have a nice day. Thanks for stopping by.

Unconvinced? Think about this: some coderacks will start to become really small (as Abhijit pointed out in the comments previously), with one or two codelets, then being emptied and destroyed. That means that at that particular point (or thing) in STM, temperature is really low. However, other coderacks will be full of stuff waiting to run; which means that there, temperature is running high.  Distributed temperature with high randomness in hot spots, low randomness in cool spots.

Maybe this has to be coupled with some information about concepts, but I’m not sure anymore. I think that it just might be one of those wonderful, marvelous, emergent effects we take so much pleasure in playing with.

On massively parallel coderacks

March 11, 2008

Here’s a question: how to make FARG massively parallel? I’ve written about parallel temperature, and here I’d like to ask readers to consider parallel coderacks.

Like temperature, the coderack is another global, central, structure. While it only models what would happen in a massively parallel minds, it does constrain us from a more natural, really parallel, model. Though I’m not coding this right now, I think my sketched solution might even help the stale codelet problem Abhijit mentions:

We need the ability to remove stale codelets. When a Codelet is added to the Coderack, it may refer to some structure in the workspace. While the codelet is awaiting its turn to run, this workspace structure may be destroyed. At the very least, we need code to recognize stale codelets to prevent them from running.

Consider that most codelets fit into one of three kinds: (i) they can propose something to be created/destroyed, (ii) they can evaluate the quality of such change, and (iii) they can actually carry it out.

Now, whenever a codelet is about to change something up, why add it to the global, central, unique, coderack? I don’t see a good reason here, besides the “that’s what we’ve always done” one. If a codelet is about to change some structures in STM, why not have (i) a list (or a set, or a collection, etc.) of structures under question & (ii) create a list-subordinated coderack on the fly? Instead of throwing codelets into a central repository, they go directly to the places in which they were deemed necessary. There are multiple repositories for codelets.

Why do I like this idea? First, because it enables parallelism of the true variety. Each of these STM-structure-lists-bound coderacks can be running in their own thread. If some crazy codelet wants to change some set of structures, it needs to find the proper coderack, or to create it during a run. This means codelets cannot interfere with STM structures to which they haven’t been assigned access; & the STM-structure-list-coderack will assure that only one codelet goes at a time.

Moreover, it helps us to solve the stale codelets issue, by simply destroying the coderack when something needed inside the lists is gone. If a structure is destroyed, and a codelet was waiting to work on it, the codelet–in fact all the coderacks associated with the structure–can go back to cyberspace heaven.

How about programming this thing? It doesn’t even have to be too hard. It can be done gradually, as all the coderacks can be running in simulated parallel and fully tested before venturing into the dangerous waters in which the threads lead us.

(I don’t know when I’ll be able to try this idea out, but hopefully, one day soon.)

Does that make any sense?

My 2008 Agenda

March 4, 2008

Or, more likely, my upcoming frustrations:

* Domain-neutral codelets

* Dynamic fluid (& domain-neutral) chunks (the only good idea I’ve ever had.  Explains everything in the known universe. More as story unfolds.)

* Distributed Temperature

* Distributed (Parallel) Coderack(s)

* Self-forming codelets

* Slipnets without IS-A or different types of links

All implemented in Numbo & Copycat variations; perhaps even a port of my chess program or even more ambitious stuff.

But of course, as Christian says, language compiles everything.

This is going to end either with Champagne or Valium.

Damn!

An extensible FARG implementation, Part II

February 28, 2008

[Microsoft Word seems to be messing up my fonts. Apologies.]

The question I explore in this post is how much and what can be shared between CRCC projects. I will try to stay as concrete as I can. In this post, I have managed to talk about a single “simple” aspect.

One of the most obviously sharable aspects of FARGitecture is the codelet system. I am not referring to the types of codelets, but rather to the infrastructure for dealing with codelets. If a good, solid, and reusable framework had been available to me, it would indeed have saved time. My final implementation is only a couple of hundred lines of code, but the effort required and mistakes repeated make it quite costly. Needlessly costly.

What are the petty things needed of this infrastructure? Obviously, we need a simple interface to add codelets and select codelets. That much is obvious. What may become more apparent only by implementing a system and struggling to grapple with its complexity are other features and tools, like the following (and I have not counted these “optional” features in the 200 lines I mentioned):

  • We need the ability to remove stale codelets. When a Codelet is added to the Coderack, it may refer to some structure in the workspace. While the codelet is awaiting its turn to run, this workspace structure may be destroyed. At the very least, we need code to recognize stale codelets to prevent them from running.
  • Writing new codelets should be easy. Most codelets, when written in the programming language being used, share boilerplate code. Tools that allow us to write closer to the domain (and then compile our code down to the programming language) have proved very useful to me. They improve code readability, lower the barrier to experimenting with new codelets, even improve error messages. Just to illustrate, here is the code for one codelet type:

    CodeletFamily flipReln( $reln ! ) does {
    RUN: {
    my $new_reln = $reln->FlippedVersion() or return;
    $reln->uninsert;
    $new_reln->insert;
    }
    }

    Mind you, I am not claiming this to be hard or undoable by appropriately setting up classes so that the “compiler” is not required. It is not difficult, but it takes careful thought and time. I am just pointing out that something needs to be done to ease codelet writing.

  • Seqsee has the notion of scripts. Some tasks are by their very nature somewhat serial. Like makings tea. Or describing a solution. How would a FARGitecture do such tasks? Certainly not by using a single codelet. We do not need a “make tea from scratch” codelet, or a “write dissertation” codelet. Seqsee “solves” this (ha ha) by splitting the task into several codelets that call each other. Painful to write? Yes. Repetitive to code? Yes. Extend the programming language to reduce busy work? Yes. So here is Seqsee’s code for one task (which is a subtask of a bigger task, but we don’t have to care).

    CodeletFamily DescribeRelationCompound( $reln !, $ruleapp ! ) does scripted {
    STEP: {
    my $category = $reln->get_category();
    SCRIPT DescribeRelnCategory, { cat => $category };
    }
    STEP: {
    my $meto_mode = $reln->get_meto_mode();
    my $meto_reln = $reln->get_metonymy_reln();
    SCRIPT DescribeRelnMetoMode,
    {
    meto_mode => $meto_mode,
    meto_reln => $meto_reln,
    ruleapp => $ruleapp,
    };
    }
    }

    The SCRIPT calls launch other codelets, which may call more scripts, and return. All along, all the laws of codelets hold: they can be removed from the Coderack without being run, several “scripts” may run in parallel, and so forth. Again, being able to focus at the task on hand is a big win.

  • At any stage, several codelets are on the Coderack. Several avenues are being explored in parallel. In order to understand what’s going on, or even to demonstrate what’s happening, we can build tools. These are only related to the codelets, and can be completely domain independent. Here are some such visualizations from Seqsee.
    • Codelets launch other codelets. By logging what codelet added what other codelet when, we can obtain trees of codelet launching. Very useful for debugging. This image is from a tool that allows exploration of such trees, allows searching for specific types of codelets, and also lets us see how long codelets sit on the Coderack.

    • At any stage, there is pressure to do several things. Each codelet is a tiny bit of pressure. The log mentioned above also allows us to create graphs that display the change in pressure to do a particular thing over time.

      The image below shows the pressure to extend groups during a single run.

All tools mentioned here are domain independent. Just writing the system that manages the infra takes little time, but writing tools takes longer. And deciding what tools to build takes longer still, and yet, in the long run, they save time. Without these tools, I may not have been able to write Seqsee.

Imagine writing a FARGitecture to be like programming a task. Well, don’t imagine, it is programming a task. Except that we design it from scratch: we build our own virtual machine, write our own tools. It is high time we had a shareable toolset, at the very least.

I will end by pointing out that the images I have added above were generated from a log file. This file could have been dumped by a COBOL program, if somebody wanted to write a FARGitecture in that wonderful language. We don’t need to agree on a programming language to share tools.