Information-Theoretic Advisors in Invisible Chess.

bud,dwa,annn,ingrid@csse.monash.edu.au

SchoolofComputerScienceandSoftwareEngineering,MonashUniversity

Clayton,Victoria3800,AUSTRALIA

phone:+6139905-5225Abstract

Makingdecisionsunderuncertaintyremainsacen-tralprobleminAIresearch.Unfortunately,most

uncertainreal-worldproblemsaresocomplexthatprogressinthemisextremelydifficult.Gamesmodelsomeelementsoftherealworld,andofferamorecontrolledenvironmentforexploringmeth-odsfordealingwithuncertainty.Chessandchess-likegameshavelongbeenusedasastrategical-lycomplextest-bedforgeneralAIresearch,andweextendthattraditionbyintroducinganimper-fectinformationvariantofchesswithsomeusefulpropertiessuchastheabilitytoscaletheamountofuncertaintyinthegame.Wediscussthecomplex-ityofthisgamewhichwecallinvisiblechess,andpresentresultsoutliningthebasicgame.Wemo-tivateanddescribetheimplementationandappli-cationoftwoinformation-theoreticadvisors,anddescribeourdecision-theoreticapproachtocom-biningtheseinformation-theoreticadvisorswithabasicstrategicadvisor.Finallywediscusspromis-ingpreliminaryresultsthatwehaveobtainedwiththeseadvisors.

1Introduction

Gamesandgametheorymodelsomepropertiesofreal-worldsituationsandthereforeallowanalysisandempiricaltestingofdecision-makingstrategiesinthesedomains.Inthisca-pacity,gameshavelongbeenusedasatestbedforgeneralAIresearchandideas.Inparticular,chesshasalonghistoryofusebecauseofitsstrategiccomplexity,andwell-studiedandunderstoodproperties.

Despitetheseadvantages,chesshastwosignificantdraw-backsasageneralAItestbed:thefirstisthesuccessofcomputerchessplayersthatusehard-coded,domainspecificrulesandstrategiestoplay;andthesecondisthefactthatstandardchessisaperfectinformationdomain.Anumberofresearchershavetackledthefirstofthesedrawbacks.ForexampleBerliner[2]investigatedgeneralisedstrategiesusedinchessplayasamodelforproblemsolving,andPell[16]introducedmetagamer—asystemforplayinggamesarbi-trarilygeneratedfromasetofgamesknownasSymmetricChess-Likegames(SCLGames).

Inthispaper,weaddresstheseconddrawbackofchessasageneralAItestbed—thatofperfectinformation.Wede-scribeamissing(orimperfect)informationvariantofstan-dardchesswhichwecallinvisiblechess[4].Invisiblechess

fax:+6139905-5146

consistsofaconfigurablenumberofinvisiblepieces,i.e.,piecesthataplayer’sopponentcannotsee,andisthusarep-resentativeofthegeneralclassofstrategicallycomplex,im-perfectinformation,twoplayer,zero-sumgames.

Manyresearchershaveinvestigatedgameswithmissingin-formationincludingpoker([7],[14],[13]),bridge([10],[12],[21]),andmulti-userdomains[1].WiththeexceptionofAlbrechtetal.[1],whousealargeuncontrollabledomain,allofthesedomainsarestrategicallysimplegivenperfectinformation.Invisiblechessretainsthestrategiccomplexi-tyofstandardchesswiththeadditionofacontrollableel-ementofmissinginformation.Invisiblechessisrelatedtokriegspiel([15]and[5]),achessvariantinwhichalltheopponent’spiecesareinvisibleandathirdpartyrefereede-termineswhetherornoteachmoveisvalid.

