컴퓨터 고

Computer Go
이 기사는 인공지능의 바둑에 대한 연구입니다.컴퓨터 프로그래밍 언어에 대해서는 이동(프로그래밍 언어)을 참조하십시오.
Go 소프트웨어와 혼동하지 마십시오.
시리즈의 일부
가세요
Go board part.jpg
게임 상세
역사와 문화
참가자와 조직
컴퓨터와 수학

컴퓨터 고는 전통적인 보드 게임을 하는 컴퓨터 프로그램을 만드는 데 전념하는 인공지능 분야이다.그 분야는 두 시대로 크게 나뉘어져 있다.2015년 이전에는 그 시대의 프로그램이 약했다.1980, 90년대 최고의 노력으로 초보자도 꺾을 수 있는 AI만 배출됐고 2000년대 초반의 AI는 기껏해야 중급 수준이었다.전문가들은 AI를 위해 10개 이상의 돌을 핸디캡을 줘도 이 프로그램들을 물리칠 수 있었다.바둑의 19x19 보드에서는 체커와 체스를 위한 AI와 같이 잘 작동하는 알파 베타 미니맥스와 같은 알고리즘의 많은 부분이 고려하기에는 너무 많은 분기 가능성이 있었기 때문에 산산조각이 났다.그 시대의 기술과 하드웨어를 이용한 인간 전문 품질 프로그램의 창설은 불가능했다.일부 AI 연구자들은 인간과 같은 AI를 만들지 않고서는 이 문제를 해결할 수 없을 것이라고 추측했다.

Monte Carlo 트리 검색의 Go 알고리즘에 대한 적용은 2000년대 후반의 현저한 개선을 제공했으며, 프로그램은 마침내 저단 레벨, 즉 더 약한 프로페셔널의 레벨을 달성할 수 있었다.더 나은 전문가들은 여전히 이러한 프로그램의 약점을 이용하여 꾸준히 이길 수 있지만, AI의 성과는 중급 수준을 넘어섰습니다.최고의 인간 선수들을 핸디캡 없이, 오랫동안 도달할 수 없는 것으로 여겨져 온 감질나는 달성 불가능한 골은 새로운 관심을 불러일으켰다.핵심 통찰력은 머신러닝과 딥러닝의 응용으로 판명되었습니다.구글의 AI 연구 전문 기업인 딥마인드는 2015년 알파고를 생산해 2016년 세상에 발표했다.알파고는 2016년 노핸디캡 대결에서 프로 9단 이세돌을 꺾은 데 이어 2017년에는 2년간 세계 랭킹 1위를 유지하던 커제이를 꺾었다.체커들이 1995년에 기계로, 1997년에 체스로 떨어졌던 것처럼, 컴퓨터 프로그램들은 2016-2017년에 마침내 인류 최고의 바둑 챔피언들을 정복했다.DeepMind는 알파고를 공개하지 않았지만, DeepMind가 발표한 알파고와 그 변종을 설명하는 저널 기사를 바탕으로 다양한 프로그램이 만들어졌다.

개요 및 이력

바둑은 직관, 창의적이고 전략적인 [1][2]사고를 필요로 하는 복잡한 보드게임이다.인공지능(AI) 분야에서 오랫동안 어려운 도전으로 여겨져 왔고 [3]체스보다 훨씬 풀기 어렵다.이 분야의 많은 사람들은 바둑이 [4]체스보다 인간의 생각을 모방하는 요소들을 더 많이 필요로 한다고 생각했다.수학자 I. J. 굿은 1965년에 [5]다음과 같이 썼다.

컴퓨터로 할까요?- 컴퓨터가 단순한 법정 게임이 아닌 합리적인 바둑을 두도록 프로그래밍하기 위해서는 좋은 전략의 원칙을 공식화하거나 학습 프로그램을 설계해야 합니다.원칙은 체스보다 더 질적이고 신비롭고 판단력에 더 의존한다.그래서 나는 체스보다 합리적인 바둑을 두기 위해 컴퓨터를 프로그래밍하는 것이 더 어려울 것이라고 생각한다.

2015년 이전에는 최고의 바둑 프로그램들이 아마추어 단 [6][7]레벨에 도달하는 데 성공했습니다.작은 9×9 보드에서는 컴퓨터의 성능이 향상되었고, 일부 프로그램은 프로 선수와의 9×9 게임 중 극히 일부만 간신히 이겼다.알파고 이전에, 일부 연구원들은 컴퓨터가 [8]바둑에서 최고의 인간을 절대 이길 수 없다고 주장했었다.

수십 년 전

최초의 바둑 프로그램은 1968년 Albert Lindsey Zobrist에 의해 [9]패턴 인식에 대한 논문의 일부로 작성되었습니다.영역을 추정하기 위한 영향함수와 ko를 검출하기 위한 조브리스트 해시를 도입했다.

1981년 4월, Jonathan K Millen은 Byte에 KIM-1 마이크로컴퓨터의 1K [10]RAM에 들어가는 15x15 보드를 갖춘 바둑 프로그램인 Wally에 관한 기사를 실었습니다.Bruce F. 웹스터는 1984년 11월 맥포스 [11]소스를 포함한 애플 매킨토시용 바둑 프로그램에 관한 기사를 잡지에 실었다.바둑 프로그램은 약했다; 1983년의 한 기사는 그것들이 기껏해야 초보자의 등급인 20규에 상당하며 종종 더 작은 판으로 [12]제한된다고 추정했다.19x19 크기의 보드에서 Internet Go Server(IGS)에서 플레이한 AI는 하드웨어가 [13]대폭 개선된 후 2003년에 약 20-15규의 강도를 보였다.

1998년, 매우 강한 선수들은 25-30스톤의 핸디캡을 주면서 컴퓨터 프로그램을 이길 수 있었는데, 이는 거의 인간 선수들이 감당하지 못할 엄청난 핸디캡이었다.1994년 세계 컴퓨터 바둑 선수권 대회에서는 우승 프로그램인 고 인텔리젼이 청소년 선수들에게 15스톤의 [14]핸디캡을 받으면서 3전 전패한 사례가 있었다.일반적으로 프로그램의 약점을 이해하고 이용하는 선수들은 일반적인 [15]선수들보다 훨씬 큰 핸디캡으로 이길 수 있었다.

