An investigation of the game of Defend the Island

Abstract

Motivated by the problem of “Defend the Roman Empire”, we propose a variant of graph pebbling, named $(d, t)$ -pebbling, and use this idea to devise a two-player game of imperfect information, named “Defend the Island”. On an island, the target castle attacked by the opponent is securable if t Field Armies (FAs) can reach the target castle from neighboring castles within a distance of d. The aim is to obtain more points than the opponent before an insecure castle on the island is attacked. There is a minimum number of FAs initially deployed on the island so that each castle is securable. In graph pebbling, this number is called the optimal $(d, t)$ -pebbling number of a graph G, denoted by $π_{(d, t)}^{*} (G)$ . When the number of FAs is less than $π_{(d, t)}^{*} (G)$ , there exists at least one insecure castle. This property is the core idea to devise the new game. In addition, when the castles forms a cycle, that is, the graph is a cycle, we give a lower bound of $π_{(d, t)}^{*} (G)$ for $d = 1, 2$ and determine the exact value of $π_{(d, t)}^{*} (G)$ for the ordered pairs $(d, t) = (2, 2), (1, 4 m)$ and $(2, 10 m)$ , where m is any positive integer.

Keywords

Game design

1. Introduction

In the problem of “Defend the Roman Empire” (Stewart, 1999), there is a map with several regions and a fixed number of Field Armies (FAs) is distributed in the regions. A region on the map is secured or securable if there is at least one FA stationed in it already or if one can be deployed in a single step of movement. There is no loss of FAs during the deployment. Usually, a map is represented by a graph. A region is represented by a vertex and a road is represented by an edge.

Motivated by the above problem, we propose a variant of graph pebbling, named $(d, t)$ -pebbling, and use this idea to devise a two-player game of imperfect information, named “Defend the Island”. Based on “Defend the Roman Empire”, we propose three extensions for the new game. First, a certain ratio of FAs is lost during the process of moving. Second, considering the limitation of time, FAs must arrive at the target region in time, that is, only the regions within a given distance d can dispatch FAs. Third, a region is secured or securable if the region can aggregate at least t FAs, where $t ⩾ 1$ .

An interesting issue derived from “Defend the Island” is to find the minimum number of FAs placed on the island initially so that each region is secured or securable. In this paper, we use the $(d, t)$ -pebbling to tackle this issue. This number is called the optimal $(d, t)$ -pebbling number of a graph. When the graph is a cycle, we prove the lower bound of the optimal $(d, t)$ -pebbling number for $d = 1, 2$ and determine the exact value of the optimal $(d, t)$ -pebbling number for the ordered pairs $(d, t) = (2, 2), (1, 4 m)$ and $(2, 10 m)$ , where m is any positive integer.

This paper is an extension of a preliminary work presented in the 10^th International Conference on Computers and Games (CG2018) by investigating more properties when the map is a cycle. In the remainder of this paper, we first introduce the idea that motivates the invention of the new game in Section 2. We describe the rules of the game in Section 3. Some properties of the $(d, t)$ -pebbling number for a cycle are proven and a (2, 2)-pebbling game in cycles is proposed in Section 4. We make conclusions in Section 5.

2. Background and preliminaries

In this section, we introduce the problem of “Defend the Roman Empire” in Section 2.1. Then, the preliminaries of graph pebbling to model the new game are described in Section 2.2.

2.1. Defend the Roman Empire

In the problem of “Defend the Roman Empire”, a region is secured if it has one or more mobile FAs stationed in it already. In addition, the region is securable if an FA can be deployed to protect that region in a single step of movement. An FA can be deployed from one region to an adjacent region only if it moves from a region where there is at least one other FA to help launch it. That is, the securable region must be adjacent to a region which can be deployed with at least two FAs (including FAs moved from other regions).

