For those of us that play board games with friends online, especially games that take multiple days, waiting for friends to make their turn can stir some impatience. While waiting for my turn in a game against friends across 3 countries and 4 time zones I realized our turn order was less than ideal given our schedules. This presented a great opportunity to work on my React skills and make our games run faster. Thus I created a board game scheduler to choose the optimal turn order for board games that minimizes wait time based on everyone’s schedules and time zones.
- To try it out, go to: https://stcase.github.io/board-game-scheduler
- To see the code in React: https://github.com/stcase/board-game-scheduler
- And to learn how it works, read further
Theory
The image above is a hypothetical schedule. Each number represents the hour of that person’s local time with UTC time at the top. Green squares represent when that person is available to play. It’s quickly apparent that if the turn order is top down then two rounds can be played per day, but if it’s bottom up then there is less than one round per day. The goal is to find the most turns per day possible.
I turned to Graph Theory. Each playable hour (green square) is a vertex in a graph, and each edge points to the next player’s playable hour. The weight of each edge is how many hours away the next player’s turn is. The rules are:
- A green–or available–square points to the square below it with an edge weight of 0.
- An unavailable square points to the square to the right of it with an edge weight of one.
- When an edge points beyond the bottom or right of the grid, it wraps back to the top or left.
- From the above, each vertex can only point to one other vertex, but each vertex can have bewteen zero and two vertices pointing to it.
- All vertices are adjacent to their connecting vertices.
We can try different permutations of player orders, construct the graphs, and pick the graph and turn order that provides the optimal solution. It’s tempting to phrase the graph as a shortest path problem, but that unfortunately doesn’t work. What we want to do is find the cycle with the maximum rounds per total weighted path. That means the cost function is dependent not just on weights, but also the number of vertices visited. However, there are some other tricks we can use.
Because each vertex only points to one other vertex and all vertices are adjacent to their connecting vertices, it creates some useful features for solving this:
- Multiple closed and separate cycles (of the same length) can exist in one graph.
- However, any closed cycle is equal to the optimal solution for the graph.
The first point is simple: you can have two possibilities of timing as long as they have the same path length. For example, in the image below there are two cycles for a turn order running from top to bottom. One starting at 11 and one at 19 in Japan. The second feature in the list is key to solving the problem: any closed cycle is an optimal cycle. If there was a more and less frequent cycle in the same graph, the more frequent would intercept with the less frequent (because all vertices are adjacent to their connecting vertices), and thus the less frequent one would become part of the more frequent one.
The solution is then to traverse the map until a cycle is found, because any cycle is an optimal cycle. Once a cycle is found, recurs back to the meeting point and subtract the edge weights (hours) and turns to get the amount of hours and turns in the cycle. With that you can get the optimized rounds per day.
The traversal of the map will need to be completed for each permutation of player order. We can start with the first player on the schedule without permutation because turn order is what matters, not who starts. Unfortunately, this permutation of players gives a run time of (n-1)!. If too many players are added, the algorithm becomes prohibitively slow. For now this is working well enough for my friends and I, but possible future solutions might be to reuse or not recreate the map traversal for each permutation.