The number one thing that causes a lot of lag is loops within loops.
Eg:
For each asteroid
Compare to all other asteroids
Loops within loops are somewhat inevitable though, unless you build an ai that precalculates all the relationships during levelsetup and stores the data in a series of matrices.. But that is not a trivial thing to do, and means the ai can't cope with moving asteroids.
The number one challenge in building a deadly ai is identifying generalised circumstances with generalised responses. Once you know what the ai ought to do in a given circumstance, you can build your rules so it responds appropriately to that situation.
For example, imagine the ai starts with a single asteroid, with 2/4 trees, 50 seedlings, and two nearby asteroids - one with good stats and 3 neighbouring unknown asteroids, the other with average stats and 2 neighbouring asteroids.
What is the optimal opening actions for the ai to take?