Note that there is no loss of troops in the moving process. So, if a region R has at least two FAs, one FA can be deployed from R to an adjacent region of R and the other FA stays at R. For example, Fig. 1(a) shows the map of the Roman Empire. Assume that two FAs are placed at $R_{2}$ and $R_{3}$ respectively as shown in Fig. 1(b). We can deploy an FA from $R_{3}$ to $R_{4}$ and then deploy an FA from $R_{2}$ to $R_{3}$ . Now, $R_{3}$ has two FAs and $R_{4}$ has one FA. We can deploy an FA from $R_{3}$ to $R_{4}$ and thus $R_{4}$ has two FAs. Finally, we can deploy an FA from $R_{4}$ to $R_{9}$ .

Fig. 1.

A map of Defend the Roman Empire.

Note that in the problem “Defend the Roman Empire”, a region is secured or securable if we can deploy an FA (that is, if we place at least one FA initially or we can move an FA from other regions). However, in this paper, considering that the attack power may vary, we assume that a region is secured or securable if we can deploy t FAs at this region. Moreover, considering the limitation of time, we assume that we must complete deploying enough FAs at a region R by using at most d steps of movements. That is, we can move FAs only from the regions with the distance of at most d steps away from R.

2.2. Graph pebbling

Let G be a graph. Then $V (G)$ and $E (G)$ denote the vertex set and the edge set of G, respectively. Usually, a map is represented by a graph G and a region in a map is a vertex in G. Two vertices u and v are adjacent, that is, $u v$ is an edge in G, if their two corresponding regioins are connected by a road. A function $δ : V (G) \to N \cup {0}$ is called a distribution of pebbles of G if we distributes $δ (v)$ pebbles to each vertex $v \in V (G)$ , where $N$ is the set of all positive integers. The total number of pebbles distributed on the vertices of G is called the weight of δ, calculated by $\sum_{v \in V (G)} δ (v)$ . A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex.

A graph H is called an induced subgraph of G if H is a subgraph of G satisfying the property, which is for any pair of vertices u and v in $V (H)$ , $u v \in E (H)$ if and only if $u v \in E (G)$ . If H is an induced subgraph of G with the vertex set S, then we say that H is a subgraph induced by S. Let δ be a distribution of G and H be an induced subgraph of G. For each vertex $v \in V (H)$ , we use $m (δ, H, v)$ to denote the maximum number of pebbles that can be moved to v from the vertices of H by using pebbling moves.

A distribution δ of pebbles of a graph G is said to be t-fold solvable if $m (δ, G, v) ⩾ t$ for each $v \in V (G)$ . Usually, a 1-fold solvable distribution is said to be solvable. The optimal t-pebbling number of G, denoted by $π_{t}^{*} (G)$ , is the minimum number of pebbles required in a t-fold solvable distribution of G (Shiue, 2015). The optimal pebbling number of G is the optimal 1-pebbling number of G (Pachter et al., 1995).

In terms of applications, a pebbling graph can be used to model a “resource allocation and transportation system”. In this system, we initially distribute some units of resources (pebbles) on each location (vertices). When a target location needs t units of resources, we can transport resources from other locations to support it. In the process of transporting resources from a location to one of its adjacent locations, a portion of the resources (e.g. $1 / 2$ ) will be lost (in a pebbling move). Now, we present a modification for this model. Consider that the necessary resource must be sent to the target location on time, we need to restrict the distance from the target location to any location which can supply resources. This revised model can be tackled using the following pebbling idea.

Let G be a graph. For any vertex $v \in V (G)$ , we define the vertex sets $N_{d} (v) = {u \in V (G) | 1 ⩽ distance (u, v) ⩽ d}$ and $N_{d} [v] = N_{d} (v) \cup {v}$ , where d is a positive integer and $distance (u, v)$ denotes the length of a shortest path from u to v. When $d = 1$ , the d-neighborhood is the neighborhood. Suppose that we distribute p pebbles on the vertices of G initially. If we can move pebbles on any target vertex $v \in V (G)$ by using pebbling moves only from the vertices in $N_{d} [v]$ . Then we call the graph G a d-distance restricted pebbling graph. A distribution δ of a d-distance restricted pebbling graph G is $(d, t)$ -solvable if we can move t pebbles to any target vertex v of G (including the pebbles on v initially). That is, if we let H be the subgraph induced by $N_{d} [v]$ , then $m (δ, H, v) ⩾ t$ for each vertex v of G. For convenience, in this paper we denote $m (δ, H, v)$ by $m (δ, d, v)$ when H is the subgraph induced by $N_{d} [v]$ . The optimal $(d, t)$ -pebbling number of G, denoted by $π_{(d, t)}^{*} (G)$ , is the minimum number of pebbles needed so that there is a $(d, t)$ -solvable distribution of G.

