평가 기능

Evaluation function
문자열 평가 함수는 eval을 참조하십시오.
기능 평가와 혼동하지 마십시오.
이 기사는 에 관한 시리즈의 일부입니다.
체스 프로그래밍
Chess Programming.svg
이사회의 표현
평가 기능
그래프 및 트리 검색 알고리즘
체스 컴퓨터
체스 엔진

휴리스틱 평가 함수 또는 정적 평가 함수로도 알려진 평가 함수는 게임 [1]트리의 위치(보통 리프 또는 터미널 노드)의 값 또는 장점을 추정하기 위해 게임 플레이 컴퓨터 프로그램에 의해 사용되는 함수입니다.대부분의 경우 값은 실수 또는 양자화된 정수이며, 종종 스톤인고나 체스의 폰과 같은 플레이 피스 값의 n분의 1에 해당하며, 여기서 n은 10분의 1, 100분의 1 또는 기타 편리한 분수일 수 있습니다.그러나 때때로 그 값은 단위 간격에서 3개의 값의 배열로 승, 무승부 및 손실 비율을 나타냅니다.es의 위치에 있습니다.

미해결 게임에 대한 평가 함수에 대한 분석적 또는 이론적 모델이 존재하지 않으며, 그러한 함수는 완전히 임시방편적인 것도 아니다.평가 함수의 구성은 자동화에 후보 함수를 삽입하고 후속 성능을 평가함으로써 경험적으로 결정된다.체스, 장기, 평가 기능의 일반적인 구성에 관한 중요한 증거가 현재 존재한다.

게임을 하는 컴퓨터 프로그램이 평가 기능을 사용하는 게임은 체스,[2] 바둑,[2] 장기,[2] 오셀로, 헥스, 백개먼,[3] [4][5]체커 등이다.또한, MuZero와 같은 프로그램이 등장하면서, 컴퓨터 프로그램들은 아타리 2600과 [6]같은 비디오 게임을 하기 위해 평가 기능을 이용하기도 한다.tic-tac-toe와 같은 일부 게임은 강력한 해결 방법을 제공하며 개별 솔루션 트리를 사용할 수 있기 때문에 검색이나 평가가 필요하지 않습니다.

검색과의 관계

이러한 평가의 트리는 일반적으로 몬테카를로 트리 검색 또는 알파 베타 검색과 같은 미니맥스 알고리즘과 같은 검색 알고리즘의 일부이다.이 값은 게임 트리가 해당 노드에서 게임 종료 시까지 확장되었을 때 상대적인 승리 확률을 나타내는 것으로 추정됩니다.이 기능은 현재 위치(즉, 조각이 있는 공간 및 서로 간의 관계)만 보고 위치의 이력을 고려하지 않거나 노드의 가능한 전방 이동(따라서 정적)을 탐색하지 않습니다.이는 전술적 위협이 존재하는 동적 포지션의 경우 평가 기능이 포지션에 대한 정확한 평가가 되지 않음을 의미한다.이러한 위치를 논쿼센트라고 합니다.평가 전에 위협을 해결하려면 중지 검색이라는 제한된 종류의 검색 확장이 필요합니다.평가 함수에 의해 반환되는 일부 값은 노드에서 승패 또는 무승부가 발생할 경우 경험적 접근 방식이 아닌 절대값입니다.

평가 기능에는 검색과 지식 사이에 복잡한 관계가 있습니다.심층 검색은 단기적인 전술적 요소를 줄이고 평가에서 보다 미묘한 장기 수평 위치 모티브를 선호합니다.또, 부호화된 지식의 유효성과 계산의 복잡성 사이에는 트레이드오프도 있습니다.상세한 지식의 계산에는 시간이 너무 걸려 퍼포먼스가 저하될 가능성이 있기 때문에, 정확한 지식에의 근사치가 높은 경우가 많습니다.평가 함수는 검색에 사용되는 확장 및 감소뿐만 아니라 검색의 공칭 깊이에 따라 달라지기 때문에 평가 함수에 대한 일반적이거나 독립적인 공식은 없습니다.어떤 어플리케이션에서 잘 동작하는 평가 기능은 다른 어플리케이션에서 효과적으로 동작하기 위해 일반적으로 실질적으로 재튜닝 또는 재트레이닝이 필요합니다.

