인공지능과 게임 - 체스와 체커

    인공지능 연구 초기부터 다루어진 게임 프로그램들에 대해 알아봅니다. 체스와 체커에서 시작하여 장기와 바둑으로 이어지는 게임프로그램과 관련된 인공지능의 기초 기술들의 연구를 중심으로 공부합니다.

1. 탐색과 휴리스틱

    초기 게임 연구에서 자주 다루어지던 체스와 체커에는 다음과 같은 공통된 특징이 있습니다. 

    1) 두 명이 대전한다.

    2) 한쪽이 유리해지면 다른 한쪽은 불리해진다.

    3) 플레이어는 게임에 관한 모든 정보를 알 수 있다.

 

   이와 같은 게임을 제로섬게임(zero-sum)이라고 합니다. 게다가 체스나 체커는 주사위와 같은 확률적 요소가 없는 확정적인 게임입니다. 이러한 특징은 바둑이나 장기에서도 공통적인 사항입니다. 확정적인 제로섬게임은 원리적으로는 가능한 모든 순서를 탐색하여 최적의 게임 전략을 구현하는 것입니다. 따라서 두 명의 플레이어가 각각 최선책을 선택해서 게임을 하면 결과는 어느 한 선수의 승리나 패배 또는 무승부가 될 것입니다. 

1.1 게임 트리(game tree)

    체스나 장기 등 두 플레이어가 번갈아서 수를 쓰는 게임에 있어서 AI 플레이어(컴퓨터)는 주로 게임트리라는 개념을 사용합니다.

게임 트리 (위키백과)

 

    게임트리는 각각의 노드가 게임의 한 상태(말들의 위치)를 의미하며, 각 노드의 자식 노드들은 한 수 이후에 도달할 수 있는 다음 위치들을 의미하는 특별한 트리(tree)입니다. 우선 게임 트리의 용어를 정리하면 다음과 같습니다.

• 뿌리는 게임이 시작되는 점(초기상태)을 말한다.
• 가지(branch)는 플레이어가 선택하는 각각의 의사결정을 나타내며, 게임 트리에서 실선으로 표시한다.
• 노드(node) 또는 마디는 경기자 중 누군가가 의사결정을 해야 하는 상태 또는 의사결정을 마치고 보수가 주어지는 상태를 표현한다. 게임 트리에서 점으로 표시된다.

    게임의 AI 플레이어는 게임트리를 이용해서 다음 수순을 미리 예측하고 가장 유리한 수를 찾습니다. 확정적인 제로섬게임은 가능한 모든 순서를 탐색하여 최적의 게임 전략을 구현하는 것이 원칙적이나, 체스나 체커처럼 보드의 수가 방대하고 매우 복잡한 게임의 경우 전체적인 게임트리를 모두 탐색하는 것은 불가능하기 때문에 전체가 아닌 앞으로 진행될 몇 수에 대한 부분적인 게임트리를 가지고 최적의 수를 찾는 것입니다.

1.2 휴리스틱 함수(heuristic function) 

    게임에서 가장 유리한 보드를 선택하기 위해서는 탐색의 한계 내에서 나타난 게임 도중의 보드를 평가해 점수를 주고 가장 고득점인 노드를 선택합니다. 이렇게 점수를 평가하는 함수를 평가함수(evaluation function) 또는 휴리스틱 함수(heuristic function)라고 합니다.

    휴리스틱 함수란 선험적 지식에 근거한 평가방법을 의미합니다. 휴리스틱 함수는 게임에 따라 다르지만 체스의 경우에는 자신이 게임에서 이기는 체크메이트가 되는 노드, 즉 상대의 킹이 도망갈 곳이 없는 상태에 대응하는 노드에는 가장 높은 평가값을 줍니다. 또는 적의 유력한 말을 잡을 수 있는 상태에서는 상대말의 가치에 적합한 점수를 줍니다. 

    보드 평가에서 착수를 선택하기 위해 평가값을 주는 휴리스틱 함수의 구성 방법은 AI 플레이어의 우열과 직결됩니다. 초기 AI 게임 플레이어에서는 인간이 경험적으로 휴리스틱 함수를 구성했기 때문에 시스템을 만드는 사람의 게임에 대한 이해도가 AI 게임 플레이어의 강약과 직결되었습니다. 그러다가 머신러닝을 이용해 휴리스틱 함수를 구성하는 방법에 대한 연구가 발전하면서 프로그램이 자동으로 휴리스틱 함수를 구성할 수 있게 되었습니다. 

    최근에는 딥러닝을 이용하여 대규모 데이터에서 정밀한 휴리스틱 함수를 구성하고 인간을 초월한 실력을 갖춘 AI 게임 플레이어가 만들어지고 있습니다.

