Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (524)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (592)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Balancing computation power  (Read 1216 times)
0 Members and 1 Guest are viewing this topic.
Offline thePerfectMan

Senior Newbie





« Posted 2013-01-04 13:10:21 »

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.
Offline Damocles
« Reply #1 - Posted 2013-01-04 13:22:15 »

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.

Offline Danny02
« Reply #2 - Posted 2013-01-04 13:26:15 »

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 Smiley
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Damocles
« Reply #3 - Posted 2013-01-04 13:28:05 »

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.

Offline thePerfectMan

Senior Newbie





« Reply #4 - Posted 2013-01-04 14:00:39 »

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.
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.

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.
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.

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 Smiley

Hehe, rules are there to be broken, eeh? Wink

Something like a Java bytecode interpreter API would be useful. => going googling
Offline Damocles
« Reply #5 - Posted 2013-01-04 14:05:39 »

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.



Offline Best Username Ever

Junior Devvie





« Reply #6 - Posted 2013-01-04 22:04:27 »

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.)
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

toopeicgaming1999 (64 views)
2014-11-26 15:22:04

toopeicgaming1999 (57 views)
2014-11-26 15:20:36

toopeicgaming1999 (10 views)
2014-11-26 15:20:08

SHC (24 views)
2014-11-25 12:00:59

SHC (24 views)
2014-11-25 11:53:45

Norakomi (28 views)
2014-11-25 11:26:43

Gibbo3771 (24 views)
2014-11-24 19:59:16

trollwarrior1 (37 views)
2014-11-22 12:13:56

xFryIx (76 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!