Theremainderofthepaperisorganisedasfollows.Sec-tion2discussessomerelatedwork.Sections3and4outlinethegameandourbasicapproachtoinvisiblechess.Sec-tion5presentsabriefanalysisofplaywithvariousinvis-iblepieces.Interestingly,weshowthattherelativevaluesofminorinvisiblepiecesdiffersfromstandardchesspiecerankings.Section6discussestherelationshipbetweenun-certaintyandtheinformation-theoreticconceptofentropy,andtheapplicationofentropytoourresults.Section6alsomotivatesthedesignofinformation-theoreticadvisors,de-scribestheseadvisorsandpresentspreliminaryresultsthatdemonstratetheefficacyofourapproach.Finally,Section7containsconclusionsandideasforfurtherwork.

2RelatedWork

Sincethe1950s,whenShannonandTuringdesignedthefirstchessplayingprograms[19],computershavebe-comebetteratplayingcertaingamessuchaschessus-inglargeamountsofhand-codeddomainspecificinforma-tion.Inanswertothesuccessofhard-codedalgorithms,Pell[16]introducedaclassofgamesknownasSymmetricChessLike(SCL)Games,andasystemcalledMetagamerthatplaysgamesarbitrarilygeneratedfromthisclassusingasetofadvisorsrepresentingstrategiesintheclassofgames.Pelldidnotconsiderimperfectinformationgames.Invisi-blechessisonegameintheextensionofPell’sclassofSCLGamestotheclassofInvisibleSCLGames,whereoneormoreofaplayer’spiecesishiddenfromtheiropponent.Kolleretal.[13]investigatedsimpleimperfectinformationgameswithagoalofsolvingthem.However,theirapproachdoesnotscaleuptocomplexgamessuchasinvisiblechess.

Smithetal.[21]wroteabridgeplayingprogramusingamodifiedformofgametreewithenumeratedstrategiesratherthanactions,effectingaformofforwardpruningofthegametree.Smithetal.statedthatforwardpruningworkswellforbridge,butnotforchess.Ginsberg[11]introducedparti-tionsearchtoreducetheeffectivesizeofthegametree.Heshowedthatthisapproachworkswellforbridgeandothergameswithahighdegreeofsymmetry.Inbridge,theor-derinwhichthefirstcardsareplayedisirrelevantifthesamecardsremainineachplayer’shands.However,inchess,partlybecausepawnsonlymoveforward,andpartlybecausetheorderofmovesininvisiblechesschangestheflowofthegame,thesamepositionsdonottendtooccurinasignific-antnumberofnodesinthegametree,andthereforepartitionsearchisnotlikelytobeveryeffectiveonchessvariants.MorerecentlyGinsberg[12]includedMonteCarlometh-odstosimulatemanypossibleoutcomes,choosingtheactionwiththehighestexpectedutilityoverthesimulations.Gins-bergclaimsthattryingtogleanorhideinformationfromanopponentisprobablynotusefulforbridge.Incontrast,wepresentresultsthatshowthatbothinformationhidingandgleaningcanbeusefulininvisiblechess.

FrankandBasin([9]and[8])haveperformedadetailedin-vestigationofsearchinimperfectinformationgames,con-centratingalmostexclusivelyonbridge.TheyfocusonanumberofsearchtechniquesincludingflatteningthegametreewhichtheyhaveshowntobeanNP-Completeproblem,andMonteCarlomethods.TheirinvestigationsuggeststhatMonteCarlomethodsarenotappropriateforimperfectin-formationgames.Thisproblemisexacerbatedininvisiblechessgiventherelativelackofsymmetryandthesizeofthegametree.

