컴퓨터 오델로

Computer Othello
아케이드 게임은 컴퓨터 오델로(비디오 게임)를 참조하십시오.
컴퓨터 오델로
Ntest computer othello.jpg
NTest - 강력한 오델로 프로그램

컴퓨터 오셀로는 컴퓨터 하드웨어와 오셀로의 게임을 할 수 있는 컴퓨터 소프트웨어를 포괄하는 컴퓨터 구조를 말한다.

유용성

NTest, 사이오, 에닥스, 카시오, 포인티 스톤, 헤라클스, WZebra, 로지스텔로 등 인터넷에서 무료로 다운로드할 수 있는 오셀로 프로그램이 많다.이 프로그램들은, 어떤 최신 컴퓨터에서도 실행될 때, 최고의 인간 플레이어들이 쉽게 패배하는 게임을 할 수 있다.움직임의 결과는 컴퓨터와 인간 모두에게 예측 가능하지만, 컴퓨터는 그것들을 더 잘 예측하기 때문이다.[1]

검색기법

컴퓨터 오셀로 프로그램은 게임 트리를 사용하여 가능한 모든 법적 움직임을 검색한다.이론적으로, 그들은 모든 위치/노드를 조사하는데, 각각의 위치가 한 플레이어에 의해 움직이는 것을 "플라이"라고 부른다.이 검색은 특정 최대 검색 깊이 또는 프로그램이 최종 "리프" 위치에 도달할 때까지 계속된다.

미니맥스나 네가맥스라고 알려진 이 접근방식의 순진한 실행은 실제적인 시간 내에 작은 깊이로만 검색할 수 있기 때문에 좋은 움직임을 찾기 위한 탐색 속도를 크게 높일 수 있는 다양한 방법이 고안되었다.이것들은 알파-베타 가지치기, 네가스코트, MTD(f), 네가크*[2]에 기초한다.알파벳 알고리즘은 어차피 사용되지 않을 케이스를 제거해 미니맥스 검색 루틴을 앞당기는 방식이다.이 방법은 나무의 다른 모든 레벨이 최대화되고 모든 레벨이 최소화된다는 점을 활용한다.[3]

또한 검색된 트리의 크기를 줄이기 위해 몇 가지 경험적 접근법이 사용된다: 양호한 이동 순서, 전환 테이블, 선택적 검색.[4]

프로세서나 코어가 여러 개인 컴퓨터에서 검색 속도를 높이기 위해 "병렬 검색"을 구현할 수 있다.최근 프로그램에서는[5] YBWC가[6] 선호하는[7] 접근방식으로 보인다.

멀티프로브 컷

Multi-ProbCut은 검색 트리의 알파-베타 가지치기 작업에 사용되는 경험적 경험이다.[8]ProbCut 경험적 접근법은 깊이와 얕은 점수 사이의 선형 회귀 분석을 사용하여 검색 트리의 더 깊은 수준에서 평가 점수를 추정한다.Multi-ProbCut은 이 접근방식을 검색 트리의 여러 레벨로 확장한다.선형 회귀 자체는 이전의 트리 검색을 통해 학습되어 휴리스틱을 일종의 동적 검색 제어로 만든다.[9]특히 오셀로와 같은 게임에서 더 깊은 수준의 평가 점수와 더 낮은 수준의 평가 점수 사이에 강한 상관관계가 있는 게임에서 유용하다.[10][11]

평가 기법

평가 기능을 만드는 데는 세 가지 다른 패러다임이 있다.

디스크-제곱 테이블

사각형마다 값이 다르다 - 모서리가 좋고 모서리 옆에 있는 사각형이 나쁘다.대칭을 무시한 채 보드에 10개의 다른 위치가 있으며, 각각 블랙디스크, 화이트디스크, 비어있는 세 가지 가능성 각각에 대한 값을 부여한다.보다 정교한 접근방식은 게임의 다른 단계에서 각 포지션에 대해 서로 다른 가치를 갖는 것이다. 예를 들어, 코너는 엔드게임보다 오프닝과 미드게임 초반에 더 중요하다.[12]

이동성 기반

대부분의 인간 플레이어는 이동성(사용 가능한 이동 횟수)을 극대화하고 프런티어 디스크(빈 사각형에 인접한 디스크)를 최소화하기 위해 노력한다.선수 이동성과 상대 이동성이 계산되고, 선수 이동성과 상대 이동성이 계산된다.[13]이러한 조치는 매우 빨리 발견될 수 있으며, 경기력을 크게 향상시킨다.대부분의 프로그램은 에지와 코너 구성에 대한 지식을 갖고 있으며, 인간 플레이어가 사용하는 또 다른 전략인 미드게임 초반에 디스크 수를 최소화하려고 노력한다.[12]

