How can I make sure multiple player scripts all get the same amount of execution time per game tick?

Question

I'm looking for a way to allow players to write code in a high level language, but I need to be able to keep all script instances synchronized in terms of script execution time per game tick so that no player gets an advantage.

The purpose for this is a simulation in which there are many bots scripted by several people, and the bots are in competition. The idea is to have a level playing field by advancing the execution in a controlled way so that no bot can gain an advantage.

This also has to be synchronized in a meaningful way with the rest of the simulation/physics. Having control over granular execution steps seems like one way to do this, although I'd be open to other potential solutions. In other words, if i made up my own assembly language and associated interpreter, I could control execution granularly, but besides being a significant undertaking, assembly languages are far more difficult to work with then high level ones.

Here are some ideas I've come up with :

• If there is a way for each bot to run a simple OS/VM, that could work, provided the OSes can be instantiated, controlled/execution time metered, and interfaced with programmatically from .NET code, but I don't know of anything like that.

• A scripting engine like Google's V8 seemed like it would be awesome, but there's no way to ensure program A and program B can each be allowed equal execution time; line by line stepping doesn't work here, as a line from program A could read:

  q=(((x+y)/z)-(a*b))/c;
  

  while a line from program B could read:

  q=3;
  

  meaning running each line's program results in one (probably) executing for a longer time than the other.

Answer 1

High Level Languages Turn Into Assembly Languages

I think you're overestimating the difficulty of building a high level language to provide to your players, you can quite easily build an interpreter to your simple bot scripting language that compiles down to a bytecode that runs on a virtual machine you can advance in fixed intervals in parallel with other virtual machines that control your game.

There's a wonderfully simple and common sense approach to building an interpreted language in the Bytecode chapter of Game Programming Patterns that should be able to get you started with building your own language or at least helping you decide if you need to build your own language for it. If you really want to, you could dive into a more complex language, learn compiler frontends and code generation with Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman; I have a personal fondness to the 1986 print, but any other version should be just as valuable.

Once you have your language compiled down to your interpreter friendly assembly/bytecode just advance it at fixed intervals like anything else in your game loop; tweak as desired.

Answer 2

What you are trying to do is far outside the usual use-case of off-the-shelf script engines. Scripting engines use lots of optimization tricks to run code as fast as they can. But that means the programmer can not know for sure how fast code will actually run. The runtime behavior could also change when you install some minor update to the scripting engine.

But when you want to have a competing programming game where managing execution time is a core gameplay element, then you want reliable and consistent execution speed.

For that reason I think the best option would be to write your own script interpreter for your own scripting language.

This allows you to define how many resources each instruction consumes by having the engine track the gameplay-relevant "virtual" execution time of scripts separately from the actual real-world execution time. Now you are able to freely balance the resource consumption of each instruction for a more accessible and balanced gameplay. You can simply say "each bot gets 100 virtual instructions per second, each arithmetic operation takes one virtual instruction". That way it becomes predictable for the player how much runtime their script actually takes.