game environment asymmetry?

[spongman]

I have two different players that are completely deterministic -
there's no randomness whatsoever. Every time I play them against each
other (synchronously) I always get the same score.

The weird thing is that the scores they get depends on the order I
specify them on the command-line.

For example, let's say I have players A & B.

If I do: java -jar coercion.jar -player synccpp A -player synccpp B
I get this result (every time)
Winner: 0
Score: 2600 (1717400) 400 (585200)


However, if I do: java -jar coercion.jar -player synccpp B -player
synccpp A
I get this result (every time)
Winner: 0
Score: 1200 (1060000) 800 (490800)



I would expect the environment to be completely symmetrical and for
the results to be:
Winner: 1
Score: 400 (585200) 2600 (1717400)
the reverse of the 1st set of results.




This seems like a somewhat serious bug to me: it means, that even for
fairly mismatched opponents, the outcome of the match depends more on
your position on the command-line than the quality of your
implementation.

[Mutu Cosmin]

Your assumption is correct only if players (A & B) don't affect each other. If they cross, clearly you can understand why the results differ depending on who makes the first move.

Assuming there is tie between players and that for the next move A and B would try to occupy the same square.

Assuming that A's algorithm is to occupy another empty square while B's algorithm is to retreat to an already occupied square by B.

If A moves first it will score two points and B none.
If B moves first it will score one point and A also one.

On Jan 25, 2012 10:24 PM, "spongman" <pie...@gmail.com> wrote:

[spongman]

I think you misunderstood my post. Please re-read it carefully.

I understand that the two players behave differently.

However, my expectation is that if you swap A & B then the scores
should also swap. In reality they don't. The playing field is uneven.

[spongman]

Also, the docs state:

"players only see instantaneous snapshots of the game state at the
beginnings of the turns"

so there's no such thing as moving first. both players move together.
or, at least, the forces returned by the players are applied to their
pushers at the same time.

[Stephen Denne]

If you generate trace files from each, you could figure out when they first diverge.

[spongman]

yeah, it's a bit of a pain because it would require rotating one of
the trace files 180deg.

i'll try dumping my own logs post-rotation and comparing those...

[Stephen Denne]

The two trace files would be identical if the  game was symmetrical, so without rotating one, the very first difference will show what causes the lack of symmetry.

[Stephen Denne]

Oh - they're different players? Both deterministic?

[Stephen Denne]

I can see the same thing with two deterministic players of my own.

Examining the trace files, the first difference is in the time of a collision:

collision 32.175551 5 19

vs

collision 32.175550 0 14

Then at time 40.333333 the first pusher location difference noticeable at the precision that the trace files record occurs.

14.9369 41.9231 -0.2999 -1.6672

vs

85.0630 58.0769 0.2999 1.6672

(Note the x positions add to 99.9999 instead of 100.0000)

The difference slowly increases, till in my game, at time 78.666667, a collision occurs in one game, but not the reverse. From there on, the games differ a lot.

Stephen.

[spongman]

yeah, they're both completely deterministic. it's all due to rounding
errors.

you have to rotate one, because the 'turns' file output by the
coercion.jar driver is always from the viewpoint of player 0 (the 1st
player on the command line). and since player 0 and player 1 have
different heuristics, the turns files /should/ be (and are) different.
they should be an exact rotation of each other, but they're not.

here's a ZIP containing trace & turns files
http://codewithoutborders.com/posted/turns.zip

there's one file of each type from each side (*1.txt are from A vs B,
*2.txt are from B vs A)

the 'trace*.txt' files are output by coercion.jar, if you diff these
you'll notice the 180deg rotation. for example, notice forces and
velocities are negated, and the the positions are all (100-x,100-y)
and everything's in the reverse order. this is all done by the driver.
and it's fine, it just obscures the errors.

