Minimax & Alpha-Beta Search Engine

Java 21로 작성한 2인 제로섬 턴제 보드 게임용 고성능 범용 탐색 엔진입니다. 게임 상태와 평가 함수를 주입하면 Negamax 기반의 반복 심화 탐색(Iterative Deepening)을 수행합니다.

core 모듈은 게임에 독립적인 탐색 엔진과 최적화 알고리즘을 제공하고, tictactoe 모듈은 이를 사용하는 틱택토 상태·평가 함수·Swing 애플리케이션의 예시입니다.

plus 모듈은 다자간 게임 지원을 우한 알고리즘을 제공하며, grid-survivor 모듈은 다자간 알고리즘 테스트를 위한 턴제 게임입니다.

주요 기능

• Negamax 기반 Minimax 탐색: 2인 제로섬 관점 단순화 및 일관된 부호 전환
• Alpha-Beta Pruning: 불필요한 가지치기를 통한 탐색 공간 축소
• Iterative Deepening: 점진적 깊이 확장과 시간 제한 처리
• 최소 탐색 깊이 보장 옵션: 시간 제한이 있어도 설정 깊이까지는 완료 보장
• Lock-Free 스레드 안전 Transposition Table: AtomicReferenceArray 기반으로 가상 스레드 환경에서도 안전한 상태 재사용
• 캐시 최적화 Zobrist Hash: 1차원 평탄화(Flat array)로 CPU 캐시 지역성 극대화
• 정밀 PVS (Principal Variation Search): 부동소수점 엡실론 Null-Window 및 Fail-High 재탐색 보장
• 고성능 Move Ordering: PV, TT 최선 수, Killer Move, History Heuristic 결합 및 GC 프리 인라인 정렬
• 최적 수순(PV Line) 추출: 최선의 수(Best Move)뿐만 아니라 완성된 수순(List<M>) 반환
• LMR (Late Move Reductions): 비전술적 후순위 수의 깊이 축약 탐색 및 안전한 보호 조건
• 게임별 Quiescence Search: 전술적 불안정 국면(기물 교환 등)의 지평선 효과 방지
• Virtual Thread 기반 루트 병렬 탐색: 기준 alpha 확보 후 가상 스레드로 자식 노드 병렬 탐색
• 동률 최선 수 무작위 선택: 완전 동일한 점수의 수들 중 시드 기반 재현 가능한 무작위 분기

모듈과 핵심 타입

모듈	설명
core	게임 상태, 평가 함수, 수 정렬, Minimax 탐색 엔진
plus	다자간(1:n) 게임 탐색 엔진
tictactoe	틱택토 상태·평가 함수·전술 정책 및 Swing 애플리케이션
grid-survivor	다자간 알고리즘 테스트를 위한 턴제 게임

core 모듈

타입	설명
GameState<S, M>	종료 여부, 가능한 수, 상태 전이, 현재 플레이어, Zobrist hash 제공
Evaluator	상태를 기준 플레이어 관점의 점수로 평가 (단독 평가용 편의 메서드 제공)
MoveSorter<S, M>	Alpha-Beta 효율을 위한 수 정렬 인터페이스
DefaultMoveSorter<S, M>	PV, TT, Killer, History 가중치를 반영하는 고성능 기본 정렬기
QuiescencePolicy<S, M>	깊이 제한 이후 추가로 탐색할 전술 수 제공
MinimaxEngine<S, M>	전체 탐색과 최적화 기능 통합
SearchResult	최선의 수, 평가 점수, 깊이, 노드 수, 완료 여부, 최적 수순(PV Line) 반환
ZobristHash	상태 식별에 사용하는 결정적 64-bit hash 생성

엔진 작동 방식

findBestMove(initialState, minDepth, maxDepth, timeLimit)는 호출마다 전달된 탐색 설정으로 다음 흐름을 수행합니다.

상태 검증
  ↓
시간 제한 계산
  ↓
반복 심화: depth = 1 ... maxDepth
  ├─ 가능한 수 정렬 (PV, TT, Killer, History)
  ├─ 각 루트 수를 Negamax로 탐색 (순차 또는 Virtual Thread 병렬)
  ├─ Alpha-Beta, PVS, LMR, Lock-Free TT 적용
  ├─ 깊이 0에서 필요하면 Quiescence Search (지평선 효과 방지)
  ├─ 완료된 깊이의 결과 및 최적 수순(PV Line) 갱신
  └─ 다음 깊이의 Move Ordering을 위해 PV 정보 전달
  ↓
