1 전통적 AI 검색에서 평가 함수(Evaluation Function)의 개념과 역할
맹목적 완전 탐색의 늪에서 벗어나 컴퓨터에게 "어떤 상태가 더 좋은가?"를 가르치는 가치 척도
체스, 바둑, 15-퍼즐, 경로 탐색과 같은 문제에서 가능한 모든 상태의 수는 우주의 원자 수(약 1080개)를 가볍게 뛰어넘습니다. 따라서 모든 경우의 수를 끝까지 읽어보는 것은 물리적으로 불가능합니다. 이때 컴퓨터가 지능적으로 결정을 내리기 위해 도입된 것이 바로 평가 함수(Evaluation Function)입니다.
새로 생성된 후계 노드(Successor Nodes) 중에서 어떤 노드가 목표에 도달하는 최단 경로 상에 있을 확률이 높은지를 평가하여 우선순위 큐(OPEN List)의 순서를 재조정(Ranking)합니다.
알파-베타 가지치기나 분기한정법에서 평가 함수는 한계값(Bound)으로 작용하여, 가망 없는 거대한 하위 서브트리를 계산 없이 단번에 잘라내는 절단 기준으로 작동합니다.
더 깊은 수순을 탐색하지 않고 현재 판면 상태만을 즉시 평가(Static)함으로써, 초당 수백만 번의 형세를 신속하게 스캔할 수 있는 연산 효율성과 정확성 간의 실용적 균형을 달성합니다.
2 고전 AI의 양대 평가 함수 체계: 게임 트리 vs 경로 탐색
가중치 선형 결합(체스 형세 판단)과 경로 최소비용 추정 함수 f(n) = g(n) + h(n)
1. 게임 트리의 정적 평가 함수 (Static Evaluation)
체스 (Chess)나 바둑에서 특정 깊이의 리프 노드에 도달했을 때, 돌의 배치 상태를 다양한 특징(Feature)의 가중치 합(Weighted Sum)으로 평가합니다:
- • 기물 점수(Material): 퀸=9, 룩=5, 비숍/나이트=3, 폰=1 등 보유 전력 차이
- • 기동력(Mobility): 둘 수 있는 합법적인 수의 개수
- • 킹의 안전도(King Safety): 캐슬링 여부 및 방어벽 형성 상태
- • 중앙 지배력(Center Control): 체스판 중앙 4칸에 대한 장악력
2. 경로 탐색의 평가 함수 f(n) = g(n) + h(n)
연세대 김재희 교수(1988)와 닐스 닐슨(Nils J. Nilsson) 교수가 정리한 A* 알고리즘의 정석 평가 함수입니다:
- • f̂(n): 출발 노드로부터 노드 n을 거쳐 목표 노드까지 가는 최소 비용 경로의 총 예상 비용
- • ĝ(n): 출발 노드로부터 현재 노드 n까지 도달하는 데 소요된 실제 누적 비용
- • ĥ(n): 현재 노드 n부터 목표 노드까지의 남은 최적 경로 비용에 대한 휴리스틱 예측치
3 [인포그래픽] 평가 함수 작동 흐름과 상태 순위 결정 메커니즘
후계 노드 생성부터 특징 추출, 가중치 평가 점수 산출 및 최선 노드 확장 파이프라인
4 원본 수식 도해 분석 및 고전 자산 보존 (Preserved Equations)
연세대 김재희 교수 원문에 수록된 공식 이미지(GIF 4종)와 표준 HTML 수식 표기의 완벽한 대조
| 번호 | 원본 수식 이미지 (Preserved GIF) | 표준 HTML 수식 표기 | 수학적 정의 및 학술적 의미 |
|---|---|---|---|
| eqn1 | ![]() |
f̂(n) = ĝ(n) + ĥ(n) | 노드 n을 경유하는 전체 최적 경로 비용의 총 추정 평가 함수 |
| eqn2 | ![]() |
f̂(n) | 노드 n에서의 평가 함수 값 (출발지 → 노드 n → 목표지 최소비용 예측치) |
| eqn3 | ![]() |
ĝ(n) | 출발 노드로부터 현재 노드 n까지의 실제 최소비용 (누적 비용 실측치) |
| eqn4 | ![]() |
ĥ(n) | 현재 노드 n부터 목표 노드까지의 남은 최적 경로 비용에 대한 휴리스틱 예측치 |
5 [Deep Research] 최신 AI와 LLM에서 평가 함수(Evaluation Function)의 결정적 중요성
"생성(Generation)은 쉽지만 검증과 평가(Evaluation)는 지능의 본질이다" — PRM, RLHF, GRPO 및 테스트 시간 추론의 핵심 열쇠
2024~2026년 인공지능 연구에서 가장 큰 패러다임 전환은 "모델 크기를 무작정 키우는 사전 학습(Pre-training Scaling)"에서 "추론 시점의 계산량을 확장하는 테스트 시간 탐색(Test-Time Compute Search Scaling)"으로 이동한 것입니다. OpenAI o1/o3, DeepSeek-R1, Google Gemini Flash Thinking 등 세계를 뒤흔든 추론 모델들의 핵심 비밀은 더 많은 단어를 외운 것이 아니라, "자신이 생성한 사고(Thought)가 옳은지 그른지를 판별하는 초정밀 평가 함수"를 탑재했다는 점입니다.
전통적인 결과 보상 모델(ORM, Outcome Reward Model)은 최종 답변이 맞았는지만(0점 또는 1점) 평가하여 중간 단계의 치명적 논리 오류나 환각을 감지하지 못했습니다.
반면 최신 PRM(과정 보상 모델)은 수학 증명이나 코딩의 각 사고 단계(Step-by-Step Thought)마다 "이 수식 전개가 타당한가?"를 실시간 평가하는 현대판 휴리스틱 평가 함수입니다. Lightman et al. (2023) "Let's Verify Step by Step" 연구 이후, PRM 평가 점수를 기반으로 한 Best-of-N 및 트리 탐색은 올림피아드 수학 정답률을 2배 이상 폭발적으로 끌어올렸습니다.
DeepSeek-R1의 핵심 학습 알고리즘인 GRPO(Group Relative Policy Optimization) 및 PPO는 보상 모델(Reward Model, 고차원 평가 함수)의 기대 점수를 극대화하는 방향으로 모델의 가중치를 업데이트합니다.
정확한 평가 함수(컴파일러 실행 성공 여부, 수학 정답 검증기, 논리 일관성 스코어)가 주어지지 않으면 강화학습은 길을 잃습니다. 평가 함수는 인공지능이 인간의 개입 없이 스스로 강화 학습(Self-Play & Self-Improvement)을 수행하게 만드는 궁극의 기준선입니다.
LLM이 사고의 트리(ToT)나 몬테카를로 트리 탐색(MCTS)을 수행할 때, 평가 함수는 "어떤 사고의 줄기를 더 깊이 파고들고, 어떤 환각의 가지를 즉각 잘라낼 것인가(Pruning)?"를 결정하는 관제탑 역할을 합니다.
평가 함수가 부정확하면 모델은 엉뚱한 거짓 논리를 끝까지 밀고 나가는 오류 증폭(Drift)에 빠지지만, 정교한 평가 함수는 모델이 막다른 길에 부딪혔을 때 즉시 상위 노드로 백트래킹하여 최적의 대안을 찾도록 유도합니다.
현대의 에이전트 시스템에서는 정형화된 수학 공식 대신, 고성능 모델(GPT-4o, Claude 3.5 Sonnet 등) 자체가 다른 모델의 답변, 소스 코드, 보고서를 정량 루브릭에 따라 채점하는 LLM-as-a-Judge가 범용 평가 함수로 활약합니다.
자연어 프롬프트로 정의된 다차원 평가 척도(정확성, 안전성, 유용성, 간결성)를 통해 소프트웨어 개발, 법률 검토, 의료 상담의 품질을 실시간 검증합니다.
🎯 평가 함수(Evaluation Function)가 AI의 미래에 던지는 핵심 진실
"지능의 한계는 생성할 수 있는 아이디어의 수가 아니라, 좋은 아이디어와 나쁜 아이디어를 가려낼 수 있는 평가 능력에 의해 결정된다." 1950년대 체스 프로그램에서 시작된 평가 함수는 70년의 세월을 거쳐 오늘날 AGI로 향하는 추론 AI의 가장 본질적인 두뇌(Verifier & Reward Model)로 완성되었습니다.
6 [인포그래픽] LLM 추론에서의 평가 함수: ORM(결과 보상) vs PRM(과정 보상)
다단계 수학 및 논리 추론에서 중간 단계 평가 함수(PRM)가 환각을 조기에 잘라내는 시각적 메커니즘
최종 결론만 평가 → 중간 오류 방치
치명적 결함: 2단계에서 이미 논리가 틀렸음에도 3단계까지 토큰을 낭비하고, 어디가 틀렸는지 짚어내지 못함.
사고 단계별 실시간 평가 → 조기 절단(Pruning)
혁신적 장점: 단계별 평가 함수가 거짓 생각을 그 자리에서 잘라내고(Pruning), 올바른 논리 줄기에만 연산을 집중시킴.
7 고전 AI vs 현대 LLM 평가 함수 종합 비교표
시대별 평가 함수의 진화 과정, 입력 형태, 수학적 메커니즘 및 주요 역할 비교
| 구분 | 평가 대상 (Input) | 평가 함수 수식 및 형태 | 주요 알고리즘 & 엔진 | 핵심 기여 및 진화적 의미 |
|---|---|---|---|---|
| 고전 체스 정적 평가 | 체스판 기물 배치 상태 | Σ wi × Featurei (선형 가중합) | Mini-Max, Alpha-Beta, Deep Blue | 끝까지 수를 읽지 않고 현재 판세의 승률을 즉각 추정 |
| 고전 경로 탐색 (A*) | 그래프 노드 및 좌표 | f(n) = g(n) + h(n) | A*, Best-First, IDA* | 허용성(h ≤ h*) 충족 시 전역 최단 경로 100% 보장 |
| 강화학습 보상 모델 (RM) | 인간 선호도 대화 쌍 | rθ(prompt, response) ∈ ℝ | RLHF, PPO, DPO, GRPO | 인간의 가치관과 안전성 기준에 맞게 LLM 행동 정렬 |
| 과정 보상 모델 (PRM) | 각 단계별 자연어 사고 (Step) | PRM(s1...t) ∈ [0, 1] | OpenAI o1/o3, DeepSeek-R1, ToT | 사고 중간의 논리 오류를 실시간 검증하고 환각 조기 차단 |
| LLM-as-a-Judge | 에이전트 산출물 전체 | 자연어 프롬프트 루브릭 채점 | SWE-bench, 자동 벤치마킹 | 인간 전문가를 대신해 코드/문서 품질을 다차원 정량 평가 |
8 원문 학술 레퍼런스 & 멀티미디어 강의 (Preserved Classics)
연세대 김재희 교수, 스탠포드 닐스 닐슨 교수 및 정보처리학회/멀티미디어학회 원문 논문 PDF 3종 완벽 보존
Harvard CS50 AI - Game Evaluation & Mini-Max
체스 및 틱택토 게임 트리에서 정적 평가 함수(Static Evaluation)가 상태의 승률을 판정하는 원리 해설
MIT AI Lecture - Heuristic Evaluation in Search & Games
MIT 패트릭 윈스턴 교수의 미니맥스 형세 판단 가중치 평가 함수 및 알파-베타 가지치기 특강
📚 원문 학습 자료 및 고전 학술 링크 (Preserved Classical Links)
원문 아카이브에 수록된 국내외 학술 논문 PDF, 석학 프로필 및 체스 엔진 휴리스틱 소스를 중첩 태그 없이 정갈하게 분류하였습니다.
📑 국내 학술 논문 원문 PDF 보존 (Domestic Academic Papers)
얼굴 특성 반영 휴리스틱 평가함수 기반 특징 검출
Facial Features Detection Using Heuristic Cost Function (장경식 저). 얼굴 특징점 탐색 비용 함수 연구.
점진적 개념학습의 클러스터 응집도 개선
The Study on Improvement of Cohesion of Clustering in Incremental Concept Learning (박영택, 백혜정 저).
적응적 특징자 평가함수를 사용한 실시간 얼굴인식
Adaptive Face Region Detection Based on Face Feature Evaluation Function (김지홍, 김정훈, 이응주 저).
🏛️ 석학 저작 및 체스 휴리스틱 소스 (Pioneering Theories & Engine Sources)
평가 함수의 사용 (Using Evaluation Function)
닐스 닐슨 교수의 AI 탐색 명저. 휴리스틱 정보와 평가 함수의 수학적 정의 해설.
GNU Chess Heuristics Text ↗
세계적인 오픈소스 체스 엔진 GNU Chess에서 구현된 실제 정적 평가 함수 알고리즘 텍스트 문서.
⚙️ 핵심 연계 탐색 알고리즘 시리즈 (Search Series)
AI 탐색 알고리즘 시리즈 함께 보기
평가 함수 이론부터 A* 알고리즘, 미니맥스 게임 트리, 최신 LLM 과정 보상 모델(PRM)까지 완전 정복하세요.



