Heuristic Problem Solving

This page will help address the conceptual portion of applying heuristics to problems, specifically crypto problems. The following heuristics will be evaluated:

H1 - if sameP(A,B)^zeroP(C,D,E)^oneP(G) then ((A/B) + zeroX(C,D,E))
H2 - if sameP(A,B) and goalP(C,D,E) then ((A - B) + goalX(C,D,E))
H3 - if zeroP(A) and goalP(B) and numbersP(C,D,E) then (B + (A * (C * (D * E))))
H4 - if sameP(A,B) and goalP( C ) and numbersP(D,E) then (C + ((A - B) * (D * E)))
H5 - if oneP(A) and zeroP(B,C,D) and onemoreP(E,G) then ((E - A) + zeroX(B,C,D))
H6 - if oneP(A) and oneP(B) and zeroP(C,D) and twomoreP(E,G) then ((E -(A + B)) + zeroX(C,D))
H7 - if sameP(A,B) and sameP(C,D) and twomoreP(E,G) then (E - ((A / B) + (C / D)))
H8 - if twoP(A,B) and zeroP(C,D) and twomoreP(E,G) then ((E - twoX(A,B)) + zeroX(C,D))
H9 - if sameP(A,B,C,D,E,G) then (A + ((B - C) + (D - E)))

The Heuristic Language

These heuristics use a language composed of predicates and functions which are combined into an ifthen statement, indicating that if the predicate(s) return true, then the answer is the following expression, using whatever function(s) are included. Here, we will define the predicates and functions that we have used so far:

The Predicates

  1. sameP - Takes in two numbers, returning true if they are the same number.
  2. zeroP - Takes in one to three numbers, returning true if the single number is zero, or if the numbers can be used to make zero.
  3. oneP - Takes in one number, returning true if the number is one.
  4. onemoreP - Takes in two numbers, returning true if the first number is one more than the second.
  5. twoP - Takes in one to three numbers, returning true if the single number is two, or if the numbers can make two.
  6. twomoreP - Takes in two numbers, returning true when the first number is two more than the second.
  7. goalP - Takes in one to three numbers, returning true if the single number is the same as the goal, or if the numbers can make the goal.
  8. numbersP - Returns true when given numbers.

The Functions

  1. zeroX - Generates a fully parenthesized expression that evaluates to zero using the numbers given to it.
  2. goalX - Generates a fully parenthesized expression that evaluates to the goal number using the numbers given to it.
  3. twoX - Generates a fully parenthesized expression that evaluates to two using the numbers given to it.

A Few Crypto Problems

A few crypto problems that can be solved with the above heuristics:

H1 - if sameP(A,B)^zeroP(C,D,E)^oneP(G) then ((A/B) + zeroX(C,D,E))

  1. Numbers = {3,6,4,3,2}, Goal = 1
  2. Numbers = {8,8,4,2,2}, Goal = 1
  3. Numbers = {6,9,3,4,4}, Goal = 1

H2 - if sameP(A,B) and goalP(C,D,E) then ((A - B) + goalX(C,D,E))

  1. Numbers = {5,4,1,2,5}, Goal = 8
  2. Numbers = {3,3,8,9,0}, Goal = 1
  3. Numbers = {1,2,3,4,4}, Goal = 9

H3 - if zeroP(A) and goalP(B) and numbersP(C,D,E) then (B + (A * (C * (D * E))))

  1. Numbers = {0,7,9,3,4}, Goal = 9
  2. Numbers = {3,0,6,4,2}, Goal = 3
  3. Numbers = {5,6,8,0,1}, Goal = 6

H4 - if sameP(A,B) and goalP( C ) and numbersP(D,E) then (C + ((A - B) * (D * E)))

  1. Numbers = {7,7,6,5,3}, Goal = 6
  2. Numbers = {2,2,1,5,9}, Goal = 9
  3. Numbers = {5,3,2,1,1}, Goal = 3

H5 - if oneP(A) and zeroP(B,C,D) and onemoreP(E,G) then ((E - A) + zeroX(B,C,D))

  1. Numbers = {1,0,8,3,4}, Goal = 3
  2. Numers = {5,3,2,1,5}, Goal = 4
  3. Numbers = {7,1,2,3,5}, Goal = 6

H6 - if oneP(A) and oneP(B) and zeroP(C,D) and twomoreP(E,G) then ((E -(A + B)) + zeroX(C,D))

  1. Numbers = {1,1,4,4,3}, Goal = 5
  2. Numbers = {1,0,5,2,1}, Goal = 7
  3. Numbers = {6,1,3,6,1}, Goal = 8

