바둑 메타버스 내 오목 및 바둑 AI 로직 분석

바둑 메타버스 내에서 게임 플레이를 담당하는 game-worker.js 파일은 오목과 바둑이라는 두 가지 보드 게임의 인공지능(AI) 로직을 포함하고 있습니다. 이 문서는 각 게임의 AI가 어떤 원리와 전략을 사용하여 최적의 수를 찾아내는지에 대해 상세히 설명합니다. 특히, 오목 AI는 '미니맥스' 알고리즘과 '알파-베타 가지치기'를 통해 승리 경로를 탐색하며, 바둑 AI는 복합적인 '휴리스틱' 평가 함수를 통해 바둑의 다양한 전술적, 전략적 요소를 고려하여 착수합니다.

오목 AI의 핵심 목표는 가장 빠른 승리 경로를 찾거나 상대방의 승리를 확실하게 저지하는 것입니다. 이를 위해 게임 트리 탐색 기법인 미니맥스(Minimax) 알고리즘과 그 효율을 높이는 알파-베타 가지치기(Alpha-Beta Pruning)를 활용합니다.

오목 AI는 보드의 특정 부분을 '창(Window)'으로 보고 해당 창 내의 돌 배치를 평가하여 점수를 부여합니다. 이는 각 수가 가져올 수 있는 잠재적 가치를 수치화하는 과정입니다.

• SCORES (점수표)

• evaluateWindow(window, color) 함수
  1. 5칸짜리 '창'을 분석하여 현재 플레이어(color)와 상대방 돌의 개수, 빈 공간의 개수를 파악합니다.
  2. 상대방이 열린 4나 열린 3을 만드는 경우, 이를 막아야 하는 긴급 상황이므로 각각 높은 음수 점수( -SCORES.FOUR) 및 (-SCORES.THREE)를 부여하여 AI가 방어하도록 유도합니다.

이 함수는 미니맥스 알고리즘이 특정 보드 상태의 가치를 판단하는 휴리스틱 함수입니다.

• 평가 방식
  1. 행, 열, 대각선 점수: 바둑판의 모든 가능한 5칸짜리 '창'에 대해 evaluateWindow 함수를 적용하여 점수를 합산합니다.
  2. 위치 보너스: 돌이 중앙에 가까울수록 약간의 보너스 점수를 부여하여, 초반에 중앙을 선점하도록 유도합니다. 이는 바둑판 중앙이 사방으로 확장하기 좋다는 전략적 판단을 반영합니다.

오목 AI의 핵심 의사결정 로직입니다.

• 미니맥스 알고리즘:
  1. AI(Maximizing Player)는 자신의 점수를 최대화하고, 상대방(Minimizing Player)은 AI의 점수를 최소화하려고 한다는 가정하에 가능한 모든 경우의 수를 트리 형태로 탐색합니다.
  2. 게임의 끝(승리/패배/무승부) 또는 미리 정해진 최대 탐색 깊이(depth)에 도달하면 scorePosition 함수로 현재 국면의 가치를 평가합니다.
  3. 현재 코드에서는 SEARCH_DEPTH가 2로 설정되어 있어, AI는 자신의 다음 수와 그에 대한 상대방의 응수까지 총 2수를 예측합니다.

• 알파-베타 가지치기:
  1. 미니맥스 탐색의 효율성을 극대화하는 기법입니다.
  2. alpha (최대화 플레이어가 보장할 수 있는 최저 점수)와 beta (최소화 플레이어가 보장할 수 있는 최고 점수) 값을 유지하며 탐색합니다.
  3. 만약 현재 경로에서 alpha가 beta보다 커지거나 같아지면, 해당 경로를 더 이상 탐색할 필요가 없다고 판단하여 가지치기합니다. 이는 불필요한 계산을 대폭 줄여줍니다.

아래는 미니맥스 및 알파-베타 가지치기 알고리즘의 개념적인 코드 예시입니다.

