2인 제로섬 유한 결정적 완전 정보 게임

2인 : 플레이어가 2명

제로섬 : 플레이어가 서로 대립해서 한쪽 플레이어가 이득을 얻으면 다른쪽 플레이어는 같은 양의 손해를 봄

유한 : 게임이 반드시 유한한 횟수에 끝남

결정적 : 무작위 요소가 존재하지 않음

완전 정보 : 모든 정보가 양쪽 플레이어에 공개됨

ex) 장기, 바둑, 오셀로

hill climbing

국소 탐색법이라는 탐색 방법으로 분류되는 알고리즘

어떤 상태에서 약간만 구조를 바꾼 상태를 이웃이라고 부른다

답을 무작위의 이웃으로 전이 시켜서 특정 조건을 만족하면 유지하고 조건을 만족하지 않으면 원래 장소로 돌아간다. 이런 과정을 반복해 최종적으로 가장 점수가 높았던 상태가 답이 된다.

hill climbing 문제점

이론상 최적해에 도달할 수 있지만

탐색을 계속하면 국소 최적해에서 벗어날 수 업ㅅ을 가능성이 있다

simulated annealing

국소 최적해를 탈출하는 방법

hillclimbing을 조금 바꿔서 국소 최적해에서 빠져 나올수 있도록 만든다

기록 점수가 개선되지 않더라도 전이하게 만든다

어떤 답의 now의 점수가 score일 때 무작위로 선택한 답 next로 ㅇ전이할 지 여부를 생각

minimax 알고리즘

상대방은 나에게 불리한 행동응ㄹ 하고 자신은 난에게 유리한 행동을 선택한다고 가정하면서 탐색하는 방법