Ciancarinietal.[5]consideredkingandpawnendgamesinthegameofkriegspiel—anexistingchessvariantwhereneitherplayercanseetheopponent’spiecesormoves.Theyusedagame-theoreticapproachinvolvingsubstantiveratio-nalityandhaveshownpromisingresultsinthistrivialversionofkriegspiel.Thusfartheyhavenotappliedtheirapproachtoacompletegameofkriegspiel.Kriegspieldiffersfrominvis-iblechessinanumberofimportantareas.Alltheopponent’spiecesareinvisibletoaplayerofkriegspiel.Thusthereisnowaytoreducetheuncertaintyinthedomainwithoutreduc-ingthestrategiccomplexity.Bycontrast,ininvisiblechess,thenumberandtypesofinvisiblepiecesisconfigurable.Ad-ditionally,inkriegspiel,aplayerattemptsmovesuntilalegalmoveisperformed;athirdpartyarbitratorindicateswhetherornoteachmoveislegal.Ininvisiblechess,theplayerisgiv-enspecificinformationwhenamoveisimpossibleorillegal,andmaymissaturnasaresultofattemptinganimpossi-blemove(seeSection3).Thesedifferencesmakekriegspielasubstantiallymorecomplexandlesscontrollabledomainthaninvisiblechess.Specifically,exploringtherelationshipbetweenuncertaintyandstrategicplaywouldbemorediffi-cultinkriegspiel.Ultimately,thepathologicalcaseofinvisi-blechesswhereallpiecesareinvisibleapproachesthecom-plexityofkriegspiel.Thusinvisiblechessprovidesaconve-nientsteppingstonetoamuchmoredifficultproblem.1

8

7

6

5

4

3

2

1

abcdefghFigure1:Animpossiblemove.Theblackbishoponb2isinvisible.Whiteattemptsanimpossiblemovebytryingtomovethebishoponc1toa3.

abilityofoccupation,thentheaverageapproximatebranch-ingfactorofthatgameofinvisiblechessis.Forthreeinvisiblepieceseach,theboardandmoving.Assumingforapproximatelythatthethebranchinginvisiblefactorhalfthepiecesisaround

game,arethenon

thecompleteexpandedgametreeforthreeinvisiblepieces

eachisintheorderof

()nodes.Tomakethedomainevenmorecomplex,chesshasvirtuallynoaxesofsymmetrythatallowthesizeofthegametreetobereducedasinhighlysymmetricalgamessuchastic-tac-toe,andSmithandNau[20]claimthatforwardpruningtoreducethebranchingfactorofchesshasbeenshowntoberelativelyineffective.

Inadditiontodealingwiththecombinatoriallyexpansivena-tureoftheinvisiblechessgametree,aplayermustmain-tainbeliefsaboutthepositionsoftheopponent’sinvisiblepieces.Aplayerthatusesanybeliefupdatingschemethatdoesnottakeintoaccounteverypossibledestinationsquarewhenaninvisiblepieceismoved,willloseimportantinfor-mationabouttheflowofthegame.

Assumingnostrategicknowledge(i.e.,eachsquarethataninvisiblepiececanmovetoisaslikelytobevisitedasanyother),andonlyoneinvisiblepiece,aplayercaneasilymain-taintheprecisedistributionforthatpiece(see[3]).However,formultipleinvisiblepieces,thepositionsofinvisiblepiecesarenotconditionallyindependentwithrespecttoeachother.Theprobabilityofoneinvisiblepieceoccupyinganypartic-ularsquareaffectstheprobabilityofanotherinvisiblepieceoccupyingthatsquare.Maintainingtheprobabilitydistribu-tionsofmultipleinvisiblepiecesinvolvescombinatorialcal-culationsinthenumberofinvisiblepiecesorthestorageofcombinatoriallylargeamountsofdatatomaintainthecom-pletejointdistributionsofallinvisiblepiecesovertheentirechessboard.

4BasicDesign

Tocopewiththecombinatorialexplosion,andthestrategiccomplexityofinvisiblechess,weemploya“divideandcon-

8

7

6

5

4

3

2

1

abcdefgh

Figure2:Anillegalmove.Whiteisin

checkfromtheblackbishopona5,andat-temptstocapturetheinvisibleblackknightonf1whereitwouldbeincheckfromtheinvisibleblackbishoponc4.

quer”approach.Wesplittheproblemofchoosingthenextmoveintoanumberofsimplersub-problems,andthenuseutilitytheory[17]torecombinethecalculationsperformedforthesesub-problemsintoamove.Weuseinformation-theoreticideas[18]todealwiththeuncertaintyinthedo-main,andstandardchessreasoningtodealwiththestrategicelements.

