[논문]유전 알고리즘을 이용한 삼목 게임 전략 분석

이병두

doi:10.7583/jkgs.2014.14.6.39

유전 알고리즘을 이용한 삼목 게임 전략 분석
Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm 원문보기

한국게임학회 논문지 = Journal of Korea Game Society, v.14 no.6, 2014년, pp.39 - 48

초록
AI-Helper

바둑은 단순한 규칙에도 불구하고 매우 복잡한 전략보드 게임이다. 몬테카를로 트리탐색을 이용하여 컴퓨터 바둑 프로그램들이 접바둑으로 프로기사를 제압해 왔다. 몬테카를로 트리탐색은 전략의 개념보다는 몬테카를로 시뮬레이션에 의해 계산된 승률에 근간을 한다. 반면에 적절한 적합도 함수로 된 유전 알고리즘은 게임 내 최적 해를 찾아낼 수 있다. 삼목 게임(또는 ${\bigcirc}{\times}$게임)은 가장 대중적인 게임 중의 하나이다. 저자는 삼목 게임에서의 최선의 전략을 찾고자 했다. 실험 결과로 유전 알고리즘은 효율적인 전략들을 찾을 수가 있으며, 바둑과 서양장기와 같은 여타 보드게임들에 적용할 수 있음을 보였다.

Abstract ▼ AI-Helper

Go is an extremely complex strategy board game despite its simple rules. By using MCTS, the computer Go programs with handicap game have been defeated human Go professionals. MCTS is based on the winning rate estimated by MC simulation rather than strategy concept. Meanwhile Genetic algorithm equipped with an adequate fitness function can find out the best solutions in the game. The game of Tic-Tac-Toe, also known as Naughts and Crosses, is one of the most popular games. We tried to find out the best strategy in the game of Tic-Tac-Toe. The experimental result showed that Genetic algorithm enables to find efficient strategies and can be applied to other board games such as Go and chess.

주제어

AI 본문요약
AI-Helper

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

문제 정의

MCTS는 위치평가함수(position evaluation function)를 필요로 하지 않는 최대우선탐색(best-first search) 방법으로 탐색공간에 대한 무작위적 탐험(randomized exploration)에 근간을 두고 있으나[1,3,9], 바둑 게임에서 중요한 전략과 전술을 적절히 적용할 수 없는 약점을 안고 있다. 이에 저자는 향후 컴퓨터바둑 프로그램 제작에 앞서 전략과 전술을 활용할 수 있는 유전 알고리즘(Genetic algorithm)을 삼목(Tic-Tac-Toe) 게임에 적용시켜 최선의 전략을 갖는 수순(手順)을 찾고자 했으며, 그 결과를 MCTS의 결과와 비교하고자 했다.

제안 방법

