[Community Puzzle] SameGame

https://www.codingame.com/multiplayer/optimization/samegame

Send your feedback or ask for help here!

Created by @aCat,validated by @radekmie,@Zylo and @hoggi.
If you have any issues, feel free to ping them.

1 Like

I hope you will like the game :smiley_cat: If any issues or comments, please don’t hesitate to contact me.

SameGame has been used as a benchmark in several publications concerning simulation-based algorithms: Single-Player MCTS, Nested Monte Carlo Search, and Nested Rollout Policy Adaptation. Most of those are openly available, so you can take a look if you’re interested. I hope this puzzle will serve as a motivation and a good opportunity to learn something new and improve AI skills.

Have fun and good luck.

PS More stuff like this coming “soon” :smirk_cat:

8 Likes

Easy to code 100% success e.g. with “clicking” the biggest pool and then long way to master the algorithm.
That’s addictive.
Somehow not many tried this puzzle.

2 Likes

I lack of experience and knowledge, thus I’m going through theory of MCTS.
There are some simulations to be made, and my question is if I have to code SameGame game algorithm (not efficient in python) or is there a way to connect simulation with already existing game algorithm?

There is no possibility to merg your code with other existing code. All the work is expected to be made by your program.
However, you can take a look on the engine implementation (in Java) to hel you with writing your simulation-based algorithm.

2 Likes

Human-playable version link is not working!
Please, fix.
Thanks!

1 Like

This is not my server, nor I have anything in common :crying_cat_face: .
So sadly anything I can do is wait for them to resolve issues.

1 Like

It is back up now.

2 Likes

Stuck at 80% completed. But no errors in the test run. Any ideas on how to understand what is triggering errors in the validators test cases?.

Hard to say… the validators follow similar pattern as tests, and as long as you perform legal moves everything should be ok. 80% means that your program fails four of the 20 initial positions.

You can download the game source from here - https://www.codingame.com/contribute/view/52286850570a02e25f12d5b1b9a30bdb954c and see how your program behaves on all the validators. (StandardTestset.txt file from test/java)

1 Like

Or click “test in IDE” at the link from above and get access to the validators.

1 Like

Thanks, worked to run the validators that way. :slight_smile:

Nice puzzle, I really like it, even though my current score is not too high.
Even with the allowed 20sec, I run out of time and cannot clear completely many test cases.
I can simulate only 20-25k moves per second (that was 3x less before some micro-optimizations in my code).
So I am wondering how people on the top could reach such stellar score:

  • Using a much better search algo with more efficient pruning, getting bigger regions to clear at once for the quadratic score?
  • So much faster simulation code is achievable?
  • OR: as the github link includes the validator inputs (…does it? I see 50 test cases there, IDE has only 10…), does everyone on top find the solution offline using much more CPU time and the submitted code is only test case detection and submitting hard coded actions?
1 Like

I searched offline. I know about some people ranking above me doing the same. As suggested above, you have view the contribution to see the validators. Actually there are only 20 different ones. The next 20 are the same with swapped colors (which is why everyone at the top has an even score: offline solver and each testcase twice).

2 Likes

Thanks for the help. I have no problem with offline search, that is also an interesting coding challenge, although bit a different one than the original…

Very interesting puzzle to learn about Single-Player MCTS, thanks!

I just tried to find the origin of the standard testset for samegame and failed O_o. @aCat can you help me? Every academic paper reference this testset, but what is it’s origin?

http://www.js-games.de/eng/games/samegame/lx

1 Like

How many time did you turn the offline beam search ? for hardcoding after? it takes a long time for a little gain.

Fantastic puzzle ! I love that we can compare our results to a standard test set used in papers about the problem. I tried the pilot method (evaluating every possible move with greedy rollouts), with decent results (around 27000 with no offline computation or tuning)

My main problem is most of my computation time is spent cloning the grid to perform the rollouts. Has anyone tried a more efficient way, maybe partial cloning or reverting changes to the grid ?