文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 文学研究 > go-moku-and-threat
侵权投诉

go-moku-and-threat

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

第1页

你可能喜欢

热门文档

相关文档

  • allis1994

    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) 诘...

  • ...of Computer Virus Occurrence and Virus Threat Le...

    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 ...

  • ...of Computer Virus Occurrence and Virus Threat Le...

    The Effect of Computer Virus Occurrence and Virus Threat Level on Anti-virus Companies’ Financial Performance* John R. Harrald’, Sonia A. Schmitt’, ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email