This week, I worked on optimizing the physics simulation to improve a simulated shot’s runtime. During the interim demos last week, we noticed that the best shot algorithm would sometimes give a local minimum instead of a global minimum. I touched on this a bit last status report, but this is happening because simulated annealing is inherently random, and the fewer iterations it goes through results in more random outputs. To fix this, I tried implementing the physics simulation in C++, then using pybind11 to call the C++ simulation in the best shot algorithm file (which is in Python). Unfortunately, due to the overhead created by having to convert data from Python types to C++ types, the latency didn’t improve at all — the runtime was much slower because of the computational overhead.
I then tested three different variations to see which had the best runtime: 1) purely Python, 2) Python best shot & C++ shot simulation, and 3) purely C++. I figured that since C++ is an inherently quicker language than Python, option 3 would have the best runtime. However, through testing, I still found that option 1 (purely Python implementation) had the best runtime. I believe this is because Numpy vectorization in Python is incredibly optimized, and the C++ version of Numpy (Xtensor) is not. Below are the average runtimes of the shot algorithm for the three implementations on 10,000 random board positions (note that my computer was not plugged in, so runtime is slightly slower than the 25ms we were getting earlier with option 1).
Purely Python
Python & C++
Purely C++
This next week I will look into different ways to optimize the runtime of the purely Python implementation. I am still on schedule and everything I am working on as of now is pretty much post-MVP.