게임 AI를 위한 탐색 알고리즘 입문 : 트리 탐색과 메타 휴리스틱으로 완성하는 최적화

아오키에이타

저자:아오키에이타
현재HEROZ주식회사에서게임AI개발을전문으로하고있습니다.프로그래밍대회에서는‘thunder’라는닉네임으로활동하며,매년열리는IEEEConferenceonGames에서개최되는게임AI경쟁대회에서7회우승한경력이있습니다.그중에서특히FightingGameAICompetition에서4연패를달성했습니다.또한,Qiita에는이책의기반이된‘세계4연패AI엔지니어가제로부터알려주는게임트리탐색입문’이라는글을기고하는등탐색알고리즘을널리알리고자힘쓰고있습니다.

역자:서수환
일본에서IT시스템을설계,개발하는엔지니어다.귀찮은일이생기면대신해줄무언가를찾다가없으면만드는게취미.또뭐하며놀까늘고민한다.

1장게임과탐색의세계
1.1게임AI와탐색
__1.1.1게임에서말하는AI와탐색
__1.1.2게임종류와탐색알고리즘
1.2게임에서탐색의매력
__1.2.1개인게임개발을한다면탐색!
__1.2.2대규모상업게임개발에서도탐색!
__1.2.3다양한프로그래밍대회에서이기기위한비장의무기

2장개발환경준비
2.1WSL(WindowsSubsystemforLinux)설치방법
__2.1.1WSL동작확인
__2.1.2CPU가상화기능확인
__2.1.3바이오스/UEFI에서가상화기능활성화
__2.1.4배포판설정
__2.1.5패키지업데이트
__2.1.6C++개발환경설치하기

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.4Chokudai탐색
__3.4.1Chokudai탐색의특징과동작:다양성을자동으로확보!간편하고초보자에게추천!
__3.4.2Chokudai탐색구현하기

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.6MCTS몬테카를로트리탐색
__5.6.1MCTS의특징과동작:적을얕보지말라!강자대결시뮬레이션
__5.6.2MCTS구현하기
5.7Thunder탐색
__5.7.1Thunder탐색의특징과동작:필자가발명!게임판평가를이용해서유리한노드를탐색한다!
__5.7.2Thunder탐색구현하기
COLUMNThunder탐색은어떻게만들어졌나?


6장동시에두는2인게임에서사용하고싶은탐색알고리즘
6.1예제게임소개:동시에두는숫자모으기미로게임
__6.1.1동시에두는숫자모으기미로게임
__6.1.2동시에두는숫자모으기미로구현하기
6.2교대로두는게임용알고리즘적용
__6.2.1순수몬테카를로탐색구현하기
__6.2.2MCTS구현하기
6.3DUCT(DecoupledUpperConfidenceTree)
__6.3.1DUCT의특징과동작:동시에두는게임이라면바로이거!
__6.3.2DUCT구현하기


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커넥트포에비트연산을적용해서구현하기

게임AI에빠질수없는탐색알고리즘의이론부터실전게임적용까지
*실전AI게임구현을위한C++기반예제코드제공

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

이책은게임AI에빠질수없는핵심중하나인탐색알고리즘의기본개념을소개하면서,게임유형에따라어울리는탐색알고리즘을살펴봅니다.여러게임에적용할수있는알고리즘뿐만아니라여러대회에서우승했던저자가직접개발한알고리즘도함께알아봅니다.또한C++기반의예제코드는주석을통해친절하게설명되어있으며,COLUMN과POINT구성을통해입문자들도이해하기쉽게구성했습니다.추가로실전에서사용가능한템플릿코드도추가로제공하여게임AI개발에필요한이론과노하우를체계적으로전달합니다.