https://startagainbornagain.tistory.com/106
스튜어드 러셀의 인공지능을 읽어보자(13) : 온라인 검색 에이전트와 미지 환경
저번 글 https://startagainbornagain.tistory.com/104 스튜어드 러셀의 인공지능을 읽어보자(12) : 부분 관찰 가능 환경의 검색 오랜만입니다 ㅠㅠ 많이 늦었죠..? 다시 열심히 하도록 하겠습니다. 저번 글 http
startagainbornagain.tistory.com
게임
각 에이전트가 다른 에이전트들의 동작과 그것이 자신의 이익에 미치는 영향을 고려해야 하는 다중 에이전트 환경을 소개 했었습니다. 다른 에이전트들의 예측 불가능성 때문에 에이전트의 문제 해결 공정에서 논의한 우발성(CONTINGENCY)이 도입되었습니다. 이번에는 에이전트들의 목표가 상충하는 경쟁적 환경과 그런 환경에서 발생하는 대항검색(adversarial search; 적대적 탐색)문제들을 살펴보겠습니다. 그런 문제를 흔히 게임(game)이라고 부릅니다
경제학의 한 분과인 수학적 게임이론은 에이전트들이 협동적이든 경쟁적이든, 각 에이전트가 다른 에이전트에 미치는 영향이 '뚜렷'하기만 하다면 모든 다중 에이전트 환경을 게임으로 간주합니다.
인공지능에서 가장 흔히 볼 수 있는 게임은 상당히 특화된 종류의 게임입니다. 게임이론가들이 결정론적이고 차례기반(turn-based) 인 완벽한 정보(perfect information; 또는 완전 정보)가 주어지는 2인용 영합 게임(zero-sum game)이라고 부르는 것이 바로 그것으로, 체스가 좋은 예입니다.
인공지능의 어법에서 이런 게임은 결정론적이고 완전히 관찰 가능한 환경에서 두 에이전트가 번갈아 행동하는, 그리고 게임의 끝에서의 효용 값들이 항상 동등하고 반대인 경우에 해당합니다. 예를 들어 체스 게임에서 한 플레이어가 이기면 다른 플레이어는 반드시 지게 됩니다. 이처럼 에이전트들의 효용 함수가 서로 반대라서 두 플레이어가 서로 대항하는(adversarial)상황이 만들어집니다.
게임은 오랫동안, 문명이 존재하 때부터 인간의 지적 능력에 관여해왔습니다. 게임은 그 추상적 성질 때문에 인종지능 연구자에게 매력적인 연구 주제입니다. 게임의 상태는 표현하기 쉽고 에이전트들은 적은 수의 동작들만 실행할 수 있으며, 동작들의 결과는 엄밀한 규칙으로 정의됩니다.
이번 대항검색에서는 최적의 수와 그것을 찾는 알고리즘을 정의합니다. 그런 다음에는 시간이 제한된 상황에서 좋은 수를 선택하는 기법들을 살펴볼 것입니다. 가지치기(pruning)를 이용하면 검색 트리에서 최종 선택에 영향을 미치지 않는 부분을 무시할 수 있습니다. 그리고 발견법적 평가 함수(evaluation function)를 이용하면 트리 전체를 탐색하지 않고도 한 상태의 효용의 참값을 근사할 수 있게 됩니다.
게임의 끝에서는 이긴 플레이어에게 승점이 주어지고, 패자에게는 벌점이 주어집니다. 이런 게임을 다음과 같은 요소들을 가진 일종의 검색 문제로 형식화 할 수 있습니다.
- S0: 초기 상태. 시작 시점에서의 게임의 설정을 명시합니다.
- PLAYER(s): 주어진 상태에서 수를 두는 플레이어를 정의합니다.
- ACTIOON(S): 주어진 상태에서 가능한 수들의 집합을 돌려줍니다.
- RESULT(s,a): 전이 모형, 한 수의 결과를 정의합니다.
- TERMINAL-TEST(S): 말단 판정(terminal test). 게임이 끝났으면 참, 그렇지 않으면 거짓입니다. 게임이 끝난 상태를 가리켜 말단 상태(terminal state)라고 부릅니다.
- UTILITY(s,p): 효용 함수(목적 함수 또는 보상함수(payoff function)라고 부르기도 합니다). 좀점 상태 s에서 끝난 게임의 , 플레이어 p에 대한 최종 수치 값을 정의 합니다. 체스에서 겨과는 승,무,패 중 하나로, 각각의 효용 값은 +1, 0 1/2입니다 가능한 결과가 좀 더 다양한 게임도 있습니다.
초기 상태와 ACTION함수, RESULT 함수는 게임에 대한 트리, 즉 게임 트리(game tree)를 정의합니다. 이 트리의 노드는 게임 상태이고 간선은 수입니다.
오늘은 여기까지구요 다음 시간에는 게임의 최적 결정에 관해 알아보도록 하겠습니다.
'인공지능 > 논문 번역 및 공부' 카테고리의 다른 글
| 스튜어드 러셀의 인공지능을 읽어보자(16) : 대항 검색3 (0) | 2021.09.28 |
|---|---|
| 스튜어드 러셀의 인공지능을 읽어보자(15) : 대항 검색2 (0) | 2021.09.14 |
| 스튜어드 러셀의 인공지능을 읽어보자(13) : 온라인 검색 에이전트와 미지 환경 (0) | 2021.08.10 |
| 스튜어드 러셀의 인공지능을 읽어보자(12) : 부분 관찰 가능 환경의 검색 (0) | 2021.08.03 |
| 스튜어드 러셀의 인공지능을 읽어보자(11) : 비결정론적 동작들을 수반한 검색 (0) | 2021.06.01 |
