[AI][C#][오델로 AI] 2. DP로 오델로 AI를 만들자!

728x90

글에서 쓰이는 모든 코드는 제가 쓴 것이 아닙니다. 동계캠프를 진행하는 동안의 수업 자료입니다.

엄밀히 말하면 DP는 학습을 하지 않으므로, DP로 만드는 것은 AI보다는 프로그램에 가까울 테지만... 아무튼 AI 카테고리에 올리고 싶으니까 편의상 AI라고 말할 것이다. ㅎ_ㅎ

보드의 상태를 가치 함수의 키값으로 쓰고, 갱신을 위해 전 값과 오차를 구하하고, 적은 오차값을 구하기 위해 같은 패턴을 반복해나가는 게 다이나믹 프로그래밍인 이유라고 생각한다.

DP AI는 이런 기능으로 세분화해 개발했다.

가치함수 초기화
그리디 정책에 의한 학습
- 행동에 대한 최적의 기댓값 구하기
- 오차 구하기
학습을 토대로 다음 행동 반환

이 정도인데, 여기서 말하는 학습이란 AI가 강화 학습을 하는 게 아닌, 상태에서의 최적의 값을 그저 행동으로 저장하는 것을 학습으로 썼다.

1. 가치함수 초기화

(1) 게임 상태 초기화

오델로의 초기 상태를 바탕으로 가치 함수(키=상태, 값=보상)를 초기화할 것이다.

public GameState()
{
    // 초기상태
    BoardState = new int[,] { { 0, 0, 0, 0 }, { 0, 1, 2, 0 }, { 0, 2, 1, 0 }, { 0, 0, 0, 0 } };
    NextTurn = 1;   // 흑돌 차례

    int boardStateKey = 0;
    for (int i = 0; i <= GameParameters.BoardMaxIndex; i++) // 3진수
    {
        boardStateKey = boardStateKey * 3;
        boardStateKey = boardStateKey + BoardState[GetRowFromIndex(i), GetColFromIndex(i)];
    }

    BoardStateKey = boardStateKey * 3 + NextTurn; // 3진수 + 다음 턴
    GameWinner = 0;
    NumOfBlack = 2;
    NumOfWhite = 2;
}

1편에서 짜놓은 개요를 바탕으로 구체화했다.

판의 상태는 2차원 배열로 나타내주었지만, boardStateKey는 2차원 배열을 3진수로 변환한 값을 다시 10진수로 변환한 값이다. BoardStateKey는 보드의 상태를 담기도 하고, 현재 턴을 일의 자리숫자에 담았다.

(2) 모든 상태 구하기 + 가치함수 초기화

게임의 상태를 초기화해줬으니, 초기 보드판을 바탕으로 흑돌과 검은돌이 할 수 있는 액션, 즉 행동들을 시켜야한다. 또, 시킨 행동은 다음 상태를 불러오는데, 이를 보드의 상태. 즉 가치 함수의 키 값으로 사용해줄 것이다.

 public void InitializeValueFunction()
 {
     Console.Clear();
     Console.WriteLine("동적 프로그래밍 시작");
     Console.WriteLine("가치 함수 초기화");

     StateValueFunction.Clear();

     
     GameState gameState = new GameState();	// 초기 상태
     List<int> boardStateKeyList = new List<int>() { gameState.BoardStateKey };	// 게임 상태 후보 리스트

     // 모든 게임 상태에 대해서 반복
     while (true)
     {
         List<int> mergedChildStateList = new List<int>();

         foreach (int gameBoardKey in boardStateKeyList)
         {
             // 가치함수에 상태가 포함되어있지 않다면 넣어준다
             if (!StateValueFunction.ContainsKey(gameBoardKey))
             {
                 StateValueFunction.Add(gameBoardKey, 0.0f);
                 // 상태 생성
                 GameState processingGameState = new GameState(gameBoardKey);

                 // 끝나지 않는다면
                 if (!processingGameState.IsFinalState())
                 {
                     List<int> childStateList = new List<int>();

                     // 행동을 모두 실행
                     for (int i = GameParameters.ActionMinIndex; i <= GameParameters.ActionMaxIndex; i++)
                     {
                         // 행동할 수 있다면
                         if (processingGameState.IsValidMove(i))
                         {
                             GameState nextState = processingGameState.GetNextState(i);  // 행동을 통해 다음 상태 만들기
                             childStateList.Add(nextState.BoardStateKey);                // 후보리스트에 넣어줌
                         }
                     }

                     // 아무 행동도 할 수 없었다면
                     if (childStateList.Count == 0)
                     {
                         GameState nextState = processingGameState.GetNextState(0);  // 패스
                         childStateList.Add(nextState.BoardStateKey);
                     }

                     // 임시로 만든 후보 리스트의 상태 중에
                     // 자식 상태 리스트에 포함되어있지 않은 상태를 자식 상태에 추가
                     mergedChildStateList.AddRange(childStateList.Where(e => !mergedChildStateList.Contains(e)));
                 }
             }
         }
         if (mergedChildStateList.Count == 0)
             break;
         else
             boardStateKeyList = new List<int>(mergedChildStateList);
     }

     Console.WriteLine(Environment.NewLine);
     Console.WriteLine($"가치 함수 초기화 완료, 상태 {StateValueFunction.Count} 개");
     Console.WriteLine(Environment.NewLine);
     Console.Write("아무 키나 누르세요:");
     Console.ReadLine();
 }

많이 긴 코드이지만, 이해하기 어려운 코드는 아니다.

이렇게 가지처럼 뻗어나가는 행동들과 그에 의해서 생기는 다음 상태, 또 그 상태에서 할 수 있는 행동들과... 를 반복하다 보면 모든 경우의 수를 포함한 키 값들을 구할 수 있게 된다!

러시아 장기를 DP로 구현할 때는, 보드의 모든 경우의 수를 구할 수 있었다. 하지만, 오델로는 놓는 말과 상태가 확확 바뀌는 게임인지라, 모든 경우의 수를 이렇게 구하지 않으면 구할 수 없다고 선생님께서 말씀하신 것 같다.

2. 그리디 정책에 의한 학습

이제, 그리디 정책에 의해 DP AI를 학습 아닌 학습을 시킬 것이다. 그리디는 순간의 최적해를 선택하는 알고리즘이다. 따라서, AI를 학습시킬 때도 현재 상태에서의 기댓값들 중에 최적의 값을 선택할 것이다.

그럼, 학습의 진행 과정을 보자.

1. 현재 상태에서 할 수 있는 행동, 그에 따른 상태를 구한다.

List<float> actionExpectationList = new List<float>();

for (int i = GameParameters.ActionMinIndex; i <= GameParameters.ActionMaxIndex; i++)
{
    // 움직일 수 있다면 다음 스테이지로
    if (gameState.IsValidMove(i))
    {
        GameState nextState = gameState.GetNextState(i);
        float reward = nextState.GetReward();

        float actionExpectation = reward + DiscountFactor * StateValueFunction[nextState.BoardStateKey];

        actionExpectationList.Add(actionExpectation);
    }
}

// 패스
if (actionExpectationList.Count == 0)
{
    GameState nextState = gameState.GetNextState(0);
    float reward = nextState.GetReward();

    float actionExpectation = reward + DiscountFactor * StateValueFunction[nextState.BoardStateKey];

    actionExpectationList.Add(actionExpectation);
}

돌을 놓는 행동 혹은 패스하는 행동의 기댓값을 넣어주었다.

또, 구한 상태에 대한 보상 + 감가율 * 갱신 전 상태의 가치 함수 값을 기댓값 복합데이터에 넣고, 그 중 최적의 값을 가치 함수에 업데이트할 값으로 설정한다. 이 값은 후에 가치 함수에 업데이트할 값이다!

그리디 정책이기 때문에, 현재 상태에서 최적의 기댓값으로 가치함수를 갱신해줄 것이다.

if (gameState.NextTurn == 1)
{
    return actionExpectationList.Max();
}
else if (gameState.NextTurn == 2)
{
    return actionExpectationList.Min();
}

1편에서 말했던 것처럼, 보상 체계는 검은 돌이 이겼을 시 +100, 졌을시 -100이 보상으로 나오게 된다.

따라서, 위처럼 NextTurn이 1(검은 돌)일 때는 Max값, 그렇지 않을 때는 Min값을 반환하는 것을 볼 수 있다.

2. 원래 있던 가치 함수의 값과 구한 값의 오차를 계산한다.

float updatedValue = UpdateValueFunction(valueFunctionEntry.Key);           // 가치 함수 업데이트 계산
float updatedAmount = Math.Abs(valueFunctionEntry.Value - updatedValue);    // 오차
nextStateValueFunction[valueFunctionEntry.Key] = updatedValue;              // 갱신

// 그리디 정책에 대한 값 추출
valueFunctionUpdateAmount = Math.Max(valueFunctionUpdateAmount, updatedAmount);

기댓값(갱신할 값)과 보상값(갱신 전 값) 사이의 오차를 계산한다. 이는 반복 학습을 통해 오차를 줄이고자 하는 작업이다.

3. 1~2을 매 상태마다 반복한다.

에서 가치 함수 초기화로부터 구한 모든 키 값(상태)에 대해 이를 반복해준다. DP는 입력에 따라 계산된 출력밖에 하지 못하므로, 모든 키 값에 따라 반복해야 한다.

foreach (KeyValuePair<int, float> valueFunctionEntry in StateValueFunction)
{
    float updatedValue = UpdateValueFunction(valueFunctionEntry.Key);           // 가치 함수 업데이트 계산
    float updatedAmount = Math.Abs(valueFunctionEntry.Value - updatedValue);    // 오차
    nextStateValueFunction[valueFunctionEntry.Key] = updatedValue;              // 갱신

    // 그리디 정책에 대한 값 추출
    valueFunctionUpdateAmount = Math.Max(valueFunctionUpdateAmount, updatedAmount);
}

5. 반복할 동안, 위에서 구한 오차가 N 이하이면 학습을 멈춘다!

int loopCount = 0;
bool terminateLoop = false;

while (!terminateLoop)
{
    // 업데이트가 되는 가치 함수값을 임시로 저장
    Dictionary<int, float> nextStateValueFunction = new Dictionary<int, float>();
    float valueFunctionUpdateAmount = 0.0f;

    foreach (KeyValuePair<int, float> valueFunctionEntry in StateValueFunction)
    {
        float updatedValue = UpdateValueFunction(valueFunctionEntry.Key);           // 가치 함수 업데이트 계산
        float updatedAmount = Math.Abs(valueFunctionEntry.Value - updatedValue);    // 오차
        nextStateValueFunction[valueFunctionEntry.Key] = updatedValue;              // 갱신

        // 그리디 정책에 대한 값 추출
        valueFunctionUpdateAmount = Math.Max(valueFunctionUpdateAmount, updatedAmount);
    }

    StateValueFunction = new Dictionary<int, float>(nextStateValueFunction);

    Console.WriteLine($"동적 프로그래밍 {loopCount++}회 수행, 업데이트 오차 {valueFunctionUpdateAmount}");

    // 오차가 0.01 이하이면 종료
    if (valueFunctionUpdateAmount < 0.01f)
        terminateLoop = true;
}

전체 코드이다!

이를 실행하게 되면, 오차가 100에서부터 0까지 줄며 프로그램은 나올 수 있는 상태에 대해 학습을 하게 된다!

선생님께서 만든 프로그램(AI...)과 게임을 할 수 있게 구현해주셨다!

우와!! 내가 구현한 것은 아니지만... 코드를 이해하고 AI 학습에 대한 감을 잡았다는 생각에 기분이 참 좋다.

그래도, 아직은 부족한 점이 정말 많다... 정책이 뭔지, 감가율이 뭔지... 정말 잘 모르겠다. 수업 시간에 배운 단어들과 기억나는 내용을 활용해서 적어봤지만, 아직 더 연구가 필요할 것 같다.

깃허브에 전체 코드를 올렸다. 코드는 전부 선생님이 짜신 것!

GitHub - minyoung529/Winter_AI

Contribute to minyoung529/Winter_AI development by creating an account on GitHub.

github.com

다음 글은 Q-Learning을 이용해 진짜 학습하는 AI를 만들 생각이다!