Balancing computation power

Game Mechanics
#1

Introduction
I am writing a 2D soccer game which is kind of multiplayer. It is special in the way that players are driven by third party software. In short: Someone implements the given interface for controlling a soccer player, plugs his player implementation into the game engine together with the implementation of someone else’s player implementation and both implementations will play a soccer match against each other. This is similar (but simpler) to RoboCup’s Simulations Leage (http://www.robocup.org/robocup-soccer/simulation/, http://www.youtube.com/watch?v=BVWkndHk3AE) or MIT’s Battlecode (http://www.battlecode.org/) competition. The game is written in scala with use the akka (akka.io) actors.

I will copy parts of this introduction to other questions refering to this game as necessary.

The balancing problem
I would would like to see, that a player wins a math, because of a superior algorithm and superior implementation and not because of other criterea like availible computation power. So resources, especially CPU, time must be balanced and ideally equally distributed over the players, resulting in a fair competition.

What general concepts, approaches and availible implementations / APIs exist to solve this problem?

Here are some approaches I can think of:

  • The battlecode implemtation does execute a limited amount of bytecode (I think per cycle). Cycles are completely transparent to the player implementation. I think they use ASM (http://asm.ow2.org/), but I am afraid they made some customizations (don’t know exactly).
  • Maybe I can use a custom scheduler, dispatcher or something similar (maybe rewriting some class of akka), to perform “round-robin” or something similar.
  • There is a discussion on this topic here: http://www.techtalkz.com/java/130899-byte-code-execution-count.html with a proposal to use java.lang.management to measure CPU time. Don’t know more about this, yet.

Do you have experience with this problem, some hints or other approaches to share?

Thanks in advance.

#2

With the simulator you could imlpement a reference algorythm wich uses a lot of Resources/time per cycle.
This is defined as maximum Resource usage.

You can then measure the simulation with the reference algorythm and then with the
algorythm to test against.

If the new algorythm takes more time, its disqualified. (or put into a higher category)

This way the developer can locally test his implementation against the (max)reference.

Using an average over several simulation rounds should be used though, to adjust for temporary PC load by other
processes.

#3

why does computation power matter? the game is running in logical ticks. When a match is simulated one just has to wait for both player-bots to finish the current tick before the simulation can proceed.

Also, when both bots are run on the same processor both have access to the same power. You could of course measure the time each bot had used in total in a match and then use this to weight the match outcome.
But this can be abused of course, one could write a bot which maneuvers the opponent in positions for which it needs much time to decide what to do :slight_smile:

#4

This would put brute force approaches to an unfair advantage.
(like calculating millions of action-combinations to choose the best one)

Best is to use a cap on the available resources, but within it let the algorythm use as
much as it wants.

#5

Yes, it is one possible design decision. The advantage is that it is guaranteed that every player got some CPU time and chance to calculate something. The disadvantage are possible delays if a player takes very long and that cycles are visible to the player implementation.

The other way would be execute a loop for each player and let it process the same amount of computation on each cycle. That way cycles are transparent to the players and if they take a bigger amount of computation this could be a disadvantage compared to the opponent player, but may result in a better decision of the player and all players would have the same chance to make good decisions per time unit which results in something like fairness, I hope.

I am not sure if this is true. What if the OS-scheduler, Thread-API scheduler or akka dispatcher / scheduler decides to give one player more CPU time than another one? Context switches are transparent to user space processes. I will have to look at java.lang.management what possibilites there are to measure CPU time.

Hehe, rules are there to be broken, eeh? :wink:

Something like a Java bytecode interpreter API would be useful. => going googling

#6

Remember common chess tournaments:

every player snatches on a chess-clock when ending his turn. (tick cycle)

So every competitor has limited total time until the game ends.

I think this method is very applicable to your scenario.

http://static.zoovy.com/img/thechessstore/W600-H400-Bffffff/chess_clocks/value_wood_chess_clock_dark_600.jpg

#7

A lot of it will be beyond your control. Context switches, background processes, and garbage collection could all interfere with one player or the other. On top of that, you may have important hardware differences that mean that even if two CPUs run for the same amount of time, one might implement certain operations more efficiently and execute more of them. If you want every program to run the same everywhere, you will need to implement a simulator that runs slower than real time and uses substantially less time so that delayed simulations can take time to catch up.

If it does not need to run the same everywhere you could give each player a copy of the program. Assuming a deterministic algorithm, you could let them both run a copy of their own and their opponent’s code and use the results from the slower of the two outputs. (You would use some type of logging system where each person saves their tentative results.) Then ask each player 'How many log entries did you write?", take the smallest number, confirm that both players got the same result, and use those (the result of whichever machine is slower.) The downside to that is that a person could deliberately slow their opponent’s program, but if there is greater disincentive to cheating than there is incentive, then it won’t happen.

Game theory (the prisoner’s dilemma) would say both players would pretend their opponent couldn’t log any result and let their own programs run at full speed, but would they bother in real life? If so, then you could run the programs on a mutually trusted third party’s computer (and use that exclusively) or use an unbiased third party to “referee” the log results. (Maybe look out for suspicious behavior for example; Or, run the simulations themselves after the fact to see if the results would have been the same if you did not use the real time requirement and let both algorithms run for approximately the same amount of time as it would take for the referee to reproduce the results of the faster machine’s personal results.)