使用不同迴圈規則小棋盤圍棋殘局庫的建構及觀察

Small-board-sized Go endgames for different cycle-breaking rules: Constructions and Observations

許嘉銘(Chia-Ming Hsu)

指導教授 ： 薛智文

共同指導教授 ： 徐讚昇(Tsan-Sheng Hsu)

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2022年)

https://doi.org/10.6342/NTU202202858

摘要

圍棋在古代就被發明出來，是一個歷史悠久的遊戲，世代相傳。到了現在，雖然規則與以往不同，但在很多國家也都一直是個熱門的遊戲，圍棋的規則簡單明瞭，但玩法變化多端，因此圍棋被認為是世界上最受歡迎且有趣的棋類遊戲之一。本論文在建構4路圍棋的殘局知識庫，提供了一個圍棋殘局知識庫的建立流程。我們使用AGA圍棋計分規則，實作包含完全禁止迴圈和只禁止長度為二的劫爭迴圈在內的兩種棋規，並透過殘局知識庫觀察和探討禁止迴圈和不同圍棋規則對於圍棋決策的影響。最後建立2路、3路和5路的圍棋殘局知識庫，觀察不同棋盤大小的圍棋的解和迴圈的關聯。

關鍵字

圍棋 ； 圍棋循環 ； 殘局知識庫 ； 強連通元件 ； 回溯分析

並列摘要

Go was invented in ancient times. It is a game with a long history and has been passed down through generations. Now, although the rules are different from the past, Go has always been a popular game in many countries. The rules of Go are simple and clear, but there are many ways to play it. So Go is considered one of the most popular and interesting board games in the world. In this thesis, we propose a process to build the 4x4 Go endgame databases. We use the AGA scoring rules and try different rules, including no cycle is allowed and only allows length-2 cycles formed by ko. We analyze the impact of prohibiting cycles on the endgame databases we build. Finally, we build the endgames for 2x2 Go, 3x3 Go, and 5x5 Go and observe the relationship between the board size and cycle dealing rules.

並列關鍵字

Go ； cycles in Go ； endgame database ； strongly connected component ； retrograde analysis

參考文獻

11th computer olympiad. https://icga.org/icga/news/Olympiad/Olympiad2006/. Accessed June 8, 2022.

Aga rules. https://www.usgo.org/aga-concise-rules-go. Accessed April 29, 2022.

Asian tv cup. https://www.nihonkiin.or.jp/match/tv-asia/archive.html. Accessed April 29, 2022.

British go journal - number 174. https://www.britgo.org/files/2016/deepmind/BGJ174-AlphaGo.pdf. Accessed June 8, 2022.

Chinese rules. http://home.snafu.de/jasiek/c2002.pdf. Accessed April 29, 2022.