본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

컴퓨터 바둑에서 String Graph를 사용한 정적분석
Static Analysis In Computer Go By Using String Graph

박현수   (경동정보대학 컴퓨터정보기술과UU0000085  ); 김항준   (경북대학교 컴퓨터공학과UU0000096  );
  • 초록

    본 논문은 정적 분석을 하기 위해서 SG(String Graph)를 정의하고 ASG(Alive String Graph)를 정의한다. String의 사활의 판단을 위해 돌이 포함되지 않은 상태와 돌이 포함된 상태로 나누어 Rule을 적용한다. 돌이 포함되지 않은 상태에서 SR(String Reduction), ER(Empty Reduction), ET(Edge Transform), 그리고 CG(Circular Graph) Rule을 정의한다. 돌이 포함되어진 상태에서 DESR(Dead Enemy Strings Reduction)과 SCSR(Same Color String Reduction) Rule을 정의한다. 이러한 Rule을 사용하여 SG(String Graph)가 ASG(Alive String Graph)인지를 평가한다. 그리고 관절점의 개수에 따라 사활을 판단하기 위해 APC(Articulation Point Check)를 사용하였다. 우리의 방법에 대한 성능은 Computer Go Test Collection의 IGS_31_counted 문제 집합에 대해 실험했다. 이 Test set은 11,191 Points와 1,123 Strings을 가진다. 우리는 실험 결과에서 Points에 대해 92.5% 정확성과 Strings에 대해 95.7%의 정확성을 얻었다.


    We define a SG(String Graph) and an ASG(Alive String Graph) to the purpose to do static analysis. For a life and death judgment, we apply the rule to the situation which the stone is included and not included. We define the rules that are SR(String Reduction), ER(Empty Reduction), ET(Edge Transform), and CG(Circular Graph), when the stone is not included. We define the rules that are DESR(Dead Enemy Strings Reduction) and SCSR(Same Color String Reduction), when the stone is included. We evaluate a SG that it is an ASG or not by using rules. And we use APC(Articulation Point Check) nile according to number of articulation points lot a life and death judgment. The performance of our method has been tested on the problem set IGS_31_counted form the Computer Go Test Collection. The test set contains 11,191 Points and 1,123 Strings. We obtain 92.5% accuracy of Points and 95.7% accuracy of Strings.


  • 주제어

    Static Analysis .   String Graph .   Alive String Graph .   String Reduction .   Circular Graph.  

  • 참고문헌 (6)

    1. Thore Graepel, Mike Goutrie, Marco Kruger, and Half Herbrich. Learning on graphs in the game of Go 
    2. Muller, M. Computer Go. Artificial Intelligence, Vol. 134, Nos. 1-2,pp. 145-179. ISSN 0004-3702. 2002 
    3. Muller, M. Playing it safe: Recognizing secure territories in computer Go by using static rules and search. Game Programming Workshop in Japan '97(Ed. H Matsubara), pp.80-86, Computer Shogi Association, Tokyo, Japan, 1997 
    4. Benson, D.B. Life in the game of Go, Information Sciences, Vol. 10, pp 17-29, ISSN 0020-0255. Reprinted in Computer Games,(Ed. D.N.L.Levy), Vol. II, pp. 203-213, Springer-Verlag, New York, N. Y. ISBN, 1976 
    5. Popma, R. and Allis, L.V. Life and death refined. Heuristic Porgramming in Artificial Intelligence 3(Eds. H.J. van den Herik and L.V.Allis), pp. 157-164. Ellis Horwood Ltd., Chichester, Englad, ISBN 
    6. T.Wolf, Investigating Tsumego problems with RisiKo, in L D. Levy, D. Beal(Eds,), Heuristic Programming in Artificial Intelligence 2, pp. 153-100, Ellis Horwood, Chichester, 1991. In International. Conference on Artificial Neural Networks (ICANN-01), Vienna, Austria, 2001 

 저자의 다른 논문

  • 박현수 (3)

    1. 2003 "컴퓨터 바둑에서 String안정도와 Group 영역에 의한 정적분석" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 40 (6): 76~86    
    2. 2007 "컴퓨터 바둑에서 돌의 영향력, 영향력점 그리고 영향력영역에 대한 연구" 한국게임학회 논문지 = Journal of Korea Game Society 7 (4): 117~123    
    3. 2007 "컴퓨터 바둑에서 계가 알고리즘" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 44 (1): 49~55    
  • 김항준 (18)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기