April 2022 Project description.
This is intended as a fun open-ended project requiring coding skills.
I myself do only rather basic Python, so you will be on your own to learn the required advanced skills.
A technical starting point is to understand implementations of the Dijkstra shortest-path algorithm,
because we will need variants of that method.
The overall goal is to investigate strategies within a very over-simplified model of the initial
stages of 4X games
exemplified by Stellaris.
In our model, there is a connected graph on n vertices.
We will eventually look at different models of random graphs, and take n = 600
which is the Stellaris default size.
But to get started we need to choose some random graph model, and a convenient model
is the relative neighborhood graph
on n random points in a square.
Note that this graph has edge-lengths, so there will be a unique shortest path between any pair of vertices.
For our game there is an agent -- imagine a scout or robot or spaceship etc, according to your favorite game context --
which a player can move along edges at speed 1.
The agent is started at one vertex, but cannot see all the graph,
just the neighborhood of vertices it has already visited.
There are different notions of neighborhood that one might use,
but let's start with a minimal notion, as follows.
Initially the agent sees the number and lengths of edges at the starting vertex.
Choose one edge to traverse; upon reaching the other end-vertex, it sees the number and lengths
of other edges at that vertex.
Continue; when reaching a new vertex, use some "strategy" to choose the next unvisited vertex
to move to.
Note that sometimes the agent will have already visited all the adjacent vertices, so the next
new vertex will be several edges away.
First stage of project.
Consider the nearest unvisited vertex (NUV) strategy, which is the natural "greedy" strategy:
after arriving at a new vertex, find (Dijkstra) the nearest unvisited vertex, and move along edges
(speed 1) to the closest not-yet-visited vertex. Stop when all vertices have been visited.
So the task is to write code to simulate this process.
It would be fun (but not absolutely necessary) to show this as a dynamic graphic with the moving agent;
at least we want a graphic of the path for a printout.
In fact this NUV model has been studied before; you can see a path graphic in a different random graph model in
my article here.
But the actual mathematics in that article is not relevant/useful for this project.
Note that in writing the code we can do the Dijkstra algorithm at the start, and that provides all the info we need.
Second stage of project.
To make a game, consider two players, each with one agent, starting from different (far apart, in some sense) initial vertices.
They each do the NUV walk at the same time, but with the extra rule that when an agent visits a vertex it becomes "owned" by that player,
and the other agent cannot enter it (it must reverse along the edge).
So the game ends when neither player has an unvisited vertex that is accessible to their agent.
At that time, all vertices will be owned by one of the players.
The goal of the game is that, at the end, you own more vertices than the other player.
Here is a drawn-by-eye small simulation.
Again, the task is to write code to simulate this process -- we want to see the shapes of the two final owned regions.
The code will be more complicated because we will need to update the Dijkstra scheme as vertices become inaccessible to an agent.
Main stage of project.
The stages above are preliminaries to the main theme.
The NUV scheme is just one strategy for exploring the graph.
We next want to consider the game where one player uses the NUV strategy while the other player uses some different strategy.
Then consider different strategies and discover which work best on which types of graph.
So the main activity in the project is to invent and study other strategies, and compare performance against NUV and against
other strategies.
Note: In real 4X games, the initial stages (explore, expand) differ from our model in several ways.
One can view (very roughly) this game as a "walking in the fog" analog of Go.
Update: January 2023.
(i) The process of exploration is accompanied by a slower process of claiming ownership: our simple model combines these into one process.
(ii) The visible neighborhood is somewhat larger than ours, which we adopted as the minimal information needed to implement NUV.
(iii) A player can create several agents, not just one.
(iv) Typically there are 8 - 12 players (the others, played by the computer) instead of 2.
Two students worked on this project in Fall 2022.
Here are their write-ups.
A brief summary: it is hard to find a strategy that beats NUV. We are confident that a human would beat an opponent who used NUV, but we do not know an explicit strategy.