H7 - if sameP(A,B) and sameP(C,D) and twomoreP(E,G) then (E - ((A / B) + (C / D)))

  1. Numbers = {6,6,9,9,5}, Goal = 7
  2. Numbers = {1,1,2,2,3}, Goal = 5
  3. Numbers = {2,2,3,3,4}, Goal = 6

H8 - if twoP(A,B) and zeroP(C,D) and twomoreP(E,G) then ((E - twoX(A,B)) + zeroX(C,D))

  1. Numbers = {8,6,2,2,2}, Goal = 4
  2. Numbers = {2,1,0,5,6}, Goal = 8
  3. Numbers = {8,4,5,5,3}, Goal = 5

H9 - if sameP(A,B,C,D,E,G) then (A + ((B - C) + (D - E)))

  1. Numbers = {2,2,2,2,2}, Goal = 2
  2. Numbers = {3,3,3,3,3}, Goal = 3
  3. Numbers = {4,4,4,4,4}, Goal = 4

Calculating the Hexecutability of a Heuristic

An important aspect of a heuristic is how easy it is for a human to execute it. For future purposes, well call this hexecutability, and attempt to define a method for calculating the hexecutability of a heuristic.

If a heuristic requires the validation/interaction of more than two numbers in a nontrivial manner, more than one nontrivial operation, or a combination of the two, then the hexacutability will decrease proportionally with the number of nontrivial observations/operations.

With that definition, lets try and apply that to the heuristics we defined earlier, assigning each a value between 0 and 1, with 0 being the most difficult to execute, and 1 the easiest.:

H1 - if sameP(A,B)^zeroP(C,D,E)^oneP(G) then ((A/B) + zeroX(C,D,E))
This heuristic requires you to do two trivial validations, checking that there is a pair in the set of numbers, and that the goal is one. Then you must find an expression using C and D, C and E, or D and E, which must evaluate to 0 or E, D or C respectively, and then you must either multiply that expression (if it is zero) by the remaining number, or subtract the remaining number if it is not zero. Once that is complete, you must perform one more trivial verification in order to verify that you have zero.
Therefore: hex(H1) = 1.0 - 0.1 - 0.1 - 0.1 - 0.1 = 0.6
H2 - if sameP(A,B) and goalP(C,D,E) then ((A - B) + goalX(C,D,E))
This heuristic requires you to do one nontrivial validation, confirming that there is a pair in the set of numbers, and another trivial validation that the goal is either a member of the remaining numbers, or that a combination of the numbers can evaluate to a number needed in order to make the goal. This requires a similar number of interactions between the three numbers passed, with finding a difference, or multiple that can be made into the goal.
Therefore: hex(H2) = 1.0 - 0.1 - 0.1 - 0.1 - 0.1 = 0.6
H3 - if zeroP(A) and goalP(B) and numbersP(C,D,E) then (B + (A * (C * (D * E))))
This heuristic only requires two validations, that one is the number 0, and that another is the goal, which will be added to the product of the other numbers.
Therefore: hex(H3) = 1.0 - 0.1 = 0.9
H4 - if sameP(A,B) and goalP( C ) and numbersP(D,E) then (C + ((A - B) * (D * E)))
This heuristic requires the validation of A, B, C, and the goal.
Therefore: hex(H4) = 1.0 - 0.1 = 0.9
H5 - if oneP(A) and zeroP(B,C,D) and onemoreP(E,G) then ((E - A) + zeroX(B,C,D))
This heuristic requires you to validate that there is a 1 in the numbers, add one to the goal, and validate that the number is in the group of numbers, and then find an expression with the remaining numbers taht evaluates to 0.
Therefore: hex(H5) = 1.0 - 0.1 - 0.1 - 0.1 = 0.7
H6 - if oneP(A) and oneP(B) and zeroP(C,D) and twomoreP(E,G) then ((E -(A + B)) + zeroX(C,D))
This heuristic requires you to validate that A and B are one, add two to the goal and validate that that value is in the numbers, and find an expression that evaluates to zero, which means finding a pair or a zero and the remaining number.
Therefore: hex(H6) = 1.0 - 0.1 - 0.1 - 0.1 - 0.1 = 0.6
H7 - if sameP(A,B) and sameP(C,D) and twomoreP(E,G) then (E - ((A / B) + (C / D)))
This heuristic requires you to validate that there are two pairs, add two two the goal, and confirm that the value is in the numbers.
Therefore: hex(H7) = 1.0 - 0.1 - 0.1 = 0.8
H8 - if twoP(A,B) and zeroP(C,D) and twomoreP(E,G) then ((E - twoX(A,B)) + zeroX(C,D))
This heuristic requires you to add two to the goal and confirm that that value is in the numbers, find a number that is either double one of the other remaining numbers, or two more than one of the remaining, and confirm that the remaining two numbers are either a pair or contain a 0.
Therefore: hex(H8) = 1.0 - 0.1 - 0.1 - 0.1 = 0.7
H9 - if sameP(A,B,C,D,E,G) then (A + ((B - C) + (D - E)))
This heuristic is merely the confirmation that all of the numbers are the same, which is one trivial validation.
Therefore: hex(H9) = 1.0