2007-2014: 몬테카를로 트리 검색

2006년(2007년 기사 발표)에 Rémi Coulom은 Monte Carlo tree [16]search라는 새로운 알고리즘을 개발했습니다.그 안에서 게임 트리는 일거수일투족을 분기하는 잠재적인 미래를 위해 평상시와 같이 작성된다.그러나 컴퓨터는 반복적인 무작위 플레이아웃을 통해 트리의 말단 잎을 "점수"한다(다른 문제에 대한 몬테카를로 전략과 유사).장점은 이러한 무작위 플레이아웃이 매우 빠르게 이루어질 수 있다는 것이다.랜덤 플레이아웃이 포지션의 실제 가치와 일치하지 않는다는 직관적인 반대는 예상만큼 절차에 치명적이지 않은 것으로 판명되었습니다. 알고리즘의 "트리 검색" 측면은 탐색할 수 있는 적절한 미래 게임 트리를 찾을 수 있을 만큼 충분히 수정되었습니다.모고, 푸에고 등 기존 AI보다 성능이 우수했다.특히 탐색할 가능성이 적은 소형 9x9 보드에서 최고의 프로그램을 사용할 수 있습니다.2009년, 19x19 보드의 KGS Go Server에서 낮은 단 레벨까지 도달할 수 있는 첫 번째 프로그램이 등장했다.

2010년 핀란드에서 열린 유럽 바둑 콩그레스(European Go Congress)에서 MogoTW는 카탈린 타라누(5p)와 19x19 바둑을 두었다.MogoTW는 7스톤 핸디캡을 받아 [17]승리했다.

2011년, Zen은 서버 KGS에서 한 번에 15초씩 게임을 하며 5단에 도달했다.이 순위에 도달한 계정은 26코어 [18]머신에서 실행되는 Zen 클러스터 버전을 사용합니다.

2012년, 젠은 타케미야 마사키 선수(9p)를 5스톤 핸디캡으로 11점 차로 누르고, 이어서 4스톤 [19]핸디캡으로 20점 이겼다.

2013년 크레이지 스톤은 19×19 게임에서 이시다 요시오(9p)를 4스톤 [20]핸디캡으로 꺾었다.

심지어 19x19 게임에서 5전 4선승제인 2014 코드센트릭 Go Challenge는 크레이지 스톤과 프란츠-요제프 디쿠트(6d)가 맞붙었다.어느 강자도 바둑 프로그램과 대등한 조건에서 진지한 경쟁을 벌이기로 동의한 적이 없었다.Franz-Jozef Dickhut이 이겼지만, Crazy Stone이 첫 경기에서 1.5점 [21]차로 이겼다.

2015년 이후:딥러닝 시대

상세 정보:AlphaGo 대 Fan Hui, AlphaGo 대 Lee Sedol, AlphaGo 대 Ke Jee

2015년 10월, 구글 딥마인드 프로그램 알파고는 유럽 바둑 챔피언인 판후이(Fan Hui)를 토너먼트 [22]경기에서 5번 중 5번 이겼다.

2016년 3월, 알파고는 다섯 경기 [23]중 첫 세 경기에서 이세돌을 이겼다.9단 마스터가 컴퓨터와 [24]핸디캡 없이 프로 게임을 한 것은 이번이 처음이다.이승엽은 자신의 승리를 "가치 없는 것"[25]이라고 표현하며 네 번째 경기에서 승리했다.알파고는 이틀 [26][27]후 결승전에서 승리했다.

알파고는 2017년 5월 '퓨처오브고 서밋'[30]에서 당시 [28][29]세계 랭킹 1위였던 커제이를 3연전에서 꺾었다.

DeepMind는 2017년 10월, 100개의 [31]게임 중 89개의 게임 중에서 커제 버전을 제치고, 모든 이전 버전을 능가하는 새로운 버전의 알파고를 공개했다.

알파고의 기본 원리가 네이처지에 발표된 이후 다른 팀들은 수준 높은 프로그램을 제작할 수 있게 되었다.2017년에는 Zen과 Tencent의 프로젝트 Fine Art가 동시에 매우 높은 수준의 전문가들을 물리칠 수 있었습니다.오픈 소스 릴라 제로 엔진도 만들어졌다.

기존 AI의 전략 및 성능 과제

오랫동안, 컴퓨터 바둑이 컴퓨터 체스와 근본적으로 다른 문제를 일으킨다는 것은 널리 알려진 의견이었다.많은 사람들은 강력한 바둑 프로그램을 일반 인공지능 기술의 근본적인 발전의 결과로 먼 미래에나 달성할 수 있는 것으로 여겼다.이 문제가 실현 가능하다고 생각한 사람들은 인간 전문가에 대해 효과적인 영역 지식이 요구될 것이라고 믿었다.따라서 컴퓨터 Go 개발의 상당 부분은 인간과 같은 전문 지식을 표현하고 이를 현지 검색과 결합하여 전술적 성질의 질문에 답하는 데 초점이 맞춰져 있었다.그 결과 많은 특정 상황을 잘 처리했지만 전반적인 게임 처리에는 매우 명백한 약점을 가진 프로그램들이 나왔다.또, 이러한 고전적인 프로그램은, 이용 가능한 컴퓨팅 능력의 향상으로부터 얻을 수 있는 것은 거의 없습니다.그 분야의 진보는 대체로 느렸다.

보드의 크기

대형 보드(19×19, 361 교차로)는 강력한 프로그램을 만들기 어려운 주된 이유 중 하나로 자주 언급됩니다.큰 보드 크기 때문에 유의한 검색 확장이나 제거 휴리스틱스 없이 알파 베타 검색기가 심층적인 사전 검색을 수행할 수 없습니다.

2002년, MIGOS(MINI GO Solver)라는 컴퓨터 프로그램이 5×5 보드의 바둑을 완전히 해결했다.흑인이 이기면 [32]판을 다 잡는다.

이동 옵션 수

