컴퓨터 아리마

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Computer Arima" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2016년 3월) (이 템플릿 메시지 제거 방법과 시기 학습) 이 기사의 외부 링크 사용은 위키피디아의 정책이나 지침을 따르지 않을 수 있다. 너무 많거나 부적절한 외부 링크를 제거하고 적절한 경우 유용한 링크를 각주 참조로 변환하여 이 문서를 개선하십시오.(2016년 3월) (이 템플릿 메시지를 제거하는 방법 및 시기 학습) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

컴퓨터 아리마(Computer Arimaa)는 컴퓨터 프로그램에 의해 보드 게임 아리마(Arimaa)를 하는 것을 말한다.

2002년 인도계 미국인 컴퓨터 엔지니어 오마르 시드는 아리마에게 이 규칙을 발표하고 2020년까지 연간 1만 달러(표준, 기성 하드웨어로 실행)의 상금을 3게임 시리즈에서 3명의 최고 랭킹 인간 플레이어 각각을 물리칠 수 있는 첫 번째 컴퓨터 프로그램(표준, 기성 하드웨어로 실행)으로 발표했다.^[1]이 상은 2015년 한 컴퓨터 프로그램이 3명의 인간 플레이어와 7:2로 경기를 치렀을 때 청구되었다.^[2]그 게임은 여러 연구 논문의 주제가 되어 왔다.

아리마아의 주 공간

오프닝

각 플레이어가 경기 초반에 자신의 피스를 설정할 수 있는 다양한 방법의 수는 다음과 같다.

${\dbinom{16}{8}}\cdot {\dbinom {8}{8}}{8}}}\dbinom {6}{6}}}}\dbinom {4}}}\dbinom {1}{1}{1}}}}}}}{1}=64,864,800}$

플레이어는 16개의 가능한 사각형에 8마리의 토끼를 둘 수 있고, 그 다음에 남은 8개의 사각형에 2마리의 고양이, 6개의 나머지 사각형에 2마리의 개, 4개의 남은 사각형에 2마리의 말, 그리고 남은 두 개의 사각형 중 하나에 낙타 1마리, 그리고 사용하지 않는 마지막 사각형에 코끼리를 둘 수 있다.

각 플레이어가 64,864,800개의 오프닝 설정 중 하나로 게임을 시작할 수 있기 때문에, 오프닝을 위한 총 상태 공간은 다음과 같다.

${\displaystyle 64,864,800^{2}\약 4.2\cdot 10^{15}}$

Christ-Jan Cox가 석사학위 논문에서 말했듯이, 가능한 초기 상태의 수가 너무 많기 때문에, "[i]t는 오프닝 동작의 완전한 데이터베이스를 개발하는 것이 매우 어렵다.^[3]

인공지능 기술

재료평가

컴퓨터가 보드에 있는 조각들의 가치를 평가할 수 있어야 포획이나 교환이 바람직한지 평가할 수 있다.조각의 상대적 가치를 평가하는 것은 현재 진행 중인 아리마 연구 영역이다.현재 사용되고 있는 시스템으로는 DAPE와 FAME이 있다.

아리마 봇에 사용된 기술

아리마아를 플레이하는 인공지능 프로그램의 일부 또는 전부가 사용하는 기법은 다음과 같다.

• 비트보드
• 테이블 전환
• 조브리스트 해싱
• Minimax 및 Alpha 베타 가지치기
• 킬러 이동 및 리퓨테이션 테이블
• 정적평가함수
• 정지 검색
• 몬테카를로 나무 탐색
• UCT

아리마 봇에는 거의 사용되지 않는 기술

• 오프닝 북
• 엔드게임 테이블베이스

컴퓨터 성능

이 섹션은 검증을 위해 추가 인용구가 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 비소싱 소재에 도전하여 제거할 수 있음(2010년 3월) (이 템플릿 메시지 제거 방법 및 시기 학습)

아리마아의 여러 측면은 컴퓨터 프로그램이 훌륭한 인간 플레이어를 이기는 것을 어렵게 만든다.체스 게임을 하는 강력한 소프트웨어의 개발에 많은 노력을 기울였기 때문에, 체스에 적용되는 기술이 아리마아에게 왜 덜 효과적인지를 이해하는 것은 특히 관련이 있다.

