Pages:     | 1 |   ...   | 51 | 52 || 54 | 55 |   ...   | 82 |

The function World will take as arguments the current state of the world and the influence that our device exerts on the world at the current step. As a result, this function will return the new state of the world (which it will obtain on the next step). The function View gives the information what our device sees. An argument of this function will be the world's current state and the returned value will be the information that the device will receive (at a given step).

Life in one world will be any infinite row of the type: d, v, d, v,... where v are letters from and d are letters 1 1 2 2 i i from. Also, there has to exist infinite row s, s, s,... such that s is the staring state of the world and i>0 1 2 v =View(s ) and i s =World(s, d ). It is obvious that if the world is given then the life depends only on the i i i+1 i i+actions of AI (i.e. depends only on the row d, d, d,...).

1 2 In order to transform the definition in [1] and to make it formal, we have to define what is a program, what is a good world and when one life is better than another.

The first task is easy because this work is done by Turing in the main part. Anyway, the Turing definition of program is for a program which represents function, but here we need a transducer which inputs the row v, v, 1 v,... and outputs the row d, d, d,.... So, we will make a modification of the definition of Turing machine [6].

3 1 2 This publication is partially supported by the Bulgarian Ministry of Education (contract 1102/2001) XII-th International Conference "Knowledge - Dialogue - Solution" Our second task is to say what a good world is. It was written in [1] that if you can make a fatal error in one world then this world is not good. What is world without fatal errors needs additional formalization.

The next problem is to say when one life is better than another. This is done in [1] but there are some problems connected with the infinity which have to be fixed.

The last task is to say how intelligent our program should be and this cannot be done by comparison with a human being.

What is a Program We will define a program as a Turing machine [6]. Let its alphabet consist of the letters from, from, from one blank symbol and from some service signs.

Let our Turing machine have finite set of internal states P, one starting state p and a partial function F: P P {Left, Right}.

The Turing machine (TM) is a step device and it makes steps in order to do calculations. On the other hand, AI is a step device and its life consists of steps. In order to make distinction between these two types of steps we will call them small and big steps. When we speak about time we will mean the number of big steps.

Of course, our TM will start from the state p with infinite tape filled with the blank symbol. How our TM will make one small step. If it is in state p and if its head looks at the letter then F(p, ) will be a 3-tuple which first element is the new state after the small step, the second element will be the new letter which will replace on the tape and the third element will be direction in which the head will move.

How will our TM (which is also our AI) make one big step This will happen when after a small step the new state of TM is again p. At this moment our TM has to output one letter d and to input one letter v. We will assume that 0 i i the letter which is outputted is that which is written on the place of on this small step. But how after outputting the letter d will our TM input the letter v We will put this letter on the place where the head after the small step i i is. In this way we are intervening in the work of the TM by replacing one symbol from the tape with another. The replaced symbol is lost in some sense because it will not influence the execution of the TM from this small step on.

We will assume that our TM is outputting only letters from (no letters from the rest of ). Also, we assume that our TM never hangs. TM hangs if after reading some input v, v,..., v it stops because it falls into some state p 1 2 n and its head falls on some letter such that F(p, ) is not defined. TM also hangs if after reading of some input v, v,..., v it makes infinitely many small steps without reaching the state p (without making of big steps 1 2 n anymore).

After this we have a formal definition of a program. We have to mention that there is no restriction on the number of the small steps which TM needs to make for one big step. This number has to be finite but it is not restricted.

Maybe it is a good idea to add one parameter Max_number_of_small_steps_in_AI in order to exclude some decisions for AI which are combinatory explosions. (If we restrict the number of small steps then we have to restrict also the number of service signs in because we can speed up the TM by increasing the size of its alphabet.) If we want to use AI as a real program on a real computer then we have to take into consideration that the memory of the real computers is limited. So, we can restrict also the size of the tape. Anyway, we will not care about the efficiency of AI and we will not make such restrictions.

What is a World without Fatal Errors It is very difficult to define what a world without fatal errors is. That is why we will do something else. We will restrict our set of worlds is such a way that the new set will contain only worlds without fatal errors.

Let our world look like one infinite sequence of games. Let every game be independent from the previous ones.

Let us have three special letters in, which we will call final letters. Let this letters be {victory, loss, draw}. Let every game finish with one of the final letters. Let every game be shorter than 1000 big steps.

Remark 1: Our definition of AI will depend on many parameters. In order to simplify the exposition we will fix these parameters to concrete numbers. Such parameter is the maximum number of steps in a game which will be fixed to 1000. Also, in order to simplify the exposition we will use different numbers for different parameters.

232 Mathematical Foundations of AI Remark 2: The only parameters in our definition which are not numbers are the alphabets and. We will assume that these alphabets are fixed and that has at least 2 letters and has at least 2 letters which are not final. (If has only one letter then there will be no choice for the action of AI and the world will be independent from this action. If has only one letter, which is not final, then the game will be blind because AI will not receive any information until the end of the game. Therefore, the minimum for || is 5.) We will assume that the world has three special internal states {s_victory, s_loss, s_draw}, which we will call final states. Let these states be indistinguishable from the state s for the function World. This means that the world will behave in the final states in the same way as if it was in the starting state. Let the function View distinguish the final states and return from them the letters victory, loss and draw respectively. Also, the final states will be the only states on which the function View will return one of the letters {victory, loss, draw}.

After the restriction of the definition of World, we can be sure that there are no fatal errors in our world because the life in such a world is an infinite sequence of games and if we lose some games (finitely many) then this will not be fatal because every new game is independent from the previous ones. Also, we are sure that a new game will come sooner or later because every game is finite (i.e. previous game is shorter than 1000 steps).

