초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

본 논문에서는 오목을 두는 지능적 프로그램을 설계하고 구현하였다. 규칙은 렌주 룰(renju rule)을 기준으로 하였으며, $15{\times}15$ 게임 판에서 오목을 둔다. 초기에는 문제 분석을 통하여 분석된 가중치로 판단을 하여 판단을 하여 게임을 진행하도록 하였으나, 반복된 수행의 경험적 판단을 통하여 얻은 정보로 여러 차례 수정하며 고정된 가중치를 구성하고, 이 가중치를 게임에서 돌을 놓을 때 평가 기준으로 삼도록 하였으며, 최소-최대 게임 트리(min-max game tree)를 이용하여 상대가 있는 게임을 수행할 수 있도록 하였다. 또한 프로그램 자신에게 유리한 수를 찾기 위한 탐색에서 무의미한 노드들의 전개를 줄여 제한된 시간안에 좋은 수를 찾을 수 있도록 알파 베타 가지치기(alpha-beta pruning)를 사용하도록 프로그램을 구현하였다. 이렇게 구현된 오목 프로그램은 게임을 본 프로그램과 게임 하기 원하는 주변의 일반인들에게 90% 이상의 승률을 보이고 있었다.

본 논문에서는 오목을 두는 지능적 프로그램을 설계하고 구현하였다. 규칙은 렌주 룰(renju rule)을 기준으로 하였으며, $15{\times}15$ 게임 판에서 오목을 둔다. 초기에는 문제 분석을 통하여 분석된 가중치로 판단을 하여 판단을 하여 게임을 진행하도록 하였으나, 반복된 수행의 경험적 판단을 통하여 얻은 정보로 여러 차례 수정하며 고정된 가중치를 구성하고, 이 가중치를 게임에서 돌을 놓을 때 평가 기준으로 삼도록 하였으며, 최소-최대 게임 트리(min-max game tree)를 이용하여 상대가 있는 게임을 수행할 수 있도록 하였다. 또한 프로그램 자신에게 유리한 수를 찾기 위한 탐색에서 무의미한 노드들의 전개를 줄여 제한된 시간안에 좋은 수를 찾을 수 있도록 알파 베타 가지치기(alpha-beta pruning)를 사용하도록 프로그램을 구현하였다. 이렇게 구현된 오목 프로그램은 게임을 본 프로그램과 게임 하기 원하는 주변의 일반인들에게 90% 이상의 승률을 보이고 있었다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 논문에서는 오목을 두는 지능적 프로그램을 설계하고 구현하였다. 규칙은 렌주 룰(renju rule)을 기준으로 하였으며, 15 x 15 게임판에서 오목을 둔다.
• 본 연구에서는 오목 프로그램을 구현하였다. 평가를 위한 트리의 깊이는 3으로 하였으며, 트리의 깊이를 더 추가할 경우 메모리에 대한 압박이 있으며 연산 량 증가로 인해 한 수를 두는 시간이 더 길어졌다.

제안 방법

• 게임에 적용한 패턴에 대한 가중치는 고정 가중치를 적용하였으며, 오목을 만들기 위하여 분석하는 과정에서 만든 초기 값을 이용하여 초기 버전의 프로그램을 제작하고 제작된 프로그램으로 게임을 수행하면서 나타난 현상을 나름대로 분석하여 경험과 판단을 바탕으로 수정하여 아래와 같이 패턴들에 대한 가중치를 만들었다.
• 규칙은 렌주 룰(renju rule)을 기준으로 하였으며, 15 x 15 게임판에서 오목을 둔다. 구현된 프로그램은 초기에는 문제 분석을 통하여 분석된 가중치로 판단을 하여 게임을 진행하도록 하였으나, 반복된 수행의 경험적 판단을 통하여 얻은 정보로 여러 차례 수정하며 고정된 가중치를 구성하고, 이 가중치를 게임에서 돌을 놓을 때 평가 기준으로 삼도록 하였으며, 최소-최대 게임 트리(min-max game tree)를 이용하여 상대가 있는 게임을 수행할 수 있도록 하였다. 또한 프로그램 자신에게 유리한 수를 찾기 위한 탐색에서 무의미한 노드들의 전개를 줄여 제한된 시간 안에 좋은 수를 찾을 수 있도록 알파 베타 가지치기(alpha-beta pruning)를 사용하도록 프로그램을 구현하였다.
• 구현된 프로그램은 초기에는 문제 분석을 통하여 분석된 가중치로 판단을 하여 게임을 진행하도록 하였으나, 반복된 수행의 경험적 판단을 통하여 얻은 정보로 여러 차례 수정하며 고정된 가중치를 구성하고, 이 가중치를 게임에서 돌을 놓을 때 평가 기준으로 삼도록 하였으며, 최소-최대 게임 트리(min-max game tree)를 이용하여 상대가 있는 게임을 수행할 수 있도록 하였다. 또한 프로그램 자신에게 유리한 수를 찾기 위한 탐색에서 무의미한 노드들의 전개를 줄여 제한된 시간 안에 좋은 수를 찾을 수 있도록 알파 베타 가지치기(alpha-beta pruning)를 사용하도록 프로그램을 구현하였다.
• 따라서 좀 더 깊이 보려면 전개할 필요가 없는 노드들을 전개하지 않는 전략이 필요하다. 이를 위해 알파-베타 가지치기를 적용하였다. 이 방법은 깊이 우선 탐색을 수행하되 지금까지 나온 값들을 참고하여 더 전개할 필요가 없을 때 전개를 그만두는 가지치는 방법이다.
• 이럴 때 사용하는 방법이 최소-최대 게임 트리이다. 즉 내가 놓을 수 있는 모든 상태와 그다음 상대가 놓을 수 있는 모든 상태를 이용하여 계산하되 자신이 놓을 수 있는 말의 위치에 상대가 놓을 수 있는 말의 위치별로 앞에서 언급한 패턴별 가중치를 이용하여 계산하되 상대 차례에서 상대가 얻을 수 있는 가장 큰 값들 중, 내가 놓음으로서 상대가 얻을 수 있는 값이 가장 작아지게 하는 수를 선택한다. 반대로 한다면 상대가 나에게 불리한 수를 선택하므로 min 단계의 값 중 나에게 가장 유리한 수를 그 상위 max 단계에서 내가 불리한 수 중 가장 큰 수가 되게 선택하는 것이다.

