And what about adding some computationally intensive randomness to physics (like computing many many hashes each tick and adding it to velocity). This will make bot's speed comparable to normal human playing speed. And without careful planning bots will definitely lose.
Along with 4x sized map it will knock out bots for at least a couple of months.