четвъртък, 26 април 2018 г.

The IQ of Artificial Intelligence


All it takes to identify the computer programs which are Artificial Intelligence is to give them a test and award AI to those that pass the test. Let us say that the scores they earn at the test will be called IQ. We cannot pinpoint a minimum IQ threshold that a program has to cover in order to be AI, however, we will choose a certain value. Thus, our definition for AI will be any program the IQ of which is above the chosen value. While this idea has already been implemented in [3], here we will revisit this construct in order to introduce certain improvements.

Keywords: Artificial Intelligence, Definition of AI, IQ of AI.


Introduction

We will use a test to determine what AI is. The test will produce a certain score, and we say that this is the program’s IQ. Then we decide that all computer programs the IQ of which is above a certain level satisfy the AI definition.

In order to explain this concept, let us make an analogy with the admission tests given to candidates who wish to become university students. The problems given at the test are selected randomly, but all candidate students receive the same problems. Withal, solving the problems should require logical thinking, because we aim to enroll students who think logically rather than the lucky ones that may hit the right answers haphazardly. The score is based on the number of problems solved by each candidate student. We cannot say how many problems should be solved, because we do not know how many candidates will show up at the test, nor do we know how well or unwell they will perform. We may say set a certain score (e.g. 4.50) and say that we intend to admit all candidates who earn more than 4.50. However, it would be better to fix the minimum score after the test is done. Then we will take the score earned by the n-th ranking candidate (e.g. if n is 100 we take the score of the candidate whose score puts him in the 100th position in the ranking and thus we enroll the top 100 candidates).

This analogy describes well the AI test, but when the candidates are computer programs, we cannot select the 100 top performers, because in this case there will be infinitely many candidates. A better analogy is perhaps a recruitment contest for the CEO of a corporation with a test that drags on over time. The test will stop when a candidate earns a sufficient number of points. How many points are enough? While we may select a certain level in advance, we can adjust this level later if the initial level turns out to be too low or too high.

A similar construct was already put forward in [3] whereby the various programs were given different scores (IQÎ[0.1]). Here we will revisit this construct in order to improve it. The reasons for which [3] needs improvement are:

1. In [3] we dealt concurrently with the questions of ‘What is AI?’ and ‘How can we create AI?’. Mixing up ‘what’ and ‘how’ is not a good idea. Here we will reduce ourselves just to the ‘What is AI?’ question and will not deal with how to find such a program.

2. In [3] we defined AI as a program and here we will define AI as strategy. In [3] AI is a program and the world AI lives in is a program, too. Thus we end up with two programs playing against each other, which is somewhat perplexing. It is better to define AI as a strategy and have a program playing against a strategy. Certainly, the strategy will be computable, because it is finite. Our AI program will be any program which implements an AI strategy for the first 1000 games. What the AI program does after 1000 games will remain undetermined, however it is hoped that the program will continue to behave intelligently thereafter.

3. In [3] the world was presented by means of non-deterministic Turning machines. This is a futile complication. It would have made sense if there were no relation between the individual games and if the machine tape were erased (reset) after each game. And because the tape is not erased, each next game depends on what happened in the previous game (what has remained on the tape). For this reason we will use deterministic Turing machines which are simpler, while the fact that they depend on what has remained on the tape makes their behavior in the various games different (non-deterministic).

4. At each step we have Action and Observation. Actions and Observations in [3] consisted of a single symbol, while here the Action will consist of n symbols and the Observation will be of m symbols. We can certainly code multiple symbols into one, but this will be at odds with the idea that unnecessary coding should be avoided [6]. The world is complicated and hard to understand enough. Adding one unnecessary coding will make it even less understandable.

5. While in [3] it was assumed that all moves are correct, here we will add the concept of incorrect move. On one side it is important to assume that incorrect moves may exist. On the other side, this will spare us the indiscriminate shutdowns of the Turing machine, which we did in [3] in order to avoid cycling.

6. The Turing machine is a theoretical model which does not need efficiency. Here we will harness this model in real work and will therefore modify it in order to boost its efficiency. The complication of the model is the price to be paid for the so obtained higher efficiency.

7. In [3] we used the Turing machine in order to describe a logical world. If it is computable it should be logical. However, the world described by the Turing machine is not very logical. Everything is recorded on a single tape and the program is not structured at all. It jumps indiscriminately from one command to another (‘spaghetti code’, as software engineers have tagged this pattern). The way such a program operates is rather illogical and we will address this by adding subprograms and more tapes so the machine becomes a multi-tape one.

8. In [3] we defined IQ as an arithmetic mean which cannot be calculated precisely because of combinatorial explosion. What we say there is that it can be calculated approximately through a statistical sample. Here we will introduce the terms ‘Global IQ’ — which cannot be calculated precisely, and ‘Local IQ’ — which is readily computable through a specific statistical sample. The Local IQ will approach to the Global IQ when the size of the statistical sample approaches to infinity. The set of worlds we use for calculating the Global IQ is finite (enormous, but still finite). Nevertheless, the size of the statistical sample can tend to infinity because there may be repetitions in the sample (although repetitions are unlikely due to the hugeness of the set from which the sample is recruited).


Related work

In [7], Turing proposes his definition of AI (the Turing test). The idea is that if a machine can successfully imitate a human, then this machine is AI. In the Turing test, as in our article, we have an exam and in order for a machine to be recognized as AI, it has to pass the exam. One difference is that there is an interrogator there, while we have a test with fixed tasks. That is, the Turing test is subjective, which is why it is an informal definition of AI. However, the main problem of Turing's definition is not in its subjectivity and informality, but in the fact that it does not define an intellect, but something more. It defines an educated intellect. For an intellect to pass the Turing test, it must be educated. We can even assume it has an Anglo-Saxon education because if it does not speak English it would not perform well on the test.

Intellect and educated intellect are two different things, just like a computer without software and a computer with software are two different things. If you ask a mathematician what a computer is, he will answer you: “the Turing machine. If you ask the same question to a child, the child will answer: A computer is something that you can play games on, watch movies, etc. That is, mathematicians perceive the computer only as hardware, while the child perceives the computer as an indivisible system of software and hardware. When Turing gave a definition of a computer (the Turing machine), he described only the hardware, but when he defined intellect, he described an indivisible system of intellect and education.

Despite the Turing test defines educated intellect, Turing understands very well the difference between educated and uneducated intellect. In the end of [7] he asked the question: “Instead of trying to produce a program to simulate the adult mind, why not rather try to produce one which simulates the child's?”

The AI ​​definition we give in this article answers to this question. It does not include education and the tasks in the test do not imply any preliminary knowledge. That is, with every task we will assume that we are starting anew, and that in the course of solving the task we are learning, i.e. we find dependencies and learn from our mistakes.

In [8], McCarthy says that the distinctive feature of AI is the ability to achieve goals in the world. We will not argue with McCarthy, but we will only clarify what he has said. We will specify what a world is and what a random world is and what are the goals that AI needs to achieve. On this basis, we will create an IQ test where programs that achieve more goals have a higher IQ.

