컴퓨터 바둑에서 안정도와 string graph를 이용한 형세평가
Status evaluation in computer go using stability and string graph /d朴鉉秀
ii, 127 p.
- 원문 URL
In this paper, we present a methodology of status evaluation using stability and string graph. We classify string and group stability heuristically and get a threshold value of influence using Joseki data and define a string graph. We classify a string stability heuristically and divide the board into group territory in computer go. Elements of string stability are eye (e), eye-like (el), special-eye (se), extension-point (ex), liberty (l) and connection-point (cp). A string stability has 5 levels that are complete alive, alive, unsettled, danger and killed level. A group is made strings and link-points and have the territory. Territory division of a group is acquired by string stability and link-points which are marym-mo, hankan, nalil-ja, and twokan between string and string. We compare our method with the result of evaluation of professional player. As a result, the mean error for evaluation is 9.2. We define a influence value and a threshold value by using Joseki data. A new methodology that combined the previous method with a influence value is more efficient than the previous method. As a result, the mean error for evaluation with a influence is 6.3. A string graph (SG) and alive string graph (ASG) are presented for a static analysis of a Go game. For a life and death judgment, various rules are applied to the situation where a stone is included and not included. These rules are defined as a string reduction (SR), empty reduction (ER), edge transform (ET), and circular graph (CG) when the stone is not included, and a dead enemy string reduction (DESR) and same color string reduction (SCSR) when the stone is included. Whether an SG is an ASG or not is then determined using these rules. Plus, an Articulation Point Check (APC) rule according to number of articulation points is also used for a life and death judgment. The performance of our method has been tested on the problem set IGS_31_counted from the computer go test collection. The test set contains 11,191 points and 1,123 strings. We obtain 100% accuracy of points and accuracy of strings. At last, we test on the problem set, Dave Jarvis's problem from the BGA's collection (http://www.britgo.org/gopcres/gopcres1.html). We extract 362 probelms from the problem set because a number of games have errors of komi. The games have been played to completion and counted. We evaluate it by using the procedure which has the stability of string, area of string, influence, and string graph. As the result, the mean error of proposed method is 4.15, CGoban's is 8.66, and HT2000's is 5.96.