게임 AI를 위한 탐색 알고리즘 입문

게임 AI를 위한 탐색 알고리즘 입문

"한빛미디어 서평단 <나는 리뷰어다> 활동을 위해서 책을 제공받아 작성된 서평입니다."

게임에서 말하는 AI와 탐색

대진 게임 AI를 구성하는 기술에는 탐색, 머신러닝, 규칙 기반 3종류의 기술 요소를 사용

이 책은 이러한 세 종류 기술 요소 중에서 탐색에 중점을 두고 설명

숫자 모으기 미로게임

숫자 모으기 게임규칙

	설명
플레이어 목적	게임이 종료할 때까지 높은 기록 점수를 얻습니다.
플레어어 수	1인
플레이어의 행동 타이밍	1턴에 1회
플레이어가 가능한 행동	각 턴마다 캐릭터(@)를 상하좌우 네 방향 중 어느 하나로 1칸 이동시킵니다. 가만히 있거나 게임판 밖으로 이동시키는 것은 불가능합니다.
게임 종료 조건	정해진 턴 수를 넘깁니다.
기타	캐릭터는 무작위로 초기 배치됩니다. 캐릭터가 이동한 곳에 점수가 있으면 해당 점수를 기록 점수에 더하고 그곳에 있던 점수는 사라집니다.

 

예 1에서 플레이어의 최종 기록 점수는 3, 이 점수가 최대가 되게 만드는 것이 게임 목적

예 2는 10

숫자 모으기 미로의 동작 예 1

숫자 모으기 미로의 동작 예 2

숫자 모으기 미로 구현하기

// Copyright [2022] <Copyright Eita Aoki (Thunder) >
#include <string>
#include <sstream>
#include <random>
#include <iostream>
// 좌표를 저장하는 구조체
struct Coord
{
    int y_;
    int x_;
    Coord(const int y = 0, const int x = 0) : y_(y), x_(x) {}
};

std::mt19937 mt_for_action(0); // 행동 선택용 난수 생성기 초기화

constexpr const int H = 3;  // 미로의 높이
constexpr const int W = 4;  // 미로의 너비
constexpr int END_TURN = 4; // 게임 종료 턴

// 1인 게임 예
// 1턴에 상하좌우 네 방향 중 하나로 1칸 이동한다.
// 바닥에 있는 점수를 차지하면 자신의 점수가 되고, 바닥의 점수는 사라진다.
// END_TURN 시점에 높은 점수를 얻는 것이 목적
class MazeState
{
private:
    static constexpr const int dx[4] = {1, -1, 0, 0}; // 오른쪽, 왼쪽, 아래쪽, 위쪽으로 이동하는 이동방향 x축 값
    static constexpr const int dy[4] = {0, 0, 1, -1}; // 오른쪽, 왼쪽, 아래쪽, 위쪽으로 이동하는 이동방향 y축 값

    int points_[H][W] = {}; // 바닥의 점수는 1~9 중 하나
    int turn_ = 0;          // 현재 턴

public:
    Coord character_ = Coord();
    int game_score_ = 0; // 게임에서 획득한 점수
    MazeState() {}