Thismodular,hybridapproachisimplementedwithadvi-sorsorexpertsconnectedandcontrolledbyaGameCon-trollerandDistributionMaintenanceModule(GCDMM),andaMaximiser.TheGCDMMcontrolsthegamestate,hasknowledgeofthepositionsofallinvisiblepiecesandmain-tainsdistributionsofinvisiblepiecesonbehalfofthetwoplayers.TheGCDMMisresponsiblefordecidingwhetheramoveislegal,impossibleorillegalandensuringthatthegameprogressescorrectly.Whenitisaplayer’sturntomove,theGCDMMrequeststhenextmovefromtheMaximiserforthatplayer.TheMaximiser,responsibleforchoosingthebestmovesuggestedbytheavailableadvisors,generatesallpossi-bleboardsandallpossiblemoves,andrequestsutilityvaluesfromeachoftheadvisorsforeachmove.

Eachadvisorevaluatesthepossiblemoves,acrossasmanyboardsaspossibleintheavailabletime,accordingtoanin-ternalevaluationfunction.Thestrategicadvisor,amodifiedversionofGNUChess,returnsallpossiblemovesandtheirExpectedUtilities(EU)fromastrategicperspective.2TheEUforeachmoveoraction()iscalculatedbymultiply-ingitsutilityvaluebytheprobabilityofthegamestate()forwhichtheutilityvaluewascalculated,andsummingthisacrossallpossiblegamestates()asfollows.

(1)

TheMaximisermultipliesthevaluereturnedfromeachofthe

1N1Q2NN.I.1B

61.0

35.0

41.5

.8

39.053.413.227.61R

46.6

38.2

34.4

93.065.061.843.847.62B

86.8

56.2

72.0

95.658.565.628.045.82R

72.4

52.4

54.2

98.2

10.2

7.0

4.4

1.83

Thatendedinawin.Drawngamesarediscarded.Theyarelargelytheresultofrepeatingmovescontinuously,andconsistoflessthan10%ofgamesplayed.

1 Invisible Black Bishop versus 2 Invisible White Bishops - White Wins

160

Black’s UncertaintyWhite’s Uncertainty

140

em120

aG eht r100

evo demm80

uS yport60

nE latoT40

20

0

020406080100120140160180200

Number of Games

Figure3:Uncertainty(asentropy)ingameswithoneinvisi-bleblackbishopagainsttwoinvisiblewhitebishopsthatwerewonbywhite.

discusssomepreliminaryresultsobtainedwiththeseadvi-sors(Section6.3).

6.1UncertaintyandEntropy

Anyprobabilitydistributioncanbesaidtohaveanentropyorinformationmeasureassociatedwithit.Thisentropymea-sureisboundedfrombelowbyzero,whenthereisonlyonepossibilityandthereforenouncertainty,andincreasesasthedistributionspreads.

Ininvisiblechess,givenaprobabilitydistributionofthepo-sitionsoftheopponent’sinvisiblepieces,itispossibletode-riveaprobabilitydistributionofallpossibleboardpositions.Thuswecancalculatetheentropy()ofasetofboardstatestogetherwiththeirassociatedprobabilitiesasfollows:

(2)

whererepresentsasinglegamestate(onepossiblecombi-nationofpositionsoftheopponent’sinvisiblepieces),fromthesetofpossiblegamestates(),andrepresentstheprobabilityofthatgamestate.Asinvisiblepiecesmove,thenumberofsquarestheymayoccupyincreases.Thisleadstoanincreaseinthenumberofpossibleboardstates,andtheentropyofthedistributionofthoseboardstates,i.e.,itincreasestheopponent’suncertainty.

Figure3showstheentropyingamesthatwerewonbywhiteplayingwithtwoinvisiblebishopsagainstblackwithonein-visiblebishop.Thesolidlineshowsblackstotalentropy(theentropyofthedistributionofthepositionsofwhite’sinvisiblepieces)summedoverthecourseofthegame,sortedbyen-tropy.Thedashedlineshowswhite’stotalentropyovereachcorrespondinggame.Ofthe190gameswonbywhite,onlyonegame(number86)showsgreaterentropyforblack.Thisisnotthecaseforgamesthatwerewonbyblack.Thisex-amplecorroboratesourintuitionthatmorecertainplayersaremorelikelytowin,andunderpinsourinformation-theoreticadvisors.