McCarthy also says that there is no definition of intelligence that does not depend on how it relates to human intelligence. Indeed, in this article we calculate the value of IQ without being related to human intelligence, but to say if a program is AI, we have to say what the minimum for the IQ is. For this minimum, we chose the number 0.7. This number is arbitrarily chosen and we will change it if this level turns out to be much lower or much higher than the IQ of the human. That is, in our definition human intellect is also used, but this is only for comparison and we use it only to determine one special constant.

Yet another question McCarthy asks is: “Can we ask a yes or no question? Is this machine intelligent?” The answer is “no” and we fully agree because we do not known what the minimum for the IQ is.

However, we will not agree with McCarthy's answer to his next question. He asks: “Do computer programs have IQs?” And he answers with “no”. In this article, as in [3], we’ve showed that IQ can be defined for programs. With his answer McCarthy probably wanted to say that IQ tests for people are not suitable for computer programs. The test we offer is not for people but for programs.

In some articles (for example, in [9]), the question is how to create a program that can solve IQ tests designed for humans. In our article, the issue we are dealing with is the opposite one. Here we create IQ tests designed for programs (for strategies). The tests we will offer will not be suitable for humans, although it is possible for a human to learn to solve them after some training. The trained human will note down what has happened and will analyze to find dependencies. The untrained human will not note down and will not be able to notice the dependencies unless they are presented in visual form or in other way which is convenient for perceiving by a human.

It is very difficult to think of a human as a strategy for the following reasons. First, humans are not deterministic, that is, they do not implement a deterministic strategy. (A human can be seen as a not deterministic strategy or as a set of strategies from which one is randomly chosen.) Secondly, it is unclear how much time we have given the human to make a move. Third, it is unclear how seriously the human will approach the task (if he approaches more seriously, he will get a better result). Fourthly, humans are always trained and never start from scratch. Even a newborn baby has gone through some training in the mother's womb. Therefore, when a human implements a strategy, the outcome largely depends on his education, training, experience.

In [10], Detterman threatens to “develop a unique battery of intelligence tests” that will be able to measure the IQ of computer programs. In this article, as in [3], we do not threaten, but we are creating such a test.

It is a bit confusing that Detterman uses “computer” when he means “the system comprising of a computer and a program”. It is better to call this system a program because when we know the program, it's not very important which computer we'll run it on because the difference between two computers is only in their speed. Conversely, if we run two different programs on one computer, the difference in their behaviour will be enormous.

Detterman intends to test computer programs by using IQ tests for people. That is, he, just like Turing, does not make a distinction between intellect and educated intellect. Therefore, Detterman's test will not provide time to learn, but will assume that the computer program that is being tested has been pre-trained.

Detterman relies on the fact that computers are better than people in finding factual information. This is an ability of computers that is not directly related to the intellect. Similarly, computers are very powerful in arithmetic operations, but that does not make them smart.

There is one thing in which we agree with Detterman. He notes that with hoc algorithms many tasks can be solved, but the real intellect must be able to find the solution on its own.

In [11], the authors set the ambitious task of developing an IQ test that is appropriate for both AI and humans, and for programs like Siri and AlphaGo that are not AI. We can not compare AI with programs that are not AI because the first is a program that can be trained for a random task and the second is a program written for a specific task. For example, how do I compare a chess program with AI? The only thing a program designed to play chess can do is to play chess while AI can do everything although not immediately but after being trained. That is, the only way to compare these two programs is to let them play chess, and the chess program will have an advantage because AI will waste time learning, while its opponent would not need to learn how to play chess because it knows how to do it. If we compare the chess program with AI which is trained to play chess then the first program would still have some advantage over AI, just like the specialized hardware (i.e., hardware made specially designed for a particular task) takes precedence over a computer program running on a computer. That is, the idea of ​​comparing AI with programs that are not AI is not good.

The authors of [11] refer to concepts such as: abilities to acquire, master, create, and feedback knowledge. It is like explaining a term whose meaning we do not know by means of other terms whose meaning we do not know.

[12] discusses very comprehensively and competently how AI's IQ is measured. Also in [12], a very good overview of the different works devoted to this topic has been made. One minor disadvantage of [12] is that there is some controversy there. On the one hand, the article says “IQ tests are not for machines yet”. On the other hand, in earlier articles by Orallo [13, 14] a formal definition of AI based on the IQ test is given. It seems like Orallo is taking a step back and relinquishes the previous results. Another contradiction in [12] is that, on the one hand, it says “human IQ tests are not for machines”. This is something we fully agree with, as we agree with the arguments that accompany this statement. On the other hand, in the same article, the authors say they agree with Detterman that “there is a better alternative: test computers on human intelligence tests”.

In [12], as well as in [11], a universal IQ is sought, which is applicable to all programs and even to humans. Here we differ from the authors of [11, 12]. We have already explained why it is not a good idea to compare AI with programs that are not AI. We also explained why it is not a good idea to use the same tests for AI and for humans.

Article [13] is of significant importance because this is the first article that talks about a formal definition of AI, and this is also the first article introducing the IQ test for AI. Indeed in [13] this test is called C-test, but it is explicitly said that it is an IQ test for AI. We have to apologize for omitting to quote [13] in [3]. This is an omission that we are now correcting.

Despite the seriousness and comprehensiveness of [13], there are some inaccuracies that we have to mark. The fact that we pay attention to some omissions and inaccuracies in [13] does not in any way mean that we underestimate the significance of this article. There are no perfect articles, and inaccuracies can be found in any article. Usually the first article that appears in a new area is slightly confused and unclear. Normally, in later articles, things get clearer and more precise.

The most serious inaccuracy of [13] is that it does not define AI but something else. We will call that another thing an “observer”. We could say that an observer is a program that has only input and no output, but that would be too restrictive. That is why we will say that an observer is a program whose output does not affect the state of the world but the output can influence the reward that the program will receive.

An example of an observer is when we play on the stock market with a virtual wallet. We do not influence stock prices because we do not play with real money. (Even if we played with real money, it can still be assumed that our actions do not affect the stock exchange, because when playing with small amounts our influence is negligible.) When playing with a virtual wallet, at every step we change our investment portfolio and after each step the value of the portfolio changes depending on the change in stock prices. The reward we receive will be our virtual profit or loss.

The fact that the program defined in [13] can not influence the world is substantial problem, because as people say: "You have to touch to learn". There are other proverbs that say that we can not learn by watching only. By depriving AI of the opportunity to experiment, we are seriously restricting it.

In [5] it is noted that there are two problems that AI needs to solve. The first is to understand the world (to build a model of the world), and the second problem is to plan its actions based on the chosen model. That is, the “observer” solves only the first problem without solving the latter.

In [13] the definition is limited to “observers”, but to give the term “observer” a definition is a task sufficiently meaningful by itself because it is half of the things AI needs to do. Unfortunately, this task is not fully solved because the observer defined in [13] is a little more special. It either understands the world wholly or not at all. That is, it is observer who works on the principle “all or nothing”.

[13] suggests random strings, which can be continued in only one possible way. That is, it is supposed that there is a single simple dependence and this dependence will either be found or will not be found. This approach is too restrictive because it implies only observers who understand the world completely. This is only possible in very simple worlds. Any more complex world can not be fully understood and that’s why it has to be understood only partially.

