[컴퓨터공학]인공지능/휴리스틱/교환정렬/탐색

소개글

1. 윷놀이에서의 인공지능요소를 파악하여 분석하였고, 인공지능 프로그래밍시 요구되는 사항을 분석하여 기술하였다.
2. 교환방법 정렬에 대한 네가지에 정렬방법에 대하여 그림으로 제시하고 설명하였다.
(* 참고로 A+ 받은 레포트입니다.)

목차

<윷놀이 휴리스틱>
< 교환 방법으로의 정렬 >
1. 깊이우선탐색(DFS: depth first search)
2. 넓이우선탐색(BFS: breadth-first search)
3. UNIFORM
4. 교환정렬에서의 휴리스틱탐색

본문내용

<윷놀이 휴리스틱>
먼저 이 윷놀이 게임에서의 전제 조건은 백도가 없다는 것이고 나올 수 있는 패(도, 개, 걸, 윷, 모)의 확률은 동일하다고 전제한다. 그리고 패가 나온 순서에 따라 윷판에 순서대로 적용(ex: ‘모’ 다음에 ‘개’가 나왔다면 ‘모’를 먼저 적용하고 다음으로 ‘개’를 진행)해야한다.
처음 초기화 상태에는 윷판에 아무것도 없는 상태이기 때문에 나온 패에 따리 무조건 진행하는 수 밖에 없다. 하지만 두 번째부터는 말들이 진행되는 상태이기 때문에 현재 형성된 판세를 보고 앞으로 말을 어떻게 진행시킬 것인지 판단해야한다. 판단기준은 프래그래머가 작성한 평가기준에 따라 미래 비용을 예측하여 유리한 쪽(여기에서는 값이 높은 쪽)으로 진행해야 한다.
나는 윷놀이 게임 중 판세에 가장 큰 영향을 주는 것부터 차례대로 다음과 같이 나열해 보았다.

1. 상대방의 말을 잡을 수 있거나 나의 말이 잡힐 수 있는 경우(말이 많이 진행한 것부터 우선순위로 잡는 것으로 한다.)
2. 나의 말을 합쳐서 갈 수 있는 경우
3. 지름길로 갈 수는 경우
4. 아무 변화 없이 그냥 진행할 것 같은 경우

위의 1～4번까지의 내용을 점수화하여 세부적으로 아래와 같이 적어보았다.
[※컴퓨터(=나)의 말은 c1, c2, c3, c4 라고 표기하고, 상대방의 말은 p1, p2, p3, p4 라고 한다.]

잡을 수 있는 경우(p가 c를 앞서는 경우)
p를 한 개 잡을 수 있는 경우 : 10점
p를 두 개 잡을 수 있는 경우 : 20점
p를 세 개 잡을 수 있는 경우 : 30점
p를 네 개 잡을 수 있는 경우 : 40점

잡힐 수 있는 경우(c가 p를 앞서는 경우)에는 음의 점수를 부여하기로 한다. 예를 들면 한 개를 잡힐 수 있는 경우에는 -10을 부여한다.

참고 자료

없음