브루트 포스 검색

가장 간단한 체스 프로그램은 물질적 고려가 지배하는 정적 위치 평가와 결합된 짐승 같은 힘 검색을 사용한다.그들은 수많은 가능한 움직임을 검토하지만, 한쪽이 다른 쪽보다 더 많은 조각을 가지지 않는 한 일련의 움직임 끝에 누가 승리하는지를 결정하는 데는 (인간과 비교해서) 좋지 않다.아리마 프로그램도 마찬가지지만 실제 성적이 그리 좋지 않다.

브리트 포스 검색을 아리마아에 적용하면 턴마다 각 플레이어가 갖는 엄청난 옵션 수에 따라 검색 깊이가 제한된다.계산적으로 플레이어가 사용할 수 있는 옵션의 수는 플레이어가 내려갈 수 있는 다른 경로의 수를 좌우한다.이것을 분기계수라고 한다.체스 게임의 평균 분기 계수는 약 35인 ^[4]반면 아리마아에서는 약 17,000이다.^[5]

이러한 서로 다른 분기 요인은 체스의 각 플레이어에 대해 8회전 깊이까지 검색할 수 있는 컴퓨터가 아리마아의 각 플레이어에 대해 약 3회전 깊이만 검색할 수 있다는 것을 의미한다.

${\displaystyle 35^{8}\ abouteq 17000^{3}}$

알파베타 가지치기

체스 소프트웨어의 경우, 브뤼트 포스 검색 깊이는 알파 베타 가지치기(알파 베타 가지치기)에 의해 거의 두 배가 되는데, 이것은 소프트웨어가 약한 움직임의 가능한 모든 연속성을 검사하지 않고도 한 동작이 다른 동작보다 낫다고 결론을 내릴 수 있게 해준다.상대가 한 번의 회신만으로 특정 동작을 분쇄할 수 있다면 다른 회신을 검토할 필요가 없어 검색 속도가 획기적으로 빨라진다.그러나 아리마아에서는 움직이는 쪽이 4단계마다만 전환되기 때문에 스텝 기반 검색에서 사용 가능한 컷오프 수가 줄어든다.

더욱이 알파베타 가지치기 유용성은 이동이 고려되는 순서에 따라 크게 좌우된다.나쁜 행보가 방치되기 위해서는 나쁜 행보다 좋은 행보가 먼저 고려되어야 한다.특히 다른 동작보다 동작이 훨씬 뛰어난 경우가 많기 때문에 동작 점검과 포착이 핵심이다.아리마 소프트웨어에서는 캡처가 더 드물기 때문에 알파베타 프루닝에 의해 제공되는 속도 상승이 더 적다.arimaa.com에서 열리는 등급 게임에서는 오직 3%의 스텝만이 포획이 되는데, 체스 동작의 약 19%는 포획이 된다.

대부분의 아리마 포지션에서, 특히 보드가 아직 혼잡할 때, 경기 초반으로 향할 때, 유능한 플레이어는 다음 두 바퀴 이내에 어떤 피스라도 잃는 것을 피할 수 있다.체스에 비해 아리마아는 어느 선수가 포획을 더 오래 지연시킬 수 있도록 허용하고 있다.실제로 체스에서 첫 포획의 중앙 이동 번호는 6번, 아리마에서는 12번이다.이 투쟁은 처음에는 아리마아에서 더 위치적이며, 미래의 어느 시점에서 불가피하게 포획하는 것을 중심으로 전개된다.이것은 누가 비물질적인 방법으로 우위를 점하고 있는지를 정확하게 판단하는 것의 중요성을 확대시킨다.그러므로 컴퓨터 프로그램의 강점은 그들의 약점만큼 중요하지 않다.

