알파베타 가지치기-휴리스틱 알고리즘 틱택토 과제

소개글

인공지능 과제입니다.
알파베타 가지치기를 이용한 틱택토 소스와 노트상태, 설명이 되어있습니다.

목차

1. 상태묘사방법 및 연산자, 평가함수, 틱택토의 알파베타 가지치기 설명
2. 알파베타 가지치기-휴리스틱 알고리즘 사용한 소스코드

본문내용

■ 상태묘사방법 및 연산자, 평가함수, 틱택토의 알파베타 가지치기 설명

상태 p에 대한 평가 함수 e(p)라고 하자.

만일 p가 양쪽 모두에게 이기는 상태가 아니라면,
e(p)= (MAX 에게 가능한 행, 열, 대각선의 수) - (MIN 에게 가능한 행, 열, 대각선의 수)
만일 p가 MAX 가 이기는 상태라면,
e(p) = ∞ ( ∞ 는 아주 큰 양수를 의미함)
만일 p가 MIN 이 이기는 상태라면,
e(p) = -∞
즉, 만일 p가 다음과 같다면,

e(p) = 6 – 4 = 2 가 된다.

자식 노드들을 생성할 때는 대칭성을 고려한다. 그러면 다음의 상태들은 모두 동일한 것으로 간주된다.

게임 초기에는 대칭성 때문에 분기 계수가 작게 되고, 나중에는 가능한 상태가 적기 때문에 분기 계수가 작게 된다. MAX상태의 트리로 표현하자면,

음 MAX예제의 트리의 한 부분을 위 그림 에 다시 나타내었다.
깊이우선탐색을 사용하며, 노드가 생성될 때마다 e(p)가 계산된다고 가정하자. 또한 어떤 노드가 전달 값을 받을 수 있게 되자마자 전달 값이 지정된다고 하자.
노드는 현재 전달 값이 –1 이다. 알파 값의 제한은 –1이며, 그보다 작은 값을 가질 수는 없지만, 더 큰 수는 가질 수 있다.
첫 번째 자식 노드가 생성되었을 때, 베타값이 –1이라고 하면 –1보다 작을 수는 있지만, 더 클 수는 없다. 즉, 정리해서 말하자면,

- MAX 노드의 알파 값은 (시작 노드를 포함하여) 절대 감소되지 않는다.
- MIN 노드의 베타 값은 절대 증가하지 않는다.
이러한 제약조건 때문에, 다음과 같은 규칙에 의하여 탐색을 중단할 수 있다.

참고 자료

없음