패턴 기반 / 패턴 계수

이동성 극대화와 국경선 최소화는 함께 추가할 수 있는 로컬 구성으로 나눌 수 있다. 일반적인 구현은 각 행, 기둥, 대각선 및 코너 구성을 개별적으로 평가하고 값을 합산하는 것이며, 여러 가지 다른 패턴을 평가해야 한다.[12]모든 구성의 가치를 결정하는 과정은 모든 게임에서 각 게임 스테이지의 각 구성에 대한 통계를 계산하고 강자들 사이에서 플레이되는 게임의 큰 데이터베이스를 가져가는 것이다.[12]

최종 디스크 차이를 예측하기 위한 가장 일반적인 선택은 이긴 쪽이 디스크 수에 해당하는 보너스를 받는 가중 디스크 차이 측정치를 사용한다.[12]

오프닝 북

책을 펴는 것은 컴퓨터 프로그램을 돕는 데 도움이 되는데, 그것은 빈약한 개구부에 대항하는 좋은 방법으로 여겨지는 공통적인 개구부를 준다.모든 강력한 프로그램들은 각각의 게임이 끝나면 책을 열어보고 책을 자동으로 업데이트한다.게임 데이터베이스의 모든 게임에서 모든 포지션을 거치고 어떤 데이터베이스 게임에서도 플레이되지 않는 최상의 동작을 결정하기 위해, 이전에 검색된 포지션을 기록하기 위해 전환 테이블을 사용한다.다시 그런 자리를 검색할 필요가 없다는 뜻이다.[12]각 포지션에 대해 심층적인 검색을 수행해야 하므로 시간이 많이 걸리지만, 일단 이 작업이 끝나면 책을 업데이트하기가 쉽다.매 경기가 끝난 후, 모든 새로운 포지션들이 최고의 일탈을 찾아 나선다.

기타 최적화

더 빠른 하드웨어와 추가 프로세서는 더 깊은 플라이 검색과 같은 오델로 플레이 프로그램 능력을 향상시킬 수 있다.

오델로 해결

게임을 하는 동안 플레이어는 번갈아 움직인다.컴퓨터는 흰색을 사용하는 반면 인간 플레이어는 검은 카운터를 사용한다.인간 플레이어가 게임을 시작한다.[1]오셀로는 4×4와 6×6 보드 위에서 강하게 해결되는데, 두 번째 선수(흰색)가 완벽한 플레이로 승리한다.[14][15]표준 8×8 보드에서는 미해결 상태로 남아 있지만, 컴퓨터 분석은 그러한 선이 완전히 입증되지는 않았지만 수천 개의 추첨선, 즉 추첨 경로를 제공한다.[16]

오델로4×4

오셀로 4x4는 매우 작은 게임 트리를 가지고 있으며, 가능한 모든 포지션(약 1,000만 개)을 생성하는 미니맥스 방식을 사용하는 많은 단순한 오셀로 프로그램에 의해 1초도 안 되는 시간 내에 해결되었다.결과는 백인이 +8마진(3-11)으로 승리하는 것이다.[14]

오델로6×6번길

오셀로 6x6은 모든 가능한 포지션(약 3조 6천억)을 창출하는 미니맥스 방식을 사용하는 많은 단순한 오셀로 프로그램에 의해 100시간 이내에 해결되었다.결과는 백인이 +4마진(16-20)으로 승리하는 것이다.[17]

오델로8×8

오셀로 8x8 게임트리 크기는 10개54 노드로 추산되며, 법정 직급은 10개28 미만으로 추산된다.그 경기는 여전히 미해결로 남아 있다.솔루션은 고속 병렬 하드웨어의 상위 프로그램 또는 분산 연산을 통한 집중적인 계산을 사용하여 찾을 수 있다.

몇몇 최고의 프로그램들은 현재 수년 동안 책을 확장해왔다.그 결과, 많은 대사가 어느 한쪽을 위해 비기거나 이기고 있다.대각선, 수직선, 평행선 3개의 주요 개구부에 대해서는 대각선과 수직선이 모두 도면선으로 이어지는 반면 평행선 개구부는 검은색에 유리한 것으로 보인다.또한 대각선 개구부가 수직 개구부보다 더 크게 보인다.[18]평행 오프닝은 흑인 선수에게 강한 장점이 있어 항상 완벽한 플레이로 승리를 거둘 수 있다.[19]

컴퓨터 오셀로의 이정표