체스에서

체스에서 평가 함수의 출력은 일반적으로 정수이며, 평가 함수의 단위는 일반적으로 폰이라고 합니다.'폰'이라는 용어는 체스 피스 상대값에서 설명한 바와 같이 플레이어가 포지션의 상대편보다 폰이 하나 더 있을 때의 값을 말합니다.정수 1은 보통 폰의 일부를 나타내며 컴퓨터 체스에서 일반적으로 사용되는 것은 폰의 100분의 1인 센티폰입니다.평가가 클수록 재료의 불균형이나 위치적 우위성이 나타나거나 재료의 승리가 임박했음을 나타냅니다.매우 큰 평가는 체크메이트가 임박했음을 나타낼 수 있습니다.평가함수는 이동권리의 값도 암묵적으로 부호화하는데, 폰의 작은 부분부터 승패까지 다를 수 있다.

수작업 평가 기능

역사적으로 컴퓨터 체스에서 평가 함수의 용어는 훈련 신경망을 통해 발견되는 것이 아니라 엔진 개발자에 의해 (수작업으로) 구성됩니다.수작업 평가 함수를 구성하기 위한 일반적인 접근법은 포지션의 값에 영향을 미치도록 결정되는 다양한 가중치 용어의 선형 조합이다.그러나 수작업 평가 함수의 모든 항이 선형인 것은 아니며 킹 세이프티 및 폰 구조와 같은 일부 항은 비선형입니다.각 항은 1차 요인(공간과 그 위에 있는 부품에만 의존하는 요인), 2차 요인(다른 공간에 대한 공간) 및 n차 요인(위치 이력에 대한 의존성)으로 구성된다고 간주할 수 있습니다.

수작업 평가 함수는 일반적으로 평가를 지배하는 재료 균형 항을 가집니다.재료에 사용되는 일반적인 값은 Queen=9, Rook=5, Knight 또는 Bishop=3, Pown=1이며, 일반적으로 킹에는 다른 모든 [1]조각의 총 값보다 큰 임의로 큰 값이 할당됩니다.또한, 일반적으로 폰의 가치보다 큰 총합이 되지 않는 일련의 위치 조건을 가지고 있지만, 체크메이트가 임박한 경우처럼 위치 조건이 훨씬 커질 수 있습니다.수작업 평가 함수에는 일반적으로 수십에서 수백 개의 개별 용어가 포함됩니다.

실제로 효과적인 수작업 평가 함수는 평가된 매개변수 목록을 확장하는 것이 아니라 위에서 설명한 것과 같은 중량의 매개변수 세트를 서로 상대적인 가중치를 신중하게 조정하거나 훈련함으로써 생성된다.이를 위해 마스터 게임, 엔진 게임, Lichees 게임, 또는 강화 학습과 같이 셀프 플레이 등 다양한 데이터베이스의 포지션을 활용합니다.

예

체스의 수작업 평가 함수의 예는 다음과 같습니다.

  • c1 * 재료 + c2 * 이동성3 + c * 킹 세이프티 + c4 * 센터 컨트롤 + c5 * 폰 구조 + c6 * 킹 트로피즘 + ...

