한국정보기술진흥원한국인공지능올림피아드 (KOAI) 2026 개최안내

6월 4일 목요일

게임 트리 알고리즘, 인공지능 의사결정의 뼈대로 주목...미니맥스·알파베타 가지치기가 핵심 원리
인공지능 2

게임 트리 알고리즘, 인공지능 의사결정의 뼈대로 주목...미니맥스·알파베타 가지치기가 핵심 원리

인공지능이 게임에서 최선의 수를 찾는 원리가 주목받고 있다. [한국정보기술신문] 인공지능이 틱택토(Tic-Tac-Toe)나 체스, 바둑 같은 게임에서 다음 수를 결정하는 핵심 원리로 게임 트리 기반 알고리즘이 다시 조명받고 있다. 게임은 규칙이 명확해 추상적으로 정의할 수 있고, 인간의 지적 능력과 연관이 있는 것으로 여겨져 인공지능 분야에서 오래전부터 중요한 연구 주제로 다뤄져 왔다. 게임 트리 알고리즘은 두 명이 번갈아 수를 두는 게임을 전제로 한다. 두 경기자는 각각 맥스(MAX)와 민(MIN)으로 불리며, 맥스가 항상 먼저 수를 둔다고 가정한다. 또한 한 명이 이기면 다른 한 명은 반드시 지는 제로섬(zero-sum) 구조로, 둘이 함께 이기는 협동적 승리는 존재하지 않는다. Unsplash 제공 9! 개에 이르는 경우의 수, 트리로 표현 대표적인 사례인 틱택토는 가로세로 3×3 크기의 판에서 진행된다. 한 곳에 수를 놓으면 상대가 놓을 수 있는 칸이 하나씩 줄어든다. 이 때문에 가능한 모든 경우의 수는 9×8×7×…×1, 즉 9!(팩토리얼)인 36만2880가지에 이른다. 인공지능은 이처럼 방대한 게임 상태를 나무 모양의 구조인 '게임 트리'로 표현해 분석한다. 다만 모든 경우의 수를 전부 계산하는 일은 드물다. 경우에 따라 전부 따져야 할 때도 있지만, 실제로는 그렇지 않은 경우가 더 많기 때문이다. 불필요한 계산을 줄이기 위한 여러 기법이 고안된 배경이다. 미니맥스, 상대의 최선을 가정해 수를 선택 가장 기본이 되는 방식은 미니맥스(minimax) 알고리즘이다. 현재 보드 상태를 트리의 뿌리(루트)로 놓고, 인공지능이 둘 수 있는 빈칸의 수만큼 가지를 뻗어 가능한 미래 상태를 모두 펼친다. 게임이 끝나는 최종 상태에 도달하면 더 이상 가지를 나누지 않고 점수를 매긴다. 인공지능이 이기면 +1점, 지면 -1점, 비기면 0점이 부여된다. 핵심은 상대방이 항상 최선의 수를 둔다고 가정하는 데 있다. 작은 숫자를 골라야 유리한 민은 가지 중 가장 작은 값을 선택하고, 큰 숫자를 골라야 유리한 맥스는 가장 큰 값을 선택한다. 트리의 아래쪽 단말 노드부터 위로 올라오며 이 과정을 반복해 최선의 수를 결정한다. 미니맥스는 게임 트리 전체를 깊이 우선으로 완벽하게 탐색한다. 트리의 최대 깊이가 m이고 각 노드에서 가능한 수가 b개일 경우, 이 알고리즘의 시간 복잡도는 b의 m제곱, 즉 O(b^m)으로 표현된다. 깊이가 깊어질수록 계산량이 기하급수적으로 늘어난다는 의미다. 알파베타 가지치기로 불필요한 탐색 제거 이러한 계산 부담을 덜기 위한 기법이 알파베타 가지치기다. 미니맥스가 만드는 탐색 트리 가운데 상당수는 최종 결과에 영향을 주지 않는데, 이런 가지를 미리 쳐내는 방식이다. 탐색 과정에서 맥스는 알파(α) 값만, 민은 베타(β) 값만 갱신하며, 자식 노드로 두 값을 전달해 비교한다. 예를 들어 맥스가 이미 7이라는 값을 확보한 상태에서 다른 경로를 탐색할 때, 그 경로가 6보다 작은 값을 보낼 것이 분명하다면 나머지 단말 노드는 계산할 필요가 없다. 맥스는 7보다 큰 값을 찾고 있기 때문이다. 이처럼 부모 노드의 현재 값에 따라 트리 전체를 탐색하지 않고도 같은 결론에 도달할 수 있다. 시간 한계엔 휴리스틱 평가 함수 활용 미니맥스 알고리즘은 본래 탐색 공간 전체를 살피는 것을 전제로 한다. 그러나 실제 게임에서는 탐색 공간이 매우 커 정해진 시간 안에 모든 경우를 따지기가 사실상 불가능하다. 적당한 시간 안에 다음 수를 결정해야 하기 때문이다. 이때 활용되는 것이 휴리스틱 평가 함수(evaluation function)다. 탐색을 마쳐야 하는 시간에 도달하면 탐색을 중단하고, 아직 게임이 끝나지 않은 비단말 노드를 마치 최종 상태에 도달한 것처럼 간주해 점수를 추정한다. 완벽한 계산 대신 합리적인 추정을 통해 제한된 시간 안에서 최선에 가까운 결정을 내리는 셈이다. 게임 트리에서 출발한 이들 기법은 오늘날 다양한 인공지능 의사결정 모델의 기초로 활용되며, 탐색 효율을 높이려는 연구가 꾸준히 이어지고 있다. 한국정보기술신문 인공지능분과 박연호 기자 news@kitpa.org

