It's a stupid month anyways.

I realized recently that I've been spelling the word "February" wrong for my whole life. For as long as I can remember, I've been spelling it "Febuary". I don't know why I haven't realized until now.

BeijingChess: A New Direction in Chess Theory

I've been writing about and working on a new idea of mine, a chess engine. The approach that I'm taking hasn't been really taken seriously since the 1950's but I believe that I have some direction that may be fruitful. The project shall be called BeijingChess because I've been having quite a bit of fun learning Chinese recently. I don't naively think China is the best country in the world or any nonsense like that. But I do think that in China there is alot of "texture" that I don't know about yet, and I think it would be wise to pay attention. In the next few posts, I'm going to outline what I think is a promising direction in chess engine theory. If you know how to play chess, you shouldn't have such a hard time following.

The Concept of BejingChess

Presently, the vast majority of serious chess engines (computer programs that play chess) use a brute force style of analysis. This means that the program looks at the current position and judges the utility of every possible position that can result from that position. Because of time constraints, the brute force chess engines can normally only manage to look around somewhere between 8-12 moves ahead, depending on the time settings, the speed of the computer, and the quality of the searching algorithm. After searching as far into the future as it can, the engine plays the most rewarding move that it found.

The brute force method used in chess engines results in the engine playing a rather tactical game, meaning that the computer rarely will ever make and "stupid mistakes" and rarely will be tricked by standard 5 or 6 move mating sequences. However, the standard brute force algorithms tend to be very poor at strategic play. This means that computers will never organize their pieces for a planned attack and never will consider piece formations or balance of gameplay. Some of the best chess engines are able to mimick strategic play because the engine is able to branch out far enough in it's considerations to find that the strategic moves are most useful.

The brute force approach takes advantage of the computer's ability to quickly evaluate move sequences. The brute force algorithms consists of a state formulation, a set of rules to generate possible changes in state, and simple heuristics to evaluate the utility of a state. The engine isn't really built to understand chess at all but rather to cycle through all the possible "state changes". Chess is elegant. An algorithm that plays chess should therefore be elegant also. The algorithm's considerations should be tightly coupled to the dynamic strategies of a real chess game.

Consider the two familiar categories of chess reasoning, that done by brute force engines and that done by humans. The chess reasoning done by brute force engines requires no higher level concepts; only the current state and possible state changes are needed. Adopting a well-written brute force engine to play a slightly modified version of chess would be relatively simple. The programmer would merely need to update the rules for possible state changes. Even if the new version of chess were to have drastically different dynamics and feel than a game of standard chess, the easily updated version of the brute force engine would still play a decent game.

Contrast a brute force engine with a human. The human would need to adjust his planning procedure considerably if the rules of chess were changed even the slightest. This is because the brute force algorithm considers only the rules, whereas the human player plays chess using concepts. The player invents helper terms--such as pawn structure, attack plans, pins, forks, skewers, discovered attacks, and overloadings--to define important abstract dynamics of gameplay. Expert chess players focus on explicit sequence evaluation only a portion of the time; mostly, they see the board in terms of a new "imaginary physics" that has it's foundations in the rules of chess.

"Imaginary Physics": A New Formal System

This concept of an imaginary physics is key in BeijingChess. The potential power of BeijingChess comes from defining new, more manageable physics to describe the gameplay of chess. Ideally, this new physics will have a structure that illuminates the important dynamics of the game, so that finding the proper move becomes more manageable. This imaginary physics may also be called a formal system.

The relationship between the rules of chess and my hypothetical imaginary system is very similar to the relationship between the analogue world and the mathematical system that we have developed to describe that world. As an example, consider the following lighthearted scenario. Suppose you have two groups of cows. You would like to conceptualize how many cows how many cows are in each group and also how many cows you would have if you combined the two groups. When I said "conceptualize how many" I'm willing to bet that in your mind you immediately thought of "numbers". I didn't mention anything about numbers, counting, or adding, but you nonetheless took for granted that conceptualizing "how many" necessarily involves numbers or mathematics. But, if you consider carefully, you find that our choice of Mathematics to describe quantities is actually arbitrary. Further, many of the rules and manipulations that are allowed in mathematics do not have any relation with what is actually because conceptualized.