a b c d e f g h
1 a1X b1X c1X d1X e1X f1X g1X h1X 1
2 a2X b2X c2O d2X e2X f2X g2X h2X 2
3 a3X b3X c3X d3O e3X f3X g3O h3X 3
4 a4X b4X c4O d4X e4X f4O g4X h4X 4
5 a5X b5X c5X d5X e5X f5X g5X h5X 5
6 a6X b6X c6X d6O e6X f6X g6X h6X 6
7 a7X b7X c7O d7O e7O f7X g7X h7X 7
8 a8X b8X c8X d8X e8X f8X g8X h8X 8
a b c d e f g h
로지스텔로 vs.무라카미 다케시(4경기)
  • 1977: Scientific American은 BCPL에 N. J. D. Jacobs가 작성한 Otelo/Reversi 프로그램에 대해 가장 일찍 알려진 언급을 했다.[20] 바이트는 10월에 "Otelo, a New Ederal Game"을 BASIC 타이핑 프로그램으로 출판했다.[21]
  • 1977: Creative Computing은 FORTRAN에서 Ed Wright가 쓴 Othero 버전을 출판했다.[22][23]
  • 1978년: 닌텐도는 오락실에서 컴퓨터 오델로를 발매한다.[24]
  • 1980: 오셀로 프로그램 더 무어(마이크 리브, 데이비드 레비 작)가 세계 챔피언 이노우에 히로시와의 6연전에서 1승을 거뒀다.[25]노스웨스턴 대학의 피터 W 프레이는 컴퓨터와 인간 오셀로 전략을 BYTE로 논의했고, 그의 TRS-80 오셀로 게임에 대해 토론했는데, 프레이는 이 게임이 CDC 6600에서 실행되는 라이트의 버전을 쉽게 물리쳤다고 주장했다.[23]카네기 멜론 대학의 폴 로젠블룸은 IAGO를 개발했고, IAGO는 노스웨스턴 대학교 컴퓨터 토너먼트에서 3위를 차지했다.[26]IAGO가 The Moor를 연기할 때, IAGO는 영구적으로 조각을 포착하고 상대의 기동성을 제한하는데 더 뛰어났다.[25]
  • 1981: DEC KA10에서 뛰는 IAGO는 산타 크루즈 대학교에서 열린 산타 크루즈 오픈 오셀로 토너먼트에서 19명의 다른 참가자들보다 앞서서, 유일한 무패 기록을 세웠다.찰스 히스의 TRS 80 기반 게임은 2위로 끝났다.마이크로컴퓨터 CPU 기반 엔진은 몇 개의 메인프레임과 미니컴퓨터를 제치고 2위부터 7위까지 차지했다; 프레이는 컴퓨터 오셀로가 더 빠른 플로팅 포인트 산술과 같은 큰 컴퓨터의 몇 가지 장점으로부터 혜택을 받지 못하기 때문이라고 추측했다.[26]
  • 1980년대 후반: 카이-푸 리와 산조이 마하얀은 오델로 프로그램 Bill을 만들었는데, 이 프로그램은 IAGO와 비슷했지만 베이시안 학습을 통합했다.빌은 믿을 수 있게 IAGO를 이겼다.[25]
  • 1992: Michael Buro는 Othero 프로그램 Logistello에 대한 작업을 시작했다.로지스텔로의 검색 기법, 평가 기능, 패턴 지식 기반 등이 이전 프로그램보다 우수했다.로지스텔로는 10만 경기 이상을 자력으로 소화하며 경기를 완벽하게 소화했다.[25]
  • 1997: 로지스텔로는 세계 챔피언 무라카미 다케시와의 6게임 경기에서 매 경기 승리했다.비록 오델로 프로그램이 인간보다 강하다는 것에 큰 의심은 없었지만, 컴퓨터와 군림하는 세계 챔피언의 마지막 경기 이후 17년이 되었다.1997년 경기가 끝난 후, 로지스텔로는 그 어떤 인간 선수보다도 월등히 뛰어났다는 것에 더 이상 의심의 여지가 없었다.[27][25]
  • 1998년: 마이클 부로는 로지스텔로를 은퇴시켰다.오셀로에 대한 연구 관심은 다소 사그라들었지만, Ntest, Saio, Edax, Cassio, Zebra, Herakles 등 일부 프로그램들은 계속 개발되었다.[25]
  • 2004: Ntest는 로지스텔로보다 훨씬 더 강한, 가장 강력한 프로그램이 되었다.
  • 2005: Ntest, Saio, Edax, 시라노, Zebra는 로지스텔로보다 현저하게 강해졌다.Ntest와 Zebra는 은퇴했다.
  • 2011: 사이오, 에닥스, 시라노는 로지스텔로나 다른 프로그램보다 훨씬 빨라졌다.

