Post by 2020 in Graphomata comments

Viewing post in Graphomata comments

20204 years ago

Thank you! You've made so many cost-cycles contributions, will you get 1st place already in 2020?

When loop detection triggers, does it display "will be running forever" or "may be running forever" (those are different cases)? The former would imply a bug, the latter would not.

Most importantly, if you believe that the solution shouldn't work in the general case (with perfect nondeterminism), I can add larger inputs or improve the randomness until it is rejected.

In any case, please don't spoil the solution - while I could technically fetch it from the DB, I play the game on an equal footing without being exposed to players' solutions.

As for chat/community, well, I guess I'm still waiting for Web 3.0...

L0laapk34 years ago

I do believe I'm on track to reach first for now, I still have to optimise X5 and start working on X6, I do think it will take until 2021 tho :)

Many of my contributions are low hanging fruit, however I'm particularly proud of E4 (2 cond) and D7 (2 cond and complete undercut of all existing implementations in both cost and speed).

It does say "may be running forever", however I was under the impression that you implemented loop detection by checking if the current state exactly equals any previous state which it definitely does. The implementation I made has a limit to zero chance of running for infinite duration which I thought the game actively prevented you from making.

Either way feel free to look at my G3 implementation or G3 save board, it contains nothing of significance assuming you've finished G3 once, G3 is a straight forward level and none of the G3 designs I made are ground breaking (best I got with a 'proper' implementation was 3*26 cost for 321 cycles before I converted it to this 'broken' working 3*24 version) and it just contains some rng seed testing otherwise :P

20204 years ago (1 edit)

Solutions with few conditions are my favorite!

I've just tried to reproduce what I believed you did (the technique seemed obvious from your description), and got a 2*24 "solution" instead... The game does attempt to force you into general solutions that don't rely on randomness, but G3 is not a level I considered when I created the strategies for that (it didn't even exist).

Infinite loop detection is actually an approximation. First, it's implemented more like a solution for level <REDACTED> - comparing against all the preceding states would require me to canonicalize all of them, which would be prohibitive in terms of performance. Secondly, it runs graph isomorphism in a "best-effort" mode - it's possible (though not easy) to generate states that will make it run exponentially. If that happens, the algorithm stops after a few seconds and infinite loop detection is subsequently turned off for the level (the player also gets a message).

Because of this, for consistency, the game doesn't stop you from submitting solutions that have non-zero probability of not terminating even when it knows that this is the case.

By the way, the server receives solutions for verification only in compact form, it doesn't get the entire board.

Edit: should be fixed by now (for this level and 4 others), those solutions no longer qualify.

L0laapk34 years ago (2 edits)

Im back to complain about G3 :P Its the last level that stands between me and a perfect real score.

This time, I am getting bodied by RNG. I have two near identical setups, where the only difference is that one branch of an if statement has 1 extra instruction. Everything is otherwise completely unchanged. The frustration I am facing is that the setup with the extra instruction in the if branch is actually performing better than the other one. (longer if case: max 301 cycles, shorter if case: 308 cycles on a different input). I can provide more details if you wish, to avoid leaving spoilers in public you can contact me on discord (L0laapk3#2010).

I assume you added more randomness to the test cases to ensure my previous broken solution fails, however it seems also necessary to add plenty of fixed RNG test cases (if such a thing is possible) to ensure the max cycles seems consistent.

Also, as a suggestion, it would be nice to be able to have notifications if your score is beaten, etc. Maybe it would be an idea to set something up for this? Something like a discord server with bot that announces new best solutions would be nice. :)

Edit: messed up the two solutions in my explenation

20204 years ago

A quick reply: the phenomenon you describe is inherent, and adding the previous scenarios (which indeed included some "highly-regular" RNGs) won't necessarily help - it all depends on which type of RNG (constant or random) the worst case happens to occur in. I'm probably going to re-add them anyway for UX reasons, but meanwhile, have you tried reviewing the worst case in the profiler (accessible by clicking Cycles in Level Complete)? It may help you optimize for it if you so desire.

L0laapk34 years ago (1 edit)

I have indeed tried profiling it, which did further frustrate me :P

I have kept spoilers to an absolute minimum in these images:
The original version performs worst on input 13 with a max of 301 cycles, where, the A=D:y branch is hit 5 times. The improved version, which simply moves the A=B test up one space to exclude B join A when A=B:y, performs worst on input 26 with a max of 308 cycles, where the A=D:y branch is hit 8 times. This even makes it score 2 points less (357 vs 359..).

As you can probably understand, this makes it very frustrating to hunt for the 'best' 360 solution as it just feels like moving stuff around at random and preying to RNGesus. I'm not sure if this is fixable but I was hoping some of the "highly-regular" RNG's that I did notice in earlier levels could provide a consistent worst case for this level.

20204 years ago

You're right about that - the previous RNGs are back, and I believe that this issue is fixed now. Thanks for reporting it!

I've checked the option of a global RSS feed. Specifically, detecting changes in scoring thresholds and filtering the inconsequential ones is tricky to do automatically. There are other changes that are easier to notify of (e.g. to the leaderboards), but I don't think many players will be interested in such a mechanism (it will also be spammy).

I can give a heads up about my intention to reject the brute-force threshold for D8, one way or another. Other than that, it all depends on the people playing the game. Just make sure to save your savefile to a file so as not to rely on the browser's local storage policy for keeping it intact.

L0laapk34 years ago

Thanks for fixing G3.

I like out of the box solutions and that includes my D8 solution :P The exponential nature of the level makes it very attractive for unrolling, nothing wrong with that :P Especially because its just one level where it even is viable in the first place, and considering the cost tradeoff it will never affect the normal solutions.

If larger test cases are added, it will first of all start lagging the game quite hard and secondly, it will still always be more optimal to hardcode the bottom layers and add a proper iterative algorithm ontop of this. You could restrict the number of workers but this will invalidate a large potion of current solutions aswell as add significant difficulty for future players, and it will just bloat the root score instead if that option will be available.
Another alternative would be to just hard limit the cost but that would be quite lame. Overall I think you should just come to terms with the solution considering that it only really affects this level.

If the cost graph is the problem, why not make it logarithmic (for this level only maybe considering the exponential nature) and/or implementing a graph break?

20204 years ago

This is less about technicalities (the threshold is already excluded, so it doesn't affect other players' scores or graphs), and more about the concept that solutions work in the general case. If you need to change your algorithm whenever new test cases are added, then I don't consider it a valid solution, and I'll work to improve the test cases until it is invalidated.

Brute-forcing is actually the easiest one for me - it's evident from the graphs and doesn't require a "prove or disprove" process (recall that I handle players' solutions as black boxes). And D8 is not special in this respect, previous cases that I've invalidated included a solution that assumed out-degree <= 5 or so (I'm sure that it was out of the box...)

Note that this approach doesn't preclude loop unrolling as an optimization strategy. The game does favor minimal and elegant solutions (that's why cost is calculated as it is, and why certain achievements exist), but score is determined equally as a function of cost and cycles (i.e. commutatively).

itch.io

Viewing post in Graphomata comments