6.2Information-TheoreticAdvisors

MoveHideAdvisor.Workingonthepremisethatthemoreuncertaintheopponentis,theworsetheywillplay,themovehideadvisoradvisesaplayertoperformmovesthathidein-formationfromtheopponent.Thatis,eachmoveisscored

Weight

Seek

BvsB

BvsB57.2

50.1

5.0

82.7

51.2

13.6

47.

Theresultsinthesecolumnweregeneratedwithanoldver-sionoftheprogramwhichdidnotcalculatethevalueofimpossiblemovescorrectly.However,thepartialresultsthathavebeengen-eratedforthesecolumnswiththenewprogramfollowedthesametrendsastheresultspresentedhere.

visoronly,againstanopponentusingoneoftheinformation-theoreticadvisorsandthestrategicadvisor.

Table2showstheresultsofaddingthemovehideormoveseekadvisortoaninvisiblequeeneach(QvsQ)andaninvis-iblebishopeach(BvsB).Thefirstcolumnheaded“Weight”showstheweightoftheinformation-theoreticadvisorrela-tivetothestrategicadvisor.Thus,withaweightof0.5,ingamesplayedwithaninvisiblequeeneach,theplayerplay-ingwiththemovehideadvisorwon57.2%ofthegames.MoveHideResults.Themovehideadvisorprovedtobeasignificantadvantage.Infactthewinpercentagewithaweightof5.0fortheinvisiblebishopgameswas82.7%whichisapproachingthewinpercentageofaninvisiblebish-opagainstnoinvisiblepieces(.8%).

Thisimprovementisduetotheincreasednumberofinvis-iblepiecemoves.Withasmallincreaseinthevalueofmovesofinvisiblepieces,strategicallyreasonableinvisiblepiecemovesaregreatlyencouraged.Thistendstomaximisetheopponent’suncertainty.However,astheweightofthemovehideadvisorincreasespast5.0,thepercentageofwin-sdecreases.Thisbehaviouristypicalofallobservedmovehideruns,andresultsfromtheplayerperforminghighlyval-uedmovehidemovesattheexpenseofstrategy.Althoughtheopponentmaybeslightlymoreuncertainwhenthemovehideadvisorisweightedhighly,theplayerismakingenoughstrategicallypoormovestocounterthatadvantage.MoveSeekResults.Table2(columns5&6)showsthemoveseekadvisor’seffectivenessagainstanopponent’sin-visiblepieces.Withtheappropriateweight,themoveseekadvisordoesincreasetheplayer’swinpercentagebyaround5%.However,forweightsgreaterthanorsmallerthanthesevalues,themoveseekadvisoriseitherineffectiveordetri-mental.

Movesthattraversesquareswithapositiveprobabilityofoc-cupationbytheopponent’sinvisiblepiecesarevaluedbythemoveseekadvisor.Thesemovesmaynotcorrespondtogoodstrategicmoves.Thus,thehigherthemoveseekadvisor’sweight,thefewergoodstrategicmoveswillbeperformed.Thedifferencebetweenthebishop-seekingandqueen-seekingbehaviourisrelatedtothedifficultyoffindingtheopponent’sinvisiblepiece.Aninvisiblebishopcanhaveapositiveprobabilityofoccupyingatmosthalftheavailablesquares,whileaninvisiblequeencanhaveapositiveprob-abilityofoccupyingallavailablesquares.Thus,theadviceprovidedbythemoveseekadvisoroftenaidsintheearlycaptureoftheinvisiblebishop,therebyremovingtheuncer-taintyfromthegame.Incontrast,followingthisadvicewhentheinvisiblepieceisaninvisiblequeenleadstonon-strategicmoves.Thusthemoveseekadvisorassistswhentheuncer-taintyinthegameislow,butmaybeuselessordetrimentalwhentheuncertaintyishigh.

