Numerical approaches to the 'princess and monster' game on the interval
Steven Alpern, Robbert Fokkink, Roy H. A. Lindelauf, Geert Jan Olsder · London School of Economics and Political Science Research Online (London School of Economics and Political Science) · 2006
Abstract. Rufus Isaacs introduced Princess and Monster games in the final chapter of his classic book. The value of the Princess and Monster game on an interval is as of yet unknown. We present some numerical results to estimate this value. In the final chapter of his classic book Differential Games, Rufus Isaacs introduced the ‘Princess and Monster ’ games. A Monster and a Princess may move about in a restricted space, more specifically in a network, and the Monster tries to catch the Princess. They are not able to see each other and that is why this type of game is known as a Search Game [3, 7, 9]. It is different from the more familiar Game of Pursuit [5], in which both players have visual contact. In most of the Search Games that have been solved so far, the Princess is immobile; e.g., [6, 12]. The only Search Game with a mobile Princess that has been solved is the Princess and Monster game on a circle, and this was done a long time ago [1, 13]. In a complementary paper [4] we have shown that the Princess and Monster game on an interval [−1, 1] is not trivial (not trivial in the sense that for the Monster it is not optimal to start at one random end and then go as fast as possible to the other) and that the value V of the game is bounded by 15/11 < V < 13/9. These bounds were obtained by analytical considerations and computations that can be checked by hand. In this paper we consider a restricted game that has a value Vr ≤ V. By numerical simulations we show that Vr ≈ 1.373. 1. Rules of the game The rules of the game are as follows. The Monster M and the Princess P may choose an arbitrary initial point on the closed interval [−1, 1]. The Monster moves at speed bounded by 1, so the trajectory of M, M(t) is a