To illustrate the point, let us consider how one would conceptualize how many cows would result if both groups were combined. Also, let us assume that we know the number of cows in each of the two groups and that each group has more than ten cows. Thus, combining the groups would mean calculating the sum of two known two-digit numbers. The procedure is elementary for us. We align the numbers' places in columns and add their digits. Adding digits normally means retrieving it from memory. If the sum of the digits is greater than nine, we place a one over the adjacent column and then proceed to add the adjacent column. We continue this process for each column until we have an answer. If we did all the intermediate steps correctly, our final answer should correctly describe the number of cows in the combined group. Consider how many of our two-digit addition that we followed that had nothing to do with cows; we were merely manipulating symbols according to a predefined set of rules. Nonetheless, our final result had external relevance; it did describe how many cows would result if we were to combine the two groups. Another simpler way to conceptualize how many cows are in both groups would be to combine the groups and count one-by-one how many there are. This method allows us to use only a simple abstraction; each cow represents an increase in the count. The disadvantage of this method is that it would take much longer than using our abstract system for adding the numbers of the two groups.

We have found that we can use the formal system of Mathematics to simplify our understanding of the analogue world. We can apply this metaphor to the problem of building chess engines. I believe that a promising direction in creating a chess engine that plans is to find useful abstractions that simplify our calculation or illuminate the important dynamics of the game. This abstraction will be in the form of a formal system in that it will consist of symbols and rules to manipulate those symbols.

[to be continued...]

An Update and Accompanying Thoughts

I've finally gotten around to getting legitimately tested for ADHD. Before when I was tested, I just filled out some questionnaire that asked a number of questions about the symptoms as I saw them. I used this diagnosis so that I could get out of living in sophomore housing units on campus, but I guess I never really took it all that seriously. So this past week I took an IQ test and some other tests related to attention to finally pin down a sure diagnosis.

You may be wondering what the fuss is about. Why does it matter? Well, it's hard to explain in a vacuum but consider this. I have a number of things that I want to get done in life, but at this point I don't see myself as having the right trajectory to reach them. I feel like I work very hard to reach them and I have come very far from where I originally was, but I'm still afraid that I might not hit the mark.

I often have a hard time concentrating and I show quite a bit of absent-minded behavior. Now, these two concepts are fairly high level, and it may be hard to really understand what they mean to me specially without giving examples or anecdotes. I could do that, but I would rather let you be skeptical for a moment; I want you to be skeptical as I have been skeptical.

I'm sure you could on a superficial level understand how these two problems could keep me from reaching my goals. I'm an academic, so most of my work involves some form of concentrating. If I'm working alone, trying to understand a concept or giving a critique, I need to be able to focus on work. If I'm in a club meeting, planning future action, I need to concentrate. Also, collaboration is ideal in academics, and collaboration involves working with people. Working with people involves a interfacing on the level of appointments and meetings. How can one work with people when one loses track of times and dates and appointments and classes?

As I have said, I have problems with concentrating and being absent-minded. And of course I ask myself why. I tend to assume that I either don't try hard enough or that I have ADHD. In a funny sort of way, you can translate this dichotomy into me wondering how much my disappointing performance is "my fault". How much of my mediocre academics resulted from behavior that I could be "judged" for?

Consider the following illustration. Suppose that a runner doesn't finish a race and we are trying to understand why. We wonder if there was perhaps some external circumstance with which the runner was burdened. Did the runner have a physical impairment like a weak knee, the flu, or asthma? Or possibly it something that set him back emotionally that would have kept him from seriously preparing. Did his parents recently get a divorce? Did someone in his family pass away? If there were some special reason for the runners underperformance, we would could accept it. But, if we looked and saw that considering circumstances into account, the runner was on the same plane as all of the other runners who did finish, we would tend to look down on the runner. We would question his commitment to running.

Similarly to the observer of the runner, I try to understand how to look at my struggle to achieve my goals. This is part of the broader attempt to have a clear identity, which nearly everyone does to a certain extent. If I'm so serious about what I want to do, why aren't I on the path to doing it? Am I a slacker? Am I hampered? Do I fail by will or by circumstance? These questions tend to be fuzzy to me. So, I got retested for ADHD.

