What Do I Know About the Problem

Problem

Solving

What is the problem

What do I know about the problem

How hard is the problem

Reduction of information to Relevant information

Apply Inductive and Deductive reasoning

Problems of interest

What is the Problem

Define the goals or subgoals to be attained

- fixed vs. moving target

- separable vs. integrated

- absolute vs. relative

- predictable vs. random

See what is given

- specific vs. generalizeable facts

- perfect vs. imperfect information

- certainty vs. uncertainty

- existing knowledge base vs. new area

- axioms and proofs vs. target shooting

Extrapolate from the "natural language" of a problem to the "natural language of the machine

- need a specific (not vague) description

- need all of the rules (constraints)

- need to "quantify" the goals

- need to handle multiple objectives

What do I know about the problem

Determine the relevant body of information

- is there a literature (start with Wikipedia & Google)

- are there theorems

- is this similar to a solved problem

- what subject area is most appropriate

- is this problem separable or decomposible

Pattern recognition and feature selection

- are there solved patterns that can be applied

- are there features that are similar to solved problems

- are there analogies that are apt

e.g. Evan's analogy (Find a transformation, apply it, find the corresponding symbol)

Representation of data

- need a knowledge representation

- must choose a data structure

- how is new knowledge added?

- do we need to learn?

- how large can the data structure get

(both in the problem and in the computer)

How Hard is the Problem

Problem difficulty is measure in terms of “n”, the size of the problem, the number of inputs, the size of the “playing field”, etc.

For each problem, need to define how “n” is measured.

Problems are classified as “EASY” or “HARD”, with the following subclassifications:

EASY:

Trivial: Small, constant effort, independent of any “n”

Practical: Effort is o(log(n)), o(n), o(n*log(n)),

o(n*log(n)*log(n)), …

Polynomial: Effort is o(n*n) or greater, but bounded by a polynomial in “n”

HARD:

NP Hard/NP Complete: Can find no algorithm that works in polynomial time. But we can verify that something is a correct answer in polynomial time. A computer with infinite parallelism could solve the problem in polynomial time.

Exponential: Both computation of a result and verification of a result provably take exponential time

Impossible: Provably impossible, even with infinite speed, infinite parallelism, infinite memory, and infinite time.

References:

· Dreyfus, Hubert (1972), What Computers Can't Do, New York: MIT Press, ISBN 0-06-090613-8

· Dreyfus, Hubert (1979), What Computers Can't Do, New York: MIT Press, ISBN 0-06-090624-3

· Dreyfus, Hubert (1992), What Computers Still Can't Do, New York: MIT Press, ISBN 0-262-54067-3

Reduction of information to RELEVANT information

May need to develop a "heuristic" for hard problems

Defn: A heuristic is a trick, a rule of thumb, a stratagem, etc. which drastically limits the search for solutions in large spaces - ideally not throwing away any "good" answers - hopefully retaining at least one "good" answer.

Heuristic functions measure the "goodness" or a "figure of merit" of a particular choice, action, subgoal, goal, or proposed solution.

Heuristics MAY lead in the wrong direction. This is sometimes called "going down the primrose path" or "going down the garden path"

Examples:

In Othello, might think that the largest number of opponents pieces flipped in a move is a good heuristic (it is not). A better heuristic is number of your pieces that the opponent cannot ever flip.

In Chess, might think that the greatest material advantage after a move is a good heuristic (it is not). This heuristic opens up the player to "classic" sacrifices.

In Checkers, might think that the greatest number of pieces captured in a move is a good heuristic (it is not). This heuristic ignores what the opponent might be able to recapture

There needs to be both major (winning) and minor (positional/power/strategic/mobility) advantage

Apply inductive and deductive reasoning, as appropriate

Need to generate measurements

Need measurements to see how close we are to a solution

Can work from both ends

Need heuristic techniques

Sometimes a figure of merit can be derived in a heuristic to find a step that is "good enough" - especially in a game

Problems of interest:

Problems where “n” is the number of digits of accuracy:

Newton’s method

Successive approximations of Pi using pi/2 = 2/1 x 2/3 x 4/3

x 4/5 x 6/5 x 6/7 x 8/7 x 8/9

Golden ratio using Fibonacci starting at 0, 1

Golden ratio using Fibonacci starting anywhere

Problems where “n” is the number of entries in an array, table, or file:

Sorting

Searching

Statistical computation

Payroll

Missionaries and Cannibals (n of each, canoe for m)

Problems where a proof is desired for every integer or rational number or real value, “n” is the number of steps in the proof:

Collatz’s conjecture (3n +1 or divide by 2 problem)

Problems where “n” is the size of one side of a square:

Tic-Tac-Toe (on an n x n grid – not just 3 x 3)

Sudoku

Travelling Salesperson

Pairing people for a dance