Calculating the Applicability of a Heuristic

Another important part of a heuristic is how applicable it is to the situation it is used in. There are several ways to figure out what the applicability of a heuristic, one of which is running through trials, dividing the number of times the heuristic was applied. That is the method I chose to follow for finding the applicability of the heuristics. I created a prolog program which does just that. You can find the code for it here. The following are the probabilities found, with a value from 0 to 1, with 1 being always applicable, and 0 being never applicable.

H1 - 0.04
H2 - 0.36
H3 - 0.08
H4 - 0.21
H5 - 0.03
H6 - 0.006
H7 - 0.01
H8 - 0.0005
H9 - 0.00001

For the last two of these heuristics, my program would only return a value of 0, so for heuristic 8, I estimated that it must be some degree smaller than the previous heuristic, which was only applicable ~1% of the time, to the point where it would not show up. This led me to estimate that it would be used ~0.05% of the time. For heuristic 9, I attempted to figure out mathematically what the probability of the situation where the heuristic is applicable. From that perspective, I calculated that there are only 10 problems which would have the heuristic be applicable. With 1000000 possible problems (10 possible goals and 105 possible combinations of numbers), that would make the probability of the heuristic being used 0.00001.

Some new Heuristics

The heuristics defined so far are far from all of the heuristics that you may need in order to create a heuristic problem solver. So, lets add a few more heuristics and predicates to our system:

The Predicates

  1. oneHalfP - Takes in two numbers, returning true if the first number is one half of the second number
  2. doublegoalP - Takes in one to four numbers, returning true if the single number is double the goal, or if the numbers can be used to make double the goal.
  3. newgoalP - takes in four or five numbers, returning true if the first three or four numbers can be used to make the last number.
  4. oneP - Now takes in one to four numbers, returning true if the single number is one, or if the numbers can be used to make one.

The Functions

  1. oneX - Generates a fully parenthesized expression that evaluates to one, using the numbers given to it.
  2. doublegoalX - Generates a fully parenthesized expression that evaluates to dobule the goal number.
  3. subgoalX - Generates a fully parenthesized expression that evaluates to the last number given to it, using all of the numbers before it.

The Hueristics

  1. H10 - If oneHalfP(A,G) and oneP(B,C) and oneP(D,E) then (A * (oneX(B,C) + oneX(D,E)))
  2. H11 - If twoP(A) and doublegoalP(B,C,D,E) then (doublegoalX(B,C,D,E) / A).
  3. H12 - If oneP(G) and newgoalP(B,C,D,E,A) then (subgoalX(B,C,D,E,A) / A).

Problems, Hexecutability, and Applicability

Lets look at some examples of when these heuristics can be applied, and what their human executability and applicability might be.

H10

Examples:

  1. Numbers = {8,8,2,6,6}, Goal = 4
  2. Numbers = {6,2,3,3,5}, Goal = 6
  3. Numbers = {4,9,8,5,5}, Goal = 8

Hexecutability: 0.7

Applicability: 0.027

H11

Examples:

  1. Numbers = {5,5,7,2,2}, Goal = 6
  2. Numbers = {6,4,8,2,3}, Goal = 5
  3. Numbers = {3,9,5,2,8}, Goal = 4

Hexecutability: 0.6

Applicability: 0.25

H12

Examples:

  1. Numbers = {2,6,1,8,7}, Goal = 1
  2. Numbers = {8,9,7,4,3}, Goal = 1
  3. Numbers = {0,3,8,9,6}, Goal = 1

Hexecutability: 0.5

Applicability: 0.09

You can find a full reflection on this assignment here