시작 단계에서 아리마 프로그램의 약점은 설정 단계에 의해 더욱 확대된다.체스에서 모든 경기는 같은 위치에서 시작된다.경기 전에 모든 표준 오프닝 동작에 대한 주식 리스트를 컴파일함으로써 체스 프로그램은 종종 "생각"을 시작하기 전에 십여 개 또는 그 이상의 뛰어난 동작을 할 수 있다.인간은 똑같은 일을 하지만, 더 작고 덜 신뢰할 수 있는 열린 기억을 가지고 있기 때문에, 체스에서 인간을 상대적으로 불리하게 만든다.이와는 대조적으로 아리마아는 첫 작품이 움직이기 전부터 수백만 가지의 가능한 설정 방법을 가지고 있다.이것은 프로그램들이 의미 있는 오프닝 북을 갖지 못하게 한다.

경기가 진행될수록 교류와 토끼의 발전은 그 위치를 더욱 개방적이고 전술적으로 만드는 경향이 있다.아리마 프로그램은 인간이 간과하는 전술적인 샷을 보기 때문에 전형적으로 이런 포지션에서 더 잘 한다.그러나 인간은 대개 보수적인 놀이에 의해 넓게 열린 자세를 피하고, 컴퓨터가 더 나빠지는 전략적 위치를 향해 각도를 세우는 것이 가능하다.보수적인 적수를 상대로 아리마아에서 그 자리를 박차고 나가는 것은 거의 불가능한 반면 체스에서는 단지 어려운 일이다.프로그램이 잘 되지 않는 작고 장기적인 이점을 축적함으로써 수비적인 플레이를 이겨내야 한다.

아리마아에게 적용되지 않는 컴퓨터 체스의 한 가지 추가 기술은 엔드게임 테이블베이스다.마스터 레벨의 체스 게임은 가끔 킹과 나이트 대 킹과 루크 같은 몇 개의 조각만 가지고 불분명한 엔딩게임으로 거래된다.역행 분석을 통해 그러한 모든 위치에서 정확한 이동의 전체 표를 작성할 수 있다.프로그램은 인간에 비해 상대적인 이점을 주는 '생각'을 새롭게 하기보다는 그런 자세로 미리 생성된 표를 참조하기만 하면 된다.이와는 대조적으로 아리마는 좀처럼 엔드게임에 이르지 않는다.같은 조각의 교환은 체스보다 덜 흔하기 때문에 아리마 한 판이 "거래를 줄였다"는 것은 드문 일이며 여전히 불분명하다.평균적인 아리마 게임은 8개의 캡처(체스 17개와 비교)밖에 되지 않으며, 상위 인간들은 예를 들어 2014 챌린지 경기 2차전을 예로 들며 단 한 점의 실점도 없이 아리마아 최고의 프로그램을 무찌를 수 있는 경우가 많다.포획 밀도가 낮은 또 다른 예로는 2012년 세계선수권대회 4강전이 있는데, 단 한 번의 포획, 골인 코끼리 희생을 특징으로 한다.

오마르 시드는 전통적인 인공지능 기법이 아리마아에게만 적당히 효과적이기 때문에 프로그래머들이 강력한 아리마 플레이 프로그램을 만들기 위해 새로운 인공지능 기법을 사용할 수밖에 없을 것이라고 기대하고 있다.세계 챔피언쉽 체스 프로그램을 구축하기 위한 성공적인 탐구는 게임을 성공적으로 하기 위한 많은 기술들을 만들어냈지만, 본질적으로 더 일반적인 추리에 전혀 기여하지 못했다; 사실, 체스 게임 프로그램의 기술은 인공지능의 어떤 정의에서 제외되었다; 아리마아의 목표는 티크라는 것이다.이 게임을 하는 데 관련된 학파들은 인공지능의 더 큰 목표에 도움을 줄 것이다.

시드의 인간애그스트 머신 챌린지 구조는 하드웨어의 진보가 아닌 AI 소프트웨어의 진보를 보상하는 데 초점이 맞춰져 있다.매년의 도전에서 프로그램은 전형적인, 저렴하고 기성품인 가정용 컴퓨터라는 기준에 따라, 시드가 직접 선택하고 제공하는 기계에서 운영된다.이 도전은 비록 아리마의 발명에 영감을 준 하드웨어 집약적인 접근법의 성공이었음에도 불구하고 최고 수준의 체스 선수들에게 도전할 때 사용되는 것과 같은 값비싼 멀티 프로세서 기계가 필요한 사람들에게는 개방되지 않을 것이다.시드는 2004년 챌린지 경기(512MB RAM을 탑재한 펜티엄 4 2.4GHz 시스템)에 사용된 컴퓨터조차 제대로 된 소프트웨어만 가동하면 챌린지 상을 탈 수 있는 하드웨어가 충분했다고 보고 있다.슈퍼컴퓨터는 이미 기존의 AI 소프트웨어를 이용해 무력으로 아리마아를 정복할 수 있는 힘을 갖고 있을 수 있으며, 하드웨어가 현재 속도로 계속 발전한다면 결국 개인용 컴퓨터도 그렇게 될 것이다.아리마 챌린지 상이 원래 2020년까지만 제공되는 이유다.