마지막으로 완료된 깊이의 SearchResult 반환

터미널 상태이거나 가능한 수가 없으면 빈 SearchResult를 반환합니다. 시간 제한으로 현재 깊이를 끝내지 못하면 직전 완료 깊이의 결과를 우선 반환합니다.

Negamax

2인 제로섬 게임에서는 한 플레이어의 이득이 다른 플레이어의 손실과 반대입니다. 엔진은 Max와 Min 노드를 별도로 구현하는 대신 자식 점수에 음수를 취합니다.

현재 수의 점수 = -상대 차례에서의 최선 점수

Evaluator는 기준 플레이어 관점의 점수를 반환하고, 엔진은 현재 상태의 플레이어 관점(isMaximizingPlayer() ? 1.0 : -1.0)으로 변환합니다.

Alpha-Beta Pruning

탐색 중 하한 alpha와 상한 beta를 유지합니다. alpha가 beta 이상이 되면 나머지 수는 결과를 바꿀 수 없으므로 해당 가지를 중단(Cutoff)합니다. 좋은 수를 먼저 탐색할수록 Cutoff가 빠르게 발생하므로 Move Ordering과 PVS가 결정적인 성능 차이를 만듭니다.

Iterative Deepening & PV Line

깊이 1부터 호출 시 전달된 maxDepth까지 반복합니다. 각 깊이가 완료될 때마다 최선 수뿐만 아니라 완성된 최적 수순(Principal Variation Line: List<M>)을 함께 추출하여 SearchResult.principalVariation()으로 제공합니다. 이 PV 정보는 다음 깊이 반복 탐색 시 자식 노드의 Move Ordering 우선순위로도 전달되어 탐색 속도를 가속합니다.

depth 1 완료 → depth 2 완료 → depth 3 탐색 중 시간 초과
                              ↓
                    depth 2 결과 및 PV 반환

호출별 탐색 설정

minDepth, maxDepth, timeLimit은 Builder에 고정하지 않고 탐색 호출마다 유연하게 지정할 수 있습니다.

SearchResult<Integer> result = engine.findBestMove(
        initialState,
        3,                         // minDepth (시간 제한 유예)
        10,                        // maxDepth
        Duration.ofMillis(100));   // timeLimit

• minDepth: 시간 제한이 도달해도 무조건 완료를 보장할 최소 깊이 (0 이상)
• maxDepth: 탐색할 최대 반복 심화 깊이 (1 이상)
• timeLimit: 전체 탐색 시간 제한 (null이면 시간 무제한)

적용된 최적화 알고리즘

Transposition Table과 Zobrist Hash

서로 다른 수순으로 동일한 판면에 도달할 수 있으므로, 엔진은 getZobristHash()를 key로 사용하여 이미 탐색한 점수와 탐색 깊이, 최선 수를 재사용합니다.

• Lock-Free 스레드 안전성: AtomicReferenceArray 슬롯을 사용하여 Virtual Thread 기반 병렬 탐색 시에도 데이터 레이스 없이 안전하게 공유됩니다.
• 깊이 보존 교체 전략: 슬롯 충돌 시 더 깊게 탐색한 엔트리를 우선적으로 보존합니다.
• 1차원 평탄화 Zobrist 테이블: long[] 플랫 배열 구조로 설계되어 2차원 객체 배열의 다중 포인터 역참조 오버헤드를 없애고 CPU 캐시 히트율을 극대화했습니다.

Move Ordering & DefaultMoveSorter

기본 수 정렬 우선순위는 다음과 같습니다.

Principal Variation (PV) → TT Best Move → Killer Moves → History Heuristic → 기존 순서

DefaultMoveSorter는 정렬 비교 시 람다 객체 생성 및 중복 우선순위 계산을 피하기 위해 **1회 점수 캐싱 후 인라인 삽입 정렬(Stable Insertion Sort)**을 수행합니다. 분기 계수가 작은 게임 탐색 트리에서 객체 할당(GC) 오버헤드를 완전히 제거하고 최고의 정렬 속도를 냅니다.

Principal Variation Search (PVS)

첫 번째 최적 후보 수는 전체 창([-beta, -alpha])으로 탐색하고, 이후의 수는 좁은 Null Window([-alpha - EPSILON, -alpha])로 빠르게 검증합니다.

• 평가 함수가 정규화된 실수(예: 0.1, 0.5)를 반환하는 경우에도 왜곡되지 않도록 정밀 엡실론(1e-4) 창을 사용합니다.
• Null Window 탐색 결과가 현재 alpha를 초과(score > alpha, Fail-High 포함)하면 전체 창으로 재탐색하여 정확한 평가치를 획득합니다.