The authors of [13] are making serious efforts to make the dependencies exceptions-free. The definition of exception-free given in [13] is very interesting. However, we would not go that way because if dependencies included exceptions, that would be a way to allow a partial understanding of the world. Seeking a single exception-free dependence to describe everything is the reason why the observer defined in [13] relies on the “all or nothing” principle.

We have a few other minor recommendations for [13].

We give some time to AI to find dependence. The question is whether we will give this time at once or we will distribute it in many steps. In general, AI is searching for dependencies throughout its entire live. That is, in many steps. In [13], dependency is sought in just one step. In our article, we assume that in life the steps are approx. one million (a thousand games with a thousand steps each one). This means that we must give the program, which is defined in [13], a million times longer time. Our recommendation is for dependences to be sought after each step, not only after the last one.

In [13] we do not like also the fact that the program that generates the test is not working due to combinatorial explosion. This is the program called “The Generator”. That is, [13] does not present a test, but only shows that such a test exists theoretically.

Yet another problem is that two restrictions have been imposed. When the “observer” makes a prediction, it must bet all on single result only and always bet the same amount. It would be better to have the freedom to bet on more than one result, and to decide what amount to bet. When we are more confident we bet more, and when we hesitate, we bet less or we pass. These two limitations do not change things fundamentally, because the smart will prove to be smart even with these limitations, but that blurs the picture. If there were no such restrictions, the difference between the IQ of the clever and the stupid would be greater.

We also do not like the fact that the more complex tasks in the [13] have a greater weight than the simpler ones, when it should be the opposite. (There is a coefficient e, which is assumed to be non-negative and would be better to be negative.) It is true that when we make a test we give more points to the more difficult tasks, but that's because we suppose that students will lose more time on the more difficult task. This is not the case here. Here, for every task we give the same time. Therefore, if a simple task can not be solved, it is a serious problem and this should be reflected in the score. Moreover, sometimes we will guess the solution of a difficult problem randomly, so those must be given less weight, otherwise they will result in undeserved rise in the IQ.

We have the concepts of global and local IQ (these two concepts are defined in our article). Global IQ is something accurate that can not be accurately calculated (because of a combinatorial explosion). Local IQ is not something accurate because it depends on the choice of the specific tasks in the test, but for specific tasks it can be easily and accurately calculated. What is defined in [13] is local IQ, not global IQ. However, let's not forget that the local IQ approaches the global IQ, but [13] says nothing about the “nerd” program, which is the main problem of local IQ.

How are we to correct the definition given in [13] in order to get a definition of the observer that does not follow the principle “all or nothing”?

Instead of taking a special k-comprehensible sequence, we will take a totally random program and the sequence that this random program generates. Instead of predicting the next symbol a single time, we will predict it at every step. We will not bet everything on a single prediction, but we will allow the bet to be divided between several predictions. We will also allow the bet to be different. (For example, we will assume that the sum of bets for the last five steps is limited to a given constant, but that we have the freedom to choose when to bet.) The reward to a sequence will be the sum of the rewards of all steps. Local IQ will be the arithmetic mean of the rewards to the sequences we have included in the test.

In this way, we will not want the “observer” to understand the world completely because it can grasp some dependencies and thus, through a partial understanding of the world, get a relatively high IQ.

A problem with [13] is that the program it defines is actually the program [1]. This is a simple program that predicts the next symbol on the basis of the simplest dependency that can generate the beginning of the sequence.

I even dare go a bit further and say: No program satisfying the definition given in [13] is better than [1]. That none is better as a result is clear, but I say that even as a matter of efficiency none is better because the definition in [13] does not give us any opportunities to play tricks and discover dependencies partially (step by step), leaving us the only option to foolishly go through all possible dependencies.

Interestingly, in his more recent articles Orallo (as in [14]) has obviously understood the main omission made in [13], and what he defines there is no longer an “observer” but a program that can influence the world. Unfortunately this program is not AI again. [14] defines a program that plays a game which consists in going round a labyrinth (graph) by chasing something good and running away from something bad. To play this game one definitely needs intelligence, but the program playing this game is not AI just like the program playing chess is not AI.

Again in [14] the authors speak of reinforcement learning. That is, it is clear that they know very well what the general form of AI is. Why, then, do they not use this general form, but restrict themselves to the worlds of one specific game? I think the reason is that they are trying to avoid the worlds where fatal errors are possible. The problem with fatal errors is mentioned even in [2], but fatal errors are not really a problem. We humans also live in a world with fatal errors, but that does not prevent us showing who does better and who does worse. Well yes, it's a problem for people because we live only one life, but the IQ test consists of many tasks, each of which is a separate life. Even if fatal errors occur in several lives, this will not significantly affect the average score. Even with humans, life is not just one. From the point of view of the individual, life is one, but from the point of view of evolution, lives are many. Some of our heirs will die because of fatal mistakes, but others will survive. Thus the average score of our successors will not be significantly affected by the fact that some of them have made fatal errors.

It is true that in this article, as in [3], we also do not use a random world, but we only take computable worlds, but this constraint is not essential, because every time-limited world is computable, and we can easily assume that all worlds are limited in time. That is, by limiting ourselves to the computable worlds, we are not limited at all, but only give more weight to the worlds that are simpler (according to Kolmogorov complexity).

In [14] there is one more thing we do not agree with. This is something called the “discount-rate factor”. Of course, this is not something conceived by the authors of [14], but is something widespread among people working in the field of reinforcement learning. The idea of ​​the “discount-rate factor” is that the past is more important than the future. Life is potentially endless, and to evaluate an endless life, we have to devalue the future. However, the past being more important than the future is not a good idea. It would be better to do the opposite, because in the past we have not yet been trained, and in the future we have already been trained. With humans, we do not count how many times a person wet his bed while he was a baby. Instead, we see what achievements the person has attained in his adult age. Therefore, the approach we have adopted in [3] and this article is that there is no “discount-rate factor” but life is limited. In other words, the approach here and in [3] is that the discount-rate factor to be equal to one until a given moment in time (the end of life) and to be zero from that moment on.





Formulation of the problem

Let us have a Device which lives in a certain World. At each step the Device produces n symbols (this is the Action) and then receives m symbols from the outer world (in our terminology the first one will be ‘Reward’ and the remaining m-1 symbols will be ‘Observation’). The Reward can have five possible values: {nothing, victory, loss, draw, incorrect_move}.

We will use the words ‘move’ and ‘action’ interchangeably. If we perceive life as a game it is more appropriate to say move rather than action. Likewise, we will use the words ‘history’ and ‘life’ as synonyms.

Let one step of the Device be a triple consisting of <Action, Reward, Observation>. The ‘life’ of the Device will be a sequence of steps resulting from the interaction of the Device with some World.

‘Real life’ will be life without incorrect moves. Therefore, all <Action, Reward, Observation>. triples where the Reward value is ‘incorrect_move must be removed from the life and what remains is the real life.

A ‘moment’ will be a sequence of steps where the last step before the sequence and the last step of the sequence are correct and all steps in between are incorrect. That is, in life there may be more steps than moments, but in real life the number of steps is equal to the number of moments.

