Totoro Beam Search C++ Starter

Anonymous
5,300 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

About

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.

Code

TODO

  • 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.

Thanks!

~ AntiSquid

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content