1.3 미니맥스법(minimax method)과 알파베타 가지치기(Alpha-beta pruning)

    서브 트리의 탐색에서는 더욱 고속으로 탐색하는 알고리즘이 요구됩니다. 알파-베타 가지치기(Alpha-beta pruning)라는 방법은 오래전부터 이용되던 기본 알고리즘으로 미니맥스법(minimax method)이라 불리는 탐색 알고리즘을 효율화한 알고리즘입니다.

   

알파-베타 가지치기법을 적용한 게임트리의 예 (출처. 인공지능개발자보임)

    미니맥스법에 의한 선택은 자신의 순서일 때는 평갓값이 가장 높은 것을 고르고, 상대의 순서일 때는 평갓값이 가장 낮을 것을 고른다는 개념을 따른 것입니다. 그림에서 나타낸 것처럼  잎노드에서 순서대로 가지를 고르면 처음에 어떤 가지를 선택할지 결정할 수 있습니다. 이와 같이 최솟값과 최댓값을 번갈아 가면서 선택하기 때문에 이 알고리즘을 미니맥스법이라고 부릅니다.

    미니맥스법을 이용하면 최적의 착수를 선택할 수 있습니다. 그러나 알고리즘을 그대로 구현하면 불필요한 가지들이 생겨납니다. 이런 가지들은 더 이상 탐색을 할 필요가 없는 것들이기 때문에 탐색의 대상에서 제외하여 탐색을 더욱 효율적으로 만드는 것이  알파-베타 가지치기(pruning)입니다. 미니맥스법의 불필요한 부분을 줄이기 위해 가지치기(pruning)를 하는 것입니다.

2. 딥블루(Deep Blue)

     딥블루(Deep Blue)는 1997년에 인간 세계 의 챔피언을 무너뜨린 IBM이 개발한 체스 전용 컴퓨터입니다. 딥블루는 지금까지 이야기한  탐색으로 대표되는 소프트웨어 기술만이 아닌 탐색을 고속화하기 위한 전용 하드웨어까지 이용한 공격적인 탐색에 기반을 둔 시스템입니다. 

    탐색에 기반을 둔 AI 플레이어의 능력을 향상하려면 가능한 탐색 범위를 확장할 필요가 있습니다. 그래서 딥블루에서는 고속화를 위해 체스라는 문제에 특화된 하드웨어 체스 칩(chess chip)을 새롭게 개발하여 탐색과 평가를 고속으로 실행시켰습니다. 딥블루는 그 자체가 하나의 시스템으로 30 노드의 컴퓨터 시스템을 갖춘 병렬 컴퓨터입니다. 각각의 노드에 16개의 체스칩을 심어 시스템 전체로 치면 480개의 체스 칩을 사용해서 병렬처리하는 것입니다.

    이처럼 딥블루는 소프트웨어와 하드웨어 양쪽의 기술을 이용해 체스라는 특수한 분야를 효율적으로 다루는 시스템으로 구성된 것입니다. 병렬처리를 활용한 탐색에 기반을 둔 디블루 시스템은 인간이 체스 게임을 할 경우의 정보처리와는 방법이 전혀 다른 것입니다. 딥블루가 내부구조나 처리기구가 인간과는 완전히 다르지만, 약한 AI의 입장에서는 시스템의 동작이 지적인 전형적인 인공지능 시스템이라고 할 수 있겠습니다.

    (약한 AI의 개념에 대해서는 다음에 다시 공부하도록 하겠습니다)

 

2023.06.11 - [인공지능(AI; Artificial Intelligence)] - 에이전트와 강화학습 (4) - 강화학습