The results came; I do indeed show it. Only 5% of the people that have ADHD will graduate from college, compared with 30% of the people that don't? Isn't that absurd? On PET scans, people with ADHD even show decreased blood flow to certain specific areas of the brain.

---

There is a subtle point in the illustration about the runner that has ofter terrified me. I avoid thinking about it and I wouldn't be surprised if, as I result, I have an undeveloped way of looking at it. In the illustration, I took for granted that we have a solid concept of "external circumstance". We might say that it is any fact unrelated to running that would effectually prevent the runner from finishing. We implicitly used this definition and were able easily list a few examples. But, it falls through because it is unable to provide a limit on what sorts of facts that we can use. And without this limit, our whole system of subjective judgment falls into pieces. An an example, what if we allowed ourselves to attribute the runner's not finishing the race to the fact that his father never instilled in him a sense of excellence? If we do call the runner "lazy", do we blame his father rather than him? Probably not, because after probing the father's situation we would find that there was some "external circumstance" that kept him from properly raising his son. We could continue this process until we eventually conclude that the faults of everybody are the result of external circumstances and that therefore nobody is to blame for any of their actions.

This certainly doesn't do. Now, we are unable to pass judgment on anything. Thinking this way, I must assume that the problems of the world are inherent because nobody is to blame for anything. I become completely confused and afraid because I have no way of knowing where to inject the changes needed to make it a better place. This line of thought is manifested quite powerfully in the movie Dogville. The movie is a dialog between the two extreme views on the topic: that individuals can be judged and held accountable for their actions and that individuals always will have had some external circumstance that gives excuse for their behavior.

Funny Subculture in a Back Corner of Society

I may have funny memories related to videos like these...

BEON BEON!

Closer to the beginning of the summer, I was working on a toy ALife program that would allow for a qualitatively higher amount of complexity. Essentially, the program was to be an artificial chemistry like John Conway's game of life but with more expressive primitives. I wanted to cut to the chase, so to speak, because computing irl chemistries is a huge waste of computing time. Many aspects of physics occur in parallel and I tend to think that they could be reduced down to simpler rules. I've stopped working on this though because I'm seriously thinking about changing focus in life (ambiguous? you bet) and starting a large programming project doesn't appeal to me at the moment. I post my incomplete notes to feel connected to collective intelligence called Internet. Skim it if you want...

Theory

The digital life system will not necessarily be a useful tool for quantitative alife research. Rather, it is an arbitrary model that attempts to illustrate the dynamics that come into play in a bare bones living system. Also, it attempts to demonstrate open-ended evolution better than previous models.

The primary innovation with Offy is it's choice of medium. It is a well accepted view that life can be loosely defined as information in a medium that persists over time. Previous models have struggled to find a suitable medium. Though the term 'medium' includes the space in which the life is found (square vs hexagonal cells, toroidal or finite shape, etc), it also more abstractly refers to the physics of the world that onto which the information is mapped.

