Clips andResolution of:
`CountDown-Game'
Using Clips
Short Description:
This document is about the language of programing
Clips and the use of it to solve the common game `CountDown'
where you have to try to get one target number using a free combination
of the six that the random program give to you at the beginning of the game
with the mathematical operations add, subtract, division and multiply.
Student: Luca Sanchez Aliaga Nr: 170973
Index:
1/ What's Clips
1.1/ How Clips Works
2/ Description of CountDown Game
3/ Description of possible solutions
4/ Algorithms Used
5/ Program in Clips
6/ References
1/ What is clips?
CLIPS is a public domain software tool for building expert systems . The name is an acronym for `` C Language Integrated Production System.'' The syntax and name was inspired by Charles Forgy 's OPS (``Official Production System,'' although there was nothing really official about it). The first versions of CLIPS were developed starting in 1985 at NASA - Johnson Space Center (as an alternative for existing system ART*Inference) until the mid 1990s when the development group's responsibilities ceased to focus on expert system technology. The original name of the project was NASA's AI Language ( NAIL ).
CLIPS is probably the most widely used expert system tool because it is fast, efficient and free. Although it is now in the public domain, it is still updated and supported by the original author, Gary Riley. CLIPS incorporates a complete object-oriented language COOL for writing expert systems. Though it is written in C , its interface more closely resembles that of the programming language LISP . Extensions can be written in C, and CLIPS can be called from C.
Main characteristics
Representation of the knowledge : Clips use a big variety of knowledge, working with three ways of programation: declarative, imperative and oriented to objects. The logic programation based on rules let the knowledge be represented as heuristics rules that specify the actions to be executed in each situation.
Portability : CLIPS was written in C thinking on make it be easy to port and faster, and can be installed in many different OS without modify the code.
Interactive developing: The standard version of CLIPS provide an interactive developing environment and based on text, this include depuration tools, online help and an editor.
Verification and validation: CLIPS include tools to verify the rules incluyed in the expert system that is being developed, including modular design and partitioning of the data base of knowledge of the system, static checking of constraints and dynamic for functions and some kind of data, and semantic analysis of rules to avoid inconsistence.
Documentation: In the web page of CLIPS we have many documentation and a manual of reference for using the language.
Low Cost: is free software of public domain.
1.1/ How Clips Works
Sho rt description: Here I will explain how this language works using also some examples to make it easier to understand.
Starting and ending of the program:
Clips is a program for MS-DOS converted to windows, so the program is based in commands in a text screen. The executable is CLIPS.exe and works just doing double click on it. To exit we have to put on clips the command exit: CLIPS> (exit)
Inserting Fact:
To insert a fact we will use the command assert. A fact can be very flexible for clips: from just a word until many of them, let's we see it with an example:
CLIPS> (assert (foxterrier))
<fact-0>
CLIPS> (assert (milu foxterrier))
<fact-1>
CLIPS> (assert (try_kill marco cesar))
<fact-2>
The best is to follow any kind of schedule of notation, to make the facts being useful to create rules. The facts are showed in a screen (Windows ->facts) and can be showed in the main screen using the command (facts)
CLIPS> (facts)
f-0 (foxterrier)
f-1 (milu foxterrier)
f-2 (try_kill marco cesar)
Inserting Rules:
We can insert rules in clips using the command `Defrule', putting at first the facts that will be input, it mean the preconditions, to make the rule works we will use a symbol `=>' and later, all the actions related with the rule.
CLIPS> (defrule flu
(feel_sick)
(fever)
(cold)
=>
(assert (flu))
(printout t "you have the flu." crlf)
)
As we can see is the typical notation of Lisp. We don't need to keep this format for the input, we can put all in the same line.
In logic notation:
flu :- feel_sick, fever, cold
In programming notation:
if
(feel_sick
and
fever
and
cold)
then conclude
flu.
The command (printout t [output|CRLF]*) help us to print the screen.
Using Variables:
We can use variables, universal variables.
For example:
Car(x) :- four_wheels(x), motor (x)
With x is read as “for all x”
This is translated into a rule of CLIPS as:
CLIPS> (defrule is_car
(four_wheels ?x)
(motor ?x)
=>
(assert (car ?x))
)
“is_car” is just the name of the rule
A working example for a expert system built:
"Pepe is a person"
"Pepe lives in Wroclaw"
"Every person who lives in Wroclaw is from Poland"
"Every person who lives in Poland is from Europe"
P
erson (pepe)
fromwroclaw(pepe)
frompoland(x) :- fromwroclaw(x)
fromeurope(x) :- frompoland(x)
CLIPS> (reset)
CLIPS> (assert (person pepe))
<f-1>
CLIPS> (assert (fromwroclaw pepe))
<f-1>
CLIPS> (defrule frompoland
(person ?x)
(fromwroclaw ?x)
=>
(assert (frompoland ?x))
(printout t ?x " is from poland." crlf)
)
CLIPS> (defrule fromeurope
(person ?x)
(frompoland ?x)
=>
(frompoland ?x)
(printout t ?x " is from europe." crlf)
)
CLIPS> (run)
In the last example, the facts (from Poland pepe) and (from Europe pepe) will be included to the data base of facts.
2/ Description of the Count Down Game
Count Down
Try to get as close to the target
number with the 6 numbers you get at the beginning
You don't have to use all numbers
You cant use the same number just once.
Only this operations are valid: +, /, -, x.
The number s of the beginning will be selected randomly between this list of numbers ( 1, 2, 3, 4,…9, 10, 25, 50, 75, 100 ), the target will be selected also randomly from 1 to 999.
At the beginning are given to us six numbers that can be: 1, 2, 3, 4,…9, 10, 25, 50, 75, 10 0, and the target number, that is between 101 and 999. With the six numbers we have to get, using the four elemental operations Add, rest, multiplication and division the target number or get close to it.
It seems to be easy but give us some interesting porpoise:
When the number we have to achieve is big: What is the maximum number that I can reach with the first six numbers? The answer is not difficult.
Between two normal numbers, the multiplication is the operation that give us bigger results, except if one of the first numbers is 1, in that case is better to add. The ideal strategy to get the biggest number then is to multiply the first 6 numbers if none of them is 1. If any is 1, How we should add the number 1 to get the biggest result? Being (n+1) x b = a x b != b, we have to make b as big as possible. So the best strategy is to add 1 at the lower of the initial numbers and multiply the result with the four other numbers.
But, coming back to the main problem of the game: Get the target number using the first 6.
3/ Description of possible solutions
Sho rt description: Here we will see the possible solutions for the problem and how the human being use the mind to solve if, also, we will talk about decision trees an important branch in the artificial intelligence world and the importance of it in the application for this game.
So for that we have to do a exhaustive searching in all the possible combinations.
For this we will use a typical strategy in the Artificial Intelligence: Decision Trees.
We organize all the possible solutions in a tree that is built with some decisions as the illustration shows. Each decision is consist on choose two numbers and an operation to use with them.
There is not ambiguity with the order for use the operation, because the adding and the multiplication are commutative and the rest and division only can give us a positive number in the correct order of operations. With many couples of numbers, the division is not able to be realized in the way to get an integer number, in that case, the operation is ruled out.
In the first example of the illustration we have taken 10 and 7 and we have multiplied them. We remove from the list both numbers and add later the result of the multiplication. So, step by step, we have less numbers to operate.
The algorithm explores all the possible decisions until reach the objective number in each of the step been done.
For example, in the second case, the target number is 288, and we have found it in the fourth step so, we don't need to go on. The algorithm save the number that's more close to the solution in each step, so if we don't reach the goal we give as solution the closer number to it.
Is possible to do this exploration in a normal time? First we have to calculate the size of the decision tree.
In the first step we can choose between (6x5)/2 pairs of numbers = 15 and use 4 kinds of operations with them. So, supposing that the division is always able to be applied the number of solutions in the first step is 4 x (6x5)/2 = 60.
In general we have n numbers the possible options are:
4 x n (n-1) /2 = 2n (n-1)
So, the total number of options for the first five steps is:
2 ^5 x 6 x (5 x 4 x 3 x 2) ^2 = 2.764.800
So, close to 3 million possibilities. Ruling out the division the result would be:
(3/2) ^5 x 6 x (5 x 4 x 3 x 2) ^2 = 656.100
Close to 1 million possibilities. The final number should be between these two numbers.
There are some ways of going, as operate at first with bigger numbers or save the combinations of four numbers and avoid explore the same branches of the tree.
People to solve this problem use two strategies at the same time, in one of them we try to approximate to the target in a rude way, using the biggest initial numbers, and using multiplication, and later get close to the solution with lower numbers using adds and rests. For example in the illustration, we would multiply 75x4 = 300 and later we would try to get a 22 using combinations with the other numbers. This strategy doesn't drive us to the exact solution.
The second strategy more elaborated is to factorize the target number and try to get these factors. For example, 288 is 72x4 and 72 is pretty easy to get with the initial numbers. Each strategy put at beginning or at the end the multiplication because is the clue of the game, due to it gives us the bigger number of results.
4 / Algorithms Used
Sho rt description: This part is more dense and theoretical and contemplate the use of one of the famous algorithm iterative as is the A* and a version of it delimiting
s ome limits to make easier get the solution and find the correct way to solve the problem.
Also I will explain the code of the algorithm and the advantages and disadvantages that we can see in the use of it.
The Strategy that I will use to solve the problem of the Count Down Game is a Cost Algorithm in Iterative way with F-limits.
First of all talk about the algorithm of heuristic of searching as A*, they can need a big space that grow up in a exponential way with the long of the solution of the problem. This mean s that although the problem has a temporal cost easy to get, the space cost will make it be a unreachable problem.
The algorithm for this are called heuristic algorithm of searching with limitation of memory, and the most known is the IDA* (Iterative Deepening A*).
This is easy to implement and is a good solution for many problems, being the space cost linear with the long of the longest way to be explored. So, we convert the solution in an iterative process that can expand many times the same nodes.
Description of the Algorithm IDA*
This, Iterative Deepening A* consist on an algorithm of deepening in a iterative way where we use the heuristic information that we have about the problem to decide what node expand later, and to where go in one of the each iterations of the process.
This Algorithm, as each algorithm of iterative deepening, in each iteration will search using First in Deep. In this case the deepness is based on the heuristic information and will end when we will reach one node whose cost of the heuristic evaluation function:
F = g + h
It w ill be bigger than the actual limit of cost from F.
In this way, in each iteration we will look in all of the nodes with a cost of F lower or equal to the actual cost limit.
Also, we will evaluate all the nodes of the frontier of the tree, that have a cost bigger than the actual limit of F, and to calculate the limit of F, to calculate the limit of F that will be used in the next iteration. This new limit will be the lowest value of all the values F from the nodes of that frontier.
So for the Count Down game, it works like this:
We expand the root
From the Leave Nodes I take the lowest F-Limit
I delete the nodes.
I expand again all the nodes with a F value f>=f-limit
Save the new one
I delete the nodes
I expand again…
Code:
Characteristics of the algorithm:
IDA is an optimal and complete method of searching, so it always find one solution if this solution exist and it promise get the best solution of all.
This method has the same advantages and disadvantages of A, except the related to the space cost. In this way, IDA, presents advantages due to that it only need a proportional space to the length of the larger way explored.
This limitation in the use of memory is very positive but also has some disadvantages, because, looking for the solution in an iterative way we will expand many times the same nodes. This is something to take into account, because due to the characteristics of the problems to be solved we will get better or worse success.
In the best case, the temporal cost of IDA* can be very similar to A*, or even lower, because is a very simple algorithm and doesn't need insertions, deletes, reorder list of priorities and so on. T he best case will happen when we will have a problem where the heuristics will have values close to the real cost from the beginning of the execution, because we will do few iterations, expanding also few nodes in the first iterations.
In the worse case the temporal cost of the IDA * i s close to one algorithm of iterative deepening normal as the IDS (iterative deepening search), because, in each iteration we go deeper just in a level more in the tree. This happen in problems where the heuristics values are quite wrong, so in each iteration we only grow it up in one or two levels.
5/ Program in CLIPS
There is attached also:
ClipsWin to execute CLIPS on windows.
The program in clips to be executed.
6/ References
1) www.wikipedia.com
2, 3) http://www.i-math.org/files/file/prensa/prensa%20normal/31632245.pdf
4, 5, 6)
[Nilsson, 87].- "Principios de Inteligencia Artificial". Nils J. Nilsson. Editorial Diaz de Santos (1987).
[Rich, 94].- "Inteligencia Artificial". Second edition. Elaine Rich. Kevin K night. Editorial McGraw-Hill. (1994).
[Russell, 96].- "Inteligencia Artificial, un enfoque moderno". Stuart Russell. Peter Norvig. Editorial Prentice Hall. (1996).