tcj_07 1984-05 02.03.pdf

(2117 KB) Pobierz
THE COMPUTER
VOl II No.3
JOURNAL~
$2.50 US
For Those Who Interface, Build, and Apply Micros
Heuristic Search in Hi-QpOl,e2
Build a High-Resolution S-100
Graphics Board
Part Two: Theory of OperationpOlle12
Multi-user:
Etherseriespale 17
System Integration
Part Two: Disk Controllers and CP/M
2.2
System Generationpa
le21
New ProductspOl,e28
The Computerist's
Calendar~,e2o
Editor's Page
The End of the "Programmer Prima Donna"
The computer software market is changing rapidly
now that more computers are being used in offices
and homes by non-computerists. Until recently most
of the microcomputers were used by people
interested in computers. These knowledgeable users
were willing to make do with awkward programs or
rewrite them, but the market is changing and has
now reached a point where programs will have to be
designed for the end user in order to be successful.
When microcomputers first became popular. only
programmers knew enough about these marvelous
new devices to foresee what they could do. These
pioneering individuals wrote business programs. and
we were amazed at the power available in word
processors. data bases. and other useful programs.
These early business programs were the primary
reason for the rapid expansion of micro sales.
Unfortunately. the programmers (who were the
only ones to understand the micro) did not
understand the requirements of a business system.
The result was that hundreds of programs were
developed which were difficult to use. and which
almost
did the job. The programmers worked in
isolation and produced elaborate programs which sold
because they were so much better than working
without a computer.
The programmers were "high priests" who decided
what the customers should use. and the customers
did not have enough experience with computers to
intelligently evaluate the offerings. The programmers
also lost sight of who their users were. and were not
really interested in understanding their needs. The
software industry talks about alpha and beta testing
of programs. but this testing was (and perhaps still is)
done by experienced computerists. The testing should
really be done by the lowest level of people expected
to use the program.
If
you are selling a program
which will be purchased and used by other
programmers it should be tested by programmers.
If
the program will be used by people on the street. it
should be tested by people on the street.
It
took a
long time for other industries to realize that they had
to identify their market. really visualize the
individuals expected to lay their cash on the counter
and put the product to use. and then spend enough
time in the users' environment to understand what
they did in a typical work day.
If
you want to test a
program for real estate offices. you should load the
program and a computer into your car, and drive
around until you find an office whose personnel
represent the least knowledgeable segment of your
market. Offer them whatever cash it takes to have
them try your program using the computer you
supply, give them the documentation. and then sit in
the corner and watch what happens.
If
they have to
ask you a question. or you have to point out
something they are doing wrong. the experiment has
failed and you had better go back and make revisions.
You may also find that while the program is easy to
understand and put to use. it just may not perform
the required functions.
The problem of non-performing software became
very evident to us while we were searching for a data
base for use on our new CP/M machine. We had been
using
The General Manager
by Sierra On-Line on our
Apple~
• and were quite satisfied with it. but we are
changing to a S-100 system and need a simple data
base. So far the offerings we have seen for CP/M are
expensive, hard to use. and are incapable of handling
our mail list needs. We also reviewed some mail list
programs. but they failed to handle our needs for 3rd
continued
o~
page 25
Editor/Publisher
A rt Director
Technical Editor
Technical Editor
Production Assistant
Contributing Editor
Art Carlson
Joan Thompson
Lance Rose
Phil Wells
Judie Overbeek
Ernie Brooner
The Computer Journal'!> is published
12
times
a
year. Annual subscription is
S24
in the US.,
S30
in Canada, and
139
in other countries.
Entire contents copyright
©
198.1,
by The
Computer JournaL
Postmaster: Send address changes to: The
Computer
Journa~
P.O. Box
1697,
Kalispel~
MT
59903-1697.
Address all
editoria~
advertising and
subscription inquires to: The Computer
Journa~
P.O. Box
1697,
Kalispel~
MT
59903·1697.
2
The Computer Jourr:a,
HEURISTIC SEARCH IN HI-Q
by Henry W.
Davis
Computer Science Department
Wright State University, Dayton, Ohio
Computer games challenge humans to be smart. Have
you ever wanted to reverse the role? This article is about
how to write a program which makes the computer appear
as smart as a human, or smarter!
It
also demonstrates a
technique called "heuristic search," an important component
in many artificial intelligence systems.
Our medium is "hi-Q," a popular puzzle played in a certain
chain of restaurants by customers who are waiting for their
food. When I first encountered hi·Q, I was so intrigued that I
decided to share it with my students in an artificial
intelligence course at Wright State University. The course
includes heuristic search algorithms. On two occasions, I
asked students to try these algorithms on hi-Q. They used a
wide variety of languages and computers, from BASIC,
FORTRAN, and PASCAL on home computers to
SIMSCRIPT on a CYBER. They obtained a number of
fascinating results showing that heuristic programs can do
quite well at hi-Q, considerably better than most humans.
In this article, I will describe the basic algorithm used
along with specifics of the hi·Q environment. Then I would
like to share with you some aspects of a particularly nice
program written by Ed Dudzinski, a former masters degree
student in computer science at Wright State. Ed currently
works on software optimization for array processors at the
Wright-Patterson Air Force Base in Dayton, Ohio. His
program, written in FORTRAN, is interesting because it
performs well while demanding little memory - less than
40,000 bytes in a home computing environment.
Nevertheless it has analyzed game situations involving as
many as 190,000 different board configurations.
Our results are only a beginning.
It
is still not clear what
the best computer hi·Q strategy is, even for the simplest hi-
Q version described below.
, o.
,1lf
1
4
5
2
6
3
7
8
9 10
11
12 13
14 15 16 17 18
19 20 21
Figure 1:
HI-Q
is played on a board
With POSitions patterned as shown
above In the center of each num·
bered square IS a hole for a Single
peg. Initially 20 pegs are placed
randomly into the holes The pegs
may Jump one another hOrIZontally.
vertically or diagonally as long as
they land In a vacant location
Jumped pegs are removed from the
board and the goal is to remove all
but one peg
game was initialized by
arbitrarily
choosing
hole 6 to be empty. The
game is easily played
and studied by simply
drawing a big version
of Figure 1 (without
the numbers
l
and using
pennies instead of pegs.
In fact, for this reason
it is sometimes called
the "20-penny puzzle."
The version just
described will stump
most people for quite
a while. Try it! For the
very ambitious there
are harder versions
coming up.
i'
••
,,11
,ill
·It
The Basic
Algorithm
,J
The Rules of
Hi·Q
A common version of hi-Q has 21 holes drilled into a piece
of wood. Figure 1 shows the pattern: there is assumed to be
one hole in the center of each of the numbered squares. The
puzzle begins with pegs in 20 of the holes. The goal is to
"jump and remove" 19 of these pegs, ending with only one
peg on the board. The rules are as follows:
1)
A peg can be moved only by jumping and thereby
removing a single adjacent peg.
2) A peg can jump either horizontally (eg., from hole 5 to
hole 7), vertically (eg., hole 17 to 7), or diagonally (eg., hole 7
to hole 15).
3) The jump can be made only if the destination is empty
(eg., hole 7 in a 5-to-7 jump) and the jumped hole (hole 6) is
full; the jumped peg is removed.
Figure 2 shows the first three moves of a typical game. This
The basic hi-Q search
algorithm is a variation of Nils Nilsson's "ordered search
algorithm" which may be found in Chapter 3 of his 1971
book Problem solving Methods
in
Artificial Intelligence. This
is also the "graphsearch procedure in Chapter 2 of his 1981
book Principles of Artificial Intelligence.
It
is shown in
Figure 4 and explained below.
The many possible configurations of the hi-Q board are
called
states.
The states are connected by arrows, or
directed arcs, which represent legal moves transforming one
state into another. The result is a directed graph, called the
state space.
Figure 3 shows a very small portion of the state
space for the hi·Q puzzle whose initial state is Figure 2a.
't
,,~
a
b
c
d
,,"
Figure 2: A typical initial state for hi·Q IS shown
In
Figure 2a Any
square could be left empty, but
In
thiS case It'S square number 6
(using the numbering scheme of Figure
1).
Figures 2b, 2c, and
2d show the results of typical first, second and third moves For
example, in the third move, the peg at 1 jumps the peg at 6 and
lands
In
location 12.
The Computer
JOJma,
5
Compute f (START), store rt wrth START. and insert START Into Oper,
CURRENT~NULL: FOUND~'FALSE'
o a a a a
c o o
0,
C'
0
0
0
I
:~
r---
a c a
0
0
0
0
0
10
1
a a
a
0
0
0
~
0
I
I
ro
10
o
0
0
0
0
i
C
~
'00000'
0
0
0
o!
~
~OOOOI
~
o
a
~
o
o
0
0
0
0
0
1
a
!
DO UNTIL OPEN
IS
empty or FOUND = 'TRUE'
CURRENT(;- node on OPEN with least f value
(resolve ties lexically)
Insert CURRENT Into CLOSED and delete it from OPEN
Generate all successors to CURRENT
IF some successor is a goal THEN
Report solution (using search tree)
[
FOUND~'TRUE'
ELSE
For each successor M of CURRENT DO
f M is not on OPEN or CLOSED THEN
Compute f( M) and store
It
With M
,rect a "parent pOinter" from M to CURRENT
(for search tree)
[ [
Insert M into Open
IF FOUND= 'FALSE' THEN report failure.
Figure 4: The basic hi-Q search algOrithm starts by putting the
initial puzzle configuration on the OPEN list. In the main iteration a
node is removed from OPEN and its successors are generated by
applying all legal moves. If a goal (only one peg left) is not found.
then those successors not previously seen are added to OPEN If a
goal is found, then search tree pointers enable the program to
report the route it discovered.
Figure 3: A very small portion of the
puzzle is shown. The different board
states,
or
nodes
Arrows indicate legal
another. The whole construct of states
directed graph, called the
stale space.
"state space" of a hi-Q
configurations are called
moves from one state to
and legal moves forms a
The algorithm "knows" the legal moves and takes as input
an initial state.
It
performs all legal moves on the initial
state. generating new states. The legal moves are then
performed on some or all of these new states obtaining still
more states, etc. Intuitively, this process has the program
"wandering around the state space" looking for a goal
state - much like a rat in a maze. Obviously if this is to
work, the program needs some bookkeeping devices to keep
track of where it has been, how it got there, and where it
might still go. It also needs a decision mechanism to
determine where to go next. The key ingredients for doing
this are the
open list.
the
closed list.
the
search tree,
and
the
evaluation function.
each described below.
1)
OPEN is a list of states. or nodes. in the state space
which the program knows about but to which the legal
moves have not yet been applied. Initially the beginning
puzzle configuration is placed on OPEN. In a typical cycle of
the search procedure a node is removed from OPEN and all
legal moves are applied to it obtaining a set of
successor
nodes.
One says that the node removed from OPEN was
expanded
and that the successor nodes were
generated
from
it.
2) CLOSED is a list of nodes which have been removed from
OPEN and expanded. Why bother to remember a node we
have already expanded and hence seem to be through with?
The reason is so that whenever we generate a new node we
can tell whether or not it has been previously generated.
Namely, we compare the new node with the entries on
OPEN and CLOSED.
If
we find a copy of it there. then we
will behave differently than we would had the node not been
previously discovered.
3) When a new node is generated, the program will place in
its record of the node a pointer to the node's parent. The
resulting structure of nodes and pointers forms a tree, called
the search tree. The initial problem state is the tree's root.
The sole purpose of the search tree is to enable the program
to find its way back to the start once it has found the goal.
By following the parent pointers back to the root. a listing of
the legal moves from start to goal is obtained.
4)
We come now to the crucial question: In what pattern
shall the program "move through the state space?" This is
equivalent to asking "in what order shall it expand the
nodes which are on OPEN?" This decision is made by an
evaluation function. f. When f is evaluated on a puzzle state
it returns a real number: the smaller that number is. the
more likely it is felt that the given state is close to a goal
state. The search program expands that node on OPEN
whose f value is lowest. Most of the apparent "smartness" of
our program is due to f. Without a good evaluation function,
all is lost.
Let us examine the algorithm of Figure
4
more closely. In
the outside iteration, the program removes from OPEN the
"most promising node" (lowest f value), puts this node on
CLOSED and then expands it. obtaining all legal successors.
If
there is no solution, then those nodes not seen before are
placed on OPEN. and another iteration is made. CURRENT
is a location which references the node now being expanded.
If
several nodes on OPEN are tied with the lowest
f
value.
then the "lexically" lowest is chosen. This simply means that
the program views the board description as a string of
'
4
The Computer Journal
.
..
example. The darkened path shows the particular solution
which is discovered. The numbers beside each node give its f
value. As the algorithm iterates, the search tree is built up
level-by-level, left-to-right. A completed level in the search
tree corresponds to having investigated all nodes within a
fixed distance of START in the state space. Due to this
systematic expansion from START in all directions, the
algorithm is called "breadth first." It is an example of a
"blind search" because no heuristics are used.
Another type of blind search is called "depth first"
because it always favors expanding those nodes which are
furthest away from START. To achieve it in the puzzle of
whenever a node
Q
is
generated from a node P, we set f(Q)
=
f(P) -
1.
The resulting
search tree and solution obtained is shown in Figure 5c. A
deeper and more costly goal is found than in the breadth
first case; however. fewer nodes are generated. For hi-Q it is
very important to go deep quickly. More about this shortly.
Now suppose we would like to have a more-or-Iess breadth
first search tempered by some heuristic information. For
example, suppose a hunch tells us that whenever the
program generates a square node (eg., like d or f in Figure
Sa) then it is probably close to a solution and it should keep
moving in that direction. A triangular node Oike j in Figure
Sa) is similar but not as good. Then we might define the
"heuristic function" h by:
h(N)
=
0
if N is square
h(N)
=
1 if N is triangular
h(N)
=
4 if N is round
The heuristic function punishes nodes for being round or
triangular, but the latter less. Define f
=
g
+
h. The effect of
g is to "add breadth to the search."
If
the program gets
carried away following square and triangular nodes deeply
into the state space, then sooner or later g will grow and
force it back to shallower nodes which it ignored earlier. In
Figure 5d this f is applied to the puzzle of Figure Sa. It
happens to work very well: the least cost goal is found while
fewer nodes are generated or expanded than with the other
evaluation functions. Setting f
=
h and dropping the gout
works just as well in this case. In general, however.
conventional wisdom suggests leaving the g component in
for the reasons mentioned above: h might sometimes lead
one astray and g helps cover for that event. (It's easy to
alter Figure Sa so that this happens,)
,.",
,""
'Ill
,<it
\0
"111
Fi~ul'~
5A,
set
flgTARTl
=
0;
,<it
·5
\e
Figure 5: The state space for a fictitious puzzle is shown
In
Figure
5a. Figures 5b, 5c, and 5d show the search tree and solution
(darkened path) found by three evaluation functions In 5b, f
rewards being close to START, yielding a breadth first search In 5c,
f rewards being far away from START, yielding a depth first search
In 5d, the f of 5b has added to it a heuristic component which
punishes nodes for being circular, less for being triangular and not
at all for being square. The numbers beside each node are the f
values (see article for computation details). It
IS
assumed that ties
are broken lexically (eg , in figure 5b node a is expanded before
node b)
i,'~
,oli
'Ill
characters and chooses the smallest string relative to
normal sorting of character strings. Alternatively. such ties
could be broken "arbitrarily." But it turns out that the
success of many evaluation functions on a particular initial
puzzle varies tremendously (sometimes by a factor of
10001
with how such ties are broken. Rather than leaving the tie-
breaking up to an accident of coding, we choose to make it
an explicit part of the algorithm. For one thing. our results
are more easily duplicated by others. We return to this
problem later because it raises the question of how we can
properly judge the effectiveness of an evaluation function.
",.
,j,j
,,!il
Evaluation Functions:
The Main Source of Intelligence
It is important to understand how different evaluation
functions can alter the search pattern. Figure 5 illustrates
this. In Figure 5a the state space for a fictitious puzzle is
shown. Some of the states are shaped as circles and others
as triangles or squares. Each state is given a name (eg.•
S.a,b. or
G21
and there are two goal states. For each node N
in Figure
Sa
let g(Nl be the least distance from S to N that
the program has seen at a given instance. where we assign
to
each directed arc a distance of
1.
One common practice is
to
set f(Nl - g(Nl. Figure 5b shows the search tree that
results when the algorithm of Figure 4
is
run on this
The Hi-Q Landscape
Since the state space for hi-Q is finite, even a blind search.
like breadth first. will eventually find a goal. The solution it
reports will require only 19 moves because all solutions
require exactly 19 moves. On what basis, then, can we say
that one computer search heuristic is better than another?
There are several criteria which students in my classes have
used:
.1
The number of nodes generated: An algorithm which
consistently generated fewer nodes then others would seem
to
be
working less hard.
bl
The number of nodes expanded: When a node is
expanded the algorithm is saying, "I think the goal is in this
,M
,M

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin