欢迎来到天天文库
浏览记录
ID:33943739
大小:237.67 KB
页数:5页
时间:2019-03-02
《CSCI103_05a_WinningLosing(print)4.pdf》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、Games•Thislectureisabouthowtowinsomesimpletwo‐persongames.CSCI103•Thekeytowinningistheabilitytorecognise,andtakeadvantageof,invariants.WinningandLosing•Oftenthewinningstrategyinvolvesmakingthemovethatmaintainstheinvariant.Problem1Problem1•MatchstickGames•Thesegamesareimpart
2、ial,two‐persongamewith•Thesegamesareplayedwithoneormorecompleteinformation.pilesofmatches.–Impartial:bothplayerscanmakethesamemoves(unlikechesswhereoneplayermayonlymovewhitepiecesand•Twoplayerstakeitinturnstoremovematchestheotherplayermayonlymoveblblkackpii)eces).accordingt
3、osomepre‐definedrules.–Two‐player:(thisoneshouldbeobvious).•Thewinner(sometimestheloser)istheplayer–Completeinformation:bothplayerscanseeallthattherethattakesthelastmatch.istobeseen(unlikebattleshipswhereeachplayercanonlyseetheirownboard).1WinningandLosingAnExample•Awinning
4、positionisoneinwhichtheplayer•Thereisasinglepileofmatches.whoseturnitistomovecan,bycorrectplay,•Anallowedmoveistotake1or2matchesfromthebecertainofwinning.pile.•Awinningstrategyisanalgorithmfor•Thewinneristheonewhotakesthelastmatch.choosingthemovefromawinningposition•Whatisa
5、winningposition?thatensuresthewin.•Whatisthewinningstrategy?AnExampleOtherExamples•Anypositioninwhichthereisamultipleof3•Whatarethewinningpositionsforeachofthematchesinthepileisalosingposition–anyotherfollowinggames?positionisawinningposition.1.Onepile–eachplayercantakeonem
6、atch.•Wewillleavethequestionofawinningstrategyuntil2.Onepile–eachplayercantakezeromatches.alittlelater.3.Onepile–eachplayercantakeatmostnmatches,wherenisfixedinadvance.4.Onepile–eachplayercantake1,3or4matches.2WinningStrategiesAssumptions•Bruteforce.•Thereareafinitenumberof
7、positions.–Listallpossiblepositionsinthegame.•Thegameisguaranteedtoterminate,nomatter–Arrangethemintoagraphshowingwhichpositionsleadtowhatmovesaremade.(I.e.therearenopossiblewhich.drawngames).–Labeleachpositionaswinningorlosing(ordrawn).–Labelthewinningmoves.•Inpractice,bru
8、teforceisnotagoodapproachbutwemayfindsomevalueinexaminingitanyway.•Forourexamplewe
此文档下载收益归作者所有