    // h*w 크기의 미로를 생성한다.
    MazeState(const int seed)
    {
        auto mt_for_construct = std::mt19937(seed); // 게임판 구성용 난수 생성기 초기화
        this->character_.y_ = mt_for_construct() % H;
        this->character_.x_ = mt_for_construct() % W;

        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++)
            {
                if (y == character_.y_ && x == character_.x_)
                {
                    continue;
                }
                this->points_[y][x] = mt_for_construct() % 10;
            }
    }

    // [모든 게임에서 구현] : 게임 종료 판정
    bool isDone() const
    {
        return this->turn_ == END_TURN;
    }

    // [모든 게임에서 구현] : 지정한 action으로 게임을 1턴 진행한다.
    void advance(const int action)
    {
        this->character_.x_ += dx[action];
        this->character_.y_ += dy[action];
        auto &point = this->points_[this->character_.y_][this->character_.x_];
        if (point > 0)
        {
            this->game_score_ += point;
            point = 0;
        }
        this->turn_++;
    }

    // [모든 게임에서 구현] : 현재 상황에서 플레이어가 가능한 행동을 모두 획득한다.
    std::vector<int> legalActions() const
    {
        std::vector<int> actions;
        for (int action = 0; action < 4; action++)
        {
            int ty = this->character_.y_ + dy[action];
            int tx = this->character_.x_ + dx[action];
            if (ty >= 0 && ty < H && tx >= 0 && tx < W)
            {
                actions.emplace_back(action);
            }
        }
        return actions;
    }

    // [필수는 아니지만 구현하면 편리] : 현재 게임 상황을 문자열로 만든다.
    std::string toString() const
    {
        std::stringstream ss;
        ss << "turn:\t" << this->turn_ << "\n";
        ss << "score:\t" << this->game_score_ << "\n";
        for (int h = 0; h < H; h++)
        {
            for (int w = 0; w < W; w++)
            {
                if (this->character_.y_ == h && this->character_.x_ == w)
                {
                    ss << '@';
                }
                else if (this->points_[h][w] > 0)
                {
                    ss << points_[h][w];
                }
                else
                {
                    ss << '.';
                }
            }
            ss << '\n';
        }

        return ss.str();
    }
};

미로를 푸는 AI 구현, 게임 진행

일단은 무작위로 이동하는 AI

using State = MazeState;

// 무작위로 행동을 결정한다.
int randomAction(const State &state)
{
    auto legal_actions = state.legalActions();
    return legal_actions[mt_for_action() % (legal_actions.size())];
}

// 시드를 지정해서 게임 상황을 표시하면서 AI에 플레이시킨다.
void playGame(const int seed)
{
    using std::cout;
    using std::endl;

    auto state = State(seed);
    cout << state.toString() << endl;
    while (!state.isDone())
    {
        state.advance(randomAction(state));
        cout << state.toString() << endl;
    }
}
int main()
{
    playGame(/*게임판 초기화 시드*/ 121321);
    return 0;
}

무작위 행동 선택의 플레이 결과

그리디 알고리즘(탐욕법)

그리디 알고리즘(Greedy algorithm)은 1 턴 후에 발생 가능한 모든 결과 중에서 가장 평가가 높은 결과를 내는 행동을 선택하는 방법

구현이 간단하고 평가 방법을 잘 만들면 일정 수준 이상의 효과를 기대할 수 있기 때문에 게임에서 가장 먼저 시도해 볼 만한 방법

 

점수 2,0,5,6 중에서 6이 가장 높은 점수이므로 6의 게임판으로 이동

이후 위치에서 선택 가능한 가장 높은 점수를 계속 선택해 총 4번을 이동

그리디 알고리즘의 선택: 1턴쨰

그리디 알고리즘의 선택: 2턴쨰

그리디 알고리즘의 선택: 3턴쨰

그리디 알고리즘의 선택: 4턴쨰

그리디 알고리즘 구현하기

// Copyright [2022] <Copyright Eita Aoki (Thunder) >
#include <string>
#include <sstream>
#include <random>
#include <iostream>
// 좌표를 저장하는 구조체
struct Coord
{
    int y_;
    int x_;
    Coord(const int y = 0, const int x = 0) : y_(y), x_(x) {}
};

std::mt19937 mt_for_action(0);                // 행동 선택용 난수 생성기 초기화
using ScoreType = int64_t;                    // 게임 평가 점수 자료형을 결정
constexpr const ScoreType INF = 1000000000LL; // 불가능한(무한) 점수의 예로 정의

constexpr const int H = 3;  // 미로의 높이
constexpr const int W = 4;  // 미로의 너비
constexpr int END_TURN = 4; // 게임 종료 턴

// 1인 게임 예
// 1턴에 상하좌우 네 방향 중 하나로 1칸 이동한다.
// 바닥에 있는 점수를 차지하면 자신의 점수가 되고, 바닥의 점수는 사라진다.
// END_TURN 시점에 높은 점수를 얻는 것이 목적
class MazeState
{
private:
    static constexpr const int dx[4] = {1, -1, 0, 0}; // 오른쪽, 왼쪽, 아래쪽, 위쪽으로 이동하는 이동방향 x축 값
    static constexpr const int dy[4] = {0, 0, 1, -1}; // 오른쪽, 왼쪽, 아래쪽, 위쪽으로 이동하는 이동방향 y축 값

