Python Algorithm Chapter8
Python Algorithm
적대적 탐색
1. 보드게임 구성 요소
제네릭을 사용하여 탐색 알고리즘에 필요한 모든 상태를 정의하는 간단한 기본 클래스를 정의하여 구현
특정 게임에 따라 상속받는 서브 클래스를 만들고, 서브클래스에서 탐색 알고리즘을 사용한다.
Piece클래스 : 말에 대한 기본 클래스Board클래스 : 게임의 상태 관리
탐색 알고리즘이 대답해야하는 항목
누구 차례인가?말은 현재 위치에서 어디로 움직일 수 있는가?이겼는가?무승부인가?
클래스의 조치
현재 위치에서 새 위치로 이동한다.플레이어의 말 위치를 평가하여 어느 쪽이 유리한지 확인한다.
2. 틱택토
3*3 사이즈의 격자 맵에서 세로, 가로, 대각선 줄 중 어느 하나라도 자신의 말로 채우면 이기는 게임
2.1 틱택토 상태관리
TTPPiece클래스 : 열거형 클래스에서Piece클래스 상속, 각 말을 나타내는 방법TTTBoard클래스 : 게임 상태를 저장하고, 서로 다른 두 말의 상태 추적 (위치(1차원리스트), 플레이어 턴)
TTTBoard 클래스는 변경 불가능한 자료구조이다. 따라서 게임이 진행될 때마다 변경되는 것이 아니라 새로운 TTTBoard 객체가 생성되는 것이다. 따라서 전 상황을 실수로 바꾸지 않고, 탐색을 이어 나갈 수 있다.
틱택토는 게임 끝까지 탐색할 수 있는 충분한 깊이이기 때문에 끝까지 탐색할 수 있다.
따라서 evaluate() 매서드로 승리, 무승부, 패배 시 점수를 차등적으로 반환할 수 있다.
2.2 최소최대 알고리즘
2인용 제로섬 게임의 최적의 이동을 찾는 고전 알고리즘
각 플레이어가 최대화 플레이어 또는 최소화 플레이어로 지정된 재귀함수를 사용하여 구현
최대화 플레이어는 이득 최대화, 최소화 플레이어는 이득 최소화하는 이동을 기저 조건에 도달할 때까지 재귀적으로 반복하여 호출한다. 기저 조건은 게임 종료 상태 혹은 최대 탐색 깊이이다.
-find_best_move() 작동에 대해 이해하지 못하였습니다.-
2.3 틱택토에서 최소최대 알고리즘 테스트하기
단위 테스트
- 다음 이동에 게임을 이기는 위치 테스트
- 상대방이 이기는 상황 막기
- 앞으로의 두 수 고려
최소최대 알고리즘을 사용할 때 적절한 자료 구조를 사용하는 것이 중요하다.
- 변경되는 수정 가능한 자료구조 불가
2.4 틱택토 AI
상대방 말의 움직임에 의해 생성된 위치만 평가한다.
3. 커넥트포
7x6 격자 맵에서 세로, 가로, 대각선 중 4개의 말을 연속으로 놓으면 이기는 게임
3.1 커넥트포 구현
-
C4Piece클래스 :TTTPiece클래스와 유사 (Piece클래스 상속) -
세그먼트 : 격자 위치 리스트의 리스트 이다. 즉, 4개의 격자 위치들인데, 4개가 모두 같은 색 말이면 그 플레이어가 이긴다. 세그먼트를 확인해서 승패를 확인할 수 있다.
-
C4Board클래스 :Column내부 클래스 사용(1장Stack클래스와 유사), 7개의 열 그룹으로 이해하면 나머지 코드 부분 작성이 쉽다. 각 열은 6개의 항목으로 제한된다.
is_win() 매서드에서 보드의 모든 세그먼트를 확인하여 _count_segment() 메서드를 사용하여 같은 색 말 4개 있는 세그먼트를 찾아서 승리를 결정한다.
is_draw 속성도 사용가능하다.
_evaluate_segment() 메서드는 세그먼트마다 점수를 메겨서 총점수를 평가할수 있다.
3.2 커넥트포 AI
minimax()와 find_best_move()함수를 똑같이 사용할 수 있지만, 계산 깊이를 3개까지만으로 제한한다. 시간이 너무 오래 걸리는 것을 방지한다.
3.3 알파-베타 가지치기로 최소최대 알고리즘 개선하기
이미 탐색한 위치보다 점수가 낮은 탐색 위치를 제외시키면서 최소최대 알고리즘의 탐색 깊이를 향상시키는 방법
- 알파 : 탐색 트리에서 현재까지 발견된 최고의 최대화 움직임 평가
- 베타 : 상대방에 대해 현재까지 발견된 최고의 최소화 움직임 평가
베타가 알파보다 작거나 같으면 해당 위치의 탐색 분기를 더이상 살피지 않음 - 완벽하게 이해 못함-
4. 알파-베타 가지치기를 넘어서
최소최대 탐색을 개선하는 방법
- 할당된 시간동안 더 깊은 탐색(각 위치에서 더적은 시간 소비) : 코드의 효율성, 더욱 빠른 하드웨어
- 위치를 평가하는데 사용되는 평가 함수 개선 :더 많은 매개변수 혹은 휴리스틱 사용
5. 적용사례
작은 검색공간에서는 계산이 시간 내 가능하기에 최소최대 알고리즘이 효과적이었지만, 검색공간이 큰 바둑과 같은 영역에서는 계산이 불가능하다. 따라서 머신러닝과 같은 기술이 주목 받고 있다.