Choosing the Optimal Turn Order for Board Games

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.

Theory

board_game_schedule

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.

schedule_2_closed_cycle

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.

Exporting Eufy Smart Scale’s raw data from android

From a default to a custom chart.

Eufy Smart Scale and App

I recently purchased a Eufy Smart Scale. Not only does it automatically record my weight and upload it to the Eufy app, it also provides a breakdown for details like muscle mass, body fat, and more. While I enjoy having the data conveniently recorded, the charts fail to answer questions I have. Like how does my data vary over periods of more than a week? Is there a correlation between time of day and my weight, or day of the week and weight? To answer these questions and more, I wanted to get Eufy Smart Scale’s raw data off my phone and onto my computer. While these steps are specific to Eufy’s app, they can work for other android apps, too.

Getting Eufy Smart Scale’s raw data

To get the data, some special software is required. Fortunately, you do not need to root your phone to make it work. While these steps are focused on Windows, they should also work for Mac or Linux with a few changes.

      1. First, create a folder for us to work in. We’ll say “smart_scale”.
      2. Now you need to download  adb (https://developer.android.com/studio/releases/platform-tools) to your PC, and extract the archive to the “smart_scale” folder. adb is a tool for debugging android apps, but for us it also allows us to download data from apps on a device.
      3. You also need Android Backup Extractor (https://sourceforge.net/projects/adbextractor). Download and extract the archive and copy “abe.jar” in “android-backup-tookit\android-backup-extractor\android-backup-extractor-20180521-bin” to the “smart_scale” folder. Note that “20180521” may change depending on your version. Android Backup Extractor will extract the data from adb.
      4. Enable debugging on your android device (https://developer.android.com/studio/command-line/adb#Enabling). This allows adb to connect to the device.
      5. Plug your android device into the PC with USB. If prompted on the android device, select “Allow USB debugging.”
      6. Open a command prompt and navigate to the “smart_scale” folder.
      7. Now we export the data from the device using adb. From the command prompt, run
        platform-tools/adb backup -noapk com.oceanwing.smarthome

        Enter (and remember) a password when prompted on the android device. The name ‘com.oceanwing.smarthome’ can be seen as the app name in the Google Play Store URL.

      8. You should now have a file titled “backup.ab” in your folder containing the app data.
      9. Extract the backup by running the following from the command line, and when prompted enter the password you just made.
        java -jar abe.jar unpack backup.ab backup.tar

        Note that you may need to change “20180521” depending on what version of abe you have.

      10. “backup.tar” is now created in your “smart_scale” folder. Unpack it using your favorite file archiver (like 7-zip). You’ll see the raw data as a SQLite database at “apps\com.oceanwing.smarthome\db\EufyLifeDB.db”.

Accessing the Data in SQLite

You can access the data with SQLite

      1. Download SQLite3 tools from https://www.sqlite.org/download.html, and extract the archive to your “smart_scale” folder
      2. Access the database from the command line with 
        .\sqlite-tools-win32-x86-3350300\sqlite3.exe .\apps\com.oceanwing.smarthome\db\EufyLifeDb.db

        Note that you may need to change versions or folders in that command depending on your setup.

      3. View a list of tables with the “.tables” command, help with “.help”, or see the full documentation at https://www.sqlite.org/cli.html.

Visualizing the Data with Tableau

You can use many ways to access and visualize SQLite data. I used Tableau, and connected to the data using the SQLite instructions found here: https://help.tableau.com/current/pro/desktop/en-us/odbc_customize.htm. Use the table name “bodyfathistorym” in the data source pane. One thing to note is that after connecting to the database, it’s helpful to create an extract. SQLite doesn’t support many common database operations, which means Tableau won’t be able to perform certain data operations. To see my own visualization, look below or see it on Tableau Public.

And to answer one of my initial questions: it seems that my weight increases throughout the week until the weekend, when it drops, possibly because I’m working less and outside more. If I wanted to lose a couple kilos, maybe one option is to exercise more during the week.

Notable columns in Eufy Smart Scale’s raw data

The table “bodyfathistorym” contains the interesting data, and within it, some of the notable columns are as follows.

Column Name Description
createtime Unix time when the weighing occurred
weight Total weight (kg)
impedance and encryptionimpedance Presumably used to calculate values like muscle and fat mass
bodyfat and bodyfatmass Body fat in % and kg respectively
muscle and musclemass Muscle mass in % and kg respectively
bone and bonemass Bone mass in % and kg respectively