chess_engine_using_python

Python을 사용한 체스 엔진

이 저장소에는 Minimax , Alpha-Beta 가지치기 및 정지 검색 알고리즘을 사용하는 체스 엔진 구현이 포함되어 있습니다. 코딩에는 Docker 컨테이너 내부의 Jupyter 노트북이 사용됩니다. 모든 Jupyter Notebook은 Docker 이미지 형태로도 제공됩니다.

자세한 분석을 보려면 프로젝트 문서를 확인하세요.

사용된 외부 모듈

• 파이썬 체스

도커를 사용하여 실행하는 방법

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

체스 엔진 알고리즘

최소최대

이론

체스의 핵심은 minmax에서 체스를 하는 것입니다. Minmax는 일반적으로 검정색 조각을 MAX와 연관시키고 흰색 조각을 MIN과 연관시키며 항상 흰색 관점에서 평가합니다.

Minmax 알고리즘은 게임 이론의 적대적 검색 알고리즘입니다. 게임 트리를 활용하며 두 명의 플레이어 MIN과 MAX를 포함합니다. 두 플레이어 모두 다른 플레이어의 행동을 무효화하려고 합니다. Max는 결과를 최대화하려고 시도하는 반면 MIN은 결과를 최소화하려고 시도합니다. 두 플레이어 모두 최적의 플레이를 하고 있다는 가정 하에 교대로 플레이합니다. 최적의 플레이는 두 플레이어가 규칙에 따라 플레이하는 것을 의미합니다. 즉, MIN은 결과를 최소화하고 MAX는 결과를 최대화합니다.

minmax 알고리즘은 깊이 우선 탐색 방식을 활용하여 결과를 찾습니다. 또한 역추적과 재귀도 활용합니다. 알고리즘은 터미널 노드까지 순회한 다음 모든 하위 값을 비교하면서 역추적됩니다. 누구의 차례인지에 따라 최소값 또는 최대값이 선택됩니다. 그런 다음 값을 상위 항목으로 다시 전파합니다. 정적 평가 기능을 사용하여 각 리프 노드의 값을 결정합니다. 제로섬 게임(Zero-Sum Game)의 장점을 활용한 것입니다.

구현

Minmax를 사용하는 체스 엔진

시간 복잡도

Minmax는 게임 트리에서 깊이 우선 검색(DFS)을 사용하므로 minmax 알고리즘의 시간 복잡도는 O(b**m) 입니다. 여기서 b는 게임 트리의 분기 요소이고 m은 트리의 최대 깊이입니다.

공간 복잡도

minmax 알고리즘의 공간 복잡도는 O(bm) 인 DFS와 유사합니다. 여기서 b는 게임 트리의 분기 요소이고 m은 트리의 최대 깊이입니다.

완전성

Minmax 알고리즘이 완료되었습니다. 유한 탐색 트리에서 해결책이 존재한다면 확실히 찾을 것입니다.

최적성

Minmax 알고리즘은 두 상대가 모두 최적으로 플레이하는 경우 최적입니다.

---

알파-베타 가지치기

이론

minmax 알고리즘은 몇 가지 분기를 잘라내어 최적화할 수 있습니다. 가지치기된 가지는 결과에 영향을 미치지 않는 가지입니다. 시간 복잡도가 개선됩니다. 이 버전의 minmax는 알파-베타 가지치기 기능이 있는 minmax로 알려져 있습니다. 알파-베타 알고리즘이라고도 합니다.
Alpha-Beta Pruning에는 Alpha와 Beta라는 두 가지 값이 있습니다. 다음은 알파와 베타에 관해 고려해야 할 몇 가지 사항입니다.

Alpha(α)에 대한 몇 가지 요점

• 알파는 MAX 경로를 따라 발견되는 가장 높은 값입니다.
• 알파 값은 움직일 때마다 계속 증가하거나 동일하게 유지되므로 알파의 초기 값은 음의 무한대입니다. 음의 무한대 이외의 값을 선택하면 모든 알파 값이 선택한 값보다 작은 시나리오가 발생할 수 있습니다. 그래서 우리는 가능한 가장 낮은 값을 선택해야 하는데, 그것은 음의 무한대입니다.
• 알파는 MAX 플레이어에서만 업데이트됩니다.

베타(β)에 관한 몇 가지 사항

