GA - 미로 속 슬라임 - 개요

"찾았다"

어느 병사의 외침에 다른 병사들이 달려왔다. 그들 한가운데에는 슬라임 한마리가 반투명한 몸체를 흔들며 서 있었다. 병사들은 슬라임을 둘러싸고 무기를 슬라임에게 향했다.

그것은 창 같지만 창이 아니었다. 창날이 있어야 할 곳에 넓적한 판자가 달려 있었다.

"시작하십시오"

대장이 옆에 있는 노마법사에게 말하자, 다섯명의 젊은 마법사들이 슬라임을 중심으로 오망성을 이루었다.

"자, 모두들 주의하시오. 저놈이 포위망을 뚫으면 안됩니다"

노마법사의 명령에 이어 젊은 마법사들은 주문을 읇기 시작했다. 갑자기 슬라임이 붉은 빛에 휩싸이는 듯 싶더니 몸부림을 쳤다. 그와 함께 병사들의 판자에서는 룬문자가 빛나기 시작했다. 그 판자에 닿은 슬라임은 감전이라도 된 듯 물러났다. 하지만 그와 함께 병사들 역시 몇걸음씩 뒤로 물러나곤 했다.

"힘내라, 밀리면 안된다!"

주문이 끝나갈 동안 병사들은 슬라임을 버티고 있었다. 마침내 붉은 빛이 잦아들면서 슬라임은 주먹만한 크기로 줄어들었다. 노마법사는 그제서야 유리병을 꺼내 슬라임을 넣었다.

"됐다. 성공이다."

"잘 됐다니 다행이군요. 그런데 그 슬라임을 뭐에 쓰려고 잡는 겁니까?

"보시겠습니까?"

대장과 함께 텐트로 돌아온 노마법사는 탁자 위의 천을 걷었다. 그곳에는 다음과 같은 미로가 있었다.

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @
@ S @           @           @
@   @   @ @ @   @ @ @     @ @
@       @       @           @
@ @ @ @ @   @ @       @     @
@           @   @ @ @       @
@   @ @ @ @ @       @   @ @ @
@   @           @ @ @       @
@   @   @ @ @       @ @     @
@   @   @         @         @
@       @     @ @     @     @
@ @ @ @     @       @       @
@   @       @   @ @     @ @ @
@               @         E @
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @

노마법사는 슬라임을 왼쪽 위에 넣고는 뚜껑을 닫았다. 그리고 오른쪽 아래에 있는 문을 열었다. 노마법사가 잠시 슬라임에게 주문을 걸자 슬라임은 미로를 돌아다니기 시작했다

"지금 저 슬라임은 자기 주위에 장애물이 있는지 없는지와, 출구의 방향만을 알 수 있습니다. 그것만으로 이 미로를 빠져나와야 합니다. 조금이라도 미로를 더 잘 찾는 슬라임들만 골라서 번식시키면 마침내는 미로를 빠져나오는 슬라임이 만들어질 겁니다. 저는 그런 슬라임을 만들려는 것입니다."

"호오.. 그래요? 그런데 미로찾는 슬라임은 뭐에 쓰실려구요?"

"예? 뭐에 쓸 거냐구요? 저... 그러니까... 글쎄요... 어디에 쓰면 좋을까요?"

1. 유전자 설계
다른 것도 마찬가지지만, 일반적으로 유전자는 어떤 상황에서 어떻게 행동할까로 정의하는 것이 쉽습니다.

1.1 상황패턴
위에서도 말했지만 슬라임이 알 수 있는 것은 동서남북에 장애물이 있는가와 출구의 방향입니다.
슬라임의 현 상황을 묘사하기 위해서는 8개의 숫자가 필요합니다. 만약 윗 그림의 슬라임이 S위치에 있다면

1101 1010

이 될 것입니다. 이때 앞 4자리는 동서남북의 장애물 유무(동, 서, 북쪽에 장애물이 있고 남쪽에는 없다), 뒤 4자리는 출구가 동서남북 어느 쪽에 있는지(출구는 동남쪽이 있음)를 의미합니다.

1.2 행동패턴
다음에는 이 슬라임이 어떻게 행동할까(어떤 방향으로 움직일까)입니다. 간단히 하자면, 동서남북 중 어느쪽으로 갈지만 묘사하면 됩니다. 그러므로 오델로의 경우와 마찬가지로 다음과 같은 상황과 행동의 묶음을 유전자로 할 수 있습니다.

(1101 1010 - S)

(1001 1101 - E)

(0011 1000 - N)

...

즉, 슬라임이 출발점에 있다면 그 슬라임은 남쪽으로 이동하게 될 것입니다.

그러나 만약 이 슬라임이 다음과 같이

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @
@   @           @           @
@   @   @ @ @   @ @ @     @ @
@       @       @           @
@ @ @ @ @   @ @       @     @
@           @   @ @ @       @
@   @ @ @ @ @       @   @ @ @
@   @           @ @ @       @
@   @   @ @ @       @ @     @
@   @   @         @         @
@       @     @ @     @     @
@ @ @ @     @       @       @
@   @       @   @ @     @ @ @
@               @       S E @
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @

