Detecting maze algos

[zigzagninja]

Im making a reactive algo right now, and to my suprise its actually pretty decent. Now my algos biggest weakness are Maze Algos.
I know what I want to do about them if I detect that my opponent uses a maze algo but I only want that strategy to fire if its actually a maze.
So how would I go about detecting whether or not my enemy is a maze algo?

[Isaac]

This is something I have spent a fair bit of time thinking about, and I imagine others have as well. I’ll mention a few options I think could be viable (or have been for me).

1. Check for lines. Simple as that. I won’t go into a ton of detail about how to find them, cause that’s the interesting part :). But, I do it by looking at their units, identifying colinear points, discarding non-horizontal pairs, and then combining nearby points. If there is a long enough line, etc, you can identify a maze (this is just a starter, you can do more to make it more accurate). You could skip the colinear part, but it will get very slow if they have a lot of units.

2. Use clustering and Machine Learning to cluster/identify maze strategies. This is a more difficult and less certain option, but I wanted to bring it up because of my discussion here and the potential for it to identify other strategies as well. I haven’t completed this yet, but it looks promising .

3. Similar to #1, look at their units path and find horizontal lines. This will probably take a bit longer (in turns) to identify because it will only see it after their algo completely finishes building the maze. Alternatively, if you are explicitly looking for maze algos (and not walls) you could maybe (untested) just look at the length of their path. Most mazes have units taking a longer path then most other strategies could have - you’d have to see about the error though, I can think of several cases where this would give a false positive.

4. Check positions you can go. Run the pathing algorithm and if says you only have a couple of points you can pass through, chances are it’s a maze algo. I’m also not sure about the error on this one, untested for this purpose.

These are just some initial thoughts, hope it sparked some ideas :).

[zigzagninja]

interesting ideas, thanks for the help

[KauffK]

One of the things that stymied me when I wanted to do this was that if you’re trying to detect a maze, it’s probably because you hope to deploy something like a ping cannon and race them down. But for this to have a high chance of victory, it really should happen on turn 1 or even turn 0. Waiting until the features of the maze are obvious can make attacking difficult, and some of your defenses may have been destroyed already.

I attempted to use a rather naive method for this which actually had a reasonable amount of success: Look at what rows they build in on turns 0 and 1. The classic “maze” structure ultimately wants solid walls in the first and third rows, and empty space in the second and fourth rows. If they spend most or all of their cores on turn 0 or 1 and haven’t used the third row very much, it is very unlikely that they’re a maze. If they spend all of their cores and the third row is mostly full, they are likely to be in the maze family.

This approach of course suffers from a bunch of false-positives or false-negatives, but if you add enough tuning parameters and try a whole bunch of profiles, you can probably find something that works, and making a decision on turn 0 or 1 can yield a huge advantage vs waiting a few turns.

[zigzagninja]

Hmmm yes I agree, you could also look for if there only using EMPs, a lot of mazes only use EMPs.
I might still go for the waiting a few moves strategie, since if you focus on EMP sniping it should be fine if you wait a few moves.

[kkroep]

I believe this discussion was held in a previous topic. I think you should think of a way to counter EMP lines. Mazes are just a specific way of implementing EMP lines, but it has the same weaknesses and benefits as normal lines for at least the first 10 turns. EMP sniping is possible, but it would only work against crude and very static algos. If you face a more dynamic solution it can backfire.

There are some spectacular algos out there that crush mazes, but for sure it is much easier to program a maze than to counter it. This also holds true for the ping cannon.

Interesting algos that don’t participate in EMP lines themselves but counter them include the aelgoo series, tiny_oracle, and ActorV6. Maybe take a look at some replays of those algos. These algos will be hard to copy though…

I personally deal with EMP lines… by building better EMP lines B-)

[zigzagninja]

Yeah, you’re right, I just lost to someone with an EMP line.
How can I watch other peoples replays?

[kkroep]

Uhm, there are some posts by 8********** with highlight of top algos. You can start there. Otherwise you can watch replays if other people share them. Or you can go to the twitch channel of c1games and take a look at past tournaments. Good luck!

[zigzagninja]

Alright, thanks you’ll see me up on that leaderbord soon B-) (i hope)

[KauffK]

@kkroep

I believe this discussion was held in a previous topic.

Yeppers. @zigzagninja if you want to read a large number of thoughtful responses on mazes from a variety of pretty dedicated players, check out this thread:

Regarding Maze Algos

4 of the top 8 algos in the CB challenge were “maze” algos. And AdrianMargel’s sawtoothV2, the originator of the 9-11-13 maze won it all with a non-adaptive approach. Which leaves me to eat my words: sawtoothV2 builds the same structures in the same order every game and never spends more than 92 cores. Each turn he spawns as many EMPs on [24, 10] as he can. And he just won $2000. Having hit the top8 myself with a maze algo, I wanted to share some thoughts on why I think it’s dominating th…

[zigzagninja]

It actually worked!
My algorithm detected a maze algo (probably way to late but still im proud xD)

heres the game: https://terminal.c1games.com/watch/1375329

It has worked a bunch of times not just this once, eventhough I definitly have to make it better.

[kkroep]

Nice man!

I recommend you to send 3 scramblers instead of one, so they guarantee a blow up (if there are not too many destructors). Also in your example the opponent completely stopped sending anything for some reason? I would be interested to see this work if the maze keeps operating as normal.

[zigzagninja]

Yeah I agree, its weird that he stopped, it usually still works even if the opponent still attacks:

https://terminal.c1games.com/watch/1395816

Also yes good idea, ill switch to 3 scramblers soon, thanks.

[emm]

I totally didn’t copy your stuff…! https://terminal.c1games.com/watch/1424185 (it got a bit confused and wanted to change sides for a moment, but hey - everything worked out just fine in the end, so …^^)
(also, here’s one quite similar to the last match you’ve posted, but my algo apparently didn’t feel like changing strats for this one… https://terminal.c1games.com/watch/1422998)

[zigzagninja]

All good xD, you won anyway so its fine that your algo didnt want to change i guess.
I just wanted to post, that I now changed strategy:
I now make a maze (adaptive) to counter mazes (very effective btw, currently place 11 on global) but it was very weak to ping rushes, so I made a system that detects ping cannons and then it goes back to my other strategy, which was very effective against these.

So its quite funny if I let them play against eachother, since first The_Monster will build a maze, then ListofNoobs will detect a maze algo and build a ping cannon, then The_Monster will detect a ping cannon and change into ListofNoobs stratetgy, if you know what I mean:

11-5-2018-15-20-24.replay (1.7 MB)

Edit:
Wow, I’m 9th right now, didn’t expect it to work this well