function minimax(board, depth, alpha, beta, maximizingPlayer, aiColor) {
    // 게임 종료 또는 최대 깊이 도달 시 보드 평가
    if (depth === 0 || checkWin(board, /* any color */) || checkDraw(board)) {
        return scorePosition(board, aiColor);
    }

    // AI 턴 (최대화 플레이어)
    if (maximizingPlayer) {
        let maxEval = -Infinity;
        for (const move of getPossibleMoves(board)) {
            const newBoard = applyMove(board, move, aiColor);
            const evaluation = minimax(newBoard, depth - 1, alpha, beta, false, aiColor);
            maxEval = Math.max(maxEval, evaluation);
            alpha = Math.max(alpha, evaluation);
            if (beta <= alpha) { // 알파-베타 가지치기
                break;
            }
        }
        return maxEval;
    } else { // 상대방 턴 (최소화 플레이어)
        let minEval = Infinity;
        for (const move of getPossibleMoves(board)) {
            const newBoard = applyMove(board, move, getOpponentColor(aiColor));
            const evaluation = minimax(newBoard, depth - 1, alpha, beta, true, aiColor);
            minEval = Math.min(minEval, evaluation);
            beta = Math.min(beta, evaluation);
            if (beta <= alpha) { // 알파-베타 가지치기
                break;
            }
        }
        return minEval;
    }
}

• 승리 판정 함수 (checkGomokuWin 및 checkWin):
  1. 특정 위치에 돌을 놓았을 때 5목이 완성되는지 확인합니다. checkWin은 checkGomokuWin을 호출하여 전체 보드에서 승리 여부를 판정합니다. 미니맥스 탐색의 종료 조건 중 하나로 사용됩니다.

AI가 실제로 착수할 위치를 결정하는 함수입니다.

1. 우선순위 기반 결정:
   1. 1. 즉시 승리 지점 확인: AI(백돌)가 한 수를 두어 바로 오목을 완성할 수 있는 곳이 있는지 가장 먼저 탐색합니다. 있다면 해당 위치에 착수합니다.
   2. 2. 상대방 승리 방어 지점 확인: 상대방(흑돌)이 다음 수에 오목을 완성할 수 있는 곳이 있는지 탐색합니다. 있다면 해당 위치에 착수하여 방어합니다.
   3. 3. 미니맥스 최적의 수 탐색: 위의 두 경우에 해당하지 않을 경우, minimax 함수를 호출하여 SEARCH_DEPTH (현재 2)까지 탐색하여 가장 유리하다고 판단되는 위치에 착수합니다.
   4. 4. 첫 수: 만약 바둑판이 완전히 비어있다면 (총 361칸), 중앙(9, 9)에 착수하여 균형 잡힌 시작을 시도합니다.
   5. 5. 비상시 랜덤 착수: 미니맥스 계산 중 오류가 발생하거나 유효한 수를 찾지 못할 경우, 임의의 빈칸에 착수합니다.

오목 AI의 착수 결정 우선순위는 다음 표와 같습니다.

1. 3-3 규칙 검사 (checkThreeThree):
   1. 흑돌에만 적용되는 오목 규칙으로, 한 번의 착수로 동시에 두 개 이상의 '열린 3'을 만들 수 없는 규칙입니다. processMove 함수에서 착수 유효성 검사 시 사용됩니다.

바둑은 오목보다 훨씬 복잡한 게임이므로, 단순한 승리/패배 예측 대신 각 착수 위치가 가져올 수 있는 다양한 가치(집, 세력, 사활, 연결 등)를 종합적으로 평가하는 휴리스틱 기반 접근 방식을 사용합니다.

이 함수는 바둑판의 특정 위치(x, y)에 특정 색깔(color)의 돌을 놓았을 때의 잠재적 가치를 점수로 환산합니다. stoneCount를 통해 게임 진행 단계를 파악하여 평가 가중치를 조절합니다.

• 0. 자충수 방지:
  1. 자신이 둔 돌이 바로 잡히는 '자충수'는 기본적으로 금지합니다. 단, 상대방 돌을 잡는 경우는 예외로 허용합니다.

