Hey guys! I currently made a simulator that takes in different possible attack options and return each simulation’s damage done to the enemy and the breach count. Also, I simulate the scenario where I “delay” executing my bits and form a larger attack next round(never delay more than one round). So I kind of simulate every spot that is available to drop troops, which is around 20 of them in to total. And since I’m taking the “delay” scenario into consideration I have to double the simulation times, which then comes to around 40. However, my simulator isn’t efficient enough to make so many simulations. What’s worse is that if I take different defense option and enemy’s possible attack into consideration it will slow the simulator even more.
So there are two problems right now. First, should I try to optimize the built in path finding algorithm and my simulator so I can make more simulations in one round or should I make less but more critical simulations?
Second, to decide which outcome is better than another, I kind of just calculate the damage done to the enemy + factor * breach count and then pick the largest one. Sometimes it makes excellent decisions but sometimes it seems to be too aggressive. What I mean by aggressive is sending lots of pings in one round. Is there a better way to decide which simulation is better than another?
Note: I’d be happy to hear your thoughts on this topic, feel free to leave a comment down below even if you’re not answering the questions! It’s just a discussion! Thank you guys in advance!
I probably won’t answer any questions, as I see this as a critical part of the competition, but I can give you a few benchmarks to compare from. Up until the last couple of weeks of the season one competition, I was only using 20-30 simulations each turn, much in the ballpark of what you’re doing now. My defensive placements were carefully generated for each simulation so I didn’t feel a need to simulate than one set of defenses per attack. If you’re running EMP simulations, though, those seems to take the longest and are conveniently the ones you can evaluate pretty well outside of the simulator (which paths spend the most time on my side of the map, perhaps?), so if you must cut something down I’d recommend optimizing those.
As for the speed of the simulator, a lot of recent threads went pretty far into how to accomplish this, so I trust you’ll find something to optimize 
. I would check on how efficiently you make expensive function calls though. For instance, do you get the locations of all the encryptors and recalculate what unit has or doesn’t has what shield each frame? Probably could be done a bit quicker.
As for the metrics (picking aggressive pings each time), that can be one of three things: being stopped by an enemy unit you’re not accounting for, flawed metrics, or a bug in the simulator that gives pings an advantage. All three are certainly fixable, but the first one’s the hardest and the last one is the most likely. I’d recommend printing out the results of each simulation and making sure they look reasonable, then trying a few out in the playground to make sure they match.
The top algos have become very good at saving bits and cores into the next round and popping out extra encryptors for perfect planned attacks, that’s what got a lot of algos into the top ten recently, so need to run at least 28 * 2 * 2 simulations to simulate ping/emp for next two rounds, and then what about simulating opponent moves… so 200+ simulations?
I’m stuck at 50 with build in functions, it seems one needs to roll you own pathfinding, i’m seeing around 1ms per path in testing…work in progress… this explains A* pathfinding well:
Thank you so much for the kind reply! Maybe a simulator isn’t as important as I thought since lots of analysis can be done without it. Will verify the correctness of my simulator as well…Much thanks again!
Yeah, it’s kind of frustrating that I’ve stuck at around 20~30 place for a week already… Wow, 1ms is impressive, I tried to memoized the get_range function and replace the Queue with a list but still ended up spending 10ms for each path finding. Maybe I’ll try to implement A* as well. Not sure how much will it speed up though.
If you figure out the pathfinding thing, let us know. I just can’t seem to get the zigzag to work correctly to approach a wall using A*, looking at previous chat perhaps the A* pathfinding is a red herring:sob:
seems there’s some good ideas out there from november:
The way I deal with it is to simply ignore it (kinda). Let me explain. I run A* to find the shortest path and then step in that direction. I then keep track of the the direction I moved (up, down, left, right). Then, when doing A*, if there is a tie in directions (eg up or left) I then pick the one that is not the one I moved last time.
Thus, the zig zag motion has nothing to do with A* finding the shortest path, but you do it outside of the algorithm.
That being said, I don’t necessarily think that implementation will work for you, since you are trying to return the path all in one. One possible solution I see is maybe using a different metric for your f_cost where you add distance based on the last move made, but only if there is a tie. That could work but you’d have to incorporate a bit more into your algorithm.
thx, i think you’re right some fudge is needed… think may have an idea, when putting the 4 adjacent open moves into a*, also force feeding the diagonal moves into A* (vertical forward + horizontal) with 1.41 h cost, would perhaps automatically create the zig zag.
You can fudge it like that, you’ll just need to do some testing and be very careful.
For example, if you have a path and you assign it an f_cost up higher than because they are equal, this will give incorrect behavior down the line unless you remove the fudge on the next position after it. This depends on how you are implementing your algorithm.
So now I found another problem with my simulator. Correct me if I’m wrong. I think one can never make a “full” simulation without coding a new path finding algorithm. Due to the fact that the built in path finding algorithm can only calculate the scenario “from edge to edge”, it can not calculate the scenario where a firewall is destroyed and all information troop need to recalculate a path to edge. I think this feature makes any simulator without a customized path finding algorithm much less useful since it can’t find a weak area to “break through”.
By the way, I found it weird when using the “get_target” function in advanced game state. When I passed in a destructor, it sometimes returns a filter game unit. Not sure if the function isn’t allowed to pass in a firewall unit though… will be nice if someone can answer my dumb questions!
The built-in path finding algorithm can simulate path from any location that doesn’t contain stationary unit.
You can use it like this:
path_finder = ShortestPathFinder()
path = path_finder.navigate_multiple_endpoints(start_location, end_locations, game_state)
I think a check is missing on line 43 of advanced_game_state.py, if I’m reading it correctly. Should probably read like if unit.player_index == attacking_unit.player_index or ((attacking_unit.unit_type == SCRAMBLER or attacking_unit.stationary) and is_stationary(unit)):
The built-in path finding algorithm can simulate path from any location that doesn’t contain stationary unit.
You can use it like this:
This can break the zigzag pattern on occasion. A different pathfinder would be needed to account for this.
I know it can, but it just return a horizontal path to me if I recall it correctly
Yeah so I guess it’s some kind of bug
Yup, to make units walk in a “terminal” way I guess I’ll have to make some adjustment
nice, finally understand the attacking order, it seems get_target() is fairly unoptimized and can be speeded up.
It would seem the existing function line 43 is correct if def get_target(self, attacking_unit): is only called with offensive units
update… terminal-style zig zag paths can be made by A* pathfinding using diagonal jumps (if not blocked) with 1.41 cost, then after soliving the path, going back and fill in the corners of the diagonals. prob not 100.0% but complicated paths are looking very close to the ‘terminal’ style shortest path…
Looks good, but shouldn’t it be going to the top right?
Couldn’t you use the get ideal endpoints function to find the correct position to path to?
I’m still working on mine… so might be wrong
I would be a Really-Bad-Coder if it was going the wrong direction:) was a test from given point to top-left.
The diagonal hack works, but still have a few problems with the zig zag becoming a zag zag when there’s an obstacles. A* is really hard to debug, using the matplotlib scatter() graph really helps find the mistakes, the yellow circles are the search/open circles…
I was thinking since I didn’t want to screw around with the search, id modify the backtracking function to add the terminal “zig-zag” priority. I never thought of the “diagonal-hack” method. Good thinking!