LAWS@SRI-AI.ARPA (06/01/85)
From: AIList Moderator Kenneth Laws <AIList-REQUEST@SRI-AI>
AIList Digest Saturday, 1 Jun 1985 Volume 3 : Issue 71
Today's Topics:
Administrivia - Mailer Problems,
Games - Computer Scrabble,
Query - Self-Reproducing System,
Applications - Tax Rules,
PROLOG - The Berkeley PLM Benchmarks,
Humor - Contest,
Games - Cheating at Chess,
Conference - Submission Date for AIE
----------------------------------------------------------------------
Date: Fri 31 May 85 22:54:09-PDT
From: Ken Laws <Laws@SRI-AI.ARPA>
Reply-to: AIList-Request@SRI-AI.ARPA
Subject: Mailer Problems
SRI-AI has been down for five days, since Sunday morning.
If you have sent mail to AIList during that time, you
should probably send it again.
-- Ken Laws
------------------------------
Date: Thu 30 May 85 11:47:54-EDT
From: John R. Kender <KENDER@COLUMBIA-20.ARPA>
Subject: Computer Scrabble
What is the state of the art in computer Scrabble?
I am aware of a company called Ritam that produces a device called
Monty that is "pretty good", according to the president of the
Scrabble Players' Club. I have no idea what, if any, AI techniques it
uses. Further, the Club president knows of no tournaments involving
computers. At first glance this does not appear because the game
would be trivial to program, rendering computers invincible to humans
or making games between them boring.
My interest is more in using the game as a task domain in an AI
course. Thus:
o What work has been done? References? Software? Anecdotal
remarks?
o How deep is the strategy of the game: is it more on the level of
blackjack, or of go? Are there commonly known or articulated
heuristics? How far ahead do human players look? Is a multi-
handed game qualitatively different from a two-handed one?
o Assuming a word data base, is Scrabble a game of difficulty
appropriate to the level of a homework assignment?
a term project? a Master's degree project? Would it be worth
doing: are their sufficiently interesting issues of representation,
search, and control that are not overwhelmed by bookkeeping details
or brute force methods?
------------------------------
Date: 24 May 85 06:35:12 EDT (Fri)
From: zim@mitre.ARPA
Subject: size of self-reproducing system; intelligence?
Q: What's the minimum "size" for a self-reproducing thing? For an
"intelligent" thing??
These are half-baked questions and I need help in sharpening then up.
Maybe this subject has been all worked out and all I really need is a few
pointers to the appropriate literature? I don't know... Here are some
preliminary thoughts, to clarify the question I'm trying to ask:
A measure of "size" probably needs to include the complexity of the
environment ... for instance, a virus takes advantage of a highly-ordered
set of cell mechanisms and can reproduce with only a few thousand (or so?)
bits of information ... its "size" measure should be bigger than the amount
of DNA in it might seem to imply. All living creatures make use of some
of the physical laws of the universe (mostly chemistry), and should be
charged some for that in "size" measure ... though they probably shouldn't
be charged for remote-seeming physics such as general relativity, high-energy
particle physics, etc. (On the other hand, maybe the information "cost" of
those theories is tiny compared to the more immediate environmental "size"
around a living cell??) The problem is to define a "relevant" environment.
Self-reproducing cellular automata that I've heard of seem to
generally require billions and billions of cells or so (as in
Conway's LIFE); they live in a very simple universe, where there is almost
no information stored in their environment. On the other hand, most of
the self-reproducing automata I've seen are quite huge and inefficient,
because they're structured to be comprehensible to people....
Are the questions of self-reproduction and intelligence related? I'm
thinking vaguely about notions of Godel's theorem, complexity of human
brains, self-reference, etc. Maybe an appropriate size measure would come
out about the same for a single cell and for a brain?? Presumably brains
should be charged for their structure, not for the details of how neurons
metabolize, in a size measure.... On the Godel's theorem again, the coding
schemes needed in producing the self-referential statement typically seem
to require really huge numbers (unless a lot of information is hidden
somewhere else). Maybe one could define "intelligence" in terms such as
"capable of formulating Godel's theorem", or some other definition (with
malice aforethought) to make the self-reproducing size measure come out
the same as the intelligence size measure?
So to restate the question, can one define an appropriate measure and prove
that any self-reproducing (or intelligent?) system has to be at least of a
certain size?
This might have interesting implications as to how hard it will be to make
AI systems with human-like consciousness ... how many logic elements or gates
will be required, how many gigaflops (or gigalips) are needed to think at a
human pace, etc....
-zim@mitre
[I remember John DeVore at K-State building a self-replicating
2-D binary pattern as his master's project circa 1978. I'm sure it
had millions of cells rather than billions. AIList readers interested
in such questions should be aware of the Self-Org@MIT-MC discussion
list. -- KIL]
------------------------------
Date: Mon, 20-May-85 09:52:10 PDT
From: (David Sherman) pesnta!dave@UCB-Vax
Subject: Suggestions needed for tax rules
[Forwarded from the Prolog Digest by Laws@SRI-AI.]
I am trying to design a system which will apply the rules of
the Income Tax Act (Canada) to a set of facts and transactions
in the area of corporate reorganizations.
This is not a typical "AI and law" problem, because the Income
Tax Act is highly technical and extremely specific about what
rules apply and when. To the extent there is "open texture", or
issues which require legal judgment (e.g., whether an amount
is "reasonable"), I assume the lawyer using the system will
provide the judgment as an input fact. The problems are therefore
quite different from those addressed by McCarty@Rutgers' TAXMAN
program, because the approaches of the Income Tax Act and the
Internal Revenue Code are very different.
The difficulty in programming the system is simply the complexity
of the Income Tax Act. On a given transaction, a large number of
rules have to be examined to determine possible tax effects. Some
of these rules create new facts (e.g., a deemed dividend or a deemed
disposition). The passage of time is very important: steps happen
in a particular sequence, and the "state of the world" at the moment
a step is taken is crucial to determining the tax effects. In the
context of corporate transactions, this state includes such things
as who controls a corporation; who owns what assets; the residence
and status of and relationships among taxpayers; cost bases and
proceeds of disposition; and so on.
(My background to this: I'm a tax lawyer and an experienced C
programmer. I'm doing this work towards an LL.M. thesis.)
I've tried several approaches to this field before. Last year
I did a small version in C which uses an event-driven simulation,
and as it encounters each event calls a function for each rule in
the database to generate new events and tax results. (Incidentally,
if anyone wants a copy of that paper, "Towards a
Comprehensive Computer-Based Problem Solving Model of the
Income Tax Act: A Suggested Approach and Implementation of
Examples from Corporate Reorganizations", let me know.)
One of the problems with the C implementation was designing the
order in which the rules should be applied. For even the small subset
I implemented, this was awkward and difficult.
I came across Prolog at an ICS course on expert systems a few
weeks ago. It looks like the perfect tool for much of what I want
to do. Besides the workshops at the course (taught=sdcsvax!vis!greg),
I've now read Clocksin & Mellish and skimmed through How To Solve
It In Prolog.
The definitional stuff is fine. Using C-Prolog 1.4 on a VAX (not this
machine), I've already coded the Income Tax Act's definitions for
things like "resident", "private corporation", etc.
The problem I have (if you've read this far, thank you!) is how
to deal with _time_. I suppose the overall model I need to work with
is one of "changing states", where a transaction (e.g., X transfers
property to corporation Y in exchange for shares in Y) changes the
world from state A to state B, and the rules can examine differences
between the states to determine the effects. But then how does that
jive with definitional tests which may need to look back in time
(e.g., a corporation is resident in Canada in a given year if it
meets certain conditions and it was resident in Canada, or carried
on business in Canada, in the previous year. This is a perfect
recursive definition for Prolog, and I've implemented the rule,
but only as a fixed definition, not as part of a "changing
state" system.)?
I guess part of my problem is that I'm not working in an
AI department, or even a Computer Science department, and
so I don't have knowledgeable people to bounce my ideas off.
If you have any suggestions as to approaches I should be taking,
I'd greatly appreciate hearing from you. I'd be happy to send you
a copy of the code I've written so far to explain what I mean.
(You could even learn all about Canadian tax law!)
-- David Sherman
The Law Society of Upper Canada
Osgoode Hall
Toronto, Canada M5H 2N6
(416) 947-3466
------------------------------
Date: Wed, 22 May 85 10:47:11 pdt
From: (Tep Dobry) Tep%ucbdali@Berkeley
Subject: The Berkeley PLM Benchmarks
[Forwarded from the Prolog Digest by Laws@SRI-AI.]
At the Warren Abstract Machine Workshop a few weeks ago
I was asked to publish the set of benchmarks programs I've
been using on my simulator for the Berkeley Prolog
Machine(PLM). I've finally got them all collected together
in Prolog form (CProlog) and have sent them to the Digest.
They're really too big to just publish in the Digest, so
they are being set up in a directory in the PROLOG directory
at SU-SCORE. There are 11 files with a total of 400 lines.
Since our machine is based on compiled Prolog, the top level
queries are also compiled in, generally as the predicate
main/0.
The benchmarks were primarily chosen to exercise all of
the features of the PLM, not for any complexity of program-
ming. About half of them come from Warren's thesis, and the
others we've added here. Our original performance figures
were based on simulations of hand compiled versions of these
benchmarks. We are currently looking for larger, more com-
plex benchmarks to run on the hardware when it is available.
So I'd be interested seeing large benchmarks sent to the
Digest.
-- Tep Dobry
[ the code for these benchmarks is available from the SCORE
PROLOG library under the subdirectory PS:<Prolog.BM> ]
------------------------------
Date: Wed 29 May 85 12:50:32-EDT
From: Bob Hall <RJH%MIT-OZ@MIT-MC.ARPA>
Subject: You thought it was over...
[Forwarded from the MIT bboard by SASW@MIT-MC.]
No, but
AI JOKES II: THE WRATH OF CONS
is entering its final week, so if you've heard any good ones
and want to get in on the glory, send your entry to me
<rjh%mit-oz@mit-mc> before June 7, 1985. Remember to include
T-shirt size and school from the list on the announcement.
------------------------------
Date: 24 May 85 11:39:32 EDT (Friday)
From: MJackson.Wbst@Xerox.ARPA
Subject: Re: cheating at chess
From: cugini@NBS-VMS:
"Sooo... rather than bend the rules to allow humans to cheat also, why
not restrict computers to the use of internal storage during play? ie
they can load up from disk, tape, whatever, but once the clock starts,
we unplug all the I/O ports, and may the best rational agent win."
Surely if we unplug *all* the I/O ports, one of the rational agents will
lose by exceeding the time limit before making its first move?
Mark
------------------------------
Date: Thursday, 30 May 1985 22:41:31 EDT
From: Duvvuru.Sriram@cmu-ri-cive.arpa
Subject: Submission Date for AIE
A number of people have inquired about the due date for the Artificial
Intelligence in Engineering Conference, to be held in April 1986 at
University of Southampton, UK. The due date is extended to June 15th. If you
still plan to send an abstract don't waste your money on overnight mail,
good old US mail would do the job.
Sriram
------------------------------
End of AIList Digest
********************