난수를 이용하여 25,872개의 전략 중 N = 250개 염색체를 포함하는 해집단(population)을 (eq. 2)와 같이 생성시켰다.
[10,11]은 삼목 게임에서의 최선의 전략을 구하기 위해 삼목에서 발생되는 패턴을 분석하여 원형 패턴을 구한 후, 유전 알고리즘을 이용하여 최적의 전략을 찾고자 했다. 또한 최선의 전략 우선순위로 (1) 상대방의 삼연형(三連形)을 우선적으로 봉쇄하고, (2) 중앙이 비워져 있으면 그 곳을 두며, (3) 중앙에 비워져 있지 않으면 귀, 변 순으로 둘 것을 제안했다. 저자 역시 유사한 방법을 택했으나 주요 차이점으로는 (1) 전략에 대한 실제 보상값을 전략 적합도 함수에 적용하였으며, (2) 유전 알고리즘을 통해 구한 최적해와 MCTS를 통해 구해낸 최적해를 비교하여 결론을 유도하였다.
교차는 선택된 두 부모 염색체의 정보를 교환하는 것이다. 본 실험에서는 단순하게 한 개의 부모 염색체를 선택한 후 [Fig. 9]와 같이 착수 1을 중심으로 좌우 수순의 값을 교환하여 자식 염색체를 생성하였다. 이때 생성된 자식 염색체가 불가능한 전략인 경우에는 변이과정을 거치도록 하였다.
또한 최선의 전략 우선순위로 (1) 상대방의 삼연형(三連形)을 우선적으로 봉쇄하고, (2) 중앙이 비워져 있으면 그 곳을 두며, (3) 중앙에 비워져 있지 않으면 귀, 변 순으로 둘 것을 제안했다. 저자 역시 유사한 방법을 택했으나 주요 차이점으로는 (1) 전략에 대한 실제 보상값을 전략 적합도 함수에 적용하였으며, (2) 유전 알고리즘을 통해 구한 최적해와 MCTS를 통해 구해낸 최적해를 비교하여 결론을 유도하였다.
6](b)와 같다고 밝혔다. 저자는 단순히 승리 확률을 갖고 수순을 찾아내는 MCTS의 한계를 극복하기 위하여 전략의 보상값을 부여한 유전 알고리즘을 삼목 게임에 적용하였다. 전략의 보상값에 전적으로 영향을 받는 유전 알고리즘의 단점에도 불구하고 [Fig.
즉 공격, 수비, 게임 결과를 고려하여 [Table 6]과 같이 전략을 18가지의 형태로 분류를 하였으며 그에 따른 보상값을 책정하였다.
8]과 같이 두 부분으로 구성하였다. 즉 삼목 게임에서 (1) 가능한 전략을 추출하기 위한 패턴 및 전략 생성 과정과 (2) 유전 알고리즘을 적용하는 과정으로 구분하였다.

대상 데이터

변이는 염색체의 유전자를 바꾸는 작업이 된다. 본 실험에서는 변이를 위해 새로운 염색체를 25,872개의 가능 전략으로부터 임의로 1개를 선택하였다. 변이에 사용된 변이율은 p_m = 0.

이론/모형

우수한 염색체를 생성하기 위한 유전자 선택 방법으로 룰렛 휠(roulette wheel) 선택 방법을 사용하였다. 일반적인 유전자 선택 방법은 해집단 내에 있는 두 염색체를 선택하여 유전자 조작인 교차(crossover) 과정을 수행한다.

성능/효과

[Fig. 10]에서 보듯이 최대 적합도(best fitness)는 +34, +35, +39로 단계적으로 증가했으며, 평균 적합도(average fitness)는 -3.8에서 +35.9로 수렴했으며, 표준편차(SD: standard deviation) 역시 12.1에서 3.0으로 수렴함을 알 수 있었다. 결국 유전 알고리즘을 적용한 결과 삼목 게임에서 최선의 전략을 갖는 수순은 전략 적합도가 +39인 [Fig.
6](b)의 전략 적합도는 +36이 되는 것을 알 수 있다. 이는 전략 적합도에 직접적인 영향을 받는 유전 알고리즘과 승리 확률에 직접적인 영향을 받는 몬테카를로 트리탐색에 있어 각각 최선의 전략 차이가 있을 것이라는 당연한 사실을 확인했으며, 아울러 유전 알고리즘을 통해 새로운 최선의 전략을 찾아낼 수 있음도 보였다.
이는 현재 개발되고 있는 컴퓨터바둑에서 단순한 MCTS 방법이 아닌 전략의 의미를 적용하여 새로운 전략기반 유전 알고리즘을 컴퓨터바둑에 적용할 수 있다는 새로운 사실을 알아냈다.

질의응답