계속해서 체스에 비유하자면 바둑은 게임의 규칙에 의해 제한되지 않는다.체스의 첫 수를 위해, 그 선수는 20개의 선택지를 가지고 있다.바둑 기사들은 55개의 뚜렷한 법적 조치 중에서 선택할 수 있으며, 이는 대칭성을 고려합니다.대칭이 깨짐에 따라 이 수치는 빠르게 증가하며 곧 보드의 361개의 거의 모든 점을 평가해야 합니다.

평가 기능

게임에서 가장 기본적인 작업 중 하나는 보드 위치를 평가하는 것이다: 어느 쪽이 더 선호되고 어느 정도까지 선호되는가?체스에서, 트리의 많은 미래 위치는 한쪽에 대한 직접적인 승리이며, 보드는 전당 구조와 같은 특정 위치 요소뿐만 아니라 단순한 재료 계수에서 평가를 위한 합리적인 휴리스틱을 가지고 있습니다.한쪽이 아무런 이익도 없이 여왕을 잃은 미래는 분명히 다른 쪽에 유리하다.이러한 유형의 위치 평가 규칙을 바둑에 효율적으로 적용할 수 없습니다.바둑 포지션의 값은 그룹의 생존 여부, 서로 연결될 수 있는 돌, 강한 포지션이 영향을 미치는 범위 또는 약한 포지션을 공격할 수 있는 범위에 대한 휴리스틱에 따라 달라집니다.돌을 놓는 것은 즉각적인 영향을 미치지 않을 수 있지만, 많은 움직임이 있은 후 이사회의 다른 영역이 형성됨에 따라 돌이켜보면 매우 중요해질 수 있다.

이사회 상태를 제대로 평가하지 못하면 AI가 유리하다고 잘못 믿지만 실제로는 그렇지 않은 쪽으로 움직이게 됩니다.

생사

바둑 기사의 주요 관심사 중 하나는 어떤 돌무더기를 살려둘 수 있고 어떤 돌무더기를 잡을 수 있는가이다.이러한 일반적인 종류의 문제를 삶과 죽음이라고 한다.지식 기반 AI 시스템은 때때로 이사회에 속한 그룹의 생사 상태를 파악하려고 시도했다.가장 직접적인 접근은 해당 돌에 영향을 미칠 수 있는 움직임에 대해 나무 탐색을 수행하고, 그 후 주요 플레이 라인의 끝에 돌의 상태를 기록하는 것입니다.그러나 시간과 기억의 제약 속에서, 어떤 움직임이 돌 그룹의 '생명'에 영향을 미칠 수 있는지를 완전히 정확하게 결정하는 것은 일반적으로 가능하지 않다.이는 고려할 이동을 선택하기 위해 경험적 접근 방식을 적용해야 함을 의미합니다.순효과는 어떤 프로그램이든 재생속도와 생사판독력 사이에 균형이 있다는 것입니다.

Benson의 알고리즘을 사용하면 무조건 활성 체인을 결정할 수 있으며, 따라서 안전성을 위해 미래에 점검할 필요가 없습니다.

상태 표시

모든 바둑 프로그램들이 해결해야 할 문제는 경기의 현재 상태를 어떻게 나타내느냐 하는 것이다.보드를 표현하는 가장 직접적인 방법은 1차원 또는 2차원 배열로, 배열 내의 요소는 보드 상의 점을 나타내며 흰색 돌, 검은색 돌 또는 빈 교차로에 해당하는 값을 취할 수 있습니다.포획된 돌의 수, 포획된 돌의 순서, 불법 교차로 등을 저장하기 위해서는 추가 자료가 필요하다.일반적으로 기계학습 프로그램은 가장 단순한 형태에서 멈추고 유기 AI가 보드의 의미를 이해하도록 합니다. 이는 단순히 몬테카를로 플레이아웃을 사용하여 플레이어의 좋고 나쁨을 "점수"하는 데 사용할 수 있습니다.그러나 인간의 전략을 직접 모형화하려는 고전적인 AI 프로그램은 더 나아가 죽은 것으로 추정되는 돌, 무조건 살아있는 돌, 상호생활 상태의 돌 등 데이터를 겹겹이 쌓아올려 게임의 상태를 표현한다.

시스템 설계

역사적으로, 상징적인 인공지능 기술은 Go AI의 문제에 접근하기 위해 사용되어 왔다.뉴럴 네트워크는 2000년대 들어 대체 접근법으로 시도되기 시작했습니다. 왜냐하면 뉴럴 네트워크는 초기 수십 년 동안 도달하기 어려웠던 엄청난 컴퓨팅 능력을 필요로 했기 때문입니다.이러한 접근은 바둑의 분기 요인이 높고 다른 많은 어려움이 있는 문제를 완화하려고 시도한다.

프로그램이 해야 할 유일한 선택은 다음 돌을 어디에 놓을 것인가 하는 것이다.그러나 하나의 돌이 전체 판에 미칠 수 있는 광범위한 영향과 다양한 돌의 그룹이 서로 가질 수 있는 복잡한 상호작용 때문에 이러한 결정은 어렵다.이 문제를 해결하기 위해 다양한 아키텍처가 등장했습니다.일반적인 기술 및 설계 철학은 다음과 같습니다.

미니맥스 트리 검색

게임 플레이 소프트웨어를 만드는 전통적인 AI 기술은 미니맥스 트리 검색을 사용하는 것입니다.여기에는 보드 상의 모든 가상적인 움직임을 특정 지점까지 실행한 후 평가 함수를 사용하여 현재 플레이어의 포지션의 가치를 추정하는 것이 포함됩니다.최적의 가상 보드로 이어지는 이동이 선택되고 매 회마다 프로세스가 반복됩니다.나무 검색은 컴퓨터 체스에서 매우 효과적이었지만 컴퓨터 바둑 프로그램에서는 덜 성공적이었다.이는 전통적으로 바둑판의 효과적인 평가 기능을 만드는 것이 어려웠기 때문이기도 하고, 가능한 많은 수의 이동이 각각 높은 분기 계수로 이어질 수 있기 때문이기도 하다.이로 인해 이 기술은 계산 비용이 매우 많이 듭니다.따라서 검색 트리를 광범위하게 사용하는 많은 프로그램은 전체 19×19 보드가 아닌 더 작은 9×9 보드에서만 재생할 수 있습니다.