We will assume that the behavior of the Device and of the World is deterministic. In other words, we will assume that if we know which is the Device and which is the World then we know which is the history.

The behavior of the Device can be presented as a strategy, i.e. as a function which defines the next move of the Device for each start of life. Likewise, the World’s behavior can be presented as a strategy which for each start of life and for each Action of the Device delivers the Reward and the Observation which the Device will get at the next step. It should be noted that the World’s strategy does not depend on incorrect moves. Hence, we can imagine the strategy of the World as a function of real life. Conversely, the strategy of the Device will depend on incorrect moves (these moves will provide additional information for the Device to use).

The Device and the World can be thought as two strategies playing against one another, but that would not be accurate, because the Device has an objective and the World has not. Therefore, the World does not play against the Device. We assume that the World is simply there and does not care whether the Device feels good or bad.

Presenting both the World and the Device as strategies is not a very good idea, because a strategy remembers everything (i.e. depends on entire life until the moment). It makes sense to assume that the Device may not necessarily remember everything. A similar statement can be made in respect of the World. There may be a world the entire past of which (previous life until the current moment) can be reconstructed out of its internal state. It may be, however, that the world does not remember everything, which leaves us that two different histories can lead to the same internal state of the world. This is the reason why, we will present the Device and the World as functions.

Let us have two sets, Q and S. These will be the sets of the internal states of the Device and of the World. These sets will be finite or countable, at the most. Let q0 and s0 be the initial states of the Device and of the World. We will assume that these states are fixed, because life will depend on the initial states we start from, but we want life to depend only on the Device and on the World.

The Device and the World will be the following functions:

Device: Q´Rewards´ Observations´2 Actions ® Actions´Q
World: S´Actions ® Rewards´Observations´S

For each Internal State of the Device, Reward, Observation and Set of Moves which are confirmed as incorrect at the moment, the Device function will return an Action and a new State of the Device. We will assume that the Device never returns an Action which is confirmed as incorrect at the moment.

The Internal State of the Device will reflect everything the Device has remembered. What can it have remembered? It can remember everything that has happened until the moment plus its last Action. That is why our expression is Actions´Q, rather than Q´Actions. We wish to stress that the Internal State of the Device can remember the last Action.

For each Internal State of the World and Action, the World function will return a Reward, Observation and a new Internal State of the World. It makes sense to assume that there are moments (Internal States of the World) in which a specific action is impossible or incorrect. It is natural to assume, therefore, that the World function is a partial one. We will supplement the definition of the function so as to accommodate those moments as well, and in this way will extend the function to a total one. In these moments Reward will equal incorrect_move, the Observation value will be irrelevant and the new internal state will be the same as the previous one although this is irrelevant, too.

The Internal State of the World will reflect what the World has remembered. What can it have remembered? It can remember everything that has happened until the moment plus the last Reward and Observation. That is why our expression is Rewards´Observations´S, rather than S´Rewards´Observations. We wish to stress that the new Internal State can remember the last Reward and Observation.

In [2] and [3] we defined the new <Reward, Observation> as a function of the new internal state. So we assumed that they must be remembered, but now we dispense of this requirement. Let us take a world in which we play chess. The chess game ends and the new internal state of the world is a chessboard with the initial lineup. In this case we do not have to remember who won the last game. Such requirement would be one unnecessary care.

This is how the life of the Device looks like:
<a1, r1, o1>, <a2, r2, o2>, …, <at-1, rt-1, ot-1>

Let us see how the Device and the World function define life.

<ai+1, qi+1>= Device(qi-j, ri-j, oi-j, incorrect_actionsi)
<ri+1, oi+1, si+1>=World(si-j, ai+1)

In this case, i-j is the last correct step before i+1. The incorrect_actionsi set contains the confirmed incorrect actions at this moment. The set has j elements. Therefore, incorrect_actionsi ={ai-j+1, …, ai}. The incorrect_actions0 set will be an empty set, because there will not be any confirmed incorrect actions in the first moment before the first step is made.

In order to define life, we must fix the first Reward and the first Observation (r0, o0). We do not wish life to depend on the first Reward and the first Observation, so decide that the value of all symbols of these two vectors is nothing. This is a sensible decision, because it is quite natural that in the first moment we do not get any reward and do not see anything significant (i.e. what we see in the first moment is the zero step). We will not define the zero action a0, because we do not use it.

Now that we have fixed (q0, s0, r0, o0, incorrect_actions0) we can build life up to step t and this life will depend only on the functions Device and World.
<a1, r1, o1>, <a2, r2, o2>, …, <at-1, rt-1, ot-1>

In addition to life, we will also construct the series of internal states of the Device and of the World, as well as the incorrect_actionsi series of confirmed incorrect moves at the relevant moment. Let us note that at each given moment there may be many incorrect actions, but the confirmed ones are only those which we have tried and have thus verified that they are indeed incorrect at that moment.

We will assume that the Device function always returns a move which is not confirmed as incorrect. The opposite will lead to cycling. What shall we do if all moves turn out to be confirmed incorrect moves? (I.e. if incorrect_actionsi coincides with the entire Actions set.) In this case we will assume that the Device function is not defined. This is the case when we end up in a blind alley and there are no possible next moves.

Note: The definitions of Device as a function and as a strategy are almost identical save that if we consider Device as a strategy, the order in which we tried the incorrect moves may matter at some moments, while in the function definition it would not matter. This difference can be resolved in two ways. The first one: when defining a function, instead of the set of confirmed incorrect moves we take the list of these moves. The second one is to limit our exercise only to those strategies which are insensitive to the order in which we tried the incorrect moves. In this study it would not matter what happens if the strategy tries the incorrect moves in another order, because we assume the strategy to be deterministic and the order in which it tries the incorrect moves is fixed.

Note: We assume here that when we try to play an incorrect move nothing happens and all we get is information that the move has been incorrect. We can let the Device check whether a move is correct or not even without necessarily playing that move (as we have done in previous studies). In this case we need to modify the formulation of the problem and add an additional reward correct_move. The Device function will need one more argument containing the confirmed correct moves. When we try a confirmed correct move we will assume that we shall play this move. Where a move is not in the set of confirmed correct moves, then we assume that we only try it. The World function will have another Boolean parameter to indicate whether the move is actually played or just tried. In the latter case, the function will return either correct_move or incorrect_move rewards. Then the move will not be played but will only be added to the next set of confirmed correct or confirmed incorrect moves.

A game will be a stretch of life located between two consecutive final rewards. In our terminology, ‘final rewards’ stands for the values {victory, loss, draw}. We will assume that the length of each game is limited to 1000 moves (i.e. 1000 moments, while the number of steps may be greater because of incorrect moves).

We will define which strategy is an AI strategy and our definition will depend on a number of parameters. We will fix the values of the majority of these parameters to one thousand, because 1000 is a nice round number. Another good round number is one million. Replacing one thousand with one million would produce another AI definition, which will not be much different from the one we are dealing with.


Parameters