각 항은 가중치에 차이 요인(흰색 재료 또는 위치 항 값에서 검은색)을 곱한 값입니다.

  • 재료 항은 각 조각에 폰 단위의 값을 할당하여 얻습니다.
  • 이동성은 플레이어가 사용할 수 있는 법적 움직임의 수 또는 각 피스에 의해 공격 또는 방어되는 공간의 총합입니다(우호 또는 반대 피스에 의해 점유되는 공간을 포함).효과적인 이동성 또는 부품이 이동할 수 있는 "안전한" 공간의 수도 고려될 수 있습니다.
  • 왕의 안전은 왕의 위치, 왕의 주변 또는 앞에 있는 전당포와 조각의 구성, 그리고 왕의 주변 공간에 있는 상반된 조각들에 대해 평가되는 상여와 벌칙의 집합이다.
  • 중앙 제어는 4개의 중앙 공간(때로는 확장된 중앙의 12개 공간)을 점유하거나 점유하는 폰과 피스의 수에서 파생됩니다.
  • 폰 구조는 이중으로 격리된 폰에 대한 벌칙과 같은 폰 구조의 다양한 강점과 약점에 대한 벌칙과 보너스 집합입니다.
  • 왕 트로피즘은 특정 조각, 특히 여왕과 기사들의 상대 왕과의 친밀함에 대한 보너스이다.

뉴럴 네트워크

반면로는 신경 네트워크 체스 엔진의 평가 기능의 늦은 1980s,[7][8]부터 쓰였다가 하드웨어로는 신경 네트워크 훈련하는 것이 필요하다면 그들은 컴퓨터 체스의 늦은 2010s까지 인기를 끌지 못 했을 만큼 그 당시 빠른 훈련 알고리즘과 네트워크 위상과 구조해 발전하지 않고 강하지 않았다교육 아직처음에 뉴럴 네트워크 기반 평가 기능은 일반적으로 전체 평가 기능에 대해 하나의 뉴럴 네트워크로 구성되며, 기판에서 선택된 입력 피쳐와 출력이 정수이며, 100의 값이 폰의 물질적 장점과 거의 동등하도록 정규화되었습니다.신경망의 매개변수는 일반적으로 강화 학습 또는 감독 학습을 사용하여 훈련된다.최근 컴퓨터 체스의 평가 기능은 여러 개의 신경망을 사용하기 시작했고, 각 신경망은 폰 구조나 엔드 게임과 같은 평가의 특정 부분을 위해 훈련되었다.이는 평가 기능이 신경망과 수작업 용어로 구성된 하이브리드 접근법을 가능하게 한다.

딥 뉴럴 네트워크는 2015년 매튜 라이의[9] 기린과 2017년 딥마인드의 알파제로가 평가 기능에서 딥 뉴럴 네트워크의 실현 가능성을 입증한 이후 컴퓨터 체스에서 거의 사용되지 않고 있다.분산 컴퓨팅 프로젝트 릴라 체스 제로(Reela Chess Zero)는 Deepmind의 Alpha Zero 논문 결과를 복제하기 위해 바로 시작되었습니다.네트워크의 크기 외에도 AlphaZero와 릴라 체스 제로에서 사용되는 신경망은 [10]평가용(값 헤드)과 이동 순서용(정책 헤드)의 두 가지 출력이 있기 때문에 기존 체스 엔진에서 사용되는 신경 네트워크와 다릅니다.또한 릴라 뉴럴 네트워크의 값 헤드의 출력을 기존의 체스 엔진에서 사용되는 지판 스케일에 근사하는 실수로 설정할 수 있지만, 기본적으로는 출력은 단위 [10]간격에서 각각 3개의 값의 벡터인 윈 드로우 손실 비율이다.심층뉴럴네트워크는 매우 크기 때문에 평가기능에 심층뉴럴네트워크를 사용하는 엔진은 일반적으로 평가기능을 효율적으로 계산하기 위해 그래픽 처리장치가 필요하다.

조각 정사각형 테이블

