CSCI103_05a_WinningLosing(print)4.pdf

《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