I shall expound on what I mean when I talk about information mapping onto a medium. [Consider Adami's discussion of information in evolution in Adami 2002 What Is Complexity?] We assume that an organism's information is maximized if it's behavior is optimal for a given system. The medium is any aspect of the system that if changed affects the information content in the organism.

The important aspect of the medium that we need to focus on is the manner in which information increases as the genetic algorithm search proceeds. It helps to first qualitatively define an arbitrary attribute of the system, the difficulty in which information increases as natural selection is in place. Consider in an environment a population that has been evolving as a result of natural selection. As time goes towards infinity, we assume if the environment stays the same that the genomes in the population will get closer to “optimal” in the sense that the information contained therein is associated with the highest probability of being propagated. In this population, it is fairly unlikely that any mutation in a genome will endow the genome's information with a higher probability of being propagated. In this sense, the information in the environment increases with a nearly maximum difficulty.

Conversely, consider another system of the same type except that the population's genomes are completely randomized. The genomes contain no information with respect to that system. When the population is subjected to natural selection, one expects the information to increase fairly quickly with relative ease.

These two hypothetical systems qualitatively correspond to the maximum and minimum difficulty values with which information in the system increases. We might think of the systems differing in their “potential” for information increase, that is, the information entropy contained in the genomes.

It is important that we remember the information in this instance isn't measured in continuous values. Rather, in this instance the information changes by discrete amounts. For example, consider a genome comprised of a string of bits. If we assume that we somehow derived a string that call “optimal” for the given domain. We may think to measure the information in the genome by comparing it to the optimal genome. How much does the bit string under consideration resemble the optimal string?

The problem with this approach is that it may lead us to think that a given bit string has high information content though it actually performs very poorly in the environment. The literature concerning genetic algorithms usually refers to the concept of a schema, a string of bits whose presence in the genome results in the genome having a relatively dramatic increase in fitness. And conversely, a modification of one of these strings results in a relatively dramatic decrease in fitness. A real life example of this may be a string of DNA that codes for a protein that can metabolize a specific protein. Once by chance this string is created in the course of natural selection, the organism would have an increased probability of survival and gene propagation.

The important point to bring out of this discussion of information and schemas is its implications of the design of a digital evolution system. I propose that the largest limitation to fostering open-ended evolution in existing digital evolution systems is the choice of medium.

[...]

[Explanation of how the genome needs greater access to the physics of the world:]

[justification for arbitrary artificial chemistry:]

It is true that a number of well-known cellular automata or artificial chemistry models already contain the functionality to be Turing complete. This may at first thought be encouraging because if a system is proved to be Turing complete the system can scale up to possibly an infinite number of computational problems. The problem with this line of thinking however is that our simulated evolution of complexity is limited by our powers of computation. Consider the most simple and most well-known example of an artificial chemistry, John Conway's Game of Life. It has been shown that the system can be Turing complete; so theoretically speaking if one repeatedly generated random grid distributions, as simulation time approached infinity, the probability of producing a structure capable of remembering its own design information would tend towards one. In addition to the problem of limited computation time, one would also face the problem of limited computational space. Even if the we were certain the it were possible create a robust evolving system in such an artificial chemistry, we have be sure that is computationally feasible. After all, if computation weren't the limiting factor, what would keep us from simply modeling the low-level rules of real world particle physics to create the sort of complexity that we are already familiar with?

If we want to create in silico the dynamic systems that we see in real life, we need to construct artificial chemistries that are more expressive. [Talk about how the time it takes to express something in a simple language is longer than the time it would take to express something in a more complicated language. But in the end, does the increased number of computer cycles needed to process the more complicated language make up for this difference? If we are counting the total number of words that we speak, increasing the size of the vocabulary will certainly help. But, if we are talking about reducing the words to bits anyways (the smallest unit of information), could it be impossible to make such a simplification? ]

The following is a list of easily generalizable themes that can be seen in living systems:

• information transfer
• compartmentalization (enclosed area of information exchange)
• directed information transfer (nerves)
• information distribution to area within a given radius
  
• locomotion
• efficiency
• flexibility
• energy
• competition for energy energy is a universally accepted currency (fungible and fluid)
• the processes of sending and receiving of energy are akin to information transfer (eg. metabolism)]