출구 바로 앞까지 도착했다면 어떻게 될까요? 이때의 상황은 0011 1000이며, 유전자 묶음에서의 행동은 N, 북쪽으로 이동하는 것입니다. 결국 이 슬라임은 출구 바로 앞에서 좌절하겠죠.
그러므로 여기서는 행동패턴은 단일한 방향이 아닌 10% 단위의 확률로 나타내기로 했습니다. 이를테면

(0011 1000 - ENNENENNEW)

와 같이 할 수 있습니다. 여기서 E가 3개, W가 2개, N이 5개이므로 이 경우에는 동쪽으로 갈 확률 30%, 북쪽 50%, 서쪽 20%, 남쪽으로 갈 일은 없게 되겠죠. 이 슬라임은 30%확률로 동쪽으로 갈 것이며 목적지에 도착할 것입니다(물론 20% 확률로 서쪽으로 가겠지만, 그래도 목적지에 도착할 가능성이 0%는 아닙니다).

2. 미로찾기
전체적으로, 이 슬라임은 오델로와 비슷한 루틴을 가지고 있습니다. 각 슬라임은 최초에 아무것도 없는 상태에서 시작하며, 자신이 있는 위치에서 현재 상태를 감지, 유전자리스트에서 유전자를 찾습니다.
다음 함수는 현 위치에서 슬라임이 어느 위치로 이동할지 생각하는 함수입니다.

function SlimeThink(slime, maze)

   // 슬라임 동서남북의 블럭정보 얻기

   curstate.detect.EastBlock := maze.IsBlock(slime.LocX + 1, slime.LocY)

   curstate.detect.WestBlock := maze.IsBlock(slime.LocX - 1, slime.LocY)

   curstate.detect.SouthBlock := maze.IsBlock(slime.LocX, slime.LocY + 1)

   curstate.detect.NorthBlock := maze.IsBlock(slime.LocX, slime.LocY - 1)

   // 나갈 입구의 방향 찾기

   curstate.detect.ExitEast := maze.IsExitEast(slime.LocX, slime.LocY)

   curstate.detect.ExitWest := maze.IsExitWest(slime.LocX, slime.LocY)

   curstate.detect.ExitSouth := maze.IsExitSouth(slime.LocX, slime.LocY)

   curstate.detect.ExitNorth := maze.IsExitNorth(slime.LocX, slime.LocY)

   // GeneList(유전자들의 묶음)에서 curstate 찾기

   fnd := slimt.GeneList.Find(curstat)

   if fnd == nil then // 처음 만나는 상황

      // effect부분을 랜덤으로 만듦

      for k := 0, 10 do

         curstate.effect[k] = Random("EWSN") // EWSN 중에서 하나 선택

      end

      slime.GeneList.Append(curstate) // 현재 상황 추가

      fnd = curstate

   end

   // 여기까지 해서 fnd에는 현재상황에 맞는 유전자가 들어있음

   return fnd.effect[Random(0, 9)]

end

최초에 슬라임을 초기위치(1, 1)에 넣은 후 SlimeThink()를 실행, 미로를 진행하게 됩니다.

procedure MazeProcess(slime, maze)

   // 슬라임을 출발점에 세움

   slime.LocX := 1

   slime.LocY := 1

   // 미로 안에서 슬라임 움직임

   for k := 0, 900 do // 미로 안에서 슬라임이 움직이는 횟수

               // 미로가 클수록 커져야 함

      // 어디로 움직일지 생각

      movedirect = SlimeThink(slime, maze)

      // 이동할 위치

      if movedirect == 'E' then

         newx := slime.LocX + 1

         newy := slime.LocY

      elseif movedirect == 'W' then

         newx := slime.LocX - 1

         newy := slime.LocY

      elseif movedirect == 'S' then

         newx := slime.LocX

         newy := slime.LocY + 1

      elseif movedirect == 'N' then

         newx := slime.LocX

         newy := slime.LocY - 1

      end

      // 이동한 결과 계산

      if maze.IsBlock(newx, newy) then // 블럭에 충돌

         slime.Fitness := slime.Fitness - 10 // 적응도 감소

      else // 충돌하지 않을 경우

         slime.LocX := newx

         slime.LocY := newy

         slime.Fitness := slime.Fitness - 1 // 적응도 감소

         // 목적지에 도착했나?

         if maze.IsGoal(slime.LocX, slime.LocY) then

            slime.Fitness := slime.Fitness + 1000 // 적응도 대폭 증가

            break // for 루프 탈출

         end

      end

   end

end

여기서 충돌하지 않고 이동했을 때도 적응도를 감소시키는 것은, 목적지에 빨리 도달한 슬라임에게 적응도를 높여주기 위함입니다.
이런 식으로 각각의 슬라임은 저 미로를 100회씩 돌게 됩니다.

procedure MainRoutine

   for generation := 0, 100 do

      for k := 0, 4096 do

         SlimeList[k].Fitness := 0

         for m := 0, 100 do

            MazeProcess(SlimeList[k], Maze)

         end

      end

      Rebirth Next  Generation

   end

end