간단한 체스 AI 제작을위한 단계별 가이드

간단한 체스 AI를 만드는 데 도움이되는 몇 가지 기본 개념을 살펴 보겠습니다.

  • 이동 세대
  • 보드 평가
  • 미니 맥스
  • 알파 베타 가지 치기.

각 단계에서 시간이 오래 걸리는 체스 프로그래밍 기술 중 하나를 사용하여 알고리즘을 개선 할 것입니다. 각각이 알고리즘의 연주 스타일에 어떤 영향을 미치는지 보여 드리겠습니다.

GitHub에서 최종 AI 알고리즘을 볼 수 있습니다.

1 단계 : 생성 및 보드 시각화 이동

이동 생성에는 chess.js 라이브러리를 사용하고 보드 시각화에는 chessboard.js를 사용합니다. 이동 생성 라이브러리는 기본적으로 체스의 모든 규칙을 구현합니다. 이를 바탕으로 특정 보드 상태에 대한 모든 법적 움직임을 계산할 수 있습니다.

이동 생성 기능의 시각화. 시작 위치는 입력으로 사용되며 출력은 해당 위치에서 가능한 모든 이동입니다.

이러한 라이브러리를 사용하면 가장 흥미로운 작업에만 집중할 수 있습니다 : 최상의 움직임을 찾는 알고리즘 만들기.

가능한 모든 동작에서 임의의 동작을 반환하는 함수를 만드는 것으로 시작하겠습니다.

이 알고리즘은 매우 견고한 체스 플레이어는 아니지만 실제로 사용할 수있는 좋은 출발점입니다.

블랙은 무작위로 움직입니다. https://jsfiddle.net/lhartikk/m14epfwb/4에서 재생 가능

2 단계 : 위치 평가

이제 특정 위치에서 어느 쪽이 더 강한 지 이해해 봅시다. 이를 달성하는 가장 간단한 방법은 다음 표를 사용하여 보드의 조각의 상대 강도를 계산하는 것입니다.

평가 기능을 사용하여 가장 높은 평가를 제공하는 이동을 선택하는 알고리즘을 만들 수 있습니다.

유일하게 확실한 개선은 알고리즘이 가능한 한 조각을 캡처한다는 것입니다.

간단한 평가 기능을 통해 블랙이 재생됩니다. https://jsfiddle.net/lhartikk/m5q6fgtb/1/에서 재생 가능

3 단계 : Minimax를 사용하여 트리 검색

다음으로 알고리즘이 최적의 움직임을 선택할 수있는 검색 트리를 만듭니다. 이것은 Minimax 알고리즘을 사용하여 수행됩니다.

이 알고리즘에서는 가능한 모든 이동의 재귀 트리가 지정된 깊이까지 탐색되고 위치는 트리의 끝 "잎"에서 평가됩니다.

그 후, 우리는 흰색 또는 검은 색 이동 여부에 따라 자식의 가장 작은 값 또는 가장 큰 값을 부모 노드로 반환합니다. 즉, 각 수준에서 결과를 최소화하거나 최대화하려고합니다.

인공 위치에서 minimax 알고리즘의 시각화. 우리가 평가가 -50 인 위치에 도달 할 수 있음을 보장 할 수 있기 때문에 흰색에 대한 최선의 움직임은 b2-c3입니다.

minimax가 제정되면 알고리즘이 체스의 기본 전술을 이해하기 시작합니다.

깊이 수준이 2 인 Minimax. 재생 가능 : https://jsfiddle.net/k96eoq0q/1/

minimax 알고리즘의 효과는 우리가 달성 할 수있는 검색 깊이에 따라 크게 좌우됩니다. 다음 단계에서 개선 할 사항입니다.

4 단계 : 알파-베타 가지 치기

알파-베타 전정은 검색 트리에서 일부 분기를 무시할 수있는 minimax 알고리즘에 대한 최적화 방법입니다. 이를 통해 동일한 리소스를 사용하면서 minimax 검색 트리를 훨씬 더 깊이 평가할 수 있습니다.

알파-베타 가지 치기는 이전에 발견 된 이동보다 상황이 더 악화되는 이동을 발견하면 검색 트리의 일부 평가를 중지 할 수있는 상황을 기반으로합니다.

알파-베타 가지 치기는 minimax 알고리즘의 결과에 영향을 미치지 않으며 단지 더 빠릅니다.

알파-베타 알고리즘은 또한 좋은 움직임으로 이어지는 경로를 먼저 방문하면 더욱 효율적입니다.

알파-베타 가지 치기가 사용되고 나무가 설명 된 순서대로 방문되면 탐색 할 필요가 없습니다.

알파-베타에서는 다음 예제와 같이 minimax 알고리즘이 크게 향상되었습니다.

깊이가 4 인 검색을 수행하려는 경우 평가에 필요한 위치 수는

알파 AI 베타 버전의 체스 AI를 사용해 보려면이 링크를 따르십시오.

5 단계 : 개선 된 평가 기능

초기 평가 기능은 보드에서 찾은 재료 만 계산하므로 매우 순진합니다. 이를 개선하기 위해 조각의 위치를 ​​고려한 요소를 평가에 추가합니다. 예를 들어, 보드 중앙에있는 기사는 보드 가장자리에있는 기사보다 더 좋습니다 (더 많은 옵션이 있고 더 활성화되어 있기 때문에).

우리는 원래 체스 프로그래밍 위키에 설명되어있는 약간 조정 된 조각-제곱 테이블을 사용합니다.

시각화 된 조각-제곱 테이블이 시각화되었습니다. 조각의 위치에 따라 평가를 줄이거 나 늘릴 수 있습니다.

다음과 같은 개선으로, 우리는 최소한 캐주얼 플레이어의 관점에서 볼 때 "괜찮은"체스를 재생하는 알고리즘을 시작합니다.

검색 깊이가 3 인 평가 및 알파-베타 가지 치기 개선. https://jsfiddle.net/q76uzxwe/1/에서 재생 가능

결론

간단한 체스 게임 알고리즘의 장점은 바보 같은 실수를하지 않는다는 것입니다. 이것은 여전히 ​​전략적 이해가 부족하다고 말했다.

여기에 소개 된 방법을 사용하여 기본 체스를 재생할 수있는 체스 재생 알고리즘을 프로그래밍 할 수있었습니다. 최종 알고리즘의 "AI- 파트"(이동 생성 제외)는 200 줄의 코드로 기본 개념이 구현하기가 매우 간단합니다. 최종 버전은 GitHub에 있습니다.

알고리즘을 개선 할 수있는 몇 가지 추가 개선 사항은 다음과 같습니다.

  • 이동 주문
  • 더 빠른 이동 생성
  • 최종 게임 특정 평가.

자세한 내용을 보려면 체스 프로그래밍 위키를 확인하십시오. 여기에 소개 된 기본 개념을 넘어서 탐색하는 데 유용한 리소스입니다.

읽어 주셔서 감사합니다!