the 'turns*.txt' files are the stdin of /one/ of my players. in the
case of turns1.txt it's after the driver has already done the rotation
on behalf of the player. I have already replaced instances of
'-0.0000' with '0.0000', but otherwise, you'll see they start to
diverge (by 1/10,000) at around turn 74. but by the end the scores are
completely different.

because of this I have written test scripts that run my players both
ways against each other over all the maps I have. The variation in the
scores is quite significant. here's a table of results from the
provided maps:

https://docs.google.com/spreadsheet/ccc?key=0AqykN8Qbx3NfdEdyMHNyT1FxS3hWcFVtZUlOWGQxeUE

each row is a map. the 1st 2 columns are the results when A is player
0. the 2nd pair are the results when B is player 0. the columns on the
right are the score differences for each game. the totals are below.
want to guess which is the better player?

I'm wondering how accurate a double-elimination round is going to be
given this level of noise. I suggest that, if the errors cannot be
fixed, each match in the tournament be the average of 4 games. with
each player taking turns to be in the player-0 slot.

Piers.

On Jan 25, 10:20 pm, Stephen Denne <step...@datacute.co.nz> wrote:
> Oh - they're different players? Both deterministic?
>

[Stephen Denne]

Oh.. correction (these differing trace files are hard to read)

collision 78.666658 4 27

 was in the other file:

collision 78.666680 1 6

However the differences do continue to grow, till they have an effect on the decisions of the players.

I don't think it is enough of a problem to need to have anything done about it. It looks like it is due to the limited approximation of locations, velocities, and times possible with floating point maths, and representing n vs. 100-n.

Stephen.

[spongman]

On Jan 25, 11:34 pm, Stephen Denne <step...@datacute.co.nz> wrote:
> I don't think it is enough of a problem to need to have anything done about
> it.

I think my results would suggest otherwise. they show that the
rounding errors can be significantly more important to the outcome
than the quality of the player.

[spongman]

Imagine that there was a significant advantage gained by playing White
in a game of chess.

Now imagine that the world chess championship final was decided in one
game, and the choice of black or white was decided by a coin toss.

Ok, so this isn't the world chess championship, but you get the
idea...

[Hogan]

I think your spread sheet shows a significant advantage to going
first.

A is clearly better but when first B gets a slightly higher score.
(The total of all game is positive.)

I was thinking why the first player gets then advantage. Then it
became clear....

If there are rounding errors in the rotation of the board the
algorithm is using in accurate information to to base it's
calculations if it goes second.

Bad data = bad result.

Does anyone agree?

Hogan

> https://docs.google.com/spreadsheet/ccc?key=0AqykN8Qbx3NfdEdyMHNyT1Fx...

[Stephen Denne]

I still don't think the rounding effect is that significant.

There are only ten maps, repeated in the 14 rounds files, so including the repeats incorrectly amplifies the difference.

Very small changes in locations or timings of things can result in different decisions, and it is those different decisions which determines the outcome. The biggest effect is when a collision or change in pressure on a region no longer occurs just before the start of a turn, but would happen just after.

I tested the ten maps with two players of my own, and got the opposite results:

A vs B B vs A A vs B B vs A

map A B B A A - B B - A

0 4600 4600 2800 6600 0 -3800

1 4525 4175 4300 5000 350 -700

2 5400 3200 6200 3600 2200 2600

3 8400 400 1500 6100 8000 -4600

4 5200 3400 3800 5800 1800 -2000

5 7500 1350 900 7950 6150 -7050

6 4600 3800 3200 5400 800 -2200

7 6100 2700 2600 6000 3400 -3400

8 9200 800 4600 5400 8400 -800

9 2700 5300 400 8400 -2600 -8000

28500 -29950

Overall my player A appears better than my player B, with a slight advantage to being the second player, but that is all thanks to map9 having a much bigger score difference than map2.

I think that the locations are reported with less precision than they are stored within the simulation engine. A possible improvement is to change the simulation so that at each step, the stored locations and velocities are rounded to the values reported in the trace files and to the players.