Number of Action symbols
n
Number of Observation symbols
m
Number of symbols possible for each Action symbol
k1, …, kn,
ki ≥ 2.
Number of symbols possible for each Reward and Observation symbol
kn+1, …, kn+m,
ki ≥ 2, kn+1=5.
Tape symbols count
Global tapes count
7 (from 3 to 9)
Internal states count
1000
Test worlds count
1000
Maximum number of games per life
1000
Maximum number of moves per game
1000
Maximum number of Turing machine steps per one life step
1000
Probability by means of which the machine is generated
= 10%
Minimum IQ required for a strategy to be recognized as AI
0.7 = 70%

The first four rows of the table above provide the parameters which describe the AI input and output. They tell us what the format of the sought AI is. Thus, we cannot vary these parameters randomly. The next eight parameters influence the choice of worlds selected for the test and, therefore, influence the IQ we get, and thus the AI definition as such. The last parameter also influences the definition. This means that if we varied the last nine parameters we would also vary the AI definition.

The table does not include other parameters which also influence the AI definition. For example, it does not say which pseudorandom numbers generator we will use in order to select the test worlds. Thankfully this parameter’s bearing on the definition is insignificant.

The possible symbols for the i-th Action symbol will range from 0 to ki-1. Likewise, the possible symbols for the i-th Observation symbol will range from 0 to k n+1+i-1. Let us call the 0 symbol ‘nothing’. The first Observation symbol will be the Reward. When it comes to the Reward, we will name the symbols 1, 2, 3 as ‘victory’, ‘loss’, ‘draw’, and these will be the final rewards. The reward 4 (incorrect move) will not be returned by the Turing machine as a result of the invocation of the command q1. This reward will be returned only when Turing goes cycling (makes more than 1000 steps without reaching a final state) or crashes (e.g. invokes a return command when the stack is empty).

The tape symbols will be as many as needed for coding the Action and the Observation. I.e. the maximum ki for i from 1 to n+m. To that we will add another 10 utility symbols the first of which will be empty symbol l.


How will the test work?

We will select 1000 worlds for the test. In each of these 1000 worlds, the candidate will live one life consisting of not more than 1000 games. Finally we will calculate the number of victories, losses and draws. This will give us an IQ, which is an arithmetic mean where victory is 1, loss is 0 and draw is 1/2.

We will pick the worlds randomly, but we want the selected worlds to be fixed, so we will use pseudorandom selection by setting the pseudorandom generator to 1 before starting the selection process. Thus we will always use the same worlds in the test.

In many of the generated worlds we will win every time or we will loss every time (doesn’t matter what we do). It is meaningless to include such worlds in the test so we will discard all of them from test. Thus we will be left with 1000 meaningful worlds.


What is a World?

In newspapers one can come across problems such as ‘Which is the next number in the series?’ If all possible series are equally probable, the next number may be any one. When looking for the next number in a series we assume that simpler series are more probable than more complex series. We therefore use the principle known as ‘Occam’s razor’.

The situation with worlds is similar. If we perceive the world as a strategy and all strategies are equally probable, then there is no way we can tell the future and a basis for preferring one move over another is lacking. We will therefore apply Occam’s razor to the worlds and will assume that more simple worlds are more probable. What makes one world simpler than another world? We will use the Kolmogorov complexity. That said, if the world is a strategy, the more simple strategy is the one which is generated by a Turing machine with less states.

We have limited the life so all strategies are finite. Therefore, all strategies are computable. So we will assume that a world is some Turing machine which calculates some strategy.





Which will be the set of all worlds?

The set will be limited to Turing machines with 1000 states. This set includes machines with less than 1000 states, because each machine can be filled up with unreachable states. Turing machines which use more than 1000 states (and cannot be simplified) will be excluded from the set. We will consider these worlds as too complex and will accordingly exclude them from the definition.

The result is a huge set of strategies (worlds). The more simple strategies here will bear more weight (will be more probable), because there are generated by more Turing machines (from the set).

Furthermore, we will assign some weight to each Turing machine. Hence we will prefer some machines over others. For example, if a machine tends to use more states with lower numbers, we will prefer it to the one which uses more states with higher numbers.

There are two reasons why we assign different weights to the different Turing machines. The first one is that we give more weight to more simple machines (e.g. the ones with less reachable states are simpler). The second reason is that we wish to randomly generate a machine which works, and this is very difficult. The machines which have a greater chance of being working ones will have more weight, therefore we increase the probability of selecting these machines and accordingly our chances of hitting a working machine.

The weight of a machine is equal to the probability of this machine to be selected by us. We will not calculate this probability. That would be a rather difficult calculation. We simply select a machine randomly and by this selection we induce probability as a parameter of the formula. That is, the probability will not be calculated when the Local IQ is calculated. When calculate the Global IQ, we should consider all Turing machines in order to calculate the success rate of the Device with any of these machines and the probability that this very machine is selected. We have to multiply these numbers and sum up the values for all machines. This is an impossible calculation because of combinatorial explosion. The fact that we complicate the calculation by adding the calculation of probabilities is not a problem. We do not change anything in this way. While the Global IQ remains theoretically computable, in practice it is still uncomputable, even more uncomputable than before.


How to calculate the IQ of a particular computer program?

We may say that the IQ is the arithmetic mean of success rates of all worlds. (Note that the worlds are not equally probable and we need to multiply the success rate by the probability (weight) of each world.)

We will call the so obtained IQ a Global IQ. The Global IQ definition is very nice save that Global IQ cannot be calculated. To be precise, it can be calculated in theory, but not in practice because of the huge number of worlds which we have assumed to be possible.

Nevertheless, we can still calculate the Global IQ by approximation using statistical methods. We will select randomly 1000 worlds and will calculate the arithmetic mean for these worlds. The result obtained would be close to the Global IQ.

The problem with this approach is that different selections of test worlds will yield different Global IQ approximations. What we need is a program which awards to the candidate the IQ this candidate deserves, withal it must be a specific value rather than an approximation of something else. Hence we will fix the randomly selected 1000 worlds and will say that the Local IQ is the average success rate across these 1000 worlds. (In this case different worlds will not have different weights, because the weight is already accounted for in the selection of test worlds. The more weighty ones are more likely to be selected.)

The idea of fixing the randomly selected worlds is tantamount to giving the same problems to all candidate students.

The Local IQ is an easily computable function and describes well our understanding of what IQ is. There is just one problem. There is one program which we will call a ‘crammer’. This program is designed specifically for the 1000 test worlds and its Local IQ is very high, but its Global IQ is low. How should we resolve this issue? We will use the Local IQ in order to find the AI. When we hit a program with a very high Local IQ and suspect that this program is a crammer, we will give it additional problems, so that we calculate a second local IQ. This means that we will take the next 1000 random worlds and derive another arithmetic mean from these worlds. We can go on with a third and fourth Local IQ.


How does Turing machine make a move?

We present the world as a Turing machine. Thus, our machine must take Actions as inputs and deliver Observations as outputs.

The first m+1 states of the machine will be special. The qm+1 state will be the initial and the final state of the machine. In states q1 to qm we will use in order to output the Observation symbols.

When the machine makes its first move, all tapes will be empty (i.e. they will be covered with the l symbol). The first running tape will be No 3 (Nos. 0, 1 and 2 are reserved for utility purposes).

