CREATIVE SOLUTIONS TO PROBLEMS - Stanford …

1 CREATIVESOLUTIONSTOPROBLEMSJohnMcCarthyC omputerScienceDepartmentStanfordUniversi tyStanford,CA 29, 1999 AbstractTheideais tochipa pieceoutof theproblemof creativity bydefiningacreativesolutionto a problemrelative to thefunctionsandpredicatesusedin of theproblemsolver butonlyaboutthecreativity of (informal):A solutionto a problemis creativeif it in-volvesconceptsnotpresentin statementof theproblemandthegen-eral tidentifycreativity alsoconsiderhow toexpressconciselytheideaof a adequateis relative to theknowledgeandability of thepersonor programto which theideais programsis likelyto remaina distant goalforAIuntil someonecomesupwitha ,it is worthwhileto chippiecesoffthecreativity problemandworkonthemseparately.

2 It seemsthatit is possibleto studythenotionof a1creative solutionto a problemapartfromstudyinghow a (informal):A solutionto a problemis creativeifit involvesconceptsnotpresentin statementof theproblemandthegeneral smallsteptowardprogramsthatfindcreative SOLUTIONS ,weconsiderhow to expresstheideaof a solutionconcisely. Theadequacyof anideaof a solutionis relative to thebackgroundof solutionsis themutilatedcheckerboard oppositecornersquares are removed froma checker-board. Is it possibleto covertheremainingsquares withdominoes?Adominois a 1 2 rectangle, two thatthisis impossiblenotesthata dominocoversoneblack squareandonewhitesquare,andthereforeany cov-eringby dominoes coversequalnumbersof squaresof thetwo ,themutilatedcheckerboardhas32 squaresof onecolorand30 squaresof regardthisproof as CREATIVE , becauseit involves anelementnotpresent in theformulationof theproblem sa conciseexpressionof dominocoverstwo squaresof somepeoplethiswillbe requirethead-ditionalsentenceThetwo squaresthathave beenremovedareof implicitlywhenacheckerboardis mentioned,andperhapstheproblemwouldbe purerif it referredto an8 8 array.

3 However,one sinitialreactionto theproblemis to considertherebeingtwo colorsas irrelevant, justas it is2irrelevant whatthetwo colorsare someboardshave black andwhitesquares,somehave redandblack, andsomehave greenandoff-white(perhapsthought to be morerelaxingfortheplayers).(McCarthy 1964) presentedtheproblemas a toughnutforfirstordertheoremprovers,beca usea straightforwardformalizationof theproblemprovidesnoway of makingtheargument in was notmentionedin that1964memo,butI evidentlymentionedit in lectures,becausetheproblemgaveriseto an informalcompetitionaimedat findingthemostnon-creativesolutionto non- CREATIVE solutionwas proposedby ShmuelWino-gradof was non- CREATIVE , becauseit didn of dominoes projectingfromthetoprow to thesecondrow is fromthesec-ondto thethirdis odd, ,thetotalnumber of verticaldominoes is thesumof of horizontaldominoes is + oddis evensothetotalis even.

4 Butthetotalis anapparent mathemat-icalinductionherein the etc..We willseelaterthattheideaitselfdoes sproof is CREATIVE , butwe canaskwhetherthereis onecreative ideain it or thattherewas onecre-ative idea,andtherestwas straightforwardfora good mathematicianlike by MarvinMinskyof mustprojectfromit to theadjacent , the5-diagonal,2 projectfromthe5-diagonalto the6-diagonal,4 fromthe6-diagonalto the7-diagonalandfinally3 projectfromthe7 diagonalto of the8 squaresin squaresof the8-diagonal, sproof getshighpoints fornon-creativity,becauseit is specificto the8 by 8 is by DimitriStefanukof Moscow, proofs or17,takinginto account , theirunmarked neighbors3.

5 Continuinguntil everyunex-3cludedsquareis in Minsky sproof,count-ingthenumber of dominoes projectingfromthe1-squaresto the2-squares, geta proof if therearenotenoughdominoes pro-jectingfromthen 1 squaresto Stefanukproof uncreative :CountingcolorsshowsthatStefanukproofsan dMinskyproofsalways workonany ,thisargument is ata meta-level to theMinskyandStefanukproofsandthereforeca n tclaimto be fact,theWinograd,MinskyandStefanukproofs areall CREATIVE ,andwe willtryto identifythecreativity involvedandgive a conciseexpressionof proofs,by separatecomputerprogramswrittenby MarkStickel ((Uribe andStickel 1994))andDanPehoushek(per-sonalcommunica tion)applypropositionalsatisfactionalgor ithmstoa propositionalexpressionin a variableassert-ingforeach squareandeach of thefourdirectionwhethera dominoprojectsfromthatsquarein , dominoprojectsinexactlyonedirectionfrome ach square,thatthereis a dominoprojectback froma squareinto which a dominoprojectsandthatnodominoprojectsoff theboardor into a forbiddensquareis takenas straight-forward, (Subramanian1993)