When is One Life Better than Another In [1] we gave the following definition for the meaning of the life: One life is better than another if it includes more good letters and fewer bad letters. Here good letters will be {victory, draw} and bad letters will be {loss, draw}.

So, here life is good if we win often and lose seldom.

We want to introduce one function Success which will evaluate with a real number every life in order to say how good it is. For that we will define first the function Success for the every beginning of life (all beginnings are finite). After that we will calculate the limit of Success when the size of the beginnings goes to infinity and this limit will be the value of Success for the entire life.

The function Success can be defined for the beginnings like the difference between the number of victories and the number of losses. This is not a good idea because then the limit of Success will possibly converge to infinity (plus or minus infinity). It is a better idea to calculate the percentage of victories. So, we define Success as (2.N_victory +N_draw)/ (2.N_games). Here N_victory is the number of victories (analogically for N_draw and N_games). Function Success will give us a number between 0 and 1 for every beginning and its limit will be also between 0 and 1. The only problem is that Success may not have a limit. In such a case we will use the average between limit inferior and limit superior.

Trivial Decisions Now we have a really formal definition of AI and this gives us the first trivial decision for AI.

TD1 will be the program which plays at random until the first victory. After that TD1 repeats this victory forever.

For this TD1 needs only to remember what it did in the last game. If the last game was victorious then it can repeat this last game because the function World is deterministic and if TD1 is doing the same then the world will do the same too.

TD1 is perfect in all worlds in which the victory is possible. If the victory is not possible then TD1 will play at random forever. That is why we will make TD2 which will be perfect in all worlds.

TD2 will be this program which tries sequentially all possible game's strategies until it finds the first victory and after that repeats this victory forever. If there is no victorious game strategy then TD2 repeats the last draw game forever. If the draw game is not possible too then TD2 plays at random. (It is important that the game's length is not more than 1000. This means that the number of the game's strategies is finite.) TD2 is perfect in all worlds and this means that it is a trivial decision on our definition for AI. Really, the definition stated that AI has to cope no worse than a human but for the perfect program this is true because it copes no worse than anything even no worse than a human being.

It is suspicious that such simple program like TD2 can satisfy our definition for AI. That is why we will change the definition by accepting more possible worlds. It is too restrictive to assume that the game is deterministic and every time you do the same the same will happen.

XII-th International Conference "Knowledge - Dialogue - Solution" Nondeterministic Games We will assume that the function World is not deterministic. It is better to say that it is multy-valued function, which chooses at random one of its possible values. Let every possible value correspond to one real number, which is the possibility for this value to be chosen. We will assume also that s World(s, ) has at least one value and that s ( for every two different values of World(s, ) the function View returns different result).

Remark 3: The latter means that if something nondeterministic happens this information will be given to AI immediately by the function View. There is no sense to assume existence of a nondeterministic change which cannot be detected immediately but later or even which cannot be detected never.

Now we will ask the question what is the best strategy in such a world and we will offer a program, which will be almost perfect. Before that we need several definitions:

Definition 1: Tree of any game. It will have two types of vertices. The root and the other vertices which are on even depth will be the vertices of type AI (because they correspond to the moments when AI has to do its choice).

The vertices which are on odd depth will be vertices of the type world (because they correspond to the moments when the world will answer at random). From the vertices of type AI go out || arcs and to every such arc corresponds one of the letters from. There is one exception. If the arc which is right before this vertex corresponds to a final letter, then this vertex is a leaf. From the vertices of type world go out || arcs and to every such arc corresponds one of the letters from. Here there is an exception again. If this vertex is on depth 1999, then only three arcs go out and these three arcs correspond to the final letters.

You can see that the tree of any game is finite and its maximum depth is 2000 (because games are not longer than 1000 steps). Nevertheless, there are leaves on any even depth between 2 and 2000.

Definition 2: Tree of any 100 games. Let us take the tree of any game. Let us replace all of its leaves with the tree on any game. Let us repeat this operation 99 times. The result will be the tree of any 100 games (which is 100 times deeper than the tree of any game).

From the tree of any game we will receive Strategy for any game. This will be its subtree which is obtained by choosing one vertex from the successors of every vertex of the type AI and deleting the rest successors (and their subtrees). Analogically we make Strategy for any 100 games like a subtree from the tree of any games. We have to mention that the Strategy for any 100 games can be different from repeating one Strategy for any game 100 times. The reason is because the strategy on the next game can depend on the previous games.

Definition 3: Tree of this game. For every concrete game (i.e. concrete world) we can construct the tree of this game as a subtree from the tree of any game. We will juxtapose internal states of the world to the vertices of type AI in the time of this construction. First, we will juxtapose the state s to the root. Let k, k and k be vertices and 0 0 1 let k be successor of k and k be successor of k. Let k be vertex of type AI and let the state s be juxtaposed to 1 0 2 1 it. Let the letters and be juxtaposed to the arcs < k, k > and < k, k >. In this case if View(World(s, )) 0 1 1 for every value of World(s, ) then we delete the vertex k (and its subtree). In the opposite case we juxtapose k to this value of World(s, ) for which = View(World(s, )). This value is only (look at remark 3). Also, we will juxtapose the possibility to be the value of View(World(s, )) to the arc < k, k >. So, one letter and one 1 possibility will be juxtaposed to the arc < k, k >.

Pages:     | 1 |   ...   | 51 | 52 || 54 | 55 |   ...   | 82 |

2011 www.dissers.ru -

, .
, , , , 1-2 .