Turing machine will make a move by starting from the initial state qm+1 and finishing in the same state (which is also the final state). In the beginning of the move, a word of n symbols (the Action word) will be recorded on the current tape under the head of the machine (anything previously written in the first n symbols on the tape before the recording of the word will be deleted).

At every step it will be observed if the states q1 to qm are called up. When these states are called up, the Observation symbols will be outputted. If the qi state is called several times within one move, only the first call will be considered. If it is not called up at all, the i-th Observation symbol will be nothing. If it is called up at least once, i-th Observation symbol will be the value of the ‘head memory’ at the moment following the first call on the qi state. If the i-th Observation letter is too big (equals or exceeds the kn+i), the machine will crash in a cycling-like fashion.




Incorrect moves

When the Turing machine fails to make a move because it goes cycling or crashes for some other reason, we will deem that the input Action entered at the start of the move is incorrect or impossible. In this case we go back and try to enter another Action. More precisely, it is not us who go back, instead we will turn back the world (the Turing machine). We give the Device an incorrect _move reward and take the next move the Device chooses to give us. We continue with this move as if the Device has played it instead of the incorrect move. (If the Device plays the same incorrect move, we disqualify it because it cannot try the same move twice in a single moment.)

Taking the Turing machine back is a perfectly natural operation. All we need is to memorize the total state of the machine before the start of the move. If we reconstruct this total state, we can enter another Action and continue was if it were the first action we ever tried.

Another approach was applied in [3], where it was assumed that all moves are correct and the cycling problem was resolved by aborting the execution of the program, awarding a utility draw and restarting the program from its initial state. With this type of restart the tape remains in the state it was at the time of abortion. This is very poor practice. You will know that to turn down your PC you should enter the ‘Shut Down’ command. The other option is to pull the plug off the socket, but this will leave the hard disk in the state it was when the plug was pulled off. This treatment would make your PC behave in a bizarre and illogical manner. The same can be said when a Turing machine is shut down randomly and then restarted from its initial state. We want the world to be as logical as possible and take care to avoid these abortions.

Now that we have opened the gate for incorrect moves, we should know what to do when all moves are incorrect. Let us assume that we have about 100 possible Actions. We try them all and all of them prove to be incorrect. So we will say that we have ended in a blind alley with no way out.

If life is the sequence of 1000 games, then life ends with a natural death after 1000 games or with a sudden death (blind alley). How to reward a life that ends prematurely? We can reward only the games played until death. Then our AI strategy will prefer to commit a suicide (enter a blind alley) as soon as it realizes that things in the current life have gone wrong and only losses lie ahead.

We do not want suicidal AI strategies and will therefore opt for another solution. When a strategy is caught in a blind alley, we shall say that all remaining games up to 1000 are losses. This will provide assurance that the strategy will not go in blind alley on its own will, but will keep fighting to the end.

Will the strategy realize that it is entering a blind alley? One cannot learn this by trial and error because you fall in a blind alley just once. But, if the strategy is very smart, it may be able to predict that some blind alley is forthcoming. For example, if the number of possible moves is decreasing, this is not a good sign, because in the end of the day one may run out of possible moves and enter in a blind alley. People can be another example. Let us have someone who has never died. He or she has no experience of their own but can still predict a few potentially fatal situations.

We penalize beating around the bush

We said that a game cannot be longer than 1000 moves. What shall we do if a game continues for more than 1000 moves? We shall then award a utility draw. Note than by doing so we do not interfere in the workings of the Turing machine as it continues to play the same game. The intervention concerns only the strategy, because it will get a draw reward when the world (Turing machine) has awarded nothing. The fact that we do not abort the machine guarantees that the machine will maintain its logical behavior.

If another 1000 moves are played without a final reward, we award a utility loss. That is, we penalize strategies which kick the can down the road. We want an AI strategy which aims to close the game quickly and start the next one.

By penalizing early death and procrastination we vary the IQ of the random strategy. If we play heads or tails, the expected IQ is 1/2. To earn a higher IQ one must purposefully aim to win. For a lower IQ, one must purposefully aim to lose. By declaring all post-death games lost, we reduce the IQs of all strategies. Similarly, the inclusion of utility losses will lead to a likewise reduction. This solution means that the IQ of the random strategy will be less than 1/2.

We will be able to calculate the exact IQ value of a random strategy once we write the program which calculates the Local IQ. Naturally, a random strategy is non-deterministic meaning that we should test it a few times and take the mean value. Hence, the IQ of the random strategy will be an approximate value. Only deterministic strategies have exact Local and Global IQ values.


More logical and more efficient Turing machine

As announced already, we will redefine the Turing machine in order to make it more logical and more efficient. To this end, we will make Turing a multi-tape machine and will enable it call subprograms.

Why would such a machine deliver a more logical world?

First, it is the multiple tapes of the machine. It is legitimate to present the state of the world as a Cartesian product of many parameters which are in weak correlation with one another. That is why a multi-tape Turing machine produces a more logical model of the world than the single-tape machine.

Second, the machine will have subprograms which can be called up from many points. This is more logical than calling a different subprogram each time. When no stack is in place, we have to remember where we should go back after the subprogram is executed. To this end, each subprogram should be called up from one point only (otherwise it will not know where to go back).

When we invoke a subprogram we give it a clean tape so it can write its intermediate results. In the opposite case the subprogram will have to use for this one of the common tapes and this will largely frustrate its logic due to the weird interactions that will occur among different calls of the subprogram.

Why would this machine make less steps and have less internal states?

Higher efficiency means less steps and, more importantly, less internal states. It is important that the steps are not too many, because a machine making more than 1000 steps per move will be presumed to be in a cycling situation and will be stopped. It is also important that internal states are not too many, because we have limited our set to machines having less than 1000 states. Hence our machine should preferably use less states.

Having multiple tapes in the machine means there will be less steps, because a single tape will force the head make a lot of movements in order to write intermediate results. It would be easier to write these results on another tape.

More significantly, we will reduce the number of internal states of the machine. A classical Turing machine uses a huge number of internal states (it memorizes everything that needs to be memorized in its internal state). For example, when a subprogram has been called up we must remember where the subprogram was called from (where it must return). If we want to move a symbol from one place to another we must remember which symbol we have pulled up.

Thus, we complicate the Turing machine so that, in addition to its internal state, it should also remember which is the running tape, the stack index (for subprograms) and a ‘head memory’ symbol.


A stacked Turing machine

How would the program of this machine look like? It will be a table of 1000 x MaxSymbols, where 1000 are the possible commands and MaxSymbols are the possible symbols. In each field of the table there will be five commands.

The first command is ‘Write on tape’
MaxSymbols+2 possible values:
(unchanged, previous value of the head memory, concrete symbol)

The second command is ‘Change the head memory’
MaxSymbols+2 possible values:
(unchanged, previous value of the symbol on tape, concrete symbol)

The third command is ‘Move head’
Three possible values:
(left, right, stay there)

The fourth command is ‘Subprogram’
There are two fields:
‘State’, the value of which is in the interval [0, 1000] (where 0 is the command NULL).
‘New current tape’, the value of which is in the interval [0, 9] (where 0 is the previous current tape, 1 is the current tape of the parent program, 2 is the temporary tape created especially for this invocation of the subprogram and 3—9 are the global tapes).