    int points_[H][W] = {}; // 바닥의 점수는 1~9 중 하나
    int turn_ = 0;          // 현재 턴

public:
    Coord character_ = Coord();
    int game_score_ = 0;            // 게임에서 획득한 점수
    ScoreType evaluated_score_ = 0; // 탐색을 통해 확인한 점수
    MazeState() {}

    // h*w 크기의 미로를 생성한다.
    MazeState(const int seed)
    {
        auto mt_for_construct = std::mt19937(seed); // 게임판 구성용 난수 생성기 초기화
        this->character_.y_ = mt_for_construct() % H;
        this->character_.x_ = mt_for_construct() % W;

        for (int y = 0; y < H; y++)
            for (int x = 0; x < W; x++)
            {
                if (y == character_.y_ && x == character_.x_)
                {
                    continue;
                }
                this->points_[y][x] = mt_for_construct() % 10;
            }
    }

    // [모든 게임에서 구현] : 게임 종료 판정
    bool isDone() const
    {
        return this->turn_ == END_TURN;
    }
    // [모든 게임에서 구현] : 탐색용으로 게임판을 평가한다.
    void evaluateScore()
    {
        this->evaluated_score_ = this->game_score_; // 간단히 우선 기록 점수를 그대로 게임판의 평가로 사용
    }
    // [모든 게임에서 구현] : 지정한 action으로 게임을 1턴 진행한다.
    void advance(const int action)
    {
        this->character_.x_ += dx[action];
        this->character_.y_ += dy[action];
        auto &point = this->points_[this->character_.y_][this->character_.x_];
        if (point > 0)
        {
            this->game_score_ += point;
            point = 0;
        }
        this->turn_++;
    }

    // [모든 게임에서 구현] : 현재 상황에서 플레이어가 가능한 행동을 모두 획득한다.
    std::vector<int> legalActions() const
    {
        std::vector<int> actions;
        for (int action = 0; action < 4; action++)
        {
            int ty = this->character_.y_ + dy[action];
            int tx = this->character_.x_ + dx[action];
            if (ty >= 0 && ty < H && tx >= 0 && tx < W)
            {
                actions.emplace_back(action);
            }
        }
        return actions;
    }

    // [필수는 아니지만 구현하면 편리] : 현재 게임 상황을 문자열로 만든다.
    std::string toString() const
    {
        std::stringstream ss;
        ss << "turn:\t" << this->turn_ << "\n";
        ss << "score:\t" << this->game_score_ << "\n";
        for (int h = 0; h < H; h++)
        {
            for (int w = 0; w < W; w++)
            {
                if (this->character_.y_ == h && this->character_.x_ == w)
                {
                    ss << '@';
                }
                else if (this->points_[h][w] > 0)
                {
                    ss << points_[h][w];
                }
                else
                {
                    ss << '.';
                }
            }
            ss << '\n';
        }

        return ss.str();
    }
};

using State = MazeState;

// 무작위로 행동을 결정한다.
int randomAction(const State &state)
{
    auto legal_actions = state.legalActions();
    return legal_actions[mt_for_action() % (legal_actions.size())];
}

// 탐욕법으로 행동을 결정한다.
int greedyAction(const State &state)
{
    auto legal_actions = state.legalActions();
    ScoreType best_score = -INF; // 불가능한만큼 작은 값으로 최고 점수를 초기화
    int best_action = -1;        // 불가능한 행동으로 초기화
    for (const auto action : legal_actions)
    {
        State now_state = state;
        now_state.advance(action);
        now_state.evaluateScore();
        if (now_state.evaluated_score_ > best_score)
        {
            best_score = now_state.evaluated_score_;
            best_action = action;
        }
    }
    return best_action;
}

// 시드를 지정해서 게임 상황을 표시하면서 AI에 플레이시킨다.
void playGame(const int seed)
{
    using std::cout;
    using std::endl;

    auto state = State(seed);
    cout << state.toString() << endl;
    while (!state.isDone())
    {
        state.advance(greedyAction(state));
        cout << state.toString() << endl;
    }
}
int main()
{
    playGame(/*게임판 초기화 시드*/ 121321);
    return 0;
}