Each of the Python runs mentioned in the initial post took around 4 hours to execute. Although not as accurate, the issue can be demonstrated in less than 5 minutes through the use of:

  # If needed use the following to install Python3.8.0rc1
  $ apt-get update
  $ sudo apt-get upgrade
  $ sudo add-apt-repository ppa:deadsnakes/ppa
  $ sudo apt update
  $ sudo apt install python3.8

  # Use Python3.7 to produce baseline.
  $ python3.7 permutations2x2 --max_depth 6 | egrep "^# Total_Time"

  # Perform Python3.8.0rc1 execution
  python3.8 permutations2x2 --max_depth 6 | egrep "^# Total_Time"

When I did this on my server the Python3.7 execution produced:

  # Total_Time: 62.46

While the Python3.8.0rc1 execution produced:

  # Total_Time: 79.72

By running the program with "--max_depth 6" specified, the program only traversed through permutations that are up to 6 moves from the initial position. Although much less than running through an unlimited number of moves, the above run still showed the Python3.8.0rc1 run as 26.7% ((79.72 - 62.46) / 62.46) slower than the Python3.7 execution. Which is close to the 28.6% reduction in performance seen from runs with unlimited depth of moves.