C++ starter code for the CG Spring Challenge 2021. (Totoro / Photosynthesis / Whatever you want to call it)
Algorithm is Chokudai's variant of Beam Search.
Totoro has a lot of high ranking bots with just basic heuristics (if/else conditions), therefore a basic search with some decent eval will get you very far on the leaderboard. Best way to do this is by analysing the game and spot best plays. Doing this will then get you accustomed to the code.
You're meant to improve on the code and optimize it yourself. Bitsets are a personal preference.
Beam Search is about taking n most promissing moves and exploring their future outcomes. This variant however has n (the beam width) starting at 1 and then gradually increase with each iteration.
- Fix the sorting function
- Write the eval / scoring
- Optimize the code. For example a Heap could do a lot more than a vector for states or look up zobrist hash for copying gamestates.
- Reuse states next turn.
- Improve by adding opponent prediction or a separate search
- Fix the time limit conditions.
- You can precompute a lot more than just shadows (see the
initialize()function). For example distances, tree costs and much more.
- Further improve based on strategies listed on the forums: https://www.codingame.com/forum/t/spring-challenge-2021-feedbacks-strategies/190849
Feedback and Suggestions
are very much appreciated. Looking forward to hear from you.