A* Craft - Feedback & Strategies


#41

So I just fixed my bug and submitted in multi player version.

Took me like 10 minutes :confused: I score around 8500 which is not great but still better than my 4500ish score in the contest.

The bug was pretty obnoxious compiler default behavior stuff:

unsigned char myByte = 0xff;

The test: “if (~myByte)…” I expected it to equal if(0) but it was always true probably because of default promotion to int I guess…

It was not hard to find as it implied an immediate and constant issue but I was short on time and was also a bit sleepy at the end.

At least i’m quite happy it wasn’t a 12k score, I would have been very frustrated lol.

My strategy was pretty simple, I just simulated moves and tried to change direction when a bot was about to disappear, I also randomized the cells and kept best results at time limit…

I’ll try a few different things to see if i can improve :slight_smile:


#42

Hi!

Congrats Magus and Agade for a nice puzzle! I didn’t have time to participate unfortunately.

About the auto-submit of codes: it’s quite an old feature that was too risky to take care of in such a short time. We realized it during the contest… I’ll think about it in the following days. We have a larger issue concerning the global competition (contest points vs multiplayer points) that is getting worse with every contest. I’ll unearth the related forum post and relaunch the discussions.

About the contest points themselves, there was a bug and the points have been wrongly awarded. Thanks @papyjo for noticing it.


#43

I use an array of unsigned char[4], each one of them representing the visits of all the robots in a particular direction (UP=0, RIGHT=1, etc)

So:

grid[x][y]->visited[UP] = 1 (in bits 00000001) means robot 0 visited cell x,y in the UP direction
grid[x][y]->visited[LEFT] = 9 (in bits 00001001) means robots 0 and 3 visited cell x,y in the LEFT direction and so on.

To check if a robot visited cell x,y in direction dir I use

if (grid[x][y]->visited[dir] & (1 << robot_id)) { }

To mark a cell x,y in direction dir as visited by robot_id I use:

grid[x][y]->visited[dir] |= (1 << robot_id);


#44

Maybe we’ll have the formula modification we ask for years ? :heart_eyes:


#45

And how did you reset state to run a new simulation without cleanup? Or you just throw away this array and take new one from pool?


#46

Oh yeah, this one is deleted. I reset the map and the robot positions/directions only


#47

Hello. Thank you for the great contest.

For the first a suggestion about point calculation. Now you just take sum of results for all final tests as final score. This approach is stimulate to take care only about big tests with many points (where you could gain or lose 100 points at once) and forget about small tests. Nothing is changes for you if your algorithm could not find solution for 100 point in Roundabout and find only for 99 or 95. I suggest to change point calculation in next contests by something like this:
For each test order all results from all participants. Then all who gain top 1 score on this test will get 200 points for this test. All who gain top 2 score will get 150 points. 3rd score - 100 points. All the rest - (50-order of his score).
Such system will stimulate to achieve best results on each test even small one. There was some smart optimizations in A*Craft for small puzzles that could not help in big ones. For example removing arrows in long corridors. Another example is splitting optimization in puzzles that factors on several independent areas. But this techniques did not bring almost anything because they are not work in big tests and effects from them is very little among optimization for big tests.

Now about my solution. I finished 24 with 9,394 points. I used Late acceptance search algorithm with history window of size 8 and restarting after 6000 turns without improvement. As mutations i used changing arrow is single cell. Probabilities of changing to empty arrow is made higher then probabilities for changing to direction arrow. Some arrow directions was excluded from mutations: arrow pointing to void or to opposite arrow.


#48

Where does this information come from ? Did you checked among all the plays in your DB ?
754 seems to be the maximum for this test, am I wrong ?


#49

He said during the contest that he checked the best score for each test cases he found in the database for all submits. So someone submitted a code that does 784 for the 29th test case.