to appear in ICGA Journal Hex Gold at Graz Six defeats Mongoose

This year’s tournament had two new entrants: Six by Gábor Melis, and Mongoose

toappearinICGAJournal

HexGoldatGraz:SixdefeatsMongoose

G´aborMelis1andRyanHayward2

Thecontestants.2003sawaHextournamenttakeplaceattheComputerGames

Olympiadforthe rsttimesince2000,whenVadimAnshelevich’sHexy(gold)defeated

JackvanRijswijck’sQueenbee(silver)andEmanuelBrasa’sKillerBee(bronze)[1].Thisyear’stournamenthadtwonewentrants:SixbyG´aborMelis,andMongoosebyYngviBjornsson,RyanHayward,MikeJohanson,MorganKan,andNathanPo.BothprogramsincorporatethekeyideasbehindHexy[2], ndingvirtualconnectionsviaH-search(whichusesandandorcompositionrules)andthencomputinganedge-to-edgeresistancemeasurebasedonwhichpairsofcellsarevirtuallyconnected.

Sixperformsa2-plysearchwithalpha-betapruning,analysingthemostpromising201-plyand152-plymoves.Withagametreesearchthisshallow,mostoftheworkisdonewithintheH-search.Six’simplementationofH-searchkeepstrackofallcomputedvirtualconnectionsandvirtualsemi-connectionsbetweengroups,butusesonlyasmallnumberofthem,namelythosewiththesmallestcarriers(thecarrierofavirtualconnectionistheassociatedsetofemptycellswhichguaranteestheconnection).ThefeaturewhichmostcontributestoSix’scharacteristicstyleofplayisthecomputationofconnectionswhichgothroughtheedgeoftheboard,namelyconnectionswhichcanonlybeconstructedbyusingoneoftheboardedgesasthepivotpointintheandrule.Sixdoesnothaveanopeningbook.Duringtheopeningfourmovesofthegame,itdispenseswith2-plyaltogetherandconsidersonly301-plymoves,althoughwithanH-searchwhichismorethoroughthanusual.TheSixsourcecodecanbefreelydownloadedfromhttp://hex.retes.hu/six.

Mongooseusesalpha-betasearchwithiterativedeepening,searchingasdeeplyastheallocatedtimeforagivenmovepermits.Foropeningplay,itusesabookforthe rsttwotofourmoves,dependingontheposition.AcharacteristicfeatureofMongooseisitsmovepruning.Asdescribedin[3],itreducesthenumberofmovesunderconsiderationbyinsomecasesdeducingthatamoveisprovablyinferiortosomeothermove,andinothercasesdeterminingthatoneormorestonescanbeaddedtotheboardwithoutchangingthetheoreticaloutcomeofthegame.

Double-round1.The rstSix/Mongoosedouble-roundoffourgames(Figures1and

2)startedintheGrazCasinoonSundayNovember23at14:00.Six(black)openedGame1with1.A3andwonquicklyafterquestionableearlymoves6.H5and10.E5byMongoose.MongooseopenedGame2with1.B3andSixswapped(takingblack).Again,Sixwon

mega@http://www.wendangwang.com,http://six.retes.hu/

DepartmentofComputingScience,UniversityofAlberta,EdmontonCanada,hayward@cs.ualberta.ca,http://www.cs.ualberta.ca/~hayward.ThesupportofNSERCandtheUofAGAMESgroupisgratefullyacknowledged.

21

to appear in ICGA Journal Hex Gold at Graz Six defeats Mongoose相关文档

最新文档

返回顶部