Stephen.

[spongman]

On Jan 26, 5:06 am, Stephen Denne <step...@datacute.co.nz> wrote:
> I still don't think the rounding effect is that significant.

You're right, the rounding effect by itself is tiny.

What is significant is that it can affect the final result.

I think the chess analogy is a good one, but consider after the IPCP
final: a winner is declared, but it is later discovered that when the
order on the command-line is switched, the 2nd-place player becomes
the champion.

both our results show that this outcome is entirely possible, indeed
likely.

[masato12610]

Maybe we are seeing an example of chaos theory in action.
http://en.wikipedia.org/wiki/Chaos_theory

[Nooch]

Out of curiousity, does anyone know if coercion.jar uses
java.lang.math or java.lang.strictmath? I had a major problem with
determinism using math. Forced us to use strictmath instead.

On Jan 26, 1:26 pm, masato12610 <jimthompson5...@aol.com> wrote:
> Maybe we are seeing an example of chaos theory in action.http://en.wikipedia.org/wiki/Chaos_theory

[Mike]

This does seem like a problem that needs to be addressed before the tournament. 

I have a hard time taking this seriously when the environment is susceptible to deterministc chaos.

Mike

[Mutu Cosmin]

It appears to be using java.lang.Math

[Claus Makowka]

This is a very interesting thread. Sorry to be joining it late.

First, the good news is that deterministic players do yield repeatable
results. At first blush, I would have claimed that my player,
implemented in Java, is deterministic. However, I iterate over data
structures like Sets which rely on an object hash, that in Java
defaults to the object memory address, more or less. Even with new VM
image for each game, there appears to be enough variation in object
memory addresses to result in decidedly nonrepeatable results. I only
mention this because the game engine is in Java, so it appears to
avoid that implementation problem. However, this does illustrate that
the game is quite sensitive to small changes.

The rounding problem is worth considering. Even classical mechanics
is subject to the chaos problem that small errors in initial
conditions can lead to large errors after long time. The time frame
of the game seems a bit short,
but this is not real classical mechanics either. We have forces
applied instantaneously and then everything coasts. The game only
reports 6 digits of precision, and in the home region the precision is
even lower, due to the fixed point representation. However, if the
rounding error is enough to shift a collision from one turn to the
next, then it would create a large effect on the collision due to the
gravity impulse on marker and pusher, and the acceleration impulse
that may be applied to the pusher. Suddenly a 0.01% error (100 turns
of round off) can result in a much larger change in the collision.

This does not also rule out a potential problem with how collisions
are implemented. Whenever more than two objects are involved in a
collision with each other during the turn, the computation of the
collision could be sensitive to the order in selecting objects while
calculating collisions. This applies in particular if the collisions
are computed algebraically, as the game rules appear to imply.

That said, I am not convinced that we have a major problem here.
spongman has reported one case where for a pair of deterministic
players, the results favor being the first player position on the
command line (red). Stephen Denne confirms the asymmetric behavior
with another pair of deterministic players but has not commented on
whether being the red player is an advantage in that case. Given the
causes suggested, I do not see why the asymmetric behavior would
always favor being the first player on the command line (red), for all
pairs of deterministic players. Moreover, the game is a simplistic
simulation of controlling robots (the six pushers) and any physical
robot cannot be controlled
with absolute precision, so even a deterministic controller would have
varying results. The player (controller) needs to be robust in the
face of variable conditions.

At most an argument can be made that each pair of players should play
each other twice, reversing colors between games and combining the
scores to determine the winner. This eliminates the effect of any
"bias".

On Jan 26, 1:39 pm, spongman <pie...@gmail.com> wrote:

[Hogan]

It should be the case that you can make a given deterministic player
safe from these issues by only using a few digits of the input when
generating your turns. In this way minor changes in the input won't
have exploding effects on what a given player performs.

Has anyone tried this?