엔비디아 CEO 젠슨 황 "지금이 AI 혁명의 시작"...카네기멜론 졸업식 축사에서 강조

엔비디아 CEO 젠슨 황 "지금이 AI 혁명의 시작"...카네기멜론 졸업식 축사에서 강조

인공지능 · 교육 · 정보통신 1
유니브컨설팅, 중고생 대상 AI·게임 진로특강 23일 개최...산학계 전문가가 직접 강연

유니브컨설팅, 중고생 대상 AI·게임 진로특강 23일 개최...산학계 전문가가 직접 강연

교육 · 인공지능 1
백준, 문제 열람 넘어 "채점 서비스와 함께 돌아오겠다"...종료 페이지 문구 변경 확인

백준, 문제 열람 넘어 "채점 서비스와 함께 돌아오겠다"...종료 페이지 문구 변경 확인

교육 · 정보기술 2
중고생 모두 도전하는 국내 최초 AI 올림피아드 'KOAI 2026'...5월 22일 접수 마감

중고생 모두 도전하는 국내 최초 AI 올림피아드 'KOAI 2026'...5월 22일 접수 마감

인공지능 · 교육 3
건국대학교, 인공지능학과 신설 2027년 개교...AI 인재 양성 본격화, 연 50명 선발

건국대학교, 인공지능학과 신설 2027년 개교...AI 인재 양성 본격화, 연 50명 선발

인공지능 · 교육 1
[백준 서비스 종료 ⑪] 백준 온라인 저지, 16년 역사에 마침표...메인 화면에 카운트다운만 남았다

[백준 서비스 종료 ⑪] 백준 온라인 저지, 16년 역사에 마침표...메인 화면에 카운트다운만 남았다

정보기술 · 교육 3
[백준 서비스 종료 ⑩] 고동진 의원 "백준은 살아있는 유산...정부가 응답해야"

[백준 서비스 종료 ⑩] 고동진 의원 "백준은 살아있는 유산...정부가 응답해야"

교육 · 유관기관 · 정보기술 3
[백준 서비스 종료 ⑨] 종료 3일 앞두고 마지막 글..."LLM이 문제 잘 푼다고 코딩 테스트 무의미하다는 의견에 동의 어렵다"

[백준 서비스 종료 ⑨] 종료 3일 앞두고 마지막 글..."LLM이 문제 잘 푼다고 코딩 테스트 무의미하다는 의견에 동의 어렵다"

교육 · 정보기술 5
한국정보기술진흥원, 국제인공지능올림피아드 한국 공인 주관기관 선정…대표팀 구성·파견 맡아

한국정보기술진흥원, 국제인공지능올림피아드 한국 공인 주관기관 선정…대표팀 구성·파견 맡아

교육 · 인공지능 2
[백준 서비스 종료 ⑧] 백준 이후 어디로 가나...이용자들 대체 플랫폼 찾기 분주

[백준 서비스 종료 ⑧] 백준 이후 어디로 가나...이용자들 대체 플랫폼 찾기 분주

