Name
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 pi*((d,t))(G). When the number of FAs is less than pi*((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 pi*((d,t))(G) for d = 1, 2 and determine the exact value of pi*((d,t))(G) for the ordered pairs (d, t) = (2, 2), (1, 4m) and (2, 10m), where m is any positive integer. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.3233/ICG-180052 | ICGA JOURNAL |
Keywords | Field | DocType |
Game design,(d,t)-pebbling | Computer science,Artificial intelligence | Journal |
Volume | Issue | ISSN |
40 | 4 | 1389-6911 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jr-Chang Chen | 1 | 42 | 15.19 |
| Chin-Lin Shiue | 2 | 10 | 3.93 |