Deductive Reasoning: Prototypical Eye Shape Analysis in the Life-and-Death Problems of Go, using Constraint Satisfaction and Point Pattern Matching
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Go has a history of at least 2,500 years and has been regarded as a unique game field for humans, but in 2016 it became the last board game to be overpowered by alphaGo, a computer Go. The life-and-death problem in Go becomes a fundamental problem domain that must be solved when implementing a computer Go. Deductive reasoning is a term in logic that infers new facts based on known judgements. In this paper, we tried to find the 4-tuple forms representing the prototypical eye shapes of 3-eyes, 4-eyes, 5-eyes, and 6-eyes, which are directly related to the life-and-death problems, by using the constraint satisfaction method for deductive reasoning. Afterwards, we tried to figure out the number of prototypical eye shapes of each eyes by using point pattern matching with the generated 4-tuple form. According to the experimental results, we can see that the 4-tuple forms have 1 for 3-eyes, 3 for 4-eyes, 4 for 5-eyes, and 8 for 6-eyes. We also found that the numbers of prototypical eye shapes for each eyes are 2 for 3-eyes, 5 for 4-eyes, 12 for 5-eyes, and 35 for 6-eyes. Lastly, for solving the life-and-death problem in computer Go, we also presented prototypical eye shapes as the 5-tuple forms which are variants of 4-tuple forms.
Abstract
Go has a history of at least 2,500 years and has been regarded as a unique game field for humans, but in 2016 it became the last board game to be overpowered by alphaGo, a computer Go. The life-and-death problem in Go becomes a fundamental problem domain that must be solved when implementing a computer Go. Deductive reasoning is a term in logic that infers new facts based on known judgements. In this paper, we tried to find the 4-tuple forms representing the prototypical eye shapes of 3-eyes, 4-eyes, 5-eyes, and 6-eyes, which are directly related to the life-and-death problems, by using the constraint satisfaction method for deductive reasoning. Afterwards, we tried to figure out the number of prototypical eye shapes of each eyes by using point pattern matching with the generated 4-tuple form. According to the experimental results, we can see that the 4-tuple forms have 1 for 3-eyes, 3 for 4-eyes, 4 for 5-eyes, and 8 for 6-eyes. We also found that the numbers of prototypical eye shapes for each eyes are 2 for 3-eyes, 5 for 4-eyes, 12 for 5-eyes, and 35 for 6-eyes. Lastly, for solving the life-and-death problem in computer Go, we also presented prototypical eye shapes as the 5-tuple forms which are variants of 4-tuple forms.
참고문헌 (17)
- 이병두, "세력 함수를 활용한 알파고 간의 50개 대국에 대한 형세 판단", 한국게임학회 논문지, 21(3), pp.107~116 (2021), 한국게임학회
- A. E. Nagy, "The Game is Not over Yet – Go in the Post-AlphaGo Era", Philosophies, 5(37), pp.1~15 (2020)
- D. B. Benson, "Life in the game of Go", Information Intelligence, 9(1), pp.91~124 (1976)
- 이병두, "바둑에서의 사활문제 해결을 위한 외곽선 추적", 한국게임학회 논문지, 20(2), pp.91~100 (2020), 한국게임학회[DOI]
- K. Chen, "Static analysis of life and death in the game of Go", Journal of Information Sciences, 121, pp.113~134 (1999)
- N. Sasaki, "A Neural Network Program of Tsume-Go", Computer and Games, pp.167~182 (1998)
- D. Silver, "Mastering the game of Go with deep neural networks and tree search", Journal of Nature, 529(7587), pp.484~489 (2016)
- B. H. Shekar, "Shape Representation and Classification through Pattern Spectrum and Local Binary Pattern", 2014 Fifth International Conference on Signal and Image Processing (2014)
- M. Tico, "Point Pattern Matching using a Genetic Algorithm and Voronoi Tessellation", 9th European Signal Processing Conference (EUSIPCO 1998, pp.1~4 (1998)
- W. Xiaoyun, "Point Pattern Matching Algorithm for Planar Point Sets under Euclidean Transform", Journal of Applied Mathematics, 2012 (2012)
- B. D. Lee, "Multi-strategic Learning, Reasoning and Searching in the Game of Go", PhD, pp.2005
- M. A. Akta, "Shape Descriptors", PhD, pp.2012
- D. Aiger, "Approximate input sensitive algorithms for point pattern matching", Pattern Recognition, 43, pp.153~159 (2010)
- "Life and Death"[URL]
- "Combining tactical search and deep learning in the game of Go" (2021)[URL]
- "Constraint satisfaction problem" (2021)[URL]
- "Hausdorff distance" (2021)[URL]