Re: The n-knights problem

Lash Rambo <lr@xxxxxxxxxxxx> wrote:
russell kym horsell <kym@xxxxxxxxxxxxxxxxxxx> wrote in
news:eeg1d0$aum$1@xxxxxxxxxxxxxxxx:
It's not that humans use some very clever method to solve problems,
but that the heuristics used are so simple and fail so often. The
evolutionary pressure that has only the "best" arguments recorded, and
all the ones that failed lost to obscurity and supermarket tabloids --
that is what has many believing that "thinking" is the next best thing
to having prayers answered.
Several months ago I dabbled in genetic programming (the software kind).
I guess you could say GP uses a very non-clever method and a very simple
heuristic to do its thing. It's basically trial and error with a focus
on things that were promising in the past. Some say humans aren't really
much above that, themselves. (In fact, it seems you're making that case
now!) Yet, human methods scale much better with problem complexity than
GP does. It occurred to me one of the reasons for that is: humans are
able to frame what they're doing in logic, and use deductions (and
inductions) to prune away large, fruitless areas of the answer space.
Thus, my interest in the "pure logic" approach. (Of course, humans also
use "lossier" heuristics, like the ever-mysterious "intuition." I
figured I'd start with logic since people can at least agree on the
definition of that. :) )
[...]

Ah, yes, the *do* that prining thing. But I think you're beginning to
see this is not part of the machinery. One of the "reasons" that some
undedidability results obtain is that there's a difference between
"inside" the theory and "outside". Somewhat related to quantum theory
and mathematically dealing with the observer, there are limits on
what a closed system (e.g. "pure logic") can discover about or for itself.

With "everday thinking" this is all obscured. It's hard to tell where the
logic leaves off and the negative entropy coming in from ouside comes in. :)

Even sticking to "traditional research in logic" -- things that were being done
before computers were around -- it's not unusual that systems for solving
theorems (NOTE: not "proving" theorems) distinguiosh bewteen the actual
proof machinery -- the dumb stuff like trying to find a contradiction in
a set of assertions or (God forbid :) clauses -- and the "tactics" used
to drive the dumb machinery.

When Prolog was a kid there was a lot of talk about Resolution (unification)
being a "tool" and the "depth first, left to right" tactic as just being
the simplest method to drive it. It was often mentioned that other tactics
could be used, and maybe allow more "theorms" to be handled. But to complicate
matters it was only 10 sec before people started writing theorem provers
IN Prolog, and those TP's used all sorts of tactics themselves.

The kinds of "general" principles in everyday problem solving that apply
to your quest are things like thinking in terms of heirarchies, generalisation,
categorising (although related to heirarchies again), and tactial thinking.

Human thinking is also very rough -- "intelligence" is a matter of
not knowing when to quit. You need SOME solution to the problem inside
a deadline, even if the solution is convoluted and maybe doesn't completely
solve the problem. In some cases it's also intelligent to just guess, maybe
with some weighting on the guesses if some game-theoretic info is available
(or can be guessed at in a sub-problem).

It all sounds "too hard", but the thinking these days is it's a matter
of complexity. Many properties of systems simply "inevitibly emerge" when
they get big enough, provided they have the right internal structure that
will not rule out such things developibg.

Genetic or Evolutionary (slightly different from GP) Programing is one
way a simple system can "hack together" tactics and plans. I'm imagining
for your problem, some hybrid system that then can go on to simply
run the tactic through a more-0or-less conventional deductive logic process
like a theorem prover.


What I wrote in that little program -- although something of a joke --
illustrates some of these points. The initial "leap" was to divide the
chessboard into 2 populations (i) that had knights, and (ii) that
diud not have knights, and try to derrive a generalising rule for (i).
Then pick those rules -- a la GP -- that also allowed an estimate of
the size of the population.

Having come up with (e.g.) "black squares" as the generalisation,
we have an immediate lower bound on the "anwer" to the original prob

But to prove this may (or may not!) be the "maximum" we have to
eliminate SOMEHOW any value that's larger. That program -- supposed to
be simple enough to be computer-writable -- did that. In fact, opver-did that.
It tried to establish there was no way to divide up a chessboard so that
a total of more than 32 knights to be placed on it. It didn't consider
whether knights between regions might attach each other. It was content
to prove that if there was no "rough" way to divide up the chessbopard to
put more than 32 knights on it, there was no "accurate" way, eiother.

I.e. knowing that you didn't HAVE to deal with inter-region conflicts
was one key to "solving" the problem.

Other lemmas -- which can be generated automatically, as long as you
don't want them all (another group of logical theory deals with
whether something can or can not be "axiomatised", given the theory
may be undecidable) -- I implicitly used were things like
"if you divide up the board using method X and find a region of size S can
contain N1 knights at most,
and you find mthod Y shows N2, take the smaller as the tighter bound".

Those kinds of lemmas for this case can be generated without using
a theorem prover with mathematical induction, because the board is finite.

But stepping back now, we can re-consider some of th eother solutions proposed
for this probnlem. E.g. someone talked about "constraint programming".
This is more the kind of "proving" that is eqsy to generate automatically.
If you just want s/w to say "hey, boss, the answer is X" this is a fine method.
But, funny, internally constraint systems are solved more-or-less by
trial-and-error and various heuristics; and sopme of them are not guaranteed
to work all the time. The performance is not guaranteed to be of a better
order than simply "try all possibilities", but USUALLY has a better constant
of proportionaity :).

Linear programming is another kind of tool, related to constraints.
This also typically involves a lot of internal trial-and-error
and has pretty bad running time on worst case, but sometimes has very
fast running time. :)

But sometimes simple is best. I was recently asked to write a small
Sudoku (various spellings) program. It was *imagined* I gather that
I would use a standard backtracking method -- as does Prolog, internally --
to make the sequence of dcision that's needed to solve the problem.
But it turned out an optimistic/greedy method -- which assumes that
solving the constraints/conflicts in some determined order will normally
not require backtracking and will head more-or-less straight to the answer --
was good. Comparing the greedy method with a linear programming method
for the sme problems showed the greedy algorithm ran 100 times faster
for situations where there WAS a soilutiuon. Naturally, it looped forever
if the particular puzzle had no solution.


Oh, well. Time limiots come in handy sometimes, too. ALso non-logical. :)
.

Relevant Pages

  • Re: Complete Arithmetic?
    ... >>Building automated theorem prover is a great challenge, ... but still the abilities are way beyond expectations. ... >>Genetic programming can be regarded as a buzzword. ...
    (sci.logic)
  • Super computer to write apps for computers.
    ... the opening screen would be what type of app is to be ... proceed by heuristics to put together the required calculations, ... Since programming aids are already on the market, ...
    (sci.cognitive)
  • Re: Bash scripting....
    ... That's the logic you need to feed, time to join good programming ... bash, grep, sed and, or awk tools. ... Bash too is an interpretor, can provide you fundamental tools, so ... Guessing is heuristics; the heuristics are good for gaming theory, ...
    (comp.os.linux.misc)