적어도 1990년대 초반 이후 평가에서 중요한 기술은 평가를 [11][12]위해 조각-제곱 표(조각-값 표라고도 함)를 사용하는 것이다.각 테이블은 체스판의 정사각형에 대응하는 64개의 값의 집합이다.피스퀘어 테이블의 가장 기본적인 구현은 각 플레이어의 피스 유형별로 별도의 테이블로 구성되어 있으며, 체스의 경우 총 12개의 피스퀘어 테이블이 됩니다.보다 복잡한 변종의 피스 정사각형 테이블은 컴퓨터 체스에서 사용되며, 가장 두드러진 것 중 하나는 킹피스 정사각형 테이블로, 스톡피시, 코모도 드래곤, Ethereal 및 다른 많은 엔진에서 사용되며, 각 테이블은 모든 유형의 피스의 위치를 플레이어의 킹에 대한 위치보다 고려합니다.e만.표의 값은 각 공간 상의 각 조각 위치에 대한 보너스/벌금으로, 분석적으로 정량화하기 어려운 많은 미묘한 요소들의 조합을 인코딩합니다.수작업 평가 기능에서는 오프닝/미드게임용 테이블과 엔드게임용 테이블 두 세트가 있는 경우가 있습니다.중간게임의 위치는 [13]둘 사이에 보간됩니다.

컴퓨터 체스에 사용되는 일반적인 수작업 평가 함수는 Piece-Square Table Only(피스-스퀘어 테이블만)입니다.이것은 재료 항과 두 세트의 피스 정사각형 테이블로 구성되어 있습니다.하나는 오프닝용이고 다른 하나는 엔드게임용입니다.그럼에도 불구하고 PeSTO는 컴퓨터 체스에서 사용되는 다른 많은 수작업 평가 기능을 수행할 수 있습니다.PeSTO는 2003년 Tomasz Michniewski에 의해 "Simplified Evaluation Function"이라는 이름으로 처음 개발되었으며, 현재 이름은 Ronald Friederich가 엔진 RofChade에 [14]PeSTO를 구현하면서 소개되었습니다.

2018년 유나스(Yu Nasu)[15][16]에 의해 컴퓨터 장기에서 개발되었으며, 오늘날 컴퓨터 체스에서 가장 일반적인 평가 기능은 효율적으로 업데이트 가능한 뉴럴 네트워크, 줄여서 NNUE로, 뉴럴 [17]네트워크의 입력으로 조각 정사각형 테이블만 있는 희박하고 얕은 뉴럴 네트워크입니다.사실, 가장 기본적인 NNUE 아키텍처는 위에서 설명한 12개의 조각-제곱 테이블로, 1개의 레이어만 있고 활성화 기능은 없는 뉴럴 네트워크입니다.킹피스 정사각형 테이블을 입력으로 사용하는 효율적으로 업데이트 가능한 뉴럴 네트워크 아키텍처는 Stockfish NNUE라고 불리는 Stockfish 파생 모델에 처음 포팅되어 2020년 [18]5월 30일 공개적으로 출시되었으며, 많은 다른 엔진에 채택된 후 2020년 [19][20]8월 6일 공식 Stockfish 엔진에 통합되었습니다.

게임 종료 테이블 베이스

주요 기사 : 엔드게임 테이블베이스 » 컴퓨터 체스

체스 엔진은 엔드게임에서 엔진을 완벽하게 작동시킬 수 있기 때문에 평가 기능에 엔드게임 테이블베이스를 자주 사용한다.

인고

