We will denote the above defined game, played on graph G = (V, E) and starting from initial position G,K K (x, y) ∈ V 2 by ΓG (x,y). The game analysis becomes easier if we assume that the game always lasts an infinite number of rounds if a capture occurs at tc, then we will have xt = yt = xtc for all t ≥ tc. C wins if capture takes place for some t ∈ N. We will call this “en passant ” capture it does not have an analog in TBCR. (b) The cop is located at xt−1 and moves to yt−1, while the robber is located at yt−1 and moves to xt−1. This capture condition is the same as in TBCR. A capture occurs at the smallest t ∈ N for which either of the following conditions holds: (a) The cop is located at xt, the robber is located at yt, and xt = yt. At every round both players know the current cop and robber location (and remember all past locations). At the t-th round (t ∈ N) C moves the cop to xt ∈ N and simultaneously R moves the robber to yt ∈ N 2. The game starts from given initial positions: the cop is located at x0 ∈ V and the robber at y0 ∈ V. We assume the reader is familiar with the rules of TBCR and proceed to present the rules of CCCR for the case of K = 1 (a single cop).
Player C, controlling K cops (with K ≥ 1) pursues a single robber controlled by player R (we will sometimes call both the cops and robber tokens). In case K > 1 cops are considered, this will be stated explicitly the extension of definitions and notation is straightforward.īoth CCCR and TBCR are played on an undirected, simple and connected graph G = (V, E) by two players called C and R. In this section, as well as in the rest of the paper, we will mainly concern ourselves with the case of a single cop this is reflected in the following definitions and notation. Finally, in Section 6 we present our conclusions and future research directions. In Section 4 we concentrate on the “game of degree” aspect: we equip CCCR with a payoff function (namely the time required to capture the robber) and prove that (a) CCCR has a game theoretic value, (b) the cops have an optimal strategy and (c) for every ε > 0 the robber has an ε-optimal strategy in addition we provide an algorithm for the computation of the value and the optimal strategies. In Section 3 we concentrate on the “game of kind” aspect: we define the concurrent cop number e c (G) and prove that, for every graph G, it is equal to the “classical” cop number c (G).
In Section 2 we define preliminary concepts and notation and use these to define the CCCR game rigorously. The CCCR game (similarly to TBCR) can be considered as either a game of kind (the cops’ goal is to capture the robber) or a game of degree (the cops’ goal is to capture the robber in the shortest possible time)1. In all other aspects, the concurrent game (henceforth CCCR) follows the same rules as the classical, turn-based game (henceforth TBCR). On the other hand, in concurrent CR the players move simultaneously. In the classical CR game each player observes the other player’s move before he performs his own. In this paper we study the concurrent cops and robber (CCCR) game. For every graph G, CCCR has a value, the cops have an optimal strategy and, for every ε > 0, the robber has an ε-optimal strategy. For every graph G, the concurrent cop number is equal to the “classical” cop number. For the variant in which it it required to capture the robber in the shortest possible time, we let time to capture be the payoff function of CCCR the (game theoretic) value of CCCR is the optimal capture time and (cop and robber) time optimal strategies are the ones which achieve the value. The cops’ goal is to capture the robber and the concurrent cop number of a graph is defined the minimum number of cops which guarantees capture. CCCR follows the same rules as the classical, turn-based game, except for the fact that the players move simultaneously. Kehagias JAbstract In this paper we study the concurrent cops and robber (CCCR) game. Simultaneously Moving Cops and Robbers G.
0 kommentar(er)
