Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!pasteur!NORVIG@Teak.Berkeley.EDU
From: NORVIG@Teak.Berkeley.EDU (Peter Norvig)
Newsgroups: comp.ai
Subject: RE: HI-Q game
Message-ID: <13008@pasteur.Berkeley.EDU>
Date: 24 Apr 91 15:55:54 GMT
Sender: news@pasteur.Berkeley.EDU
Lines: 32
In-reply-to: <1991Apr24.055054.16724@cunixf.cc.columbia.edu>

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 Norvig