Wednesday, July 29, 2015

Deducing concepts


Suppose you need to find a rule and append new lines to the following array:







2 5 10 17 26 37 50
4 9 18 31 48 69 94
8 15 28 47 72 103 140
16 25 42 67 100 141 190

If you put the first row into iqsolver you will get an answer
Apply "-" on consecutive elements in [2, 5, 10, 17, 26, 37, 50] to get [3, 5, 7, 9, 11, 13]
  Apply "-" on consecutive elements in [3, 5, 7, 9, 11, 13] to get 2

The second row lead to a very similar solution:
Apply "-" on consecutive elements in [4, 9, 18, 31, 48, 69, 94] to get [5, 9, 13, 17, 21, 25]
  Apply "-" on consecutive elements in [5, 9, 13, 17, 21, 25] to get 4

The solutions differ however by parameters: the number which is the difference of the prime sequence is 2 in the first case and 4 in the second. There are also other hiden parameters: when creating a differential sequence from a given one - an information is lost about the value of the first element in the original sequence. I marked these transformation parameters in fuchsia for the original sequence and lime for the prime one. So if you extract them and put them along with the length of the original sequence you get all 4 parameters required to build the original sequence (just like you need parameters a and r to build an infinite geometric progression )

You may think about it as a procedure, which a programmer would create in order not to calculate these numbers herself:
[2,5,10,17,26,37,50] == double_minus_and_identity(2,2,3,7)
[4,9,18,31,48,69,94] == double_minus_and_identity(4,4,5,7)

But this double_minus_and_identity is a concept, which will be extracted by AI and applied to further sequences. Thus, a new table may be created with 4 columns - one for each parameters and number of rows matching number of original sequences:

2 2 3 7
4 4 5 7
6 8 7 7
8 16 9 7

When AI applies reasoning to the columns treating each as a separate series, it will not only conclude what are the parameters of next rows (10,32,11,7) and be able to add new row to the original arrays (32,43,64,95,136,187,248).

It will also be able to create a higher level concept. The concept (lets call it double_minus_and_identity_table) has 7 parameters (2 for each sequence in the first 3 columns and one for the last), however some of the parameters are equal. 1st and 3nd columns share the same difference (=2) which is quotient in the 2nd column. So maybe a 3-parameter (2, 3, 7) concept should be created? When you see a square (1-parameter) it may be treated as well as quadrilateral for which 4 lenghts and 1 angle should be stated. So AI should rather generate a few concept from this example and check if it can be applied to other cases or another question given by another user. And this may be called learning by experience because it will reach faster to concepts it is already familiar with. However, this may distract from learning new things. Experience may be an obstacle for fresh look.

In board games

The above described example is pretty simple, but from analysis of difference of boards of chess AI could deduce a concept of move, capture and promotion. Analysis of Go boards could lead to infering concepts of chains and liberties. It is however a problem how to find the right path among tree of possibilities, what to concentrate on. But this is a topic for another post.

Tuesday, July 28, 2015

How does it work

IQ Solver is designed to handle data presented as a graph. However the current version solves only sequential tests. Simplified version of algorithm of finding the solution works in the following way. For every sequence the following steps are ordered:

  • Check if it composes of the same elements - if yes then in description you will see.

[7, 7, 7] consists only of : 7
  • Check if it repeats the same subsequence of elements. If yes then the description is:
[1, 1, 2, 1, 1, 2, 1, 1, 2] is repeated sequence of : [1, 1, 2]
  • Check if element a[n] = a[n-2] # a[n-1]  where # is +, -, * or / . Sample description:
Obtain element by applying "-" on previous 2 elements of [1, 4, -3, 7, -10] 

  • Create a new imaginary sequence by applying +, -, * or / on the current and previous elements. 
Apply "-" on consecutive elements in [1, 3, 7, 15] to get [2, 4, 8]
  • Create n imaginary sequences by splitting the original sequence:
[1, 1, 2, 2, 3, 4, 4, 8] may be divided into 2 sequences: 
         [1, 2, 3, 4]; [1, 2, 4, 8]
  • If some elements are repeated - create 2 imaginary sequences - one with number of each repetition (or 1 is an element is single) and the second with the repeated elements.
[5, 8, 5, 5, 8, 5, 5, 5, 8] may be divided into values [5, 8, 5, 8, 5, 8] and number of their repetitions [1, 1, 2, 1, 3, 1]

The same steps as applied on original series are also applied on the imaginary ones. This creates a a huge tree  of potential solutions. To handle this, a total complexity of solution is calculated and it determines which steps should be performed first. This rate is even shown as the low value indicate simple solution, which should be the right one.

Example


Here is the generated explanation of the sequence 5,8,5,5,8,5,5,5,8
[5, 8, 5, 5, 8, 5, 5, 5, 8] may be divided into values [5, 8, 5, 8, 5, 8] and number of their repetitions [1, 1, 2, 1, 3, 1]
  [5, 8, 5, 8, 5, 8] is repeated sequence of : [5, 8]
  [1, 1, 2, 1, 3, 1] may be divided into 2 sequences: 
         [1, 2, 3]; [1, 1, 1]
    Apply "-" on consecutive elements in [1, 2, 3] to get 1
    [1, 1, 1] consists only of : 1

And the graph to this solution generated using GraphStream library


Monday, July 27, 2015

Introduction

Vision


This blog is about my project of Artificial Intelligence. It is planned to be able to deduce concepts, create complex concepts basing on basic ones and apply them to new data. It is supposed to pass experience from one task into another. The ultimate test to check if it is general enough - I don't know if achievable at all - is to let it control characters in arbitrary virtual world. It should be able to learn from the scratch how this world works and how to act within it. People could then watch the concepts it creates and how it perceives the world, which is the only reality it knows.

Current state


Currently this AI is able to solve numerical IQ tests. It is available online, so you may check it at http://iqsolver.eu/ . Here is a list of samples questions: http://iqsolver.eu/samples.html, you may try to solve them yourself and then compare with the answer of AI :). For most questions more than 1 answer are generated, but the first one is probably the right one. I will write later about what it can and cannot do.

Plans

Below is an ambitious list of test steps the AI should be able to achieve during its development. However, it shouldn't be designed specifically to them, but rather solve them using generality of its intelligence.

  1. Solving numeric single-line sequence tests
  2. Solving multiple-lines or matrix numerical tests
  3. Deducing rules in arbitrary complex structure containing sequences, maps, maps of sequences, etc. Anything that could be stored in a JSON document
  4. Deducing rules of complete information games for example: board games (Chess, Go, Reversi)  being given sequence of game snapshots.
  5. Learning how to play full information games.
  6. Coping with partial information games - distinguishing between what is perceived and what is real
  7. Theory of mind - being able to deduce what other agents may know
  8. Being able to learn the rules of any computer game provided that non-graphical interface is given: not a 3D image but a set of number which indeed every object in computer game is. Agents controlled by this AI could be put in the virtual environment.

Currently step 1 is generally achieved. Many single-sequence tests require step 2: dividing sequence into many sub-sequences. I have some ideas how to make steps 2-4, the rest is just a vision. If you have some ideas - please comment.