공주와 괴물 게임

Princess and monster game

게임 이론에서 공주와 몬스터 게임은 루퍼스 아이작스가 고안해 그의 저서 미분 게임 (Differential Games)(1965)에 출판된 추격 게임이다. 이 게임은 한 지역에서 공주와 괴물이라는 두 명의 선수가 한다. 간단히 말해서 괴물의 목표는 공주를 사로잡는 것이고, 공주의 목표는 괴물의 포획을 피하는 것이다.[1]

형식 정의

루퍼스 아이작스는 그의 저서 Differential Games (1965년)에서 이 게임을 다음과 같이 정의했다.

그 괴물은 공주를 찾아다닌다, 그 보상이 필요한 시간이다. 그들은 둘 다 완전히 어두운 방에 있지만 각각 그 경계를 인식한다. 포획은 공주와 괴물의 거리가 포획 반경 내에 있다는 뜻으로, 방의 치수에 비해 작다고 가정한다. 이 괴물은 지능이 높은 것으로 알려져 있는 속도로 움직인다. 우리는 공주에게 모든 이동의 자유를 허락한다.[2]

공주와 괴물 게임에 대한 해결책

그 게임은 간단해 보이지만 꽤 복잡하다. 임의의 끝에서 시작하여 전체 간격을 가능한 한 빨리 "sweeping"하는 명백한 검색 전략은 예상 캡처 시간을 0.75로 보장하며, 최적 상태가 아니다. 보다 정교한 혼성 탐색기와 히더 전략을 활용하면 예상 캡처 시간을 약 8.6% 단축할 수 있다. 만약 누군가가 공주의 관련 전략의 최적성을 증명할 수 있다면 이 숫자는 게임의 가치에 상당히 근접할 것이다.[1][3]

이 게임은 1970년대 후반 슈무엘 갈에 의해 해결될 때까지 잘 알려진 개방적인 문제로 남아 있었다.[4][5] 공주를 위한 그의 최적의 전략은 다른 (독립적인) 임의의 장소로 가서 절차를 반복하기 전에 방 안의 임의의 장소로 이동하여 너무 짧지도 길지도 않은 시간 간격을 두고 가만히 있는 것이다.[5][6][7] 몬스터에 대해 제안된 최적의 검색 전략은 방을 많은 좁은 직사각형으로 세분화하여 무작위로 직사각형을 선택하고, 얼마간의 시간이 흐른 후 다른 직사각형을 임의로 그리고 독립적으로 선택하는 등의 특정한 방법으로 검색하는 것에 기초한다.

프린세스와 몬스터 게임은 미리 선택한 그래프에서 할 수 있다. 유한 그래프에 대해 최적의 혼합 검색 전략이 존재하여 유한 보수가 발생함을 증명할 수 있다. 이 게임은 스티브 알펜에 의해 해결되었고 미하일 젤리킨에 의해 독립적으로 단일 루프(원)로 구성된 매우 단순한 그래프에 대해서만 해결되었다.[8][9] 단위 간격의 게임 값(연결이 중간인 두 개의 노드가 있는 그래프)은 근사하게 추정되었다.

참고 항목

참조

  1. ^ a b S. 알펜, R. 포크링크, R. 린델라우프, 그리고 G. J. 올스더. 수치상 '공주와 괴물' 게임 간격에 대한 접근 SIAM J. 제어 및 최적화 2008.
  2. ^ R. Isaacs, Differential Games: 전투와 추적, 제어와 최적화에 응용한 수학 이론, John Wiley & Sons, 뉴욕 (1965), PP 349–350.
  3. ^ L. Geupel. '공주와 몬스터' 게임을 인터벌로 한다.
  4. ^ S. Gal, SEARK GAMES, Academic Press, New York (1980)
  5. ^ a b Gal Shmuel (1979). "Search games with mobile and immobile hider". SIAM J. Control Optim. 17 (1): 99–122. doi:10.1137/0317009. MR 0516859.
  6. ^ A. Garnaev (1992). "A Remark on the Princess and Monster Search Game" (PDF). Int. J. Game Theory. 20 (3): 269–276. doi:10.1007/BF01253781.[영구적 데드링크]
  7. ^ M. Chrobak (2004). "A princess swimming in the fog looking for a monster cow". ACM SIGACT News. 35 (2): 74–78. doi:10.1145/992287.992304.
  8. ^ S. Alpern (1973). "The search game with mobile hiders on the circle". Proceedings of the Conference on Differential Games and Control Theory.
  9. ^ M. I. Zelikin (1972). "On a differential game with incomplete information". Soviet Math. Dokl.