Feel free to send your feedback or ask some help here!
can any1 help me with the last test case in this puzzle(single queue)?
I’m not sure about the lightning strikes. They go in a square of 9 spaces around Thor. Does that mean the strike hits everything 4 spaces North, East, South and West? Also, does the strike hit the giants at the point where they are when the “STRIKE” command is given or at the place where they will be the next turn?
How do the giants move? It seems like they are not moving optimally. By this I mean they do not always go diagonally when they should (look at the video here: https://www.youtube.com/watch?v=KOTLzGqw51A). I firmly believe that if they moved optimally, the last two test cases would be impossible to solve.
Example (distance = 0 spaces vertically, 4 spaces horizontally):
--------------------------------- | | | T GGGGGG | | | ---------------------------------
If Thor goes north in this situation, all the giants should optimally go northwest, however the giants go west instead.
If the giants moved optimally, the result would be (distance = 0 spaces vertically, 3 spaces horizontally):
--------------------------------- | T GGGGGG | | | | | ---------------------------------
In reality (distance = 1 space vertically, 3 spaces horizontally):
--------------------------------- | T | | GGGGGG | | | ---------------------------------
Thank you for the answer.
I noticed that you need a Range of 5! 4 is the Hitrange of Thor and 1 more because the Giants move before the Strike hits.
T -> Thor
X -> Strike will hit here
I’m trying to solve the hard puzzle : Thor Vs Giants, and I’m block on the two last tests, where all the giants are in one line.
Do you have tips, general ideas, how you detect that you need to not got for the centroid and take a longer path?
@cerobe I moved your question here, try to search for the topic before creating a new one.
I di try to look, but thought it was like always => title of the puzzle equal title of the thread.
That not the case here so it’s confusing.
Fair enough, you can get to the appropriate topic directly from the games page by clicking DISCUSS.
For this puzzle the best way is to evade the giants strategically in order to get them together, and use your strike only when you are cornered or if you can kill them all in one blast.
Yeah this almost what I am doing, I strike only when I’m cornered.
So every time I move in direction of the direction of the centroid, or the direction of the closest safe place to the centroid.
I undestood that I need to improve my evade strategy.So I was wondering, how I could improve that.
I though about some complicated steps, like calculate how many strikes I need to kill all the giants giving the current giants positions, then if I’m short on strike try to regroup them by moving (as they are attracted to me).
But even here I’ll need to know how they moved.
So I guess there is an easier way, but I can’t find it.
The thing I remeber about this puzzle was not about moving into the center of the unoccupied places, it was moving so that giants afar get closer, that means i move in order to get the giant to the same distance. I dunno if that helps?
Not really, because in my opinion you still need to know how the Giants will move.
I think I’ll just assume a way how they move and try to solve the problem with it.
I believe it uses kind of “natural” algorithm - so it selects direction basing on real angle to Thor. So if it is closer to 45 than to 90 then it uses 45.
(so when smaller difference between coordinates is less for tan(22.5) times shorter than larger difference then it goes straight )
You’re right it is not optimal, if they behaved like you suggest it wouldn’t have any solution.
Okay I need help with this.Just moving to the controid or safe place when cornered dosent help.Any tips ?
Moving toward to the centroid (even with some cleverness) won’t help you with the queuing tests. My working solution involved some linear regression and a bit of good old fashioned linear algebra.
I needed to be able to foresee the giants moves to solve it too, in the end I used thresholds at 30° or 60°, not 22.5° and 67.5°:
For example, if a is the angle between the direction and the horizontal:
- if abs(a) <= 30° the giant will move horizontally
- if 30° < abs(a) < 60° the giant will move diagonally
- if 60° <= abs(a) the giant will move vertically
These values for tan are nice enough to make the comparison easy. ^^
If I remember correctly there were still times when the giants were a bit off when compared to my predictions, but I blamed that on the order the algorithm picks to move the giants.
You can solve it with a simple minimax to depth 1 (so a max, really), and it’s not too hard to find a good evaluation function… But before I figured out the giants moves, I spent quite some time trying to tweak my evaluation function, without success.
Havn’t solved it yet but my testing of the giant’s movement leads me to about 28 degrees 30 wasn’t explaining certain moves.
EDIT: Struggled alot to solve because I havn’t been able to predict giants’ moves perfectly. The problem is when two giants covet the same spot. Winning solution was a bruteforce over 2 turns (only) where the move that surrounds you with as many giants as possible is preferred. Striking is done when a move is impossible.
Hi, with little difficulties and after reading the forum, i solved it without knowing how giants move. I used a game evaluation with giants distance, giants center, and space from borders because of the last test. This puzzle was very interesting, and i was ready to implement min max, but all tests passed on deep zero,
But i don’t know if all this is very optimized because on last test, i choose direction to the larger side of the board, and i think that if the board had been shorter, Thor would have been killed.
So my method is more a lucky balance between searching the center, avoid being too close of giants, and choose the more space in all that.
Thanks to all contributors on this forum, because it helps a lot.
I implemented a solution like yours and the comment about taking into account the space border in the heuristic helped a lot. Thank you !
This method helped me too with the last test case. It’s a bit lucky, but also smart. Thanks man!