3. A new game: Defend the Island

With the assumptions above, we are interested in the following problem called “Defend the Island”, described in Section 3.1. The rules of the game are designed in Section 3.2.

3.1. The idea

A map of the island is represented as a graph shown in Fig. 2(a). To defend the island, we must place some FAs at some regions on this island initially. When a region R is attacked, we can move FAs from other regions to support R. Armies will suffer from attack in the process of moving, resulting in a loss of half of the troops. That is, when we move $2 s$ FAs from one region, only s FAs can be deployed successfully at an adjacent region. This movement is called a deploying step that takes one unit of deploying time. Note that we can only move an even number of FAs, that is, if there are $2 s + 1$ FAs, only $2 s$ FAs can be moved and one FA stays at the original region. In addition, there may be no FA stationed at the original region after a deploying step. For example, in Fig. 2(b), let us place two FAs at each of $R_{2}$ and $R_{3}$ . After we move two FAs from $R_{2}$ to $R_{3}$ , $R_{2}$ has no FAs and $R_{3}$ has three FAs. Then, after we move two FAs from $R_{3}$ to $R_{4}$ , each of $R_{3}$ and $R_{4}$ has one FA. No FAs can reach $R_{9}$ .

Assume that the enemy will choose only one target region R on the island to attack. To defend R, we must deploy enough number of FAs at R before the enemy starts attacking. Considering the limitation of time, assume that we must complete the deployment at R in d units of deploying time. Thus, we can deploy FAs at R from any region $R^{'}$ through a path only if the distance between R and $R^{'}$ is at most d. We call such a region $R^{'}$ a $(R, d)$ -region. For example, in Fig. 2(a), when $d = 2$ and the target region is $R_{2}$ , we have $(R_{2}, 2)$ -regions $R_{1}$ , $R_{2}$ , $R_{3}$ , $R_{4}$ , $R_{7}$ and $R_{8}$ . We can simultaneously move FAs from $R_{1}$ and $R_{4}$ to $R_{3}$ and from $R_{7}$ to $R_{8}$ by applying one deploying step, and then simultaneously move FAs from $R_{3}$ and $R_{8}$ to $R_{2}$ by applying one deploying step. Hence, the total time that we have spent is two units of deploying time.

Fig. 2.

A map of Defend the Island.

We say that a region is $(d, t)$ -securable if we can deploy t FAs at this region from all $(R, d)$ -regions by applying deploying steps. In this problem, we seek to use the minimum number of FAs to defend the island. That is, we want to find the minimum number of FAs to place at the regions of the island initially such that any region is $(d, t)$ -securable. This problem can be tackled by the $(d, t)$ -pebbling idea. Note that if the number of pebbles on G is less than $π_{(d, t)}^{*} (G)$ , then there exists a vertex v such that $m (δ, d, v) < t$ . That is, there is a region that is not $(d, t)$ -securable on the island. We use this property to devise a new game in Section 3.2.

3.2. The rules

The game we propose is a two-player game of imperfect information. At the beginning of the game, an arbitrary map with n castles is shown to both players.1

¹
A map is represented by a graph, and a castle is represented by a vertex.

There are m FAs.2

m must be less than the optimal $(d, t)$ -pebbling number of the map according to Section 2.2.

The defender can transfer FAs from castles with distance at most d away from the attacked castle. In each deploying step, half of FAs are deployed successfully and half are lost. There are k rounds in a game, and the two players take turns to be the roles of the attacker and the defender once in each round. This game contains the following procedure:

Set up

Two players choose to be the attacker and the defender at the beginning of the game, and take turns once in each round.

There are k rounds in a game, which is decided by the two players at the beginning of the game.

An arbitrary map is assigned in each round. Each map has n castles that is shown to both players.

The defender secretly deploys his or her m FAs (pebbles) at the n castles. Each castle can be placed with at most $2 t$ FAs. The attacker has no information about the deployment.

Playing the game

The attacker chooses a castle v to attack. If v is $(d, t)$ -securable, the defender obtains $m (δ, d, v) - ⌊ t / 2 ⌋$ points. Then, the attacker knows the value $m (δ, d, v)$ and the defender chooses a castle u to show the number of FAs placed at u. After that, the attacker chooses another castle to attack.

If v is not $(d, t)$ -securable, which means the defender cannot transfer t FAs (including the FAs placed initially) to defend, the attacker obtains $2 t - m (δ, 2, v)$ points.

The two players swap their roles. Repeat the above two steps once and finish this round.

After k rounds, the game ends.

Winning the game

The player who obtains more points in a game is the winner.

4. The game in cycles

When n castles are located along the coast of an island, and are connected as a cycle, the map can be represented by a graph $C_{n}$ .3

³
A graph with vertices $v_{1}, v_{2}, \dots, v_{n}$ is called a cycle, denoted by $C_{n}$ , if it is a cycle itself, where $v_{i} v_{i + 1} \in E (C_{n})$ for $i = 1, 2, \dots, n - 1$ and $v_{n} v_{1} \in E (C_{n})$ .

First, we derive the bounds of the optimal

(d, t)

-pebbling number for

C_{n}

in Section 4.1. Next, we determine the exact value of the optimal

(2, 2)

-pebbling number for any cycle in Section 4.2 and devise a (2,2)-pebbling game in cycles in Section 4.3. Finally, an example of

(2, 2)

-pebbling game in cycles is given in Section 4.4.

4.1. Bounds of the optimal

(d, t)

-pebbling number for

C_{n}

The optimal $(d, t)$ -pebbling number of a graph is defined in Section 2.2. In this subsection, we derive the bounds of the optimal $(d, t)$ -pebbling number for $C_{n}$ when the distance d is 1 or 2. First, we consider the case $d = 1$ .

Proposition 1.
For each integer $n ⩾ 3$ , $π_{(1, t)}^{} (C_{n}) ⩾ \frac{n t}{2}$ and equality holds when t is a multiple of* 4.
Proof.
Let δ be a $(1, t)$ -solvable distribution of $C_{n}$ . We need to claim that the weight of δ, $\sum_{v \in V (C_{n})} δ (v)$ , is at least $\frac{n t}{2}$ . For each vertex $v \in V (C_{n})$ , the following inequality must hold. $\begin{matrix} m (δ, 1, v) = δ (v) + \sum_{u \in N_{1} (v)} ⌊ \frac{1}{2} δ (u) ⌋ ⩾ t . \end{matrix}$ This implies that $\begin{matrix} δ (v) + \sum_{u \in N_{1} (v)} \frac{1}{2} δ (u) ⩾ t . \end{matrix}$ Thus, $\begin{matrix} \sum_{v \in V (C_{n})} [δ (v) + \sum_{u \in N_{1} (v)} \frac{1}{2} δ (u)] ⩾ n t . \end{matrix}$ Since there are two neighbors of v for each $v \in V (C_{n})$ , we have $\begin{matrix} \sum_{v \in V (C_{n})} [δ (v) + 2 \cdot \frac{1}{2} δ (v)] ⩾ n t . \end{matrix}$ Thus, $\begin{matrix} 2 \sum_{v \in V (C_{n})} δ (v) ⩾ n t . \end{matrix}$ So, the weight of $δ_{1}$ is at least $\frac{n t}{2}$ and hence $π_{(1, t)}^{} (C_{n}) ⩾ \frac{n t}{2}$ .

Now, we prove that equality holds when t is a multiple of 4. It suffices to give a $(1, t)$ -solvable distribution with the weight $\frac{n t}{2}$ . Suppose that t is a multiple of 4. Then we let $q = \frac{t}{4}$ and distribute $2 q$ pebbles to each vertex of G. We use $δ_{1}$ to denote this distribution. It is easy to see $m (δ_{1}, 1, v) = 4 q = t$ for each vertex $v \in V (C_{n})$ . Thus, $δ_{1}$ is a $(1, t)$ -solvable. Clearly, the weight of $δ_{1}$ is $2 q n = \frac{n t}{2}$ pebbles. This completes the proof. □
Next, we consider the case $d = 2$ . Proposition 2.
For each integer* $n ⩾ 5$ , $π_{(2, t)}^{} (C_{n}) ⩾ \frac{2 n t}{5}$ and equality holds when t is a multiple of* 10.
Proof.
Let δ be a $(2, t)$ -solvable distribution of $C_{n}$ . We need to claim that the weight of δ, $\sum_{v \in V (C_{n})} δ (v)$ , is at least $\frac{2 n t}{5}$ . For each vertex $v \in V (C_{n})$ , the following inequality must hold. $\begin{matrix} m (δ, 2, v) = δ (v) + \sum_{u \in N_{1} (v)} ⌊ \frac{1}{2} (δ (u) + \sum_{w \in N_{2} (v) ∖ N_{1} (v)} ⌊ δ (w) / 2 ⌋) ⌋ ⩾ t . \end{matrix}$ This implies that $\begin{matrix} δ (v) + \sum_{u \in N_{1} (v)} [\frac{1}{2} δ (u) + \sum_{w \in N_{2} (v) ∖ N_{1} (v)} \frac{1}{4} δ (w)] ⩾ t . \end{matrix}$ Thus, $\begin{matrix} \sum_{v \in V (C_{n})} {δ (v) + \sum_{u \in N_{1} (v)} [\frac{1}{2} δ (u) + \sum_{w \in N_{2} (v) ∖ N_{1} (v)} \frac{1}{4} δ (w)]} ⩾ n t . \end{matrix}$ It follows that $\begin{matrix} \sum_{v \in V (C_{n})} {δ (v) + \frac{1}{2} δ (v) \cdot | N_{1} (v) | + \frac{1}{4} δ (v) \cdot | N_{2} (v) ∖ N_{1} (v) |} ⩾ n t . \end{matrix}$ Since $n ⩾ 5$ , we have $| N_{1} (v) | = 2$ and $| N_{2} (v) ∖ N_{1} (v) | = 2$ for each $v \in V (C_{n})$ . This implies $\begin{matrix} \sum_{v \in V (C_{n})} [δ (v) + δ (v) + \frac{1}{2} δ (v)] ⩾ n t . \end{matrix}$ Thus, $\begin{matrix} \frac{5}{2} \sum_{v \in V (C_{n})} δ (v) ⩾ n t . \end{matrix}$ It follows that the weight of δ is at least $\frac{2 n t}{5}$ and hence $π_{(2, t)}^{} (C_{n}) ⩾ \frac{2 n t}{5}$ .

Now, we show that the equality holds when t is a multiple of 10. It suffices to give a $(2, t)$ -solvable distribution with the weight $\frac{2 n t}{5}$ .

If t is a multiple of 10, we let $q = \frac{t}{10}$ and then distribute $4 q$ pebbles to each vertex of $C_{n}$ . We use $δ_{1}$ to denote this distribution and then we have $\begin{matrix} m (δ_{1}, 2, v) = 4 q + 2 ⌊ \frac{4 q + 2 q}{2} ⌋ = 10 q = t \end{matrix}$ for each vertex $v \in V (C_{n})$ . Thus, $δ_{1}$ is a $(2, t)$ -solvable. Also, it is easy to see that the weight of $δ_{1}$ is $4 q n = \frac{2 n t}{5}$ and we have the proof. □

4.2. The exact values of $π_{(2, 2)}^{} (C_{n})$

We determine the exact value of the optimal $(2, 2)$ -pebbling number for any cycle in this subsection. For $C_{3}$ , the following result is easy to check.

Proposition 3.
$π_{(2, 2)}^{} (C_{3}) = 4$ .
By the definitions mentioned in Section 2.2, the following result is obvious. Proposition 4.
For any graph G,* $π_{(d_{1}, t)}^{} (G) ⩾ π_{(d_{2}, t)}^{} (G) ⩾ π_{t}^{} (G)$ for* $1 ⩽ d_{1} ⩽ d_{2}$ .
In Shiue et al. (2018), $π_{2}^{} (C_{n}) = n$ for $n ⩾ 4$ was proven. By Proposition 4, we obtain the following lower bound. Proposition 5.
$π_{(2, 2)}^{} (C_{n}) ⩾ π_{2}^{} (C_{n}) = n$ for* $n ⩾ 4$ .
Now, we prove that the lower bound is also an upper bound. Proposition 6.
$π_{(2, 2)}^{} (C_{n}) ⩽ n$ for* $n ⩾ 4$ .
Proof.
Let $C_{n} = u_{0}, u_{1}, \dots, u_{n - 1}$ . As shown in Fig. 3, we can choose a distribution δ of $C_{n}$ , defined by $δ (u_{2 i}) = 2$ and $δ (u_{2 i + 1}) = 0$ for $i \in [0, ⌊ n / 2 ⌋ - 1]$ . If n is odd, let $δ (u_{n - 1}) = 1$ . Clearly, the weight of δ is n and it can be easily checked that δ is a $(2, 2)$ -solvable distribution of $C_{n}$ . □
By combining Propositions 3, 5 and 6, we obtain our main result in this subsection.

Fig. 3.
A optimal $(2, 2)$ -pebbling distribution.
Theorem 7.
$\begin{matrix} π_{(2, 2)}^{*} (C_{n}) = \{\begin{matrix} n + 1 & (if n = 3) \\ n & (if n ⩾ 4) . \end{matrix} \end{matrix}$
4.3. $(2, 2)$ -Pebbling game in cycles

Let δ be a distribution of 2-distance restricted pebbling cycle $C_{n}$ , $n ⩾ 4$ . By Theorem 7, δ is not $(2, 2)$ -solvable if the weight of δ is less than n. In this simplified version of “Defend the Island”, we set $d = 2$ , $t = 2$ , and the total number of FAs (pebbles) to be placed initially is $m = n - 1$ . For example, a map represented by a graph $C_{16}$ is shown in Fig. 4(a). The distribution δ is also indicated by the number at each vertex. After applying pebbling moves, the vertices in Fig. 4(b) marked by ‘1’ is not $(2, 2)$ -securable, that is, these vertices cannot have more than two pebbles. For convenience, we combine Fig. 4(a) and Fig. 4(b) into Fig. 4(c).

The procedure of “Defend the Island for $C_{n} (n ⩾ 3)$ ” is shown below.

Fig. 4.

A $(2, 2)$ -pebbling game in $C_{16}$ .

Initial step: Assign $count$ with 0.

Step 1: The defender chooses any distribution δ of $C_{n}$ such that the weight of δ is $n - 1$ and $0 ⩽ δ (v) ⩽ 4$ for each $v \in V (C_{n})$ . The attacker has no information about the distribution δ.

Step 2: The attacker chooses a vertex v to attack. If v is $(2, 2)$ -securable, then the attacker loses $m (δ, 2, v) - 1$ points, the attacker knows the value $m (δ, 2, v)$ , and goto Step 3. Otherwise, the attacker obtains $4 - m (δ, 2, v)$ points and goto Step 4.

Step 3: The defender chooses a vertex u to show the value $δ (u)$ to the attacker and goto Step 2.

Step 4: If $count = 1$ then stop. Otherwise, swap the defender and the attacker, goto Step 1, and assign $count$ with 1.

4.4. An illustration of

(2, 2)

-pebbling game in

C_{16}

In this subsection, an example is used to illustrate the process of $(2, 2)$ -pebbling game in $C_{16}$ .

Initial step: Assign $count$ with 0.

Step 1: The defender chooses a distribution δ of $C_{n}$ as shown in Fig. 4(c). The attacker has no information as shown in Fig. 5(a).

Step 2: The attacker chooses the vertex $u_{6}$ to attack. Since $u_{6}$ is $(2, 2)$ -securable, the defender obtains $m (δ, 2, u_{6}) - 1 = 2$ points, the attacker knows the value $m (δ, 2, u_{6})$ as shown in Fig. 5(b). Goto Step 3.

Step 3: The defender chooses the vertex $u_{0}$ and shows the value $δ (u_{0})$ as shown in Fig. 5(c), and goto Step 2.

Step 2: The attacker chooses the vertex $u_{9}$ to attack. Since $u_{9}$ is $(2, 2)$ -securable, the defender obtains $m (δ, 2, u_{9}) - 1 = 1$ points, and the attacker knows the value $m (δ, 2, u_{9})$ as shown in Fig. 5(d). Goto Step 3.

Step 3: The defender chooses the vertex $u_{14}$ and shows the value $δ (u_{14})$ as shown in Fig. 5(e), and goto Step 2.

Step 2: The attacker chooses the vertex $u_{1}$ to attack. Since $u_{1}$ is not $(2, 2)$ -securable, the attacker obtains $4 - m (δ, 2, u_{1}) = 3$ points and goto Step 4.

Step 4: Assign $count$ with 1, swap the role of the defender and the attacker, and goto Step 1.

In this example, after the first half round, both of the defender and the attacker obtain three points. Since the attacker has no information after executing Step 1, the probability that

u_{i}

is chosen to attack in the first Step 2 is

1 / 16

for each

i = 0, 1, \dots, 15

. Hence, the expected value of the points obtained by the definder after executing the first Step 2 is

\frac{1}{16} \sum_{v \in V (C_{n}), m (δ, 2, v) ⩾ 2} [m (δ, 2, v) - 1] = \frac{14}{16} = \frac{7}{8}

while the expected value of the points obtained by the attacker is

\frac{1}{16} \sum_{v \in V (C_{n}), m (δ, 2, v) ⩽ 1} [4 - m (δ, 2, v)] = \frac{18}{16} = \frac{9}{8}

, as shown in Fig. 4(c).

Fig. 5.

An example of $(2, 2)$ -pebbling game in $C_{16}$ . The symbol ‘-’ indicates that the value of $δ (u_{i})$ or $m (δ, 2, u_{i})$ is still unknown to the attacker.

5. Concluding remarks

In this paper, we use the concept of $(d, t)$ -pebbling to devise a new graph pebbling game, named “Defend the Island”. It is a two-player game of imperfect information. In this game, we restrict the number of FAs (pebbles) placed on any castle (vertex) initially such that there exists insecure castles. This type of pebbling can be seen in Chellali et al. (2017). When the graph is a cycle, we give a lower bound of the optimal $(d, t)$ -pebbling number for $d = 1, 2$ and determine the exact value of the optimal $(d, t)$ -pebbling number for the ordered pairs $(d, t) = (2, 2), (1, 4 m)$ and $(2, 10 m)$ , where m is any positive integer.

In the future, we will design variants based on this graph pebbling model and devise more interesting and challenging games. In addition, we will be interested in the following two problems in the game in cycle.

Problem 1.

How to distribute the pebbles on the cycle in Step 1 to maximize the difference of the expected value of the points obtained by the defender and that obtained by the attacker after executing Step 2 for the first time?

Problem 2.

Given n castles, how many times do Step 2 and Step 3 need to be executed such that the attacker has enough information to attack successfully?

Footnotes

Acknowledgements

Research supported in part by the Ministry of Science and Technology of Taiwan under the contract numbers MOST 106-2115-M033-002, 106-2221-E-305-016-MY2, 106-2221-E-305-017-MY2, 107-2634-F-259-001- and 107-2634-F-009-011-.

References

Chellali, M., Haynesb, T.W., Hedetniemi, S.T. & Lewis, T.M. (2017). Restricted optimal pebbling and domination in graphs. Discrete Applied Mathematics, 221, 46–53. doi:10.1016/j.dam.2016.12.029.

Pachter, L., Snevily, H.S. & Voxman, B. (1995). On pebbling graph. Congress. Numer., 107, 65–80.

Shiue, C.-L. (2015). Optimally t-pebbling graphs. Utilitas Math., 98, 311–325.

Shiue, C.-L., Chiang, H.-H., Wong, M.-M. & Srivastava, H.M. (2018). Optimal t-pebbling in cycles. Utilitas Math., to appear.

Stewart, I. (1999). Defend the Roman Empire! Sci. Amer., 281(6), 136–139. doi:10.1038/scientificamerican1299-136.