역사적으로, 바둑의 평가 기능은 영토 통제, 돌의 영향, 포로 수, 그리고 보드 내 집단의 생사를 모두 고려했다.그러나 현대의 바둑 프로그램은 알파고, 릴라 제로, 파인 아트, 카타고 등 평가 기능에 주로 심층 신경망을 사용하고 있으며, 돌의 수보다 승/추첨/패율을 출력하고 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Shannon, Claude (1950), Programming a Computer for Playing Chess (PDF), Ser. 7, vol. 41, Philosophical Magazine, retrieved 12 December 2021
  2. ^ a b c Silver, David; Hubert, Thomas; Schrittwieser, Julian; Antonoglou, Ioannis; Lai, Matthew; Guez, Arthur; Lanctot, Marc; Sifre, Laurent; Kumaran, Dharshan; Graepel, Thore; Lillicrap, Timothy; Simonyan, Karen; Hassabis, Demis (7 December 2018). "A general reinforcement learning algorithm that masters chess, shogi, and go through self-play". Science. 362 (6419): 1140–1144. Bibcode:2018Sci...362.1140S. doi:10.1126/science.aar6404. PMID 30523106.
  3. ^ Tesauro, Gerald (March 1995). "Temporal Difference Learning and TD-Gammon". Communications of the ACM. 38 (3): 58–68. doi:10.1145/203330.203343. S2CID 8763243. Retrieved Nov 1, 2013.
  4. ^ Schaeffer, J.; Burch, N.; Y. Björnsson; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). "Checkers is Solved" (PDF). Science. 317 (5844): 1518–22. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228.
  5. ^ Schaeffer, J.; Björnsson, Y.; Burch, N.; Kishimoto, A.; Müller, M.; Lake, R.; Lu, P.; Sutphen, S. "Solving Checkers" (PDF). Proceedings of the 2005 International Joint Conferences on Artificial Intelligence Organization.
  6. ^ Schrittwieser, Julian; Antonoglou, Ioannis; Hubert, Thomas; Simonyan, Karen; Sifre, Laurent; Schmitt, Simon; Guez, Arthur; Lockhart, Edward; Hassabis, Demis; Graepel, Thore; Lillicrap, Timothy (2020). "Mastering Atari, Go, chess and shogi by planning with a learned model". Nature. 588 (7839): 604–609. arXiv:1911.08265. Bibcode:2020Natur.588..604S. doi:10.1038/s41586-020-03051-4. PMID 33361790. S2CID 208158225.
  7. ^ Thurn, Sebastian (1995), Learning to Play the Game of Chess (PDF), MIT Press, retrieved 12 December 2021
  8. ^ Levinson, Robert (1989), A Self-Learning, Pattern-Oriented Chess Program, vol. 12, ICCA Journal
  9. ^ Lai, Matthew (4 September 2015), Giraffe: Using Deep Reinforcement Learning to Play Chess, arXiv:1509.01549v1, retrieved 12 December 2021
  10. ^ a b "Neural network topology". lczero.org. Retrieved 2021-12-12.
  11. ^ Beal, Don; Smith, Martin C., Learning Piece-Square Values using Temporal Differences, vol. 22, ICCA Journal
  12. ^ Jun Nagashima; Masahumi Taketoshi; Yoichiro Kajihara; Tsuyoshi Hashimoto; Hiroyuki Iida (2002), An Efficient Use of Piece-Square Tables in Computer Shogi, Information Processing Society of Japan
  13. ^ Stockfish Evaluation Guide, retrieved 12 December 2021
  14. ^ Ronald Friederich (January 4, 2020). "PeSTO: Piece Square Tables Only". Retrieved December 12, 2021.
  15. ^ Yu Nasu (April 28, 2018). "Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi" (PDF) (in Japanese).
  16. ^ Yu Nasu (April 28, 2018). "Efficiently Updatable Neural-Network-based Evaluation Function for computer Shogi (Unofficial English Translation)" (PDF). GitHub.
  17. ^ Gary Linscott (April 30, 2021). "NNUE". GitHub. Retrieved December 12, 2020.
  18. ^ Noda, Hisayori (30 May 2020). "Release stockfish-nnue-2020-05-30". Github. Retrieved 12 December 2021.
  19. ^ "Introducing NNUE Evaluation". 6 August 2020.
  20. ^ Joost VandeVondele (July 25, 2020). "official-stockfish / Stockfish, NNUE merge". GitHub.
  • Slate, D 및 Atkin, L., 1983, "Ches 4.5, 인간 및 기계 2판 93-100"의 체스 기술에서 "Northwestern University Chess Program"스프링거-벌러그, 뉴욕, 뉴욕
  • Ebeling, Carl, 1987, All the Right Moves: 체스를 위한 VLSI 아키텍처(ACM Distinguished Defendation), 56-86. MIT Press, 캠브리지, MA

외부 링크