First-order logic + the Einstein Challenge

Welcome ProgSchedule villagers, our AI Team has been working in a couple of First-order logic challenges, which are a very approach to how would machines make their own deductions, applying inference rules, through a formal system. Let’s have a brainstorm to get in the context:

  1. Inference is the act of deriving logical conclusions from premises known or assumed to be true.
    EX: 
    a->b 
    b->c
    Therefore, a->c
  2. First-order logic is the standard for the formalization of mathematics into axioms. A theory about some topic is usually first-order logic. It’s formal syntax includes:
    1. Logical connectives ^ “and”, v “or”, ~ “not”, → “imples”…
    2. Quantifier symbols ∀ “for all”, ∃ “there exists”
    3. Parentheses, brackets, variables, equality symbol…

With this in mind, let’s assume we are ready for the challenges:

#1 THE FAMILY TREE

family tree unsolved

Could you fill the tree above using the following clauses?

  • Miguel and Alejandro call “dad”and “son” among them.
  • Fernando has an older brother.
  • Alejandro is the brother of Carmen.
  • Alberto is the grandfather of Marcos.
  • María only has 2 children, just as Carmen and Alberto.
  • Tomás is the brother in law of Lucía
  • Berta is the youger sister of her sister, but is older than her brother.
  • Patricia is the niece of Carmen.

#2 THE EINSTEIN LOGIC PROBLEM

There are five houses in a row and in five different colors.

In each house lives a person from a different country.

Each person drinks a certain drink, plays a certain sport, and keeps a certain pet.

No two people drink the same drink, play the same sport, or keep the same pet.

  • The Brit lives in a red house
  • The Swede keeps dogs
  • The Dane drinks tea
  • The green house is on the left of the white house
  • The green house owner drinks coffee
  • The person who plays polo rears birds
  • The owner of the yellow house plays hockey
  • The man living in the house right in the center drinks milk
  • The Norwegian lives in the first house
  • The man who plays baseball lives next to the man who keeps cats
  • The man who keeps horses lives next to the one who plays hockey
  • The man who plays billiards drinks beer
  • The German plays soccer
  • The Norwegian lives next to the blue house
  • The man who plays baseball has a neighbor who drinks water.

Question: Who owns the fish?

WARNING!!!
ANSWERS COME BELOW

#1 THE FAMILY TREE

family tree solved

#2 THE EINSTEIN LOGIC PROBLEM

         
R#        
1 ( i , j ) nacionality(i)!=nacionality(j)    
2 ( i , j ) color(i)!=color(j)    
3 ( i , j ) pet(i)!=pet(j)    
4 ( i , j ) cigarrete(i)!=cigarrete(j)    
5 ( i , j ) drink(i)!=drink(j)    
6 ( i , j ) link(i,j) -> (j=i+1 ^ j<=5) V (j=i-1 ^ j>=1)
 
7 ( i ) i == 1 -> nacionality(i)= Norwegian
8 ( i , j ) i==1 ^ color(j)==blue -> link(i,j)
9 ( i ) i == 3 -> drink(i)= milk
10 ( i ) color(i) == red -> nacionality(i)= Brit
11 ( i ) pet(i) == dog -> nacionality(i)= Swede
12 ( i ) drink(i) == tea -> nacionality(i)= Dane
13 ( i , j ) color(i)==white^ color(j)==green -> j = i+1
14 ( i ) drink(i) == brown -> color(i)= green
15 ( i ) cigarrete(i) == pallmall -> pet(i)= birds
16 ( i ) cigarrete(i) == dunhill -> color(i)= yellow
17 ( i , j ) cigarrete(i)==blend ^ pet(j)==cats -> link(i,j)
18 ( i , j ) cigarrete(i)==dunhill ^ pet(j)==horses -> link(i,j)
19 ( i ) cigarrete(i) == bluemaster -> drink(i)= beer
20 ( i ) cigarrete(i) == prince -> nacionality(i)= German
21 ( i , j ) cigarrete(i)==blend ^ drink(j)==water -> link(i,j)
 

 

