欢迎来到天天文库
浏览记录
ID:33943741
大小:208.89 KB
页数:3页
时间:2019-03-02
《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.numberofmatche7、sthatmaybetakenina•Considerthefollowinggame:movetosamevalueK.•Now,ifthedifferencebetweenmandnisgreaterthanKwecannotrestoresymmetryasawaytowin.•Whatisourwinningstrategynow?Problem2Problem2•Therearetwopilesofmatchesofsizemandn•Foreithersinglegamethewinningstrategyistorespe8、ctively.ensurethatthenumberofmatchesisaninteger•Aturnconsistsoftakingfrom1toMmatchesmultipleofthemaximumnumberthatcanbefromthefirstpileorfrom1toNmatchesfromremoved(mmodM+1=0).thesecondpile.•Whatifweplaysothatwemaintainthefollowing•Asimplesymmetricstrategyisclearlyimpossi9、ble.“symmetry”?•So,whatcanwedotowin?–mmodM+1=nmodN+1•Thisgivesawinningstrategy.Problem2TheMEXFunctionbegingame_3ifmmodM+1=nmodN+1thenremovesomematchesrandomlyfromarandompile•Wecangeneralisethe“symmetricpositions”elseifmmodM+1>nmodN+1thenstrategytothesumofanytwogames.remo10、ve(mmodM+1)-(nmodN+1)frompilem•Considerthesumoftwogamesleftandright.elseremove(nmodN+1)-(mmodM+1)from•A
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
此文档下载收益归作者所有