Go-MokuandThreat-SpaceSearch
L.V.H.J.vanAllis
denHerik
UniversityofLimburgP.O.Box616
6200MDMaastricht,TheNetherlands{allis,herik}@cs.rulimburg.nl
Abstract
Manydecadesago,JapaneseprofessionalGo-MokuplayersstatedthatGo-Moku(Five-in-a-rowonahorizontallyplaced15×15board)isawongamefortheplayertomovefirst.Sofar,thisclaimhasneverbeensubstantiatedby(atreeof)variationsorbyacomputerprogram.MeanwhilemanyvariantsofGo-Mokuwithslightlydifferentruleshavebeendeveloped.Thispapershowsthatfortwocommonvariantsthegame-theoreticalvaluehasbeenesta-blished.
Moreover,theGo-MokuprogramVictoriaisdescribed.Itusestwonewsearchtechniques,threat-spacesearchandproof-numbersearch.OneoftheresultsisthatVictoriaisboundtowinagainstany(optimal)counterplayifitmovesfirst.Further-more,itachievesgoodresultsasadefenderagainstnon-optimallyplayingopponents.Inthiscontribu-tionwefocusonthreat-spacesearchanditsadvan-tagescomparedtoconventionalsearchalgorithms.1.Introduction
JapaneseprofessionalGo-Mokuplayershavestatedformanydecadesthattheplayertomovefirst(i.e.,Black)hasanassuredwin(SakataandIkawa,1981).Still,uptothiscontribution,asfarasweknow,noproofhasbeenpublishednorhasanyGo-MokuprogramevershowntobeundefeatablewhenplayingBlack.AsacaseinpointwementionthegamebetweentheGo-Moku1991WorldChampionprogramVertex(Black)andtheprogramPolygon(White),VertexmaneuvereditselfintoapositionprovablylostforBlack(Uiterwijk,1992a).Theintriguingdifferencebetweenhumanstrategicabilitiesandtheperformanceofthestate-of-the-artcomputerprogramsmakesGo-Mokuanattractiveresearchdomain.Theinvestigationsfocusonthediscoveryofnewdomain-specificstrategicknowledgeandonthedevelopmentofnewsearchtechniques.Bothissuesarediscussedbelowalthoughemphasisisplacedonanewsearchtech-nique.
Thecourseofthisarticleisasfollows.Insection2,therulesoffiveGo-Mokuvariantsarebriefly
M.P.H.Huntjens
VrijeUniversiteitDeBoelelaan1081
1081HVAmsterdam,TheNetherlandsmatty@cs.vu.nl
discussed.Insection3,someinsightisgivenintothewayofthinkingbyhumanGo-Mokuexperts,the"thinking"ofthestrongestcomputerprogramsandthemaindifferencesbetweenthem.Section4con-tainsadescriptionofthreat-spacesearch.Theresultsofthisnewsearchtechniquearepresentedinsection5.TheGo-MokuprogramVictoriaisdescribedinsection6.Themainresultisgiveninsection7:howVictoriasolvedthecommonvariantofGo-Moku.Section8containsconclusions.2.TherulesofGo-Moku
InGo-Moku,simplerulesleadtoahighlycomplexgame,playedonthe225intersectionsof15horizon-taland15verticallines.Goingfromlefttorighttheverticallinesareletteredfrom’a’to’o’;goingfromthebottomtothetopthehorizontallinesarenum-beredfrom1to15.Twoplayers,BlackandWhite,moveinturnbyplacingastoneoftheirowncoloronanemptyintersection,henceforthcalledasquare.Blackstartsthegame.Theplayerwhofirstmakesalineoffiveconsecutivestonesofhiscolor(horizontally,verticallyordiagonally)winsthegame.Thestonesonceplacedontheboardduringthegamenevermoveagainnorcantheybecap-tured.Iftheboardiscompletelyfilled,andnoonehasfive-in-a-row,thegameisdrawn.
ManyvariantsofGo-Mokuexist;theyallrestricttheplayersinsomesense,mainlyreducingtheadvantageofBlack’sfirstmove.Wementionfivevariants.
A.Intheearlydaysthegamewasplayedona19×19board,sinceGoboardshavethatsize.Thisvariantisstilloccasionallyplayed.How-ever,thelargerboardsizeincreasesBlack’sadvantage(SakataandIkawa,1981).B.Anoverlineisalineofsixormoreconsecutivestonesofthesamecolor.InthevariantofGo-Mokuplayedmostoftentoday,anoverlinedoesnotwin(thisrestrictionappliestobothplayers).Onlyalineofexactlyfivestonesisconsideredasawinningpattern.C.Blackplayshisfirstmoveusuallyatthecentersquareandhissecondmovediagonally
Moreover, the Go-Moku program Victoria is described. It uses two new search techniques, threat-space search and proof-number search. One of the results...
(half an eye) 半眼 han-ko 半劫 han-moku (...(ko threat) 劫材 (*) kyu 级 (*) kyusho (...(*) tsume-go (a life and death problem) 诘...
The Effect of Computer Virus Occurrence and Virus Threat Level on Anti-virus Companies’ Financial Performance* John R. Harrald’, Sonia A. Schmitt’, ...
(ko threat) 在对方提劫后,棋手的一个使对方不得...(mimic go) 一种不常见的对弈方式,棋手在盘面斜...(mokuhazushi) 三五的日本说法 模样 (moyo) 实地...
(half an eye) 半眼 han-ko 半劫 han-moku (...(ko threat) 劫材 (*) kyu 级 (*) kyusho (...(*) tsume-go (a life and death problem) 诘...
Go-Moku was solved by Allis in 1992. He proved that it is a won game...(Allis, Van der Meulen, and Van den Herik, 1994) and threat-space ...
The Effect of Computer Virus Occurrence and Virus Threat Level on Anti-virus Companies’ Financial Performance* John R. Harrald’, Sonia A. Schmitt’, ...
热门文档