How fast does my simulation have to be for, say, GA or beam search?

Hi all, a novice coder here. I thought I’d experiment with simulation and solution space search in Code vs Zombies. On my first try, I was able to simulate around 500 solutions before timeout. This is obviously way too slow… But how fast would I need to be in order to have any chance of success with any kind of state search/metaheuristic solution? I mean very roughly… Are we talking 10 000 nodes or 500 000 nodes? Guess it depends a lot on whether I am doing a blind shotgun search or a GA, right? Any rules of thumb on the needed speed would be greatly appreciated.

A follow-up question: do I have any chance to simulate enough outcomes with Python 3? Have people succeeded in a state space search solution with Python in Code vs Zombies? Please note that I am at a point where my goal is obviously not to challenge the top 10 C++/Java coders here, but just to take first steps on the path of learning about simulation and state search.

EDIT: fixed typo

(and sorry if there is already a similar topic, I was not able to find another one though…)

1 Like

CvZ is one of those games that penalizes slow languages, unfortunately. There are a few (not many, but some) Python3 entries in the top-100 of the game, but none in the top-50. So it’s definitely possible to do something decent in Python but don’t plan on doing something awesome. That said, there are close to 3,000 other players in the leaderboard, so top-100 is nothing to sniff at.

I don’t know for sure how those Python bots work but I’d be amazed if they aren’t doing a simulation and some form of search.

Not sure what a reasonable number of nodes would be for a Python bot. For reference though, my C# bot runs around 250k round simulations each turn (and it’s not even all that good). Don’t forget though, that a good algo in a slow language will beat a bad algo in a fast language most of the time. i.e. what you do is usually more important than how often you do it.

1 Like

Number of simulations required in 100ms depends of the puzzle.

For example, my Hypersonic code can simulate 250k turns in 100ms but my Fantastic bits code can only run 50k turns. For CvZ my C++ code can do 500k turns in 100ms.

1 Like

Another thing about CvZ : the postmortem by eldidou on the forum is pretty explanatory and easy to code, so lots of people have taken this option. I guess most of the top100 are actually following his method which is simulation based.

To get back to your initial question, it is actually possible to have pretty decent simulation in Python. Let’s be clear, you won’t be able to challenge an optimized C++ code BUT, if you are clever and use as much as possible numpy (or other fortran/C based functionalities) you can have a decent time in simulations. I guess you can approach the speed of a good Java code this way. Now the problem is that coding a simulation is hard enough, but having it properly based on numpy vectorization is an additional difficulty :slight_smile:

1 Like