The road to the Last Piece - computing with partial knowledge


#1

For my project I have now 3 vital pieces in place: A scripting language for in-game programming (Dyon), an idea for balancing an economic system (Mix-Algorithm) and a fictional physical world that explains super heroes (The Youngness Problem).

I think this is a good starting point for a game which creates a new category all by itself. Of course I don’t expect a such project to succeed, I do it because I think these ideas are worth pursuing. What I expect is to learn something or create something useful out of it. It has been very interesting to explore these ideas independently, but it will be also interesting to see how they interact. The learning curve of working on these problems has been quite steep, so I want to work on some easier projects from time to time to keep it challenging, but not too hard.

The Last Piece is perhaps the most difficult of them all, one that I don’t expect to expose to players directly. It is so hard that I am concerned it never will get finished. I have worked on this idea for 2 years already, but still find it very challenging. Only recently I starting to realize how this could be turned into something useful.

I call it the “Last Piece” because I don’t know any significant challenge in computing beyond this horizon. This is as far as my knowledge can stretch, and I fail to imagine what is beyond that.

You might wonder what the heck these different ideas got to do with each other, so I will tell you.

If you look closer at the 3 other pieces, you see that they take a perspective on 3 key areas of a technological civilization:

To me these parts belong to a fictional category, kind of like when an author writes a book exploring ideas in a science-fiction world. I don’t impose them on others, because that is not my goal. It is part of a story, a perspective. Yet, they are fully real in the sense that work, as far as I can comprehend them. I expect reality to show how these ideas break down and fail, and when this happens, I will learn something.

It like a work of philosophy, where the goal is to ask the big questions like WHY NOT and WHAT IF? I believe a program, a game, can be a question, and the answer is given by the players!

The Last Piece is one area that is very close to my heart, because it is my critique of mathematics and logic itself. This also makes it the hardest part.

People like Immanuel Kant, George Cantor, David Hilbert and Bertrand Russel made their largest contributions in this area, together with many, many other people. It is a picture I have of the utmost important events in history and what people were thinking about and striving for, that almost nobody strives for today. Because of the simple reason that many people don’t know or don’t believe this opportunity exists. This makes it quite interesting to use as a concept for technology in a game.

The Last Piece is a perspective of what thinking and understanding means!

Much of history of logic is about expressing truth, up to the point of Wittgenstein which raised doubt about it in all his madness. First I could see the genius in Wittgenstein, and later I learned enough to consider him partly delusional, but he was on to something.

I won’t pretend that I know enough about Wittgenstein to tell what he would think, because I don’t. This is about what I think is the core idea of his philosophy:

The distinction between the known and the unknown, and problem of representing this knowledge as logic!

The problem with logic, is that it draws a picture of the world that is without doubt. It is a single-minded way of describing the world. Various extensions of logic uses probability to fuzzy out the boundary. Today we also use machine learning and Bayesian reasoning to capture or structure the knowledge from data.

Yet, the mind blowing thing about logic is that you can capture aspects of a problem in a few sentences. It is extremely efficient at getting to the core of the problem! It is like having it with you in the pocket, it does not take up much room, and it is useful in various situations.

When I started thinking about this 2 years ago, I did not know logic. I still don’t master it. What I am about to tell you about is something that helped me understand more about logic. It started because I wanted to figure out why dependently types is so useful in some ways, but hard to use in other ways.

The result is something I call “path semantics”. It is directly analogous to logic in some ways, but represents knowledge in a way that I prefer when there is a question of whether something is known or unknown about some piece of knowledge.

Path semantics

Imagine that you have a machine which you feed 1$ and you get a cup of coffee. We don’t know how the machine works internally, but we know this:

insert_coin(coin, machine) -> res[coffee]

The machine is an object that exists in the physical world. It is not a piece of data in a computer program. The knowledge we want to express is about the machine and how it interacts with other concepts taken from the real world. It does not matter that knowledge is inaccurate or big parts of it is lacking, as long as it is useful.

In path semantics, you use the trick of pretending that real objects are algorithms. Since path semantics can express knowledge about algorithms, using algorithms, it can express knowledge about real world objects without knowing their internal workings.

Here is how you can express that if you put on less than 1$, you don’t get a cup of coffee:

insert_coin(: <1$, : _) -> : err("You need 1$")

If you put on 1$ and the machine is not broken, then you get a cup of coffee:

is_broken(machine) -> bool

insert_coin(: 1$, is_broken : false) -> : ok(new_coffee())

It looks quite like ordinary programming, but I will show the difference later.
Anyway, what does this have to do with logic?

Computing with partial knowledge is a form of communication

The problem with logic is that it asserts something, but does not tell how to use that knowledge. Path semantics takes some ideas from logic that can be communicated.

For example:

Alice and Bob want to get a cup of coffee. Alice knows how to tell whether the machine is broken, but Bob doesn’t know. How can Bob know whether he will get a cup of coffee if he got 1$?

The sentence is_broken : false is a first-class citizen in path semantics. It tells that is_broken was called and false was returned. Since is_broken takes a machine as first argument, then Alice could tell Bob she knows is_broken(machine) -> bool and then tell him is_broken : false. Bob can use this knowledge to determine whether inserting a coin will give him a cup of coffee.

Path semantics is a formal language for communicating logic!

Alice and Bob might not have the same way of representing the machine. Yet, if both understands path semantics, then they can help each other.

For example, if Bob knows:

insert_coin(: 1$, is_broken : false) -> : ok(new_coffee())

This corresponds to the logical statement:

forall X: machine {
    !is_broken(X) &&
    insert_coin(1$, X) == ok(new_coffee())
}

So, if you represent and compute knowledge using path semantics, you can translate back and forth from logic. You could have a theorem prover that takes a question and answers them. A puzzle solver with backtracking could find solutions for a given problem. A situation can be recognized and searched for in a knowledge database for learned solutions.

I believe that many problems are more readable in path semantics than in logic. There are also other properties that are desirable about this notation:

  1. Partial knowledge can be learned and erased independently
  2. It resembles syntax of functional programming
  3. Lot of “common sense” problems has an intuitive representation

Why is this such a big deal?

The immitation game, also called the Turing test, is actually very desirable in gameplay.

When programming characters controlled by AI in a game, we want them to be sophisticated but cheap to compute. The best methods for AI today are very expensive, such as deep learning. Over time I expect such techniques to improve performance through integrated hardware, but it will take a while before this becomes mainstream. So, I need some new ideas.

There are many challenges in game AI:

  • There are almost no interesting AI characters because they are simply acting on the environment instead of thinking about problems and communicating
  • If AI pretends to be human in a game, we would expect it to make errors like humans do - this is hard to fake
  • There are many ways to reach the same conclusion from existing knowledge - this is very hard to program in a normal programming language

A knowledge database with path semantics could be reused between projects. It is relatively easy to to read and understand. Knowledge can be tested for consistency offline. It is suitable for communication, which could give room for many collaboration games.

I think path semantics has a lot of potential to give AI characters “thoughts” a bit similar to what humans have.

Now you should realize why this is a big deal!

How far I have come with this idea?

I can compute with very simple forms of knowledge, but there are lots of bugs. Will open source it as soon as I have something usable. I do not expect this idea to be interesting for others besides myself, but it is an important piece in the project I want to work on.

How hard is it?

At this stage, I do not even know if the idea can be made practical at all. I expect it to take a few years before it becomes usable.