Color Nacionality Pet Cigarrete Drink
yellow Norwegian cats Dunhill water
blue Dane horses Blend tea
red Brit birds Pallmall milk
green German   Prince coffe
white Swede dog Blue Master beer

Answer: Not the Norwegian, nor the Dane, nor the Brit, not the Swede

Heuristic Optimization to our State Generator

Greetings from the AI-ProgSchedule Team, we continued improving our state generator and have now incorporated a heuristic optimization to the program we explained on the last post!

The heuristic we implemented works as following:
Each state has a list of possible following states, that we use to find a path to the target state. Each time the next state has to be chosen, we order the list of states according to how similar the next state is to the target state.

For example, suppose we want to get to a target state such as this:
1 2 3
4 5 6
7 8 –

If on a certain part of the analysis we are on a state such as this:
1 2 –
6 4 3
7 8 5

There are two possible states we can pass from such a state;
Moving 3 up:
1 2 3
6 4 –
7 8 5

And moving 2 right:
1 – 2
6 4 3
7 8 5

However, if we count how many numbers on each possible state match the target state, we find that moving 3 up matches 5 numbers, while moving 2 right matches only 3 numbers.

At that point, our program would order the list so that moving the 3 up would be the first state to be attempted, since its more likely to lead us to the solution.

Here is a screenshot of a test run for a depth-first-search from this initial state:
– 1 2
3 4 5
6 7 8

To this target state:
1 2 5
4 6 8
3 7 –

Heuristic Run

As you can see using our heuristics takes less than a second to complete. We are certain applying more complex heuristics the time could be improved, but for our first attempt we are happy with the result.

You can find the source code here:
https://github.com/rominavarela/ai/tree/master/GeneratrixB

We will keep you informed on the progress of the project. See you later!

States Generator and Searches

Greetings from the AI-ProgSchedule Team, today we will show you a practice that we develop that creates a Generic States Generator for a given problem and  how we apply Depth First Search and Breadth First Search.

This practice consists in develop a generic states generator of all possible states for a given problem. We have an initial state that could be any possible state and applying operators and some functions to obtain all the states linked by operators.

Once we have all states linked by operators we can apply Depth First Search or Breadth First Search to solve the problem.

In this practice the search determine what is the next state (step) to solve the problem, and at the end we will have the final state that it’s the solution.

Now we will show you some screenshot.

We can see that depending if we use Depth First Search or Breadth First Search  the results are different (in time).

STATE GENERATOR

ss3

BFS

ss1

DFS

ss2

You can check the code here:

https://github.com/rominavarela/ai/tree/master/GeneratrixB

We can try having better results  implementing some heuristic, but that will come in our next Post… so we hope you can read us next time, see you!!

The Artificial Intelligence Debate

Greetings from the AI-ProgSchedule Team, today we were reading the Computer Machinery and Intelligence, written by Allan Turing, the father of computer science.This writing leads us to pose some questions such as: what does being intelligent means? what is the difference between a human and a computer? can machines think?

Let’s just summarize the introduction of Allan Turing by quoting the description of his Imitation Game:

It is played with three people, a man (A), a woman (B), and an interrogator (C) whom may be of either sex. The interrogator stays in a room apart from the other two. The object of the game for the interrogator is to determine which of the other two is the man and which is the woman […] We now ask the question , “What will happen when a machine takes the part of A in this game ? ” Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman?

The article and the general opinion proposes some potential objections against the artificial intelligence search, they say that there are several human skills impossible to be replicated by a computer; distinguishing good from evil or loving for instance. In fact, we believe that the most difficult part to mimic is that of our feelings and emotions, we humans do stupid things while machines would never lose their logic sense.

As machines may not be able to feel -and act illogically as consequence of that- we would have to program their behaviour, the problem would then depend on our understanding of ourselves…

We can add some other doubts like how would a computer pass a psychological test? would we detect any characteristic such as egoism or altruism? How would a machine relate cognitive abstractions like shapes with colours? What about pattern recognition? Would the computer figure out a shape in a spot? a constellation?

The article was written in 1950, in it, Turing predicted that by 2000 a computer should have a 30% chance of passing a Turing Test 5 minutes with an average interrogator. We are considering that in 2015, in the era of instant communications, we are not so far from what we predicted, we believe it is very likely that there is already a machine that pass these tests.