[Answer this: This doesn't really demonstrate the complexity that is found in real life because you are programming the complexity to be built in.

Model Physics and World

The world consists of a hexagonal grid of cells, most likely infinite or toroidal. Each cell can either be “alive” or “lifeless”. Each living cell is assigned a type, which corresponds to a unique function that the cell can perform. The various types of cells were created in such a way to parallel themes found in real-life living systems.

[Possible information contents of a cell]

• organism id

[Possible information contents of a organism]

• energy level

The following is a list of possible cell types.

• The Mover
• Can move an adjacent cell or group of cells to an adjacent square
  
• The Signaler (area signal)
  
• Creates a signal that is received by all cells within a certain distance
  
• The Signaler (line signal)
  
• Creates a signal that is carried byPropagators
  
• The Compartmentalizer
  
• Is involved with defining a compartment
  
• The Propagator
  
• If a line signal is received on one side of the cell, the signal is propagated to all other sides of the cell
  
• The Repository
• Stores a certain number of bits that can be accessed
  
• The Computer
• Similar to the microprocessor of the Avida system

Each cell types in a member of a class:

• Computer, has VM and registers
  
• Register Only, has registers
  
• Inert, has nothing

I Opened the Circuit Breaker and then I Saw...

Last post I outlined an armchair theory, well, not really a theory but more of an approach to building a system to generate music. I ended the post saying that I would outline my idea to algorithmically calculate musical dissonance. Well, it turns out that I forgot that before I can talk about dissonance, I first have to talk about another idea that I've been thinking about (not mine) called structuralism (lol).

I have to admit that I only really know the concept of structuralism from a book I read called 'Digital Mantras', which among various things talked about art and music as it applied to pre-nineties linguistics. I admit that much of the thinking that I've been doing on music is a direct result of that book; it's worth reading in my opinion.

From what I can gather from the book and from wiki, Structuralism was the idea that tried to take over abunch of different disciplines. Originally a concept from linguistics to explain the function of word symbols, it spread to the social sciences to help understand the dynamics of social conventions. You should wiki the word if you're really interested in what it actually means. I think I really only understand a small part of it, a certain dynamic of differentiation, specifically that the meaning of symbols in a set is dependent on the other symbols in the set.

Sounds fancy, right? It's really not too difficult if you have a common example to think of. As an example that has to do with symbols, when I received grade cards in elementary school, I always got the grade "Good" in spelling. So I'd go home and tell my parents that I got a "Good" and they'd be really proud. Well, the problem is that the meaning of the grade depends on whatever other grade possibilities are also in the set. Obviously, it would make quite a bit of difference if the grade set consisted of "Excellent", "Very Good", and "Good"; or alternatively if there were simply "Good" and "Bad".

This dynamic of differentiation generally can be seen in nearly any domains where elements are compared to each other in a set. A few examples of where it can be used:

-In social psych to explain the interpretation of social conventions by members of a group
-In anthropology to help understand the meaning of old myths.
-In music as a way to look at the dynamics of playing to a genre expectation.
-It can be used in fashion to understand the process by which new styles are affected by the recent styles.
-In any art to understand the significance of the use of a particular device

Ah, I kinda wish that I could explain all these applications that I'm claiming; maybe I'll do that later. Seriously though, the the concept was pretty popular at one point and I'm certain that somebody has already formalized these ideas in a fancy paper.

Now that you (maybe) have a general idea of what the concept is, it would help to be a bit more specific about what I mean. Let us define a set S that contain an N number of objects of an arbitrary type T, except that the object type must have a dimension by which it can be compared to other objects in the set. We will call this dimension by which we compare D. We assume that the function F(T1, S), with T1 being an instance in that set, will return some meaning about that particular instance. The important point in Structuralism is that there exists no function G(T1)—it knows nothing of the set--that can yield any information about T1.

An important dynamic that comes into play when trying to apply structuralism to various domains is that the nature of function F is dependent on the domain in which you are studying and a little more specifically on the dimension D that you have chosen. It often depends on the semantics of the dimension D. For example, let us go back to the story of my grade school report card. The elements in the set carry the semantic value of judgment; they are intended to reflect on my performance. Thus, for this purpose the elements in the set are assumed to have a distinct order. If the set consists in-order of “Good”, “Very Good”, and “Excellent”, one would be quite confused if they were listed any other way. Thus, by the semantics of the set, order matters.

I’ll continue later…

Background to Idea about Natural Simulated Annealing

Lately, I've been thinking about computer models of evolution. I have to admit that I might not know as much as I should in this domain with respect to how much I talk about it. With how much I get distracted by other fields and how this past year my academic life crumbled to pieces, I haven't been reading much about evolution or ALife recently. But, I had this idea about a way the natural process of evolution could mimic the Simulated Annealing algorithm that is popular as an AI search strategy.

If you would first like some background knowledge computer models of evolution, you should look up the wiki page about "Avida", which is the most popular of computer evolutionary models. But in short, Avida is a program that simulates a population of simplified organisms and demonstrates their evolution over time.

Each of the organisms, the Avidians, consists really of just a genome of instructions, which are continuously being executed. The instructions are in the form of a modified computer assembly language, which performs operations on memory locations.

In the Avida model, organisms are rewarded for doing specific things by getting more SIPs, which can be thought of as being the "energy" to carry out instructions. If an organism runs out of SIPs, it dies. Thus, because there are a limited number of SIPs in the world, the Avidian the can get SIPs most efficiently reproduce more often than others, and thus their genes are more likely to be propagated through time. This leads to natural selection and evolution of form.

Well, this model is really great for answering lots of questions about the dynamics of evolution when it happens, but one concept that isn't quite understood is that of open-ended evolution. The last time I checked, we were having problems creating systems that can evolve and continue to evolve. Simulations usually evolve up to a certain point, at which they've reached a local fitness maximum in the given domain. Because there is no simple change in the genome that can cause them to have a higher fitness, the population diversity drops through the floor and evolution stops.

In the last paragraph I described a problem that is common in both ALife sims and AI search local search strategies whenever a "hill climbing" paradigm is used. For example, imagine that you are trying to find the highest peak of a mountain. The simplest algorithm to use is to merely walk directly uphill, and eventually you will reach the peak. This works most of the time, but there are certain situations where this wouldn't work, namely when there is more than one peak. Walking directly uphill could lead to your reaching the wrong peak, and if you don't have some contingency, you'll be stuck.

This is a problem in genetic algorithms, because no one is "driving" it so there is no contingency when the population gets stuck on a local fitness maximum.

Given this bit of introductory information, in my next entry I'll move on to the actual reason for posting this, namely that I had an idea for a natural algorithm that could mimic the effects of the Simulated Annealing technique, which is used to avoid getting stuck on fitness maximums.

(Btw, I'm still developing the idea on musical composition, so, that'll have to come later.)

Armchair Music and an Ironic Picture

I had an idea that I’ve been working on for a while. Except, by working on it, I mean that I've been thinking and writing about it; so, it may or may not be grounded in the literature; or, it may something that is completely obvious. I wouldn't know, and I don't really care that I don't know, at least for right now.

Anyways, the idea has to do with building a framework to allow for the automated composition of music. Obviously, one of the most significant difficulties in generating such a framework is that the way that music interacts with the human mind in such a way that creates emotional response is quite a complicated process. The type of music that can give a person the chills has to interact with the listener in a low-level psychological, or I say even social dynamic. I do not think that any such algorithm would be simple or trivial. I remember reading at one point the webpage of someone who developed a system of tonal jazz composition that involved using the Fibonacci sequence. I listened to some of their samples and the stuff was awful. They tried to reduce the complex dynamics of music to a simple number sequence and it was pretty much painful to hear and emotionally void.

Okay, so the scientist is admitting that dissecting human appreciation of music won't be an easy task. A gross understatement, right? Yeah. I'm not even sure that making such a system is possible, but if we assume that it is, the best way to work towards building one would be to pick known musical devices and to try to build models as to how they work. Then, implement the models in a musical generation program and see if the models produce music that captures the point of the devices.

Also, I should say that I use the word 'device' very loosely. I'm sure somewhere there is a precise definition as to what a musical device actually means in terms of musical scale (notes, lines, phrases, sections, movements, pieces). Really, I am just using it to mean any strategy used in any of the musical domains (harmony, melody, rhythm, dynamics between parts, movement of a single part, etc) to affect the listener.

So, my strategy for building a musical composition framework is to first separate the devices and to for each develop a model to explain the effect of each. The first device that I've been thinking about, which generally covers some aspects of harmony and melody is that of the tonal relationship between neighboring tones. Specifically, given the frequencies of a series of tones, I propose that one could combinatorially calculate a single term to describe the tonality (in terms of dissonance) between all or any subset of the series.

I will continue describing the concept of calculating dissonance in my next post as this is enough to read for right now.

Random ending tidbit: In a paper that we covered in our Sages class, I read about an experiment that used brain scans to determine which parts of the brain are activated when a person gets the chills from listening to music. It sounds pretty subjective I guess, but they used lots of controls to make sure that what they were finding was legit. Anyways, they found that many of the areas of the brain that are active when a person gets the chills from listening to music overlap with areas of the brain that are active when a person is doing common overtly pleasurable activities, such as having sex, taking drugs, or eating.