Tips for heuristic/bot programming contests

Psyho @FakePsyho

Let's make a silly experiment. For every like this post receives in the next 24 hours, I will post one tip for heuristic/bot programming contests. I will start posting these as a thread in ~1h from now. I could talk about those things for days, so bring it on!

Psyho @FakePsyho

This is going to be a long ride 😅 Small disclaimer first: I'm limited to 280 characters per tip. Sometimes it's going to be hard to squeeze 15 years of experience into a single tweet. A lot of details are going to be left out, etc.

Psyho @FakePsyho

#0: Free tip Everyone is unique & has different background. Each one of us struggles with different subjects. Not every piece of advice is going to be applicable for you, but I'll try making all tips as general as possible & mention if something is situation specific.

Psyho @FakePsyho

#1: In a week-long contest there's enough to do ALL of the research during the contest. No matter how inexperienced you are, if you put a lot of effort into a single contest. You have a chance of winning it. This is in contrast to CP contests where you have to train for years.

Psyho @FakePsyho

#2: You never need any advanced math. There is always alternative of writing simulation code. In ~200 contests I've done, I can recall a single instance someone performed better due to math knowledge. Exception: Bayes' theorem. For reference: I don't know calculus 😅

Psyho @FakePsyho

#3: In heuristic ([H] from now on) contests there are only two common techniques that are worth knowing: Beam Search & Simulated Annealing. Rarely, it's useful to have decent experience with Graph Theory, Dynamic Programming, Linear Programming & Flow Problems.

Psyho @FakePsyho

#4: Touch typing is extremely important. If you can't that should be your #1 priority. It takes roughly 10-30h for most. Touch typing gives you an ability to think about other things while coding. Reduces number of bugs, smooths out prototyping, etc.

Psyho @FakePsyho

#5: H (Heuristic) vs B (Bot) contests, which ones are better? Other than different set of standard techniques, the main difference is that H contests give you fast & precise feedback, while B are generally more fun. You'll learn at much faster pace in H contests.

Psyho @FakePsyho

#6: The best sites for contests: H: Topcoder (marathon), AtCoder (AHC) B: CodinGame (there's a contest going on right now!) All sites feature good problems, fair evaluation system & community that talks about solutions post-contest. Some sites might be rough on the UI side ;)

Psyho @FakePsyho

#7: [H] Googling about the problem is generally a waste of time* Good problem design (above sites) means that problem writers made sure that the problems are unique. *there are rare exceptions; it might be useful to research a particular subproblem that exist

Psyho @FakePsyho

#8: For most people, the most limiting skill is prototyping speed. With some experience, you'll always have dozens of ideas that you want to implement. The limiting factor is how quickly can you iterate through them. The faster you go, the quicker you learn about the problem

Psyho @FakePsyho

#9: Best way to get good quickly is to focus on a single contest instead of half-assing many. You won't learn much by only doing basic solutions. The proper learning period starts when you hit a wall and don't know how to proceed. You have to push yourself to get results.

Psyho @FakePsyho

I'm done with food, let's go for some quick Simulated Annealing (SA) tips now: #10: All local-search alternatives to SA are (almost always) bad. Genetic Algorithms, Tabu Search, Ant Colony, etc. Just forgot them. They are not only less effective, but slower to implement.

Psyho @FakePsyho

#11: Why SA? - You can start with Hill Climbing (HC) and convert to SA with 2 additional lines. - Gives you ability of fast dynamic evals - When tweaked properly has higher potential (due to fast evels) than other methods - Allows for very fast iterations

Psyho @FakePsyho

#12: Standard SA: temp schedule: t = t_start * (t_final / t_start) ^ time_passed, where time_passed is in 0..1 acceptance (when min is better): RNG() < exp((cur_result - new_result) / t), where RNG() returns 0..1 uniformly It's the best starting point in almost all cases

Psyho @FakePsyho

#13: Good SA temperature schedule is such where the acceptance rate slowly decreases. If it's stuck on the same acceptance rate value for a long time, it won't be effective.

Psyho @FakePsyho

#14: Things to do when it's easy to stuck in a local optimum - very high temperatures / acc rate - complex transition states - (rarely) kicks - (rarely) soft restarts (restarting temp schedule without solution) - (rarely) multiple runs

Psyho @FakePsyho

#15: Things to do when a lot of states are invalid (due to restrictions) a) add an additional scoring component based on number of collisions that has initial weight 0 and a final weight of infinity b) (if possible) do many short SA runs with high temp on a partial subsolution

Psyho @FakePsyho

#16: Things to do when your eval is very fast: - make sure your RNG is not a bottleneck - make sure your exp function is not a bottleneck - make sure your function that gets current time is not a bottleneck That happens way more often than you may think

Psyho @FakePsyho

#17: Overall priorities for SA: - prototype different transition functions - make eval function very fast (= make it dynamic) - find proper temp schedule (usually 3-4 runs are enough) - test a lot - only when you're done with the above move to other things

Psyho @FakePsyho

#18: Make sure that you constantly update your best result and return your best instead of the final one. I can't tell how many times I saw this mistake. Constantly updating your best results allows you to have a much higher final temperature.

Psyho @FakePsyho

#19: When SA is not great - it's very easy to get stuck in local optima: check #14 for hints - you mix simple transitions with complex ones: have a separate acceptance function for each transition - your eval is very erratic during transtions: you're out of luck

Psyho @FakePsyho

Ok, enough about SA. Contests are essentially simple feedback loops: a) do stuff b) get results c) extract information You can get better by improving any of those areas. The most neglected area by everyone is (b). Let's focus on testing now

Psyho @FakePsyho

#20: Testing is the most neglected aspect of contests by almost everyone. Testing is your way of getting feedback. If your testing is slow you're going to progress very slowly. If your testing is inaccurate, it's going to be very hard to figure out correct next steps.

Psyho @FakePsyho

This will mostly focus on H, as testing in B is very hard and quite often nearly unfeasible. #21: [H] Use a local tester. If you're only using provisional testing for evaluation, you're making everything extremely hard for yourself. You're not saving time, you're wasting it.