It seems that regardless of technological advances, there still exist objections against artificial intelligence, even considering a half-century of distance between the author of this and that article. Beliefs and a growing paranoia of an invasion never stops being fashionable.

Technology evolves so fast that it also annoys some economic and social factors, factors that may add to the refusal of developing an intelligence comparable to ours; a kinda flashback to what happened back in the Industrial Revolution times.

In the end we concluded that the knowledge we have is not yet definitive and it would be a very interesting challenge to build an intelligence that works to fulfil the experiment. It requires a multidisciplinary team work… In a broader sense this would also helps us to know ourselves. What about you readers think?

Cloud Computing elementals: SaaS PaaS IaaS

Cloud computing is the paradigm where we rely on services offered through the internet. It stands on a layered architecture whose primal objective is to encapsulate the different concerns of a complex computational solution; therefore, we can break the problem into smaller individuals. In other words, it is the cloud’s Divide and Rule protocol.

Cloud Computing Pyramid

Cloud Computing Pyramid

 SAAS

Software as a Service

Software applications are addressed to end users. The advantages of cloud applications implementation, above traditional models, are due to the characteristic that software is a service that customers can access to with no need to acquire a copy.

Product vs Service

Product vs Service

So you don’t have to harass users with false licenses, compile customized versions or provide specialized  support and updates.

 

PAAS

Platform as a Service

Includes the operating system, programming language execution environment, database and web server required to hold your application running. Cloud-destined software is built up on a a cloud-specialized platform.

IAAS

Infrastructure as a Service

Infrastructure as a service points to hardware: storage media, networking components, servers and virtual/physical machines.

 

 

 

 

The SQL pillars: DDL, DML, DCL, TCL, and why

database_hierarchy

Considering the hierarchy bellow, SQL statements are classified in 4 pillars:

  • DDL (Data Definition Language)

Comprising instructions that work in the hierarchy from table upwards:

create, alter, drop, rename…

  • DML (Data Manipulation Language)

Working in fields and records with:

select, insert, update, delete, explain…

  • DCL (Data Control Language)

For administrative purposes, working with users and permissions with:

grant, revoke…

  • TCL (Transaction Control Language)

With magic power to undo or save changes:

commit, rollback, savepoint, set transaction…

NOTE: There are some differences from one to another Database engine, for example Oracle’s hierarchy encloses groups of tables in schemas; SQL statements also differ a little because of this, but no matter what, SQL language defined in the World Wide Web Consortium (W3C) reference have never failed with me.

WHY THE CLASSIFICATION? TCL usage

If you are like me, I’d always asked my self why such a complexity of knowing which instruction belongs to which group. Well, answer is that interesting stuff happens when theory faces the realm. Let’s first talk about TCL…

When you

Transaction Control Language comprises magic powers,

New Improved Version of Raspberry Pi released

A new model of the famous credit-card sized computer has been released. This new model is called Raspberry Pi B+, it is already available for orders. Here you’ll see its most important new features.

The computer is designed and manufactured in the UK by the non-profit foundation named Raspberry Pi Foundation. This new redesigned of this credit-card size computer is meant to promote de development of bigger projects on it. That’s why this new model (called B+) contains extra connector and sensors.

rsz_b-

The Model B+ uses the same BCM2835 application processor (700MHz) as the Model B. It has 512 MB RAM.

  • More GPIO. The GPIO header has grown to 40 pins, while retaining the same pinout for the first 26 pins as the Model B.
  • More USB. It has 4 USB 2.0 ports, compared to 2 on the Model B, and better hotplug and overcurrent behaviour.
  • Micro SD. The old friction-fit SD card socket has been replaced with a much nicer push-push micro SD version.
  • Better audio. The audio circuit incorporates a dedicated low-noise power supply.

‘We’ve been blown away by the projects that have been made possible through the original B boards and, with its new features, the B+ has massive potential to push the boundaries and drive further innovation.’ Said by Eben Upton, CEO of Raspberry Pi Trading.

mechanicalspecB+