6 Includesan interactive proof usingtheBoyer-Mooreprover ,EnglishfirstActuallysolvinga probleminvolves botha CREATIVE partanda is sometimespossibleto separatethecreative cantella person,Startingwiththediagonalnextto an excludedsquare,com-putehow many dominoes projectfromeach diagonalto sprogramsolvedit in 1983andrunningona Pentium200solvedit recentlyin to be adequatefora sampleof a kindof program,butit doesn tneeda terminationcondition,be-causetheterminat ionis apparent to is harderto tellwhetherit is closeto theformin which thesolutionwas dis-covered,althoughit considerexpressingthecreative ideato a computerpro-gram,it wouldbe mostconvenient totellit a factortotellit know of no-onewhohastriedto make com-puterprogramsthatcanaccepta fragment of a programas above asthenon-routinepartof thesolutionto sa tryat expressingconciselytheideaof seemsto be longerandto involve , computetheparity of thenum-ber of dominoes projectingdownoutof each of of thetotalnum-ber of dominoes comparedto thesumof thetwo a 1999personalcommunication,theideacanbe ex-pressedmoreconcisely.

7 Winogradgottheideaas a resultof seeingamovieabouttheSocraticmethod in stu-dent saidsomethinglike, Anoddnumber of dominoes projectdownfromthetoprow andan oddnumber downfromthesecondrow to thethird.. At thispoint theteacherinterruptedthestudent andledhimby theSocraticmethod to soriginalideacouldbe pushedthrough,andthisledto it thisway, thecreative ideaseemsto beNotethatan oddnumber of dominoes projectfromthetoprow to abletopushtheargumentthrough,becauseat somepoint youhave to noticethatalthoughyougetnocontradictionf romdeterminingthatthereareanoddnumberof verticaldominoes,youalsogetanoddnumber of horizontaldomi-noes andaneven number of dominoes thenotionofcreativesolutionseemsto dependontheability availableto pushedthroughwhentwo squaresofthesamecolorareremovedany onestartsat5thetopandcomputesthesuccessi ve parities.

8 Thereis a jogin paritywhenanexcludedsquareis account thejogonegetsan answer as to theparity of thenumber of somepairsof excludedsquares,theparity turnsoutto be ,theparity turnsout,it willbe of thenumber of verticaldominoes projectingfromeach row to involve two tolabel liketheMinskysolution,namelyStartingwith n= 1, computehow many dominoes projectfromthesetof squareslabellednto thesquareslabelledn+ thissectionI have striven forconciseexpressionsof to establishthatthereis oneideain each of willbe easierto make computerscomeupwithcreative solutionsif theideaof thesolutionis justonething whateverkindof thingthatmay statement is readilyformulatedasa sentenceofthepredicatecalculus,butI don tseehow theparity andcountingargument canbe translatedinto a guideto themethod of semantictableaus,into a resolutionargument, or into a elementary is usedin thesensethatthequantifiersrangeover numbersandnotover youdon tlike readingthem.

9 Therestof thissectionmay be numbertherowsandcolumnsfrom1 to8 andwe intro-ducepredicatesS(x, y),L(x, y),E(x, y),G1(x, y),G2(x, y),G3(x, y),G4(x, y), andG5(x, y) withthefollowingintendedinterpretations: S(x, y) meansy=x+ (x, y) meansx < (x, y) meansx= (x, y) meansthesquare(x, y) andthesquare(x+ 1, y) arecov-eredby a (x, y) meansthesquare(x,y)andthesquare(x,y+1)ar ecoveredby a (x, y) meansthesquare(x,y)andthesquare(x-1,y)ar ecoveredby a (x, y) meansthesquare(x,y)andthesquare(x,y-1)ar ecoveredby a (x, y) meansthesquare(x,y)is shallaxiomatizeonlyas much of thepropertiesof thenumbersfrom1 to 8 as we (1,2) S(2,3) S(3,4) S(4,5) S(5,6) S(6,7) S(7,8) (x, y) L(x, y).

10 (x, y) L(y, z) L(x, z) S(x, z). (x, y) E(x, y). (x, x).Theseaxiomsinsurethatalleight numbersaredifferent anddeterminethevaluesofS(x, y),L(x, y), andE(x, y) forx, y=1, .. , (x, y) G2(x, y) G3(x, y) G4(x, y) G5(x, y) (x, y) (G2(x, y) G3(x, y) G4(x, y) G5(x, y)) (x, y) (G3(x, y) G4(x, y) G5(x, y)) (x, y) (G4(x, y) G5(x, y)) (x, y) G5(x, y)Theseaxiomsinsurethateverysquare(x,y)s atisfiesexactlyoneGi(x, y). (x, y) x= 1 y= 1 x= 8 y= (x, y) (E(1, x) E(1, y)) (E(8, x) E(8, y)) Theseaxiomsinsurethattheuncoveredsquares areprecisely(1,1)and(8,8). (x1, x2) G(x1, y) G3(x2, y) (y1, y2) G2(x, y1) G4(x, y2) Theseaxiomsstatethecondi-tionsthata pairof adjacent squaresbe coveredby a G3(1, y) G1(8, y) G2( ) G4(x,1)7 Theseaxiomsstatethatthedominoes don tstick outover theedgeof hada modelof these15sentences(inRobinson sclausalformalism,therewouldbe 31 clauses).