• 1. 전술적 평가 (매우 높은 가중치):
  1. a. 상대 돌 잡기 (Capture): 인접한 상대 돌 그룹의 활로가 0이 되는 경우, 해당 돌들을 잡을 수 있으므로 매우 높은 점수를 부여합니다. 잡는 돌의 개수에 비례하여 점수가 증가합니다.
  2. b. 내 돌 구하기 (Save): 단수(활로가 1개 남은 상태)에 몰린 내 돌 그룹의 활로를 늘려 살리는 위치에 높은 점수를 부여합니다.
  3. c. 상대 돌 단수 치기 (Atari): 상대 돌 그룹을 단수로 만드는 위치에 보너스 점수를 줍니다.

• 2. 전략적 평가 (게임 단계별 가중치 조절):
  1. phaseMultiplier 변수를 통해 stoneCount에 따라 게임 초반에는 전략적 가치를 높게, 후반에는 낮게 평가합니다.

게임 단계별 phaseMultiplier 가중치 및 적용 목표는 다음과 같습니다.

1. a. 빈 귀 차지 또는 걸치기/굳히기:
   1. 바둑의 기본 격언인 '귀→변→중앙'의 중요도를 반영하여, 비어있는 귀의 주요점(화점, 소목)을 차지하는 것에 높은 점수를 줍니다.
   2. 내 돌이 있는 귀를 굳히거나, 상대 돌이 있는 귀에 걸치는 수에도 보너스를 줍니다.
2. b. 변 확장: 바둑판의 3선(실리선)이나 4선(세력선)에 착수하여 집이나 세력을 확장하는 가치를 평가합니다.
3. c. 연결성 (evaluateConnectivity): 주변의 같은 색 돌과 연결될 가능성을 평가하여, 튼튼한 모양을 만들도록 유도합니다.

• 3. 모양(패턴) 평가:
  1. a. 좋은 모양 (evaluateGoodPatterns):
     1. 호구 (checkKnightMove): 한 칸 띄어서 대각선으로 연결되는 형태에 보너스.
     2. 쌍립 (checkDoubleWing): 두 돌이 나란히 서서 세력을 확장하는 형태에 보너스.
     3. 철주 (checkSolidConnection): 견고한 연결 형태에 보너스.
     4. 눈 만들기 (checkEyeMaking): 돌 그룹의 생존에 필수적인 '눈'을 만들 가능성에 보너스.
     5. 게임 초반에는 패턴 점수의 가중치를 낮춰 큰 곳 우선 원칙을 따르도록 합니다.
  2. b. 나쁜 모양 (evaluateBadPatterns):
     1. 빈삼각 (checkEmptyTriangle): 비효율적인 모양에 페널티.
     2. 우형 (checkBulkyFive): 머리를 들이미는 형태와 같이 비효율적인 모양에 페널티.
     3. 단조로운 연결 (checkHeavyConnection): 비효율적인 연결 형태에 페널티.

• 4. 영역적 가치 평가 (evaluateTerritorialValue):
  1. 착수 위치가 귀, 변, 중앙 중 어디에 해당하는지에 따라 다른 가치를 부여합니다.
  2. 게임 단계별 접촉전 가치 조정:
     1. 초반에는 상대 돌과의 접촉(붙는 수)을 피하도록 높은 페널티를 주어 넓은 곳을 차지하게 유도합니다.
     2. 중반에는 적절한 견제를, 후반에는 적극적인 침입에 보너스를 줍니다.
  3. 큰 곳 우선 평가 (evaluateBigPoints):
     1. 빈 귀는 가장 큰 가치를 가지며, 변의 확장 가치, 그리고 중반 이후 중앙 진출 가치를 종합적으로 평가합니다.

다음은 바둑 착점 가치 평가 함수 getBadukMoveScore의 개념적인 구조를 보여주는 코드 예시입니다.