인공지능 · 교육 4
[백준 서비스 종료 ⑦] 백준 서비스 종료 이틀 앞두고 "Good Bye, BOJ" 고별 대회 열린다

[백준 서비스 종료 ⑦] 백준 서비스 종료 이틀 앞두고 "Good Bye, BOJ" 고별 대회 열린다

정보기술 · 교육 3
[백준 서비스 종료 ⑥] 3만 이용자 백준허브는 살아남는다..."백준은 끝나도 기록은 계속"

[백준 서비스 종료 ⑥] 3만 이용자 백준허브는 살아남는다..."백준은 끝나도 기록은 계속"

정보기술 · 교육 3
[백준 서비스 종료 ⑤] 백준 확장 프로그램 토탐정도 동반 종료..."4년간의 여정, 파워포인트로 시작했습니다"

[백준 서비스 종료 ⑤] 백준 확장 프로그램 토탐정도 동반 종료..."4년간의 여정, 파워포인트로 시작했습니다"

정보기술 · 교육 3
[백준 서비스 종료 ④] "이제 두려울 게 없다"...백준 종료 앞두고 봉인 풀린 전설의 함정 문제

[백준 서비스 종료 ④] "이제 두려울 게 없다"...백준 종료 앞두고 봉인 풀린 전설의 함정 문제

정보기술 · 교육 3
[백준 서비스 종료 ③] solved.ac, 백준 종료에도 난이도 정보 계속 제공..."별조각 10배 이벤트도 즉시 시행"

[백준 서비스 종료 ③] solved.ac, 백준 종료에도 난이도 정보 계속 제공..."별조각 10배 이벤트도 즉시 시행"

정보기술 · 교육 3
[백준 서비스 종료 ②] 백준 온라인 저지 운영자 최백준, 종료 배경 추가 입장 발표..."고민은 수년 전부터"

[백준 서비스 종료 ②] 백준 온라인 저지 운영자 최백준, 종료 배경 추가 입장 발표..."고민은 수년 전부터"

정보기술 · 교육 3
[백준 서비스 종료 ①] 16년 역사 백준 온라인 저지, 4월 28일 서비스 종료...운영자 최백준 "부득이한 결정"

[백준 서비스 종료 ①] 16년 역사 백준 온라인 저지, 4월 28일 서비스 종료...운영자 최백준 "부득이한 결정"

정보기술 · 교육 3
이공계 박사 우수장학금 사업 첫 시행...박사과정생 1000명에 연 750만원 지원, 2030년까지 1만명 확대

이공계 박사 우수장학금 사업 첫 시행...박사과정생 1000명에 연 750만원 지원, 2030년까지 1만명 확대

교육 1
2026 한국정보올림피아드 1차 대회, 4월 13일부터 접수 시작...5월 10일 온라인 개최

2026 한국정보올림피아드 1차 대회, 4월 13일부터 접수 시작...5월 10일 온라인 개최

교육 2
법무보호공단-한기대, 비대면 교육체계 구축 업무협약 체결...AI 기반 온라인 플랫폼으로 보호대상자·직원 역량 강화 교육 실시

법무보호공단-한기대, 비대면 교육체계 구축 업무협약 체결...AI 기반 온라인 플랫폼으로 보호대상자·직원 역량 강화 교육 실시

교육 1
한국정보기술진흥원, 국내 첫 AR/VR 민간기능경기대회 개최...고용노동부 장관상 걸린 전국 대회

한국정보기술진흥원, 국내 첫 AR/VR 민간기능경기대회 개최...고용노동부 장관상 걸린 전국 대회

보도자료 · 실감형콘텐츠 · 교육 2
2026 제6회 청소년 IT경시대회, 전국 우수 인재 가린다...대상·금상 수상자 공개

2026 제6회 청소년 IT경시대회, 전국 우수 인재 가린다...대상·금상 수상자 공개

보도자료 · 교육 1
4대 과기원, AX 혁신 생태계 조성 전략 발표...지역균형발전 핵심 엔진으로

4대 과기원, AX 혁신 생태계 조성 전략 발표...지역균형발전 핵심 엔진으로

유관기관 · 교육 3
구글, 미국 교사 600만 명에 AI 리터러시 무료 교육 제공...ISTE+ASCD와 파트너십 체결

구글, 미국 교사 600만 명에 AI 리터러시 무료 교육 제공...ISTE+ASCD와 파트너십 체결

인공지능 · 교육 2