예제 소스
SGF 기보로 학습하는 바둑 LLM 인공지능 · 파일 169개
gamejudge.cpp
#include "gamejudge.h"
#include <QQueue>
#include <QSet>
namespace GameJudge {
namespace {
constexpr int kDR[4] = {-1, 1, 0, 0};
constexpr int kDC[4] = {0, 0, -1, 1};
inline bool inBounds(int N, int r, int c)
{
return r >= 0 && r < N && c >= 0 && c < N;
}
struct EmptyRegion {
QVector<int> cells;
QSet<Stone> borderColors;
QSet<int> borderGroupIds;
};
} // namespace
Stone Analysis::settledOwner(int r, int c) const
{
if (!(r >= 0 && r < N && c >= 0 && c < N))
return Stone::Empty;
const int idx = r * N + c;
const int rid = cellRegion[idx];
if (rid < 0)
return Stone::Empty;
const RegionKind k = regionKind[rid];
if (k == RegionKind::SettledBlack)
return Stone::Black;
if (k == RegionKind::SettledWhite)
return Stone::White;
return Stone::Empty;
}
bool Analysis::isDame(int r, int c) const
{
if (!(r >= 0 && r < N && c >= 0 && c < N))
return false;
const int idx = r * N + c;
const int rid = cellRegion[idx];
return rid >= 0 && regionKind[rid] == RegionKind::Dame;
}
bool Analysis::isActive(int r, int c) const
{
if (!(r >= 0 && r < N && c >= 0 && c < N))
return false;
const int idx = r * N + c;
const int rid = cellRegion[idx];
return rid >= 0 && regionKind[rid] == RegionKind::Active;
}
Analysis analyze(const GoBoard &b)
{
Analysis res;
const int N = b.size();
res.N = N;
res.stoneToGroup.fill(-1, N * N);
res.cellRegion.fill(-1, N * N);
// ---------- 1) 돌 그룹 수집 + 활로 계산 ----------
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
const int idx = r * N + c;
const Stone s = b.cellAt(r, c);
if (s == Stone::Empty || res.stoneToGroup[idx] >= 0)
continue;
const int gid = res.groups.size();
GroupBrief g;
g.color = s;
QSet<int> libs;
QQueue<int> q;
q.enqueue(idx);
res.stoneToGroup[idx] = gid;
while (!q.isEmpty()) {
const int cur = q.dequeue();
++g.stones;
const int rr = cur / N;
const int cc = cur % N;
for (int d = 0; d < 4; ++d) {
const int nr = rr + kDR[d];
const int nc = cc + kDC[d];
if (!inBounds(N, nr, nc))
continue;
const int nidx = nr * N + nc;
const Stone v = b.cellAt(nr, nc);
if (v == s) {
if (res.stoneToGroup[nidx] < 0) {
res.stoneToGroup[nidx] = gid;
q.enqueue(nidx);
}
} else if (v == Stone::Empty) {
libs.insert(nidx);
}
}
}
g.liberties = libs.size();
res.groups.append(g);
}
}
// ---------- 2) 빈 영역 수집 ----------
QVector<EmptyRegion> regions;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
const int idx = r * N + c;
if (b.cellAt(r, c) != Stone::Empty || res.cellRegion[idx] >= 0)
continue;
const int rid = regions.size();
EmptyRegion er;
QQueue<int> q;
q.enqueue(idx);
res.cellRegion[idx] = rid;
while (!q.isEmpty()) {
const int cur = q.dequeue();
er.cells.append(cur);
const int rr = cur / N;
const int cc = cur % N;
for (int d = 0; d < 4; ++d) {
const int nr = rr + kDR[d];
const int nc = cc + kDC[d];
if (!inBounds(N, nr, nc))
continue;
const int nidx = nr * N + nc;
const Stone v = b.cellAt(nr, nc);
if (v == Stone::Empty) {
if (res.cellRegion[nidx] < 0) {
res.cellRegion[nidx] = rid;
q.enqueue(nidx);
}
} else {
er.borderColors.insert(v);
er.borderGroupIds.insert(res.stoneToGroup[nidx]);
}
}
}
regions.append(er);
}
}
// ---------- 3) 잠재 눈 카운트 ----------
// 한 색만 둘러싸고 크기가 작은(≤ 2) 빈 영역 = 그 색 그룹들의 잠재 눈.
// (false eye 검출까지는 안 함. 종반 판정엔 충분히 안전한 휴리스틱.)
for (const EmptyRegion &er : regions) {
if (er.borderColors.size() != 1)
continue;
if (er.cells.size() > 2)
continue;
for (int gid : er.borderGroupIds)
res.groups[gid].potentialEyes += 1;
}
// ---------- 4) alive 판정 ----------
// 종반 자충수/패스 권장이 정확히 작동하려면, 사실상 살아 있는 그룹은
// alive 로 잡혀야 한다 (그래야 그 주변 빈 영역이 SettledX 로 분류되어
// AiPlayer 가 "자기 집 메우기 -1500" 페널티를 발동시키고 gameIsOver 도 작동).
// 이전 버전은 "잠재 눈 ≥ 2 OR 돌+활로 ≥ 6+6" 으로 너무 보수적이었음.
//
// 새 기준 (보수적 → 관대 순):
// (a) 잠재 눈 ≥ 2 → 명백 alive
// (b) 잠재 눈 ≥ 1 + 돌 ≥ 3 + 활로 ≥ 3 → 한 눈 + 보강 가능
// (c) 돌 ≥ 4 + 활로 ≥ 4 → 작지만 단단한 그룹
// (d) 돌 ≥ 8 + 활로 ≥ 3 → 큰 그룹은 활로가 적어도 alive 가능성 매우 높음
for (GroupBrief &g : res.groups) {
if (g.potentialEyes >= 2)
g.alive = true;
else if (g.potentialEyes >= 1 && g.stones >= 3 && g.liberties >= 3)
g.alive = true;
else if (g.stones >= 4 && g.liberties >= 4)
g.alive = true;
else if (g.stones >= 8 && g.liberties >= 3)
g.alive = true;
}
// ---------- 5) 영역 분류 ----------
res.regionKind.resize(regions.size());
for (int i = 0; i < regions.size(); ++i) {
const EmptyRegion &er = regions[i];
const bool hasBlack = er.borderColors.contains(Stone::Black);
const bool hasWhite = er.borderColors.contains(Stone::White);
bool allBordersAlive = true;
for (int gid : er.borderGroupIds) {
if (!res.groups[gid].alive) {
allBordersAlive = false;
break;
}
}
if (hasBlack && hasWhite) {
res.regionKind[i] = allBordersAlive ? RegionKind::Dame : RegionKind::Active;
} else if (hasBlack) {
res.regionKind[i] = allBordersAlive ? RegionKind::SettledBlack : RegionKind::Active;
} else if (hasWhite) {
res.regionKind[i] = allBordersAlive ? RegionKind::SettledWhite : RegionKind::Active;
} else {
// 어느 색도 인접하지 않음 (개막처럼 빈 보드일 때) — 미정 = active.
res.regionKind[i] = RegionKind::Active;
}
}
// ---------- 6) 의미 있는 수 존재 여부 ----------
// active 영역이 한 군데라도 있으면 일단 둘 가치가 있는 후보. 하지만
// 종반에 자잘한 dame 자리만 남고 active 영역 총합이 매우 작으면
// "사실상 종국" 으로 본다 — 안 그러면 자충수가 끝없이 반복됨.
//
// 임계: active 총 점 수 > 4. (1~4 점 짜리 active 잔재는 의미 있는 수 없음.)
QVector<int> regionSizes(regions.size(), 0);
for (const EmptyRegion &er : regions) {
const int rid = res.cellRegion[er.cells.first()];
regionSizes[rid] = er.cells.size();
}
int activeSum = 0;
for (int i = 0; i < res.regionKind.size(); ++i) {
if (res.regionKind[i] == RegionKind::Active)
activeSum += regionSizes[i];
}
const bool anyMeaningful = activeSum > 4;
res.blackHasMeaningfulMove = anyMeaningful;
res.whiteHasMeaningfulMove = anyMeaningful;
return res;
}
bool shouldPass(const GoBoard &b, Stone who)
{
const Analysis a = analyze(b);
if (who == Stone::Black)
return !a.blackHasMeaningfulMove;
if (who == Stone::White)
return !a.whiteHasMeaningfulMove;
return true;
}
bool gameIsOver(const GoBoard &b)
{
const Analysis a = analyze(b);
return !a.blackHasMeaningfulMove && !a.whiteHasMeaningfulMove;
}
Estimate estimateScore(const GoBoard &b)
{
// 매 수 표시용 어림 계가: 종국 finalScoring 과 같은 analyze() 파이프라인을 쓴다.
// 중국식 area 근사 — 산 돌 + 확정 집 + (죽은 상대 돌 자리), 공배(dame)·분쟁(active)은 미가산.
// 생사/영역 휴리스틱이 좋아질수록 이 표시도 같이 정확해진다.
const Analysis a = analyze(b);
Estimate e;
e.komi = b.komi();
const int N = b.size();
for (int idx = 0; idx < N * N; ++idx) {
const Stone s = b.cellAt(idx / N, idx % N);
if (s != Stone::Black && s != Stone::White)
continue;
const int gid = a.stoneToGroup[idx];
if (gid < 0)
continue;
const GroupBrief &g = a.groups[gid];
if (g.alive) {
if (s == Stone::Black)
++e.blackAliveStones;
else
++e.whiteAliveStones;
} else {
// 사석 → 상대 영토 1점 (중국식 면적 계가 근사).
if (s == Stone::Black) {
++e.blackDeadStones;
++e.whiteTerritory;
} else {
++e.whiteDeadStones;
++e.blackTerritory;
}
}
}
for (int idx = 0; idx < N * N; ++idx) {
if (b.cellAt(idx / N, idx % N) != Stone::Empty)
continue;
const int rid = a.cellRegion[idx];
if (rid < 0 || rid >= a.regionKind.size())
continue;
switch (a.regionKind[rid]) {
case RegionKind::SettledBlack:
++e.blackTerritory;
break;
case RegionKind::SettledWhite:
++e.whiteTerritory;
break;
case RegionKind::Dame:
++e.dame;
break;
case RegionKind::Active:
++e.active;
break;
}
}
e.finalBlack = double(e.blackAliveStones + e.blackTerritory);
e.finalWhite = double(e.whiteAliveStones + e.whiteTerritory) + e.komi;
if (e.finalBlack > e.finalWhite) {
e.leader = Stone::Black;
e.margin = e.finalBlack - e.finalWhite;
} else if (e.finalWhite > e.finalBlack) {
e.leader = Stone::White;
e.margin = e.finalWhite - e.finalBlack;
} else {
e.leader = Stone::Empty;
e.margin = 0.0;
}
return e;
}
ScoreReport finalScoring(const GoBoard &b)
{
const Analysis a = analyze(b);
const int N = b.size();
ScoreReport rep;
rep.komi = b.komi();
// 1) 그룹별 처리: alive → 자기 돌, dead → 사석으로 상대 territory 에 가산.
QVector<bool> stoneCounted(N * N, false);
for (int gid = 0; gid < a.groups.size(); ++gid) {
const GroupBrief &g = a.groups[gid];
if (g.color != Stone::Black && g.color != Stone::White)
continue;
// 그룹의 돌 좌표를 stoneToGroup 에서 모은다.
for (int idx = 0; idx < N * N; ++idx) {
if (a.stoneToGroup[idx] != gid) continue;
stoneCounted[idx] = true;
if (g.alive) {
if (g.color == Stone::Black) ++rep.blackStones;
else ++rep.whiteStones;
} else {
// 사석 (숨구멍이 없는/살지 못한 그룹) → 상대 territory.
if (g.color == Stone::Black) ++rep.whiteTerritory;
else ++rep.blackTerritory;
}
}
}
// 2) 빈 영역 + dead 그룹 위치 합쳐서 BFS. dead 그룹은 빈칸처럼 통과 가능
// (사석으로 처리된 자리 = 상대 territory 의 일부).
// 인접한 alive 그룹 색만 border 로 본다.
QVector<bool> visited(N * N, false);
int dameTotal = 0;
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
const int sidx = r * N + c;
if (visited[sidx]) continue;
const Stone sv = b.cellAt(r, c);
int sgid = a.stoneToGroup[sidx];
const bool isEmpty = (sv == Stone::Empty);
const bool isDeadStone = (!isEmpty && sgid >= 0 && !a.groups[sgid].alive);
if (!isEmpty && !isDeadStone) {
visited[sidx] = true;
continue;
}
QQueue<int> q;
q.enqueue(sidx);
visited[sidx] = true;
QVector<int> region;
bool aliveBlack = false;
bool aliveWhite = false;
int emptyCells = 0;
while (!q.isEmpty()) {
const int idx = q.dequeue();
region.append(idx);
if (b.cellAt(idx / N, idx % N) == Stone::Empty)
++emptyCells;
const int rr = idx / N;
const int cc = idx % N;
for (int d = 0; d < 4; ++d) {
const int nr = rr + kDR[d];
const int nc = cc + kDC[d];
if (!inBounds(N, nr, nc)) continue;
const int nidx = nr * N + nc;
if (visited[nidx]) continue;
const Stone nv = b.cellAt(nr, nc);
if (nv == Stone::Empty) {
visited[nidx] = true;
q.enqueue(nidx);
} else {
const int ngid = a.stoneToGroup[nidx];
if (ngid < 0) continue;
const GroupBrief &g = a.groups[ngid];
if (!g.alive) {
// dead 그룹은 통과해서 그 자리를 영역에 포함.
visited[nidx] = true;
q.enqueue(nidx);
} else {
if (g.color == Stone::Black) aliveBlack = true;
else if (g.color == Stone::White) aliveWhite = true;
}
}
}
}
// 빈 점만 territory/dame 으로 카운트 (dead 돌 자리는 위에서 사석 처리됨).
const int sz = emptyCells;
if (aliveBlack && !aliveWhite) {
rep.blackTerritory += sz;
} else if (aliveWhite && !aliveBlack) {
rep.whiteTerritory += sz;
} else {
// 양쪽 alive 인접 또는 어느 쪽 alive 도 인접 안 함 → dame 으로.
dameTotal += sz;
}
}
}
// 3) 공배(dame)는 어느 쪽 점수도 아님 (중국식/일본식 공통).
rep.dame = dameTotal;
// 4) 최종 점수 (중국식 area: 산 돌 + 영토 + 사석 환원분, 덤은 백).
rep.finalBlack = rep.blackStones + rep.blackTerritory;
rep.finalWhite = rep.whiteStones + rep.whiteTerritory + rep.komi;
if (rep.finalBlack > rep.finalWhite) rep.winner = Stone::Black;
else if (rep.finalWhite > rep.finalBlack) rep.winner = Stone::White;
else rep.winner = Stone::Empty;
return rep;
}
} // namespace GameJudge