휴리스틱 세력 함수를 이용한 바둑 사활 문제의 눈모양 분석

• 영문명: Eye Shape Analysis of Life-and-Death Problems with a Heuristic Influence Function, in the Game of Go
• 발행기관: 한국컴퓨터게임학회
• 저자명: 이병두(Byung Doo Lee)
• 간행물 정보: 『한국컴퓨터게임학회논문지』제15호, 111~117쪽, 전체 7쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2008.12.30

국문 초록

바둑에 있어 사활 문제는 컴퓨터 바둑을 구현하기 위하여 반드시 극복되어져야 하는 기본적인 문제이다. 사활 문제와 같은 국부적인 문제를 풀기 위하여, 중요하게 고려되어야 할 사항은 어떻게 하면 게임 트리의 분기수와 그 깊이를 줄일 수 있느냐는 것이다. 본 논문에서는 게임 트리를 위한 첫 수들을 생성하기 위하여 휴리스틱 세력 함수로 눈 모양 분석이라는 초유의 방법을 적용하였다. 휴리스틱 세력 함수로 둘러싸인 돌들의 눈 모양을 분석하는 주요 목적은 아주 짧은 시간내에 둘러싸인 돌들이 살았는지, 미생(未生)인지 아니면 죽었는지를 판단하는 것이다. 만약 둘러싸인 돌들이 죽거나 미생일 경우가 높으면, 완전 게임 트리 내에서 최선의 수순을 찾아내기 위해 소요되는 엄청난 계산 시간을 절약할 수 있는 가능한 급소 점(첫 수)들로 사용될 수가 있다. 비록 눈 모양 분석기는 40% 미만의 정확도를 보였지만, 단순한 휴리스틱 세력함수로 된 눈 모양 분석기는 짧은 시간 내에 둘러싸인 돌들의 생사 여부를 판단하는 데 상당한 도움이 됨을 발견했다.

영문 초록

In the game of Go, the life-and-death problem is a fundamental problem to be definitely overcome for implementing a computer Go program. To solve local Go problems such as life-and-death problems, an important consideration is how to tackle the game tree's huge branching factor and its depth. We applied a novel method, eye shape analysis with a heuristic influence function, to generate a set of first moves for the game tree. The main objective of analyzing the eye shape of a surrounded group with a heuristic influence function is to determine in a short time whether the surrounded group is alive, dead or unsettled. If there is a high possibility that the surrounded group is dead or unsettled, then we can use the possible vital points (the first moves) to save enormous amounts of computing time in searching for the best sequence of moves in a complete game tree. Although the resulting accuracy of the eye shape analyzer is less than 40%, we found that the eye shape analyzer with a simple heuristic influence function can significantly contributes to quickly finding the life-and-death status of the surrounded group.

목차

Ⅰ. Introduction

II. Eye Shape Analysis

III. Conclusions

References

키워드

컴퓨터 바둑 사활 문제 눈 모양 분석 휴리스틱 세력 함수 Computer Go Life-and-Death Problem Eye shape analysis Heuristic influence function