Late Move Reductions (LMR)

깊이 4 이상에서 순서가 늦은 수(moveIndex >= 4)는 먼저 축약된 깊이(1~2 깊이 감소)로 탐색하여 노드 수를 대폭 절감합니다.

• 안전성 보호 조건: TT 최선 수, PV 수, Killer Move, 또는 state.isTacticalMove()로 지정된 전술적 수는 축약 대상에서 제외하여 블런더를 방지합니다.
• 축약 탐색 결과가 alpha를 넘어서면 원래 깊이로 전체 재탐색을 수행합니다.

Quiescence Search (QS)

탐색 깊이 한계에 도달했을 때 판면이 불안정(체크, 기물 교환, 즉시 승리 위협 등)한 경우 발생하는 지평선 효과(Horizon Effect)를 방지하기 위해 전술적 수만 추가 탐색합니다.

QuiescencePolicy<MyGameState, Integer> policy = state -> state.getPossibleMoves()
        .stream()
        .filter(state::isTacticalMove)
        .toList();

MinimaxEngine<MyGameState, Integer> engine = MinimaxEngine
        .<MyGameState, Integer>builder()
        .setEvaluator(new MyEvaluator())
        .setQuiescencePolicy(policy)
        .setMaxQuiescenceDepth(8)
        .build();

Virtual Thread 루트 병렬 탐색

enableParallelSearch(true) 설정 시 깊이 2 이상에서 첫 번째 루트 수를 먼저 탐색하여 기준 alpha를 확보한 뒤, 나머지 루트 수를 Java 21 Virtual Thread 기반 비동기 태스크로 병렬 탐색합니다.

각 스레드는 로컬 통계(SearchStats)를 독립적으로 집계한 뒤 병렬 작업 종료 시 안전하게 합산합니다.

Builder 옵션과 탐색 API

메서드	기본값	설명
setEvaluator(evaluator)	필수	상태 평가 함수
setMoveSorter(sorter)	null	가능한 수의 탐색 순서
enableTranspositionTable(enable)	false	TT 사용 여부
setMaxTranspositionTableSize(size)	100,000	TT 최대 엔트리 수
enablePrincipalVariationSearch(enable)	true	PVS 사용 여부
enableLateMoveReductions(enable)	true	LMR 사용 여부
enableParallelSearch(enable)	false	루트 병렬화 여부
setQuiescencePolicy(policy)	null	Quiescence 전술 수 정책
setMaxQuiescenceDepth(depth)	4	Quiescence 최대 추가 깊이
enableRandomTieBreaking(enable)	false	동률 최선 수 무작위 선택
setRandomSeed(seed)	무작위	동률 선택 재현용 seed

사용 방법

상태 및 평가 함수 구현

public final class MyEvaluator implements Evaluator<MyGameState> {
    @Override
    public double evaluate(MyGameState state, int remainingDepth) {
        if (state.isWin()) return Evaluator.WIN_SCORE + remainingDepth;
        if (state.isLoss()) return Evaluator.LOSS_SCORE - remainingDepth;
        return heuristicScore(state);
    }
}

엔진 실행 및 결과 조회

SearchResult<Integer> result = engine.findBestMove(
        initialState, 2, 9, Duration.ofMillis(500));

if (result.hasBestMove()) {
    System.out.println("최선의 수: " + result.bestMove());
    System.out.println("평가 점수: " + result.score());
    System.out.println("탐색 깊이: " + result.depthSearched());
    System.out.println("평가 노드 수: " + result.nodesEvaluated());
    System.out.println("최적 수순(PV): " + result.principalVariation());
}

SearchResult 구조

필드	의미
bestMove()	선택된 최선의 수 (없으면 null)
score()	선택된 수의 가치 평가 점수
depthSearched()	완료했거나 부분적으로 탐색한 깊이
nodesEvaluated()	탐색 중 방문/평가한 노드 수
isExactScore()	점수가 완전한 탐색 결과인지 여부
isComplete()	해당 깊이의 모든 루트 수가 끝났는지 여부
principalVariation()	루트로부터 탐색된 최적 수순 목록 (PV Line)

틱택토 애플리케이션 실행

tictactoe는 사용자가 X, Minimax AI가 O인 Swing GUI 예제 애플리케이션입니다.

./gradlew :tictactoe:run

테스트 실행

./gradlew test