• 베타는 MIN 경로를 따라 발견되는 가장 낮은 값입니다.
• 베타 값은 움직일 때마다 계속 감소하거나 동일하게 유지되므로 베타의 초기 값은 양의 무한대입니다. 양의 무한대 이외의 값을 선택하면 베타의 모든 값이 선택한 값보다 클 수 있는 시나리오가 발생할 수 있습니다. 그래서 우리는 가능한 최대값을 선택해야 하는데, 그것은 양의 무한대입니다.
• 베타 값은 MIN 플레이어에 의해서만 업데이트됩니다.

역추적하는 동안 알파 및 베타 값이 아닌 노드 값만 상위로 전달됩니다.

알파-베타 가지치기 조건:

 α >= β

이동 주문

알파베타 알고리즘의 효율성은 순회 순서에 따라 크게 달라집니다. 이는 시간 및 공간 복잡성에서 중요한 역할을 합니다.

최악의 주문

어떤 경우에는 게임 트리에서 노드나 하위 트리가 제거되지 않는 경우도 있습니다. 이 경우 게임 트리의 오른쪽 하위 트리에서 가장 좋은 이동이 발생합니다. 이로 인해 시간 복잡도가 증가합니다.

이상적인 주문

이 경우 노드와 하위 트리의 최대 개수가 정리됩니다. 가장 좋은 움직임은 왼쪽 하위 트리에서 발생합니다. 시간과 공간의 복잡성을 줄여줍니다.

구현

Alpha-Beta Pruning을 사용하는 체스 엔진

시간 복잡도

알파 베타 알고리즘은 게임 트리에서 깊이 우선 검색(DFS)도 사용합니다.

• 최악의 순서인 경우: O(b^m)
• 이상적인 순서의 경우: O(b^m/2)

공간 복잡도

• 최악의 주문의 경우: O(bm)
• 이상적인 순서의 경우: O(b(m/2))

완전성

알파-베타 알고리즘이 완료되었습니다. 유한 탐색 트리에서 해결책이 존재한다면 확실히 찾을 것입니다.

최적성

알파-베타 알고리즘은 두 상대 모두 최적의 플레이를 하고 있을 때 최적입니다.

---

정지 검색

정지 검색은 최소-최대를 사용한 알파-베타 가지치기 위에 수정된 것입니다. 조용하다는 것은 조용하다는 뜻이다. 이 검색은 조용한 움직임만 평가합니다. 즉, 특정 깊이 이후에는 캡처 동작만 사용하여 다음 동작을 계산합니다. 정지 검색을 사용하면 지평선 효과를 피할 수 있습니다.
지평선 효과는 특정 깊이까지만 검색할 때 발생하지만, 한 수준 더 깊게 보면 이동하면 점수가 더 낮아질 수 있습니다. 정지 검색은 이를 방지하기 위해 캡처 이동만 사용합니다. 또한 정지 검색은 다양한 수준에서 분기 요인을 줄여 빠른 알고리즘을 구현합니다.

시간 복잡도

정지 검색 알고리즘은 게임 트리에서 깊이 우선 검색(DFS)도 사용합니다.

• 최악의 순서인 경우: O(b^m)
• 이상적인 순서의 경우: O(b^m/2)

공간 복잡도

• 최악의 주문의 경우: O(bm)
• 이상적인 순서의 경우: O(b(m/2))

완전성

정지 검색 알고리즘이 완료되었습니다. 유한 탐색 트리에서 해결책이 존재한다면 확실히 찾을 것입니다.

최적성

정지 검색 알고리즘은 두 상대가 모두 최적으로 플레이하는 경우 최적입니다.

---

핵심 내용

• 이동당 탐색되는 노드는 Minmax에 비해 Alpha Beta에서 10배 감소합니다.
• 최적의 움직임을 찾는 데 걸리는 시간도 Minmax에 비해 Alpha Beta에서 10배 단축되었습니다.
• 정지 검색은 더 높은 깊이에서 잘 수행됩니다.
• 정지 검색은 세 가지 알고리즘 중 가장 빠른 알고리즘입니다.
• 정지 검색은 더 적은 수의 노드를 평가합니다.
• 정지 검색을 제대로 처리하지 않으면 반복적인 이동이 발생할 수 있습니다.