대상 데이터

• 본 논문에서 적용한 렌주 룰은 먼저 돌을 놓는 흑에게 열린 33, 열린 44, 장목은 금지되나, 43은 허용되고, 백에게는 열린 33, 열린 44, 장목, 43이 모두 허용된다. 게임에 이용되는 판의 크기는 15x15이다.

이론/모형

• 본 논문에서는 오목을 두는 지능적 프로그램을 설계하고 구현하였다. 규칙은 렌주 룰(renju rule)을 기준으로 하였으며, 15 x 15 게임판에서 오목을 둔다. 구현된 프로그램은 초기에는 문제 분석을 통하여 분석된 가중치로 판단을 하여 게임을 진행하도록 하였으나, 반복된 수행의 경험적 판단을 통하여 얻은 정보로 여러 차례 수정하며 고정된 가중치를 구성하고, 이 가중치를 게임에서 돌을 놓을 때 평가 기준으로 삼도록 하였으며, 최소-최대 게임 트리(min-max game tree)를 이용하여 상대가 있는 게임을 수행할 수 있도록 하였다.

성능/효과

• 본 논문에서 적용한 렌주 룰은 먼저 돌을 놓는 흑에게 열린 33, 열린 44, 장목은 금지되나, 43은 허용되고, 백에게는 열린 33, 열린 44, 장목, 43이 모두 허용된다. 게임에 이용되는 판의 크기는 15x15이다.
• 8보다 같거나 작은 값이 발견되는 순간 8보다 더 큰 값이 선택될 수 없기 때문에 더 이상 방문하지 않고 가지치기 한다. 예시로 제시한 그림에서는 노드 수가 작기 때문에 가지치기의 가치를 설명하기에는 부족함이 있으나 앞에서 계산한 바와 같이 오목 게임 초기에 노드의 수가 최소 11,239,200개 전개되는 것을 생각하면 알파-베타 가지치기는 대략 30% 이상의 가지치기 효율을 기대할 수 있다.
• 최근 2018년에 열린 대회에서 FreeStyle 룰에서만 다른 인공지능에게 1위를 내어주고 아직까지도 다른 룰에서는 1등을 유지하고 있다. 인공지능과 사람과의 대결도 있었는데 인공지능 특성상 한 수를 두는 시간이 매우 길지만, 본문에서 소개한 Yixin과 사람과의 대결에서 총 전적 1승 3무 1패를 기록하였다.

후속연구

• 시간적인 제약으로 인해 트리의 깊이를 3으로 두고 실험을 진행하였는데 기본적인 수는 모두 막으나 평가 함수에 의한 행동 패턴이 존재하기 때문에 일정한 패턴으로 수를 두었으며 자신이 공격할 수 있음에도 불구하고 지나치게 수비적인 모습을 보여 공격 기회를 놓치는 모습도 보인다. 첫 번째로 노드 수 증가에 따른 메모리 효율 개선이 필요하며 두 번째로는 수비 가중치와 공격 가중치의 분리만 이루어지면 꽤나 그럴듯한 프로그램이 만들어 질 것이다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기