Examples of Simple Problem Solving Using CCM

Introduction

CCM is a model for symbol processing by randomized method only using local information. A program using CCM consists of production rules (only one rule in typical cases such as below) and local evaluation functions. Both of them are computed only using local data (or only a few number of data). CCM is similar to Genetic Algorithms in some sense. Here are some example problems. These were originally written as Java applets, but are now implemented in JavaScript. I will explain the background of this change later.

This page and the pages linked from here contain explanation for experts. If you are not interested in the detail, try only the examples (links with smiley ()). (Note that the methods used here are not the standard methods for solving these problems.)

Examples Using Java

Constraint satisfaction problems (CSPs) are suited for CCM. Three (plus one) CSPs are shown for examples.

The N queens problem and sorting

Solutions of the N queens can be computed and N data can be sorted using the same rule but using different local evaluation functions. This page contains a program that solves these problems.

Coloring of maps and graph vertices

The USA mainland map is colored using four colors for example.

Magic Squares

Magic squares are found using CCM.

A computational language called SOOC, which is based on CCM, has been developed on the top of Lisp. As explained in the introduction, types of programs can be easily expressed as a combination of production rules and local evaluation functions. However, SOOC has not yet transplanted to Java. So, the above programs are ``hand-compiled'' into Java functions in the above programs.

Rewriting from Java to JavaScript

The above programs were originally written as Java applets, but around 2016 Java applets were discontinued and stopped functioning. At first, I tried to manually rewrite them in JavaScript, but it was not easy.

After it became possible to program with ChatGPT, I attempted to rewrite them in JavaScript with its help, but things did not go as smoothly as I had hoped. Even ChatGPT 4o told me that converting them would require several steps, so I left the task unfinished. However, as soon as I was able to use ChatGPT 5, I tried again, and it successfully converted them into fully functional JavaScript programs in one go. As a result, I was able to rewrite these programs and the corresponding web pages within a few hours.

Even so, I was still troubled by some of JavaScript's quirks. When I tried to display two JavaScript canvases on a single page, overlapping variable scopes caused them not to render correctly, and I had to get ChatGPT to teach me a special workaround. In hindsight, I probably should have told ChatGPT from the start that I intended to use them in that way.

References

See a link collection on CCM. There are two reference lists. One is a list ordered in reverse time order and a list sorted by the types of problems, which can also be accessed indirectly through the first link collection. There is also a list of papers, which also contains papers on other researches (which is available only in Japanese currently). You can choose which you think the best.

Most of the papers in the above lists are accessed in PostScript format on the Internet. However, the following papers are in HTML, so you can directly see them using Web browsers.

• Kanada, Y., and Hirokawa, M.: Stochastic Problem Solving by Local Computation based on Self-organization Paradigm, 27th Hawaii International Conference on System Sciences (HICSS-27), 82-91, 1994.
• Yasusi Kanada : Toward A Model of Self-organizing Systems Using Computers, Proc. 33rd Programming Symposium, January, 1992 (in Japanese)
• Yasusi Kanada : Computational Systems as Self-organizing Systems -- Two Proposal for Software Research --, Proc. of the Summer Programming Symposium, July, 1992 (in Japanese).

The most recent paper in English is

• Y. Kanada: Methods of Parallel Processing of Constraint Satisfaction Using CCM --- A Model for Emergent Computation, SIG PPAI, Japan Society for Artificial Intelligence, Feb, 1996.

CCM was deviced in Central Research Laboratory, Hitachi, Ltd., which the author still belongs, and developed in Tsukuba Research Center, Real World Computing Partnership. However, the programs above are not developed in my organizational job. So, the copyright belongs to the author himself. You can copy or rewrite the programs freely unless commercial purpose.

This page was advertized by search engines and directory services using these messages.