게임 AI를 위한 탐색 알고리즘 입문 - 트리 탐색과 메타 휴리스틱으로 완성하는 최적화 C++ 기반 예제 코드 제공

게임 AI에 빠질 수 없는 탐색 알고리즘의 이론부터 실전 게임 적용까지 * 실전 AI 게임 구현을 위한 C++ 기반 예제 코드 제공 『게임 AI를 위한 탐색 알고리즘 입문』은 게임 AI 기술을 위한 핵심 요소 중 하나인 ‘탐색’에 대해 다룹니다. 탐색은 조합론적 게임 이론의 게임 트리 탐색과 조합 최적화를 사용한 메타 휴리스틱을 포함하여 지칭하는 용어입니다. 이 책에서는 C++ 개발 환경 준비와 플레이어의 행동을 예측하거나 조합 최적화를 이용하는 등 게임 유형에 따른 1인 게임에 맞춰 적합한 탐색 알고리즘을 설명합니다. 또한 장기나 바둑처럼 교대로 두는 2인 게임, 동시에 두는 2인 게임 등 다음 수를 전혀 예상할 수 없는 게임에 어울리는 탐색 알고리즘도 함께 살펴봅니다. 전반부에는 게임 종류에 어울리는 알고리즘을 소개했다면, 후반부에는 더 좋은 탐색을 위한 알고리즘과 실전에서 어떻게 활용할 수 있는지를 배워봅니다. ‘커넥트 포’ 놀이를 하는 AI를 직접 구현해 보고, 강화시키는 과정을 통해 실전 능력을 키워봅니다.

