CSCI103_05b_SumsOfGames(print)6.pdf

《CSCI103_05b_SumsOfGames(print)6.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SumsofGames•Inthislecturewewillexaminesomemorecomplexgames.CSCI103•Forexample,whatdowedoifwehavemorethanonepileofmatches?•WecangeneralisethisproblemtooneofWeek5:Lecture2playingmultiplegameswherewedecideSumsofGameswhichgametoplayaswellaswhatmovetomakeeachturn.Problem1Prob

2、lem1•Thisgameisthe“sum”oftwoinstancesofthe•Therearetwopilesofmatches.samesimplegame.•Aturnconsistsofpickingoneofthetwopiles•Forasingleinstancethewinningstrategyisandtakingatleastonematch.obvious:–Takeallthematchesinthepile.•Youwinifyoutakethelastmatch.•Withtwopilesthisis

3、agoodwaytolose.•Whatisawinningstrategy?•Clearly,knowinghowtosolveasingleinstancedoesnottellyouhowtowinthisgame.Problem1Problem1•Thesolutionhereliesinthesymmetryofthebegingame_2ifm=nthentwogames.m=m–1•Thelosingposition{0

4、0}hasthesameelsenumberofmatches(zero)ineachpile.ifm

5、

6、n}arelilosingpositions.n=melse•Isthisthecase?m=n•Whatisthewinningstrategy?endifendifendgame_21LossofSymmetryLossofsymmetry•Perhapsthereisadeepersymmetrythatwecan•Whathappensifwerestrictthemaximumusetoestablishawinningstrategy.numberofmatche

7、sthatmaybetakenina•Considerthefollowinggame:movetosamevalueK.•Now,ifthedifferencebetweenmandnisgreaterthanKwecannotrestoresymmetryasawaytowin.•Whatisourwinningstrategynow?Problem2Problem2•Therearetwopilesofmatchesofsizemandn•Foreithersinglegamethewinningstrategyistorespe

8、ctively.ensurethatthenumberofmatchesisaninteger•Aturnconsistsoftakingfrom1toMmatchesmultipleofthemaximumnumberthatcanbefromthefirstpileorfrom1toNmatchesfromremoved(mmodM+1=0).thesecondpile.•Whatifweplaysothatwemaintainthefollowing•Asimplesymmetricstrategyisclearlyimpossi

9、ble.“symmetry”?•So,whatcanwedotowin?–mmodM+1=nmodN+1•Thisgivesawinningstrategy.Problem2TheMEXFunctionbegingame_3ifmmodM+1=nmodN+1thenremovesomematchesrandomlyfromarandompile•Wecangeneralisethe“symmetricpositions”elseifmmodM+1>nmodN+1thenstrategytothesumofanytwogames.remo

10、ve(mmodM+1)-(nmodN+1)frompilem•Considerthesumoftwogamesleftandright.elseremove(nmodN+1)-(mmodM+1)from•A