Code VS Zombies - Optimization - Puzzle discussion

Puzzles
#56

In what situation do the two descriptions lead to different results?

#57

If Ash kill the zombie first I guess…

#58

How do I access the ‘points’ value in the game? I want to use it to evaluate my algorithms using code, rather than manually recording the scores. Newish to coding so grateful for advice!

#59

Hi all,
I am a freshman in algo. I have just learnt the genetic algo and I saw many people made their models based on ga. I would like to ask, how to apply the ga on such a practical problem. The problems I worked on was like “find the local maximum of a function”. Thanks very much!

#60

Hi,
did you manage to build your model?

#61

Hi, first of all you must have simulation for turns ahead, this means given a moving command for Ash to predict how the game state will look like. This includes moving Ash, moving zombies, destroying zombies, destroying humans, … Also you need a good evaluation function, to be able to compare states.

After that you should decide how to represent the GA. I’m using Chromosomes where each gene is a float between 0.0 and 1.0 and each pair of genes represents a moving command for Ash:
int ashXTarget = MAP_WIDTH * chromosome[0];
int ashYTarget = MAP_HEIGHT * chromosome[1];

Then I’m using the techniques, I’ve described here https://www.codingame.com/blog/genetic-algorithm-mars-lander/ to optimize the commands for Ash.

Good luck and have fun :slight_smile:

5 Likes
#62

Hi Di_Masta,
wow! I just read your blog this morning! I was thinking what a nice algorithm and I followed you!
Thanks for the advice on ga. I will try to make some progress! Thanks again!

1 Like
#63

Instead of cartesian coordinates, use polar coordinates. Given that Ash moves within a radius of 1000 during a turn, it will be easier to generate move commands

4 Likes
#64

Hi,
oh, I see. and in the polar coordinates, the center O should be Ash, right? That would be easier for him to move.
Thanks!

#65

Hi,
I’ve tried many combinations of {population size, crossover rate, mutation rate, elitism count}, but I cannot manage to have it converge on Test 09 Rectangle.
maxGenerations: 1000
PopulationSize: 100,
MutationRate: 0.05,
CrossoverRate: 0.95,
ElitismCount: 5,
For the evaluation function, I set it to 0 if there is no humans left.
Any advice ?

#66

My ElitismCount is 10. My MutationRate is higher (15%). I do not have a maxGenerations parameter: I let the search run for the allocated period of time which gives me 3K generations per second for the Rectangle test case. For crossover, I choose randomly between my two populations for each consecutive move.

Given that it is a very simple test case, it should converge with your parameters. Is it your only failed test case ?

#67

Also you could always use a “fallback” strategy if your GA doesn’t find a solution in the given time period, use a “greedy(non optimal)” approach.

#68

Thanks for the advices
My simulation engine was wrong.
I update it ==> now GA works for everything but Rectangle test case.
As mentioned, I added a fallback to naive algorithm if GA fails.
I get to 425th
I will try to change my crossover: for now it is a random swapPoint; taking [0:swapPoint] from parent 1 and [swapPoint:end] from parent 2

1 Like
#69

how to get the position of ash?

#70

it’s given in the first line of every game turn
image

#71

I’m trying to get started here so that I can begin my path down the optimization tree of the achievements and I’m just not sure what’s already been done, I discussed with somebody in chat today about using beam search and was curious what other peoples’ thoughts were?

1 Like
#72

In this thread there are several strategies explained, I personally used GA: Code VS Zombies - Optimization - Puzzle discussion

#73

Look here for some feedback on the strategies used for this puzzle (mostly MonteCarlo and genetic algorithms). Regarding beam search, this is an interesting idea but I see two potential issues:

  • given Ash movement freedom, the search space is really huge even if you discretize movements.
  • because of the scoring system which favors carnage, good solutions herd zombies first and delay shooting as much as possible, so it’s hard to distinguish the right first moves
1 Like
#74

Bonjour.
Question, Ash tue les Zombies se trouvant dans un rayon de 2000 ou dans un rayon de moins de 2000 (2000-1) ?
Parce qu’il est dit dans l’énoncé :

Si à la fin d’un tour, un zombie se trouve dans un rayon de 2000 unités de Ash, il tire sur le zombie pour le détruire

Mais plus loin on a :

Tout zombie se situant dans un rayon de moins de 2000 unités est détruit

Merci :slight_smile:

#75

Les zombies qui sont dans un rayon de moins de 2000 de Ash meurent. C’est ce que j’ai dans ma simulation et c’est cohérent avec le referee.

2 Likes