7ConclusionandFutureWork

Theresultspresentedinthispaperarepreliminaryandfur-therexplorationofthedomainisrequired.Specifically,moreaccuratepredictionofthelikelypositioningoftheoppon-ent’sinvisiblepiecesisneeded.Thispredictioncouldtaketheformofusingstrategicinformationaboutthelikelydesti-nationofamovinginvisiblepiece,orinvolveevaluatingthecompletesearchtreeformoreply.Improvingthisdistribu-

tionwouldreduceitsentropyandthereforeimprovestrategicperformance.Asideeffectofthistypeofdistributionim-provementisthepossibilityofincorporatingbluffingintoin-visiblechess,i.e.,movinganinvisiblepiecetoanunlikelypositiontoconfuseanopponent.

Modellingtheuncertaintyregardingaplayer’spiecesfromtheopponent’sperspectiveformoreplywouldimprovestrat-egicperformance.However,theproblemofthecombinatori-alexpansioninthesearchrequiredasaresultofthispredic-tionneedstoberesolved.Obtainingresultsinthisdomainisalreadyatimeconsumingexerciseandtheadditionofanex-tralayerofsearchwouldmakerapidgameplayimpractical.Themostobviouswaytomanagethisexplosionistofindef-fectivewaystoprunethegametree.However,asmentionedearlier,thisisnotlikelytobesimple.

Onesignificantdifficultyofthistypeofapproachistheprob-lemofhowtochoosetherelativeadvisorweights.Itislike-lythatplaymaybeimprovedbyusingstatisticalinferencetechniquessuchasthosedescribedin[6]todeterminestat-icweightsfortheadvisors.However,ourresultsshowthattheadvisorshavedifferentlevelsofeffectivenessindiffer-entsituations.Thusifaplayercaninferwhattypeofboardpositionthecurrentsituationis,theycanapplyanappropri-ateweightvectortotheiradvisorarray.Thetypeofcurrentboardsituationmaybebasedontheamountofentropyandthepiecesthatarecausingit,thegamemovenumber,andotherpositionalinformation.Weintendtousestatisticalin-ferencetechniquestoexplorethispossibility.

Insummary,wehavepresentedanddiscussedacomplex,butcontrolleddomainforexploringautomatedreasoninginanuncertainenvironmentwithahighdegreeofstrategiccomplexity.Wehavemotivatedandintroducedtheuseofinformation-theoreticadvisorsinthestrategicallycompleximperfectinformationdomainofinvisiblechess.Wehaveshownthatourdistributed-advisorapproachusingacombi-nationofinformation-theoreticandstrategicaspectsofthedomainleadtoperformanceadvantagescomparedtousingstrategicexpertisealone.Giventhesimplicityandgeneralityofthisapproach,ourresultspointtowardsthepotentialap-plicabilitytoarangeofstrategicallycompleximperfectin-formationdomains.

Althoughthebasicideaofinformation-theoreticadvisorsisintuitive,theirapplicationtothisdomainisnotnecessarilystraightforward.Therearecomplexmulti-levelinteractionsbetweenthestrategicadvisorandtheinformation-theoreticadvisors.Thebalancingactrequiredtomaximiseaplayer’sperformancealmostcertainlyinvolvesdynamicallymodify-ingtheweightsassociatedwiththevariousadvisorsdepend-ingonboththeinvisiblepiececonfigurationandthegameposition.However,thepreliminaryresultspresentedinthispaperindicatethatthisisadomainworthexploringfurther.

Acknowledgements

TheauthorswouldliketothankChrisWallaceforhisinsight,adviceandpatience.

References

[1]DWAlbrecht,IZukerman,AENicholson,andABud.To-wardsabayesianmodelforkeyholeplanrecognitioninlarge

domains.InUserModelling.Proc.ofthe6thInt.Conf.UM97,number383inCISMCoursesandLectures,pages365–376.SpringerWien,NewYorkNYUSA,1997.

[2]HansJ.Berliner.ChessasProblemSolving.PhDthesis,CarnegieMellonUniversity,Pittsburgh,PA,1974.