속도와 메모리 측면에서 검색 트리의 성능을 크게 향상시킬 수 있는 몇 가지 기술이 있습니다.알파 베타 프루닝, 주요 변동 검색 및 MTD(f)와 같은 프루닝 기술을 사용하면 강도를 잃지 않고 효과적인 분기 계수를 줄일 수 있습니다.삶과 죽음과 같은 전술적 영역에서 Go는 특히 전치표와 같은 캐싱 기술에 순응합니다.이는 특히 반복적인 심화 접근법과 결합할 경우 반복적인 노력의 양을 줄일 수 있다.일반적으로 풀사이즈 바둑판을 신속하게 전치표에 격납하기 위해서는 수학적으로 요약하는 해싱 기법이 필요하다.Zobrist 해시는 충돌률이 낮기 때문에 Go 프로그램에서 매우 인기가 있으며 처음부터 계산하지 않고 두 개의 XOR만으로 매번 반복적으로 업데이트할 수 있습니다.이러한 성능 향상 기술을 사용하더라도 풀사이즈 보드의 풀 트리 검색은 여전히 매우 느립니다.상대방이 이미 강한 이동은 고려하지 않고, 캡처될 돌 그룹 옆에 있는 이동을 항상 고려하는 것과 같은 선택적인 확장 기능을 사용하면 검색 속도를 높일 수 있습니다.하지만, 이 두 가지 옵션 모두 경기의 흐름을 바꿀 수 있는 중요한 움직임을 고려하지 않는 상당한 위험을 초래한다.

컴퓨터 경합 결과에 따르면, 적절한 동작을 몇 개 선택하는 패턴 매칭 기법과 현지화된 신속한 전술 검색(상기 설명)이 경쟁 프로그램을 제작하기에 충분했습니다.예를 들어, GNU Go는 2008년까지 경쟁력이 있었습니다.

지식 기반 시스템

인간 초보자들은 종종 명수들이 플레이한 오래된 게임의 기록에서 배운다.1990년대의 AI 작업은 종종 바둑 지식의 AI 인간형 휴리스틱스를 "가르치는" 시도와 관련이 있다.1996년 팀 클링거와 데이비드 메히너는 최고의 AI의 초급 강점을 인정하며 "더 나은 바둑 지식을 표현하고 유지하기 위한 도구를 사용하면 더 강력한 바둑 [33]프로그램을 개발할 수 있을 것이라고 믿는다"고 주장했다.그들은 두 가지 방법을 제안했다: 돌의 공통적인 구성과 그 위치를 인식하고 국지 전투에 집중하는 것이다.2001년 한 논문은 바둑 프로그램은 지식의 질과 양 모두 아직 부족하다며 이를 고치면 바둑 [34]AI 성능이 향상될 것이라고 결론지었다.

이론적으로, 전문적인 지식을 사용하는 것은 바둑 소프트웨어를 개선할 것이다.강한 플레이를 위한 수백 가지의 지침과 경험칙이 아마추어와 프로 선수들에 의해 형성되었다.프로그래머의 임무는 이러한 휴리스틱스를 취하여 컴퓨터 코드로 공식화하고 패턴 매칭과 패턴 인식 알고리즘을 사용하여 이러한 규칙이 적용되는 시기를 인식하는 것입니다.또한 이러한 휴리스틱에 대해 "점수"를 매길 수 있는 것이 중요합니다.이것에 의해, 상충하는 어드바이스를 제공할 때, 시스템은 어떤 휴리스틱이 상황에 보다 중요하고 적용 가능한지를 판단할 수 있습니다.비교적 성공적인 결과의 대부분은 프로그래머들의 바둑 기술이나 바둑에 대한 개인적인 추측에서 나온 것이지만, 공식적인 수학적 주장에서 나온 것은 아니다. 그들은 컴퓨터가 바둑을 두는 방식을 모방하도록 하려고 노력하고 있다.2001년 경의 경쟁 프로그램에는 호세키와 [34]같은 게임의 다양한 측면과 전략을 다루는 50-100개의 모듈이 포함될 수 있습니다.

전문가 지식에 크게 의존해 온 프로그램의 예로는 핸드톡(나중에 Goemate로 알려짐), The Many Faces of Go, Go Intelligence, Go++ 등이 있으며, 각각은 어느 시점에서는 세계 최고의 바둑 프로그램으로 여겨지고 있다.그러나 이러한 방식은 결국 수익률이 낮아졌고, 실물 크기의 이사회에서는 기껏해야 중간 수준을 넘어서는 일은 없었습니다.한 가지 특별한 문제는 전반적인 게임 전략이었다.전문가 시스템이 패턴을 인식하고 국지적인 교전을 할 줄 안다고 해도, 그것은 미래에 다가올 더 깊은 전략적 문제를 놓칠 수 있다.그 결과, 강도는 부품의 합계보다 작은 프로그램입니다.개개의 전술적인 근거에서는 좋은 움직임일 수 있지만, 그 프로그램은 그 대가로 너무 많은 것을 캐딩하도록 교묘하게 조작되어 전체적인 패배의 입장에 놓일 수 있습니다.2001년 조사에서 알 수 있듯이, "단 한 번의 나쁜 움직임이 좋은 경기를 망칠 수 있다.풀게임의 프로그램 퍼포먼스는 마스터 [34]레벨보다 훨씬 저하될 수 있습니다.

몬테카를로법

주요 기사:몬테카를로 트리 검색