function getBadukMoveScore(boardState, x, y, color, stoneCount) {
    let score = 0;
    const opponentColor = (color === 'black') ? 'white' : 'black';

    // 0. 자충수 확인
    if (isSuicide(boardState, x, y, color) && !canCapture(boardState, x, y, color)) {
        return -Infinity; // 자충수는 매우 낮은 점수
    }

    // 1. 전술적 평가 (높은 가중치)
    if (canCapture(boardState, x, y, color)) {
        score += getCaptureScore(boardState, x, y, color);
    }
    if (canSaveOwnStones(boardState, x, y, color)) {
        score += getSaveScore(boardState, x, y, color);
    }
    if (canPutOpponentInAtari(boardState, x, y, color)) {
        score += getAtariScore(boardState, x, y, color);
    }

    // 2. 전략적 평가 (게임 단계별 가중치)
    const phaseMultiplier = calculatePhaseMultiplier(stoneCount);
    score += evaluateStrategicValue(boardState, x, y, color) * phaseMultiplier;

    // 3. 모양(패턴) 평가
    score += evaluateGoodPatterns(boardState, x, y, color);
    score -= evaluateBadPatterns(boardState, x, y, color);

    // 4. 영역적 가치 평가
    score += evaluateTerritorialValue(boardState, x, y, color);

    return score;
}

바둑 AI는 복잡한 규칙과 상태를 처리하기 위해 다양한 헬퍼 함수들을 활용합니다. 다음 표는 주요 헬퍼 함수들의 역할과 활용처를 보여줍니다.

바둑 AI가 실제로 착수할 위치를 결정하는 함수입니다.

1. 모든 빈칸 평가:
   1. 바둑판의 모든 빈칸에 대해 getBadukMoveScore 함수를 호출하여 점수를 계산합니다.
   2. 가장 높은 점수를 얻은 위치를 최적의 수로 선택합니다.
   3. 동점인 수가 여러 개일 경우, 그 중 하나를 무작위로 선택합니다.

다음은 바둑 AI가 최적의 착수 위치를 결정하는 calculateBadukAIMove 함수의 개념적인 코드 예시입니다.

function calculateBadukAIMove(boardState) {
    let bestScore = -Infinity;
    let bestMoves = [];
    const aiColor = 'white'; // 또는 현재 AI의 색상

    for (let x = 0; x < 19; x++) {
        for (let y = 0; y < 19; y++) {
            if (boardState[y][x] === null) { // 빈 칸인 경우
                const stoneCount = countTotalStones(boardState);
                const currentScore = getBadukMoveScore(boardState, x, y, aiColor, stoneCount);

                if (currentScore > bestScore) {
                    bestScore = currentScore;
                    bestMoves = [{ x, y }];
                } else if (currentScore === bestScore) {
                    bestMoves.push({ x, y });
                }
            }
        }
    }

    // 최적의 수가 여러 개일 경우 무작위 선택
    if (bestMoves.length > 0) {
        const randomIndex = Math.floor(Math.random() * bestMoves.length);
        return bestMoves[randomIndex];
    }

    return null; // 유효한 수가 없을 경우
}

game-worker.js는 Node.js의 worker_threads를 사용하여 메인 스레드와 통신하며 게임 로직 및 AI 계산을 비동기적으로 수행합니다.

메인 스레드로부터 메시지를 받아 다음과 같은 작업을 수행합니다.

다음은 game-worker.js에서 메인 스레드로부터 메시지를 처리하는 개념적인 코드 예시입니다.