The fifth command is ‘Next state’
The value is in the interval [0, 1000] (where 0 is the command return).

When a subprogram is called up, what do we write in the stack? Three things: where shall we go back after return (the fifth command), which is the previous current tape (so that we recover it after return) and which temporary tape is created especially for this invocation of the subprogram. The new temporary tape should also be written somewhere. Let it not be in the stack, but somewhere else. When the return command is executed, the corresponding temporary tape will be destroyed.


Populating the table

In order to create a random Turing machine, we must populate 1000 x MaxSymbols with random commands. Before we do that let us say how a random command is selected. We must generate 6 numbers (the fourth command has two fields). These numbers may be equally probable, but we prefer smaller numbers to be more probable than larger numbers. Why would we prefer so? Because if all states are equally probable, the program will be stretched over multiple different states, while we wish certain states to be used more frequently than others. Likewise, we want some tapes to be used more often than others. This also applies to utility symbols (but does not apply to non-utility ones).

How shall we select a number from 0 to k with a decreasing probability? Let us toss a coin and if it is heads we select with a probability of 1/2 the number 0, if it is tails we toss again and if we get heads we select with a probability of 1/2 the number 1 and so forth. If do not get any heads all the way to k, we restart from 0.

A probability of 1/2 produces a very steep decrease of the probability of the next number. That is why we will use a probability of 1/10 to select all the 6 numbers. What we actually use is the geometrical distribution.

Note: Only the number of the subprogram will be assigned differently. In this case 0 will be taken with a probability of 9/10 instead of 1/10. (Thereafter we continue with 1/10.) This is so because we do not want subprograms to be invoked too often and the stack to be populated redundantly. In this way the probability of the return command will be equal to the probability of invoking a subprogram.

Now that we have explained the generation of commands (one box in the table), let us explain the generation of one column consisting of MaxSymbols boxes. We will imagine the command of this machine as a switch with MaxSymbols cases. When we write program and use a switch, we describe only some of the cases rather than all cases. The remaining cases are described as default (i.e. all other cases are the same). A program will be more logical if the same command applies to the majority of the cases. Therefore, we will select randomly how many different commands will exist in the column. We will use the decreasing probability procedure as explained above. Once we know how many different positions are there, we select randomly which these positions will be (again, smaller numbers will be more probable). Finally, we populate the positions that need to be different with different commands, and will put the same command in all other positions.

So we have an algorithm for populating one column and can populate 1000 columns. In the end of the process we have the first random Turing machine. This however is a cumbersome process, so we derive the second machine from the first one just by changing the first m+1 states (which are special ones) and another 10 random states. This change is sufficient because the vast majority of the states are not used and by changing the special states we start using other states. Thus, the new Turing machine will be substantially different in terms of the states it uses even though the two machines are almost identical in terms of their unreachable states.


Discarding the slag

So we have a fast and simple procedure to generate 1000 test worlds. The problem however is that most of these worlds are useless. Across 1000 worlds there may be as little as 2 or 3 interesting ones. Therefore, we will discard all useless worlds and do our test with 1000 interesting worlds.

Example for a useless world is if the very first move leads to a blind alley.

We will verify that a world is interesting by letting the random strategy live one life in that world. In this life, we do not want to see the strategy caught in a blind alley. We want at least one victory and at least one loss. We do not want more than 10 utility draws and utility losses. If all these conditions are met in this random life, we will deem that the world is interesting.

How to construct a test with 1000 interesting worlds? First, we initialize the pseudorandom numbers generator with the number 0. Then we generate randomly World Zero. Then we initialize the generator with 1 and apply a minor change to World Zero so as to generate World 1. If World 1 is interesting, we set the generator to 2 and generate World 2. If World 1 is useless we initialize the generator with 2, 3, 4, 5, etc. until we obtain from World Zero an interesting World 1. We keep going until we generate 1000 interesting worlds. We will not save them all, but will only save an array of 1000 numbers. These are values which we should use to initialize the generator in order to obtain a new interesting world from the previous interesting world.

Note: Please observe that we select different Turing machines with different probabilities. These different probabilities are the different weights of the different machines. We need this clarification, because we aim to provide an accurate definition of Global IQ. The definition is:


In this equation, P(TM | Interesting) is the conditional probability that the machine named ‘TM’ is selected if the world is interesting. Success(Strategy, TM) is the arithmetic mean calculated after the strategy named ‘Strategy’ has lived one life in the world defined by the machine named ‘TM’. The sum total is across all machines with 1000 states the worlds of which are interesting.

The above Global IQ practically cannot be calculated and it is the theoretical value which we try to approximate by means of the Local IQ.

The Local IQ therefore is:


Where TMi is i-th preselected test world (Turing machine).


The final definition

Definition: An AI is any strategy the Local IQ of which exceeds 0.7.

Here we selected the same value as we did in [3]. Both here and in [3] the value (0.7) is selected arbitrarily. Likewise, a corporation may announce that it is looking for a CEO and will be happy to employ anyone who solves 70% of the problems given in the test. The corporation may have to adjust this level later if the bar proves too low or too high.

Definition: An AI is any computer program if the strategy it plays in the first 1000 games is an AI strategy.


Analogy with the Grandmaster definition

We will provide another explanation of the AI definition by repeating the same construct, but this time we will define a chess playing program. We have already done so in [4], but as the present study revisits and updates the construct described in [3], here we will also revisit the construct in [4] and will reflect the relevant adjustments.

We will define a chess playing program as a program which plays like a grandmaster. If someone wants to be a grandmaster, he or she should earn an ELO rating (calculated by the ELO rating system) of at least 2500. The bad news is that the ELO rating calculation is based on his or her performance in playing against other people. To obtain an objective assessment of how good is the player, we will replace the other players with a finite set of deterministic computer programs. Then our chess player will play one game against each of these other players and his or her result will be the arithmetic mean of the results achieved in the individual games. In case a player halts (goes cycling) and does not make it until the end of game we will award a utility victory to the opponent. The same we will do if the player plays incorrect move. That is, a program which aspires to become a grandmaster must play correct moves and had better avoid cycling because in the opposite case we will penalize it with a utility loss. This applies both to the chess playing program and to computer programs in the finite set against which we assess the performance of our program.

Which will be the finite set of deterministic computer programs that used in the grandmaster test? We can take all programs that do not exceed a predefined length. Most of these will play randomly, will go cycling often and will make many incorrect moves. It would be reasonable to screen them and leave only the interesting ones (programs that play too mindlessly are a ballast which only makes the test more cumbersome). Interesting programs will be those that do not cycle, do not make incorrect moves and, on top of all, play relatively well.

When looking for interesting worlds to use in the AI test we used the brute-force search method. This method will cannot be used here because it is very unlikely to randomly hit a program which does not cycle and makes only correct moves. Hence, instead the set of all programs which do not exceed a certain length, we will take a specific set of programs whereby all programs are interesting (do not cycle, do not make incorrect moves and play relatively well).

