From cet1@cus.cam.ac.uk Sat Feb 27 01:04:34 CST 1999 Article: 238046 of sci.math Path: news.math.niu.edu!husk.cso.niu.edu!vixen.cso.uiuc.edu!howland.erols.net!news.maxwell.syr.edu!diablo.theplanet.net!uknet!diablo.dera.gov.uk!server1.netnews.ja.net!hgmp.mrc.ac.uk!pegasus.csx.cam.ac.uk!cet1 From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: Need Help re: Chomp by David Gale Date: 26 Feb 1999 17:20:36 GMT Organization: University of Cambridge, England Lines: 42 Message-ID: <7b6l54$84h$1@pegasus.csx.cam.ac.uk> References: <36D31AAC.26DF@po-box.mcgill.ca> NNTP-Posting-Host: ursa.cus.cam.ac.uk Xref: news.math.niu.edu sci.math:238046 In article <36D31AAC.26DF@po-box.mcgill.ca>, KASSAM wrote: >I need information on a project I'm working on in a computer science >course I'm taking. Here's the project: > >In the game of CHOMP, invented by David Gale, nxm pills are placed in an >nxm matrix. The pill at position (1,1) is poisonous. Each player in >turn must take a bite (chomp) of at least one pill. If he bites at >(k,l), then he eats the rectangle of all pills at positions to the right >of k and above l, (k,l) included (so, (k,l) is the left bottom tip of >the rectangle). The person forced to eat the poisonous pill (the last >pill) loses. Interestingly, the first player, if he/she plays >intelligently, can always win. Can you find the describe the proof? There's a description of Chomp in [WW] (Extras to the chapter on Sylver Coinage, I think). The proof that a rectangular starting position (larger than 1x1) is a first-player win is a classical piece of strategy stealing. Consider the move that takes a single pill from the corner (n,m). EITHER this is a winning move, OR there is a winning response (k,l). In the latter case, the move (k,l) from the starting position is a winning move, as it necessarily disposes of the pill at (n,m). This is "non-constructive", of course. >One can see how one could play this game by constructing a minimax >tree. Can you think of a computationally faster way? (Make a case.) Well, "minimax" with only two values! You should probably be storing values (P or N) for partially-chomped positions, as the same positions will occur on many branches of the tree. [WW] "Winning Ways for your mathematical plays" Elwyn R. Berlekamp & John H. Conway & Richard K. Guy Academic Press, 1982 ISBN 0-12-091101-9 Chris Thompson Email: cet1@cam.ac.uk