[3]

A.Bud,I.Zukerman,D.Albrecht,andA.Nicholson.Invisiblechess:Rules,complexityandimplementation.TechnicalRe-portforthcoming,SchoolofComputerScienceandSoftwareEngineering,MonashUniversity,2000.

[4]

A.E.Bud,A.E.Nicholson,I.Zukerman,andD.W.Albrecht.Ahybridarchitectureforstrategicallycompleximperfectin-formationgames.InProc.ofthe3rdInt.Conf.onKnowledge-BasedIntelligentInformationEngineeringSystems.,pages42–45.IEEEPress,1999.

[5]

P.Ciancarini,F.DallaLibera,andF.Maran.DecisionMak-ingunderUncertainty:ARationalApproachtoKriegspiel.InJ.vandenHerikandJ.Uiterwijk,editors,AdvancesinCom-puterChess8,pages277–298.Univ.ofRulimburg,1997.[6]

GFarrandDPowell.Unsupervisedlearninginmetagame.InNFoo,editor,Proc.ofthe12thAustralianJointConferenceonAI(AI’99),number1747inLectureNotesinAI,subseriesofLectureNotesinComputerScience,pages24–35.Springer-Verlag,December1999.

[7]NicholasV.Findler.Studiesinmachinecognitionusingthegameofpoker.CommunicationsoftheACM,20(4):230–245,April1977.

[8]I.FrankandD.Basin.Atheoreticalandempiricalinvestiga-tionofsearchinimperfectinformationgames.InTheoreticalComputerScience—Toappear.,2000.

[9]IanFrankandDavidBasin.Searchingameswithincompleteinformation:Acasestudyusingbridgecardplay.ArtificialIntelligence,100:87–123,April1998.[10]

Bj¨ornGamb¨ack,MannyRayner,andBarneyPell.Anar-chitectureforasophisticatedmechanicalBridgeplayer.InDavidN.LevyandDonF.Beal,editors,HeuristicPro-gramminginArtificialIntelligence—TheSecondComputerOlympiad2,pages87–107,Chichester,England,1991.EllisHorwood.

[11]MattGinsberg.Partitionsearch.InProc.ofthe13thNationalConf.onArtificialIntelligence,pages228–233.AAAIPress/MITPress,1996.

[12]MattGinsberg.GIB:stepstowardanexpert-levelbridge-playingprogram.InProc.ofthe16thInt.JointConf.onAI,pages584–5.MorganKaufmann,1999.

[13]DaphneKollerandAviPfeffer.Representationsandsolu-tionsforgame-theoreticproblems.ArtificialIntelligence,94(1):167–215,1997.

[14]

KBKorb,AENicholson,andNJitnah.Bayesianpoker.InKBLaskeyandHPrade,editors,Proc.ofthe15thConf.onUncertaintyinAI,pages343–350,Stockholm,Sweden,Au-gust1999.MorganKaufmann.

[15]DLi.Kriegspiel:ChessUnderUncertainty.PremierPublish-ing,1994.

[16]BarneyPell.StrategyGenerationandEvaluationforMeta-GamePlaying.PhDthesis,UniversityofCambridge,1993.[17]HowardRaiffa.Decisionanalysis:introductorylecturesonchoicesunderuncertainty.Addison-Wesley,1968.[18]Alfr´edR´enyi.Adiaryoninformationtheory.JohnWiley,1984.

[19]StuartRussellandPeterNorvig.ArtificialIntelligence:AModernApproach.PrenticeHall,1995.

[20]

S.J.J.SmithandD.S.Nau.Strategicplanningforimperfect-informationgames.InGames:PlanningandLearning,Pa-persfromthe1993FallSymposium,pages84–91.AAAIPress,1993.

[21]

S.J.J.Smith,D.S.Nau,andT.A.Throop.Total-ordermulti-agenttask-networkplanningforcontractbridge.InProc.ofthe13thNationalConf.onAI,pages108–113.AAAIPress/MITPress,1996.