손으로 코딩된 지식과 검색을 사용하는 데 대한 한 가지 주요 대안은 몬테카를로 방법을 사용하는 것이다.이것은 잠재적인 움직임의 목록을 생성하여 각각의 움직임에서 생성된 보드 상에서 수천 개의 게임을 랜덤으로 실행함으로써 이루어집니다.현재 플레이어의 가장 좋은 랜덤 게임 세트로 이어지는 동작이 가장 좋은 움직임으로 선택됩니다.이 기술의 장점은 도메인 지식이나 전문가의 조언이 거의 필요하지 않다는 것입니다.단, 메모리와 프로세서의 요건이 증가한다는 것입니다.그러나 평가에 사용되는 움직임은 무작위로 생성되기 때문에 한 가지 특정 상대 응답을 제외하고는 우수한 움직임이 좋은 움직임으로 잘못 평가될 수 있다.그 결과, 전략적인 면에서는 강하지만,[citation needed] 전술적으로는 불완전한 프로그램입니다.이 문제는 이동 세대에 도메인 지식을 추가하고 랜덤 진화에 더해 검색 깊이를 높임으로써 완화될 수 있습니다.몬테카를로 기술을 사용하는 몇몇 프로그램들은 Fuego,[35] The Many Faces of Go v12,[36] 릴라,[37] [38]MoGo, Crazy Stone, MyGoFriend,[39] 그리고 Zen이다.

2006년에는 나무에 적용되는 새로운 검색 기법인 신뢰 상한([40]UCT)이 개발되어 많은 9x9 Monte-Carlo Go 프로그램에 적용되어 우수한 결과를 얻었다.UCT는 지금까지 수집된 플레이아웃 결과를 사용하여 보다 성공적인 플레이 라인을 따라 검색을 안내하면서 대체 라인을 탐색할 수 있습니다.UCT 기법과 19x19 대형 보드에서의 플레이를 위한 다른 많은 최적화로 MoGo는 가장 강력한 연구 프로그램 중 하나가 되었습니다.19x19 바둑에 UCT 방식을 적용한 성공 사례로는 MoGo, Crazy Stone,[41] Mango 등이 있다.MoGo는 2007년 컴퓨터 올림피아드에서 우승하여 훨씬 덜 복잡한 9x9 바둑에서 5단 프로인 Guo Juan과의 전격전 (3전 중 1전)에서 승리하였습니다.많은 얼굴 오브[42] 고는 전통적인 지식 기반 엔진에 UCT 검색을 추가한 후 2008년 컴퓨터 올림피아드에서 우승했다.

몬테카를로를 기반으로 한 Go 엔진은 인간보다 지역 싸움을 계속하기 보다는 테누키를 플레이하고 보드 상의 다른 곳으로 이동하는 데 훨씬 더 의지가 있는 것으로 유명하다.이는 종종 이러한 프로그램의 [43]존재 초기에 약점으로 인식되었습니다.그럼에도 불구하고, 이러한 경향은 지배적인 결과를 가진 알파고의 플레이 스타일에 지속되어 왔기 때문에, 이것은 "약점"[44]이라기 보다는 "퀴크"에 가까울 수 있다.

기계 학습

지식 기반 시스템의 기술 수준은 프로그래머 및 관련 도메인 전문가의 지식과 밀접하게 관련되어 있습니다.이러한 한계로 인해 진정한 강력한 AI를 프로그래밍하는 것이 어려워졌다.다른 방법은 기계 학습 기술을 사용하는 것입니다.이 경우 프로그래머가 프로그래밍해야 하는 것은 포지션의 가치를 분석하는 방법과 관련된 규칙과 간단한 스코어링 알고리즘뿐입니다.그러면 소프트웨어는 이론적으로 자체 패턴, 휴리스틱스 및 전략을 자동으로 생성합니다.

이것은 일반적으로 신경 네트워크 또는 유전 알고리즘이 프로 게임의 대규모 데이터베이스를 검토하거나 자신이나 다른 사람 또는 프로그램과 많은 게임을 할 수 있도록 함으로써 이루어집니다.그런 다음 이 알고리즘은 성능을 향상시키는 수단으로 이 데이터를 활용할 수 있습니다.기계 학습 기술은 주로 다른 기술에 의존하는 프로그램의 특정 매개변수를 조정하기 위해 덜 야심찬 맥락에서 사용될 수도 있습니다.예를 들어 Crazy Stone은 Elo 등급 시스템의 [45]일반화를 사용하여 수백 개의 샘플 게임으로부터 이동 생성 패턴을 학습합니다.

이 접근법의 가장 유명한 예는 이전 AI보다 훨씬 효과적이라는 것을 증명한 알파고이다.첫 번째 버전에서는 수백만 개의 기존 포지션을 분석하여 추가 분석 가치가 있는 우선 순위를 매길 수 있는 움직임을 결정하는 계층이 하나 있었고, 제안된 레이어를 사용하여 자신의 승기를 최적화하려고 하는 계층이 하나 더 있었습니다.알파고는 몬테카를로 트리 검색을 사용하여 결과 위치를 채점했다.알파고의 최신 버전인 알파고제로(AlphaGoZero)는 기존의 바둑 게임으로부터 배우는 것을 피하고, 대신에 반복적인 게임으로부터만 배웠다.신경망을 이용한 다른 초기 프로그램으로는 NeuroGo와 WinHonte가 있다.

컴퓨터 이동 및 기타 필드

컴퓨터 바둑 연구 결과는 인지과학, 패턴 인식, 기계 [46]학습과 같은 다른 유사한 분야에도 적용되고 있다.응용 수학의 한 분야인 조합 게임 이론은 컴퓨터 [34]바둑과 관련된 주제이다.

John H. Conway는 바둑에서 최종 게임의 분석에 초현실적인 숫자를 적용할 것을 제안했다.이 아이디어는 Elwyn R에 의해 더욱 발전되었습니다. Berlekamp와 David Wolfe는 그들의 책인 Mathemical Go에서 ( ) ISBN978-1-56881-032-4).Go 엔드게임은 대부분 채워진 임의의 보드에서 절대적인 최선의 이동을 계산해야 하는 경우 PSPACE 하드임이 입증되었습니다.트리플 Ko,[47]쿼드러플 Ko,[48]당밀 Ko,[49]과 Moonshine Life[50]와 같은 특정한 복잡한 상황 이 문제 어려운.(실제로, 강한 몬테카를로 알고리즘 여전히 충분한 정상적인 가다 종반전 상황을 다룰 수 있고, 생사가 걸린 종반전 문제를 일으키는 가장 복잡한 클래스는high-lev에 생길 가능성도 있다.엘 게임이다.)[51]

