pss4@cunixb.cc.columbia.edu (Paul S Shannon) (04/24/91)
I've recently been introduced to a game I believe is distributed
by Mattel as "HI-Q". It consists of a cross-shaped board made of
holes in which pegs can be placed:
X X X
X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X X
X X X
Initially, all the holes are filled but the center one. Moves are made
by jumping a peg over another horizontally or vertically, not diagonally,
and removing the peg jumped over (like checkers). The object is to end
up with one peg in the center.
I've written a program to "randomly" move around pieces in the hope that
it would pop out the solution, but after 1000 games the game never got
below 3 pegs left over--this doesn't seem to be the way to go. I was
wondering if there might be some learning procedure that would lead to
successively better end states, till the game was finally solved.
thanks,
joseph jons
(guest on paul shannon's account).
----------------------------------------------------------------
If you happen to fall off the Sears Tower, go limp, so
people will think you're a dummy and they'll try to catch you,
because, hey, free dummy.hall@aplcen.apl.jhu.edu (Marty Hall) (04/24/91)
In article <1991Apr24.055054.16724@cunixf.cc.columbia.edu> pss4@cunixb.cc.columbia.edu (Paul S Shannon) writes: >I've recently been introduced to a game I believe is distributed >by Mattel as "HI-Q". It consists of a cross-shaped board made of >holes in which pegs can be placed: [Description of peg-jumping game and asking for computer methods to solve it] Historical note: A solution to this is described in the original MIT AI Memo "Hakmem" (Memo #239). I think the solution was due to Bill Gosper, and was considered quite an achievement at that early time (running on a PDP-1 in assembler (?)). - Marty Hall ------------------------------------------------------ hall@aplcen.apl.jhu.edu, hall%aplcen@jhunix.bitnet, ..uunet!aplcen!hall Artificial Intelligence Lab, AAI Corp, PO Box 126, Hunt Valley, MD 21030 (setf (need-p 'disclaimer) NIL)
NORVIG@Teak.Berkeley.EDU (Peter Norvig) (04/24/91)
Paul Shannon asks:
I've recently been introduced to a game I believe is distributed
by Mattel as "HI-Q". It consists of a cross-shaped board made of
holes in which pegs can be placed:
X X X
X X X
X X X X X X X
X X X X X X X
X X X X X X X
X X X
X X X
Initially, all the holes are filled but the center one. Moves are made
by jumping a peg over another horizontally or vertically, not diagonally,
and removing the peg jumped over (like checkers). The object is to end
up with one peg in the center.
I've written a program to "randomly" move around pieces in the hope that
it would pop out the solution, but after 1000 games the game never got
below 3 pegs left over--this doesn't seem to be the way to go. I was
wondering if there might be some learning procedure that would lead to
successively better end states, till the game was finally solved.
This peg game is analyzed in detail in Elwyn Berlekamp and John
Conway's "Winning Ways" (Academic Press, 1982, 2 vols.). In fact, if
you are interested in ANY game of a mathematical nature, its a good
idea to check "Winning Ways" before posting to the net.
-Peter Norvigtgd@tesla.orst.EDU (Tom Dietterich) (04/30/91)
This puzzle has been solved using an elegant machine learning method by Glenn Iba: Learning by Discovering Macros in Puzzle Solving. Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85), 1985 Vol. 1 640-642. Iba's program selectively learns macros by noting when a simple hill-climbing heuristic fails to give accurate estimates of the quality of board positions. Thomas G. Dietterich Department of Computer Science Dearborn Hall, 303 Oregon State University Corvallis, OR 97331-3102 503-737-5559
minsky@media-lab.media.mit.edu.MEDIA.MIT.EDU (Marvin Minsky) (04/30/91)
In article <1991Apr29.192045.1852@lynx.CS.ORST.EDU> tgd@tesla.orst.EDU (Tom Dietterich) writes: >This puzzle has been solved using an elegant machine learning method >by Glenn Iba: > >Learning by Discovering Macros in Puzzle Solving. Proceedings of the >Ninth International Joint Conference on Artificial Intelligence >(IJCAI-85), 1985 Vol. 1 640-642. > >Iba's program selectively learns macros ... Hi Tom! Incidentally, Iba figured out some of the macros himself, first. For example, if you have the configuration below: 0 0 0 where x means empty space, then after six moves all are gone 0 0 0 except for the bottom 0 0 Now, consider that the entire game consists of just 4 of x these patterns plus a few other units. If you think about this for a while, you should be able to solve the entire puzzle in your head! I remember not believing Glenn when he discovered this, until doing it myself.
schmidtg@iccgcc.decnet.ab.com (04/30/91)
I have written a program which solves the HI-Q puzzle in slightly less
than 3 seconds on my VaxStation 3100. The program uses a STATE-SPACE
HEURISTIC SEARCH ALGORITHM which is essentially a breadth first search
guided by some path heuristics. The algorithm is also known as the
A* ("A star") algorithm and may be found in many AI texts. The art of
solving this puzzle is in finding good heuristics which estimate the
"cost" or number of moves to a solution from a given state. I'd be
interested in hearing about other techniques which may be applicable
to solving this puzzle. BTW, how does one obtain "MIT AI Memo 'Hakmem'
(Memo #239)?
--
=============================================================================
Greg Schmidt -> schmidtg@iccgcc.decnet.ab.com
=============================================================================
"People with nothing to hide have nothing to fear from O.B.I.T"
-- Peter Lomax
-----------------------------------------------------------------------------
Disclaimer: No warranty is expressed or implied. Void where prohibited.
=============================================================================