It is powered by micro USB with AV connections through either HDMI or a new four-pole connector replacing the existing analogue audio and composite video ports. The SD card slot has been replaced with a micro-SD. The B+ board also now uses less power (600mA) than the Model B Board (750mA) when running.

It is still the same price as the B model.

You can get your own Raspberry Pi B+ ordering your own on:

 

Images thanks to:

 

Maven, Apache POMs to standard project building

Maven, a Yiddish word meaning accumulator of knowledge, is an Apache project that standard the way we build projects. It mainly works with Java, but can also be used with other languages. Maven faces traditional compilation tools, think about it as an improved Ant. This article aims to show you what, why and how.

apache maven

Maven works on the top of a XML file named POM (Project Object Model) that describes its dependencies on external modules and components, the build order, directories and required plug-ins. It dynamically downloads the required external dependecies at the moment they are specified from a central repository though you can declare different sources. Follow me in a practical example to see how it works!

INSTALLATION

There are 2 ways: you can work directly from a development tool with maven integration like Eclipse IDE for java EE or try on the command prompt way.  Since the 1st way depends on each proprietary dynamics, we will use the “universal” commando prompt.

STEP 1. To guarantee a successful instalation we must be sure we have java jdk, so go and type:

java -version

If you find a problem here, Windows users can find help in this video and Linux/Unix users here.

STEP 2.

Windows Users: download the program from it’s official source here. Unzip, move unziped folder to Program Files and open bin/mvn.bat If you have problems, it may be that you have java JRE and not JDK, so try to reinstall it properly with step 1.

Linux and Unix: run the command

sudo apt-get install maven2

 

HELLO WORLD

Now that everybody have installed maven, we can successuly type the command:

mvn -version

Using the command line, go into the folder you will to be your workspace. Noobs in Command Line: watch this video. Right in your workspace, let’s initializate a maven project:

mvn archetype:create   -DgroupId=com.dps.maven2example -DartifactId=maven2example_logic

cd maven2example_logic

mvn test

mvn package

java -cp target/maven2example_logic-1.0-SNAPSHOT.jar com.dps.maven2example.App

If success, you will get a “Hello World!” message in return. If you are inside a private network, you may fail from the first command. Solution for that is to configure your proxy at the maven configuration: please look for your maven installation folder and open the file conf/settings.xml Right there is an space for proxy configuration, uncomment it and fill the form.

ADDING NEW DEPPENDENCIES

Open your pom.xml file This is my view:

maven

maven

I strongly recommend you to use a good text editor to visualize your files, if you fell curious, I’m using Atom text editor. Atom is free and multi-platform.

See we have an dependency into our file. You may all do have noticed during the execution of your commands, some files were downloaded: this is what I refereed to when I told you maven dynamically downloads the required external dependencies at the moment they are specified. Let’s add another dependency, a spring library, and see what happens.

 STEP 1. Go to the main repository at http://mvnrepository.com/ (save this link) and search “spring”

mvn spring

mvn spring

 

From the list of results, select the one that has the spring library. There, you will find the:

  1. groupId
  2. artifactId
  3. version

STEP 2. Okay, let’s add it to our POM, run “mvn package” and see how the whole thing gets downloaded. Now we can use the librarie’s methods.

<dependency>
      <groupId>org.springframework</groupId>
      <artifactId>spring</artifactId>
      <version>2.5.6.SEC03</version>
</dependency>

MOVING TO ECLIPSE

Finally, we all know it is easier to have a IDE that reads our project’s dependencies and auto-complete our code in real time. In my case, I like to use Eclipse IDE. When you are running the Eclipse (or other IDE, I don’t know), you may import you project in File > Import… > Maven > Existing Maven Projects > Browse and choose the root directory of your project (in this case maven2example_logic).

Your project will charge then and everything down “src” folder will show up as java libraries. Note you have a division named “Maven Dependencies” with all your libraries charged inside, and not also now you are able to use such importet content.

maven in eclipse

maven in eclipse

 

We are done for today. We had a very practical tour in maven’s world. Keep following ProgSchedule because it’s getting better!

RESOURCES

Maven’s Apache site – What is Maven?

IBM – 5 cosas que usted no sabía acerca de… Apache Maven

Wikipedia – Apache Maven