計算遊戲「GO」的分數

Question

有沒有人知道如何以編程方式計算Go遊戲中的分數？ 我有一個19x19的數組，這個數組的每個元素可以是0（空點），1（黑色石頭）或2（白色石頭）。我不明白我如何檢查該區域屬於任何顏色。

Answer 1

這是一個不平凡的問題，因爲通常Go遊戲會在玩家完成必要的所有動作之前結束，以明確遊戲的「真實」分數/值。有時候，假設一個玩家未達到最佳狀態（例如，讓對手完成一套在對手領土內有生命的寶石，即使可能殺死一組寶石），遊戲的價值也會不同。計算原始未入侵區域相當明顯，只需通過棋盤邊緣或一種顏色的棋子檢查每個可能的方向組合（正面和負面的水平和垂直）中的每個空間是否「切斷」。您可以通過從空白處開始寬度優先搜索來更高效地執行此操作，並且可以跟蹤處理過程中遇到的哪些顏色（不會從佔用的斑點遍歷BFS），並且一旦找不到更多的空白斑點，那麼如果發現的彩色片都是一種顏色，那麼發現的所有空白區都屬於該顏色，否則它們不屬於任何人。然後繼續廣度優先搜索與下一個未被發現的空白點，刪除所有以前探索的空白點。但是，如果對手在已經建立的領土上有一塊棋子，那麼在計算領土時理想情況下應該忽略這塊棋子，事實上甚至被視爲被俘。如果顯而易見的是，如果玩家在沒有犯錯的情況下玩出一組對手的棋子，那麼他們最終會被抓住。如果兩個球員都有一組棋子與另一個棋子相鄰，那麼情況就更加微妙了，這樣棋子就具有了「相互的生命」，即如果一個棋手試圖做出努力殺死對方的棋子，那麼對手將能夠殺死原始棋手的棋子，反之亦然。