다양한 어려운 조합 문제(NP-하드 문제)는 충분히 큰 보드에서는 Go와 같은 문제로 변환할 수 있지만, 임의의 크기의 보드로 적절히 일반화되면 체스나 지뢰찾기를 포함한 다른 추상 보드 게임에서도 마찬가지입니다.NP-완전 문제는 일반적으로 도움을 받지 않은 사람이 적절하게 프로그램된 컴퓨터보다 더 쉽게 풀리는 경향이 없다: 예를 들어, 도움을 받지 않은 사람은 부분집합 [52][53]문제의 예를 들어, 컴퓨터보다 훨씬 못 푼다.

바둑 프로그램 목록

다음 항목도 참조하십시오.Go 소프트웨어
  • 알파고, 9단 인간 바둑 기사와 짝수 대결을 펼친 최초의 컴퓨터 프로그램
  • 이수영 프로그램[54] BaduGI
  • Crazy Stone by Rémi Coulom (일본에서는 사이쿄노이고로 판매)
  • 다크포레스트, 페이스북
  • Tencent의 Fine Art(파인 아트)
  • Monte Carlo의[35] 오픈 소스 프로그램인 Fuego
  • Sen:te의 Macintosh Go 프로그램 Goban(무료 Goban Extensions [55]필요)
  • 오픈 소스 클래식 바둑 프로그램인 GNU Go
  • 릴라, 몬테카를로 최초의 일반 판매[37] 프로그램
  • Leela Zero, Alpha[37] Go Zero 논문에서 기술된 시스템의 재실장
  • David Fotland (일본에서는 [36]AI Igo로 판매)의 「다수의 얼굴」
  • Frank[39] Karger의 프로그램 MyGoFriend
  • MoGo by Sylvain Gelly; 많은 [56][38]사람들에 의한 평행 버전.
  • Pachi, Petr Baudish의[57] 오픈 소스 몬테카를로 프로그램
  • 스마트 게임[58] 포맷의 발명가 Anders Kierulf의 Smart Go
  • 슈틴브레터, 에릭 반 데 베르프[59] 지음
  • 젠, 오지마 요지의 일명 야마토(일본에서는 덴초노이고), 가토 [60]히데키의 병행 버전.

알파고

주요 기사:알파고

구글 딥마인드가 개발한 알파고는 2015년 10월 딥러닝과 몬테카를로 트리 [61]서치를 결합한 기술을 이용해 인간 전문 플레이어를 물리치며 큰 발전을 이뤘다.알파고는 기존의 바둑 프로그램보다 훨씬 강력했고, 실물 크기의 기판에서 핸디캡 없이 9단 인간 프로를 이긴 최초의 선수였다.그 이후로 Go AI에 대한 작업은 알파고를 만드는 데 사용된 기술을 모방하는 것으로 이루어졌는데, 알파고는 다른 모든 것들보다 훨씬 더 강하다는 것이 증명되었다.

컴퓨터 바둑 프로그램 간의 경쟁

바둑 컴퓨터 프로그램 간에 매년 몇 개의 대회가 열리는데, 가장 두드러진 것은 컴퓨터 올림피아드의 바둑 경기이다.KGS Go[62] Server(월간)와 Computer[63] Go Server(계속)의 프로그램 간 정규적이고 격식을 차리지 않는 경쟁.

역사

첫 번째 컴퓨터 바둑 대회는 Aconsoft가,[64] 첫 번째 정규 대회는 USENIX가 후원했습니다.그들은 1984년부터 1988년까지 운영되었다.이 대회들은 브루스 윌콕스의 첫 번째 경쟁 바둑 프로그램인 네메시스와 나중에 코스모스와 바둑의 많은 얼굴로 진화할 데이비드 포틀랜드의 G2.5를 소개하였다.

컴퓨터 바둑 연구의 초기 원동력 중 하나는 1985년에서 2000년 사이에 매년 열리는 세계 컴퓨터 바둑 콩그레스(또는 잉컵)에서 대만 은행가인 잉창기가 후원하는 비교적 큰 상인 잉 상이었다.이번 대회의 우승자는 짧은 경기에서 핸디캡으로 어린 선수들에게 도전할 수 있었다.만약 컴퓨터가 시합에서 이기면, 상금이 수여되고 새로운 상, 즉 더 적은 핸디캡으로 선수들을 이기면 더 큰 상금이 발표되었습니다.잉상 시리즈는 2000년에 만료되거나 4000만 NT달러에 1단 프로를 핸디캡 없이 이길 수 있는 프로그램이었다.마지막 우승자는 1997년 핸드톡으로, 11-13세의 아마추어 2-6 댄스를 상대로 11스톤 핸디캡 매치를 이겨 25만 NT달러를 청구했다.2000년에 상금이 만료되었을 때, 9스톤 핸디캡 [65]시합에서 승리해, 상금은 40만 NT달러였다.

많은 다른 큰 지역 바둑 대회들 (의회들)에는 컴퓨터 바둑 이벤트가 첨부되어 있었다.유럽 바둑 콩그레스(European Go Congress)는 1987년부터 컴퓨터 토너먼트를 후원해 왔으며, USENIX는 1988년부터 2000년까지 매년 미국 바둑 콩그레스(US Go Congress)에서 열리는 미국/북미 컴퓨터 바둑 챔피언십으로 발전했다.

일본은 1995년부터 컴퓨터 바둑 대회를 후원하기 시작했다.FOST컵은 1995년부터 1999년까지 매년 도쿄에서 개최되었다.그 대회는 기후현 오가키시에서 2003년부터 2006년까지 매년 개최되는 기후 챌린지로 대체되었다.컴퓨터 Go UEC컵은 2007년부터 매년 개최되고 있다.

컴퓨터 게임에서의 채점 공식화

두 컴퓨터가 서로 바둑을 둘 때, 이상적인 것은 실제 인간의 개입을 피하면서 두 사람이 바둑을 하는 것과 같은 방식으로 다루는 것이다.단, 이것은 종료 게임 스코어링 중에는 어려울 수 있습니다.가장 큰 문제는 표준화된 GTP(Go Text Protocol)를 사용하여 통신하는 바둑 소프트웨어가 스톤의 생사여부에 대해 항상 일치하지 않는다는 것이다.

