본 콘텐츠의 이미지 및 내용은 AI로 생성되었습니다.
본 콘텐츠의 이미지 및 내용을 무단으로 복제, 배포, 수정하여 사용할 경우 저작권법에 의해 법적 제재를 받을 수 있습니다.
이미지 로딩 중...
AI Generated
2025. 12. 26. · 0 Views
Tree of Thoughts 에이전트 완벽 가이드
AI 에이전트가 복잡한 문제를 해결할 때 여러 사고 경로를 탐색하고 평가하는 Tree of Thoughts 기법을 배웁니다. BFS/DFS 탐색 전략부터 가지치기, 백트래킹까지 실전 예제와 함께 쉽게 설명합니다.
목차
1. 사고 트리 탐색
어느 날 김개발 씨는 AI 에이전트 프로젝트를 맡게 되었습니다. 선배 개발자 박시니어 씨가 물었습니다.
"AI가 복잡한 문제를 풀 때 어떻게 생각하게 만들 건가요?" 김개발 씨는 잠시 고민에 빠졌습니다.
Tree of Thoughts는 AI 에이전트가 하나의 답을 바로 찾는 대신, 여러 가능성을 트리 구조로 탐색하며 최선의 해결책을 찾는 방법입니다. 마치 체스 선수가 여러 수를 미리 생각해보는 것처럼, AI도 다양한 사고 경로를 시뮬레이션합니다.
이를 통해 더 정확하고 창의적인 문제 해결이 가능해집니다.
다음 코드를 살펴봅시다.
class ThoughtNode:
def __init__(self, content, parent=None):
# 현재 생각의 내용
self.content = content
self.parent = parent
self.children = []
# 이 생각의 품질 점수
self.score = 0.0
def add_child(self, child_content):
# 새로운 사고 경로를 추가합니다
child = ThoughtNode(child_content, parent=self)
self.children.append(child)
return child
김개발 씨는 입사 6개월 차 개발자입니다. 오늘 팀 미팅에서 CTO님이 흥미로운 과제를 던졌습니다.
"우리 AI 챗봇이 복잡한 수학 문제를 풀 때 자주 틀리는데, 어떻게 개선할 수 있을까요?" 김개발 씨는 기존 코드를 살펴봤습니다. AI가 문제를 받으면 바로 하나의 답을 생성하는 방식이었습니다.
뭔가 부족해 보였습니다. 그때 박시니어 씨가 다가왔습니다.
"김 개발자님, Tree of Thoughts라는 기법을 들어보셨나요? 사람이 어려운 문제를 풀 때처럼, AI도 여러 가지 방법을 시도해보게 만드는 거예요." Tree of Thoughts란 정확히 무엇일까요?
쉽게 비유하자면, 미로를 탈출하는 상황과 같습니다. 한 길만 계속 가다가 막다른 골목에 도달하면 다시 돌아와야 합니다.
하지만 여러 길을 동시에 탐색한다면 어떨까요? 각 길의 가능성을 평가하고, 가장 유망한 길을 선택할 수 있습니다.
Tree of Thoughts도 마찬가지로 AI가 여러 사고 경로를 동시에 고려하게 만듭니다. 기존의 단순한 Chain of Thought 방식에서는 어떤 문제가 있었을까요?
AI는 한 가지 생각의 흐름만 따라갔습니다. "A라고 생각하니, B가 되고, 따라서 C다"처럼 직선적으로 추론했습니다.
중간에 실수가 있어도 되돌아갈 수 없었습니다. 더 큰 문제는 창의적인 대안을 고려하지 못한다는 점이었습니다.
복잡한 문제일수록 이런 한계가 명확해졌습니다. 바로 이런 문제를 해결하기 위해 Tree of Thoughts가 등장했습니다.
이 방식을 사용하면 AI가 여러 가능성을 동시에 탐색할 수 있습니다. 각 생각을 노드로 만들고, 그 노드에서 파생되는 새로운 생각들을 자식 노드로 추가합니다.
마치 나뭇가지가 뻗어나가듯이 사고가 확장됩니다. 무엇보다 각 경로를 평가하고 비교할 수 있다는 큰 이점이 있습니다.
위의 코드를 한 줄씩 살펴보겠습니다. 먼저 ThoughtNode 클래스는 하나의 생각을 표현합니다.
content는 실제 생각의 내용이고, parent는 어떤 생각에서 파생되었는지를 나타냅니다. children 리스트에는 이 생각에서 이어지는 다음 생각들이 담깁니다.
score는 이 생각이 얼마나 좋은지 평가한 점수입니다. add_child 메서드를 보면 새로운 사고 경로를 추가하는 과정이 명확합니다.
자식 노드를 생성하고, 현재 노드를 부모로 설정한 뒤, children 리스트에 추가합니다. 이렇게 트리 구조가 자연스럽게 형성됩니다.
실제 현업에서는 어떻게 활용할까요? 예를 들어 금융 AI 상담 서비스를 개발한다고 가정해봅시다.
고객이 "주식 투자 전략을 추천해주세요"라고 물으면, AI는 여러 전략을 트리로 탐색합니다. 첫 번째 가지는 "성장주 투자", 두 번째는 "배당주 투자", 세 번째는 "가치주 투자"처럼 다양한 방향을 고려합니다.
각 전략에 대해 다시 세부 옵션을 탐색하고, 최종적으로 가장 적합한 조합을 추천합니다. 하지만 주의할 점도 있습니다.
초보 개발자들이 흔히 하는 실수 중 하나는 트리를 무한정 확장하는 것입니다. 모든 가능성을 다 탐색하려다 보면 계산 비용이 기하급수적으로 증가합니다.
따라서 적절한 깊이 제한과 가지치기 전략을 반드시 설정해야 합니다. 또 다른 실수는 노드 평가 기준을 명확히 하지 않는 것입니다.
score를 어떻게 계산할지 정의하지 않으면, 좋은 경로와 나쁜 경로를 구분할 수 없습니다. LLM에게 각 생각을 평가하게 하거나, 휴리스틱 함수를 설계해야 합니다.
다시 김개발 씨의 이야기로 돌아가 봅시다. 박시니어 씨의 설명을 듣고 김개발 씨는 직접 코드를 작성해봤습니다.
"아, 이렇게 하면 AI가 여러 방법을 시도해볼 수 있겠네요!" Tree of Thoughts를 제대로 이해하면 단순히 답을 맞히는 AI가 아니라, 사고하는 AI를 만들 수 있습니다. 여러분도 오늘 배운 내용을 실제 프로젝트에 적용해 보세요.
실전 팁
💡 - 트리의 최대 깊이를 설정하여 무한 확장을 방지하세요
- 각 노드의 평가 기준(score)을 명확히 정의하세요
- 초기 단계에서는 적은 수의 가지만 생성하고, 점진적으로 확장하세요
2. BFS vs DFS 전략
김개발 씨가 Tree of Thoughts 구조를 만들고 나니 새로운 고민이 생겼습니다. "이 트리를 어떤 순서로 탐색해야 할까요?" 박시니어 씨가 웃으며 말했습니다.
"좋은 질문이에요. BFS와 DFS, 두 가지 전략이 있습니다."
BFS(Breadth-First Search)는 넓이 우선 탐색으로, 같은 깊이의 노드들을 먼저 모두 탐색한 뒤 다음 깊이로 내려갑니다. 반면 DFS(Depth-First Search)는 깊이 우선 탐색으로, 한 경로를 끝까지 탐색한 뒤 다른 경로로 넘어갑니다.
문제의 특성에 따라 적절한 전략을 선택하면 효율적인 탐색이 가능합니다.
다음 코드를 살펴봅시다.
from collections import deque
class ThoughtTreeExplorer:
def bfs_search(self, root, max_thoughts=10):
# BFS: 넓게 탐색하며 다양한 가능성을 고려
queue = deque([root])
explored = []
while queue and len(explored) < max_thoughts:
# 가장 먼저 들어온 노드를 탐색
node = queue.popleft()
explored.append(node)
# 같은 레벨의 모든 자식을 큐에 추가
queue.extend(node.children)
return explored
def dfs_search(self, root, max_thoughts=10):
# DFS: 깊게 파고들며 하나의 경로를 완성
stack = [root]
explored = []
while stack and len(explored) < max_thoughts:
# 가장 최근에 추가된 노드를 탐색
node = stack.pop()
explored.append(node)
# 자식들을 역순으로 스택에 추가
stack.extend(reversed(node.children))
return explored
김개발 씨는 트리 구조를 만들었지만, 막상 어떻게 탐색할지 결정하지 못했습니다. 모든 노드를 다 탐색하기에는 시간과 비용이 너무 많이 듭니다.
효율적인 방법이 필요했습니다. 박시니어 씨가 화이트보드에 그림을 그리며 설명했습니다.
"자, 이 트리를 보세요. 탐색 방법은 크게 두 가지입니다." BFS와 DFS는 각각 언제 사용해야 할까요?
쉽게 비유하자면, BFS는 물이 퍼지는 것과 같습니다. 돌을 연못에 던지면 물결이 동심원으로 퍼져나갑니다.
가까운 곳부터 차례대로 넓게 탐색합니다. 반면 DFS는 동굴을 탐험하는 것과 같습니다.
한 갈래 길을 끝까지 가본 뒤, 되돌아와서 다른 길로 들어갑니다. 왜 두 가지 방법이 모두 필요할까요?
문제의 성격에 따라 최적의 전략이 다르기 때문입니다. 만약 답이 트리의 얕은 곳에 있을 가능성이 크다면 BFS가 유리합니다.
모든 얕은 노드를 빠르게 확인할 수 있으니까요. 반대로 답이 깊은 곳에 숨어 있다면 DFS가 더 효율적입니다.
빠르게 깊이 들어가서 완전한 해결책을 찾을 수 있습니다. BFS의 장점은 무엇일까요?
첫째, 다양성을 보장합니다. 여러 가지 초기 아이디어를 동시에 평가할 수 있습니다.
둘째, 최단 경로를 찾기 쉽습니다. 가까운 노드부터 탐색하므로, 처음 찾은 해결책이 가장 짧은 경로일 가능성이 큽니다.
셋째, AI 에이전트가 창의적인 대안을 고려하기 좋습니다. 그렇다면 DFS는 언제 빛을 발할까요?
DFS는 메모리 효율이 뛰어납니다. BFS처럼 같은 레벨의 모든 노드를 메모리에 저장할 필요가 없습니다.
스택에는 현재 경로의 노드들만 있으면 되니까요. 또한 완전한 솔루션이 필요한 경우에 유용합니다.
예를 들어 수학 증명이나 게임 플레이처럼 처음부터 끝까지 완전한 경로가 필요한 상황입니다. 위의 코드를 자세히 살펴보겠습니다.
bfs_search 메서드는 deque를 사용합니다. 큐는 FIFO(First In First Out) 구조라서 먼저 들어간 노드가 먼저 나옵니다.
popleft()로 가장 오래된 노드를 꺼내고, extend()로 그 자식들을 뒤에 추가합니다. 이렇게 하면 자연스럽게 레벨 순서로 탐색됩니다.
dfs_search 메서드는 리스트를 스택처럼 사용합니다. pop()은 가장 최근에 추가된 노드를 꺼냅니다.
LIFO(Last In First Out) 구조죠. reversed()를 사용하는 이유는 자식들을 원래 순서대로 탐색하기 위해서입니다.
왼쪽 자식을 먼저 보려면 역순으로 스택에 넣어야 합니다. 실제 AI 에이전트에서는 어떻게 선택할까요?
예를 들어 코드 생성 AI를 만든다고 해봅시다. 사용자가 "로그인 기능을 구현해줘"라고 요청하면, AI는 여러 접근 방식을 고려해야 합니다.
JWT 방식, 세션 방식, OAuth 등 다양한 옵션이 있습니다. 이 경우 BFS가 적합합니다.
여러 옵션을 넓게 평가하고, 가장 좋은 것을 선택할 수 있으니까요. 반면 게임 플레이 AI는 다릅니다.
체스 AI가 다음 수를 결정할 때, 한 수를 두고 그 결과를 끝까지 시뮬레이션해야 합니다. 이때는 DFS가 유리합니다.
한 경로를 끝까지 탐색해서 최종 결과를 평가하는 것이 중요하니까요. 주의할 점도 있습니다.
BFS는 메모리를 많이 사용합니다. 트리가 넓게 퍼질수록 같은 레벨의 노드 수가 기하급수적으로 증가하기 때문입니다.
max_thoughts 파라미터로 제한을 두는 것이 필수입니다. DFS는 무한 루프에 빠질 위험이 있습니다.
만약 트리에 순환 참조가 있거나 깊이 제한이 없다면, 한 경로에서 영원히 헤맬 수 있습니다. 반드시 최대 깊이를 설정해야 합니다.
김개발 씨는 두 방법을 모두 구현해봤습니다. "BFS는 아이디어 브레인스토밍할 때 좋고, DFS는 하나의 아이디어를 완성할 때 좋네요!" 박시니어 씨가 고개를 끄덕였습니다.
"맞아요. 실무에서는 두 방법을 조합하기도 합니다.
처음에는 BFS로 좋은 방향을 찾고, 그 다음엔 DFS로 깊게 파고드는 거죠." BFS와 DFS를 상황에 맞게 선택하면 AI 에이전트의 성능을 크게 향상시킬 수 있습니다. 문제의 특성을 먼저 분석하고, 적절한 전략을 적용해 보세요.
실전 팁
💡 - 다양한 옵션을 평가해야 한다면 BFS를, 완전한 경로가 필요하다면 DFS를 선택하세요
- 두 방법을 조합하는 하이브리드 전략도 고려해보세요
- max_thoughts로 탐색 범위를 제한하여 비용을 관리하세요
3. Pruning과 Backtracking
김개발 씨의 Tree of Thoughts 에이전트가 작동하기 시작했지만, 문제가 생겼습니다. 너무 많은 경로를 탐색하느라 시간이 오래 걸렸습니다.
박시니어 씨가 조언했습니다. "쓸모없는 가지는 잘라내야 해요.
Pruning이죠. 그리고 막다른 길에서는 돌아올 줄도 알아야 합니다.
바로 Backtracking이에요."
Pruning(가지치기)은 평가 점수가 낮거나 가망이 없는 사고 경로를 조기에 제거하는 기법입니다. Backtracking(역추적)은 막다른 길에 도달했을 때 이전 분기점으로 돌아가서 다른 경로를 시도하는 방법입니다.
두 기법을 함께 사용하면 탐색 효율이 극적으로 향상됩니다.
다음 코드를 살펴봅시다.
class SmartTreeExplorer:
def __init__(self, score_threshold=0.3):
# 이 점수 이하의 노드는 제거합니다
self.score_threshold = score_threshold
def evaluate_node(self, node, llm):
# LLM에게 이 생각의 품질을 평가하게 합니다
prompt = f"다음 생각이 문제 해결에 도움이 될까요? {node.content}"
response = llm.evaluate(prompt)
node.score = float(response)
return node.score
def prune_and_search(self, root, llm, max_depth=5):
# Pruning과 Backtracking을 활용한 탐색
def backtrack(node, depth):
if depth > max_depth:
return None # 깊이 제한 도달, 되돌아갑니다
# 현재 노드 평가
score = self.evaluate_node(node, llm)
# Pruning: 점수가 낮으면 이 가지를 버립니다
if score < self.score_threshold:
return None
# 목표에 도달했는지 확인
if self.is_goal(node):
return node
# 자식 노드들을 탐색
for child in node.children:
result = backtrack(child, depth + 1)
# 해결책을 찾으면 즉시 반환
if result:
return result
# 모든 자식이 실패하면 None 반환 (Backtracking)
return None
return backtrack(root, 0)
def is_goal(self, node):
# 목표 상태인지 확인하는 로직
return "해결" in node.content
김개발 씨는 처음 만든 AI 에이전트를 테스트해봤습니다. 간단한 문제는 잘 풀었지만, 복잡한 문제를 주자 10분이 지나도 답을 내지 못했습니다.
로그를 보니 수백 개의 노드를 탐색하고 있었습니다. "이러다간 서버 비용이 폭탄이겠는데요." 김개발 씨는 걱정이 되었습니다.
박시니어 씨가 화면을 보며 말했습니다. "아, 여기 봐요.
명백히 잘못된 방향인데도 계속 탐색하고 있네요. Pruning이 필요합니다." Pruning이란 무엇일까요?
정원사가 나무를 가꿀 때를 생각해봅시다. 건강하지 않거나 잘못 자란 가지는 잘라냅니다.
그래야 나무가 좋은 가지에 영양분을 집중할 수 있습니다. Pruning도 마찬가지입니다.
AI가 탐색 중에 "이 경로는 가망이 없다"고 판단되면 즉시 잘라내는 것입니다. 어떻게 가망 없는 경로를 판단할까요?
각 노드에 점수를 매깁니다. 위의 코드에서 evaluate_node 메서드를 보면, LLM에게 현재 생각이 문제 해결에 도움이 되는지 물어봅니다.
점수가 threshold(임계값) 이하면 그 가지를 더 이상 탐색하지 않습니다. 이렇게 하면 쓸모없는 계산을 대폭 줄일 수 있습니다.
Backtracking은 왜 필요할까요? 미로를 탐험한다고 생각해봅시다.
한 길을 따라가다가 막다른 벽에 부딪혔습니다. 어떻게 해야 할까요?
당연히 뒤로 돌아가서 다른 길을 찾아야 합니다. Backtracking이 바로 이 과정입니다.
위의 코드에서 backtrack 함수는 재귀적으로 작동합니다. 한 노드의 모든 자식을 탐색했는데 해결책을 못 찾으면 None을 반환합니다.
이것이 바로 "되돌아가기" 신호입니다. 부모 노드는 이 신호를 받고 다음 자식을 시도합니다.
코드를 단계별로 분석해봅시다. 먼저 깊이 제한을 확인합니다.
max_depth를 넘으면 무조건 None을 반환하며 되돌아갑니다. 이것이 첫 번째 안전장치입니다.
다음으로 evaluate_node로 현재 노드를 평가합니다. 점수가 threshold 미만이면 즉시 None을 반환합니다.
이것이 Pruning입니다. 더 이상 이 가지를 탐색하지 않습니다.
is_goal 메서드로 목표에 도달했는지 확인합니다. 만약 목표 상태라면 즉시 그 노드를 반환합니다.
성공적으로 해결책을 찾은 것입니다. 목표가 아니라면 자식 노드들을 하나씩 재귀 탐색합니다.
for 루프에서 각 자식에 대해 backtrack을 호출합니다. 하나라도 성공하면 즉시 결과를 반환합니다.
모든 자식이 실패하면 None을 반환하며 Backtracking이 일어납니다. 실무에서 이 기법들은 어떻게 활용될까요?
예를 들어 여행 계획 AI를 만든다고 해봅시다. 사용자가 "3박 4일 일본 여행 코스를 추천해줘"라고 요청합니다.
AI는 수많은 조합을 고려해야 합니다. 도쿄 첫날, 오사카 첫날, 교토 첫날 등 시작점만 해도 여러 개입니다.
여기서 Pruning을 적용하면 효율적입니다. 만약 사용자가 "예산은 100만원"이라고 했는데, 첫날 호텔이 50만원이라면?
이 경로는 명백히 예산 초과입니다. 즉시 잘라냅니다.
나머지 3일을 고려할 필요도 없습니다. Backtracking도 유용합니다.
3일차까지 계획을 짰는데 4일차에 공항으로 가는 교통편이 없다면? 되돌아가서 3일차 숙소를 다른 곳으로 바꿔야 합니다.
주의할 점이 있습니다. Pruning의 threshold를 너무 높게 설정하면 좋은 경로까지 잘라낼 수 있습니다.
초반에는 점수가 낮아 보여도 나중에 좋은 결과로 이어질 수 있습니다. 적절한 균형이 필요합니다.
또 다른 주의점은 평가 비용입니다. 모든 노드를 LLM으로 평가하면 그 자체로 비용이 많이 듭니다.
간단한 휴리스틱 함수를 먼저 적용하고, 애매한 경우에만 LLM을 사용하는 것이 좋습니다. 김개발 씨는 Pruning과 Backtracking을 추가한 뒤 다시 테스트했습니다.
놀랍게도 같은 문제를 30초 만에 풀었습니다. "와, 10배 이상 빨라졌어요!" 박시니어 씨가 웃으며 말했습니다.
"좋아요. 이제 진짜 스마트한 AI 에이전트네요.
모든 길을 다 가보는 게 아니라, 똑똑하게 선택하고 되돌아올 줄 아니까요." Pruning과 Backtracking은 Tree of Thoughts의 핵심 기법입니다. 이 두 가지를 잘 활용하면 효율적이고 실용적인 AI 에이전트를 만들 수 있습니다.
실전 팁
💡 - threshold 값은 실험을 통해 최적값을 찾으세요. 너무 높으면 좋은 경로를 놓치고, 너무 낮으면 비효율적입니다
- 간단한 휴리스틱으로 먼저 필터링하고, 필요할 때만 LLM 평가를 사용하세요
- 최대 깊이 제한은 필수입니다. 무한 재귀를 방지하세요
4. 실습: ToT 에이전트
김개발 씨는 이론을 충분히 배웠습니다. 이제 실제로 작동하는 Tree of Thoughts 에이전트를 만들어볼 시간입니다.
박시니어 씨가 과제를 주었습니다. "24 게임을 푸는 AI를 만들어보세요.
네 개의 숫자로 24를 만드는 거예요."
Tree of Thoughts 에이전트를 실제로 구현하면서 지금까지 배운 모든 개념을 통합합니다. 노드 생성, BFS/DFS 탐색, Pruning, Backtracking을 모두 활용하여 복잡한 문제를 해결하는 완전한 시스템을 만듭니다.
24 게임은 ToT의 효과를 명확히 보여주는 좋은 예제입니다.
다음 코드를 살펴봅시다.
class ToTAgent:
def __init__(self, llm, max_depth=4, beam_width=3):
self.llm = llm
self.max_depth = max_depth
# Beam Search: 각 레벨에서 상위 N개만 유지
self.beam_width = beam_width
def solve_24(self, numbers):
# 초기 상태 생성
root = ThoughtNode(f"주어진 숫자: {numbers}")
root.score = 1.0
# BFS 기반 Beam Search로 탐색
current_level = [root]
for depth in range(self.max_depth):
next_level = []
for node in current_level:
# 각 노드에서 가능한 다음 생각들 생성
children = self.generate_next_thoughts(node)
for child in children:
# Pruning: 평가하고 점수 매기기
child.score = self.evaluate_thought(child)
if child.score > 0.3: # threshold
next_level.append(child)
# 목표 확인
if self.is_solution(child):
return self.extract_path(child)
# Beam Search: 상위 beam_width개만 유지
next_level.sort(key=lambda x: x.score, reverse=True)
current_level = next_level[:self.beam_width]
if not current_level:
break # Backtracking: 더 이상 탐색 불가
return None # 해결 실패
def generate_next_thoughts(self, node):
# LLM에게 다음 단계 생각들을 생성하게 함
prompt = f"현재 상태: {node.content}\n가능한 다음 단계 3가지:"
thoughts = self.llm.generate(prompt, n=3)
return [node.add_child(t) for t in thoughts]
def evaluate_thought(self, node):
# 이 생각이 24에 가까워지는지 평가
prompt = f"이 단계가 24를 만드는데 도움이 될까요? {node.content}"
return float(self.llm.evaluate(prompt))
def is_solution(self, node):
# 최종 답이 24인지 확인
return "= 24" in node.content
def extract_path(self, node):
# 루트부터 현재 노드까지의 경로 추출
path = []
while node:
path.append(node.content)
node = node.parent
return list(reversed(path))
김개발 씨는 화이트보드 앞에 섰습니다. "24 게임이요?
예를 들어 4, 6, 8, 2가 주어지면 이걸로 24를 만드는 건가요?" 박시니어 씨가 고개를 끄덕였습니다. "맞아요.
더하기, 빼기, 곱하기, 나누기를 써서 24를 만들면 됩니다. 사람도 어려워하는 퍼즐이죠." 이 문제는 왜 Tree of Thoughts에 적합할까요?
24 게임은 여러 단계의 계산이 필요합니다. 첫 번째 연산을 선택하고, 그 결과로 다시 연산하고, 계속 이어집니다.
한 번에 정답을 맞히기 어렵습니다. 여러 경로를 시도해봐야 합니다.
바로 ToT가 빛을 발하는 상황입니다. 위의 코드는 어떻게 작동할까요?
ToTAgent 클래스는 세 가지 핵심 파라미터를 받습니다. max_depth는 최대 계산 단계입니다.
24 게임은 보통 3-4단계면 풀리므로 4로 설정합니다. beam_width는 Beam Search의 폭입니다.
각 레벨에서 상위 몇 개의 경로만 유지할지 결정합니다. Beam Search란 무엇일까요?
BFS와 비슷하지만, 모든 노드를 유지하지 않습니다. 각 레벨에서 점수가 높은 상위 N개만 선택합니다.
이렇게 하면 탐색 공간이 크게 줄어듭니다. 완전히 탐색하지는 못하지만, 실용적으로 충분히 좋은 답을 찾습니다.
solve_24 메서드를 단계별로 살펴봅시다. 먼저 루트 노드를 만듭니다.
주어진 숫자들을 담고 있습니다. current_level 리스트에 루트만 넣고 시작합니다.
각 깊이마다 루프를 돌립니다. current_level의 각 노드에 대해 generate_next_thoughts를 호출합니다.
이 메서드는 LLM에게 "다음 단계로 무엇을 할 수 있을까요?"라고 묻습니다. 예를 들어 "4 + 6 = 10", "4 * 6 = 24", "8 - 2 = 6" 같은 생각들이 나옵니다.
각 자식 노드를 evaluate_thought로 평가합니다. LLM에게 "이 계산이 24를 만드는데 도움이 될까요?"라고 물어봅니다.
점수가 threshold(0.3) 이상이면 next_level에 추가합니다. 이것이 Pruning입니다.
is_solution으로 목표에 도달했는지 확인합니다. 만약 현재 노드가 "= 24"를 포함하면 성공입니다.
extract_path로 루트부터 이 노드까지의 전체 경로를 추출하여 반환합니다. 목표를 못 찾았다면 Beam Search 단계입니다.
next_level을 점수 순으로 정렬하고, 상위 beam_width개만 남깁니다. 나머지는 버립니다.
이게 메모리와 계산을 절약하는 핵심입니다. current_level이 비어있으면 루프를 중단합니다.
모든 경로가 Pruning되었다는 뜻입니다. 이것이 Backtracking의 한 형태입니다.
더 이상 탐색할 길이 없으니 포기하는 것입니다. 실제로 어떻게 작동하는지 시나리오를 봅시다.
숫자 [4, 6, 8, 2]가 주어졌다고 가정합니다. 첫 번째 레벨에서 AI는 "4 + 6 = 10", "4 * 6 = 24", "8 - 2 = 6" 같은 생각을 생성합니다.
평가 결과 "4 * 6 = 24"가 가장 높은 점수를 받습니다. 명백히 정답에 가까우니까요.
두 번째 레벨로 넘어갑니다. "4 * 6 = 24"는 이미 완성된 답입니다.
is_solution이 True를 반환하고, 즉시 경로를 반환합니다. 탐색 종료!
만약 첫 번째 레벨에서 정답을 못 찾았다면? "4 + 6 = 10"이 선택되었다고 합시다.
두 번째 레벨에서는 "10 + 8 = 18", "10 * 2 = 20", "10 + 8 + 2 = 20" 같은 생각이 나옵니다. 이 중에서도 또 평가하고 상위 몇 개만 유지합니다.
이 과정은 해결책을 찾거나, max_depth에 도달하거나, 모든 경로가 막힐 때까지 계속됩니다. 왜 이 방법이 효과적일까요?
사람이 24 게임을 풀 때를 생각해봅시다. 모든 가능한 조합을 다 시도하지 않습니다.
"이건 24에서 너무 멀어지네"라고 판단되면 그 방향은 버립니다. 몇 가지 유망한 경로에 집중합니다.
ToT 에이전트도 똑같이 행동합니다. 주의할 점도 있습니다.
beam_width가 너무 작으면 정답을 놓칠 수 있습니다. 예를 들어 1로 설정하면 탐욕적 알고리즘이 되어 국소 최적해에 갇힐 수 있습니다.
반대로 너무 크면 BFS와 다를 바 없어 비효율적입니다. 보통 3-5 정도가 적당합니다.
LLM의 평가 품질도 중요합니다. 만약 LLM이 좋은 경로를 낮게 평가하면 Pruning으로 잘릴 수 있습니다.
평가 프롬프트를 신중하게 작성해야 합니다. 김개발 씨는 코드를 완성하고 테스트했습니다.
여러 숫자 조합을 넣어봤습니다. "와, 대부분 맞히네요!
사람보다 빠른 것 같아요." 박시니어 씨가 말했습니다. "좋아요.
이제 이 구조를 다른 문제에도 적용할 수 있습니다. 코드 생성, 전략 게임, 수학 증명 등 다양한 분야에서 활용 가능해요." Tree of Thoughts 에이전트를 직접 구현해보면서 모든 개념이 어떻게 연결되는지 이해할 수 있었습니다.
여러분도 자신만의 문제에 ToT를 적용해 보세요.
실전 팁
💡 - beam_width는 3-5 정도로 시작해서 실험적으로 조정하세요
- LLM 평가 프롬프트는 구체적이고 명확하게 작성하세요
- 처음에는 간단한 문제로 테스트하고, 점진적으로 복잡한 문제로 확장하세요
5. 실습: 게임 플레이 에이전트
김개발 씨는 24 게임 에이전트를 성공적으로 만들었습니다. 박시니어 씨가 새로운 도전 과제를 제시했습니다.
"이번엔 틱택토(Tic-Tac-Toe) 게임 AI를 만들어보세요. 상대방의 수까지 고려해야 하니 더 복잡할 거예요."
게임 플레이 에이전트는 자신의 행동뿐만 아니라 상대방의 대응까지 시뮬레이션해야 합니다. Minimax 개념과 Tree of Thoughts를 결합하여, 여러 수를 앞서 내다보고 최선의 수를 선택하는 AI를 만듭니다.
DFS가 특히 유용한 시나리오입니다.
다음 코드를 살펴봅시다.
class GamePlayAgent:
def __init__(self, llm, max_depth=3):
self.llm = llm
self.max_depth = max_depth
def find_best_move(self, game_state, is_maximizing=True):
# Tree of Thoughts로 최선의 수 찾기
root = ThoughtNode(game_state)
best_move = None
best_score = float('-inf') if is_maximizing else float('inf')
# 가능한 모든 수를 생성
possible_moves = self.generate_moves(game_state)
for move in possible_moves:
# 이 수를 둔 후의 상태 시뮬레이션
new_state = self.apply_move(game_state, move)
child = root.add_child(new_state)
# DFS로 미래 예측 (상대방 턴 포함)
score = self.minimax_tot(
child,
depth=1,
is_maximizing=not is_maximizing
)
child.score = score
# 최선의 수 업데이트
if is_maximizing and score > best_score:
best_score = score
best_move = move
elif not is_maximizing and score < best_score:
best_score = score
best_move = move
return best_move, best_score
def minimax_tot(self, node, depth, is_maximizing):
# DFS + Minimax로 게임 트리 탐색
game_state = node.content
# 종료 조건들
if depth >= self.max_depth:
return self.evaluate_state(game_state)
if self.is_terminal(game_state):
return self.get_terminal_score(game_state)
# 재귀적으로 자식 노드들 탐색
moves = self.generate_moves(game_state)
if is_maximizing:
max_score = float('-inf')
for move in moves:
new_state = self.apply_move(game_state, move)
child = node.add_child(new_state)
score = self.minimax_tot(child, depth + 1, False)
max_score = max(max_score, score)
# Alpha-Beta Pruning을 추가하면 더 효율적
return max_score
else:
min_score = float('inf')
for move in moves:
new_state = self.apply_move(game_state, move)
child = node.add_child(new_state)
score = self.minimax_tot(child, depth + 1, True)
min_score = min(min_score, score)
return min_score
def evaluate_state(self, game_state):
# LLM에게 현재 게임 상태 평가 요청
prompt = f"현재 게임 상태를 평가하세요 (-1~1): {game_state}"
return float(self.llm.evaluate(prompt))
def is_terminal(self, game_state):
# 게임 종료 상태인지 확인
return "승리" in game_state or "무승부" in game_state
def get_terminal_score(self, game_state):
if "승리" in game_state:
return 1.0
elif "패배" in game_state:
return -1.0
return 0.0
def generate_moves(self, game_state):
# 가능한 수들을 생성 (구현은 게임에 따라 다름)
return []
def apply_move(self, game_state, move):
# 수를 적용한 새로운 상태 반환
return game_state # 실제로는 게임 로직 필요
김개발 씨는 고민에 빠졌습니다. "24 게임은 혼자 푸는 거였는데, 틱택토는 상대가 있잖아요.
어떻게 접근해야 할까요?" 박시니어 씨가 설명을 시작했습니다. "좋은 질문이에요.
게임 AI는 상대방의 최선의 수까지 가정해야 합니다. 이게 Minimax 알고리즘의 핵심이에요." Minimax란 무엇일까요?
두 명이 체스를 둔다고 상상해봅시다. 당신은 자신에게 가장 좋은 수를 두려고 합니다.
하지만 상대방도 마찬가지입니다. 당신이 어떤 수를 두면, 상대는 그에 대한 최선의 대응을 할 것입니다.
따라서 당신은 "내가 이 수를 두면, 상대가 저렇게 대응하고, 그러면 내가 또 이렇게 하고..."를 미리 계산해야 합니다. Minimax는 바로 이 과정을 자동화합니다.
내 턴에서는 점수를 최대화(Maximize)하려 하고, 상대 턴에서는 점수를 최소화(Minimize)하려 한다고 가정합니다. 이를 트리로 표현하면 Tree of Thoughts와 완벽하게 결합됩니다.
왜 DFS가 적합할까요? 게임 AI는 완전한 경로를 평가해야 합니다.
예를 들어 "내가 A1에 두고, 상대가 B2에 두고, 내가 C3에 두면 승리"처럼 끝까지 시뮬레이션해야 합니다. BFS로는 중간 상태만 보게 되어 최종 결과를 알 수 없습니다.
따라서 DFS로 한 경로를 끝까지 탐색하는 것이 필수입니다. 코드를 자세히 살펴봅시다.
find_best_move 메서드는 현재 게임 상태에서 최선의 수를 찾습니다. 먼저 가능한 모든 수를 generate_moves로 생성합니다.
틱택토라면 빈 칸들이 가능한 수입니다. 각 수에 대해 apply_move로 새로운 상태를 시뮬레이션합니다.
그리고 minimax_tot를 호출하여 그 수의 가치를 평가합니다. 중요한 점은 상대방 턴으로 넘어간다는 것입니다.
is_maximizing을 반대로 뒤집습니다. minimax_tot 메서드가 핵심입니다.
이것은 재귀 함수입니다. 먼저 종료 조건들을 확인합니다.
max_depth에 도달했거나, 게임이 끝났으면 평가를 반환합니다. is_terminal로 승리/패배/무승부를 확인합니다.
종료가 아니라면 다음 수들을 탐색합니다. 여기서 Minimax 로직이 적용됩니다.
is_maximizing이 True면 내 턴입니다. 가능한 수들 중 점수가 가장 높은 것을 선택합니다.
False면 상대 턴입니다. 점수가 가장 낮은 것을 선택합니다.
각 수에 대해 재귀적으로 minimax_tot를 호출합니다. depth를 1 증가시키고, is_maximizing을 뒤집습니다.
이렇게 하면 자연스럽게 내 턴과 상대 턴이 번갈아 나타납니다. 실제 게임 시나리오를 봅시다.
틱택토 게임이 진행 중입니다. 현재 보드 상태에서 내가 둘 수 있는 칸이 3개 있습니다.
A, B, C라고 부르겠습니다. A에 두면 어떻게 될까요?
AI는 상대방의 가능한 대응들을 시뮬레이션합니다. 상대가 D에 두는 경우, E에 두는 경우 등을 모두 고려합니다.
각 경우에 대해 다시 내 턴을 시뮬레이션합니다. 이렇게 깊이 3까지 탐색하면, 수십 가지 시나리오가 평가됩니다.
B와 C에 대해서도 똑같이 합니다. 최종적으로 A, B, C 각각의 점수가 나옵니다.
예를 들어 A는 0.8, B는 -0.5, C는 0.3이라고 합시다. 당연히 A를 선택합니다.
Pruning은 어떻게 적용할까요? 코드 주석에 "Alpha-Beta Pruning을 추가하면 더 효율적"이라고 써있습니다.
이것은 Minimax의 고급 기법입니다. 이미 찾은 최선보다 나쁜 경로는 완전히 탐색하지 않고 잘라냅니다.
예를 들어 A를 평가하는 중에 이미 점수 0.8을 얻었습니다. B를 평가할 때, 첫 번째 상대방 대응만 봐도 최대 0.5밖에 안 나온다면?
나머지 대응들을 볼 필요가 없습니다. 어차피 A보다 나쁘니까요.
이것이 Alpha-Beta Pruning입니다. LLM의 역할은 무엇일까요?
evaluate_state 메서드를 보면 LLM에게 중간 상태를 평가하게 합니다. 체스처럼 복잡한 게임에서는 max_depth까지 가도 게임이 안 끝날 수 있습니다.
그럴 때 현재 상태가 얼마나 유리한지 LLM이 판단합니다. "백의 말 배치가 우수함, 0.7점" 같은 식입니다.
간단한 게임에서는 규칙 기반 평가 함수를 쓸 수도 있습니다. 틱택토라면 "두 줄에 말이 있으면 +0.5점" 같은 휴리스틱을 직접 코딩할 수 있습니다.
주의할 점이 있습니다. Depth가 너무 깊으면 계산이 폭발합니다.
틱택토는 9칸이라 괜찮지만, 체스나 바둑은 경우의 수가 천문학적입니다. 적절한 depth 제한이 필수입니다.
또한 시간 제한도 고려해야 합니다. 실시간 게임이라면 1초 안에 수를 둬야 합니다.
무한정 탐색할 수 없습니다. Iterative Deepening 같은 기법을 쓰면 시간 내에 최선을 찾을 수 있습니다.
김개발 씨는 틱택토 AI를 완성했습니다. 직접 플레이해보니 AI가 절대 지지 않았습니다.
"와, 정말 똑똑하게 두네요. 제가 실수하면 바로 이기고, 완벽하게 두면 무승부로 끝나요." 박시니어 씨가 말했습니다.
"맞아요. 이게 Minimax의 힘입니다.
Tree of Thoughts와 결합하면 더 복잡한 전략 게임도 가능해요. 스타크래프트 AI, 포커 AI 같은 것들도 비슷한 원리죠." 게임 플레이 에이전트를 만들면서 DFS, Minimax, Pruning이 실전에서 어떻게 조화를 이루는지 배웠습니다.
여러분도 체스, 오목, 카드 게임 등에 ToT를 적용해 보세요.
실전 팁
💡 - 게임이 복잡할수록 depth를 낮게 설정하고, 평가 함수를 정교하게 만드세요
- Alpha-Beta Pruning으로 불필요한 계산을 줄이세요
- 시간 제한이 있다면 Iterative Deepening을 고려하세요
이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!
댓글 (0)
함께 보면 좋은 카드 뉴스
Memory Systems 완벽 가이드 - LLM 에이전트의 기억력 설계
LLM 에이전트가 대화를 기억하고 학습하는 메모리 시스템의 모든 것을 다룹니다. 단기 메모리부터 벡터 DB 기반 장기 메모리, 에피소딕 메모리까지 실전 구현 방법을 배워봅니다.
Tool-Augmented Agents 완벽 가이드
LLM에 도구를 연결하여 검색, API 호출, 계산 등 실제 작업을 수행하는 에이전트를 만드는 방법을 초급 개발자도 쉽게 이해할 수 있도록 설명합니다. 실무에서 바로 활용할 수 있는 멀티 툴 에이전트와 API 통합 예제를 포함합니다.
Reflection과 Self-Correction 완벽 가이드
AI 에이전트가 스스로 생각하고 개선하는 방법을 배웁니다. Reflection 패턴을 통해 실패로부터 학습하고, 자기 평가를 통해 더 나은 결과를 만들어내는 실전 기법을 익혀봅니다.
Plan-and-Execute 패턴 완벽 가이드
LLM 에이전트가 복잡한 작업을 해결하는 Plan-and-Execute 패턴을 배웁니다. 계획 수립, 실행, 재조정의 3단계 프로세스를 실무 예제로 익히고, 멀티 스텝 자동화를 구현합니다.
ReAct 패턴 마스터 완벽 가이드
LLM이 생각하고 행동하는 ReAct 패턴을 처음부터 끝까지 배웁니다. Thought-Action-Observation 루프로 똑똑한 에이전트를 만들고, 실전 예제로 웹 검색과 계산을 결합한 강력한 AI 시스템을 구축합니다.