I was intrigued by Joe Marshall' mention of the Hercules vs. Hydra game in a
recent post here, so I decided to code it up in Lisp.
Briefly, the game is interesting because Hercules will always win,
regardless of his strategy, but the game takes so long that it cannot be
proved that Hercules will win using Peano arithmetic.
A nice description of the game and a sketch of proof can be found here:
http://www2.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/
The function HYDRA-ORDINAL below returns the ordinal of a hydra tree. This
number decreases with each Hercules cut, which is how it can be shown that
Hercules will always prevail.
CUT-LEFTMOST models a simple strategy for Hercules. It removes the leftmost
head of the Hydra and duplicates the head's parent node many times. After
the first head is removed, its parent is replicated once, after the second
cut, twice, etc. If you execute
(hercules *small-hydra* #'cut-leftmost)
you'll see that the small Hydra can be defeated in 38 cuts.
I've not been able to cut *big-hydra* much more than about 10000 times. The
various Lisps I have either exceed their heap limit or die in the garbage
collector. I'm careful to share common structure so making N cuts seems to
create only about N new cons cells. The UNIQUE-NODES function can be run on
a Hydra tree with up to about 2000 nodes. Executing
(unique-nodes hydra #'eq)
will tell you how many unique nodes a Hydra tree has. After 2000 cuts of
*big-hydra*, UNIQUE-NODES returns roughly 2000. I'm not sure why I'm having
such trouble computing 10000 cuts.
When head replication is made constant (say 5 duplicates per cut), the big
hydra is still going strong after 200 million cuts, so I'm confident that
I'll never see the big Hydra defeated.
bob
====================
(defvar *big-hydra*
'(hydra (hydra (hydra (hydra)
(hydra)
(hydra))
(hydra (hydra (hydra))))
(hydra (hydra)
(hydra (hydra)
(hydra)))))
(defvar *small-hydra*
'(hydra (hydra)
(hydra (hydra)
(hydra))))
(defun make-hydra (children)
(cons 'hydra children))
(defun children (hydra)
(cdr hydra))
(defsetf children (hydra) (children)
`(setf (cdr ,hydra) ,children))
(defun hydra-ordinal (hydra)
(let ((children (children hydra)))
(if (null children)
0
(let ((child-expressions (mapcar #'hydra-ordinal children)))
(if (every (lambda (n)
(and (numberp n) (zerop n)))
child-expressions)
(list-length children)
(labels ((power (n)
(cond ((and (numberp n) (= n 0)) 1)
((and (numberp n) (= n 1)) 'w)
(t (list 'expt 'w n)))))
(if (= (list-length child-expressions) 1)
(power (first child-expressions))
(append '(+) (mapcar #'power child-expressions)))))))))
(defun cut-leftmost (hydra count)
(labels ((copy-leftmost-branch (hydra)
(if (null (children hydra))
(make-hydra '())
(let ((children (children hydra)))
(make-hydra (cons (copy-leftmost-branch (first children))
(rest children))))))
(clone-hydra (hydra count)
(loop for i from 1 upto count
collect hydra)))
(setf hydra (copy-leftmost-branch hydra))
(let ((head hydra)
(body nil)
(body-parent nil))
(loop (when (null (children head))
(if (null body)
(return nil)
(progn (setf (children body) (rest (children body)))
(when body-parent
(setf (children body-parent)
(append (clone-hydra body count)
(children body-parent))))
(return hydra))))
(setf body-parent body)
(setf body head)
(setf head (first (children head)))))))
(defun hercules (hydra strategy)
(declare (type function strategy))
(loop for h = hydra then (funcall strategy h count)
for count upfrom 1
when (not h)
do (return (1- count))))
(defun unique-nodes (hydra test)
(let ((table (make-hash-table :test test)))
(labels ((visit (node)
(let ((entry (gethash node table)))
(unless entry
(setf (gethash node table) node)))
(dolist (child (children node))
(visit child))))
(visit hydra))
(hash-table-count table)))
On 01 Nov 2003 01:05:57 -0500, ······@speakeasy.net (Robert E. Brown)
wrote:
>I was intrigued by Joe Marshall' mention of the Hercules vs. Hydra game in a
>recent post here, so I decided to code it up in Lisp.
>
>Briefly, the game is interesting because Hercules will always win,
>regardless of his strategy, but the game takes so long that it cannot be
>proved that Hercules will win using Peano arithmetic.
>
>A nice description of the game and a sketch of proof can be found here:
>
>http://www2.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/
Excellent page, thanks!
Some of the functions described in it reminded me of the Ackerman
function. I'm curious - are they related, or is it a case of "this
leaves Ackerman in the dust" or what?
--
"Sore wa himitsu desu."
To reply by email, remove
the small snack from address.
http://www.esatclear.ie/~rwallace