1장 게임과 탐색의 세계 1.1 게임 AI와 탐색 __1.1.1 게임에서 말하는 AI와 탐색 __1.1.2 게임 종류와 탐색 알고리즘 1.2 게임에서 탐색의 매력 __1.2.1 개인 게임 개발을 한다면 탐색! __1.2.2 대규모 상업 게임 개발에서도 탐색! __1.2.3 다양한 프로그래밍 대회에서 이기기 위한 비장의 무기 2장 개발 환경 준비 2.1 WSL(Windows Subsystem for Linux) 설치 방법 __2.1.1 WSL 동작 확인 __2.1.2 CPU 가상화 기능 확인 __2.1.3 바이오스/UEFI에서 가상화 기능 활성화 __2.1.4 배포판 설정 __2.1.5 패키지 업데이트 __2.1.6 C++ 개발 환경 설치하기 3장 컨텍스트가 있는 1인 게임에서 사용하고 싶은 탐색 알고리즘 3.1 예제 게임 소개: 숫자 모으기 미로 게임 __3.1.1 숫자 모으기 미로 게임 __3.1.2 숫자 모으기 미로 게임 구현하기 3.2 그리디 알고리즘(탐욕법) __3.2.1 그리디 알고리즘의 특징과 동작: 모든 탐색 알고리즘의 기초! 이것만 있으면 싸울 수 있다! __3.2.2 그리디 알고리즘 구현하기 3.3 빔 탐색 __3.3.1 빔 탐색의 특징과 동작: 탐색 공간을 파악해라! 경진 대회 상위권에서 자주 등장하는 탐색법! __3.3.2 빔 탐색 구현하기 COLUMN 빔 탐색 구현 방식 변경 3.4 Chokudai 탐색 __3.4.1 Chokudai 탐색의 특징과 동작: 다양성을 자동으로 확보! 간편하고 초보자에게 추천! __3.4.2 Chokudai 탐색 구현하기 4장 컨텍스트가 없는 1인 게임에서 사용하고 싶은 탐색 알고리즘 4.1 예제 게임 소개: 자동 숫자 모으기 미로 게임 __4.1.1 숫자 모으기 미로 게임 __4.1.2 자동 숫자 모으기 미로 구현하기 4.2 언덕 오르기 탐색 __4.2.1 언덕 오르기 탐색의 특징과 동작: 착실하게 좋은 답을 탐색한다! 간단하고 안정감 있는 알고리즘! __4.2.2 언덕 오르기 탐색 구현하기 4.3 담금질 기법 __4.3.1 담금질 기법의 특징과 동작: 국소 최적해에서 벗어나라! 마라톤 매치로 친숙한 알고리즘! __4.3.2 담금질 기법 구현하기 COLUMN 메타 휴리스틱 5장 교대로 두는 2인 게임에서 사용하고 싶은 탐색 알고리즘 5.1 예제 게임 소개: 교대로 두는 숫자 모으기 미로 게임 __5.1.1 교대로 두는 숫자 모으기 미로 게임 __5.1.2 교대로 두는 숫자 모으기 미로 구현하기 5.2 미니맥스 알고리즘 __5.2.1 미니맥스 알고리즘의 특징과 동작: 신의 한 수! __5.2.2 미니맥스 알고리즘 구현하기 5.3 알파-베타 가지치기 __5.3.1 알파-베타 가지치기의 특징과 동작: 낭비는 용서할 수 없다! 미니맥스 알고리즘 진화! COLUMN 미니맥스 알고리즘과 알파-베타 가지치기의 관계 __5.3.2 알파-베타 가지치기 구현하기 5.4 반복 심화 탐색 __5.4.1 반복 심화 탐색의 특징과 동작: 낭비할 시간이 없다! 최적의 트리 깊이를 찾자! __5.4.2 반복 심화 탐색 구현하기 5.5 순수 몬테카를로 탐색 __5.5.1 순수 몬테카를로 탐색의 특징과 동작: 게임판 평가는 필요없다! 승률이 좋은 수를 선택하자! COLUMN 몬테카를로 탐색과 라스베가스 탐색 __5.5.2 순수 몬테카를로 탐색 구현하기 5.6 MCTS 몬테카를로 트리 탐색 __5.6.1 MCTS의 특징과 동작: 적을 얕보지 말라! 강자 대결 시뮬레이션 __5.6.2 MCTS 구현하기 5.7 Thunder 탐색 __5.7.1 Thunder 탐색의 특징과 동작: 필자가 발명! 게임판 평가를 이용해서 유리한 노드를 탐색한다! __5.7.2 Thunder 탐색 구현하기 COLUMN Thunder 탐색은 어떻게 만들어졌나? 6장 동시에 두는 2인 게임에서 사용하고 싶은 탐색 알고리즘 6.1 예제 게임 소개: 동시에 두는 숫자 모으기 미로 게임 __6.1.1 동시에 두는 숫자 모으기 미로 게임 __6.1.2 동시에 두는 숫자 모으기 미로 구현하기 6.2 교대로 두는 게임용 알고리즘 적용 __6.2.1 순수 몬테카를로 탐색 구현하기 __6.2.2 MCTS 구현하기 6.3 DUCT(Decoupled Upper Confidence Tree) __6.3.1 DUCT의 특징과 동작: 동시에 두는 게임이라면 바로 이거! __6.3.2 DUCT 구현하기 7장 더 좋은 탐색을 하는 기법 7.1 예제 게임 소개: 벽이 있는 숫자 모으기 미로 게임 __7.1.1 벽이 있는 숫자 모으기 미로 게임 __7.1.2 벽이 있는 숫자 모으기 미로 구현하기 7.2 평가 함수 설계하기 __7.2.1 실제 기록 점수 이외의 후보 점수 추가하기 __7.2.2 실제 기록 점수 이외의 보조 기록 점수를 추가하는 방법 구현하기 7.3 다양성 확보 방침 __7.3.1 동일 게임판 제거하기 __7.3.2 동일 게임판 제거 구현하기 7.4 고속화 __7.4.1 다수의 비트열로 게임판 표현하기 __7.4.2 다수의 비트열로 게임판 표현 구현하기 __7.4.3 단일 비트열로 게임판 표현하기 __7.4.4 단일 비트열을 사용한 게임판 표현 구현하기 __7.4.5 복사 횟수 제어하기 __7.4.6 참조 카운트 방식으로 복사 횟수 제어 구현하기 8장 실제 게임에 응용하기 8.1 커넥트 포 게임을 플레이하는 AI 구현하기 __8.1.1 커넥트 포 게임 __8.1.2 커넥트 포 구현하기 __8.1.3 게임판 비트보드를 이용해서 고속화하기 __8.1.4 커넥트 포에 비트 연산을 적용해서 구현하기