We have a game, that is real-time, thus not round-based.
For our AI we firstly considered a game-tee search like minimax etc. This leads to a problem for us:

Usually in our tree we would have a first layer of possible moves and their ratings for ourselves. On the second layer we would then have the possible moves of our opponent and the ratings of those moves, dependend on the moves of the first layer and so forth...

In our special case we now have the problem that the execution times of such moves may lie uneven to each other:
Initially e.g. a "turn right/left" costs 25ms, a "move forward" costs 50ms. This is not such a big problem, since 50 is obviously a multiple of 25 and we could thus slightly modify the tree to reflect the correct behaviour.

However, one can collect special powerup items that e.g. increase one's speed by let's say 20%. Now let's assume our opponent collects such a thing: His rotations now only cost 20ms and moves forward 40ms.

***
That means effectively that in the time we e.g. do 4 moves (200ms), our opponent could do 5!
***

Our problem is now: How should we be able to model this behaviour in our game tree? I s a game tree actually still the most sensible approach for such a real-time situation (in fact, it is a kind of bomberman - just that you get the feeling)?

Thanks for any help,
Eric

P.S. I have read the tutorial on game-trees and real-time but I fell that in our case it does not give a proper solution.