서로 다른 두 프로그램이 "대화"하여 충돌을 해결할 수 있는 일반적인 방법은 없지만, 이 문제는 대부분 중국어, 트롬프-테일러 또는 AGA(American Go Association) 규칙을 사용하여 회피됩니다.AGA는 보드 상의 돌의 상태에 대해 더 이상 이견이 없을 때까지 게임을 계속해야 합니다.KGS Go 서버와 같이 실제로는 서버는 특별한 GTP 명령을 2개의 클라이언트프로그램에 송신함으로써 분쟁을 중재할 수 있습니다.이 명령어는 특정 그룹의 상태에 대한 의문이 없어질 때까지 스톤을 계속 배치해야 함을 나타냅니다(모든 데드스톤이 캡처되었습니다).CGOS Go Server는 보통 게임이 채점 단계에 이르기도 전에 프로그램이 종료되는 것을 확인하지만, 그럼에도 불구하고 완전한 플레이아웃이 필요한 트롬프-테일러 규칙의 수정 버전을 지원합니다.

이러한 룰 세트는, 일본 룰로 경기 종료시에 승리 위치에 있던 프로그램(양쪽의 플레이어가 패스했을 경우)은, 해결 국면에서 플레이가 좋지 않기 때문에 패할 가능성이 있는 것을 의미하지만, 이것은 일반적인 일이 아니고, 모든 에리어 룰 세트에서는 게임의 통상적인 부분으로 여겨진다.