소프트웨어 개발자를 위한 리소스

브라이언 해스킨이 개발한 아리마 엔진 인터페이스는 아리마 엔진이 컨트롤러와 통신할 수 있도록 하는 프로토콜을 정의하고 있다.

문서에 따르면: "엔진은 아리마 게임의 상태를 파악하고 합법적인 움직임을 선택할 수 있는 프로그램이다.제어기는 엔진과 통신하고 제어하고자 하는 모든 것이다.이는 엔진이 하나의 위치를 분석하도록 하기 위한 간단한 스크립트부터 게임을 인간이나 다른 엔진과 함께 할 수 있도록 하는 GUI 프로그램에 이르기까지 모든 것이 될 수 있다."^[6]

아리마 엔진 인터페이스는 아리마 공식 웹사이트를 포함하여 프로토콜을 지원하는 모든 웹사이트에서 엔진을 제어하고 게임을 하기 위한 엔진과 컨트롤러, 문서화 및 다양한 스크립트의 구현을 포함한다.^[7][8]

연구논문

• Wu, David J. (2015). "Designing a Winning Arimaa Program" (PDF). ICGA Journal. 38 (1): 19–40. doi:10.3233/ICG-2015-38104.
• 아리마 챌린지 - MCTS와 알파베타 방법 비교 연구
  토머스 자클(Charles University, 프라하)의 논문2011년 10월
• 아리마 게임에서 순위 이동 및 평가
  데이비드 지안 우(Harvard College, Cambridge, Massachusetts, Massachusetts, Massachusetts, Massachusetts) 2011년 5
• 인공지능의 새로운 도전 아리마
  스테파노 칼리니(이탈리아 모데나와 레지오 에밀리아 대학)의 2010년 4월 논문
• MCTS와 게임 아리마의 방법
  2009년 12월 Tomas Kozelek (Charles University of Chocola, Charles University of Prague, 체코 프라하 대학)의 논문
• 언어 기하학을 이용한 아리마 게임 모델링
  2009년 9월 Joséoberto Mercado Vega와 Zvi Retchkiman Kösberg의 논문(이탈리아 밀라노에서 열린 제5회 컴퓨터 인텔리전스 및 게임 국제회의의 프로시저에서 발표됨
• 아리마 플레이를 위한 컴퓨터 에이전트 연구 및 구현
  Sam Miller (영국 Southampton University) 2009년 5월 논문
• 고선택적 검색을 안내하는 카테고리 계획, 패턴 및 이동
  2009년 5월 Gerhard Trippen의 논문 (2009년 진척된 컴퓨터 게임 12회의 스페인 팜플로나에서 발표)
• 아리마, 리얼 인텔리전스 게임?
  니콜라스 A의 발표바리가(University Tecnica Federico Santa Maria, 칠레 대학) 2006년 8월
• 게임 아리마와 부록 B의 분석과 구현
  Christ-Jan Cox (Universitit Maastricht, Institute for Knowledge and Agent Technology), 2006년 3월
• 강력한 아리마 플레이 프로그램 구축
  2005년 9월 Haizhi Zhong (Alberta University of Alberta, Computing Science)의 논문
• 세계 챔피언 아리마 프로그램 구축
  2004년 데이비드 포틀랜드(www.Smart-Games.com)의 논문
• Arima - 컴퓨터가 어려워지도록 설계된 새로운 게임
  오마르 시드와 아미르 시드의 논문; 국제 컴퓨터 게임 협회 저널; 2003년 6월

각주