Let us take a particular program, which calculates the next five moves and distinguishes between three types of positions: winning (victory within the next five moves), losing (loss within the next five moves) and undetermined (all other positions). Which move will this program play? It will pick randomly one of the winning positions. In the absence of a winning position, it will chose randomly one of the undetermined positions. If an undetermined position is also lacking, the program will go ahead randomly with a losing position.

What we described above is a non-deterministic program. If we reckon how many deterministic strategies this program can implement, they are far too many (but still finitely many, because the length of the game is limited). Each of these strategies is calculated by infinitely many programs, but we shall assume that for each strategy we have selected one program which calculates this strategy.

As a result, we obtained a huge set of programs and may be tempted to say that our ELO rating will be calculated on the basis of the games with all these programs. Unfortunately these programs are far too many and we cannot calculate the ELO in this way because of combinatorial explosion. Instead, let us select 1000 of these programs and calculate the ELO after 1000 games (one game played with each program). We will select these programs randomly, but will select them only once and will always calculate the ELO on the basis of the same test programs.

How can we make a deterministic program out of a non-deterministic one? That is easy, instead of picking a random move we pick a pseudorandom move. Before starting the game, we will initialize the random number generator with the number one (1). Thus we obtain one deterministic program. We need 1000 deterministic programs. We will initialize with the numbers from 1 to 1000 and will obtain 1000 different deterministic programs (among these 1000 there might be some identical programs, in particular where the random numbers generator is not as good as it should be). These will be the programs from which we will derive the ELO rating.

Let we say that a program will become a grandmaster if the so-calculated ELO is more than 90%. This is an arbitrary value picked by us. It may turn out that the value should be higher. We may even have to adjust the test worlds and ask them to calculate maybe the next 10 moves rather than 5 moves.

Then we stumble upon the crammer issue again. It is perfectly possible to learn by heart how to beat some of these 1000 programs. Remember these are deterministic programs and if we beat a deterministic program once we can beat it as many times as we want by replaying the same game.

A fairly good analogy emerges between the grandmaster and AI definitions. In the first case we refer to an ELO rating and in the latter case to an IQ rating. In the first case we play chess against 1000 opponents and in the latter case we live 1000 lives in 1000 worlds. The difference is that in the chess scenario we play one game against each opponent and in the IQ scenario we play one thousand games in each life. This is so because in the first case the rules of the game are fixed and it is expected that a grandmaster program knows the rules and knows how to play (rather than learning how to play while it plays). In the second case, the AI does not know the rules of life and needs one thousand games in order to discern these rules and learn how to live successfully.


Conclusion

In this study we described an exam (test) which enables us calculate the IQ of any program. More precisely, we specified the program which will conduct the test and tell us what the candidate’s IQ is. Given the deep granularity of our specification, we can now relax and ask some student to do the coding for us, perhaps as a course project.

This program will enable us do the AI test in the matter of minutes. This the time which the examiner program needs to calculate the test result. We should then add the thinking time we afford to each candidate. When we consider AI as a strategy, we need not ask the question of how much time the candidate will spend thinking. When we consider AI as a program which calculates an AI strategy, we must announce how much time we afford to the program for calculating one step.

So, the time for the test will be some minutes to calculate the test result, plus the thinking time which we afford to the candidate, plus some time for generation of the test (construction of the array of 1000 numbers). The last time we do not consider because it will be spend only once.

Let us think about what this test can be used for. If someone comes to us with a particular program, we would test it and say what the IQ of that program is. But, we do not have any AI-candidate programs. So we have nobody to apply this test to.

One possible application of the test described in this study is finding the AI. We might use the brute-force search method. Of course we can search with this method, but combinatorial explosion would not let us go too far with this method. There is, however, a smarter way of searching. We can construct a genetic algorithm. We will sit at one powerful computer, create a population of AI candidate programs, and calculate each candidate’s IQ. We shall combine candidates with higher IQs in order to obtain offspring with even higher IQ. We shall kill the low-IQ candidates in order to make room for more promising programs. Using this natural selection approach we shall obtain programs with very high IQs.

The genetic algorithm is one way of finding the AI, but we will end up with a program the inner workings of which are enigmatic to us. If we are to control a program, we better write it ourselves rather than generate it automatically. For this reason, I am a proponent of the direct approach for creating AI. Therefore, I assert that we should write this program with our own hands.


Acknowledgements

I wish to appreciate my colleagues Ivan Koychev, Anton Zinoviev and Andrey Sariev for the beneficial discussions on the AI Definition topic. Special acknowledgement to Ivan Koychev for his instrumental contribution to my summary of related work.
References

[1] Dimiter Dobrev. First and oldest application. 1993. http://dobrev.com/AI/first.html

[2] Dimiter Dobrev. AI - What is this. PC Magazine - Bulgaria, November'2000, pp.12-
13 (in Bulgarian, also in English at http://dobrev.com/AI/definition.html).

[3] Dimiter Dobrev. Formal Definition of Artificial Intelligence. International Journal "Information Theories & Applications", vol.12, Number 3, 2005, pp.277-285. http://www.dobrev.com/AI/

[4] Dimiter Dobrev. Parallel between definition of chess playing program and definition of AI. International Journal "Information Technologies & Knowledge ", vol.1, Number 2, 2007, pp.196-199.

[5] Dimiter Dobrev. Two fundamental problems connected with AI. Proceedings of Knowledge - Dialogue - Solution 2007, June 18 - 25, Varna, Bulgaria, Volume 2, p.667.

[6] Dimiter Dobrev. Giving the AI definition a form suitable for engineers. April, 2013. http://www.dobrev.com/AI/

[7] Alan Turing. Computing machinery and intelligence. Mind, 1950.

[8] John McCarthy. What is Artificial Intelligence? November, 2007. (www-formal.stanford.edu/jmc/whatisai/)

[9] Huazheng Wang, Fei Tian, Bin Gao, Jiang Bian, Tie-Yan Liu. Solving Verbal Comprehension Questions in IQ Test by Knowledge-Powered Word Embedding. arXiv: 1505.07909, May, 2015.

[10] Detterman, Douglas K. A Challenge to Watson. Intelligence, v39 n2-3 p77-78 Mar-Apr 2011.

[11] Feng Liu, Yong Shi, Ying Liu. Intelligence Quotient and Intelligence Grade of Artificial Intelligence. arXiv: 1709.10242, September, 2017.

[12] Dowe, D.L., & Hernández-Orallo, J. IQ tests are not for machines, yet. Intelligence (2012), doi:10.1016/j.intell.2011.12.001

[13] Hernández-Orallo, J., & Minaya-Collado, N. (1998). A formal definition of intelligence based on an intensional variant of Kolmogorov complexity.
Proc. intl symposium of engineering of intelligent systems (EIS'98), February
1998, La Laguna, Spain (pp. 146–163). : ICSC Press.

[14] Insa-Cabrera, J., Dowe, D. L., & Hernandez-Orallo, J. (2011). Evaluating a reinforcement learning algorithm with a general intelligence test. In J. M. J. A. Lozano, & J. A. Gamez (Eds.), Current topics in artificial intelligence. CAEPIA 2011. : Springer (LNAI Series 7023).

Няма коментари:

Публикуване на коментар