핵심어	질문	논문에서 추출한 답변
	바둑은 어떤 단계로 구성되는가?	인간이 만든 게임 중 컴퓨터가 아직까지 제압 못하고 있는 마지막 게임인 바둑은 대략 2,500년 전에 중국에서 기원된 2인-제로섬-완전정보게임이다[1,2]. 바둑은 일반적으로 포석, 중반전, 끝내기 등의 세 단계로 구성되어 있다. 포석에서는 전략(strategy) 개념이 중요하며, 중반전에서는 전술(tactics) 개념이 중요하다.
	삼목 게임은 무엇인가?	삼목 게임은 전 세계적으로 잘 알려진 게임 중의 하나이며, 두 대국자(☓, ◯)가 번갈아가며 3⨯3칸에 ☓와 ◯를 써서 가로, 세로 또는 대각선상에 동일한 모양이 연속하여 3개가 형성되면 이기는 게임이다. 참고로 [Fig.
	유전 알고리즘의 목표는?	유전 알고리즘은 다윈의 진화론을 기초로 한 계산 모델로 존 홀랜드(John Holland)에 의해서 제안되었으며 최적화 문제를 해결하는 방법 중의 하나이다[12]. 즉 환경에 잘 적응하는 유전자만을 선택, 교배하며 때에 따라 돌연변이를 하여 차세대에 우수한 형질의 유전자를 생성하는 것이다. 결국 진화가 거듭될수록 주어진 환경에 적합한 유전자들만이 남아 있게 만드는 것이다[13].

참고문헌 (14)

B.D Lee, "Monte-Carlo Tree Search Applied to the game of Tic-Tac-Toe", Journal of Korea Game Society, Vol. 14, No. 3, pp. 47-54, 2014.

원문보기 상세보기
B.D. Lee and J.W. Park, "Applying Principal Component Analysis to Go Openings", Journal of Korea Game Society, Vol. 13, No. 2, pp. 59-70, 2013.

원문보기 상세보기
B.D. Lee, "The best move sequence in playing Tic-Tac-Toe game", Journal of The Korean Society for Computer Game, Vol. 27, No. 3, pp. 11-16, 2014.
B.D. Lee, "Analysis of Korean, Chinese and Japanese Pro Go Player's Openings", Journal of Korean Society for Computer Game, Vol.26, No.4, pp. 17-26, 2013.
B.D. Lee, "Comparison of LDA and PCA for Korean Pro Go Player's Opening Recognition", Journal of Korea Game Society, Vol.13, No.4, pp. 15-24, 2013.
B.D. Lee, "Korean Pro Go Player's Opening Recognition Using PCA", Journal of Korean Society for Computer Game, Vol.26, No.2, pp. 228-233, 2013.
B.D. Lee, "Applying Neuro-fuzzy Reasoning to Go Opening Games", Journal of Korea Game Society, Vol.9, No.6, pp. 117-126, 2009.
Wikipedia, "Computer Go", from http://en.wikipedia.org/wiki/Computer_Go, 2014.
M.H.M. Winands and Y. Brornsson, "Evaluation Function Based Monte-Carlo LOA", from http://www.ru.is/∼yngvi/pdf/WinandsB09.pdf, 2014.
G. Hochmuth, "On the Genetic Evolution of a Perfect Tic-Tac-Toe Strategy", from http://www.genetic-programming.org/sp2003/Hochmuth.pdf, 2014.
A. Bhatt, P. Varshney and K. Deb, "In Search of No-loss Strategies for the Game of Tic-Tac-Toe using a Customized Genetic Algorithm", GECCO'08(Genetic and Evolutionary Computation Conference 2008), pp. 889-896, 2008.
Wikipedia, "Genetic Algorithm", from http://ko.wikipedia.org/wiki/%EC%9C%A0%E C%A0%84_%EC%95%8C%EA%B3%A0%EB %A6%AC%EC%A6%98, 2014.
I.J. Ahn and I.K. Park, "Design of Omok AI using Genetic Algorithm and Game Trees and Their Parallel Processing on the CPU", Journal of the Korea Information Science Society, Vol. 37, No. 2, pp. 66-75, 2010.
S.H. Ling and H.K. Lam, "Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functions", Journal of Intelligent Learning Systems and Applications, Vol. 3, pp. 37-44, 2011.

상세보기

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

유전 알고리즘을 이용한 삼목 게임 전략 분석
Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

질의응답

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

유전 알고리즘을 이용한 삼목 게임 전략 분석 Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm 원문보기

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

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

질의응답

참고문헌 (14)

이 논문을 인용한 문헌

저자의 다른 논문 :

이병두 (8)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

유전 알고리즘을 이용한 삼목 게임 전략 분석
Analysis of Tic-Tac-Toe Game Strategies using Genetic Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper