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.
Remember that physics is calculated not only while playing but also when other nodes check blocks for proper proof-of-play. Right now I can check about 60 blocks per second in one thread on my Core i7-3770. With 4 threads I will probably be able to check 240 blocks per second but many people have much slower processors. With your proposal physics simulation will become much slower and to really harm the bots we will need to make it at least 100 or 1000x slower. This will make block checking very slow, on some computers it will take several seconds to check one block, some probably would check new blocks slower then they are generated, inital synchronization with network will take days or even months, botnets will perform spam attacks sending a lot of invalid blocks and nodes will use 100% of their CPU time to check these blocks.
Maybe some one-way function can be used. For example client can be required to search for some nice hash each tick or second of playing so it will slow down playing, but checking solution will be very fast.