오델로/리버디 상위 프로그램 목록

  1. 크리스 웰티의 NTest(Ntest)
  2. 리처드 들로메의 에닥스 (에닥스)
  3. 로지스텔로 by Michael Buro

참고 항목

메모들

  1. ^ a b Dcs.gla.ac.uk 웨이백 머신에 2011-01-03 보관
  2. ^ 장크리스토프 웨일(1992년).NegaC* 검색.ICCA Journal, 15권, 1권, 3-7권.
  3. ^ Armanto, Hendrawan; Santoso, Joan; Giovanni, Daniel; Kurniawan, Faris; Yudianto, Ricky; Gunawan, Steven (October 2012). "Evolutionary Neural Network for Othello Game". Procedia - Social and Behavioral Sciences. 57: 419–425. doi:10.1016/j.sbspro.2012.09.1206.
  4. ^ M사 부로 "멀티프로브컷과 오셀로를 위한 새로운 고품질 평가 기능" 게임즈 인 AI 리서치, H.J 판 덴 헤릭, H. 이이다(eda), ISBN 90-621-6416-1, 2000
  5. ^ 장크리스토프 웨일(1996년).ABDA 분산 미니맥스 검색 알고리즘.1996년 ACM 컴퓨터 과학 회의의 진행, 페이지 131-138.ACM, 뉴욕, 뉴욕, N.Y.는 ICCA 저널 제19권 1호를 재인쇄했다.
  6. ^ 마크 브로킹턴(1997년).KEYANO Unplugged - 오셀로 프로그램의 건설.기술 보고서 TR-97-05, 앨버타 대학교 컴퓨터 과학 학부.
  7. ^ 레이너 펠드만, 피터 미슬리위츠, 버크하르트 모니엔(1991)이다.완전 분산형 체스 프로그램.컴퓨터 체스 6의 발전
  8. ^ Buro, Michael (1997). "Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello". Games in AI Research. 34 (4): 77–96.
  9. ^ Bulitko, Vadim; Lustrek, Mitja; Schaeffer, Jonathan; Bjornsson, Yngvi; Sigmundarson, Sverrir (1 June 2008). "Dynamic control in real-time heuristic search". Journal of Artificial Intelligence Research. 32: 419–452. doi:10.1613/jair.2497.
  10. ^ Fürnkranz, Johannes (2001). Machines that learn to play games Guide books. Nova Science Publishers, Inc.6080 Jericho Tpke. Suite 207 Commack, NYUnited States: Nova Science Publishers, Inc. pp. 11–59. ISBN 978-1-59033-021-0.{{cite book}}: CS1 maint : 위치(링크)
  11. ^ Heinz, Ernst A. (2013). Scalable Search in Computer Chess: Algorithmic Enhancements and Experiments at High Search Depths. Springer Science & Business Media. p. 32. ISBN 978-3-322-90178-1.
  12. ^ a b c d e f 2007년 4월 2일 오델로 프로그램 작성
  13. ^ Ntest 작동 방식 2005년 3월 2일 웨이백 머신에 2011-11-09 보관
  14. ^ a b Othero 4 × 4 Wayback Machine에 보관된 2011-07-07
  15. ^ 2004년 11월 17일 웨이백 머신에 2009년 11월 1일 보관된 두 가지 대체 출발 위치에서 6x6 Othelo의 완벽한 플레이
  16. ^ 2008년 11월 01일 Edax 4.0 개론서
  17. ^ 4x4 및 6x6 오셀로 문제 해결을 위한 무료 소프트웨어
  18. ^ "Strongest othello program in term of artificial intelligent". Archived from the original on 2007-01-09. Retrieved 2010-04-05.
  19. ^ 사이오의 책
  20. ^ 가드너, 마틴수학 오락.1977년 4월 과학계 미국인
  21. ^ Duda, Richard O (October 1977). "Othello, a New Ancient Game". BYTE. pp. 60–62.
  22. ^ Wright, Ed (November–December 1977). "Othello". Creative Computing. pp. 140–142. Retrieved 18 October 2013.
  23. ^ a b Frey, Peter W (July 1980). "Simulating Human Decision-Making on a Personal Computer". BYTE. p. 56. Retrieved 18 October 2013.
  24. ^ "Computer Othello - Videogame by Nintendo".
  25. ^ a b c d e f 웨이백머신에 보관된 2011-01-24 컴퓨터 게임의 역사
  26. ^ a b Frey, Peter W (July 1981). "The Santa Cruz Open / Othello Tournament for Computers". BYTE. p. 16. Retrieved 18 October 2013.
  27. ^ 무라카미 다케시 올해의 오델로 경기 vs.로지스텔로

외부 링크