parentPort.on('message', (message) => {
    const { type, payload } = message;

    switch (type) {
        case 'PLACE_STONE':
            // payload.boardState, payload.x, payload.y, payload.color
            const result = processMove(payload.boardState, payload.x, payload.y, payload.color);
            parentPort.postMessage({ type: 'BOARD_UPDATED', payload: result });
            if (result.gomokuWin) { // 오목 승리 시 추가 메시지
                parentPort.postMessage({ type: 'GOMOKU_WIN', payload: { winner: result.winner } });
            }
            break;
        case 'CALCULATE_AI_MOVE':
            // payload.gameType, payload.boardState
            const aiMove = (payload.gameType === 'gomoku')
                ? calculateGomokuAIMove(payload.boardState)
                : calculateBadukAIMove(payload.boardState);
            parentPort.postMessage({ type: 'AI_MOVE_CALCULATED', payload: { move: aiMove } });
            break;
        case 'CALCULATE_SCORE':
            // payload.boardState
            const finalScore = calculateScore(payload.boardState); // 가상의 함수
            parentPort.postMessage({ type: 'SCORE_CALCULATED', payload: { score: finalScore } });
            break;
        default:
            console.warn(''알 수 없는 메시지 타입: ${type}'');
    }
});

• 'PLACE_STONE':
  1. 플레이어의 착수를 처리합니다. processMove 함수를 통해 돌 놓기, 상대방 돌 따내기, 자살수 검사, 패(Ko) 규칙 적용, 오목 승리 판정 등의 핵심 게임 규칙을 처리합니다.
  2. 처리 결과(변경된 보드 상태, 따낸 돌, 다음 턴 정보 등)를 메인 스레드로 반환합니다.
  3. 오목의 경우 승리 조건 충족 시 GOMOKU_WIN 메시지를 별도로 전송합니다.
• 'CALCULATE_AI_MOVE':
  1. AI 착수 계산 요청을 받으면, 게임 타입(오목 또는 바둑)에 따라 calculateGomokuAIMove 또는 calculateBadukAIMove 함수를 호출하여 AI의 최적 수를 계산합니다.
  2. 계산된 AI의 수를 AI_MOVE_CALCULATED 메시지를 통해 메인 스레드로 전달합니다. 실제 보드에 돌을 놓는 작업은 메인 스레드에서 PLACE_STONE 요청을 다시 보내는 방식으로 이루어집니다.
• 'CALCULATE_SCORE':
  1. 바둑의 경우, 종국 후 집 계산 요청을 받아 최종 점수를 계산하여 반환합니다. (calculateScore 함수는 제공된 코드에 명시적으로 나타나 있지 않으나, 메시지 처리 로직에 존재합니다.)

이 함수는 플레이어나 AI의 착수가 발생했을 때, 해당 착수가 게임 규칙에 부합하는지 검증하고 보드 상태를 업데이트하는 역할을 합니다.

1. 유효성 검사: 이미 돌이 있는 곳에 두거나, 패 규칙 위반, 자살수 등을 검사하여 유효하지 않은 착수를 거부합니다.

processMove 함수에서 수행하는 주요 유효성 검사 항목은 다음과 같습니다.

1. 따내기 처리: 바둑에서 상대 돌을 따내는 경우, 해당 돌들을 보드에서 제거하고 capturedStones 목록에 추가합니다.
2. 패 정보 업데이트: 바둑에서 패가 발생했을 경우, 다음 턴에 해당 위치에 둘 수 없도록 newKoInfo를 업데이트합니다.

이 game-worker.js 파일은 바둑 메타버스 내에서 오목과 바둑 게임의 핵심 로직과 AI 기능을 효율적으로 구현하고 있습니다. 오목 AI는 '미니맥스 + 알파-베타 가지치기'를 통해 승리/방어에 초점을 맞춘 강력한 수읽기 능력을 보여주는 반면, 바둑 AI는 '휴리스틱 기반의 복합적인 가치 평가 시스템'을 통해 바둑의 다양한 전략적, 전술적 요소를 고려한 지능적인 착수를 가능하게 합니다. 특히 바둑 AI는 사활, 모양, 영역, 게임 단계별 전략 등 실제 바둑의 중요한 개념들을 잘 반영하고 있어, 초급 및 중급 사용자에게 충분히 도전적이고 흥미로운 대국 경험을 제공할 수 있을 것입니다. 이러한 AI 로직은 게임의 깊이를 더하고 사용자들에게 몰입감 있는 플레이를 선사합니다.