위의 시스템의 주요 단점은 일부 규칙 집합(일본의 전통적인 규칙 등)이 이러한 추가 동작을 하는 플레이어를 벌칙하고 두 대의 컴퓨터에 추가 플레이아웃을 사용할 수 없다는 것입니다.그러나 대부분의 현대 바둑 프로그램은 인간에 대한 일본의 규칙을 지원하며, 바둑과 채점 모두에서 유능하다(Fuego, Many Faces of Go, SmartGo 등.

역사적으로, 이 문제를 해결하기 위한 또 다른 방법은 전문가로 하여금 최종 이사회를 판단하게 하는 것이었습니다.그러나 이는 결과에 대한 주관성과 전문가가 프로그램에서 본 것을 놓칠 수 있는 위험을 초래합니다.

테스트

컴퓨터 Go 엔진이 서로 경쟁할 수 있는 많은 프로그램을 사용할 수 있으며 거의 항상 GTP(Go Text Protocol)를 통해 통신합니다.

GOGUI와 그 addon gogui-twogtp를 사용하여 단일 컴퓨터 시스템에서 [66]두 개의 엔진을 서로 플레이할 수 있습니다.스마트고와 많은 페이스 오브 바둑도 이 기능을 제공한다.

KGS Go Server는 가능한 한 다양한 상대를 상대하기 위해 Go 엔진과바둑 엔진 플레이뿐만 아니라 바둑 엔진 대 인간 대결도 랭킹과 랭킹을 가리지 않는다.CGOS는 전용 컴퓨터 대 컴퓨터 Go 서버입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Metz, Cade (9 March 2016). "Google's AI Wins First Game in Historic Match With Go Champion". WIRED.
  2. ^ "AlphaGo victorious once again". 10 March 2016.
  3. ^ Bouzy, Bruno; Cazenave, Tristan (9 August 2001). "Computer Go: An AI oriented survey". Artificial Intelligence. 132 (1): 39–103. doi:10.1016/S0004-3702(01)00127-8.
  4. ^ Johnson, George (1997-07-29), "To Test a Powerful Computer, Play an Ancient Game", The New York Times, retrieved 2008-06-16
  5. ^ "Go, Jack Good".
  6. ^ Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda; Lanctot, Marc; Dieleman, Sander; Grewe, Dominik; Nham, John; Kalchbrenner, Nal; Sutskever, Ilya; Lillicrap, Timothy; Leach, Madeleine; Kavukcuoglu, Koray; Graepel, Thore; Hassabis, Demis (28 January 2016). "Mastering the game of Go with deep neural networks and tree search". Nature. 529 (7587): 484–489. Bibcode:2016Natur.529..484S. doi:10.1038/nature16961. ISSN 0028-0836. PMID 26819042. S2CID 515925.closed access
  7. ^ Wedd, Nick. "Human-Computer Go Challenges". computer-go.info. Retrieved 2011-10-28.
  8. ^ "'Huge leap forward': Computer that mimics human brain beats professional at game of Go".
  9. ^ Albert Zobrist(1970), 패턴 인식 및 바둑의 특징 추출 및 표현.위스콘신 대학교 박사 논문 (152 페이지)기술 보고서로도 발행
  10. ^ Millen, Jonathan K (April 1981). "Programming the Game of Go". Byte. p. 102. Retrieved 18 October 2013.
  11. ^ Webster, Bruce (November 1984). "A Go Board for the Macintosh". Byte. p. 125. Retrieved 23 October 2013.
  12. ^ Campbell, J A (1983). "Part III: Go Introduction". In Bramer, M A (ed.). Computer Game-Playing: Theory and Practice. Ellis Horwood Limited. p. 138. ISBN 0-85312-488-4.
  13. ^ Shotwell, Peter (2003). Go! More than a Game. Tuttle Publishing. p. 164. ISBN 0-8048-3475-X.
  14. ^ "CS-TR-339 Computer Go Tech Report". Retrieved 28 January 2016.
  15. ^ 예를 들어 intgofed.org Archived 2008년5월 28일 Wayback Machine을 참조하십시오.
  16. ^ Rémi Coulom (2007). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search". Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Revised Papers. H. Jaap van den Herik, Paolo Ciancarini, H. H. L. M. Donkers (eds.). Springer. pp. 72–83. CiteSeerX 10.1.1.81.6817. ISBN 978-3-540-75537-1.
  17. ^ "EGC 2010 Tampere News". Archived from the original on 14 August 2009. Retrieved 28 January 2016.
  18. ^ "KGS Game Archives". Retrieved 28 January 2016.
  19. ^ "Zen computer Go program beats Takemiya Masaki with just 4 stones!". Go Game Guru. Archived from the original on 2016-02-01. Retrieved 28 January 2016.
  20. ^ "「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる 初の公式戦". MSN Sankei News. Archived from the original on 24 March 2013. Retrieved 27 March 2013.
  21. ^ "codecentric go challenge – Just another WordPress site". Retrieved 28 January 2016.
  22. ^ Gibney, Elizabeth (2016). "Google AI algorithm masters ancient game of Go". Nature News & Comment. 529 (7587): 445–446. Bibcode:2016Natur.529..445G. doi:10.1038/529445a. PMID 26819021. S2CID 4460235. Retrieved 28 January 2016.
  23. ^ "Artificial intelligence: Google's AlphaGo beats Go master Lee Se-dol". BBC News Online. 12 March 2016. Retrieved 12 March 2016.
  24. ^ "Google's DeepMind defeats legendary Go player Lee Se-dol in historic victory". www.theverge.com. 9 March 2016. Retrieved 9 March 2016.
  25. ^ "Artificial intelligence: Go master Lee Se-dol wins against AlphaGo program". BBC News Online. 13 March 2016. Retrieved 13 March 2016.
  26. ^ "Google's AlphaGo AI beats Lee Se-dol again to win Go series 4-1". The Verge. 15 March 2016. Retrieved 15 March 2016.
  27. ^ Metz, Cade (2017-05-27). "After Win in China, AlphaGo's Designers Explore New AI". Wired.
  28. ^ "World's Go Player Ratings". May 2017.
  29. ^ "柯洁迎19岁生日 雄踞人类世界排名第一已两年" (in Chinese). May 2017.
  30. ^ Metz, Cade (2017-05-25). "Google's AlphaGo Continues Dominance With Second Win in China". Wired.
  31. ^ Silver, David; Schrittwieser, Julian; Simonyan, Karen; Antonoglou, Ioannis; Huang, Aja; Guez, Arthur; Hubert, Thomas; Baker, Lucas; Lai, Matthew; Bolton, Adrian; Chen, Yutian; Lillicrap, Timothy; Fan, Hui; Sifre, Laurent; Driessche, George van den; Graepel, Thore; Hassabis, Demis (19 October 2017). "Mastering the game of Go without human knowledge" (PDF). Nature. 550 (7676): 354–359. Bibcode:2017Natur.550..354S. doi:10.1038/nature24270. ISSN 0028-0836. PMID 29052630. S2CID 205261034.closed access
  32. ^ "5x5 Go is solved". Retrieved 28 January 2016.
  33. ^ 클링거, 팀, 메치너, 데이비드컴퓨터 바둑을 위한 아키텍처 (1996년)
  34. ^ a b c d Müller, Martin (January 2002). "Computer Go". Artificial Intelligence. 134 (1–2): 148–151. doi:10.1016/S0004-3702(01)00121-7.
  35. ^ a b "Fuego".
  36. ^ a b David Fotland. "Dan Level Go Software – Many Faces of Go".
  37. ^ a b c "Sjeng – chess, audio and misc. software".
  38. ^ a b "Archived copy". Archived from the original on 2008-08-10. Retrieved 2008-06-03.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  39. ^ a b "MyGoFriend – Gold Medal Winner 15th Computer Olympiad, Go (9x9)". Archived from the original on 2010-12-08.
  40. ^ "UCT".
  41. ^ "Mango". Archived from the original on 2007-11-03.
  42. ^ David Fotland. "Smart Games".
  43. ^ "Facebook trains AI to beat humans at Go board game – BBC News". BBC News. 27 January 2016. Retrieved 2016-04-24.
  44. ^ Ormerod, David (12 March 2016). "AlphaGo shows its true strength in 3rd victory against Lee Sedol". Go Game Guru. Archived from the original on 13 March 2016. Retrieved 12 March 2016.
  45. ^ "Computing Elo Ratings of Move Patterns in the Game of Go". Retrieved 28 January 2016.
  46. ^ 무함마드, 모신생각하는 게임 인공지능 134 (2002) : p150
  47. ^ "Triple Ko".
  48. ^ "Quadruple Ko".
  49. ^ "Molasses Ko".
  50. ^ "Moonshine Life".
  51. ^ "Computer Go Programming".
  52. ^ 11페이지: "Crasmaru는 바둑에서 특정한 제한된 형태의 생사 문제의 상태를 결정하는 것이 NP-완료임을 보여줍니다." (다음 참조 참조)Erik D. Demaine, Robert A. Hearn (2008-04-22). "Playing Games with Algorithms: Algorithmic Combinatorial Game Theory". arXiv:cs/0106019.
  53. ^ Marcel Crasmaru (1999). "On the complexity of Tsume-Go". Computers and Games. Lecture Notes in Computer Science. Vol. 1558. London, UK: Springer-Verlag. pp. 222–231. doi:10.1007/3-540-48957-6_15. ISBN 978-3-540-65766-8.
  54. ^ 바두기
  55. ^
  56. ^ "Archived copy". Archived from the original on 2006-11-28. Retrieved 2007-02-21.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  57. ^ "Pachi – Board Game of Go / Weiqi / Baduk".
  58. ^ Anders Kierulf. "SmartGo".
  59. ^ "STEENVRETER".
  60. ^ "Zen (go program)".
  61. ^ "Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning". Google Research Blog. 27 January 2016.
  62. ^ "Computer Go Tournaments on KGS".
  63. ^ "9x9 Go Server". Archived from the original on 2007-01-19. Retrieved 2007-03-25.
  64. ^ "Acorn 1984 The First Computer Go Tournament". computer-go.info.
  65. ^ David Fotland. "World Computer Go Championships". Retrieved 28 January 2016.
  66. ^ GoGUI를 사용하여 서로 컴퓨터 간 대전 2011-03-09 Wayback Machine에서 보관

추가 정보

외부 링크

Wikibooks는 다음과 같은 주제에 대한 책을 가지고 있습니다: Computer Go